學(xué)習(xí)信源無(wú)失真編碼

1、信源編碼復(fù)習(xí)信源編碼復(fù)習(xí) XYW W U U U WW U 12 , , q u uu 12 , , r x xx WU 12 , , q w ww X :,1,2, ii fuwiq 11 ()() qq iiii ii lP w lP u l 1 () q i i lP u ll 1234 1 21 41 81 8 U Uuuuu P 2111 2222 2 2333 2444 ()0 ,1 ()10 ,2 : ()110 ,3 ()111,3 fuwl fuwl f fuwl fuwl 4 1 1111 ()2222 2488 2 ii i lP u l 4 1 1111 ()1233

2、2488 1.75 ii i lP u l 1111 1222 1 1333 1444 ()00 ,2 ()01 ,2 : ()10 ,2 ()11 ,2 f uwl f uwl f f uwl f uwl 。 。 12 , , q u uu 01， WU 12 , , q w ww X ii P wP u iq ()() 1,2, , H WH U ()() H WH U H X ll ()() () H WH U H X ll ()() ()R X , , 12r x xx12 , , q u uu 12 , , r x xx WU 12 , , q w ww X maxmax ()()(

3、) ()loglog c RH XH UlH U RHXrlr 1 cc X , , 12r x xx12 , , q u uu 12 , , r x xx WU 12 , , q w ww X f 1 f U WW U 5種不同的碼種不同的碼 i P uWWWWWU u u u u 35124 1 2 3 4 () 1 20000100 1 40100001001 1 8101001110011 1 8111110111111 W1：定長(zhǎng)碼。：定長(zhǎng)碼。 W3：變長(zhǎng)碼。：變長(zhǎng)碼。 奇異碼。奇異碼。 定長(zhǎng)非奇異碼肯定是定長(zhǎng)非奇異碼肯定是UDC。 u u u u u u u u u u u u u

4、 1243 4321 12121 1,00,10,01 100100110,01,00,1 1,00,1,00,1 W2：定長(zhǎng)碼。：定長(zhǎng)碼。 W4：變長(zhǎng)碼。：變長(zhǎng)碼。 W5：變長(zhǎng)碼。：變長(zhǎng)碼。 非奇異碼。非奇異碼。 非奇異碼。非奇異碼。 非奇異碼。非奇異碼。 非奇異碼。非奇異碼。 續(xù)長(zhǎng)碼。續(xù)長(zhǎng)碼。 非續(xù)長(zhǎng)碼。非續(xù)長(zhǎng)碼。 續(xù)長(zhǎng)碼。續(xù)長(zhǎng)碼。 及時(shí)碼。及時(shí)碼。 非及時(shí)碼。非及時(shí)碼。 奇異碼肯定不是奇異碼肯定不是UDC。 不是不是UDC。 非續(xù)長(zhǎng)碼肯定是非續(xù)長(zhǎng)碼肯定是UDC。 是是UDC。 非及時(shí)碼。非及時(shí)碼。 非續(xù)長(zhǎng)碼。非續(xù)長(zhǎng)碼。 碼碼 奇異碼奇異碼 非奇異碼非奇異碼 非唯一可譯碼非唯一可譯碼 唯一

5、可譯碼唯一可譯碼 定長(zhǎng)非奇異碼定長(zhǎng)非奇異碼 變長(zhǎng)非續(xù)長(zhǎng)碼變長(zhǎng)非續(xù)長(zhǎng)碼 （部分）變長(zhǎng)續(xù)長(zhǎng)碼（部分）變長(zhǎng)續(xù)長(zhǎng)碼 0 01 1 4 w3 w 2 w 1 w 0 1 0 0 0 1 1 1 4 w 3 w 2 w 1 w 0 1 1 1 4 111w 1 0w 1 1 3 011w 2 01w r 12 , q l ll 1 1 i q l i r r 4 1233 1 222221 i l i r 12 , q l ll 1 1 i q l i r r 12 , , q u uu 12 , , r x xx W U 12 , , q w ww X X 12 , , r x xx 12 , , N

6、q 12 , , r x xx W N U 12 , , N q w ww X X 12 , , r x xx 12iiiiN u uu 1212 , iiiNq uuuu uu N l r N lN rq max max ()log () loglog N r HUlq HU Nrr () () / N H U RH X lN max ()() () log c N H XH U l HX r N 12 , , N q 12 , , r x xx W N U 12 , , N q w ww X X 12 , , r x xx 。 () () log N r lH U H U Nr ()2 (

7、)2 log N r lH U H U Nr 1234567 234566 1111111 2222222 U uuuuuuu U P 1234567 : :001010011100101110111 Uuuuuuuu W 7 1 63 ()()log() 32 ii i H UP uP u 63 32 () 65.625% log3log2 c H U lr 3ll loglog7 2.8 loglog2 N lq l Nr () N r l H U N 1 () N r l H U NN rUN N N l N l N l limlim() N r NN l lH U N ()() lim

