信源編碼(1)_離散信源編碼11.11

1、第5章 信源編碼編碼的意義編碼的意義編碼定義編碼定義最佳編碼方法信源編碼的目的：信源編碼的目的： 1、便于信道的傳輸、便于信道的傳輸 例如：語(yǔ)音信號(hào)的數(shù)字傳輸例如：語(yǔ)音信號(hào)的數(shù)字傳輸 2、提高有效性、提高有效性 例：設(shè)某計(jì)算機(jī)終端用來(lái)控制檢查流水線上產(chǎn)品的質(zhì)量，按優(yōu)、中、劣三級(jí)來(lái)分類記錄。從統(tǒng)計(jì)中已知產(chǎn)品在三級(jí)中的比例為優(yōu)、劣各占1/4，中占1/2。以下研究如何將檢查結(jié)果編成二進(jìn)制碼，以通過(guò)網(wǎng)絡(luò)傳送到主機(jī)中進(jìn)行存儲(chǔ)和處理。第一種編碼方法： 產(chǎn) 品 等級(jí)出現(xiàn)概率編碼優(yōu)1/411中1/210劣1/400平均編碼長(zhǎng)度：L1=1/4*2+1/2*2+1/4*2 =2bit/符號(hào)產(chǎn) 品 等級(jí)出現(xiàn)概率編碼

2、優(yōu)1/41中1/210劣1/400第二種編碼方法平均編碼長(zhǎng)度：L2=1/4*1+1/2*2+1/4*2 =1.75bit/符號(hào)產(chǎn) 品 等級(jí)出現(xiàn)概率編碼優(yōu)1/411中1/21劣1/400第三種編碼方法平均編碼長(zhǎng)度：L3=1/4*2+1/2*1+1/4*2 =1.5bit/符號(hào)結(jié)論： 1、不同的編碼方法，平均的編碼長(zhǎng)度不一樣 2、L1L2L3結(jié)論：概率越大，用的碼越短，則平均編碼長(zhǎng)度則越小。二、編碼定義1、等長(zhǎng)碼和變長(zhǎng)碼 如果一種碼的各個(gè)碼字都是由同樣多個(gè)碼元構(gòu)成的，則成為等長(zhǎng)碼。例如：00，01，103、碼樹(shù) 碼樹(shù)是表示元素之間的結(jié)構(gòu)層次的方法。5、平均編碼長(zhǎng)度 設(shè)N個(gè)碼字中的第I個(gè)碼字的長(zhǎng)度為

3、ni,他所代表的編碼對(duì)象xi的概率為p(xi),則碼字的平均編碼長(zhǎng)度為： L=p(xi) ni6、編碼效率 最小的平均編碼長(zhǎng)度和實(shí)際的編碼長(zhǎng)度的比值。 Lmin=H(X)/logD =Lmin/L 編碼的剩余度r=1- 產(chǎn) 品 等級(jí)出現(xiàn)概率編碼優(yōu)1/411中1/21劣1/400例:平均編碼長(zhǎng)度：L3=1/4*2+1/2*1+1/4*2 =1.5bit/符號(hào)Lmin=1.5 =1三、最佳編碼方法 滿足兩個(gè)條件：1、唯一可譯性 2、碼長(zhǎng)是最小的l 目的：提高通信的有效性。目的：提高通信的有效性。l 途徑：通過(guò)壓縮信源的冗余度來(lái)實(shí)現(xiàn)。途徑：通過(guò)壓縮信源的冗余度來(lái)實(shí)現(xiàn)。l 方法：壓縮每個(gè)信源符號(hào)的平均

