1、第第4 4章：信源編碼基礎章：信源編碼基礎l 信源編碼的作用：信源編碼的作用： 使信源適合于信道的傳輸，用信道能傳輸的符號來代使信源適合于信道的傳輸，用信道能傳輸的符號來代表信源發出的消息；表信源發出的消息； 在不失真或允許一定失真的條件下，用盡可能少的符在不失真或允許一定失真的條件下，用盡可能少的符號來傳遞信源消息，提高信息傳輸率。號來傳遞信源消息，提高信息傳輸率。 l 以提高通信以提高通信有效性有效性為目的為目的。通常通過。通常通過壓縮信源的冗余壓縮信源的冗余度度來實現。采用的一般方法是壓縮每個信源符號的平來實現。采用的一般方法是壓縮每個信源符號的平均碼長。均碼長。 信源編碼概述l 信源編

2、碼理論是信息論的一個重要分支，其理論基礎信源編碼理論是信息論的一個重要分支，其理論基礎是信源編碼的兩個定理：是信源編碼的兩個定理：無失真信源編碼定理無失真信源編碼定理限失真信源編碼定理限失真信源編碼定理l 本章主要介紹本章主要介紹無失真信源編碼無失真信源編碼，它實質上是一種統，它實質上是一種統計匹配編碼，根據信源的不同概率分布而選用與之相計匹配編碼，根據信源的不同概率分布而選用與之相匹配的碼。匹配的碼。 信源編碼概述信源編碼概述l 信源的統計剩余度主要決定于以下兩個因素信源的統計剩余度主要決定于以下兩個因素 ：1）無記憶信源中，符號概率分布的非均勻性；）無記憶信源中，符號概率分布的非均勻性；2

3、）有記憶信源中，符號間的相關性及）有記憶信源中，符號間的相關性及符號概率分布符號概率分布的非均勻性的非均勻性。 信源編碼概述信源編碼概述l怎樣壓縮信源的冗余度？怎樣壓縮信源的冗余度？1) 去除碼符號間的相關性。去除碼符號間的相關性。2) 使碼符號等概分布。使碼符號等概分布。信源編碼器模型信源編碼器模型信宿信宿信道信道信源信源編碼器編碼器譯碼器譯碼器YXSSl 信源編碼：將信源符號序列按一定的數學規律映射信源編碼：將信源符號序列按一定的數學規律映射成碼符號序列的過程。成碼符號序列的過程。qsssS,2112 ,rXx xx 圖圖1 信源編碼器模型信源編碼器模型4.1 無失真可變長信源編碼定理無失

4、真可變長信源編碼定理l 將信源符號集中的符號將信源符號集中的符號 （或者長為（或者長為N的信源符號序的信源符號序列）映射成由碼符號列）映射成由碼符號 組成的長度為組成的長度為 的一一對應的的一一對應的碼符號序列碼符號序列 。編碼器編碼器,.,:21rxxxX碼字碼字qsssS,2112liiiiiwx xx信源編碼器模型信源編碼器模型ixisil12,qCw wwiw信源符號sip(si)碼1碼2s1p(s1)=1/2000s2p(s2)=1/40101s3p(s3)=1/810001s4p(s4)=1/811111例例: 4.112341234( )()()() ssssSp sp sp s

5、p sP信源編碼器模型信源編碼器模型l編碼器輸出的碼符號序列編碼器輸出的碼符號序列 稱為稱為碼字碼字；長度；長度 稱為碼稱為碼字長度，簡稱字長度，簡稱碼長碼長；全體碼字的集合；全體碼字的集合C稱為稱為碼碼。l若碼符號集合為若碼符號集合為X=0,1，則所得的碼字都是二元序，則所得的碼字都是二元序列，稱為列，稱為二元碼二元碼。關于編碼的一些術語關于編碼的一些術語iwisiwill將信源符號集中的每個信源符號將信源符號集中的每個信源符號 固定的映射成某固定的映射成某一個碼字一個碼字 ，這樣的碼稱為，這樣的碼稱為分組碼分組碼。 l若一個碼中所有碼字的碼長都相等，則稱為若一個碼中所有碼字的碼長都相等，則

