【正文】 源符號出現(xiàn)的概率大小進(jìn)行排序，出現(xiàn)概率大的分配短碼，反之則分配長碼。 （ 2）把符號序列分成上下兩部分，使上下兩部分的概率和相等或接近相等。 （ 4）重復(fù)上述步驟，直到每個(gè)子序列只包含一個(gè)符號為止。假設(shè)在編碼之前，每種字符出現(xiàn)的概率已由某種模型統(tǒng)計(jì)出來，用 字符 出現(xiàn)次數(shù) 來表示，具體值分別為： a8， b6， c3， d7， e4， f3， g4， h5 32 a 8 d 7 b 6 h 5 e 4 g 4 c 3 f 3 a 8 d 7 b 6 ——— h 5 e 4 g 4 c 3 f 3 (a)第一步 (b)第二步 解 ： 首先將信源符號按概率遞減順序排列，形成圖（ a）所示結(jié)果，然后，再把符號序列分成上下兩部分，使上下兩部分的概率和相等或接近相等，形成圖（ b）所示結(jié)果。 33 最后再重復(fù)第二步，不斷對子符號序列進(jìn)行劃分，最后得到一棵二叉樹，如圖 (c)所示。 信源字符序列 S的編碼總位數(shù) L等于每種字符編碼位數(shù)與字符出現(xiàn)次數(shù)乘積的和 ，即： L=2 8＋ 3 6＋ 4 3＋ 3 7＋ 3 4＋ 4 3＋ 3 4＋ 3 5 ＝ 118（位） 如果直接用 ASCII碼，則要用 40 8＝ 320位。 35 Huffman編碼 其編碼思想與 ShannonFano編碼方法基本一致，但構(gòu)造二叉樹的方法則相反，不是自上而下，而是自下而上、從樹葉到樹根生成二叉樹。 36 例如，對于信源 其編碼過程如下： x1 x2 x3 x4 x5 x6 X= 最后得到的編碼為： x1 – 01， x2 – 10， x3 11， x4 – 000， x5 0010， x6 0011。 ? 信源符號及其概率如下： ? 求其 Huffman編碼，信息熵及平均碼長。 Huffman編碼的基本原理是按信源符號出現(xiàn)的概率大小進(jìn)行排序，出現(xiàn)概率大的分配短碼，出現(xiàn)概率小的則分配長碼。用到兩個(gè)基本的參數(shù)，一是信源符號的概率，二是信源符號對應(yīng)的編碼區(qū)間。 ?? ?k1j 1jp41 4）當(dāng)輸入符號為 xi（ xi 對應(yīng)信源符號集 X中的第 k個(gè)符號），可按以下公式定義新的子區(qū)間 Ii，并計(jì)算區(qū)間長度 di。如果全部輸入完畢，則當(dāng)前區(qū)間Ii=[li,ri)中的任意數(shù)就是所需的編碼。如果輸入序列為S=a2a1a3a2a4…… 。 ２）運(yùn)算中出現(xiàn)溢出是一個(gè)明顯的問題，但多數(shù)機(jī)器都有16位、 32位或者 64位的精度，因此該問題可使用比例縮放方法解決。 44 行程編碼 行程編碼（ RLE）通過統(tǒng)計(jì)信源符號中的重復(fù)個(gè)數(shù)，并以重復(fù)個(gè)數(shù) 重復(fù)符號 格式來編碼。其基本思想是：按行存儲(chǔ)一個(gè)顏色值和相同色值的像素個(gè)數(shù)。 (a) 圖像示例（ 16 8像素） 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 (b) 示例圖像的像素值（ 16 8像素） 連續(xù)相同色塊圖像與像素值示例 16 0 2 0 11 1 3 0 2 0 1 1 13 0 2 0 1 1 13 0 2 0 1 1 13 0 2 0 11 1 3 0 16 0 16 0 (c) RLE編碼 45 說明： RLE壓縮編碼尤其適用于計(jì)算機(jī)生成的圖像，對減少圖像文件的存儲(chǔ)空間非常有效。 46 詞典編碼 詞典編碼主要是利用編碼數(shù)據(jù)本身存在字符串重復(fù)特性來實(shí)現(xiàn)數(shù)據(jù)壓縮的。詞典編碼又可分為兩類： 第一類詞典編碼的思想 是：查找正在壓縮的字符序列是否在以前輸入的數(shù)據(jù)中出現(xiàn)過，然后用已經(jīng)出現(xiàn)過的字符串替代重復(fù)的部分，并將指向重復(fù)字符串的指針作為輸出編碼。 47 第二類詞典編碼的思想 是：從輸入的數(shù)據(jù)中創(chuàng)建一個(gè)由短語組成的 “ 編碼詞典 ” ，編碼數(shù)據(jù)過程中當(dāng)遇到已經(jīng)在詞典中出現(xiàn)的 “ 短語 ” 時(shí)，編碼器就輸出這個(gè)詞典中短語的 “ 索引號 ” ，而不是短語本身，如下圖。 預(yù)測編碼 1） 預(yù)測編碼的基本概念 預(yù)測編碼是數(shù)據(jù)壓縮的重要技術(shù)原理之一，它是根據(jù)離散信號之間的空間或時(shí)間相關(guān)性，利用前面的一個(gè)或多個(gè)信號對下一信號進(jìn)行預(yù)測，然后對實(shí)際值和預(yù)測值的差進(jìn)行編碼。 49 2） DPCM—— 差分脈沖編碼 DPCM ： Differential Pulse Code Modulation，差分脈沖編碼調(diào)制， 用采樣量化后的樣本值與預(yù)測值之間的差值來編碼 。 s(k)是 PCM樣本值， se(k1)是 s(k)的預(yù)測值， d(k)是差分信號，即d(k)= s(k) se(k1)。原理 P205 50 3） ADPCM——自適應(yīng)差分脈沖編碼 ADPCM是自適應(yīng)量化和自適應(yīng)預(yù)測方法的總稱，是對 DPCM方法的進(jìn)一步改進(jìn)，通過調(diào)整量化步長，對不同頻段設(shè)置不同的量化字長，使數(shù)據(jù)得到進(jìn)一步的壓縮。 根據(jù)信號分布不均勻的特點(diǎn)，使系統(tǒng)具有隨輸入信號的變化而改變量化區(qū)間的大小，以保持輸入量化器的信號基本均勻的能力。 52 變換編碼 先對信號進(jìn)行域變換，以尋求更大的信號獨(dú)立性，減少相關(guān)性。數(shù)據(jù)編碼過程分為三步，即 變換、變換域采樣和量化編碼 。 常用的變換有 KLT、 DCT、 WHT以及 WLT 。用一組不相關(guān)的系數(shù)來表示連續(xù)信號，實(shí)現(xiàn)正交變換。 2） DCT DCT（ Discrete Cosine Transform）是離散余弦變換的簡稱。 54 DCT變換公式如下： ? ? ? ? ? ? ? ?? ??????????? ???????? ???1010 212cos212cos 2 NxNyv πNyu πNxx,yfNvEuEvuC ，其中： N為所劃分圖像方陣的行列數(shù)，一般 N=8； x、 y：原圖像方陣內(nèi)某個(gè)數(shù)據(jù)的坐標(biāo)位置，取值為 0～ N1； f(x,y)代表原圖像數(shù)據(jù)方陣內(nèi)的某個(gè)數(shù)值； u、 v： DCT后矩陣內(nèi)某個(gè)數(shù)值的坐標(biāo)位置，取值為 0～ N1； C(u,v) 代表 DCT變換后矩陣內(nèi)的某個(gè)數(shù)值； 當(dāng) u=0且 v=0時(shí)， E(u) = E(v) = 1/； 當(dāng) u0或 V0時(shí)， E(u) = E(v) = l 。 基本思想為： 對于圖像壓縮，首先將輸入值按 4 x 2分成小塊，分別進(jìn)行實(shí)時(shí)快速哈達(dá)瑪特變換。這樣就能更有效地區(qū)分出信號和噪波，從而達(dá)到更有效地進(jìn)行自適應(yīng)降噪的目的。是空間（時(shí)間）和頻率的局部變換。 57 混合編碼 混合編碼不是一類原理性編碼方案，是兩種或兩種以上相關(guān)編碼方法優(yōu)點(diǎn)與特長的混合應(yīng)用。 58 其它編碼 主要包括分形編碼、矢量量化編碼、子帶編碼等獨(dú)具特色編碼方法。 分形編碼 是一種以分形幾何學(xué)為理論基礎(chǔ)的編碼方法，它利用分形幾何中自相似的原理來實(shí)現(xiàn)數(shù)據(jù)壓縮的。 59 2）矢量量化編碼 矢量量化編碼利用相鄰圖像數(shù)據(jù)間的高度相關(guān)性，將輸入圖像數(shù)據(jù)序列分組，每一組由 n個(gè)數(shù)據(jù)構(gòu)成一個(gè) N維矢量，一起進(jìn)行編碼，即一次量化多個(gè)點(diǎn)。其 基本思想 是，依據(jù)語音和圖像信號可以劃分為不同的頻域段，而人眼對不同頻域段的敏感程度不同的特性，將要壓縮的信息分離成高低不同的兩個(gè)頻帶（子帶），再根據(jù)頻帶的特性分別進(jìn)行量化和編碼，完成對信息的編碼壓縮。 60 61 在數(shù)據(jù)壓縮方法中 ,有損壓縮具有 ( )的特點(diǎn)： A. 壓縮比大 ,不可逆 ,不可逆 ,可逆 ,可逆 ? 衡量數(shù)據(jù)壓縮技術(shù)性能好壞的重要指標(biāo)是（）。壓縮此較??； 另一種是 基于 DCT(離散余弦變換 )的 有失真壓縮算法 ，壓縮比可以很大，這種壓縮算