信息論課件chap3[1]

1、第三章第三章 信源編碼（一）信源編碼（一）離散信源無(wú)失真編碼離散信源無(wú)失真編碼l1、信源及其分類l2、離散無(wú)記憶信源的等長(zhǎng)編碼l3、離散無(wú)記憶信源的不等長(zhǎng)編碼l4、最佳不等長(zhǎng)編碼l5、算術(shù)編碼l6、LZ編碼前前 言言一、通信中的兩個(gè)問(wèn)題：1. 信源的輸出如何描述：計(jì)算信源信息量的問(wèn)題2. 如何表示信源的輸出：信源編碼的問(wèn)題二、信源編碼的分類： 什么是編碼？1. 無(wú)失真信源編碼：2. 限定失真的信源編碼：消息集到碼字集的一種映射3.1 信源及其分類信源及其分類信源的概念 直觀理解，信源就是信息的來(lái)源。但是必須要注意兩點(diǎn)：l在一個(gè)固定的時(shí)刻，信源發(fā)出的是一個(gè)隨機(jī)變量隨機(jī)變量。l隨著時(shí)間的延續(xù)，信源

2、發(fā)出的是一個(gè)隨機(jī)過(guò)程。隨機(jī)過(guò)程。因此，一般的信源種類太多，其統(tǒng)計(jì)性質(zhì)太復(fù)雜。怎樣做工程實(shí)用的簡(jiǎn)化？信源及其分類信源及其分類信源及其分類信源及其分類l離散信源l連續(xù)信源l無(wú)記憶信源l有記憶信源l簡(jiǎn)單信源獨(dú)立同分布l平穩(wěn)信源，各態(tài)歷經(jīng)源lM階記憶源l時(shí)間離散連續(xù)源l隨機(jī)波形源輸出消息是否連續(xù)各符號(hào)是否統(tǒng)計(jì)獨(dú)立離散信源離散信源 ： 信源每隔一個(gè)定長(zhǎng)時(shí)間段就發(fā)出一個(gè)隨機(jī)變量；隨著時(shí)間的延續(xù)，信源發(fā)出的是隨機(jī)變量序列U-2U-1U0U1U2，其中l(wèi)Uk為第k個(gè)時(shí)間段發(fā)出的隨機(jī)變量；l每個(gè)Uk都是一個(gè)離散型的隨機(jī)變量。離散無(wú)記憶信源離散無(wú)記憶信源 ：隨機(jī)變量、U-2、U-1、U0、U1、U2、相互獨(dú)立。離

3、散無(wú)記憶簡(jiǎn)單信源：離散無(wú)記憶簡(jiǎn)單信源： 隨機(jī)變量、U-2、U-1、U0、U1、U2、具有相同的概率分布。 （總結(jié)：離散無(wú)記憶簡(jiǎn)單信源就是時(shí)間離散、事件離散、各隨機(jī)變量獨(dú)立同分布的信源。課程學(xué)習(xí)所面對(duì)的信源將主要是離散無(wú)記憶簡(jiǎn)單信源）信源及其分類信源及其分類3.2 離散無(wú)記憶源的等長(zhǎng)離散無(wú)記憶源的等長(zhǎng)編碼編碼一、一些基本的概念離散無(wú)記憶源： DMS1. 消息集A：字母表A=a1,aK,概率p1,pK,且各概率累加和為1。長(zhǎng)為L(zhǎng)的源輸出序列uL=u1,uL，共有KL種序列。稱集合UL為消息集消息集。2. 碼字、D元碼碼符號(hào)字母表B=b1,bD,以碼符號(hào)表示源輸出序列，每個(gè)碼符號(hào)序列稱為碼字碼字。碼

4、符號(hào)字母表B中的字符個(gè)數(shù)為D，對(duì)應(yīng)的碼字被稱為D元碼例例：離散無(wú)記憶簡(jiǎn)單信源發(fā)出的隨機(jī)變量序列為：U-2U-1U0U1U2。其中U1的事件有3個(gè)：晴, 云, 陰。(U1U2)有9個(gè)事件（晴晴），（晴云），（晴陰），（云晴），（云云），（云陰），（陰晴），（陰云）， （陰陰）。用字母表0, 1對(duì)(U1U2)的事件進(jìn)行2元編碼如下：（晴晴）0000，（晴云）0001，（晴陰）0011，（云晴）0100，（云云）0101，（云陰）0111，（陰晴）1100，（陰云）1101，（陰陰）1111。一、一些基本的概念一、一些基本的概念一、一些基本的概念一、一些基本的概念3.等長(zhǎng)碼、不等長(zhǎng)碼4.等長(zhǎng)D元碼和

