信息論與編碼 第5章(1)教材

1、2021-12-161信源編碼信源編碼 第第5 5章章(第第1講）講）2021-12-162數(shù)字通信系統(tǒng)的一般模型數(shù)字通信系統(tǒng)的一般模型 等效信道等效信道 干擾源干擾源 物理信道物理信道 解調(diào)器解調(diào)器 編碼器編碼器 譯碼器譯碼器 信宿信宿 信源信源 調(diào)制器調(diào)制器 實(shí)際信道實(shí)際信道 編碼信道編碼信道 2021-12-163p信息通過信道傳輸?shù)叫潘薜倪^程即為信息通過信道傳輸?shù)叫潘薜倪^程即為通信通信。要做到。要做到既不失真又快速地通信，需要解決兩個(gè)問題：既不失真又快速地通信，需要解決兩個(gè)問題：n在不失真或允許一定失真條件下，在不失真或允許一定失真條件下，如何提高信息如何提高信息傳輸速度傳輸速度-這是

2、本章要討論的這是本章要討論的信源編碼信源編碼問題問題.n在信道受到干擾的情況下，在信道受到干擾的情況下，如何增加信號的抗干如何增加信號的抗干擾能力，同時(shí)又使得信息傳輸率最大擾能力，同時(shí)又使得信息傳輸率最大-這是下這是下章要討論的章要討論的信道編碼信道編碼問題問題.2021-12-1642021-12-165u信源編碼分為信源編碼分為無失真和限失真無失真和限失真。u無失真編碼無失真編碼，又名，又名冗余度壓縮冗余度壓縮編碼：僅對信源的冗余度進(jìn)編碼：僅對信源的冗余度進(jìn)行壓縮，行壓縮，不改變信源的熵不改變信源的熵；可逆編碼的基礎(chǔ)，只適用于離；可逆編碼的基礎(chǔ)，只適用于離散信源，主要用于文字、數(shù)據(jù)信源的壓

3、縮。散信源，主要用于文字、數(shù)據(jù)信源的壓縮。u限失真編碼限失真編碼，又名，又名熵壓縮熵壓縮編碼：在失真受限的情況下進(jìn)行編碼：在失真受限的情況下進(jìn)行限失真編碼。只適用于連續(xù)信源，主要用于圖像、語音信限失真編碼。只適用于連續(xù)信源，主要用于圖像、語音信源的壓縮。源的壓縮。p信源編碼的基礎(chǔ)是信息論中的兩個(gè)編碼定理信源編碼的基礎(chǔ)是信息論中的兩個(gè)編碼定理n無失真信源編碼無失真信源編碼 第一極限定理第一極限定理 n限失真信源編碼限失真信源編碼 第三極限定理第三極限定理p信道編碼定理（離散和連續(xù)信道）信道編碼定理（離散和連續(xù)信道） 第二極限定理第二極限定理2021-12-166信源編碼的主要任務(wù)信源編碼的主要任

4、務(wù)n減少冗余，提高編碼效率減少冗余，提高編碼效率。具體的說，就是針對信源輸。具體的說，就是針對信源輸出符號序列的統(tǒng)計(jì)特性，尋找一定的把信源輸出符號序出符號序列的統(tǒng)計(jì)特性，尋找一定的把信源輸出符號序列變換為最短碼字序列的方法。列變換為最短碼字序列的方法。n符號變換：使信源輸出符號與信道的輸入符號相匹配。符號變換：使信源輸出符號與信道的輸入符號相匹配。p信源編碼的信源編碼的基本途徑基本途徑有兩個(gè)有兩個(gè): :n一是編碼后使序列中的各個(gè)符號之間盡可能地互相獨(dú)立，一是編碼后使序列中的各個(gè)符號之間盡可能地互相獨(dú)立，即即解除相關(guān)性解除相關(guān)性-方法包括預(yù)測編碼和變換編碼方法包括預(yù)測編碼和變換編碼. .n二是使

5、編碼后各個(gè)符號出現(xiàn)的概率盡可能相等，即二是使編碼后各個(gè)符號出現(xiàn)的概率盡可能相等，即均勻均勻化分布化分布-方法主要是統(tǒng)計(jì)編碼方法主要是統(tǒng)計(jì)編碼. .2021-12-167p本章主要介紹信源編碼的基本思路與主要方法，討本章主要介紹信源編碼的基本思路與主要方法，討論論離散信源編碼離散信源編碼，首先從，首先從無失真編碼定理無失真編碼定理出發(fā)，重出發(fā)，重點(diǎn)討論以點(diǎn)討論以香農(nóng)碼香農(nóng)碼、費(fèi)諾碼費(fèi)諾碼和和哈夫曼碼哈夫曼碼為代表的最佳為代表的最佳無失真碼。然后介紹了無失真碼。然后介紹了限失真編碼定理限失真編碼定理。最后簡單。最后簡單介紹了一些其它常用的信源編碼方法。期望通過本介紹了一些其它常用的信源編碼方法。期