6、稱為定長碼定長碼； 否則為否則為變長碼變長碼。1. 奇異性奇異性若一個碼中所有碼字互不相同，則稱為若一個碼中所有碼字互不相同，則稱為非奇異碼非奇異碼；否則為否則為奇異碼奇異碼。信源符號信源符號si碼碼1碼碼2s1s2s3s401100110100001一、信源編碼的相關概念一、信源編碼的相關概念2. 唯一可譯性唯一可譯性l 若任意一串有限長的碼符號序列只能被唯一地譯為若任意一串有限長的碼符號序列只能被唯一地譯為對應的信源符號序列，則稱此碼為對應的信源符號序列，則稱此碼為唯一可譯碼唯一可譯碼。信源符號信源符號si碼碼1碼碼2碼碼3s1s2s3s401100110100001010110111一、

7、信源編碼的相關概念一、信源編碼的相關概念l 唯一可譯碼應當滿足的條件唯一可譯碼應當滿足的條件(1,2,., )(1,2,., )iiw iqs iq碼字與信源符號一一對應碼字與信源符號一一對應2) 不同的信源符號序列對應不同的碼字序列不同的信源符號序列對應不同的碼字序列1) 2. 唯一可譯性唯一可譯性一、信源編碼的相關概念一、信源編碼的相關概念2. 唯一可譯性唯一可譯性例：例：1)11001104321ssss2s4s奇異碼奇異碼11譯碼譯碼奇異碼一定不是唯一可譯碼奇異碼一定不是唯一可譯碼一、信源編碼的相關概念一、信源編碼的相關概念2. 唯一可譯性唯一可譯性2)01001004321ssss非

8、奇異碼非奇異碼14321sssss2334ssss0 1 00 00 1 00 10 00 0 1 0譯碼譯碼譯碼譯碼一、信源編碼的相關概念一、信源編碼的相關概念2. 唯一可譯性唯一可譯性3)111001004321ssss等長碼等長碼非奇異碼非奇異碼0 0 0 1 1 0 1 14321ssss唯一可譯碼唯一可譯碼譯碼譯碼一、信源編碼的相關概念一、信源編碼的相關概念唯一可譯定長碼存在的條件唯一可譯定長碼存在的條件l對于定長碼，非奇異碼一定是唯一可譯碼。對于定長碼，非奇異碼一定是唯一可譯碼。l所謂非奇異碼，即信源符號集中的每一個信源符號所謂非奇異碼，即信源符號集中的每一個信源符號與碼中的某一個

9、碼字與碼中的某一個碼字 一一對應。一一對應。l設信源符號集中共有設信源符號集中共有 個符號，個符號， ， 碼符號集中共有碼符號集中共有 種碼元，種碼元， ， 定長碼碼長為定長碼碼長為 , 則要滿足非奇異性必然有則要滿足非奇異性必然有lrq 12,qSs ss,.,:21rxxxXiwislrq該條件是必要條件，而不是充分條件。該條件是必要條件，而不是充分條件。二、定長碼及定長信源編碼定理二、定長碼及定長信源編碼定理例：英文字母表中，每一字母用定長編碼轉換成二進制例：英文字母表中，每一字母用定長編碼轉換成二進制表示，碼字的最短長度是多少？表示，碼字的最短長度是多少？26q 解：解：2r 信源符號

