信息論與編碼-第5章.ppt

1、第5章信源編碼,編碼(Coding)分為信源編碼(Source Coding)和信道編碼(Channel Coding)，其中信源編碼又分為無失真信源編碼和限失真信源編碼 一般稱 無失真信源編碼定理為Shannon第一極限定理； 信道編碼定理（包括離散和連續(xù)信道）稱為Shannon第 二極限定理； 限失真信源編碼定理稱為Shannon第三極限定理,第5章信源編碼,信源編碼的主要任務(wù)：由于信源符號之間存在分布不均 勻和相關(guān)性，使得信源存在冗余度，信源編碼的主要任務(wù)就是減少冗余，提高編碼效率 信源編碼的基本途徑： 使序列中的各個符號盡可能地互相獨立，即解除相關(guān)性； 使編碼中各個符號出現(xiàn)的概率盡可能

2、地相等，即概率均 勻化,第5章信源編碼,信源編碼的理論基礎(chǔ)是信息論中的兩個編碼定理： 無失真編碼定理 限失真編碼定理 無失真編碼只適用于離散信源 對于連續(xù)信源，只能在失真受限制的情況下進行限失真編碼,第5章信源編碼,本章主意討論離散信源編碼 首先從無失真編碼定理出發(fā)，重點討論以香農(nóng)(Shannon)碼、費諾(Fano)碼和霍夫曼(Huffman)碼為代表的幾種無失真信源碼 然后介紹限失真編碼定理 最后簡單介紹了一些常用的信源編碼方法,5.1 編碼的定義,X信源符號(Source Symbol)序列 Y碼字(Codeword)序列,信源編碼是指信源輸出的信源符號經(jīng)信源編碼器編碼后轉(zhuǎn)換成另外的壓縮

3、符號(碼字Codeword) 無失真信源編碼：可精確無失真地復(fù)制信源輸出的消息,5.1 編碼的定義,將信源消息分成若干組，即符號序列 xi， xi(xi1xi2xilxiL)， xilA=a1，a2，ai，an 每個符號序列xi依照固定碼表映射成一個碼字yi， yi(yi1yi2yilyiL)， yilB=b1，b2，bi，bm 這樣的碼稱為分組碼(Block Codes)，也叫塊碼 只有分組碼才有對應(yīng)的碼表，而非分組碼中則不存在碼表,5.1 編碼的定義,如果信源輸出符號序列長度L1，信源符號集 A(a1，a2，an) 信源概率空間為,若將信源X通過二元信道傳輸，就必須把信源符號ai變換成由0

4、,1符號組成的碼符號序列，這個過程就是信源編碼,5.1 編碼的定義,碼可分為兩類： 1、固定長度的碼，碼中所有碼字的長度（碼元個數(shù)）都相同，如表5-1中的碼1就是定長碼(Fixed Length Codes) 2、可變長度碼，碼中的碼字長短不一，如表中碼2就是變長碼(Variable Length Codes),5.1 編碼的定義,碼的屬性及分類 (1) 奇異碼(Singular Codes)和非奇異碼 (Nonsingular Codes) 若信源符號和碼字是一一對應(yīng)的，則該碼為非奇異碼, 反之為奇異碼 表5-2中的碼1是奇異碼，碼2是非奇異碼,5.1 編碼的定義,(2) 唯一可譯碼 (Un

5、iquely Decodable Codes) 任意有限長的碼元序列，只能被唯一地分割成一個個的碼字，便稱為唯一可譯碼 (3) 唯一可譯碼中又分為非即時碼和即時碼(Instantaneous Codes)： 如果接收端收到一個完整的碼字后，不能立即譯碼，還需等下一個碼字開始接收后才能判斷是否可以譯碼，這樣的碼叫做非即時碼,5.1 編碼的定義,即時碼：只要收到符號就表示該碼字已完整，可以立即譯碼 即時碼又稱為非延長碼(Undelayed Codes)，任意一個碼字都不是其它碼字的前綴部分，有時叫做異前綴碼(Prefix Codes),5.1 編碼的定義,5.1 編碼的定義,通?？捎么a樹來表示各碼

6、字的構(gòu)成,樹根root,樹枝 orders,節(jié)點 notes,終端節(jié)點 terminal nodes,5.1 編碼的定義,0 1 2,0 1 2 0 1 2 0 1 2,0 1 2,0 1 2,三進制碼樹,5.1 編碼的定義,唯一可譯碼存在的充分和必要條件是各碼字的長度Ki （碼元個數(shù)）應(yīng)符合克勞夫特不等式(Kraft Inequality)：,其中m為進制數(shù)，n為信源符號數(shù)，Ki為各碼字的長度（碼元個數(shù)）,必要性體現(xiàn)在如果是唯一可譯碼，則一定滿足該不等式,充分性體現(xiàn)在如果滿足該不等式，則這種碼長的唯一可譯碼一定存在，但并不表示所有滿足Kraft不等式的碼一定是唯一可譯碼,所以說，該不等式是唯