4、比特?cái)?shù)或信方法：壓縮每個(gè)信源符號(hào)的平均比特?cái)?shù)或信源的碼率。同樣多的信息用較少的碼率來(lái)傳源的碼率。同樣多的信息用較少的碼率來(lái)傳送，使單位時(shí)間內(nèi)傳送的平均信息量增加，送，使單位時(shí)間內(nèi)傳送的平均信息量增加，從而提高通信的有效性。從而提高通信的有效性。使序列中的各個(gè)符號(hào)盡可能地互相獨(dú)立，即解使序列中的各個(gè)符號(hào)盡可能地互相獨(dú)立，即解除相關(guān)性；除相關(guān)性；使編碼中各個(gè)符號(hào)出現(xiàn)的概率盡可能地相等，使編碼中各個(gè)符號(hào)出現(xiàn)的概率盡可能地相等，即概率均勻化。即概率均勻化。理論基礎(chǔ)：是信息論中的兩個(gè)編碼定理：理論基礎(chǔ)：是信息論中的兩個(gè)編碼定理：n 無(wú)失真編碼定理。只適用于離散信源。只適用于離散信源。n 限失真編碼定理。

5、對(duì)于連續(xù)信源，只能在對(duì)于連續(xù)信源，只能在失真受限制的情況下進(jìn)行失真受限制的情況下進(jìn)行限失真編碼。1110110100 0111011010 110010 10100 125. 0125. 025. 05 . 04321DCBAaaaa碼碼碼碼碼碼碼碼概概率率消消息息判斷以下碼字是否可分離？異前置碼即時(shí)碼可分離有延時(shí)可分離分離不可分離不可例例5.1.112121.()().()( )1nnniiaaap ap ap ap a設(shè)有離散無(wú)記憶信源設(shè)有離散無(wú)記憶信源12香農(nóng)編碼方法的步驟香農(nóng)編碼方法的步驟按信源符號(hào)的的順序排隊(duì))(.)()(21napapap不妨設(shè)不妨設(shè)個(gè)個(gè)碼碼字字的的累累加加概概率率

6、表表示示第第，用用令令iijapapja1),(0)(011( )( ) 1jajiip ap a22log( )1 log( )iiiikp akp a 確定 ，使其滿足()ajiipaka把用二進(jìn)制表示，用小數(shù)點(diǎn)后的 位作為 的碼字3405. 01 . 015. 02 . 025. 025. 0)(654321aaaaaaXPX設(shè)有一單符號(hào)離散無(wú)記憶信源設(shè)有一單符號(hào)離散無(wú)記憶信源試對(duì)該信源編二進(jìn)制香農(nóng)碼。試對(duì)該信源編二進(jìn)制香農(nóng)碼。11110595. 005. 01101485. 01 . 010137 . 015. 010035 . 02 . 001225. 025. 0002025. 0

7、)(654321aaaaaakapija碼字碼字10)()(jiijaapap617 .2)(iiikapKKmLKR2log()2.42325H X (X)89.75%HR對(duì)概率按m進(jìn)行分組，使每組盡可能相等；給每個(gè)分組分配一個(gè)碼元；對(duì)每個(gè)分組重復(fù)2、3步，直到不可分為止。1234按信源符號(hào)的概率的順序排隊(duì))(.)()(21napapap不妨設(shè)不妨設(shè)04. 008. 016. 018. 022. 032. 0)(654321aaaaaaXPX設(shè)有一單符號(hào)離散無(wú)記憶信源設(shè)有一單符號(hào)離散無(wú)記憶信源試對(duì)該信源編二進(jìn)制費(fèi)諾碼。試對(duì)該信源編二進(jìn)制費(fèi)諾碼。1a2a3a4a5a6a32. 022. 018

8、. 016. 008. 004. 0001010011000110110111011111編碼過(guò)程編碼過(guò)程)/(35. 2)(synbitXHmLKR2log%92.97)(RXH61)/(4 .2)(iiikapK符符號(hào)號(hào)比比特特可以看出本例中費(fèi)諾碼有較高的編碼效率。費(fèi)可以看出本例中費(fèi)諾碼有較高的編碼效率。費(fèi)諾碼比較適合于每次分組概率都很接近的信源。諾碼比較適合于每次分組概率都很接近的信源。00000111111a2a3a4a5a6a將信源符號(hào)順序排隊(duì)。給位，將其概率相加后合并作為一個(gè)新的符號(hào)，與剩下的符號(hào)一起，。給中概率最小的二個(gè)符號(hào)各分配一個(gè)碼位。重復(fù)步驟2、3直至概率和為1。21430

9、4. 005. 006. 007. 01 . 01 . 018. 04 . 0)(87654321aaaaaaaaXPX設(shè)有一單符號(hào)離散無(wú)記憶信源設(shè)有一單符號(hào)離散無(wú)記憶信源試對(duì)該信源編二進(jìn)制赫夫曼碼。試對(duì)該信源編二進(jìn)制赫夫曼碼。09. 013. 019. 023. 037. 06 . 00000000111111104. 005. 006. 007. 01 . 01 . 018. 04 . 01a2a3a4a5a6a7x8a1001011000001000101000100001100010001007a編碼過(guò)程編碼過(guò)程()2.55(/)H Xbit sym2.61K( )97.7%H xR。

10、率提高了可見(jiàn)，哈夫曼編碼的效則編碼效率若采用定長(zhǎng)編碼，碼長(zhǎng)7 .1285355. 2, 3KHuffman碼的編碼方法不是唯一的。碼的編碼方法不是唯一的。 首先，每次對(duì)縮減信源兩個(gè)最小的符號(hào)分配首先，每次對(duì)縮減信源兩個(gè)最小的符號(hào)分配“0”和和“1”碼元試任意的，所以可得到不同的碼字。只要碼元試任意的，所以可得到不同的碼字。只要在各次縮減信源中保持碼元分配的一致性，即能得在各次縮減信源中保持碼元分配的一致性，即能得到可分離碼字。不同的碼元分配，得到的具體碼字到可分離碼字。不同的碼元分配，得到的具體碼字不同，但碼長(zhǎng)，平均碼長(zhǎng)都不變，所以沒(méi)有本質(zhì)區(qū)不同，但碼長(zhǎng)，平均碼長(zhǎng)都不變，所以沒(méi)有本質(zhì)區(qū)別。別。

11、 其次，若合并后的新符號(hào)的概率與其他符號(hào)的概率其次，若合并后的新符號(hào)的概率與其他符號(hào)的概率相等，從編碼的方法上來(lái)說(shuō)，這幾個(gè)符號(hào)的次序可相等，從編碼的方法上來(lái)說(shuō)，這幾個(gè)符號(hào)的次序可任意排列，編出的碼都是正確的，但得到的碼字不任意排列，編出的碼都是正確的，但得到的碼字不同。不同的編法得到的碼字長(zhǎng)度也不盡相同。同。不同的編法得到的碼字長(zhǎng)度也不盡相同。設(shè)有離散無(wú)記憶信源設(shè)有離散無(wú)記憶信源1 . 01 . 02 . 02 . 04 . 0)(54321xxxxxXPX用兩種不同的方法對(duì)其編二進(jìn)制用兩種不同的方法對(duì)其編二進(jìn)制huffmanhuffman碼碼方法一方法一方法二方法二信源符號(hào)信源符號(hào)ai概率概

12、率p(ai)碼字碼字Wi1碼長(zhǎng)碼長(zhǎng)Ki1碼字碼字Wi2碼長(zhǎng)碼長(zhǎng)Ki2a10.41 1002a20.2012102a30.20003112a40.1001040103a50.1001140113兩種不同的編碼方法得到的碼字和碼長(zhǎng)的對(duì)比兩種不同的編碼方法得到的碼字和碼長(zhǎng)的對(duì)比平均碼長(zhǎng)和編碼效率平均碼長(zhǎng)和編碼效率兩種編碼方法編出的碼字的碼長(zhǎng)方差比較兩種編碼方法編出的碼字的碼長(zhǎng)方差比較進(jìn)行赫夫曼編碼時(shí)，為得到進(jìn)行赫夫曼編碼時(shí)，為得到碼方差碼方差最小的最小的碼，應(yīng)使合并的信源符號(hào)位于縮減信源序碼，應(yīng)使合并的信源符號(hào)位于縮減信源序列列盡可能高的位置盡可能高的位置上，以減少再次合并的上，以減少再次合并的次數(shù)

13、，充分利用短碼。次數(shù)，充分利用短碼。 游程序列游程 前面的幾種編碼方法主要時(shí)針對(duì)無(wú)記憶信源，對(duì)有前面的幾種編碼方法主要時(shí)針對(duì)無(wú)記憶信源，對(duì)有記憶信源，這些編碼方法的效率并不高，特別是對(duì)二記憶信源，這些編碼方法的效率并不高，特別是對(duì)二元相關(guān)信源，需要一些其它的方法。游程編碼就是這元相關(guān)信源，需要一些其它的方法。游程編碼就是這樣的方法，對(duì)相關(guān)信源的編碼更有效。樣的方法，對(duì)相關(guān)信源的編碼更有效。 指數(shù)字序列中連續(xù)出現(xiàn)相同符號(hào)的一段。在指數(shù)字序列中連續(xù)出現(xiàn)相同符號(hào)的一段。在二元信源中，連續(xù)的一段二元信源中，連續(xù)的一段00稱為一個(gè)稱為一個(gè)00游程，游程，00的個(gè)數(shù)稱為此游程的長(zhǎng)度，同樣，也有的個(gè)數(shù)稱為此

14、游程的長(zhǎng)度，同樣，也有11游程。游程。 用交替出現(xiàn)的用交替出現(xiàn)的00游程、游程、11游程的游程的長(zhǎng)度，來(lái)表示任意二元序列而產(chǎn)生的一個(gè)新序列。它長(zhǎng)度，來(lái)表示任意二元序列而產(chǎn)生的一個(gè)新序列。它和二元序列是一個(gè)一一對(duì)應(yīng)的變換。和二元序列是一個(gè)一一對(duì)應(yīng)的變換。二元序列：二元序列：000101110010001游程序列：游程序列：31132131二元序列二元序列赫夫赫夫曼編碼曼編碼 0：長(zhǎng)度為1的“0”游程0000：長(zhǎng)度為4的“0”游程 111：長(zhǎng)度為3的“1”游程 長(zhǎng)度為n的“1”游程11:1n多元序列也存在相應(yīng)的游程序列多元序列也存在相應(yīng)的游程序列 多元序列變換成游程序列再進(jìn)行壓縮編多元序列變換成游

15、程序列再進(jìn)行壓縮編碼沒(méi)有多大意義碼沒(méi)有多大意義 游游程編碼只適用于二元序列，對(duì)于多游游程編碼只適用于二元序列，對(duì)于多元信源，一般不能直接利用游程編碼元信源，一般不能直接利用游程編碼 因?yàn)橛纬套儞Q是一一對(duì)應(yīng)的可逆變換，所以游程變換后，熵不變。組合編碼可獲得較高的編碼效率：游程編碼赫夫曼編碼“0”、“1”的概率分別為的概率分別為p0、p1長(zhǎng)度長(zhǎng)度i的的“0”游程概率：游程概率： 01001 iilp lpp長(zhǎng)度長(zhǎng)度j的的“1”游程概率：游程概率： 11110 jljp lpp00110 11iilpp lp11011 11jjlpp lp0p00010111001000131132131因?yàn)橛纬套?/p>

16、換是一一對(duì)應(yīng)的可逆變換，所以游程變換后，熵不變。游程編碼赫夫曼編碼組合編碼可獲得較高的編碼效率：010.6,0.4pp例例“0”游程長(zhǎng)度信游程長(zhǎng)度信源源二元序列：00010111001000011110011000101110001234()0.40.240.1440.0864LP L010203040.40.240.1440.0864llll000111100010011“1”游程長(zhǎng)度信游程長(zhǎng)度信源源111234()0.60.240.0960.0384LP L111213140.40.240.0960.0384llll010101101110011000101110010000111100110001011100,100,11000,0101111100001000100110,1111111010011100000111110010010011101信號(hào)序列碼序列冗余位冗余位信源序列中不攜帶信息的符號(hào)。多元信源序列：1211 12, , , ,mmmyyyx xxxx111000,000111,100,111,211121mmmxxxxx上面二元上面二元1表示信息位，表示信息位，0表示冗余位表示冗余位 冗余位序列游程編碼信息序