信息理論編碼課程PPT 第4章 信源無失真編碼

1、信源編碼復(fù)習(xí)信源編碼復(fù)習(xí)2XYWWUU3UWWU4 12, ,qu uu12, ,rx xxWU12, ,qw wwX:,1,2,iifuwiq 11()()qqiiiiiilP w lP u l 1()qiilP u ll 512341 21 41 81 8UUuuuuP 21112222223332444()0 ,1()10 ,2:()110 ,3()111,3fuwlfuwlffuwlfuwl 411111()222224882iiilP u l 411111()123324881.75iiilP u l 11111222113331444()00 ,2()01 ,2:()10 ,2()

2、11 ,2f uwlf uwlff uwlf uwl 。 。12, ,qu uu01，WU12, ,qw wwX6 iiP wP uiq ()()1,2, ,H WH U ()() H WH UH Xll ()()()H WH UH Xll ()()()R X, ,12rx xx12, ,qu uu12, ,rx xxWU12, ,qw wwX7 maxmax()()()()loglogcRH XH UlH URHXrlr1cc X, ,12rx xx12, ,qu uu12, ,rx xxWU12, ,qw wwX8f1f UWWU9105種不同的碼種不同的碼iP uWWWWWUuuuu35

3、1241234()1 200001001 401000010011 81010011100111 8111110111111W1：定長(zhǎng)碼。：定長(zhǎng)碼。W3：變長(zhǎng)碼。：變長(zhǎng)碼。奇異碼。奇異碼。定長(zhǎng)非奇異碼肯定是定長(zhǎng)非奇異碼肯定是UDC。u u u uu u u uu u u u u12434321121211,00,10,01100100110,01,00,11,00,1,00,1W2：定長(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í)碼。

4、非及時(shí)碼。非及時(shí)碼。奇異碼肯定不是奇異碼肯定不是UDC。不是不是UDC。非續(xù)長(zhǎng)碼肯定是非續(xù)長(zhǎng)碼肯定是UDC。是是UDC。非及時(shí)碼。非及時(shí)碼。非續(xù)長(zhǎng)碼。非續(xù)長(zhǎng)碼。11碼碼奇異碼奇異碼非奇異碼非奇異碼非唯一可譯碼非唯一可譯碼唯一可譯碼唯一可譯碼定長(zhǎng)非奇異碼定長(zhǎng)非奇異碼變長(zhǎng)非續(xù)長(zhǎng)碼變長(zhǎng)非續(xù)長(zhǎng)碼（部分）變長(zhǎng)續(xù)長(zhǎng)碼（部分）變長(zhǎng)續(xù)長(zhǎng)碼12 00114w3w2w1w010001114w3w2w1w01114111w 10w 113011w 201w 13r12 ,ql ll11iqlir r412331222221ili 14 r12 ,ql ll11iqlir r15 12, ,qu uu12, ,rx

5、xxWU12, ,qw wwXX12, ,rx xx12, ,Nq 12, ,rx xxWNU12, ,Nqw wwXX12, ,rx xx12iiiiNu uu 1212,iiiNquuuu uu 16NlrNlNrq maxmax()log()loglogNrHUlqHUNrr()()/NH URH XlNmax()()()logcNH XH UlHXrN 12, ,Nq 12, ,rx xxWNU12, ,Nqw wwXX12, ,rx xx17。()()logNrlH UH UNr ()2()2logNrlH UH UNr 18123456723456611111112222222Uu