7、一可譯碼存在的充要條件,5.1 編碼的定義,例5.1 (p.88) 設(shè)二進制碼中ai (a1, a2 ,a3 , a4)，K11，K22，K32，K43，應(yīng)用Kraft定理判斷是否可能是唯一可譯碼,因此不存在滿足這種Ki的唯一可譯碼。,解：,5.1 編碼的定義,1，01，001，000 惟一可譯碼； 1，01，101，010 不是惟一可譯碼； 均滿足克勞夫特不等式,克勞夫特不等式只是用來說明唯一可譯碼是否存在，并不能作為唯一可譯碼的判據(jù)。,5.2 無失真信源編碼,信源輸出符號序列為 X(X1X2XlXL)，其中 Xla1,a2,ai,an 編碼輸出的碼序列(碼字)為 Y=(Y1Y2 Yk YK

8、L) 其中 Ykb1,b2,bj,bm 要求能夠無失真或無差錯地譯碼，同時傳送Y 時所需要的信息率最小 由于Yk平均每個符號的最大信息量為 logm KL長碼字的最大信息量為 KLlogm 則傳送每一個信源符號所需要的信息率平均為,其中,5.2 無失真信源編碼,所謂信息率最小，就是找到一種編碼方式使 最小。 無失真信源編碼定理研究的內(nèi)容: 最小信息率為多少時，才能得到無失真的譯碼？若小于這個信息率是否還能無失真地譯碼？這就是無失真信源編碼定理所要研究的內(nèi)容 定長編碼定理 變長編碼定理,5.2 無失真信源編碼,5.2.1 定長編碼定理 K是定值 且惟一可譯碼 由L個符號組成的、每個符號的熵為HL

9、(X)的無記憶平穩(wěn)信源符號序列X1X2XlXL，可用KL=K個符號Y1，Y2，Yk，YKL，（每個符號有m種可能值）進行定長編碼。對任意 0， 0，只要 則當(dāng)L足夠大時，必可使譯碼差錯小于； 反之，當(dāng) 時，譯碼差錯一定是有限值，而L足夠大時，譯碼幾乎必定出錯,5.2 無失真信源編碼,定長編碼定理含義：,碼字所能攜帶的信息量大于信源序列輸出的信息量，則可以使傳輸幾乎無失真，當(dāng)然條件是L足夠大,反之，當(dāng) 時，不可能構(gòu)成無失真的編碼，也就是不可能做一種編碼器，能使收端譯碼時差錯概率趨于零,而當(dāng) 時，則為臨界狀態(tài)，可能無失真，也可能有失真,5.2 無失真信源編碼,編碼效率 定義 編碼效率總是小于1，且

10、最佳編碼效率為 編碼定理從理論上闡明了編碼效率接近1的理想編碼器的存在性，它使輸出符號的信息率與信源熵之比接近于1,即信源的平均符號熵為HL(X)，采用平均符號碼長為 來編碼，所得的效率,即 只要L足夠大,5.2 無失真信源編碼,5.2.2 變長編碼定理 在變長編碼中，碼長K是變化的 根據(jù)信源各個符號的統(tǒng)計特性，如概率大的符號用短碼，概率小的用較長的碼，使得編碼后平均碼長降低，從而提高編碼效率。（統(tǒng)計匹配）,5.2 無失真信源編碼,單個符號變長編碼定理： 若離散無記憶信源的符號熵為H(X)，每個信源符號用m進制碼元進行變長編碼，一定存在一種無失真編碼方法，其碼字平均長度滿足下列不等式,5.2

11、無失真信源編碼,離散平穩(wěn)無記憶序列變長編碼定理： 對于平均符號熵為HL(X)的離散平穩(wěn)無記憶信源，必存在一種無失真編碼方法，使平均信息率滿足不等式 其中為任意小正數(shù) 由此式可推導(dǎo)出平均碼字長度應(yīng)滿足的不等式 用變長編碼來達到相當(dāng)高的編碼效率，一般所要求的符號長度L可以比定長編碼小得多,5.2 無失真信源編碼,編碼效率總是小于1，可以用它來衡量各種編碼方法的優(yōu)劣 為了衡量各種編碼方法與最佳碼的差距，定義碼的剩余度為,其中 為平均信息率,5.2 無失真信源編碼,例5.2 (p.93) 設(shè)離散無記憶信源的概率空間為 其信源熵為 若用二元定長編碼(0,1)來構(gòu)造一個即時碼：,平均碼長 1 二元碼符號/