5、不等長(zhǎng)D元碼的最大碼字?jǐn)?shù)目等長(zhǎng)D元碼 DN不等長(zhǎng)D元碼D(DN-1)/(D-1)思考：對(duì)于不等長(zhǎng)編碼，可否完全使用滿樹？5.單義可譯碼與非單義可譯碼（等長(zhǎng)碼） 每個(gè)消息都至少有一個(gè)碼字與之對(duì)應(yīng)，且不同消息對(duì)應(yīng)不同的碼字。6.單義可譯碼存在的充要條件（等長(zhǎng)碼） DNKL NLlogK/logD編碼速率：編碼速率： R=NlogD/L。無(wú)錯(cuò)編碼無(wú)錯(cuò)編碼：編碼速率 R=NlogD/LlogK非單義可譯碼非單義可譯碼：(U1U2UL)的有些不同事件用相同的碼字來(lái)表示。l如何譯碼？l “譯碼錯(cuò)誤”概率 ，定義為pe= P(U1U2UL)=(u1u2uL)| (u1u2uL)的碼字在譯碼時(shí)并不譯為(u1u

6、2uL)。一、一些基本的概念一、一些基本的概念（關(guān)于編碼速率的說(shuō)明：p編碼速率本來(lái)是編碼設(shè)備的性能指標(biāo)。這就是說(shuō)，首先有了編碼設(shè)備的編碼速率R0，然后選擇N和L，使得實(shí)際的編碼速率NlogD/L不能超過(guò)編碼設(shè)備的編碼速率R0 ：R=NlogD/LR0。p當(dāng)編碼速率R比較高時(shí)，可以選擇比較大的N，因此可供選擇的碼字比較多，因此更容易設(shè)計(jì)出能夠快速識(shí)別的碼，降低譯碼的難度。p當(dāng)編碼速率R比較低時(shí)，意味著使用低成本的編碼設(shè)備。此時(shí)只能選擇不大的N，因此更需要編碼的技巧。 ） 一、一些基本的概念一、一些基本的概念單義可譯的解讀：?jiǎn)瘟x可譯的解讀：l當(dāng)R=NlogD/LlogK時(shí)，能夠?qū)崿F(xiàn)無(wú)錯(cuò)編碼。l當(dāng)R

7、=NlogD/LH(U1)時(shí)，無(wú)論怎樣編碼都是有錯(cuò)編碼。這是因?yàn)镽0有P(U1U2UL)=(u1u2uL)| H(U1)-ILH(U1)+LllLVLI11)(111UHEVLEILllL1121111DVLDVLVLDDILllLllL211eLDV一、一些基本的概念一、一些基本的概念取L0使得則當(dāng)LL0時(shí)總有因此當(dāng)LL0時(shí)總有P(U1U2UL)=(u1u2uL)| H(U1)-ILH(U1)+1-。 ee201LDVee21LDV一、一些基本的概念一、一些基本的概念二、信源劃分定理二、信源劃分定理1、典型序列集的概念弱e典型序列集強(qiáng)e典型序列集)()(:),(eeeUHIUHuLTLLU)

