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

1、信源編碼復習信源編碼復習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：定長碼。：定長碼。W3：變長碼。：變長碼。奇異碼。奇異碼。定長非奇異碼肯定是定長非奇異碼肯定是UDC。u u u uu u u uu u u u u12434321121211,00,10,01100100110,01,00,11,00,1,00,1W2：定長碼。：定長碼。W4：變長碼。：變長碼。W5：變長碼。：變長碼。非奇異碼。非奇異碼。非奇異碼。非奇異碼。非奇異碼。非奇異碼。非奇異碼。非奇異碼。續(xù)長碼。續(xù)長碼。非續(xù)長碼。非續(xù)長碼。續(xù)長碼。續(xù)長碼。及時碼。及時碼。

4、非及時碼。非及時碼。奇異碼肯定不是奇異碼肯定不是UDC。不是不是UDC。非續(xù)長碼肯定是非續(xù)長碼肯定是UDC。是是UDC。非及時碼。非及時碼。非續(xù)長碼。非續(xù)長碼。11碼碼奇異碼奇異碼非奇異碼非奇異碼非唯一可譯碼非唯一可譯碼唯一可譯碼唯一可譯碼定長非奇異碼定長非奇異碼變長非續(xù)長碼變長非續(xù)長碼（部分）變長續(xù)長碼（部分）變長續(xù)長碼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例：對二元例：對二元DMS進行無失真編碼：進行無失真編碼：N=1414321uuPU符號/811. 034log434log41)43,41()(bitHUH若用

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

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

9、均碼長信源符號碼元/844. 02688. 1NllNN=3,4時，991. 0,985. 04323分析：分析：1、比較定長編碼與變長編碼的編碼效率可知，尤其在、比較定長編碼與變長編碼的編碼效率可知，尤其在N較大時變長編碼的效率遠大于定長編碼。較大時變長編碼的效率遠大于定長編碼。N定長變長20.8110.96130.8110.98540.8110.991242、若對定長編碼與變長編碼同樣要求編碼效率達到、若對定長編碼與變長編碼同樣要求編碼效率達到96%，允許的譯碼錯誤概率允許的譯碼錯誤概率 時，定長編碼所需序列長度時，定長編碼所需序列長度N：510所需的信源序列長度：所需的信源序列長度：qi

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

11、0000111111. 100123456723456611111112222222UuuuuuuuUP l2345661111111631234566222222232 cH Ulr63326332()100%loglog2 碼元碼元/符號符號 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 定長編碼

12、：定長編碼：001，010，011，100，101，110，111變長編碼：變長編碼：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( )() ()() 碼長方差：碼長方差：l21( )1.4259 l22( )0.3059 碼字不同，碼長也不同，但碼字不同，碼長也不同，但平均碼長相同，因此編碼效平均碼長相同，因此編碼效率相同。率相同。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消息符號消息符號ui消息概率消息概率pi-logpi碼長碼長li累加概率累加概率碼字碼字wiu10.202.3430000u20.192.4130.2001u30.182.

17、4830.39011u40.172.5630.57100u50.152.7430.74101u60.103.3440.891110u70.016.6670.991111110 對給定信源對給定信源 進行進行r =2進制香農編碼。進制香農編碼。1234567( )0.2 0.19 0.18 0.17 0.15 0.10 0.01iUuuuuuuuP u 3.14l 83.1%c 43比比 較較12345600.01UUuuuuuuuP 霍夫曼編碼霍夫曼編碼 費諾編碼費諾編碼 香農編碼香農編碼平均碼長（碼元平均碼長（碼元/符號）符號）2.722.74

18、3.14編碼效率編碼效率95.96%95.3%83.1%44用二元符號表用二元符號表 對其進行定長編碼，若所對其進行定長編碼，若所編的碼為編的碼為000，001，010，011，100，101，（1）對編碼器輸出碼元的一維概率）對編碼器輸出碼元的一維概率P(x1)與與P(x2)。（2）用二元符號表）用二元符號表 ，寫出利用霍夫曼編，寫出利用霍夫曼編碼后的編碼，并求編碼后的碼元的一維概率碼后的編碼，并求編碼后的碼元的一維概率P(x1)與與P(x2)、平均碼長。平均碼長。 設設DMS為為03. 007. 010. 018. 025. 037. 0654321uuuuuuPUU 1, 021xxX

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

20、00，101，求，求編碼器輸出碼元的一維概率編碼器輸出碼元的一維概率P(x1)與與P(x2)。（4）若引入失真，要求差錯率為）若引入失真，要求差錯率為Pe=10-6，編碼效率為，編碼效率為90%，則需要對多長的信源符號序列進行編碼？，則需要對多長的信源符號序列進行編碼？（5）用二元符號表）用二元符號表 ，寫出利用霍夫曼編，寫出利用霍夫曼編碼后的編碼，并求平均碼長、編碼效率、編碼后的碼元的碼后的編碼，并求平均碼長、編碼效率、編碼后的碼元的一維概率一維概率P(x1)與與P(x2)。 設設DMS為為03. 007. 010. 018. 025. 037. 0654321uuuuuuPUU 1, 02

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