1、第五章 無失真信源編碼5.5 實用的編碼技術保存在計算機的存儲介質（磁盤、光盤等）中的文本、數值、圖片、聲音、影像等信息，統稱為計算機文件對于計算機文件一般都不允許在壓縮過程中丟失信息，也就是說對于這類文件的壓縮必須是“透明”的利用消息或消息序列出現概率的分布特性，使概率和碼字長度匹配，叫做統計編碼或概率匹配編碼，統稱為熵編碼。對離散無記憶平穩信源，必須： 準確得到字符概率 ； 對各字符的編碼長度都達到它的自信息量。iP aIf Youth，throughout all history， had a champion to stand up for it； to show a doubting

2、 world that a child can think；and， possibly， do it practically； you wouldnt constantly run across folks today who claim that a child dont know anything. - Gadsby by E.V.Wright, 1939. 無需為解壓縮預先保存任何信息，整個編碼是在壓縮和解壓縮過程中動態創建的，而且自適應編碼由于其符號頻率是根據信息內容的變化動態得到的，更符合符號的局部分布規律，因此在壓縮效果上比靜態模型好許多。自適應模型將自適應模型與霍夫曼編碼結合起來

3、的問題是重建霍夫曼樹是一個非常昂貴的過程。為了讓自適應方案高效，有必要在每一個字符出現之后調整霍夫曼編碼。直到霍夫曼編碼第一次開發的 20 年之后，執行自適應霍夫曼自適應霍夫曼編碼編碼的算法都沒有發布。即使在現在，最好的自適應霍自適應霍夫曼編碼夫曼編碼算法仍然相當耗時間和金錢。5.5.1 游程編碼游程長度(RL: Run Length,簡稱游程或游長)： 由字符(或信號采樣值)構成的數據流中各字符重復出現而形成的字符串的長度。用二進制碼字給出形成串的字符、串的長度及串的位置等信息，以此來恢復出原來的數據流。是在控制論中對于二值圖像而言是一種編碼方法，對連續的黑、白像素數(游程)以不同的碼字進行

4、編碼。 游程長度編碼(RLC)：基本的RLC壓縮方法：最初出現在 IBM 3780 BYSYNC (Binary Synchronous Communication)通信協議中?；镜腞LC數據結構：符號碼標識碼游程長度數 據 流基本的RLC的數據結構游程編碼的壓縮效能平均重復長度重復出現10次的壓縮比重復出現20次的壓縮比重復出現30次的壓縮比重復出現40次的壓縮比重復出現50次的壓縮比41.0101.0201.0311.0421.05351.0201.0421.0641.0731.11161.0311.0641.0991.1361.17671.0421.0871.1361.1901.250

5、81.0531.1111.1761.2501.33391.0641.1361.2201.3161.429101.0751.1631.2661.3841.538基本的游程編碼壓縮比二值圖像的編碼過程 先對圖像進行統計分別得出白長為 i 的 概率 PiW 和黑長為 i 的概率 PiB， 然后根據霍夫曼原則按RL出現概率來分 配碼字。二值圖像的RLC實為霍夫曼碼的具體應用修正霍夫曼編碼MH編碼規則: RL=063， 用一個相應的結尾碼表示 ; RL=641728，用一個組合基干碼加一個補充結尾碼； RL(白)=128, 補充結尾碼為0(白)=00110101, 其編碼為: 10010 | 00110

6、101 RL(白)=129, 補充結尾碼為1(白)=000111, 其編碼為: 10010 | 000111 規定每行都從白游程開始，若實際掃描由黑開始，則 需在行首加零長度白游程；每行結束要加同步碼EOL。算術編碼的基本原理設一個信源，它有兩個符號a和b，出現的概率分別是p和1p，設有一個基準區域0，1，對它進行劃分，以便與信源輸出序列相對應。abp1aabap1p+p(1-p)bbabaabap2bbab圖A 符號序列與區域劃分示意例ab0.81aaba0.810.96bbabaaba0.64bbabaaabab0.810.960.64bbaaba0.5120.7680.9920.928b