10、數信源符號數碼符號數碼符號數lrqloglog264.7loglog2qlrmin5l二、定長碼及定長信源編碼定理二、定長碼及定長信源編碼定理若用若用r元碼對信源元碼對信源SN進行編碼，設進行編碼，設S中每個符號所需中每個符號所需的平均碼長為的平均碼長為 則定義：則定義：為該碼的編碼效率為該碼的編碼效率NLNrNLsHNlog)(18 要做到無失真的信源編碼，平均每個信源符號要做到無失真的信源編碼，平均每個信源符號所需最少的所需最少的r元碼元數為信源的熵元碼元數為信源的熵 。 即即 它是無失真信源壓縮的極限值。它是無失真信源壓縮的極限值。 若編碼的平均碼長小于信源的熵值若編碼的平均碼長小于信源

11、的熵值 ，則惟，則惟一可譯碼不存在，在譯碼或反變換時必然要帶一可譯碼不存在，在譯碼或反變換時必然要帶來失真或差錯。來失真或差錯。 通過對擴展信源進行變長編碼，當通過對擴展信源進行變長編碼，當N時，時，平均碼長平均碼長( )rHS( )rHS( )rHS19 無失真信源編碼的實質：無失真信源編碼的實質： 對離散信源進行適當的變換，使變換后形對離散信源進行適當的變換，使變換后形成的新的碼符號信源成的新的碼符號信源(即信道的輸入信源即信道的輸入信源)盡可盡可能為等概率分布，以使新信源的每個碼符號平能為等概率分布，以使新信源的每個碼符號平均所含的信息量達到最大，使信道的信息傳輸均所含的信息量達到最大，

12、使信道的信息傳輸率達到信道容量，實現信源與信道理想的統計率達到信道容量，實現信源與信道理想的統計匹配。這實際上就是香農第一定理的物理意義。匹配。這實際上就是香農第一定理的物理意義。20 為了衡量各種編碼是否達到極限情況，定義變長為了衡量各種編碼是否達到極限情況，定義變長碼的編碼效率為：碼的編碼效率為： 常通過編碼效率來衡量各種編碼的優劣常通過編碼效率來衡量各種編碼的優劣. 為了衡量各種編碼與最佳碼的差距，定義碼的剩為了衡量各種編碼與最佳碼的差距，定義碼的剩余度為：余度為： 信息傳輸率定義為：信息傳輸率定義為： 注意注意:雖然與在數值上相同，但它們的單位不同，編碼雖然與在數值上相同，但它們的單位

13、不同，編碼效率沒有單位，而信息傳輸率的單位是比特效率沒有單位，而信息傳輸率的單位是比特/碼符號。碼符號。LSHr)(LSHr)(11LSHR)(20:4521 為了使得平均編碼長度為最小，必須將概率大為了使得平均編碼長度為最小，必須將概率大的信息符號編以短的碼字，概率小的符號編以的信息符號編以短的碼字，概率小的符號編以長的碼字。能獲得最佳碼（或次最佳碼）的編長的碼字。能獲得最佳碼（或次最佳碼）的編碼方法有很多。碼方法有很多。 香農香農(shannon) 編碼、費諾編碼、費諾(Fano) 編碼、霍夫編碼、霍夫曼曼(Huffman)編碼等就是代表。編碼等就是代表。221 1 香農碼香農碼 香農第一

14、定理指出，可選擇每個碼字的長度滿香農第一定理指出，可選擇每個碼字的長度滿足關系式：足關系式： 或：或： x 表示不小于表示不小于 x 的整數。按不等式選擇的的整數。按不等式選擇的碼長所構成的碼稱香農碼。香農碼滿足克拉夫碼長所構成的碼稱香農碼。香農碼滿足克拉夫特不等式，所以一定存在對應碼字的長度的惟特不等式，所以一定存在對應碼字的長度的惟一可譯碼。一可譯碼。log()log()1(1, )iiip slp siq 1lo g(1,)()iiliqps 20:4523 一般情況下，按照香農編碼方法編出來的碼，一般情況下，按照香農編碼方法編出來的碼，其平均碼長不是最短的，也即不是緊致碼其平均碼長不是

15、最短的，也即不是緊致碼(最最佳碼佳碼)。只有當信源符號的概率分布使不等式。只有當信源符號的概率分布使不等式左邊的等號成立時，編碼效率才達到最高。左邊的等號成立時，編碼效率才達到最高。 香農碼的編碼步驟如下：香農碼的編碼步驟如下： 1）將個信源符號按概率遞減的方式進行排列：）將個信源符號按概率遞減的方式進行排列： 2）按香農不等式計算出每個信源符號的碼長）按香農不等式計算出每個信源符號的碼長 ； 3）為了編成惟一可譯碼，計算第）為了編成惟一可譯碼，計算第i個信源符號的個信源符號的累加概率累加概率 4）將累加概率）將累加概率 用二進制數表示。用二進制數表示。 5）取）取 對應二進制數的小數點后位構

16、成該信源符對應二進制數的小數點后位構成該信源符號的二進制碼字。號的二進制碼字。12qppp il11iikkPp iPiP20:4525()ip aiP1log( )ip sil1a2a3a4a5a6a7a概率累加概率碼長信源符號對應的二進制數碼字0.2000.0002.3430000.190.20.00112.4130010.180.390.01102.4830110.170.570.10012.5631000.150.740.10112.7431010.100.890.11103.34411100.010.990.11111106.6671111110例例:設信源共有七個信源符號，其概率分

17、布如表所設信源共有七個信源符號，其概率分布如表所示，試對該信源進行香農編碼。示，試對該信源進行香農編碼。 解解: 碼的性能分析：碼的性能分析： 通過計算可得此信源的熵通過計算可得此信源的熵: (比特符號比特符號) 而碼的平均長度而碼的平均長度: (二元碼符號符二元碼符號符號號) 編碼效率：編碼效率：71()()log()2.61iiiH Xp ap a 71()3 .1 4iiiLp al 0.831 20:45272 2 費諾碼費諾碼 費諾編碼屬于概率匹配編碼，但它一般也不是最費諾編碼屬于概率匹配編碼，但它一般也不是最佳的編碼方法，只有當信源的概率分布呈現佳的編碼方法，只有當信源的概率分布呈

18、現 分布形式的條件下，才能達到最佳碼的性能。分布形式的條件下，才能達到最佳碼的性能。( )ilip sr 20:4528 費諾碼的編碼步驟如下：費諾碼的編碼步驟如下： 1）信源符號以概率遞減的次序排列起來；）信源符號以概率遞減的次序排列起來； 2）將排列好的信源符號按概率值劃分成兩大組，使每組）將排列好的信源符號按概率值劃分成兩大組，使每組的概率之和接近于相等，并對每組各賦予一個二元碼符號的概率之和接近于相等，并對每組各賦予一個二元碼符號“0”和和“1”； 3）將每一大組的信源符號再分成兩組，使劃分后的兩個）將每一大組的信源符號再分成兩組，使劃分后的兩個組的概率之和接近于相等，再分別賦予一個二

19、元碼符號；組的概率之和接近于相等，再分別賦予一個二元碼符號； 4）依次下去，直至每個小組只剩一個信源符號為止；）依次下去，直至每個小組只剩一個信源符號為止； 5）信源符號所對應的碼字即為費諾碼。）信源符號所對應的碼字即為費諾碼。20:4529例例:將下列消息按二元費諾碼方法進行編碼。將下列消息按二元費諾碼方法進行編碼。20:4530 此信源的熵此信源的熵 (比特符號比特符號)， 而碼的平均長度而碼的平均長度 (二元碼符號符號二元碼符號符號) 顯然，該碼是緊致碼，編碼效率：顯然，該碼是緊致碼，編碼效率： 該碼之所以能達到最佳，是因為信源符號的概率分布該碼之所以能達到最佳，是因為信源符號的概率分布

20、正好滿足式，否則，在一般情況下是無法達到編碼效正好滿足式，否則，在一般情況下是無法達到編碼效率等于率等于“1”的。的。 ()2.75H X 2.75L 1 碼的性能分析：碼的性能分析：20:4531費諾碼具有如下的性質：費諾碼具有如下的性質： 費諾碼的編碼方法實際上是一種構造碼樹的方法，所以費諾碼是即時碼。費諾碼的編碼方法實際上是一種構造碼樹的方法，所以費諾碼是即時碼。 費諾碼考慮了信源的統計特性，使概率大的信源符號能對應碼長較短的費諾碼考慮了信源的統計特性，使概率大的信源符號能對應碼長較短的碼字，從而有效地提高了編碼效率。碼字，從而有效地提高了編碼效率。 費諾碼不一定是最佳碼。因為費諾碼編碼

21、方法不一定能使短碼得到充分費諾碼不一定是最佳碼。因為費諾碼編碼方法不一定能使短碼得到充分利用利用:當信源符號較多時，若有一些符號概率分布很接近時，分兩大組的組當信源符號較多時，若有一些符號概率分布很接近時，分兩大組的組合方法就會很多。可能某種分大組的結果，會使后面小組的合方法就會很多。可能某種分大組的結果，會使后面小組的“概率和概率和”相相差較遠，從而使平均碼長增加。差較遠，從而使平均碼長增加。20:45323 3 霍夫曼碼霍夫曼碼 1952年，霍夫曼（年，霍夫曼（Huffman）提出了一種構造）提出了一種構造最佳碼的方法，這是一種最佳的逐個符號的編最佳碼的方法，這是一種最佳的逐個符號的編碼方

22、法，一般就稱作霍夫曼碼。碼方法，一般就稱作霍夫曼碼。 設信源設信源 ，其對應的概率分布為，其對應的概率分布為 ，則對二元霍夫曼碼而言，則對二元霍夫曼碼而言，其編碼步驟如下：其編碼步驟如下： 12 ,.,qSs ss 12(),.,iqp sppp 20:4533 1）將）將q個信源符號按概率遞減的方式排列起來；個信源符號按概率遞減的方式排列起來； 2）用）用“0”、“1”碼符號分別表示概率最小的兩個信源符碼符號分別表示概率最小的兩個信源符號，并將這兩個概率最小的信源符號合并成一個新的符號，號，并將這兩個概率最小的信源符號合并成一個新的符號，從而得到只包含從而得到只包含q-1個符號的新信源，稱之

23、為個符號的新信源，稱之為S信源的信源的S1縮縮減信源；減信源； 3）將縮減信源中的符號仍按概率大小以遞減次序排列，）將縮減信源中的符號仍按概率大小以遞減次序排列，再將其最后兩個概率最小的符號合并成一個符號，并分別再將其最后兩個概率最小的符號合并成一個符號，并分別用用“0”、“1”碼符號表示，這樣又形成了由碼符號表示，這樣又形成了由q-2個符號構個符號構成的縮減信源成的縮減信源S2； 4）依次繼續下去，直到縮減信源只剩下兩個符號為止，）依次繼續下去，直到縮減信源只剩下兩個符號為止，將這最后兩個符號分別用將這最后兩個符號分別用“0”、“1”碼符號表示；碼符號表示； 5）從最后一級縮減信源開始，向前

24、返回，沿信源縮減方）從最后一級縮減信源開始，向前返回，沿信源縮減方向的反方向取出所編的碼元，得出各信源符號所對應的碼向的反方向取出所編的碼元，得出各信源符號所對應的碼符號序列，即為對應信源符號的碼字。符號序列，即為對應信源符號的碼字。20:4534 例例:對離散無記憶信源對離散無記憶信源 進行霍夫曼編碼。進行霍夫曼編碼。 解解:編碼過程如表所示：編碼過程如表所示： 1)將信源符號按概率大小由大至小排序。將信源符號按概率大小由大至小排序。 2)從概率最小的兩個信源符號和開始編碼，并按一定的從概率最小的兩個信源符號和開始編碼，并按一定的規則賦予碼符號，如下面的信源符號（小概率）為規則賦予碼符號，如