12、信源符號,5.2 無失真信源編碼,編碼效率為,輸出的信息率為 R0.811 比特/二元碼符號 長度為2的信源序列進行變長編碼（編碼方法后面討論），其即時碼如下表,5.2 無失真信源編碼,二元碼符號/信源序列,二元碼符號/信源符號,碼字平均長度為,每個符號的平均碼長為,編碼效率,信息效率 R20.961 比特/二元碼符號,5.2 無失真信源編碼,L3 R30.985 比特/二元碼符號 L4 R40.991 比特/二元碼符號,5.2 無失真信源編碼,5.2.3 最佳變長編碼 凡是能載荷一定的信息量，且碼字的平均長度最短，可分離的變長碼的碼字集合稱為最佳變長碼 為此，將概率大的信源符號編以短碼字，將

13、概率小的信源符號編以長碼字 能獲得最佳碼的編碼方法主要有： 香農(nóng)（Shannon）編碼 費諾（Fano）編碼 哈夫曼（Huffman）編碼等,5.2 無失真信源編碼,香農(nóng)（Shannon）碼 (1) 將信源消息符號按其出現(xiàn)的概率大小依次排列 (2) 確定滿足下列不等式的整數(shù)碼長Ki (3) 為了編成唯一可譯碼，計算第i個消息的累加概率 (4) 將累加概率Pi變換成二進制數(shù) (5) 取Pi二進數(shù)的小數(shù)點后Ki位即為該消息符號的二進制碼字,5.2 無失真信源編碼,例5.3 (p.95) 設(shè)信源共7個符號，其概率和累加概率如下表所示,5.2 無失真信源編碼,例如： 0.2=.125+.0625+ .

14、001+.0001+=.0011 0.57=.5+.0625+ .1+.0001+=.1001 0.99=.5+.25+.125+.0625+.03125+.015625+,5.2 無失真信源編碼,碼元/符號,比特/碼元,信源熵 平均碼長 信息效率,比特/符號,5.2 無失真信源編碼,費諾（Fano）編碼方法（屬于概率匹配編碼） (1) 將信源消息符號按其出現(xiàn)的概率大小依次排列： (2) 將依次排列的信源符號按概率值分為兩大組，使兩個組的概率之和近于相同，并對各組賦予一個二進制碼元“0”和“1”； (3) 將每一大組的信源符號進一步再分成兩組，使劃分后的兩個組的概率之和近于相同，并又賦予兩個組

15、一個二進制符號“0”和“1”。 (4) 如此重復(fù)，直至每個組只剩下一個信源符號為止。 (5) 信源符號所對應(yīng)的碼字即為費諾碼。,5.2 無失真信源編碼,例5.4 (p.96) 對例5.3中的信源進行費諾編碼。,5.2 無失真信源編碼,碼元/符號,bit/符號,平均碼長 信息效率,5.2 無失真信源編碼,哈夫曼（Huffman）碼 (1) 將信源消息符號按其出現(xiàn)的概率大小依次排列， (2) 取兩個概率最小的字母分別配以0和1兩個碼元，并將這兩個概率相加作為一個新字母的概率，與未分配的二進符號的字母重新排隊。 (3) 對重排后的兩個概率最小符號重復(fù)步驟(2)的過程。 (4) 不斷繼續(xù)上述過程，直到

16、最后兩個符號配以0和1為止。 (5) 從最后一級開始，向前返回得到各個信源符號所對應(yīng)的碼元序列，即相應(yīng)的碼字。,5.2 無失真信源編碼,例5.5 (p.96) 對例5.3中的信源進行哈夫曼編碼,平均碼長,碼元/符號,信息效率,bit/符號,5.2 無失真信源編碼,可見，Huffman碼的平均碼長最小，R最大、編碼效率最高 值得注意：哈夫曼編碼方法得到的碼并非唯一的 每次對信源縮減時，賦予信源最后兩個概率最小的符號，用0和1是可以任意的，所以可以得到不同的哈夫曼碼，但不會影響碼字的長度 對信源進行縮減時，兩個概率最小的符號合并后的概率與其它信源符號的概率相同時，這兩者在縮減信源中進行概率排序，其

