《信息論與編碼》課件第第5章

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

2、連續(xù)信源，只能在失真受限制的情況下進行限失真編碼 45.1 編碼的定義信源編碼器信道碼表圖5-1 信源編碼器示意圖55.1 編碼的定義信源編碼是指信源輸出符號經(jīng)信源編碼器編碼后轉(zhuǎn)換成另外的壓縮符號無失真信源編碼：可精確無失真地復(fù)制信源輸出地消息65.1 編碼的定義將信源消息分成若干組，即符號序列xi， xi(xi1xi2xilxiL)， xilA=a1，a2，ai，an每個符號序列xi依照固定碼表映射成一個碼字yi， yi(yi1yi2yilyiL)， yilB=b1，b2，bi，bm這樣的碼稱為分組碼，有時也叫塊碼。只有分組碼才有對應(yīng)的碼表，而非分組碼中則不存在碼表。 75.1 編碼的定義如

3、圖5-1所示，如果信源輸出符號序列長度L1，信源符號集A(a1，a2，an)信源概率空間為 若將信源X通過二元信道傳輸，就必須把信源符號ai變換成由0，1符號組成的碼符號序列，這個過程就是信源編碼 85.1 編碼的定義不同的碼符號序列，如表5-1所示。 表5-1 變長碼與定長碼信源符號ai信源符號出現(xiàn)概率p(ai)碼表碼1碼2a1p(a1)000a2p(a2)0101a3p(a3)10001a4p(a4)1111195.1 編碼的定義碼奇異碼非分組碼分組碼非奇異碼非唯一可譯碼非即時碼即時碼(非延長碼)唯一可譯碼105.1 編碼的定義表5-2 碼的不同屬性信源符號ai符號出現(xiàn)概率p(ai)碼1碼

4、2碼3碼4a11/20011a21/411101001a31/80000100001a41/8110110000001115.1 編碼的定義通常可用碼樹來表示各碼字的構(gòu)成 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1二進制碼樹125.1 編碼的定義 0 1 2 0 1 2 0 1 2 0 1 20 1 20 1 2三進制碼樹135.1 編碼的定義唯一可譯碼存在的充分和必要條件 各碼字的長度Ki 應(yīng)符合克勞夫特不等式： 145.1 編碼的定義例：設(shè)二進制碼樹中X (a1， a2 ， a3 ， a4 )，K11，K22，K3

5、2，K43，應(yīng)用上述判斷定理： 因此不存在滿足這種Ki的唯一可譯碼。 155.1 編碼的定義a1=1 0 1 0 1 0 1a2=01a3=011a4=0001，01，001，000 惟一可譯碼；1，01，101，000 不是惟一可譯碼；均滿足克勞夫特不等式165.2 無失真信源編碼信源輸出X(X1X2XlXL)，Xla1，a2，ai，an編碼為Y(Y1Y2Yk YkL)，Ykb1，b2，bj，bm。要求能夠無失真或無差錯地譯碼，同時傳送Y時所需要的信息率最小 175.2 無失真信源編碼無失真的信源編碼定理定長編碼定理變長編碼定理 185.2 無失真信源編碼由L個符號組成的、每個符號的熵為HL

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

7、和 均為定值時，只要L足夠大，Pe可以小于任一正數(shù)。即， 225.2 無失真信源編碼當(dāng)信源序列長度L滿足 時，能達到差錯率要求 235.2 無失真信源編碼在連續(xù)信源的情況下，由于信源的信息量趨于無限，顯然不能用離散符號序列Y來完成無失真編碼，而只能進行限失真編碼。245.2 無失真信源編碼定義為編碼效率，即信源的平均符號熵為H(X)，采用平均符號碼長為 來編碼，所得的效率。編碼效率總是小于1，且最佳編碼效率為 255.2 無失真信源編碼編碼定理從理論上闡明了編碼效率接近1的理想編碼器的存在性，它使輸出符號的信息率與信源熵之比接近于1，即 L取無限長265.2 無失真信源編碼例設(shè)離散無記憶信源概

8、率空間為 比特/符號 275.2 無失真信源編碼對信源符號采用定長二元編碼，要求編碼效率 為 90，若取L1，則可算出2.55 90%=2.8比特/符號Pe0.04 太大285.2 無失真信源編碼若要求譯碼錯誤概率 295.2 無失真信源編碼變長編碼定理在變長編碼中，碼長K是變化的根據(jù)信源各個符號的統(tǒng)計特性，如概率大的符號用短碼，概率小的用較長的碼，使得編碼后平均碼長降低，從而提高編碼效率。（統(tǒng)計匹配）305.2 無失真信源編碼單個符號變長編碼定理：若離散無記憶信源的符號熵為H(X)，每個信源符號用m進制碼元進行變長編碼，一定存在一種無失真編碼方法，其碼字平均長度滿足下列不等式315.2 無失