25、下面的信源符號（小概率）為“1”，上面的信源符號（大概率）為上面的信源符號（大概率）為“0”。若兩支路概率相等，。若兩支路概率相等，仍為下面的信源符號為仍為下面的信源符號為“1” 上面的信源符號為上面的信源符號為“0”。 3)將已編碼兩個信源符號概率合并，重新排隊，編碼。將已編碼兩個信源符號概率合并，重新排隊，編碼。 4)重復步驟重復步驟3）直至合并概率等于）直至合并概率等于“1.0”為止。為止。 5)從概率等于從概率等于“1.0”端沿合并路線逆行至對應消息編碼端沿合并路線逆行至對應消息編碼.12345()0.40.20.20.10.1iSsssssp s 20:453520:4536 碼的性

26、能分析：碼的性能分析： 信源的熵為：信源的熵為：H(s)=2.12 (比特符號比特符號) 從從 ，可得平均碼長為：，可得平均碼長為： 編碼效率為：編碼效率為：4 , 4 , 3 , 2 , 1:il2 . 241 . 041 . 032 . 022 . 014 . 051iiilpL9636. 02 . 212. 2)(LsH20:4537 按霍夫曼碼的編碼方法，可知這種碼有如下特征：按霍夫曼碼的編碼方法，可知這種碼有如下特征： 它是一種分組碼：各個信源符號都被映射成一組固定次它是一種分組碼：各個信源符號都被映射成一組固定次序的碼符號；序的碼符號； 它是一種惟一可解的碼：任何碼符號序列只能以一

27、種方它是一種惟一可解的碼：任何碼符號序列只能以一種方式譯碼；式譯碼； 它是一種即時碼：由于代表信源符號的節點都是終端節它是一種即時碼：由于代表信源符號的節點都是終端節點，因此其編碼不可能是其它終端節點對應的編碼的前綴，點，因此其編碼不可能是其它終端節點對應的編碼的前綴，霍夫曼編碼所得的碼字一定是即時碼。所以一串碼符號中霍夫曼編碼所得的碼字一定是即時碼。所以一串碼符號中的每個碼字都可不考慮其后的符號直接解碼出來。的每個碼字都可不考慮其后的符號直接解碼出來。 霍夫曼碼的譯碼：對接收到的霍夫曼碼序列可通過從左到霍夫曼碼的譯碼：對接收到的霍夫曼碼序列可通過從左到右檢查各個符號進行譯碼。右檢查各個符號進

28、行譯碼。20:4538 說明：說明： 霍夫曼碼是一種即時碼，可用碼樹形式來表示。霍夫曼碼是一種即時碼，可用碼樹形式來表示。 每次對縮減信源最后兩個概率最小的符號，用每次對縮減信源最后兩個概率最小的符號，用“0”和和“1”碼是可以任意的，所以可得到不同的碼是可以任意的，所以可得到不同的碼，但碼長不變，平均碼長也不變。碼，但碼長不變，平均碼長也不變。當縮減信源中縮減合并后得到的新符號的概率當縮減信源中縮減合并后得到的新符號的概率與其他信源符號概率相同時，從編碼方法上來說，與其他信源符號概率相同時，從編碼方法上來說，它們概率的排序是沒有限制的，因此也可得到不它們概率的排序是沒有限制的，因此也可得到不

29、同的碼。同的碼。 即對給定信源，用霍夫曼編碼方法得到的碼并非是惟即對給定信源，用霍夫曼編碼方法得到的碼并非是惟一，但平均碼長不變。一，但平均碼長不變。三種編碼的比較三種編碼的比較Huffman:不唯一，但對信源沒有特殊要求，且編碼效率較不唯一，但對信源沒有特殊要求，且編碼效率較高，設備要求簡單，綜合性能優于另外兩種。高，設備要求簡單，綜合性能優于另外兩種。相同點：相同點：三種編碼都考慮了信源的統計特性，使經常出三種編碼都考慮了信源的統計特性，使經常出現的信源符號對應較短的碼字，使平均碼長縮短，實現現的信源符號對應較短的碼字，使平均碼長縮短，實現了信源壓縮。了信源壓縮。不同點：不同點：shnno

30、n：有唯一的編碼，但編碼效率不是很高；：有唯一的編碼，但編碼效率不是很高；Fano:編碼方法不唯一，適合與分組概率相等或相近的信源；編碼方法不唯一，適合與分組概率相等或相近的信源；20:45394.5.3 MH編碼（游程編碼）編碼（游程編碼） 游程游程是指符號序列中各個符號連續重復出現而形成符號串是指符號序列中各個符號連續重復出現而形成符號串的長度，又稱游程長度或游長。的長度，又稱游程長度或游長。 游程編碼游程編碼（就是將這種符號序列映射成游程長度和對應符（就是將這種符號序列映射成游程長度和對應符號序列的位置的標志序列。如果知道了游程長度和對應符號序列的位置的標志序列。如果知道了游程長度和對應

31、符號序列的位置的標志序列，就可以完全恢復出原來的符號號序列的位置的標志序列，就可以完全恢復出原來的符號序列。序列。游程長度編碼游程長度編碼 舉例說明：舉例說明：aaaa bbb cc d eeeee fffffff (共共22228=176 bit)8=176 bit) 4a3b2c1d5e7f (共共128=96 bit)43215720:454120:4542 游程編碼特別適用于對相關信源的編碼。對二元相關信源，游程編碼特別適用于對相關信源的編碼。對二元相關信源，其輸出序列往往會出現多個連續的其輸出序列往往會出現多個連續的“0”或連續的或連續的“1”。在。在信源輸出的二元序列中，連續出現的信源輸出的二元序列中，連續出現的“0”符號稱為