6、望通過本章學(xué)習(xí)能建立起信源壓縮編碼的基本概念。章學(xué)習(xí)能建立起信源壓縮編碼的基本概念。2021-12-1685.1 編碼的定義編碼的定義5.2 無失真信源編碼無失真信源編碼5.3 限失真信源編碼限失真信源編碼5.4 常用信源編碼方法簡介常用信源編碼方法簡介主主 要要 內(nèi)內(nèi) 容容2021-12-1695.1 5.1 編碼的定義編碼的定義2021-12-1610編碼的定義編碼的定義p編碼定理證明編碼定理證明: :n必存在一種編碼方法必存在一種編碼方法, ,使使代碼的平均長度代碼的平均長度可任意可任意接近但接近但不能低于符號熵不能低于符號熵; ;n達(dá)到這目標(biāo)的途徑就是使達(dá)到這目標(biāo)的途徑就是使概率與碼長

7、匹配概率與碼長匹配。p統(tǒng)計(jì)匹配編碼統(tǒng)計(jì)匹配編碼：n根據(jù)信源的根據(jù)信源的不同概率分布不同概率分布而選用與之匹配的編而選用與之匹配的編碼碼, ,以達(dá)到在系統(tǒng)中以達(dá)到在系統(tǒng)中傳信速率最小傳信速率最小。2021-12-1611p編碼器的作用：編碼器的作用：p 將信源符號集將信源符號集X中的符號中的符號 變換成由碼符號集變換成由碼符號集y中的中的碼元碼元 組成的長度為組成的長度為KL的一一對應(yīng)的的一一對應(yīng)的碼字碼字 。p 碼字集合叫做代碼組碼字集合叫做代碼組Y；碼字；碼字 所含碼元的個(gè)數(shù)稱為該碼字所含碼元的個(gè)數(shù)稱為該碼字的的碼長碼長，記為，記為KL 。1,2,iXiq1,2,iy imiYiY12,qX

