1、第三章 無失真離散信源編碼13.1 基本概念信 源編 碼 器信道基本符號(0、1)N個消息集合X=a、b、c z、空格N個代碼組集合C=c1、 c2、cN23.1 基本概念信源編碼是以提高通信的有效性為目的編碼。 信源編碼適合信道傳輸減少冗余度33.1 基本概念 由于信源編碼可以不考慮抗干擾問題，所以由于信源編碼可以不考慮抗干擾問題，所以它的數學模型比較簡單。它的數學模型比較簡單。43.1 基本概念l輸入是信源符號集輸入是信源符號集:l x為編碼器所用的編碼符號集，包含為編碼器所用的編碼符號集，包含r個元素個元素 ，稱為，稱為碼符號碼符號(碼元碼元) 。l由碼符號由碼符號 組成的輸出序列組成的

2、輸出序列 稱為稱為碼字碼字。 其長度其長度 稱為稱為碼字長度碼字長度或或碼長碼長，全體碼字，全體碼字 的集合的集合C稱稱為為碼碼或或碼書碼書 。l編碼器將信源符號集中的編碼器將信源符號集中的信源符號信源符號 （或長為（或長為N的信源的信源符號序列符號序列 ）變成由）變成由碼符號碼符號組成的長為的與信源符號一組成的長為的與信源符號一一對應的輸出序列。即一對應的輸出序列。即 :12 ,qSs ss ixrxxx,.,21iWiliWisi12(1,2, )(1,2, )(,), iiiiiilijs iqW iqxxxxX 若要實現若要實現無失真編碼，無失真編碼，必須這種映射必須這種映射是一一對應

3、的、是一一對應的、可逆的。可逆的。53.1 基本概念 (1) 二元碼二元碼和和r元碼元碼 若碼符號集若碼符號集 ，編碼所得碼字為一些，編碼所得碼字為一些適合在二元信道中傳輸的二元序列，則稱適合在二元信道中傳輸的二元序列，則稱二元碼二元碼。二元碼是數字通信與計算機系統中最常用的一種二元碼是數字通信與計算機系統中最常用的一種碼。若碼符號集共有碼。若碼符號集共有 r 個元素，則所得之碼稱為個元素，則所得之碼稱為 r 元碼元碼。0,1X 63.1 基本概念 (2) 基本源編碼基本源編碼和和N次擴展源編碼次擴展源編碼 (3) 無失真編碼無失真編碼 和和有失真編碼有失真編碼 數學上稱為非奇異碼和奇異碼，數

4、學上稱為非奇異碼和奇異碼，若信源符號和碼字是一一對應的，則該碼為非奇異碼。反之為奇異碼。 (4)惟一可譯碼惟一可譯碼和和非惟一可譯碼非惟一可譯碼 若任意一串有限長的碼符號序列只能被惟一地譯成所若任意一串有限長的碼符號序列只能被惟一地譯成所對應的信源符號序列，則此碼稱為對應的信源符號序列，則此碼稱為惟一可譯碼惟一可譯碼（或稱（或稱單單義可譯碼義可譯碼）。否則就稱為非惟一可譯碼或非單義可譯碼。）。否則就稱為非惟一可譯碼或非單義可譯碼。 若要使某一碼為惟一可譯碼，則對于任意給定的有限若要使某一碼為惟一可譯碼，則對于任意給定的有限長的碼符號序列，只能被惟一地分割成一個個的碼字。長的碼符號序列，只能被惟

5、一地分割成一個個的碼字。73.1 基本概念 例如例如：對于二元碼：對于二元碼 ，當任意給定一，當任意給定一串碼字序列，例如串碼字序列，例如“10001101”，只可唯一地劃，只可唯一地劃分為分為1,00,01,1,01，因此是惟一可譯碼；而對另，因此是惟一可譯碼；而對另一個二元碼一個二元碼 ，當碼字序列為，當碼字序列為“01001”時，可劃分為時，可劃分為0,10,01或或01,0,01，所以，所以是非惟一可譯的。是非惟一可譯的。11,01,00C 20,10,01C 83.1 基本概念 (5) 定長碼定長碼和和變長碼變長碼 若一組碼中所有碼字的長度都相同若一組碼中所有碼字的長度都相同-（即（

