信息傳輸基礎06

4統(tǒng)計編碼統(tǒng)計編碼保存在計算機的存儲介質（磁盤、光盤等）中的文本、數(shù)值、圖片、聲音、影像等信息，統(tǒng)稱為計算機文件對于計算機文件一般都不允許在壓縮過程中丟失信息，也就是說對于這類文件的壓縮必須是“透明”的利用消息或消息序列出現(xiàn)概率的分布特性，使概率和碼字長度匹配，叫做統(tǒng)計編碼或概率匹配編碼，統(tǒng)稱為熵編碼。對離散無記憶平穩(wěn)信源，必須：①準確得到字符概率；②對各字符的編碼長度都達到它的自信息量。冗余度信源X的冗余度（redundancy）為離散無記憶信源的冗余度隱含在信源符號的非等概分布之中。數(shù)據(jù)壓縮是要去除或減少冗余度，所以只要信源不是等概分布，就存在數(shù)據(jù)壓縮的可能。這是統(tǒng)計編碼的基礎。4.1基本原理

計算機文件的冗余度類型：

1.字符分布2.字符重復3.高使用率模式4.位置冗余字符分布字符重復高使用概率位置冗余主要內容1基本原理2霍夫曼編碼3游程編碼4算術編碼5基于字典的編碼6哥倫布編碼§4.1基本原理編碼器的數(shù)學描述變長碼的基本分析唯一可譯碼的存在唯一可譯碼的構造§4.1.2編碼器的數(shù)學描述其中，X：消息集x：信號單元、消息

W：代碼、碼組、碼書w：碼字

A：構成碼字的符號集a：碼元、符號

編碼就是將每個消息依照固定的碼表，用不同的碼字來代表?！褚苑柤疉構成碼書W?！窠南⒓酱a字集的一種映射，即X～W。這樣的碼稱為分組碼或塊碼。要實現(xiàn)無失真信源編碼，必須滿足：1.無失真。2.有效。例4-1假設用構成代碼W到A2的映射建立X與W的映射關系如果為一個模擬信號，其實編碼器就是一個量化器例：英文電報有32個符號（26個英文字母加上6個字符）。若對其進行二元編碼，則顯然，對單個符號的等長編碼效率極低?？蓪π旁捶栃蛄羞M行等概定長的編碼。當N足夠大，可做到幾乎不失真編碼。離散信源X，其信息熵為，用含m個字符的碼符號集對N長信源符號序列進行等長編碼，若滿足則當N足夠大時可實現(xiàn)無失真編碼。其中，當X為離散無記憶信源時，；當X為離散平穩(wěn)信源時，為信源的極限熵；

等長編碼定理§4.1.3變長碼的基本分析對于一個消息集合中的不同消息，采用不同長度的碼字表示采用變長碼可以提高編碼效率，即對相同的信息量所需的平均編碼程度可以短一些基本思想一般離散無記憶信源輸出的各消息（符號）的概率是不相等的，若對應概率大的，出現(xiàn)機會多的采用較短的碼字；而對于概率小的，出現(xiàn)機會少的采用較長的碼字。這樣，從整個信源來看，編成的信源編碼的平均碼長最短，同時實現(xiàn)了與信源統(tǒng)計特性相匹配。1843年，莫爾斯（Morse）發(fā)明了莫爾斯電報碼。由于編成的碼字是不等長的，將它傳送至接收端如何正確識別碼字起點。碼字間留有空隙，或者加同步信號，但它直接影響編碼的效率，是不經(jīng)濟的【定義4-1】單義可譯碼若W中任一有限長的碼字序列（即有限長的一串W），可以被唯一地分割成一個一個碼字，就稱為單義可譯例考慮以下幾個變長碼例4-2碼字A不是一一對應的碼字B碼字C對碼E的譯碼要求要等到接收到全部序列，才能從尾開始進行判決，產(chǎn)生了時間上的延時和存儲容量的增加對于碼F【定理4.1Kraft不等式】長度為的m進制唯一可譯碼存在的充分必要條件是

——Kraft不等式●不滿足Kraft不等式的碼肯定不是唯一可譯碼，滿足也不一定就是唯一可譯碼。但只要按這樣的碼長來分配碼組，肯定存在相應的唯一可譯碼。4.1.5唯一可譯碼的存在例：信源對應的二進制編碼長度分別為，（1）不滿足Kraft不等式，所以，不存在滿足這種的唯一可譯碼。（2）滿足Kraft不等式，所以，存在滿足的唯一可譯碼，但滿足的不一定就是唯一可譯碼。例4.3問題：如何來確定碼字的長度？如何在確定了碼字長度后找出唯一可譯碼？由Kraft不等式可知，唯一可譯碼的要求只與碼的結構