8、XXX12, ,qYY YY 編碼器編碼器信源符號集信源符號集X代碼組代碼組Y基本符號基本符號y12, ,myy yy編碼的定義編碼的定義2021-12-1612如果信源輸出符號序列長度如果信源輸出符號序列長度L1，信源符號集，信源符號集A(a1，a2，an)，信源概率空間為，信源概率空間為 )()()(2121nnapapapaaaPX若將信源若將信源X通過二元信道傳輸，就必須把信源符通過二元信道傳輸，就必須把信源符號號ai變換成由變換成由0，1符號組成的碼符號序列，這個(gè)符號組成的碼符號序列，這個(gè)過程就是信源編碼。過程就是信源編碼。 編碼的定義編碼的定義2021-12-1613信源符號信源符

9、號信源符號信源符號概率概率 碼碼 表表 碼碼1 碼碼2 00 0 01 01 10 001 11 111 ia1a2a3a4a)(iap)(1ap)(2ap)(3ap)(4app若碼集為若碼集為0,1,所得碼字為所得碼字為二元序列二元序列,稱為稱為二元碼二元碼p例如例如,信源符號信源符號Xa1,a2,a3,a4,對應(yīng)不同碼字如表對應(yīng)不同碼字如表編碼的定義編碼的定義2021-12-1614編碼的定義編碼的定義信源符號信源符號 信源符號信源符號出現(xiàn)概率出現(xiàn)概率 碼碼 表表 碼碼0碼碼1碼碼2碼碼3碼碼4a1p(a1)=1/2000011a2p(a2)=1/40111101001a3p(a3)=1/

10、8100000100001a4p(a4)=1/811110110000001p等長碼等長碼：碼中所有碼字的長度都相同：碼中所有碼字的長度都相同p可變長碼可變長碼：碼中的碼字長短不一：碼中的碼字長短不一兩種碼：固定長度和可變長度的編碼。兩種碼：固定長度和可變長度的編碼。2021-12-1615分組碼的屬性：分組碼的屬性：(1)奇異碼和非奇異碼：奇異碼和非奇異碼：p非奇異碼非奇異碼：如果信源符號和碼字是一一對應(yīng)的，則稱該：如果信源符號和碼字是一一對應(yīng)的，則稱該碼為非奇異碼。如碼碼為非奇異碼。如碼0,2,3,40,2,3,4p奇異碼奇異碼：如果信源符號和碼字不是一一對應(yīng)的，則稱該：如果信源符號和碼字

11、不是一一對應(yīng)的，則稱該碼為奇異碼。如碼碼為奇異碼。如碼1 1分組碼分組碼/塊碼塊碼：將信源符號集：將信源符號集X中的每個(gè)符號中的每個(gè)符號 映射成一個(gè)映射成一個(gè)固定固定的碼字的碼字 。這種碼必須具有。這種碼必須具有某些屬性，才能保證在接收端能夠迅速可靠地譯碼。某些屬性，才能保證在接收端能夠迅速可靠地譯碼。1,2,iXiq1,2,iYiq編碼的定義編碼的定義2021-12-1616編碼的定義編碼的定義(2)(2)唯一可譯碼唯一可譯碼：n任意有限長的碼元序列任意有限長的碼元序列,只能被唯一地分割成一只能被唯一地分割成一個(gè)個(gè)的碼字。個(gè)個(gè)的碼字。p例：例：0,10,11是一種唯一可譯碼。是一種唯一可譯碼

12、。p任意一串有限長碼序列任意一串有限長碼序列,如如100111000,只能被分只能被分割成割成10,0,11,10,0,0。任何其他分割法都會產(chǎn)生。任何其他分割法都會產(chǎn)生一些非定義的碼字。一些非定義的碼字。p奇異碼不是唯一可譯碼奇異碼不是唯一可譯碼p非奇異碼非奇異碼 n唯一可譯碼唯一可譯碼 碼碼3 100,1,1,1000n非唯一可譯碼非唯一可譯碼 碼碼2 100001002021-12-1617(2)唯一可譯碼：唯一可譯碼：例如：例如：信源信源概率概率pi 編碼編碼編碼編碼編碼編碼編碼編碼編碼編碼U11/2000111U21/4010101001U31/810100100001U41/811

13、100110000001對于碼元序列對于碼元序列100111000110，分別用編碼，分別用編碼1，編碼編碼3，編碼，編碼4，試判斷那種是唯一可譯碼？，試判斷那種是唯一可譯碼？2021-12-1618編碼的定義編碼的定義 p非即時(shí)碼非即時(shí)碼：n如果接收端收到一個(gè)完整的碼字后不能立即譯碼如果接收端收到一個(gè)完整的碼字后不能立即譯碼,還還需等下一個(gè)碼字開始接收后才能判斷是否可以譯碼需等下一個(gè)碼字開始接收后才能判斷是否可以譯碼p即時(shí)碼（非延長碼，異前綴碼）即時(shí)碼（非延長碼，異前綴碼）：n在譯碼時(shí)無需參考后續(xù)的碼符號就能在譯碼時(shí)無需參考后續(xù)的碼符號就能立即立即作出判斷作出判斷,譯成對應(yīng)的信源符號。譯成對

14、應(yīng)的信源符號。n任意一個(gè)碼字都任意一個(gè)碼字都不是不是其它碼字的其它碼字的前綴前綴部分部分p在在延長碼延長碼中中,有的碼是唯一可譯的有的碼是唯一可譯的,取決于碼的總體結(jié)取決于碼的總體結(jié)構(gòu)構(gòu),如碼如碼3, “1,10,100,1000”.2021-12-1619例如：例如：信源信源概率概率pi 編碼編碼編碼編碼編碼編碼編碼編碼編碼編碼U11/2000000U21/401011001U31/810100110011U41/81110111110111試判斷編碼試判斷編碼4和編碼和編碼5是否為即時(shí)碼？是否為即時(shí)碼？2021-12-1620編碼的定義編碼的定義碼碼非分組碼非分組碼 分組碼分組碼奇異碼奇異

15、碼 非奇異碼非奇異碼 非唯一可譯碼非唯一可譯碼 唯一可譯碼唯一可譯碼非即時(shí)碼非即時(shí)碼 即時(shí)碼即時(shí)碼 (非延長碼非延長碼) 2021-12-1621p碼樹從樹根開始向下長出碼樹從樹根開始向下長出m個(gè)樹枝，成為個(gè)樹枝，成為m進(jìn)制碼樹，進(jìn)制碼樹，樹枝代表碼元，樹枝與樹枝的交點(diǎn)叫做樹枝代表碼元，樹枝與樹枝的交點(diǎn)叫做節(jié)點(diǎn)節(jié)點(diǎn)。經(jīng)過。經(jīng)過r個(gè)樹枝才能到達(dá)的節(jié)點(diǎn)稱為個(gè)樹枝才能到達(dá)的節(jié)點(diǎn)稱為r階節(jié)點(diǎn)階節(jié)點(diǎn)。向下不長出樹。向下不長出樹枝的節(jié)點(diǎn)稱為枝的節(jié)點(diǎn)稱為終端節(jié)點(diǎn)終端節(jié)點(diǎn)或或端點(diǎn)端點(diǎn)。m進(jìn)制碼樹各節(jié)點(diǎn)進(jìn)制碼樹各節(jié)點(diǎn)（包括樹根）向下長出的樹枝不會超過（包括樹根）向下長出的樹枝不會超過m,若樹碼的若樹碼的各個(gè)分支

16、都延伸到最后一級端點(diǎn)稱為各個(gè)分支都延伸到最后一級端點(diǎn)稱為滿樹滿樹（整樹），（整樹），否則稱為非滿樹非整樹。否則稱為非滿樹非整樹。p碼樹上任一節(jié)點(diǎn)都對應(yīng)一個(gè)碼字，組成該碼字的碼碼樹上任一節(jié)點(diǎn)都對應(yīng)一個(gè)碼字，組成該碼字的碼元就是從樹根開始到該節(jié)點(diǎn)所經(jīng)過的樹枝（碼元）。元就是從樹根開始到該節(jié)點(diǎn)所經(jīng)過的樹枝（碼元）。p一個(gè)碼，如果其所有的碼字均處于終端節(jié)點(diǎn)，即端一個(gè)碼，如果其所有的碼字均處于終端節(jié)點(diǎn)，即端點(diǎn)，則該碼就為非延長碼。點(diǎn)，則該碼就為非延長碼。編碼的定義編碼的定義-用碼樹來構(gòu)造碼字用碼樹來構(gòu)造碼字2021-12-1622p碼樹：表示各碼字的構(gòu)成（碼樹：表示各碼字的構(gòu)成（m進(jìn)制）進(jìn)制） A010

17、0000000000001111111011111二進(jìn)制碼樹2000001111122222三進(jìn)制碼樹樹根碼字的起點(diǎn) 分成m個(gè)樹枝碼的進(jìn)制數(shù)終端節(jié)點(diǎn)碼字1101中間節(jié)點(diǎn)碼字的一部分節(jié)數(shù)碼長2021-12-1623碼411110001010010001碼400001110101101110p樹碼樹碼n如果有如果有n個(gè)信源符號個(gè)信源符號,那么在碼樹上就要選擇那么在碼樹上就要選擇n個(gè)個(gè)終終端節(jié)點(diǎn)端節(jié)點(diǎn),用相應(yīng)的用相應(yīng)的r元基本符號表示這些碼字。元基本符號表示這些碼字。碼001001111100100p任一任一即時(shí)碼即時(shí)碼都可用樹圖都可用樹圖法來表示。法來表示。p當(dāng)碼字長度給定當(dāng)碼字長度給定,即時(shí)即時(shí)

18、碼不是唯一的。碼不是唯一的。 2021-12-162411010001001000p碼碼3對應(yīng)的樹如下圖對應(yīng)的樹如下圖:編碼的定義編碼的定義p該碼樹從根到終端節(jié)點(diǎn)所經(jīng)路徑上每一個(gè)該碼樹從根到終端節(jié)點(diǎn)所經(jīng)路徑上每一個(gè)中間節(jié)中間節(jié)點(diǎn)皆為碼字點(diǎn)皆為碼字,因此滿足前綴條件。因此滿足前綴條件。p雖然碼雖然碼3不是即時(shí)碼不是即時(shí)碼,但它是唯一可譯碼。但它是唯一可譯碼。 2021-12-1625編碼的定義編碼的定義p滿樹：滿樹：n每個(gè)節(jié)點(diǎn)上都有每個(gè)節(jié)點(diǎn)上都有r個(gè)分枝的樹個(gè)分枝的樹等長碼等長碼p非滿樹：非滿樹：n變長碼變長碼p用樹的概念可導(dǎo)出用樹的概念可導(dǎo)出唯一可譯碼唯一可譯碼存在存在的的充分和必要充分和必要

19、條件條件,即各碼字的長度即各碼字的長度Ki應(yīng)符合應(yīng)符合Kraft不等式不等式式中:m是進(jìn)制數(shù)n是信源符號數(shù)11niKim2021-12-1626p例例：設(shè)二進(jìn)制碼樹中：設(shè)二進(jìn)制碼樹中X=(a1 , a2 , a3 , a4), K1=1,K2=2,K3=2,K4=3,應(yīng)用應(yīng)用Kraft不等式不等式,得：得： 不存在滿足這種不存在滿足這種Ki的唯一可譯碼的唯一可譯碼 0001101011011中間中間節(jié)節(jié)點(diǎn)點(diǎn)p如果將各碼字長度改成如果將各碼字長度改成K1=1,K2=2,K3=3,K4=3,則則18922222322141iKi122222332141iKi這樣的碼字就存這樣的碼字就存在唯一可譯碼

20、在唯一可譯碼 1112021-12-1627編碼的定義編碼的定義nKraft不等式只是用來說明唯一可譯碼是否存在不等式只是用來說明唯一可譯碼是否存在,并不能作為唯一可譯碼的判據(jù)。并不能作為唯一可譯碼的判據(jù)。n如碼字如碼字0，10，010，111雖然滿足雖然滿足Kraft不等不等式式,但它不是唯一可譯碼。但它不是唯一可譯碼。2021-12-1628唯一可譯碼的判斷法唯一可譯碼的判斷法p方法一根據(jù)異前綴碼是惟一可譯碼：方法一根據(jù)異前綴碼是惟一可譯碼：n首先觀察是否是非奇異碼。若是奇異碼，肯定不是唯一可首先觀察是否是非奇異碼。若是奇異碼，肯定不是唯一可譯碼譯碼n其次，計(jì)算是否滿足其次，計(jì)算是否滿足K

21、raft不等式。若不滿足一定不是唯不等式。若不滿足一定不是唯一可譯碼；一可譯碼；n然后將碼畫成一棵樹圖，觀察是否滿足異前綴碼的樹圖的然后將碼畫成一棵樹圖，觀察是否滿足異前綴碼的樹圖的構(gòu)造，若滿足則是唯一可譯碼。構(gòu)造，若滿足則是唯一可譯碼。n缺點(diǎn)：若是前綴碼時(shí)，則無法判斷是否是唯一可譯碼。缺點(diǎn)：若是前綴碼時(shí)，則無法判斷是否是唯一可譯碼。2021-12-1629惟一可譯碼的判斷準(zhǔn)則惟一可譯碼的判斷準(zhǔn)則p方法二用方法二用A.A.Sardinas和和G.W.Patterson設(shè)計(jì)的判斷法：設(shè)計(jì)的判斷法：n算法思想：根據(jù)惟一可譯碼的定義可知，當(dāng)且僅當(dāng)有限長算法思想：根據(jù)惟一可譯碼的定義可知，當(dāng)且僅當(dāng)有限

22、長的碼符號序列能譯成兩種不同的碼字序列，則此碼是非惟的碼符號序列能譯成兩種不同的碼字序列，則此碼是非惟一的可譯變長碼。即如下圖情況發(fā)生，其中一的可譯變長碼。即如下圖情況發(fā)生，其中Ai和和Bi都是碼都是碼字。在下圖中，字。在下圖中，B1一定是一定是A1的前綴，而的前綴，而A1的尾隨后綴一的尾隨后綴一定是另一碼字定是另一碼字B2的前綴；又的前綴；又B2的尾隨后綴又是其他碼字的尾隨后綴又是其他碼字的前綴。最后，碼符號序列的尾部一定是一個(gè)碼字。的前綴。最后，碼符號序列的尾部一定是一個(gè)碼字。A1A2A3AmB1B2B3Bm有限長碼符號序列譯成兩種不同的碼字序列2021-12-1630pA.A.Sardi

23、nas和和G.W.Patterson算法步驟算法步驟n計(jì)算分組碼中所有可能的尾隨后綴集合計(jì)算分組碼中所有可能的尾隨后綴集合A,觀察觀察A中有中有沒有包含任一碼字，若無則為唯一可譯碼；若有則一沒有包含任一碼字，若無則為唯一可譯碼；若有則一定不是唯一可譯碼。定不是唯一可譯碼。n集合集合A的構(gòu)造：的構(gòu)造：p首先觀察碼首先觀察碼C中最短的碼字是否是其它碼字的前綴。若中最短的碼字是否是其它碼字的前綴。若是，將其所有可能的尾隨后綴排列出。而這些尾隨后綴是，將其所有可能的尾隨后綴排列出。而這些尾隨后綴又可能是某些碼字的前綴，再將由這些尾隨后綴產(chǎn)生的又可能是某些碼字的前綴，再將由這些尾隨后綴產(chǎn)生的新的尾隨后綴

24、列出。新的尾隨后綴列出。p然后再觀察這些新的尾隨后綴是否是某些碼字的前綴，然后再觀察這些新的尾隨后綴是否是某些碼字的前綴，再將產(chǎn)生的尾隨后綴列出。這樣，首先獲得由最短的碼再將產(chǎn)生的尾隨后綴列出。這樣，首先獲得由最短的碼字能引起的所有尾隨后綴。字能引起的所有尾隨后綴。p接著，按照上述將次短的碼字接著，按照上述將次短的碼字等等，所有碼字可能產(chǎn)等等，所有碼字可能產(chǎn)生的尾隨后綴全部列出。由此得到碼生的尾隨后綴全部列出。由此得到碼C的所有可能的尾的所有可能的尾隨后綴組成的集合隨后綴組成的集合A。2021-12-1631p例：現(xiàn)設(shè)例：現(xiàn)設(shè)C=0，10，1100，1110，1011，1101，來判斷是，來判

25、斷是否是惟一可譯碼。否是惟一可譯碼。n解法一：解法一：p首先碼字首先碼字C是非奇異碼，又由題知，信源符號數(shù)為是非奇異碼，又由題知，信源符號數(shù)為q=6，輸出信源，輸出信源的碼符號數(shù)為的碼符號數(shù)為r=2，根據(jù)，根據(jù)kraft不等式得，不等式得， 滿足滿足kraft不等式。不等式。p最后畫出樹圖，如下圖所示。又圖知，該碼是前綴碼，所以還無最后畫出樹圖，如下圖所示。又圖知，該碼是前綴碼，所以還無法判斷是否是惟一可譯碼。法判斷是否是惟一可譯碼。110101010010101010101010010101碼字0碼字1 0碼字1 0 1 1碼字1 1 0 0碼字1 1 0 1碼字1 1 1 01244441

26、2222221qliir2021-12-1632p解法二（根據(jù)解法二（根據(jù)A.A.Sardinas和和G.W.Patterson算法）：因?yàn)樗惴ǎ阂驗(yàn)樽疃檀a字為最短碼字為“0”，不是其他碼字的前綴，所以它沒有尾隨，不是其他碼字的前綴，所以它沒有尾隨后綴。觀察碼字后綴。觀察碼字“10”，它是碼字，它是碼字“1011”的前綴，所以有的前綴，所以有 尾隨后綴。根據(jù)下圖可得，尾隨后綴。根據(jù)下圖可得，A=11，00，10，01，0，1，100，110，011，101?？梢姡??？梢?，A集中集中“10”和和“0”都是碼字，都是碼字，故碼故碼C不是惟一可譯碼。（對不是惟一可譯碼。（對00，碼字，碼字0是它的