6、即 ），則稱為等長碼。），則稱為等長碼。,1,ill iq 信源符號si符號出現概率p(si)編碼1編碼2s1p(s1)000s2p (s2)0101s3p (s3)10001s4p (s4)111019符號符號 碼碼A碼碼B碼碼C碼碼D碼碼E碼碼Fa 0 0 00 0 1 0b 0 1 01 10 01 01c 1 10 10 110 001 011d 10 11 11 111 0001 0111103.2 離散無失真信源編碼定理1、數據壓縮的途徑、數據壓縮的途徑 途徑一：使序列中的各個符號盡可能地互相途徑一：使序列中的各個符號盡可能地互相獨立，即解除相關性，獨立，即解除相關性，去冗余；去冗

7、余； 途徑二：使編碼中各個符號出現的概率盡可途徑二：使編碼中各個符號出現的概率盡可能地相等，即能地相等，即概率均勻化概率均勻化。 2、數據壓縮的理論極限、數據壓縮的理論極限113.2 離散無失真信源編碼定理1. 平均碼長平均碼長 設信源有設信源有N個單符號消息個單符號消息x1，x2，xN，變長碼編碼器輸出的代碼組長度對應為變長碼編碼器輸出的代碼組長度對應為l1, l2, , lN ，其出現概率分別為其出現概率分別為 P(s1) , P(s2), P(sN)，則該變長碼的平均長度為則該變長碼的平均長度為1()NiiiLP slCode/sign123.2 離散無失真信源編碼定理2. 編碼后的信息

8、傳輸率編碼后的信息傳輸率（1）等長碼的信息傳輸速率：對單符號離散信源，設其信源熵為）等長碼的信息傳輸速率：對單符號離散信源，設其信源熵為H(X)，對其進行等長編碼，每碼字對其進行等長編碼，每碼字l個碼元，故其信息傳輸速率為個碼元，故其信息傳輸速率為 R=H(X)/l( )/RHLX（2）變長碼的信息傳輸速率：對單符號離散信源，設其信源熵為）變長碼的信息傳輸速率：對單符號離散信源，設其信源熵為H(X)，對其進行等長編碼，每碼字對其進行等長編碼，每碼字l個碼元，故其信息傳輸速率為個碼元，故其信息傳輸速率為bit/codebit/code133.2 離散無失真信源編碼定理3. 編碼效率編碼效率 信源

9、編碼器輸出代碼組的信息傳輸速率與信道容量信源編碼器輸出代碼組的信息傳輸速率與信道容量之比，稱為信源編碼器的編碼效率。即之比，稱為信源編碼器的編碼效率。即( )loglogRRH xCrLr143.2 離散無失真信源編碼定理例1： 設離散無記憶信源概率空間為 信源熵： H ( X ) = 1/4 log4 +3/4 log3/4 = 0. 811 bit / 信源符號 若用二元定長編碼 (0,1) 來構造一個即時碼： 平均碼長： 二元碼符號 / 信源符號 編碼效率： 輸出的信息傳輸率：11L 1( )0.811logH xLr1( )0.811H xRLLbit/code153.2 離散無失真信

10、源編碼定理再對長度 L 為 2 的信源序列進行 變長編碼，其即時碼如表： 碼字平均長度： 單個符號的平均碼長 編碼效率 輸出的信息傳輸率： R2 0.961bit/ 二元碼符號 L2L2/ 227/32LL163.2 離散無失真信源編碼定理編碼復雜一些，但信息傳輸率有了提高 定長編碼： 要求編碼效率達到 96 時，允許譯碼錯誤概率 10 5 173.2 離散無失真信源編碼定理1819 定理中的公式改寫成定理中的公式改寫成l 不等式左邊表示長為不等式左邊表示長為L的碼符號序列能載荷的最的碼符號序列能載荷的最大信息量，大信息量，l右邊代表長為右邊代表長為N的信源序列平均攜帶的信息量。的信源序列平均