8、limlim100% log r c NNN H UH U lrl 例：對(duì)二元例：對(duì)二元DMS進(jìn)行無(wú)失真編碼：進(jìn)行無(wú)失真編碼： N=1 4 1 4 3 21 uu P U 符號(hào)/811. 0 3 4 log 4 3 4log 4 1 ) 4 3 , 4 1 ()(bitHUH 若用二元碼符號(hào)若用二元碼符號(hào)(0，1)進(jìn)行定長(zhǎng)編碼：進(jìn)行定長(zhǎng)編碼： 。 平均碼長(zhǎng)平均碼長(zhǎng) 1 碼元碼元/信源符號(hào)信源符號(hào) 1,0 21 uu l 碼元/811. 0 )( )(bit l UH XHR 編碼效率為編碼效率為 輸出的信息效率輸出的信息效率 811. 0 log )( )( )( max 1 rl UH XH

9、 XH 要求：對(duì)比定長(zhǎng)編碼與變長(zhǎng)編碼的編碼效率（要求：對(duì)比定長(zhǎng)編碼與變長(zhǎng)編碼的編碼效率（N=2,3,4）。）。 練習(xí)題 對(duì)對(duì)U的二次擴(kuò)展信源進(jìn)行定長(zhǎng)編碼，碼表如下表的二次擴(kuò)展信源進(jìn)行定長(zhǎng)編碼，碼表如下表 ： uip(ui)碼字 u1u19/1600 u1u23/1601 u2u13/1610 u2u21/1611 信源序列碼元/2 N l 編碼效率為編碼效率為 碼字平均長(zhǎng)度碼字平均長(zhǎng)度 811. 0 log )( )( )( max 2 rl UH XH XH 單個(gè)符號(hào)的平均碼長(zhǎng)單個(gè)符號(hào)的平均碼長(zhǎng) 信源符號(hào)碼元/1 2 2 N l l N N=2 N=3,4時(shí)，811. 0 43 對(duì)對(duì)U的二次

10、擴(kuò)展信源進(jìn)行變長(zhǎng)編碼，碼表如下表的二次擴(kuò)展信源進(jìn)行變長(zhǎng)編碼，碼表如下表 ： uip(ui)碼字 u1u19/160 u1u23/1610 u2u13/16110 u2u21/16111 N=2 信源序列碼元/688. 13 16 1 3 16 3 2 16 3 1 16 9 N l 編碼效率為編碼效率為 碼字平均長(zhǎng)度碼字平均長(zhǎng)度 961. 0 844. 0 811. 0 log )( )( )( max 2 rl UH XH XH 單個(gè)符號(hào)的平均碼長(zhǎng)單個(gè)符號(hào)的平均碼長(zhǎng) 信源符號(hào)碼元/844. 0 2 688. 1 N l l N N=3,4時(shí)，991. 0,985. 0 43 分析：分析： 1

11、、比較定長(zhǎng)編碼與變長(zhǎng)編碼的編碼效率可知，尤其在、比較定長(zhǎng)編碼與變長(zhǎng)編碼的編碼效率可知，尤其在N 較大時(shí)變長(zhǎng)編碼的效率遠(yuǎn)大于定長(zhǎng)編碼。較大時(shí)變長(zhǎng)編碼的效率遠(yuǎn)大于定長(zhǎng)編碼。 N定長(zhǎng)變長(zhǎng) 20.8110.961 30.8110.985 40.8110.991 2、若對(duì)定長(zhǎng)編碼與變長(zhǎng)編碼同樣要求編碼效率達(dá)到、若對(duì)定長(zhǎng)編碼與變長(zhǎng)編碼同樣要求編碼效率達(dá)到96%， 允許的譯碼錯(cuò)誤概率允許的譯碼錯(cuò)誤概率 時(shí)，定長(zhǎng)編碼所需序列長(zhǎng)度時(shí)，定長(zhǎng)編碼所需序列長(zhǎng)度N： 5 10 所需的信源序列長(zhǎng)度：所需的信源序列長(zhǎng)度： q i ii UHuPuPU 1 222 4715. 0)()()log()( 7 522 2 22

12、22 1013. 4 10)96. 01 ()811. 0( )96. 0(4715. 0 )1 ()( )( c c UH U N 同樣的編碼效率，變長(zhǎng)編碼信源序列長(zhǎng)度同樣的編碼效率，變長(zhǎng)編碼信源序列長(zhǎng)度N=2時(shí)即可滿(mǎn)足時(shí)即可滿(mǎn)足 編碼效率達(dá)到編碼效率達(dá)到96%的要求。隨著的要求。隨著N的增加，編碼效率趨近的增加，編碼效率趨近 于于1。 11 012 0013 00014 000015 0000016 0000006 i u 1 2u1 u2 u3 u4 u5 u6 u7 () i P u 4 1 2 5 1 2 6 1 2 6 1 2 2 1 2 3 1 2 4 12 12 2 12 3

13、12 5 12 0 0 0 0 0 0 1 1 1 1 1 1 . 100 1234567 234566 1111111 2222222 U uuuuuuu U P l 234566 111111163 1234566 222222232 c H U lr 63 32 63 32 () 100% loglog2 碼元碼元/符號(hào)符號(hào) ()63 32H U 3ll max ()0.65625 65.625% ()log2 c H X HX 63 32l max ()1 100% ()log2 c H X HX ()63 32 ()0.65625 3 H U H X l ()63 32 ()1 63

14、 32 H U H X l max ()63 32 110.3 ()log7 H U HU 10.34375 cc 10 cc 定長(zhǎng)編碼：定長(zhǎng)編碼：001，010，011，100，101，110，111 變長(zhǎng)編碼：變長(zhǎng)編碼：1，01，001，0001，00001，000001，000000 1234567 234566 1111111 2222222 U uuuuuuu U P 碼字不唯一碼字不唯一 上例另一種霍夫曼編碼：上例另一種霍夫曼編碼： 11 012 0013 00014 000015 0000016 0000006 i u u1 u2 u3 u4 u5 u6 u7 () i P u

15、1234567 0.350.3040.0050.005 U Uuuuuuuu P . 005 . 065 . 035 . 015 . 001 . 100 0 0 0 0 0 0 1 1 1 1 1 1 . . l 0 35 10 3020 2030 10 40 04 50 005 60 005 6 2 21 112 102 012 0013 00014 000015 000005 . . l 0 35 20 30 20 20 20 10 30 04 40 005 50 005 5 2 21 . 005 . 065 . 035 . 015 . 001 . 100 0 0 0

16、 0 0 0 1 1 1 1 1 1 1234567 0.350.3040.0050.005 U Uuuuuuuu P i u u1 u2 u3 u4 u5 u6 u7 () i P u 11 012 0013 00014 000015 0000016 0000006 112 102 012 0013 00014 000015 000005 q iii i lE llP ull 222 1 ( )() ()() 碼長(zhǎng)方差：碼長(zhǎng)方差： l 2 1 ( )1.4259 l 2 2 ( )0.3059 碼字不同，碼長(zhǎng)也不同，但碼字不同，碼長(zhǎng)也不同，但 平均碼長(zhǎng)相同，因此編碼效平

17、均碼長(zhǎng)相同，因此編碼效 率相同。率相同。 2 1 1 1 02 2 01 2 002 3 001 3 U Uuuuuuu P 123456 0.360.080.04 qrr(1)23 (0.12) (0.46) (1.00) 0 1 2 1 2 0 1 0 2 0.32 10.22 10.1820.1620.0830.0431.58l c H U lr ()2.35 93.8% log1.58 log3 i u u1 u2 u3 u4 u5 u6 7 u () i P u 123 0.450.350.20 U Uuuu P ()1.518H U 1 0 0 1 (1.0

18、0) (0.55) 3 1 ()0.45 10.3520.2021.55 ii i lP u l ()1.518 97.9% log1.55 log2 c H U lr . 016 . 028 . 011 0 0 0 0 1 1 1 1 . 020 1 . 100 0 0 . 04025 . 05975 0 0 1 1 . 03175 1 9 2 1 ()3.0675 jj j lP u l 2 2 ()2 1.518 99.0% log3.0675 log2 c H U lr 00 2 010 3 011 3 10 2 110 3 1110 4 1111 4 1234567 0.200.19

19、50.100.01 U Uuuuuuuu P 0 0 1 0 0 0 0 1 1 1 1 1 7 1 ()0.20 20.19 30.18 30.1720.15 30.10 40.01 42.74 ii i lP u l ()2.61 95% log2.74 log2 c H U lr 7 1 ()()log()2.61 ii i H UP uP u log()log()1 iii P ulP u 1 1 1 0 ()2,3, i ik k P PP uiq 消息符號(hào)消息符號(hào)ui消息概率消息概率pi-logpi碼長(zhǎng)碼長(zhǎng)li累加概率累加概率碼字碼字wi u10.202.34

20、30000 u20.192.4130.2001 u30.182.4830.39011 u40.172.5630.57100 u50.152.7430.74101 u60.103.3440.891110 u70.016.6670.99 對(duì)給定信源對(duì)給定信源 進(jìn)行進(jìn)行r =2進(jìn)制香農(nóng)編碼。進(jìn)制香農(nóng)編碼。 1234567 ( )0.2 0.19 0.18 0.17 0.15 0.10 0.01 i Uuuuuuuu P u 3.14l 83.1% c 比比 較較 1234567 00.01 U Uuuuuuuu P 霍夫曼編碼霍夫曼編碼 費(fèi)諾編碼費(fèi)諾編碼

21、 香農(nóng)編碼香農(nóng)編碼 平均碼長(zhǎng)（碼元平均碼長(zhǎng)（碼元/符號(hào)）符號(hào)）2.722.743.14 編碼效率編碼效率95.96%95.3%83.1% 用二元符號(hào)表用二元符號(hào)表 對(duì)其進(jìn)行定長(zhǎng)編碼，若所對(duì)其進(jìn)行定長(zhǎng)編碼，若所 編的碼為編的碼為000，001，010，011，100，101， （1）對(duì)編碼器輸出碼元的一維概率）對(duì)編碼器輸出碼元的一維概率P(x1)與與P(x2)。 （2）用二元符號(hào)表）用二元符號(hào)表 ，寫(xiě)出利用霍夫曼編，寫(xiě)出利用霍夫曼編 碼后的編碼，并求編碼后的碼元的一維概率碼后的編碼，并求編碼后的碼元的一維概率P(x1)與與P(x2)、 平均碼長(zhǎng)。平均碼長(zhǎng)。 設(shè)設(shè)DMS為為 03. 007. 01

22、0. 018. 025. 037. 0 654321 uuuuuu P U U 1, 0 21 xxX 1, 0 21 xxX 對(duì)對(duì)U進(jìn)行霍夫曼編碼，并求出平均碼長(zhǎng)進(jìn)行霍夫曼編碼，并求出平均碼長(zhǎng) 和編碼效率和編碼效率 。 注：注： 設(shè)設(shè)DMS為為 1 . 01 . 02 . 02 . 04 . 0 54321 uuuuu P U U l 322. 14 . 0log,322. 22 . 0log,322. 31 . 0log 習(xí)題習(xí)題 用二元符號(hào)表用二元符號(hào)表 對(duì)其進(jìn)行定長(zhǎng)編碼，對(duì)其進(jìn)行定長(zhǎng)編碼， （1）求無(wú)失真定長(zhǎng)編碼的最小碼長(zhǎng)和編碼效率。）求無(wú)失真定長(zhǎng)編碼的最小碼長(zhǎng)和編碼效率。 （2）將編

23、碼器的輸出視為新信源）將編碼器的輸出視為新信源X，求，求H(X)； （3）若所編的碼為）若所編的碼為000，001，010，011，100，101，求，求 編碼器輸出碼元的一維概率編碼器輸出碼元的一維概率P(x1)與與P(x2)。 （4）若引入失真，要求差錯(cuò)率為）若引入失真，要求差錯(cuò)率為Pe=10-6，編碼效率為，編碼效率為 90%，則需要對(duì)多長(zhǎng)的信源符號(hào)序列進(jìn)行編碼？，則需要對(duì)多長(zhǎng)的信源符號(hào)序列進(jìn)行編碼？ （5）用二元符號(hào)表）用二元符號(hào)表 ，寫(xiě)出利用霍夫曼編，寫(xiě)出利用霍夫曼編 碼后的編碼，并求平均碼長(zhǎng)、編碼效率、編碼后的碼元的碼后的編碼，并求平均碼長(zhǎng)、編碼效率、編碼后的碼元的 一維概率一維概率P(x1)與與P(x2)。 設(shè)設(shè)DMS為為 03. 007. 010. 018. 025. 037. 0 654321 uuuuuu P U U 1, 0 21 xxX 1, 0 21 xxX 習(xí)題習(xí)題 對(duì)對(duì)U進(jìn)行霍夫曼編碼，并求出平均碼長(zhǎng)進(jìn)行霍夫曼編碼，并求出平均碼長(zhǎng) 和編碼效率和編碼效率 。 注：注： 設(shè)設(shè)DMS為為 1 . 01 . 02 . 02 . 04 . 0 54321 uuuuu P U U l 322. 14 . 0log,322. 22 . 0lo