8、()(:),(eeekkkLUapLLapLuLT二、信源劃分定理二、信源劃分定理)()()()(2| ),(|2)1 (2)(21),(eeeeeeeeUHLUUHLUHLLUHLULrLTuPLTuP2 2、非典型序列集的概念、非典型序列集的概念 稱典型序列集的補(bǔ)集為非典型序列3 3、信源劃分定理及兩個(gè)推論、信源劃分定理及兩個(gè)推論三、離散無(wú)記憶源編碼三、離散無(wú)記憶源編碼定定理理1、編碼速率：、編碼速率：R=(1/L)logM=(N/L)logD, M為碼字總數(shù)2、可達(dá)速率的定義：、可達(dá)速率的定義：對(duì)于給定信源和編碼速率R以及任意e0e0，若有L0,以及編譯碼方法，使得LL0,錯(cuò)誤概率小于小

9、于e e，R是可達(dá)的（或可采納的），否則就稱R是不可達(dá)的三、離散無(wú)記憶源編碼三、離散無(wú)記憶源編碼定定理理3、離散無(wú)記憶源編碼定理離散無(wú)記憶源編碼定理RH(U),R是可達(dá)的，是可達(dá)的，R1log)(DUHn因此三、幾個(gè)定理三、幾個(gè)定理定理3的推廣:現(xiàn)在對(duì)信源隨機(jī)向量UL=(U1U2UL)做唯一可譯的D元不等長(zhǎng)碼。此時(shí)UL的事件的個(gè)數(shù)為KL。則任一唯一可譯的D元不等長(zhǎng)碼總滿足存在唯一可譯的D元不等長(zhǎng)碼滿足DULHDUHUnLLlog)(log)()(1log)(1log)()(DULHDUHUnLL三、幾個(gè)定理三、幾個(gè)定理重新定義平均碼長(zhǎng)：任一唯一可譯的D元不等長(zhǎng)碼總滿足存在唯一可譯的D元不等長(zhǎng)碼

10、滿足DUHnlog)(LDUHn1log)(LUnnL)(三、幾個(gè)定理三、幾個(gè)定理定義編碼速率R和編碼效率分別為 任一唯一可譯的D元不等長(zhǎng)碼總滿足存在唯一可譯的D元不等長(zhǎng)碼滿足DnLDUnRLloglog)()(UHR LDUHRlog)(注注: 不等長(zhǎng)編碼與等長(zhǎng)編碼具有相似的性質(zhì)：當(dāng)不等長(zhǎng)編碼與等長(zhǎng)編碼具有相似的性質(zhì)：當(dāng)L增大時(shí)，對(duì)增大時(shí)，對(duì)UL的編碼可以的編碼可以使用更短的平均碼長(zhǎng)，因而更加節(jié)省使用更短的平均碼長(zhǎng)，因而更加節(jié)省編碼速率。但編碼速率。但節(jié)省節(jié)省編碼速率的下限編碼速率的下限是是H(U)。RUH)(h三、幾個(gè)定理三、幾個(gè)定理例例3.3.1做2元編碼。設(shè) ；H(U)=0.811。4

11、14321aaUU概率碼字平均碼長(zhǎng)編碼速率編碼效率a13/40(13/4+ 11/4)/1=110.811a21/41U2概率碼字平均碼長(zhǎng)編碼速率編碼效率a1a19/160(19/16+ 23/16+ 33/16+ 31/16)/2=27/3227/320.961a1a23/1610a2a13/16110a2a21/161113.4最佳不等長(zhǎng)編碼最佳不等長(zhǎng)編碼3.4最佳不等長(zhǎng)編碼最佳不等長(zhǎng)編碼1、對(duì)信源的一般性描述：、對(duì)信源的一般性描述：信源消息集 A=a1,a2, aK 對(duì)應(yīng)概率 p1 p2 pK二元碼字集 C=c1, c2, cK碼字長(zhǎng)度 n1 , n2,nK2、定理定理3.4.1 對(duì)于給

12、定信源，存在最佳唯一二元可譯碼，最小概率的兩個(gè)碼字碼長(zhǎng)相等且最長(zhǎng)，他們之間僅最后一位不同3.4最佳不等長(zhǎng)編碼最佳不等長(zhǎng)編碼3、Huffman編碼編碼1）整理信源（將消息集按照概率從大到小排列）2）構(gòu)成新的輔助集（將最小的兩個(gè)概率合并）3）將輔助集作為信源執(zhí)行步驟1和步驟24）重復(fù)上述過(guò)程，知道新的輔助集中只有一個(gè)元素為止。5）從最后一個(gè)元素開始，依次到推到原始信源中的每個(gè)消息，同時(shí)記錄下途徑的分支編碼6）結(jié)束Huffman編碼編碼例(0.19, 0.10, 0.01, 0.20,0.15, 0.18, 0.17)0.200.190.180.170.150.100.010.110.260.350

13、.351.00 01 10.200.190.180.170.15A AA A1 10 01 10.200.190.180.170.260.200.190.180.170 01 10.260.200.19A A2 2A A2 2A A3 30 01 10.260 01 1A A4 4A A5 50.39 0.390.610 01 1A A6 6000001010011001111011Shannon-Fano編碼編碼0 00 00 00 00 01 11 11 11 11 1a a1 1, 00, 00a a2 2, 010, 010a a3 3, 011, 011a a4 4, 10, 10a

14、 a5 5, 110, 110a a6 6, 1110, 1110a a7 7, 1111, 11110 01 13.4最佳不等長(zhǎng)編碼最佳不等長(zhǎng)編碼4、定理、定理3.4.2對(duì)輔助集U為最佳的碼，對(duì)原始集U也是最佳的若若C1，C2，CK-1是對(duì)輔助集是對(duì)輔助集U 的最佳碼，的最佳碼，相應(yīng)碼長(zhǎng)為相應(yīng)碼長(zhǎng)為n1，n2，nK-1，則對(duì)則對(duì)U的碼字的碼字C1，C2, CK的碼長(zhǎng)為的碼長(zhǎng)為lnk= nk kK2lnk= nK-1+1 k=K, K1Kkkknpn12111) 1)(KkKKKkknppnp111)(KkKKkkppnp)(1KKppn3.43.4最佳不等長(zhǎng)編碼最佳不等長(zhǎng)編碼3.4最佳不等長(zhǎng)

15、編碼最佳不等長(zhǎng)編碼5、結(jié)論、結(jié)論二元Huffman碼是最佳編碼，同理可以推廣到D元碼。6、幾個(gè)問(wèn)題、幾個(gè)問(wèn)題lHuffman碼是否唯一lHuffman碼的缺點(diǎn)lcabcedeacacdeddaaabaababaaabbacdebaceadacabcedeacacdeddaaabaababaaabbacdebaceada 共共4040個(gè)字母?jìng)€(gè)字母l頻度頻度la - 16a - 16，b - 7b - 7，c - 6c - 6，d - 6d - 6，e - 5 e - 5 1) 1) 將給定符號(hào)按照其頻率從大到小排序。將給定符號(hào)按照其頻率從大到小排序。la - 16 b - 7 c - 6 d -