9、真信源編碼 離散平穩(wěn)無記憶序列變長編碼定理：對于平均符號熵為HL(X)的離散平穩(wěn)無記憶信源，必存在一種無失真編碼方法，使平均信息率滿足不等式其中為任意小正數(shù)。325.2 無失真信源編碼編碼效率總是小于1，可以用它來衡量各種編碼方法的優(yōu)劣。為了衡量各種編碼方法與最佳碼的差距，定義碼的剩余度為 335.2 無失真信源編碼例設(shè)離散無記憶信源的概率空間為345.2 無失真信源編碼若用二元定長編碼(0，1)來構(gòu)造一個即時碼： 。平均碼長 1二元碼符號/信源符號355.2 無失真信源編碼編碼效率為輸出的信息效率為R0.811比特/二元碼符號365.2 無失真信源編碼長度為2的信源序列進行變長編碼（編碼方法

10、后面介紹），其即時碼如下表 aip(ai)即時碼a1a19/160a1a23/1610a2a13/16110a2a21/16111375.2 無失真信源編碼二元碼符號/信源序列二元碼符號/信源符號385.2 無失真信源編碼編碼效率信息效率R20.961比特/二元碼符號 395.2 無失真信源編碼L3 R30.985比特/二元碼符號 L4 R40.991比特/二元碼符號 405.2 無失真信源編碼定長二元碼編碼，要求編碼效率達到96時，允許譯碼錯誤概率 415.2 無失真信源編碼能獲得最佳碼的編碼方法主要有：香農(nóng)（Shannon）費諾（Fano）哈夫曼（Huffman）等 425.2 無失真信源

11、編碼香農(nóng)（Shannon）編碼將信源消息符號按其出現(xiàn)的概率大小依次排列確定滿足下列不等式的整數(shù)碼長Ki。435.2 無失真信源編碼為了編成唯一可譯碼，計算第i個消息的累加概率將累加概率Pi變換成二進制數(shù)。取Pi二進數(shù)的小數(shù)點后Ki位即為該消息符號的二進制碼字。 445.2 無失真信源編碼例 設(shè)信源共7個符號消息，其概率和累加概率如下表所示。 455.2 無失真信源編碼信源消息符號ai符號概率(ai)累加概率Pi-log p(ai)碼字長度Ki碼字a10.2002.323000a20.190.22.393001a30.180.392.473011a40.170.572.563100a50.150

12、.742.743101a60.100.893.3241110a70.010.996.6471111110465.2 無失真信源編碼碼元/符號比特/碼元 475.2 無失真信源編碼費諾編碼方法費諾編碼屬于概率匹配編碼(1)將信源消息符號按其出現(xiàn)的概率大小依次排列： 。(2)將依次排列的信源符號按概率值分為兩大組，使兩個組的概率之和近于相同，并對各組賦予一個二進制碼元“0”和“1”。485.2 無失真信源編碼(3)將每一大組的信源符號進一步再分成兩組，使劃分后的兩個組的概率之和近于相同，并又賦予兩個組一個二進制符號“0”和“1”。(4)如此重復(fù)，直至每個組只剩下一個信源符號為止。(5)信源符號所對

13、應(yīng)的碼字即為費諾碼。495.2 無失真信源編碼例 對以下信源進行費諾編碼。 消息符號ai各個消息概率 p(ai)第一次分組第二次分組第三次分組第四次分組二元碼字碼長Kia10.2000002a20.19100103a30.1810113a40.1710102a50.15101103a60.101011104a70.01111114505.2 無失真信源編碼 碼元/符號 bit/符號 515.2 無失真信源編碼 哈夫曼編碼方法(1)將信源消息符號按其出現(xiàn)的概率大小依次排列，(2)取兩個概率最小的字母分別配以0和1兩個碼元，并將這兩個概率相加作為一個新字母的概率，與未分配的二進符號的字母重新排隊。

14、525.2 無失真信源編碼(3)對重排后的兩個概率最小符號重復(fù)步驟(2)的過程。(4)不斷繼續(xù)上述過程，直到最后兩個符號配以0和1為止。(5)從最后一級開始，向前返回得到各個信源符號所對應(yīng)的碼元序列，即相應(yīng)的碼字。535.2 無失真信源編碼例 對以下信源進行哈夫曼編碼 信源符號ai概率p(ai)碼字Wi碼長Kia10.20102a20.19112a30.180003a40.170013a50.150103a60.1001104a70.0101114545.2 無失真信源編碼0.20 0.20 0.26 0.35 0.39 0.61 1.00.19 0.19 0.20 0.26 0.35 0.3