有關，與信源的統(tǒng)計特性無關。如果希望編出較高效率的唯一可譯碼，不僅從結構上要求

滿足Kraft不等式，而且要考慮到信源的統(tǒng)計特性，合理而充分地利用信源的統(tǒng)計特性【(按符號)變長編碼定理】對于符號熵為的離散無記憶信源進行m進制不等長編碼，一定存在一種無失真編碼方法，其碼字平均長度滿足●當m=2時，即二進制變長編碼定理：最佳變長編碼的平均碼長此時l又叫作編碼效率，有時又稱為比特率對于m進制的不等長編碼的編碼效率定義為所以定理4.2又可以改為若，就存在有唯一可譯的變長碼，若

，則不存在唯一可譯的變長碼。平均碼長的界定定理告訴我們，一個無記憶離散信源A給定了，就意味著其統(tǒng)計特性已知，則信源的熵值已經(jīng)確定了，那么這個唯一可譯碼長l的下界也就隨之確定了有了平均碼長，就可以進行碼字設計例4.4要使碼字唯一可譯§4.1.5唯一可譯碼的構造唯一可譯碼的基本要求對碼字序列能做出唯一正確的分割碼字非續(xù)長【定義4.2】若W中任一碼字都不是另外一個碼字的字頭，則W就叫做非續(xù)長碼或異字頭碼非續(xù)長碼不一定不是單義可譯碼2進制碼樹異字頭碼非異字頭碼碼組中所有的碼字均只對應地配置在終端節(jié)點上異字頭碼生成規(guī)律按照Kraft不等式的要求，對n個消息分配了編碼長度，即可用二進制碼樹來生成異字頭碼，生成規(guī)律是：

從根出發(fā)開始生出2枝；每一枝用一個碼元來表示枝盡節(jié)來，節(jié)外生枝；在第級端節(jié)點（級節(jié)點共有個）上，配置信號單元從根開始直奔對應的端節(jié)點，沿途（聯(lián)枝）所遇到的碼元

所構成的符號，即為對應于該信號單元的碼字。主要內容1基本原理2霍夫曼編碼3游程編碼4算術編碼5基于字典的編碼6哥倫布編碼§4.2霍夫曼編碼1925-1999戴維·霍夫曼，數(shù)學家，計算機科學領域的先驅?；舴蚵簧凶鞒龅闹匾暙I有：有限狀態(tài)機，開關切換電路，綜合程序，信號設計等?；舴蚵贛IT一直工作到1967年。之后他轉入加州大學的SantaCruz分校，是該校計算機科學系的創(chuàng)始人，1970—1973年任系主任。1994年霍夫曼退休?；舴蚵a的編碼定理【定理4.3】在變長編碼中，若各碼字長度嚴格按照所對應符號出現(xiàn)概率的大小逆序排序，則其平均長度為最小。按上述定理可得霍夫曼碼的編碼步驟：1）將信源符號出現(xiàn)概率按照減小的順序排列；2）將兩個最小的概率進行組合相加，并繼續(xù)這一步驟，始終將較高的概率分支放在上部，直到概率達到1.0為止；對每對組合中的上邊一個指定為1，下邊一個指定為0（霍相反，對上邊一個指定為0，對下邊一個指定為1）；畫出由每個信源符號概率到1.0處的路徑，記下沿路徑的0和1；對于每個信源符號都寫出1、0序列，則從右到左就得到了霍夫曼碼例4-6對一個7符號信源，其霍夫曼編碼如圖4-6另例關鍵在每一步，總是將最低概率的兩個符號構成一對兩種霍夫曼編碼的異同對一個5符號信源，其霍夫曼編碼如下圖所示請使用霍夫曼碼進行編碼采用兩種方式進行編碼；

求其平均碼長；兩種霍夫曼編碼的異同引入碼字長度偏離平均碼長的方差的概念：方差小的編碼方法得到的碼字結構更緊湊，碼的變化小，因此，在使用Huffman編碼時，當縮減信源的概率分布重新排列時，應使合并得來的概率和，盡量處于最高位置，這樣可使合并的元素重復編碼次數(shù)減少，減低碼字長度對于平均碼長的偏離方差，減小碼字序列長度的變化§4.2.2信源編碼基本定理例4-7：對于二值圖像，如傳真機，輸出非“黑”即“白”，有