16、 6 e a - 16 b - 7 c - 6 d - 6 e 5 52) 2) 將序列分成左右兩部分，使得左部頻率總和盡可能接將序列分成左右兩部分，使得左部頻率總和盡可能接近右部頻率總和。有：近右部頻率總和。有：l(a, b), (c, d, e)(a, b), (c, d, e)l3) 3) 我們把第二步中劃分出的上部作為二叉樹的左子樹，記我們把第二步中劃分出的上部作為二叉樹的左子樹，記 0 0，下，下部作為二叉樹的右子樹，記部作為二叉樹的右子樹，記 1 1。l4) 4) 分別對(duì)左右子樹重復(fù)分別對(duì)左右子樹重復(fù) 2 3 2 3 兩步，直到所有的符號(hào)都成為二叉樹兩步，直到所有的符號(hào)都成為二叉樹

17、的樹葉為止。的樹葉為止。bacde00101011a 00b 01c 10d 110e 111l編碼結(jié)果編碼結(jié)果lCabcedeacacdeddaaabaababaaabbacdebaceadal10 00 01 10 111 110 111 00 10 00 10 .l長(zhǎng)長(zhǎng)91bitl采用采用3bit等長(zhǎng)編碼需等長(zhǎng)編碼需120bitl采用采用ASCII碼需要碼需要320bit采用Huffman編碼a 16b 7c 6d 6e 511132401010101a 0b 100c 101d 110e 111總比特?cái)?shù)總比特?cái)?shù)88，信源熵為，信源熵為86.601bitlShannon-FanoShan

18、non-Fano編碼構(gòu)造二叉樹是自樹根到樹編碼構(gòu)造二叉樹是自樹根到樹葉，很難保證最佳性。葉，很難保證最佳性。lHuffmanHuffman編碼則是從樹葉到樹根，是最佳的編碼則是從樹葉到樹根，是最佳的lHuffmanHuffman需要知道信源的概率分布，這在實(shí)際需要知道信源的概率分布，這在實(shí)際中有時(shí)是比較困難的。中有時(shí)是比較困難的。l采用半靜態(tài)模型、自適應(yīng)模型、采用半靜態(tài)模型、自適應(yīng)模型、markovmarkov模型，模型，部分匹配預(yù)測(cè)模型等等解決這一問(wèn)題。部分匹配預(yù)測(cè)模型等等解決這一問(wèn)題。3.4最佳不等長(zhǎng)編碼最佳不等長(zhǎng)編碼7、對(duì)、對(duì)Huffman碼的進(jìn)一步評(píng)價(jià)碼的進(jìn)一步評(píng)價(jià)S=（s1, s2