15、90.18 0.18 0.19 0.20 0.260.17 0.17 0.18 0.190.15 0.15 0.170.10 0.110.01010101010101555.2 無失真信源編碼 碼元/符號 bit/符號 565.2 無失真信源編碼哈夫曼編碼方法得到的碼并非唯一的每次對信源縮減時，賦予信源最后兩個概率最小的符號，用0和1是可以任意的，所以可以得到不同的哈夫曼碼，但不會影響碼字的長度。575.2 無失真信源編碼對信源進行縮減時，兩個概率最小的符號合并后的概率與其它信源符號的概率相同時，這兩者在縮減信源中進行概率排序，其位置放置次序是可以任意的，故會得到不同的哈夫曼碼。此時將影響碼字

16、的長度，一般將合并的概率放在上面，這樣可獲得較小的碼方差。585.2 無失真信源編碼例 設(shè)有離散無記憶信源595.2 無失真信源編碼信源符號ai概率p(ai)碼字Wi1碼長Ki1碼字Wi2碼長Ki2a10.411002a20.2012102a30.20003112a40.1001040103a50.1001140113605.2 無失真信源編碼0.4 0.4 0.4 0.6 1.0 0.2 0.2 0.4 0.40.2 0.2 0.20.1 0.2 0.10.4 0.4 0.4 0.6 1.0 0.2 0.2 0.4 0.40.2 0.2 0.20.1 0.20.101010101010101

17、01615.2 無失真信源編碼 碼元/符號 625.2 無失真信源編碼635.2 無失真信源編碼 進行哈夫曼編碼時，為得到碼方差最小的碼，應(yīng)使合并的信源符號位于縮減信源序列盡可能高的位置上，以減少再次合并的次數(shù)，充分利用短碼。 645.2 無失真信源編碼哈夫曼碼是用概率匹配方法進行信源編碼。哈夫曼碼的編碼方法保證了概率大的符號對應(yīng)于短碼，概率小的符號對應(yīng)于長碼，充分利用了短碼；縮減信源的最后二個碼字總是最后一位不同，從而保證了哈夫曼碼是即時碼。655.3 限失真信源編碼定理 信息率失真函數(shù)給出了失真小于D時所必須具有的最小信息率R(D)；只要信息率大于R(D)，一定可以找到一種編碼，使譯碼后的

18、失真小于D。 665.3 限失真信源編碼定理限失真信源編碼定理：設(shè)離散無記憶信源X的信息率失真函數(shù)R(D)，則當(dāng)信息率RR(D)，只要信源序列長度L足夠長，一定存在一種編碼方法，其譯碼失真小于或等于D，為任意小的正數(shù)。反之，若RR(D)，則無論采用什么樣的編碼方法，其譯碼失真必大于D。675.3 限失真信源編碼定理如果是二元信源，對于任意小的，每一個信源符號的平均碼長滿足如下公式 685.3 限失真信源編碼定理在失真限度內(nèi)使信息率任意接近R(D)的編碼方法存在。然而，要使信息率小于R(D)，平均失真一定會超過失真限度D。對于連續(xù)平穩(wěn)無記憶信源，無法進行無失真編碼，在限失真情況下，有與上述定理一

19、樣的編碼定理。695.3 限失真信源編碼定理限失真信源編碼定理只能說明最佳編碼是存在的，而具體構(gòu)造編碼方法卻一無所知。因而就不能象無損編碼那樣從證明過程中引出概率匹配的編碼方法。一般只能從優(yōu)化的思路去求最佳編碼。實際上迄今尚無合適的可實現(xiàn)的編碼方法可接近R(D)這個界。 705.4 常用信源編碼方法簡介算術(shù)編碼 非分組碼的編碼方法之一算術(shù)碼715.4 常用信源編碼方法簡介符號概率與積累概率的遞推關(guān)系725.4 常用信源編碼方法簡介采用累積概率P(S)表示碼字C(S)，符號概率p(S)表示狀態(tài)區(qū)間A(S) 735.4 常用信源編碼方法簡介P(S)把區(qū)間0，1)分割成許多小區(qū)間，每個小區(qū)間的長度等

20、于各序列的概率p(S)，小區(qū)間內(nèi)的任一點可用來代表這序列 0(P1) P2 P3 P4 P5 1 p1 p2 p3 p4 745.4 常用信源編碼方法簡介 0(P1) P2 P3 P4 P5 1 p1 p2 p3 p4 代表大于或等于的最小整數(shù)。把積累概率P(S)寫成二進位的小數(shù)，取其前L位;如果有尾數(shù)，就進位到第L位，這樣得到一個數(shù)C 755.4 常用信源編碼方法簡介例如P(S)0.10110001，p(S)=1/17，則L5，得C0.10111這個C就可作為S的碼字 編碼效率很高，當(dāng)序列很長時，可達到概率匹配。平均代碼長度接近S的熵值?？梢晕ㄒ坏刈g碼 765.4 常用信源編碼方法簡介符號符號概率pi符號累積概率Pja0.100(1/2)0.000b0.010(1/4)0.100c0.001(1/8)0.110d0.001(1/8)0.111例 有四個符號a，b，c，d構(gòu)成簡單序列Sabda