27、前綴，所以是它的前綴，所以有尾隨后綴有尾隨后綴0）101100100101110100110011101011碼字尾隨后綴2021-12-16335.2 5.2 無失真信源編碼無失真信源編碼2021-12-1634無失真信源編碼無失真信源編碼p信源編碼器輸入的消息序列信源編碼器輸入的消息序列: X=(X1 X2Xl XL), Xla1,an, 輸入的消息總共有輸入的消息總共有nL種可能的組合種可能的組合p輸出的輸出的碼字碼字為為: Y=(Y1 Y2 Yk YKL ) , Ykb1,bm 輸出的碼字總共有輸出的碼字總共有mKL種可能的組合。種可能的組合。信源編碼器碼表碼表信源信源信道信道XYL長

28、序列KL長碼字2021-12-1635無失真信源編碼無失真信源編碼p實(shí)現(xiàn)實(shí)現(xiàn)的信源編碼的信源編碼,要求要求:n信源符號信源符號X1 X2Xl XL 是一一對應(yīng)的是一一對應(yīng)的n 碼字碼字Y1 Y2Yk YKLp能夠無失真或能夠無失真或無差錯(cuò)地從無差錯(cuò)地從Y恢復(fù)恢復(fù)X,也就是能正確地也就是能正確地進(jìn)行反變換或譯碼進(jìn)行反變換或譯碼 ;p傳送傳送Y時(shí)所需要的時(shí)所需要的信息率最小信息率最小 MLmLKKLlog1log_信息率最小信息率最小就是找到一種編碼方式使就是找到一種編碼方式使最小最小2021-12-16365.2.1 5.2.1 定長編碼定理定長編碼定理p在在定長定長編碼中編碼中,K（KL）是是