7、bbbaaabbaab設一個信源，它有兩個符號a和b，出現的概率分別是0.8和0.2，有3個符號輸出時，符號序列與區域劃分的對應關系。圖B 3符號輸出時的 符號序列與區域劃分示意編碼字符串 aabaa對應的區域為0.512，0.59392)該區域的二進制表示0.1000001，0.1001100 )二進制數0.1001輸出編碼 1001對于這個信源：對于這個信源：H（X）=0.7219Huffman編碼:算術編碼:%19.72%24.90平均碼長 R=0.8平均碼長 R=1相比Huffman編碼，算術編碼的編碼效率有明顯提高。對于長序列，理論上算術編碼可以達到信源的熵。多元符號編碼定理輸入符號

8、串 s 取自符號集 ， mmppprrrS,2121s 后跟 ri (riS)擴展成符號串 sri ,空串記做 , 只有一個符號 ri 的序列就是 ri 。 碼字刷新： F(sri) = F(s)+P(s)F(ri) 區間刷新： p(sri) = p(s)p(ri)其中:11)()(ikkispsP是符號的累積概率。初始條件為C( )=0, A( )=1和P( )=0, p( )=1 。符號串每一步新擴展的碼字 C(sai) 都是由原符號串的碼字 C(s) 與新區寬度 A(sai) 的算術相加而得?！八阈g碼算術碼”的由來的由來例例設某信源取自符號集 S=a,b,c,d,e,! , 各符號概率和

9、初始區間如表。字符概率累積概率區間范圍a0.200,0.2)b0.10.20.2,0.3)c0.10.30.3,0.4)d0.30.40.4,0.7)e0.20.70.7,0.9)!0.10.90.9,1.0)設待編碼的字符串為單詞“dead”，編碼器和解碼器都知道區間初值為0,1。6元信源的算術編碼過程C(sai),C(sai) +A(sai)A(sai)初始值0, 1)1.0編完 d 后0.4, 0.7)0.3編完 e 后0.61, 0.67)0.06編完 a 后0.61, 0.622)0.012編完 d 后0.6148, 0.6184)0.0036編完 ! 后0.61804, 0.618

10、4)0.00036編碼過程如圖所示編碼端無需發送最后的區間范圍 0.61804, 0.6184) 實際上只要發送其間的某一個值即可, 如0.6181 。解碼端收到0.6181，得知區間范圍為0.4, 0.7) ，立即解得第一個字符為d，此后解碼區間由初始0,1)變為0.4, 0.7)。得到這一范圍后，再對所有字符按照公式計算,并與最終的區間范圍0.61, 0.67) 相比較,得出第二個字符為e。依此類推，解碼器就唯一地解出字符串“dead！”。解碼過程算術編碼過程:依據字符的發生概率對碼區間的分割過程(即子區間寬度與正編碼字符發生概率相乘的過程)。算術解碼過程:只需知道最終編碼區間中的某一個值

11、就可以解碼。算術編碼每次遞推都要做乘法，而且必須在一個信源符號的處理周期內完成，有時難以實時，為此采用了查表等許多近似計算來代替乘法。小結： 二進制編碼二進制編碼編碼對象是二元序列編碼對象是二元序列:符號概率較小者為p(L)=2-Q形式, 以右移Q位代替乘2-Q;符號概率較大者為p(H)=1-2-Q形式, 以移位和相減代替;從而算術編碼的迭代公式在具體實現時的計算格式為： 碼字刷新： C= C+P(ai)A 區間刷新： A= p(ai)A 有限長寄存器C實現C(s): 存在進位問題, 采用插入“填充位”解決, 對編碼效 率略有影響; 有限長寄存器A來實現A(s)。實際中只能用令 S=H,L,并

12、設 p(L)=2-Q, p(H)=1-2-Q, 則P(H)=0, P(L)=1-2-Q 。 對子區間寬度A(s)做迭代運算: A(sL)=A(s)2-Q(s) (右移Q位) A(sH)=A(s)- A(sL) (X 表示X的小數點后取q位) 對碼字C(s)做迭代運算： C(sH)=C(s) C(sL)=C(s)+A(sH)有限精度、不做乘法且假設Q(s)已經估計出的二進制算術編碼的具體步驟如下: 初始化： , ;00.000qC 個10.111qA 個 如果A(sx)0.100, 則A、C重復左移，直到A 0.100為止(即保持A(s)的小數點后的第1位總是“1”); 如果緊靠C的小數點前有連