11、攜帶的信息量。 所以定長編碼定理告訴我們：只要碼字傳輸所以定長編碼定理告訴我們：只要碼字傳輸的信息量大于信源攜帶的信息量，總可實現幾乎的信息量大于信源攜帶的信息量，總可實現幾乎無失真編碼。無失真編碼。20例題結論：定長編碼簡單，但要達到一定的差錯率不易實現，且編碼效率低。21( )( )1loglogH SH SLrr 對離散無記憶信源，消息長度為N，符號熵為H(S),對信源進行r元變長編碼，一定存在無失真的信源編碼方法2 碼字平均長度碼字平均長度 不能小于極限值不能小于極限值 ，否則唯一可譯碼不，否則唯一可譯碼不存在。存在。 定理給出平均碼長的上界，但并不是說大于上界不能構成唯定理給出平均碼

12、長的上界，但并不是說大于上界不能構成唯一可譯碼，而是我們希望一可譯碼，而是我們希望 盡可能短。盡可能短。 定理給出緊致碼的最短平均碼長，并指出這個最短的平均碼定理給出緊致碼的最短平均碼長，并指出這個最短的平均碼長與信源熵是有關的。長與信源熵是有關的。LrSHlog)(L2223如何分離碼字？1001110？要求：碼是唯一可譯要求：碼是唯一可譯243.2.3碼字唯一可譯條件延時碼即時碼可分離唯一可譯碼非唯一可譯碼非奇異碼奇異碼碼)(25判斷以下碼字是否可分離？例例3.2.2263.2.3碼字唯一可譯條件即時碼的一種簡單構造方法是即時碼的一種簡單構造方法是樹圖法樹圖法。對于給定碼字的全體集合對于給

13、定碼字的全體集合C，可用，可用碼樹碼樹來描述它。來描述它。所謂所謂樹樹，既有根、枝，又有節點。，既有根、枝，又有節點。n圖中最上端圖中最上端A點為點為根根，從根出發，從根出發向下伸出樹枝，樹枝的數目等于向下伸出樹枝，樹枝的數目等于碼符號的總數碼符號的總數r。n樹枝的盡頭為樹枝的盡頭為節點節點，從節點出發，從節點出發再伸出樹枝，每次每個節點伸出再伸出樹枝，每次每個節點伸出r枝，依次下去構成一棵樹。枝，依次下去構成一棵樹。273.2.3碼字唯一可譯條件n在下圖中，當某一個節點被安在下圖中，當某一個節點被安排為碼字后，就不再繼續伸枝，排為碼字后，就不再繼續伸枝，此節點稱為此節點稱為終端節點終端節點（

14、用粗黑點（用粗黑點表示）。表示）。n其他節點稱為其他節點稱為中間節點中間節點，不安，不安排為碼字（用空心圈表示），給排為碼字（用空心圈表示），給每個節點所伸出的樹枝分別從左每個節點所伸出的樹枝分別從左向右標上碼符號向右標上碼符號0，1，r。283.2.3碼字唯一可譯條件任一即時碼都可用任一即時碼都可用樹圖法樹圖法來表示。來表示。當碼字長度給定時，即時碼不是唯一的。當碼字長度給定時，即時碼不是唯一的。在每個節點上都有在每個節點上都有r個分枝的樹稱為個分枝的樹稱為整樹整樹（滿樹滿樹），），否則稱為否則稱為非整樹非整樹（非滿樹非滿樹）。）。rllllr當當 元元 節的碼樹的所有樹枝都被用上時，第節的

15、碼樹的所有樹枝都被用上時，第 階節階節點共有點共有 個終端節點，正好對應于長度為個終端節點，正好對應于長度為 的等長碼，的等長碼，可見等長碼也是即時碼的一種。可見等長碼也是即時碼的一種。29即時碼的樹圖結構樹與編碼的關系樹根碼的起點樹枝碼的進制數節點碼字或其部分終結點碼字節數碼長滿樹等長碼非滿樹變長碼0120120120120123.2.3碼字唯一可譯條件30克拉夫特不等式lr元長度為li的異前置碼存在的充要條件是11inlir3.2.3碼字唯一可譯條件313.2.3碼字唯一可譯條件 Kraft不等式不等式是惟一可譯碼存在的是惟一可譯碼存在的充要條件充要條件， 必要性表現在如果碼是惟一可譯碼，

16、則必定滿必要性表現在如果碼是惟一可譯碼，則必定滿足足Kraft不等式不等式;充分性表現在如果滿足充分性表現在如果滿足Kraft不等式，則這種碼不等式，則這種碼長的惟一可譯碼一定存在，但并不表示所有滿足長的惟一可譯碼一定存在，但并不表示所有滿足Kraft不等式的碼一定是惟一可譯碼。不等式的碼一定是惟一可譯碼。 因此，克拉夫特不等式是惟一可譯碼因此，克拉夫特不等式是惟一可譯碼存在存在的充要的充要條件，而不是惟一可譯碼的充要條件。條件，而不是惟一可譯碼的充要條件。323.2.3碼字唯一可譯條件 例例：設二進制碼樹中：設二進制碼樹中X= ， ， ， ，對應，對應的的 ， ， ， ，由上述定理，可得，由

17、上述定理，可得因此不存在滿足這種碼長的唯一可譯碼。因此不存在滿足這種碼長的唯一可譯碼。18922222322141ili22l11l34l23l4a3a1a2a333.2.3碼字唯一可譯條件a1=1 0 1 0 1 0 1a2=01a3=001a4=000 1，01，001，000 惟一可譯碼；惟一可譯碼； 1，01，101，000 不是惟一可譯碼；不是惟一可譯碼； 均滿足克勞夫特不等式均滿足克勞夫特不等式122222332141iKi343.2.3碼字唯一可譯條件 注意注意：不滿足克拉夫特不等式的碼，一定不是唯一：不滿足克拉夫特不等式的碼，一定不是唯一可譯碼。碼長滿足克拉夫特不等式的碼，也不

18、一可譯碼。碼長滿足克拉夫特不等式的碼，也不一定是唯一可譯碼。定是唯一可譯碼。 克拉夫特不等式只是說明唯一可譯碼是否克拉夫特不等式只是說明唯一可譯碼是否存存在在，并不能作為一種碼制是否是唯一可譯碼的判，并不能作為一種碼制是否是唯一可譯碼的判斷依據。斷依據。353.3 香農編碼香農編碼niinnxpxpxpxpxxx121211)(,)(.)()(.設有離散無記憶信源362log()iip al1234香農編碼方法的步驟香農編碼方法的步驟按信源符號的概率從大到小的順序排隊按信源符號的概率從大到小的順序排隊)(.)()(21napapap100)()() 1)(, 0)(jiijajaapapiij

19、apap累加概率個碼字的表示第用令計算各信源符號的計算各信源符號的自信息量自信息量。編碼碼長應該大于自信息量。編碼碼長應該大于自信息量。5累加概論二進制化，取給定碼長，得到累加概論二進制化，取給定碼長，得到編碼碼字編碼碼字。3738香農編碼香農編碼例： 有一單符號離散無記憶信源 39 香農碼的平均碼長香農碼的平均碼長 信源熵 編碼效率 為提高編碼效率，可把 x 4 x 5 換成前面的節 點，可減小平均碼長。 不應先規定碼長，而是由碼樹來規定碼 字，可得更好的結果。 L2logLRrLN( )78%H xR書例書例3.3.105. 01 . 015. 02 . 025. 025. 0)(6543

20、21xxxxxxXPX設有一單符號離散無記憶信源設有一單符號離散無記憶信源試對該信源編二進制香農碼。試對該信源編二進制香農碼。3.3 香農編碼香農編碼40123456()0.2502000.250.252010.20.531000.150.731010.10.85411010.050.95511110ajipxlxxxxxx編碼過程編碼過程10)()(jiijaxpxp（1）碼字碼字4161()2.7iiiLp x l2logLRrLN42. 2)(XH%63.89)(RxH3.3 香農編碼香農編碼423.4 3.4 費諾編碼費諾編碼對概率按r進行分組，使每組概率盡可能相等給每個分組分配一個碼

21、元對每個分組重復2、3步，直到不可分為止1234按信源符號的概率從大到小的順序排隊12()().()np ap ap a不妨設43概率匹配概率匹配 443.4 3.4 費諾編碼費諾編碼L( )H xR453.4 3.4 費諾編碼特點費諾編碼特點1) 費諾編碼在構造費諾編碼在構造碼樹碼樹時，是從樹根開始到終端節時，是從樹根開始到終端節 點結束；點結束； 2) 由于賦碼元時的任意性，因此編出的碼字不唯一；由于賦碼元時的任意性，因此編出的碼字不唯一； 3) 費諾編碼雖屬于費諾編碼雖屬于概率匹配概率匹配范疇，但并未嚴格遵守范疇，但并未嚴格遵守 匹配規則，有時出現概率小的碼長反而小。因此匹配規則，有時出