19、,s3 ,s3 ,s5）P=（0.4，0.2，0.2，0.1，0.1）0.40.20.20.10.1碼長(zhǎng)碼字0.40.20.20.0.40.0.20.0.3.4最佳不等長(zhǎng)編碼最佳不等長(zhǎng)編碼0.40.20.20.10.1碼長(zhǎng)碼字0.40.20.20.0.40.0.20.0.結(jié)論：平均碼長(zhǎng)相同時(shí)看方差，方差越小越好結(jié)論：平均碼長(zhǎng)相同時(shí)看方差，方差越小越好3.4最佳不等長(zhǎng)編碼最佳不等長(zhǎng)編碼、 D元元Huffman碼碼例子：三元例子：三元HuffmanU=（ a1, a2, a3, a4, a5, a6）P=（p1, p2, p3, p4, p5, p6）結(jié)論：結(jié)論：q = （D-1）m + D3.5

20、算術(shù)編碼與算術(shù)編碼與LZ編碼編碼一、一、Huffman碼的本質(zhì)與缺點(diǎn)碼的本質(zhì)與缺點(diǎn)1、Huffman碼的本質(zhì)碼的本質(zhì)Huffman從本質(zhì)上說(shuō)是一種分組碼：即對(duì)待編碼序列分割為長(zhǎng)為L(zhǎng)的段，然后生成長(zhǎng)為N的輸入。消息序列與碼字一一對(duì)應(yīng)保證唯一可譯。一、一、Huffman碼的本質(zhì)與缺點(diǎn)碼的本質(zhì)與缺點(diǎn)、Huffman碼的缺點(diǎn)碼的缺點(diǎn)當(dāng)已知信源分布，要求對(duì)長(zhǎng)信源序列進(jìn)行編碼時(shí)需要知道后者的信源分布，編碼工作量大。二、香農(nóng)編碼二、香農(nóng)編碼、香農(nóng)第一定理、香農(nóng)第一定理碼字長(zhǎng)度的選擇應(yīng)滿足對(duì)任意的1)()(iiixIKxI、編碼方法：、編碼方法：l排列信源概率(x1)(x2) (xn) l確定滿足香農(nóng)第一定理

21、的正數(shù)碼長(zhǎng)Ki二、香農(nóng)編碼二、香農(nóng)編碼l保證唯一可譯性：計(jì)算第i個(gè)消息的累加概率11)(ikkixppl將累加概率換算成二進(jìn)制小數(shù)l取二進(jìn)制小數(shù)點(diǎn)后Ki位為該消息符號(hào)的二進(jìn)制碼字二、香農(nóng)編碼二、香農(nóng)編碼例：x1 , x2 , x3 , x4 , x5 , x6 , x7 0.20, 0.19, 0.18, 0.17, 0.15, 0.10, 0.01 以x4 為例100.100100. 057. 018. 019. 020. 0356. 356. 2117. 0log17. 0log4431444242CxpPkkkii二、香農(nóng)編碼二、香農(nóng)編碼同理可得全部編碼：源事件p(xi)Pi-log2p

22、(xi)碼長(zhǎng)碼字x10.2002.343000 x20.190.202.413001x30.180.392.483011x40.170.572.563100 x50.150.742.743101x60.100.893.3441110 x70.010.996.6671111110三、算術(shù)編碼三、算術(shù)編碼1、與、與Huffman碼的不同碼的不同a) Huffman是分組碼，算術(shù)編碼不是。其是從全序列出發(fā)，需要考慮前后符號(hào)間的依賴關(guān)系來(lái)編碼。b) 算術(shù)編碼無(wú)需計(jì)算全序列的概率分布，其可以直接對(duì)信源符號(hào)序列進(jìn)行編碼，可以達(dá)到漸近最佳的性能。在這個(gè)過(guò)程中需要的僅僅是計(jì)算累加概率。三、算術(shù)編碼三、算術(shù)編碼