6、uuuuuuUP 1234567:001010011100101110111UuuuuuuuW7163()()log()32iiiH UP uP u 6332()65.625%log3 log2cH Ulr 3ll loglog72.8loglog2NlqlNr19()NrlH UN 1()NrlH UNNrUNNNlNlNllimlim()NrNNllH UN()()limlimlim100%logrcNNNH UH Ulrl 20例：對(duì)二元例：對(duì)二元DMS進(jìn)行無失真編碼：進(jìn)行無失真編碼：N=1414321uuPU符號(hào)/811. 034log434log41)43,41()(bitHUH若用

7、二元碼符號(hào)若用二元碼符號(hào)(0，1)進(jìn)行定長(zhǎng)編碼：進(jìn)行定長(zhǎng)編碼： 。平均碼長(zhǎng)平均碼長(zhǎng) 1 碼元碼元/信源符號(hào)信源符號(hào)1,021uul碼元/811. 0)()(bitlUHXHR編碼效率為編碼效率為輸出的信息效率輸出的信息效率811. 0log)()()(max1rlUHXHXH要求：對(duì)比定長(zhǎng)編碼與變長(zhǎng)編碼的編碼效率（要求：對(duì)比定長(zhǎng)編碼與變長(zhǎng)編碼的編碼效率（N=2,3,4）。）。練習(xí)題21對(duì)對(duì)U的二次擴(kuò)展信源進(jìn)行定長(zhǎng)編碼，碼表如下表的二次擴(kuò)展信源進(jìn)行定長(zhǎng)編碼，碼表如下表 ：uip(ui)碼字u1u19/1600u1u23/1601u2u13/1610u2u21/1611信源序列碼元/2Nl編碼效率

8、為編碼效率為碼字平均長(zhǎng)度碼字平均長(zhǎng)度811. 0log)()()(max2rlUHXHXH單個(gè)符號(hào)的平均碼長(zhǎng)單個(gè)符號(hào)的平均碼長(zhǎng)信源符號(hào)碼元/122NllNN=2N=3,4時(shí)，811. 04322對(duì)對(duì)U的二次擴(kuò)展信源進(jìn)行變長(zhǎng)編碼，碼表如下表的二次擴(kuò)展信源進(jìn)行變長(zhǎng)編碼，碼表如下表 ：uip(ui)碼字u1u19/160u1u23/1610u2u13/16110u2u21/16111N=2信源序列碼元/688. 13161316321631169Nl編碼效率為編碼效率為碼字平均長(zhǎng)度碼字平均長(zhǎng)度961. 0844. 0811. 0log)()()(max2rlUHXHXH單個(gè)符號(hào)的平均碼長(zhǎng)單個(gè)符號(hào)的平

9、均碼長(zhǎng)信源符號(hào)碼元/844. 02688. 1NllNN=3,4時(shí)，991. 0,985. 04323分析：分析：1、比較定長(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.96130.8110.98540.8110.991242、若對(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：510所需的信源序列長(zhǎng)度：所需的信源序列長(zhǎng)度：qi

10、iiUHuPuPU12224715. 0)()()log()(7522222221013. 410)96. 01 ()811. 0()96. 0(4715. 0)1 ()()(ccUHUN同樣的編碼效率，變長(zhǎng)編碼信源序列長(zhǎng)度同樣的編碼效率，變長(zhǎng)編碼信源序列長(zhǎng)度N=2時(shí)即可滿足時(shí)即可滿足編碼效率達(dá)到編碼效率達(dá)到96%的要求。隨著的要求。隨著N的增加，編碼效率趨近的增加，編碼效率趨近于于1。2526271101200130001400001500000160000006iu1 2u1u2u3u4u5u6u7()iP u41 251 261 261 221 231 24121221231251200

11、0000111111. 100123456723456611111112222222UuuuuuuuUP l2345661111111631234566222222232 cH Ulr63326332()100%loglog2 碼元碼元/符號(hào)符號(hào) 2829()63 32H U 3ll max()0.6562565.625%()log2cH XHX 63 32l max()1100%()log2cH XHX ()63 32()0.656253H UH Xl ()63 32()163 32H UH Xl max()63 32110.3()log7H UHU 10.34375cc 10cc 定長(zhǎng)編碼

12、：定長(zhǎng)編碼：001，010，011，100，101，110，111變長(zhǎng)編碼：變長(zhǎng)編碼：1，01，001，0001，00001，000001，000000123456723456611111112222222UuuuuuuuUP 30碼字不唯一碼字不唯一31 上例另一種霍夫曼編碼：上例另一種霍夫曼編碼：321101200130001400001500000160000006iuu1u2u3u4u5u6u7()iP u 12345670.350.3040.0050.005UUuuuuuuuP . 005. 065. 035. 015. 001. 100000000111111

13、.l 0 35 10 3020 2030 10 40 04 50 005 60 005 62 2133112102012001300014000015000005 .l 0 35 20 30 20 20 20 10 30 04 40 005 50 005 52 21. 005. 065. 035. 015. 001. 10000000011111112345670.350.3040.0050.005UUuuuuuuuP iuu1u2u3u4u5u6u7()iP u3411012001300014000015000001600000061121020120013000140

14、00015000005qiiiilE llP ull2221( )() ()() 碼長(zhǎng)方差：碼長(zhǎng)方差：l21( )1.4259 l22( )0.3059 碼字不同，碼長(zhǎng)也不同，但碼字不同，碼長(zhǎng)也不同，但平均碼長(zhǎng)相同，因此編碼效平均碼長(zhǎng)相同，因此編碼效率相同。率相同。3536211102201200230013 UUuuuuuuP1234560.360.080.04 qrr(1)23(0.12)(0.46)(1.00)0121201020.32 10.22 10.1820.1620.0830.0431.58l cH Ulr()2.3593.8%log1.58 log3 i

15、uu1u2u3u4u5u67u()iP u371230.450.350.20UUuuuP ()1.518H U 1001(1.00)(0.55)31()0.45 10.3520.2021.55iiilP u l ()1.51897.9%log1.55 log2cH Ulr 38. 016. 028. 01100001111. 0201. 10000. 04025. 059750011. 031751921()3.0675jjjlP u l 22()2 1.51899.0%log3.0675 log2cH Ulr 39400020103011310211031110411114 12345670

16、.1UUuuuuuuuP 00100001111171()0.20 20.19 30.18 30.1720.15 30.10 40.01 42.7 4iiilP u l ()2.6195%log2.74 log2cH Ulr 71()()log()2.61iiiH UP uP u 41log()log()1iiiP ulP u 1110()2,3,iikkPPP uiq 42消息符號(hào)消息符號(hào)ui消息概率消息概率pi-logpi碼長(zhǎng)碼長(zhǎng)li累加概率累加概率碼字碼字wiu10.202.3430000u20.192.4130.2001u30.182.

17、4830.39011u40.172.5630.57100u50.152.7430.74101u60.103.3440.891110u70.016.6670.991111110 對(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.01iUuuuuuuuP u 3.14l 83.1%c 43比比 較較12345600.01UUuuuuuuuP 霍夫曼編碼霍夫曼編碼 費(fèi)諾編碼費(fèi)諾編碼 香農(nóng)編碼香農(nóng)編碼平均碼長(zhǎng)（碼元平均碼長(zhǎng)（碼元/符號(hào)）符號(hào)）2.722.74

18、3.14編碼效率編碼效率95.96%95.3%83.1%44用二元符號(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)表 ，寫出利用霍夫曼編，寫出利用霍夫曼編碼后的編碼，并求編碼后的碼元的一維概率碼后的編碼，并求編碼后的碼元的一維概率P(x1)與與P(x2)、平均碼長(zhǎng)。平均碼長(zhǎng)。 設(shè)設(shè)DMS為為03. 007. 010. 018. 025. 037. 0654321uuuuuuPUU 1, 021xxX

19、1, 021xxX對(duì)對(duì)U進(jìn)行霍夫曼編碼，并求出平均碼長(zhǎng)進(jìn)行霍夫曼編碼，并求出平均碼長(zhǎng) 和編碼效率和編碼效率 。注：注： 設(shè)設(shè)DMS為為1 . 01 . 02 . 02 . 04 . 054321uuuuuPUUl322. 14 . 0log,322. 22 . 0log,322. 31 . 0log習(xí)題習(xí)題45用二元符號(hào)表用二元符號(hào)表 對(duì)其進(jìn)行定長(zhǎng)編碼，對(duì)其進(jìn)行定長(zhǎng)編碼，（1）求無失真定長(zhǎng)編碼的最小碼長(zhǎng)和編碼效率。）求無失真定長(zhǎng)編碼的最小碼長(zhǎng)和編碼效率。（2）將編碼器的輸出視為新信源）將編碼器的輸出視為新信源X，求，求H(X)；（3）若所編的碼為）若所編的碼為000，001，010，011，1

20、00，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)表 ，寫出利用霍夫曼編，寫出利用霍夫曼編碼后的編碼，并求平均碼長(zhǎng)、編碼效率、編碼后的碼元的碼后的編碼，并求平均碼長(zhǎng)、編碼效率、編碼后的碼元的一維概率一維概率P(x1)與與P(x2)。 設(shè)設(shè)DMS為為03. 007. 010. 018. 025. 037. 0654321uuuuuuPUU 1, 02

21、1xxX 1, 021xxX習(xí)題習(xí)題46對(duì)對(duì)U進(jìn)行霍夫曼編碼，并求出平均碼長(zhǎng)進(jìn)行霍夫曼編碼，并求出平均碼長(zhǎng) 和編碼效率和編碼效率 。注：注： 設(shè)設(shè)DMS為為1 . 01 . 02 . 02 . 04 . 054321uuuuuPUUl322. 14 . 0log,322. 22 . 0log,322. 31 . 0log習(xí)題習(xí)題47信源編碼信源編碼由于信源符號(hào)之間存在分布由于信源符號(hào)之間存在分布不均勻和相關(guān)性不均勻和相關(guān)性，使得信源存在，使得信源存在冗余度冗余度，的主要任務(wù)就是減少冗余，提高編碼效率，提高通信的的主要任務(wù)就是減少冗余，提高編碼效率，提高通信的；而；而的目的是降低差錯(cuò)率，提高傳送的的目的是降低差錯(cuò)率，提高傳送的。信源編碼的基本途徑有兩個(gè)：信源編碼的基本途徑有兩個(gè)： 使序列中的各個(gè)符號(hào)盡可能地互相獨(dú)立，即解除相關(guān)性；使序列中的各個(gè)符號(hào)盡可能地互相獨(dú)立，即解除相關(guān)性； 使編碼中各個(gè)符號(hào)出現(xiàn)的概率盡可能地相等，即概率均勻化。使編碼中各個(gè)符號(hào)出現(xiàn)的概率盡可能地相等，即概率均勻化。 無失真編