13、續v個“1”,則緊靠小數點前插 入1個“0”(填充位); 按上述步驟對字符串中所有字符進行迭代運算,直到最 后一個字符輸出C(s)代碼。參數q與Q的選擇直接關系到編碼器精度。例對字符串“01000101”來說，H符號是“0”，L符號“1”：取q=4，v=3和Qmax=3，并假定由某個編碼模型提供的Q(s)值為(2,1,2,2,3,1,1,2),對其進行算術編碼。已編碼的字符串編碼符號x有限精度附加操作Q(s)A(s)C(s)A(s 1)A(s 0)C (sx)空020.11110.00000.00110.11000.00000011左移1位10.1100 0.11000.00000.11000

14、.01100.01100.011001020.11000.11000.00110.10010.110001001000左移1位20.10010.11100.11001.10000.00100.01110.11000100030.11101.10000.00010.11011.1000010000100011左移1位10.11010.11001.100011.11100.01100.01111.1111010001010001001000100左移1位,填充進位10.11000.110011.1110111.11001110.11000.01100.011011.1110010001001000

15、1011左移2位20.11000.11001110.1100111101.01000.00110.10011111.0101字符串 s =“01000101” 可由最終子區間0.11110101, 0.11111)表示, 編碼端傳送碼字“1111011” 即可，碼長7位。算術編碼最鮮明的特點： 效率高對于大部分黑白文件傳真數據：對一個具體序列:平均編碼效率約為98.5%看其概率分布是否集中2-Q附近, 在p= 2-Q處, 編碼效率為100%, 實際應用中的關鍵問題就是要選擇合適的概率模型, 使大部分條件概率接近于2-Q?；谧值涞膲嚎s方法將長度不同的符號串(短語)編碼成一個個新單詞, 用其形成

16、一本短語詞典的索引。若單詞的碼長短于它所替代的短語，就實現了數據的無損壓縮，而且該短語字典都是自適應生成的。LZ編碼的基本原理1977 年，以色列人 Jacob Ziv 和 Abraham Lempel 發表了論文“順序數據壓縮的一個通用算法”(A Universal Alogrithem for Sequential Data Compression)。1978 年，他們發表了該論文的續篇“通過可變比率編碼的獨立序列的壓縮”(Compression of Individual Sequences via Variable-Rate Coding)。在這兩篇論文中提出的兩個壓縮技術被稱為LZ7

17、7LZ77和LZ78LZ78。簡單地說LZ碼思路完全不同于從Shannon到Huffman到算術壓縮的傳統思路，人們將基于這一思路的編碼方法稱作“字典”式編碼。LZ碼字典式編碼不但在壓縮效果上大大超過字典式編碼不但在壓縮效果上大大超過了了Huffman編碼，編碼，而且易于實現，其壓而且易于實現，其壓縮和解壓縮的速度也異常驚人縮和解壓縮的速度也異常驚人。LZ編碼一例英文字母和符號串編碼成12位碼字的壓縮字符串表。符號串符號串碼字碼字A1AB2AN3AND4AD5Z6D7DO8DO空空9空空10空空空空11空空空空空空12空空空空空空空空13空空空空空空空空空空14空空空空空空空空空空空空1501

18、60017000180000190000120$4095LZ碼的特點 能有效地利用字符出現頻率冗余度、字 符重復性和高使用率模式冗余度，但通 常不能有效地利用位置冗余度； 算法是自適應的，無需有關輸入數據統 計量的先驗信息，運算時間正比于消息 的長度； 對每一消息的起始端的壓縮效果很差， 對整段消息壓縮得更好。 如果信源非均勻且冗余度特性隨消息而 變動，那么消息長度遠大于算法實現的 自適應范圍，壓縮效率就會降低。現代漢語詞典中的實例LZ77的編碼原理從當前壓縮位置開始，考察未編碼的數據，并試圖在滑動窗口中找出從當前壓縮位置開始，考察未編碼的數據，并試圖在滑動窗口中找出最長的匹配字符串，如果找到