23、2、累加概率、累加概率a) 信源符號(hào)的累加概率：設(shè)信源符號(hào)集A=a1 , a2 , ak ，其對(duì)應(yīng)的概率分布為p(ai)0(i=1,2,K) 定義信源符號(hào)的累加概率為：1111110)()(,.)()(iikikiikapaFAaaapaF三、算術(shù)編碼三、算術(shù)編碼b) 即時(shí)碼即時(shí)碼：累加概率函數(shù)將0到1的區(qū)間非成了不重疊的K個(gè)小區(qū)間，每個(gè)信源符號(hào)對(duì)應(yīng)其中一個(gè)區(qū)間。取區(qū)間中一點(diǎn)小數(shù)后L位作為信源的碼字可保證即時(shí)性。c) 信源序列的累加函數(shù)信源序列的累加函數(shù)：lU=u1 ,u2 , uL ul取值為0或1lF(0) = 0 , F(1) = p(0)F(0)F(1) p(0) p(1)1F(0)F

24、(1) p(0) p(1)1F(0)F(01) p(00) p(01)p(0)F(1)F(01)F(011) p(010) p(011)p(01)F(1)F(011)F(0111) p(0110) p(0111)p(011)F(1)三、算術(shù)編碼三、算術(shù)編碼l設(shè)當(dāng)前序列為S，由上圖可以歸納出 F(S0)=F(S) 對(duì)應(yīng)區(qū)間寬度為A(S0)=A(S).p(0) F(S1)=F(S)+ A(S0)= F(S)+ A(S).p(0) 對(duì)應(yīng)區(qū)間寬度為A(S1)=A(S).p(1)=A(S)-A(S0)l結(jié)論： F(Sr)=F(S)+ p(S).F(r) (r=0,1) A(Sr)= p(Sr)=p(S)

25、.p(r) (r=0,1)三、算術(shù)編碼三、算術(shù)編碼Eg:當(dāng)S=“011”，接著輸入1，得符號(hào)序列S1的累加概率為F(S1)=F(0111)=F(s=“011”)+p(011).p(0) =F(s=“01”)+ p(01).p(0)+ p(011).p(0) =F(s=“0”)+p(0).p(0)+ p(01).p(0)+ p(011).p(0) =0+p(00)+p(010)+p(0110)對(duì)應(yīng)區(qū)間寬度為A(S1) = A(s=“011”).p(1)=p(011).p(1)=p(0111)F(S1)= 0+p(00)+p(010)+p(0110)0 00 00 00 01 11 11 11 1

26、1 1三、算術(shù)編碼三、算術(shù)編碼3、編碼方法、編碼方法a)碼長(zhǎng)的選取：設(shè)等待編碼序列為u，則其碼長(zhǎng)為)(1logupN)編碼步驟：針對(duì)u計(jì)算出對(duì)應(yīng)的累積概率將該累積概率轉(zhuǎn)換為二進(jìn)制小數(shù)從小數(shù)后截取N位，如果后面還有尾數(shù)則進(jìn)位Eg:F(S)=0.10110001 N=3 C=0.110三、算術(shù)編碼三、算術(shù)編碼4、碼字唯一性討論、碼字唯一性討論a）C中沒(méi)有進(jìn)位b）C中有進(jìn)位5、例子、例子s=11111100，p(0)=1/4, p(1)=3/4, 所以有H(u)=0.81bit/符號(hào)； 6231( )( ) ( )44p s 21log7( )Lp s三、算術(shù)編碼三、算術(shù)編碼A：通過(guò)計(jì)算來(lái)編碼， F

27、(s)=p(00000000)+p(00000001)+p(11111011) =1-p(11111111)-p(11111110)-p(11111101) -p(11111100)=1-p(1111111)-p(1111110) =1-p(111111) =1- =0.110100100111 所以C(s)=0.1101010 63()4()92.7%7/8H Uh三、算術(shù)編碼三、算術(shù)編碼B：用遞推公式編碼 輸入符號(hào)P(s)=A(s)A(s)*P(0)F(s)L(s)C(s)10.0100空10.110.00110.0110.110.10010.0010010.011110.110.0110110.10010120.1110.010100010.1010011120.1110.00111100110.110000110130.11110.0010110110010.11010010011130.11100.000010110110010.110