信息傳輸基礎(chǔ)06

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

計(jì)算機(jī)文件的冗余度類型：

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

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

A：構(gòu)成碼字的符號(hào)集a：碼元、符號(hào)

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

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

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

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

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

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

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

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

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