29、定值定值。目的是尋找。目的是尋找最小最小K值值。p編碼器輸入編碼器輸入X=(X1 X2Xl XL), Xla1,an, 輸入的輸入的消息總共有消息總共有nL種可能的組合種可能的組合p輸出的碼字輸出的碼字Y=(Y1 Y2 Yk YK ) , Ykb1,bm,輸輸出的碼字總共有出的碼字總共有mK種可能的組合種可能的組合p若對信源進(jìn)行若對信源進(jìn)行定長定長編碼編碼,必須滿足必須滿足: nLmK 信源編碼器碼表碼表信源信源信道信道XYL長序列K長碼字2021-12-1637定長編碼定長編碼p若對信源進(jìn)行若對信源進(jìn)行定長定長編碼編碼,必須滿足必須滿足: mnLKmnKLloglog或p只有當(dāng)只有當(dāng)K長的碼

30、符號序列數(shù)長的碼符號序列數(shù) mK大于或等于信源的符大于或等于信源的符號數(shù)號數(shù)nL時(shí)時(shí),才可能存在才可能存在定長定長非奇異碼。非奇異碼。 p例如英文電報(bào)有例如英文電報(bào)有27個(gè)符號個(gè)符號,n=27,L=1,m=2(二元編碼二元編碼)527logloglog222mnLK每個(gè)英文電報(bào)符號至少要用5位二元符號編碼2021-12-1638定長編碼定長編碼p實(shí)際英文電報(bào)符號信源實(shí)際英文電報(bào)符號信源,在考慮了符號出現(xiàn)的概率在考慮了符號出現(xiàn)的概率以及符號之間的依賴性后以及符號之間的依賴性后,平均每個(gè)英文電報(bào)符號平均每個(gè)英文電報(bào)符號所提供的信息量約等于所提供的信息量約等于1.4比特比特,大大小于大大小于5比特。