17、位置放置次序是可以任意的，故會得到不同的哈夫曼碼。此時將影響碼字的長度，一般將合并的概率放在上面，這樣可獲得較小的碼方差,5.2 無失真信源編碼,例5.6 (p.97) 設(shè)有離散無記憶信源,5.2 無失真信源編碼,0.4 0.4 0.4 0.6 1.0 0.2 0.2 0.4 0.4 0.2 0.2 0.2 0.1 0.2 0.1,0.4 0.4 0.4 0.6 1.0 0.2 0.2 0.4 0.4 0.2 0.2 0.2 0.1 0.2 0.1,兩種方法給出的Huffman碼的平均碼長是相同的 所以編碼效率也是相同的,5.2 無失真信源編碼,碼元/符號,但兩種碼的質(zhì)量是不相同的，用碼方差描

18、述,第一種方法的碼方差為,第二種方法的碼方差為,可見，第二種方法的碼方差比第一種方法的碼方差小許多，也就是說第二種方法的Huffman碼的質(zhì)量要好,5.2 無失真信源編碼,進行哈夫曼編碼時，為得到碼方差最小的碼，應(yīng)使合并的信源符號位于縮減信源序列盡可能高的位置上，以減少再次合并的次數(shù)，充分利用短碼,哈夫曼碼是用概率匹配方法進行信源編碼 哈夫曼碼的編碼方法保證了概率大的符號對應(yīng)于短碼，概率小的符號對應(yīng)于長碼，充分利用了短碼； 縮減信源的最后二個碼字總是最后一位不同，從而保證了哈夫曼碼是即時碼。,前一節(jié)討論的無失真信源編碼是屬于保熵編碼 本節(jié)將要討論的限失真信源編碼屬于熵壓縮編碼 其中心任務(wù)是：在

19、允許的失真范圍內(nèi)把編碼后的信息率壓縮到最小 引入有失真的熵壓縮編碼的原因： (1)保熵編碼并非總是必需的； (2)保熵編碼并非總是可能的； (3)降低信息率有利于信息的傳輸和處理，因此有必要進行熵壓縮編碼，尤其是對于連續(xù)信源，熵壓縮編碼就是必需的了,5.3 限失真信源編碼定理,5.3 限失真信源編碼定理,信息率失真函數(shù)給出了失真小于D時所必須具有的最小信息率R(D) 只要信息率大于R(D)，一定可以找到一種編碼，使譯碼后的失真小于D 限失真信源編碼定理： 設(shè)離散無記憶信源X的信息率失真函數(shù)R(D)，則當(dāng)信息率RR(D)，只要信源序列長度L足夠長，一定存在一種編碼方法，其譯碼失真小于或等于D，為

20、任意小的正數(shù)。反之，若RR(D)，則無論采用什么樣的編碼方法，其譯碼失真必大于D 如果是二元信源，對于任意小的，每一個信源符號的平均碼長滿足如下公式,5.3 限失真信源編碼定理,限失真定理的意義： 在失真限度內(nèi)使信息率任意接近R(D)的編碼方法存在。然而，要使信息率小于R(D)，平均失真一定會超過失真限度D。 對于連續(xù)平穩(wěn)無記憶信源，無法進行無失真編碼，在限失真情況下，有與上述定理一樣的編碼定理。 限失真信源編碼定理只能說明最佳編碼是存在的，而具體構(gòu)造編碼方法卻一無所知。因而就不能象無失真編碼那樣從證明過程中引出概率匹配的編碼方法。一般只能從優(yōu)化的思路去求最佳編碼。實際上迄今尚無合適的可實現(xiàn)的

21、編碼方法可接近R(D)這個界。,實用化技術(shù)不同于單純理論探討；實用技術(shù)不是只追求理論上的性能（如：壓縮比），還要考慮工程上的可實現(xiàn)性 為了與復(fù)雜的實際信源統(tǒng)計匹配，實際的信源編碼方法往往都不是單一的方法，而是多種方法的組合應(yīng)用 本節(jié)簡單介紹幾種常用的信源編碼方法,5.4 常用信源編碼方法簡介,5.4 常用信源編碼方法簡介,5.4.1 游程編碼 在二元序列中，連0段稱為0游程 連1段稱為1游程 二元碼序列： 000101110010001 可變換成下列游程序列： 31132131 若已知二元序列以0起始，從游程序列很容易恢復(fù)成原來的二元序列 游程序列是多元序列，各長度可按霍夫曼編碼或其它方法處理