19、，則進行步驟最長的匹配字符串，如果找到，則進行步驟2，否則進行步驟，否則進行步驟3。輸出三元符號組輸出三元符號組(off,len,c)。其中。其中off為窗口中匹配字符串相對窗口邊界為窗口中匹配字符串相對窗口邊界的偏移，的偏移，len為可匹配的長度，為可匹配的長度，c為下一個字符。然后將窗口向后滑動為下一個字符。然后將窗口向后滑動len+1個字符，繼續步驟個字符，繼續步驟1。輸出三元符號組輸出三元符號組(0,0,c)。其中。其中c為下一個字符。然后將窗口向后滑動為下一個字符。然后將窗口向后滑動len+1個字符，繼續步驟個字符，繼續步驟1。1984年，Terry Welch發表了名為“高性能數據

20、壓縮技術”(A Technique for High-Performance Data Compression)的論文，實現了LZ78算法的一個變種 LZW。LZW保留了保留了LZ碼的自適應性能，碼的自適應性能，壓壓縮比也大致相同，其顯著特點是邏輯縮比也大致相同，其顯著特點是邏輯簡單、硬件實現廉價、運算速度快簡單、硬件實現廉價、運算速度快。LZW編碼LZW算法將輸入字串映射成定長(通常為12位)的碼字,其串表具有“前綴性”:表中任何一個字符串的前綴字符也在表中。若由某個字符串和某個單字符K 所組成的字符串K 在表中，則 也在表中。 K 叫做前綴串的擴展字符。LZW算法描述初始化：將所有的單字符

21、串放入串表 讀第一個輸入字符 前綴串 Step：讀入下一個輸入字符K If 沒有這樣的K(輸入已窮盡): 碼字() 輸出; 結束。 If K 已存在于串表中: K ; repeat Step.else K不在串表中: 碼字() 輸出; K 串表; K ; repeat Step.例對一個最簡單的3字母字符串“ababcbababaaaaaaa”作LZW編碼。字串表另一種形式a 1a 1b 2b 2c 3c 3ab 41b 4ba 52a 5abc 64c 6cb 73b 7bab 85b 8baba 98a 9aa 101a 10aaa 1110a 11aaaa 1211a 12輸入符號 a

22、b ab c ba bab a aa aaa a輸出符號 1 2 4 3 5 8 1 10 11 1加進表中 5 7 9 11 的新字串 4 6 8 10 12LZW算法對各種類型的計算機文件都有壓縮效果:數據類型壓縮比英語課文1.8Cobol文件(8位ASCII碼)26倍浮 點 數 據1.0格式化的科學數據2.12.1系統登錄數據2.6程序源代碼2.3目標代碼1.5LZW對不同數據類型的壓縮結果對不同數據類型的壓縮結果LZW編碼待壓縮的信息為DAD DADA DADDY DADO.待壓縮的信息為DAD DADA DADDY DADO.待壓縮的信息為DAD DADA DADDY DADO.4

23、信道及信道容量信道是指信息傳輸的通道，包括空間傳輸和時間傳輸。關于信道的主要問題信道的建模信道傳輸信息的能力在有噪信道中能不能實現可靠傳輸？ 4.1 信道的分類4.2 離散單符號信道的數學模型 4.2.1 離散單符號信道的數學模型 信道的輸入、輸出都取值于離散符號集，且都用一個隨機變量來表示的信道就是離散單符號信道。條件概率 P(y/x) 描述了輸入信號和輸出信號之間統計依賴關系。反映了信道的統計特性。信道矩陣設離散單符號信道的輸入隨機變量為 ，其所有可能的取值為且 輸出隨機變量為Y，其所有可能的輸出值為yj， 由于信道中存在干擾，因此輸入符號在傳輸中會產生錯誤，這種信道干擾對傳輸的影響可用傳