31、比特。p編碼后編碼后5個(gè)二元符號只攜帶約個(gè)二元符號只攜帶約1.4比特信息量。比特信息量。p定長編碼的信息傳輸效率極低。定長編碼的信息傳輸效率極低。2021-12-1639定長編碼定理定長編碼定理p定長編碼定理定長編碼定理：p由由L個(gè)符號組成的、每個(gè)符號的熵為個(gè)符號組成的、每個(gè)符號的熵為HL(X)的無記憶的無記憶平穩(wěn)信源符號序列平穩(wěn)信源符號序列X1XlXL,可用可用 K個(gè)符號個(gè)符號Y1YkYK(每個(gè)符號有每個(gè)符號有m種可能值種可能值)進(jìn)行定長編碼。進(jìn)行定長編碼。對任意對任意0,0,只要只要 則當(dāng)則當(dāng)L足夠大時(shí)足夠大時(shí),必可使譯碼差錯(cuò)小于必可使譯碼差錯(cuò)小于;反之反之,當(dāng)當(dāng) 時(shí)時(shí),譯碼差錯(cuò)一定是有限

32、值譯碼差錯(cuò)一定是有限值,而當(dāng)而當(dāng)L足夠大時(shí)足夠大時(shí),譯碼幾乎譯碼幾乎必定出錯(cuò)必定出錯(cuò) )(logXLHmLK2)(logXLHmLK2021-12-1640定長編碼定理定長編碼定理當(dāng)編碼器容許的輸出信息率當(dāng)編碼器容許的輸出信息率,也就是當(dāng)每個(gè)信源符也就是當(dāng)每個(gè)信源符號所必須輸出的碼長是號所必須輸出的碼長是 時(shí)時(shí),只要只要 ,這種編碼器一定可以做到這種編碼器一定可以做到幾乎幾乎無失真無失真,也就是收端的譯碼差錯(cuò)概率接近于零也就是收端的譯碼差錯(cuò)概率接近于零,條件是所取的符號數(shù)條件是所取的符號數(shù)L足夠大足夠大。MLmLKKLlog1log_)(_XHKL2021-12-1641p將定理的條件改寫成將

33、定理的條件改寫成其中：其中：左邊：左邊：KL長碼字所能攜帶的最大信息，長碼字所能攜帶的最大信息， 右邊：右邊：L長信源序列攜帶的信息量。長信源序列攜帶的信息量。log()()LLKmLHXH Xp上述定理表明上述定理表明: :n只要碼字所能攜帶的信息量大于信源序列輸出的只要碼字所能攜帶的信息量大于信源序列輸出的信息量信息量, ,則可以使傳輸幾乎無失真則可以使傳輸幾乎無失真, ,當(dāng)然條件是當(dāng)然條件是L足夠大。足夠大。n反之反之, ,當(dāng)當(dāng) 時(shí)時(shí), ,不可能構(gòu)成無失真的編不可能構(gòu)成無失真的編碼碼, ,也就是不可能做一種編碼器也就是不可能做一種編碼器, ,能使收端譯碼時(shí)能使收端譯碼時(shí)差錯(cuò)概率趨于零。差

34、錯(cuò)概率趨于零。n 時(shí)時(shí), ,則為臨界狀態(tài)則為臨界狀態(tài), ,可能無失真可能無失真, ,也可也可能有失真。能有失真。 )(_XHKL)(_XHKL2021-12-1642_111234567881,()3/()3/33 000,001,010,011 100,101,110,111LHXbitKHXbitbitbitxxxxxxxx例如某信源有 種等概率符號，現(xiàn)假設(shè)則信源熵達(dá)到最大值符號, 設(shè)符號（臨界狀態(tài)）所以，該信源肯定可以用的信息速率進(jìn)行無失真的編碼（相當(dāng)于每一個(gè)符號對應(yīng)一個(gè)的碼字）。例如定長編碼定理的應(yīng)用例子：定長編碼定理的應(yīng)用例子：2021-12-1643定長編碼定理的應(yīng)用例子：定長編碼

35、定理的應(yīng)用例子：概率比較小。小，這時(shí)使差錯(cuò)號序列出現(xiàn)的概率特別取值比較大，有一些符如果而會引起差錯(cuò)。但是其它的碼字來代替，從現(xiàn)這些符號，也只能用果出有對應(yīng)的碼字，信源如則會有部分信源符號沒如果取個(gè)碼字，所以種信源符號共需要的要求，前面的無失真信源編碼種可能的碼字，而根據(jù)符號共可以表示由于符號此時(shí)符號。則有率不相等時(shí)，如果信源輸出的符號概LKbitbitXHKbitXHapi,55. 2886856. 52/55. 2/55. 2)(/55. 2)(04. 0 ,05. 0 ,06. 0,07. 0 , 1 . 0 , 1 . 0 ,18. 0 , 4 . 0)(_55. 21_12021-12

36、-1644定長編碼定理定長編碼定理p為了衡量編碼效果為了衡量編碼效果,定義定義編碼效率編碼效率：0,)()(XHXHLLp對定長編碼對定長編碼,若要實(shí)現(xiàn)幾乎無失真編碼若要實(shí)現(xiàn)幾乎無失真編碼,則信源長度則信源長度必須滿足（必須滿足（為差錯(cuò)率為差錯(cuò)率）:22)(XL 22() ( )() iXE I xH Xn信源單符號的自信息方信源單符號的自信息方差差 （離散無記憶）（離散無記憶）KXHL)(p最佳編碼效率最佳編碼效率：p闡明了編碼效率接近闡明了編碼效率接近1的理想編碼器的存在性，使的理想編碼器的存在性，使輸出符號信息率與信源熵之比接近于輸出符號信息率與信源熵之比接近于12021-12-1645

37、例例5-212345678_2.83( )0.40.180.10.10.070.060.050.04()2.55/90%,1() 2.83/27.11,7.118LXaaaaaaaap xH XbitLHXKbit設(shè)離散無記憶信源概率空間為：根據(jù)信源熵的計(jì)算公式可以得到： 符號如果用二元編碼，要求編碼效率為并且取符號同時(shí)由于種來表示 個(gè)符號8,0.04a顯然不夠，如果去掉概率最小的則誤碼率為。2021-12-1646p方差：方差：p若取差錯(cuò)率若取差錯(cuò)率106,編碼效率為編碼效率為90%(則則=0.28=0.28),則則L應(yīng)滿足應(yīng)滿足22281282. 7)()(log)(bitXHppXiii

38、76222108 . 91028. 082. 7)(XLp在差錯(cuò)率和編碼效率要求并不十分苛刻的條件下在差錯(cuò)率和編碼效率要求并不十分苛刻的條件下,需需要要L=108個(gè)信源符號進(jìn)行聯(lián)合編碼個(gè)信源符號進(jìn)行聯(lián)合編碼,這顯然很難實(shí)現(xiàn)這顯然很難實(shí)現(xiàn)2021-12-16475.2.2 5.2.2 變長編碼定理變長編碼定理p在在變長變長編碼中碼長編碼中碼長K是變化是變化的。的。p我們可根據(jù)信源各個(gè)符號的我們可根據(jù)信源各個(gè)符號的統(tǒng)計(jì)特性統(tǒng)計(jì)特性,如概率大的符如概率大的符號用短碼號用短碼,概率小的用較長的碼概率小的用較長的碼,這樣在大量信源符這樣在大量信源符號編成碼后平均每個(gè)信源符號所需的輸出符號數(shù)就號編成碼后平

39、均每個(gè)信源符號所需的輸出符號數(shù)就可以降低可以降低,從而提高編碼效率從而提高編碼效率2021-12-1648變長編碼定理變長編碼定理p單個(gè)符號變長編碼定理單個(gè)符號變長編碼定理：n若一離散無記憶信源的符號熵為若一離散無記憶信源的符號熵為H(X),每個(gè)信源每個(gè)信源符號用符號用m進(jìn)制碼元進(jìn)行變長編碼進(jìn)制碼元進(jìn)行變長編碼,一定存在一種無一定存在一種無失真編碼方法失真編碼方法,其其碼字平均長度碼字平均長度滿足下列不等式滿足下列不等式:()()1 loglogLH XH XKmm2021-12-1649變長編碼定理變長編碼定理p離散平穩(wěn)無記憶序列變長編碼定理離散平穩(wěn)無記憶序列變長編碼定理n對于平均符號熵為對于平均符號熵為HL(X)的離散平穩(wěn)無記憶信源的離散平穩(wěn)無記憶信源,必存在一種無失真編碼方法必存在一種無失真編碼方法,使使平均信息率平均信息率 滿滿足不等式足不等式 ( )( )( ) LLHKHXXKn其中其中為任意小正數(shù)為任意小正數(shù)logLKKmL2021-12-1650變長編碼定理變長編碼定理p用變長編碼來達(dá)到相當(dāng)高的編碼效率用變長編碼來達(dá)到相當(dāng)高的編碼效率,一般所要求的