22、以達到壓縮碼率的目的,5.4 常用信源編碼方法簡介,多元序列也存在相應(yīng)的游程序列，但與二元序列變換所得到的游程序列不同，每個 r 游程的前后均可以是 r 以外的任何符號的游程序列，因此需要插入一個標(biāo)志來說明后面游程的類別 多元序列變換成游程序列再進行壓縮編碼沒有多大意義 游程編碼只適用于二元序列，對于多元信源，一般不直接利用游程編碼,5.4 常用信源編碼方法簡介,冗余位編碼，游程編碼在多元信源的應(yīng)用 有許多信源序列中，常存在不少的符號不攜帶信息，因此處理這些符號的數(shù)目和時長外，可以不傳 如電話通信和視頻通信 這些符號稱為冗余位，若能刪除，可提高壓縮比 如下多元序列 x1,x2,xm1,y,y,

23、y,xm1+1,xm1+2,xm2,y,y, 其中x是信息代碼，稱為信息位，y是冗余位 可以用下面序列表示 111，100，000111，111000 x1，x2，xm1，x m1+1，x m1+2x 2， 1表示信息位，0表示冗余位,5.4 常用信源編碼方法簡介,后一個序列是去除了冗余位的信息位序列 此變換是一一對應(yīng)的，可逆 此變換將一個含有（大量）冗余位的多元序列變換成了一個二元序列和一個縮短了的多元序列 這樣，這兩個序列就可能用不同的方法來編碼，以獲得更高的壓縮碼率 比如二元碼序列再采用游程編碼然后根據(jù)信源概率分布在利益Huffman編碼,5.4 常用信源編碼方法簡介,5.4.2 算術(shù)編

24、碼 非分組碼的編碼方法之一算術(shù)碼 分組碼的缺點：不考慮信源符號間的相關(guān)性，使得信源編碼的匹配原則不能充分滿足 算術(shù)編碼的基本思路：從全序列出發(fā)，考慮符號之間的依賴關(guān)系，將各信源序列的概率映射到0,1 區(qū)間上，使每個序列對應(yīng)這個區(qū)間內(nèi)的一點，也就是一個二進制的小數(shù)。這些點把0,1區(qū)間分成許多小段，每段的長度等于某一序列的概率。再在段內(nèi)取一個二進制小數(shù)，其長度可與該序列的概率匹配，達到高效率編碼的目的 算術(shù)編碼方法與Shannon編碼有點類似，只是算術(shù)碼中的信源序列長度要長的多,5.4 常用信源編碼方法簡介,信源符號集為A=a1,a2,an，概率分布為P(A)=p1,p2,pn 信源符號序列 xi

25、(xi1xi2xilxiL)，共有nL種可能序列 定義各符號的累積概率（累積分布函數(shù)）： 顯然，P1=0, P2=p1, P3=p1+p2=P2+p2, , Pr+1=Pr+pr, 即 pr =Pr+1-Pr 由于Pr+1和Pr都為小于1的正數(shù)，可分別對應(yīng)0,1區(qū)間內(nèi)的兩個點，所以pr 就是Pr+1和Pr這兩點間的長度,5.4 常用信源編碼方法簡介,不同的符號有不同的小區(qū)間，而且彼此互不重疊，因此可以把小區(qū)間的任意一點的二進制小數(shù)作為該符號的代碼（碼字） 若信源已經(jīng)發(fā)出一個序列S，即信源輸出為S狀態(tài)，后面接著發(fā)一個符號r，則符號概率與積累概率的遞推關(guān)系 采用累積概率P(S)表示碼字C(S)，符

26、號概率p(S)表示狀態(tài)區(qū)間A(S),5.4 常用信源編碼方法簡介,P(S)把區(qū)間0,1)分割成許多小區(qū)間，每個小區(qū)間的長度等于各序列的概率p(S)，小區(qū)間內(nèi)的任一點可用來代表這序列,代表大于或等于x的最小整數(shù)。 把積累概率P(S)寫成二進位的小數(shù)，取其前L位;如果有尾數(shù)，就進位到第L位，這樣得到一個數(shù)C,令,5.4 常用信源編碼方法簡介,例如: P(S)0.10110001，p(S)=1/17，則L5，得C0.10111 這個C就可作為S的碼字 編碼效率很高，當(dāng)序列很長時，可達到概率匹配。平均代碼長度接近S的熵值。可以唯一地譯碼,5.4 常用信源編碼方法簡介,例5.7 (p.105)有四個符號a,b,c,d構(gòu)成簡單序列Sabda，各符號及其對應(yīng)概率如下表，算術(shù)編解碼過程如下：,5.4 常用信源編碼方法簡介,設(shè)起始狀態(tài)為空序列，則 A()1，C()0 遞推得,5.4 常用信源編碼方法簡介,C(abda)即為編碼后的碼字010