24、輸概率Xix1,2, ,ir1,2, ,jsjip y xjijip y xP Yy Xx11211112222212ssrrrsrp y xp y xp y xxp y xp y xp y xxPxp y xp y xp y x二元對稱信道多元信道前向概率后向概率4.2.2 信道容量的概率定義：定義： 消息在信道的傳輸過程中，單位時間內所傳輸的信息量，消息在信道的傳輸過程中，單位時間內所傳輸的信息量，稱為消息在信道中的稱為消息在信道中的，簡稱為，簡稱為，通常用，通常用R表示。表示。 當信息量單位用比特、時間單位為碼元或符號當信息量單位用比特、時間單位為碼元或符號或符號序列等所占用的時間時，信

25、息傳輸速率或符號序列等所占用的時間時，信息傳輸速率的量綱為比特的量綱為比特/碼元（或比特碼元（或比特/符號、比特符號、比特/符號符號序列等），通常用序列等），通常用R表示；表示； 當信息量單位用比特、時間單位為秒時，信息當信息量單位用比特、時間單位為秒時，信息傳輸速率的量綱為傳輸速率的量綱為 bit/s 或或bps（bit per second），），通常用通常用Rt表示。表示。 4.2.2 信道容量的概率噪聲的存在，使得傳輸中的錯誤不可避免，但是只要傳輸速率低于某一個值，理論上在噪聲背景下進行可靠傳輸(錯誤概率可低于任意給定值)仍然是可能的平均互信息是接收到輸出符號集Y后所獲得的關于輸入符號

26、集X的信息量。 稱為信道疑義度。而平均互信息稱為信道的信息傳輸率。信息傳輸速率信道容量：進行可靠傳輸的最高速率 H X Y;/RI X YH XH X Y比特 符號1;tRI X Yt max;p xCI X Y二元對稱信道的信道容量4.2.3 幾種特殊信道的信道容量具有擴展性能的無損信道具有歸并性能的無噪信道具有一一對應關系的無噪無損信道1 具有擴展性能的無噪信道 此信道的舉例如右圖所示。此信道的舉例如右圖所示。 nm，輸入，輸入X的符號集個的符號集個數小于輸出數小于輸出Y的符號集個的符號集個數。其信道矩陣如下：數。其信道矩陣如下：)/()/(00000000)/()/()/(0000000

27、0)/()/()/(3837262524131211xypxypxypxypxypxypxypxyp 雖然信道矩陣中的元素不全是雖然信道矩陣中的元素不全是“1”或或“0”，但由于每列中，但由于每列中只有一個非零元素：只有一個非零元素： 已知已知Y后，后，X不再有任何不確定度，損失熵不再有任何不確定度，損失熵 H(X/Y)=0， I(X;Y)= H(X) -H(X/Y)= H(X) 。 例如，輸出端收到例如，輸出端收到y2后可以確定輸入端發送的是后可以確定輸入端發送的是x1，收到，收到y7后可以確后可以確定輸入端發送的是定輸入端發送的是x3，等等。，等等。 接收到符號接收到符號Y后，對發送的符號

28、后，對發送的符號X是完全確定的，損失熵為是完全確定的，損失熵為零，但噪聲熵不為零。這類信道被稱為有噪無損信道。零，但噪聲熵不為零。這類信道被稱為有噪無損信道。 若信道的傳遞矩陣中每一列有一個也僅有一個非零元素時，若信道的傳遞矩陣中每一列有一個也僅有一個非零元素時，該信道一定是有噪無損信道，其平均互信息等于信源熵。該信道一定是有噪無損信道，其平均互信息等于信源熵。即信道容量為即信道容量為 與一一對應信道不同的是，此時輸入端符號熵小于輸出端與一一對應信道不同的是，此時輸入端符號熵小于輸出端符號熵，符號熵， H(X) m，輸入，輸入X的符號集個數大于輸出的符號集個數大于輸出Y的符號集個數。其的符號集個數。其信道矩陣如下：信道矩陣如下：100010010001001 信道矩陣中的元素非信道矩陣中的元素非“0”即即 “1” ，每行僅有一個非零元，每行僅有一個非零元素，但每列的非零元素個數大于素，但每列的非零元素個數大于1： 已知某一個已知某一個xi后，對應的后，對應的yj完全確定，信道噪聲熵完全確定，信道噪聲熵H(Y/X)=0。 但是收到某一個但是收到某一個yj后，對應的后，對應的xi不完全確定，信