22、現概率小的碼長反而小。因此 平均碼長一般不會最小。平均碼長一般不會最小。 費諾碼比較適合于費諾碼比較適合于每次分組概率都很接近每次分組概率都很接近的信源，特的信源，特 別是對每次別是對每次分組概率都相等的信源分組概率都相等的信源進行編碼時，可達進行編碼時，可達 到理想的編碼效率。到理想的編碼效率。 46例： 對該信源進行二 進制費諾編碼。 平均碼長： 編碼效率：1L =2.12L =2.005. 010. 015. 02 . 025. 025. 0)(654321aaaaaaXPX設有一單符號離散無記憶信源設有一單符號離散無記憶信源試對該信源編二進制費諾碼。試對該信源編二進制費諾碼。書例書例3

23、.4.1NoImage3.4 3.4 費諾編碼費諾編碼471a2a3a4a5a6a25. 025. 02 . 015. 01 . 005. 0001010011000110110111011111編碼過程48)/(42325.2)(signbitXH2logLRrN%91.98)(RxH61()2.45(/)iiiLp a lbitsign 可以看出本例中費諾碼有較高的編碼效率。可以看出本例中費諾碼有較高的編碼效率。費諾碼比較適合于每次分組概率都很接近的信源。費諾碼比較適合于每次分組概率都很接近的信源。3.4 3.4 費諾編碼費諾編碼4900000111111a2a3a4a5a6a50將信源符

24、號按概率由大到小順序排隊給兩個概率最小的符號各分配一個碼位，將其概率相加后合并作為一個新的符號，與剩下的符號一起，再重新排隊給縮減信源中概率最小的符號各分配一個碼元重復步驟2、3直至概率和為121433.5 3.5 赫夫曼編碼赫夫曼編碼51從最后一級開始，向前返回得到各個信源符號所對應的碼元序列，即相應的碼字。 552例：試對該信源編二進制哈夫曼碼。試對該信源編二進制哈夫曼碼。 讀取碼字的時候，要從后向前讀，此 時編出來的碼字是可分離的即時碼。 5353平均碼長平均碼長 信源熵信源熵 H(X) = H (0.2,0.19,0.18,0.17,0.15,0.1,0.01)=2.61 bit/ 符

25、號符號 編碼效率編碼效率 L( )H xR541) 哈夫曼編碼在構造碼樹時，是從端點開始直到樹 根結束； 2) 哈夫曼編碼采用概率匹配方法來決定各碼字長度， 概率大的符號對應于短碼，概率小的符號對應與長 碼，充分利用了短碼，從而使平均碼長最小； 3) 哈夫曼編碼時，縮減信源的最后二個碼字總是最 后一位不同，從而保證了哈夫曼碼是即時碼。 3.5 3.5 赫夫曼編碼特點赫夫曼編碼特點設有一單符號離散無記憶信源試對該信源編二進制哈夫曼碼。書例書例3.5.105. 010. 015. 02 . 025. 025. 0)(654321aaaaaaXPX5515. 03 . 00.450.55000001

26、111105. 010. 015. 02 . 025. 025. 01a2a3a4a5a6a101101100100000001000000005a編碼過程56()2.42325(/)H Xbit sym2.45L( )98.91%H xR573,2.5585312.7L若采用定長編碼，碼長則編碼效率 可見，哈夫曼編碼的效率提高了。58Huffman碼的編碼方法不是唯一的首先:每次對縮減信源兩個最小的符號分配“0”和“1”碼元試任意的;其次:若合并后的新符號的概率與其他符號的概率相等，這幾個符號的次序可任意排列;一般將合并的概率放在上面，這樣可獲得較小的碼方差。說明：說明：59例例 設有離散無

27、記憶信源設有離散無記憶信源1 . 01 . 02 . 02 . 04 . 0)(54321xxxxxXPX用兩種不同的方法對其編二進制huffman碼60方法一方法一方法二方法二61信源符號信源符號xi概率概率p(xi)碼字碼字Wi1碼長碼長Ki1碼字碼字Wi2碼長碼長Ki2x10.411002x20.2012102x30.20003112x40.1001040103x50.1001140113兩種不同的編碼方法得到的碼字和碼長的對比62平均碼長和編碼效率平均碼長和編碼效率63碼字的碼長方差比較碼字的碼長方差比較64可以看出第二種編碼方法的碼長方差要小許多,碼長變化較小，比較接近平均碼長。要求

28、：Huffman編碼時應使合并的信源符號位于縮減信源序列盡可能高的位置上，碼長變化較小，比較接近平均碼長，易于實現。結論：結論：65663.5 3.5 赫夫曼編碼赫夫曼編碼m 進制哈夫曼編碼 在編 m 進制哈夫曼碼時，為了使短碼得到充分利用， 使平均碼長最短，必須使最后一步的縮減信源有 m 個 信源符號。 縮減次數 每次縮減所減少 的信源符號個數 信源符號數 n 應滿足：不滿足時：設q個概率為 0 的信源符號，使q+n 滿足要求 第一次對最小概率符號分配碼元時只取 (m-q) 個，分別 配以 0,1, m-q-1 ，把這些符號的概率相加作為一個新 符號的概率，與其它符號一起重新排列。以后每次取

29、 m 個符號，分別配以 0,1, m-1；如此下去，直至所有 概率相加得 1 為止，即得到各符號的 m 進制碼字。 673.5 3.5 赫夫曼編碼赫夫曼編碼m 進制哈夫曼編碼 例 試對該信源編三進制哈夫曼碼。 m =3 ， n =8 無法滿足 n = s ( m -1) + m s =3 ， q =1 q + n = s ( m -1) + m 第一次取 m - q =2 個符號進行編碼 683.5 3.5 赫夫曼編碼赫夫曼編碼m 進制哈夫曼編碼 693.5 3.5 赫夫曼編碼赫夫曼編碼m 進制哈夫曼編碼 平均碼長 編碼效率 L( )H xR70簡單討論簡單討論 T：0.072 O：0.065

30、4 A：0.063 N：0.059 I：0.055 R：0.054 S：0.052 V：0.008 K：0.003 X：0.002 J、Q：0.001 Z：0.001英文各個字符的統計概率如下：71簡單討論簡單討論1、編碼效率：、編碼效率：Shannon碼碼：碼長碼長:3-11,平均碼長平均碼長: 4.602bit/sym,效率效率：0.895Fano碼碼：碼長碼長:3-11,平均碼長平均碼長: 4.168bit/sym,效率效率：0.989Huffman碼碼：碼長碼長:3-10,平均碼長平均碼長: 4.156bit/sym,效率效率：0.9922、編碼思路：、編碼思路：Shannon碼碼：自

31、信息：自信息Fano碼碼：等概劃分：等概劃分Huffuman碼碼：從概率最小的符號開始：從概率最小的符號開始三種編碼的比較Huffman:不唯一，但對信源沒有特殊要求，且編碼效率較高，設備要求簡單，綜合性能優于另外兩種。相同點：三種編碼都考慮了信源的統計特性，使經常出現的信源符號對應較短的碼字，使平均碼長縮短，實現了信源壓縮。不同點：shannon：有唯一的編碼，但編碼效率不是很高；Fano:編碼方法不唯一，適合與分組概率相等或相近的信源；723.6 游程編碼73 前面的幾種編碼方法主要時針對無記憶信源，對有前面的幾種編碼方法主要時針對無記憶信源，對有記憶信源，這些編碼方法的效率并不高，特別是對二記憶信源，這些編碼方法的效率并不高，特別是對二元相關信源，需要