信息論第5章 信源編碼

1、第章 信源編碼 對(duì)信源有兩個(gè)重要問題1. 信源輸出的信息量的度量問題度量問題；2. 如何更有效地有效地表示信源輸出的問題輸出的問題； 信源輸出的符號(hào)序列，經(jīng)過信源編碼，變換成適合信道傳輸?shù)姆?hào)序列，同時(shí)，在不失真或允許一定失真的條件下，用盡可能少的碼符號(hào)來傳遞信源消息，提高信息傳輸?shù)男?。概述概述信源編碼是以信源編碼是以提高通信的有效性提高通信的有效性為目的編碼。為目的編碼。通常通過通常通過壓縮信源的冗余度壓縮信源的冗余度來實(shí)現(xiàn)。來實(shí)現(xiàn)。信源編碼信源編碼統(tǒng)計(jì)匹配編碼據(jù)信源符號(hào)的概率不同，編碼的碼長不同。概率大的信源符號(hào)編的碼字短，使平均馬場最短 ，達(dá)到壓縮信源冗余度的目的編碼的定義 將信源符號(hào)

2、序列按一定的數(shù)學(xué)規(guī)律映射成碼符號(hào)序列的過程是信源編碼過程，完成編碼功能的器件就是niiaaaaxAl,21Lliiiiixxxxx,21編碼器的作用編碼器的作用是將信源符號(hào)集X中的符號(hào)變換成由碼符號(hào)組成的一一對(duì)應(yīng)的輸出符號(hào)序列編碼器的輸出編碼器的輸出稱為碼字碼字，碼字的集合稱為碼碼，信源符號(hào)對(duì)應(yīng)碼字需的碼符號(hào)的個(gè)數(shù)表示碼字長度，簡碼字長度，簡稱碼長稱碼長。分組碼才有對(duì)應(yīng)的碼表舉例舉例怎么用編碼器實(shí)現(xiàn)對(duì)信源符號(hào)的編碼 信源的概率空間為 把信源符號(hào)編碼為適合二元信道的二元碼。二元信道是數(shù)字通信中最常用的一種新到，它的碼符號(hào)集為0，1。)()()(442211spsspsspsPS將信源通過一個(gè)二元

3、信道傳輸，就必須把信源符號(hào)si變換成由0，1符號(hào)組成的碼符號(hào)序列，即進(jìn)行編碼?？梢杂貌煌亩a符號(hào)序列與信源符號(hào) 一一對(duì)應(yīng)，就得到不同的碼。信源符號(hào)信源符號(hào)P(si)碼碼1碼碼2s1P(s1)000s2P(s2)0101s3P(s3)10001s4P(s4)11111定長碼定長碼變長碼變長碼二次擴(kuò)展信源符號(hào)二次擴(kuò)展信源符號(hào)二次擴(kuò)展碼字二次擴(kuò)展碼字S1=S1S100s2=S1S2001s4=S4S4111111碼的分類1. 分組碼和非分組碼:將信源符號(hào)集中的每個(gè)信源符號(hào)固定映射成一個(gè)碼字 ，這樣的碼稱為。非分組碼非分組碼(樹碼樹碼):樹碼編碼器輸出的碼符號(hào)通常與編碼器的所有輸入的信源符號(hào)都有關(guān)

4、碼的分類2. 奇異碼和非奇異碼 若一種分組碼中所有碼字都不相同，也即信源符號(hào)和碼字一一對(duì)應(yīng)，則稱為，否則為奇異碼。信源符號(hào)信源符號(hào)ai符號(hào)出現(xiàn)概率符號(hào)出現(xiàn)概率p(ai)碼碼1碼碼2a11/200a21/41110a31/80000a41/81101奇異碼非奇異碼碼的分類3. 唯一可譯碼和非唯一可譯碼 任意有限長的碼元序列，只能唯一地分割成一個(gè)個(gè)碼字，便是唯一可譯碼。信源符號(hào)信源符號(hào)ai符號(hào)出現(xiàn)概率符號(hào)出現(xiàn)概率p(ai)碼碼1碼碼2碼碼3a11/2001a21/4111010a31/80000100a41/811011000奇異碼非奇異碼EG: 10000100由碼2產(chǎn)生(10,0,0,01,0

5、0)產(chǎn)生的碼流，譯碼時(shí)可有多種分割方法，產(chǎn)生歧義。唯一可譯碼首先是非奇異碼，且任意有限長的碼字序列不會(huì)雷同。一個(gè)分組碼，若對(duì)以任意有限的整數(shù)N，其N次擴(kuò)展碼均維非奇異，則為唯一可譯碼 。碼的分類4.即時(shí)碼和非即時(shí)碼 無須考慮后續(xù)的碼符號(hào)就可以從碼符號(hào)序列中譯出碼字，這樣的唯一可譯碼 稱為 即時(shí)碼。 信源符號(hào)信源符號(hào)ai符號(hào)出現(xiàn)概率符號(hào)出現(xiàn)概率p(ai)碼碼1碼碼2碼碼3碼碼4a11/20011a21/411101001a31/80000100001a41/8110110000001奇異碼非奇異碼即時(shí)碼非即時(shí)碼碼的分類碼非分組碼分組碼奇異碼非奇異碼非唯一可譯碼唯一可譯碼即時(shí)碼非即時(shí)碼樹圖樹根碼字

6、的起點(diǎn)樹枝數(shù)碼的進(jìn)制數(shù)節(jié)點(diǎn)碼字或碼字的一部分終端節(jié)點(diǎn)碼字節(jié)數(shù)碼長非滿樹變長碼滿樹等長碼根節(jié)點(diǎn)終端節(jié)點(diǎn)中間節(jié)點(diǎn)一階節(jié)點(diǎn)有最多r個(gè)；N階節(jié)點(diǎn)最多有rN個(gè)；若制定某個(gè)N階節(jié)點(diǎn)為終端節(jié)點(diǎn)，表示一個(gè)信源符號(hào)，則該節(jié)點(diǎn)就不再延伸，相應(yīng)的碼字即為從樹根到此端點(diǎn)的樹枝標(biāo)號(hào)序列，其長度為N。為即時(shí)碼。0001111克拉夫特Kraft不等式1 ,C,X,S121q212121qilqrqirlllxxxsss存在的充要條件是則即時(shí)碼碼長分別為的碼為對(duì)信源進(jìn)行編碼，得到碼符號(hào)集為設(shè)信源符號(hào)集為舉例 用二進(jìn)制對(duì)符號(hào)集a1,a2,a3,a4進(jìn)行編碼，對(duì)應(yīng)的碼長分別為K1=1，K2=2，K3=2，K4=3，問是否存在滿足

7、這種Ki的唯一可譯碼？解：據(jù)克勞夫特不等式得 因此，不存在滿足這種Ki的唯一可譯碼 18922222322141iKi其中：m是進(jìn)制數(shù)； n是信源符號(hào)數(shù)；11niKim各碼字的長度Ki應(yīng)符合：該不等式是唯一可譯碼的必要條件，不是唯一可譯碼的必要條件。定長碼及定長信源編碼定理 若要實(shí)現(xiàn)無失真編碼，所編的碼必須是唯一可譯碼。 若定長碼是非奇異碼，則它的任意有限長N次擴(kuò)展碼一定也是非奇異碼，定長非奇異碼一定是唯一可譯碼。若對(duì)信源S的N次擴(kuò)展信源次擴(kuò)展信源進(jìn)行定長編碼，信源的符號(hào)個(gè)數(shù)qN滿足： 若對(duì)一個(gè)有q個(gè)信源符號(hào)的信源S進(jìn)行編碼，信源S存在唯一可譯定長碼的條件，其中 是碼符號(hào)集中的碼元數(shù)， 是定長

8、碼的碼長。lNrq取對(duì)數(shù)qNlrlog對(duì)于定長唯一可譯碼，平均每個(gè)原始信源符號(hào)至少需要碼符號(hào)的個(gè)數(shù) 英文電報(bào)信源有32個(gè)符號(hào)，對(duì)每一個(gè)符號(hào)進(jìn)行二元編碼，每個(gè)英文電報(bào)符號(hào)至少要用二元符號(hào)進(jìn)行編碼才能得到唯一可譯碼。q=32r=25logqlr：考慮到符號(hào)出現(xiàn)的概率以及符號(hào)之間的相關(guān)性后，實(shí)際平均每個(gè)英文電報(bào)符號(hào)所提供的信息量約1.4bit，遠(yuǎn)小于5bit，因此定長編碼后，每個(gè)碼字只載1.5bit信息，5個(gè)二進(jìn)制符號(hào)最大能載5bit信息 ，因此，定長編碼的信息傳輸效率低。: (1)對(duì)于不會(huì)出現(xiàn)的符號(hào)序列不予編碼，這樣不會(huì)造成誤差； (2)對(duì)于概率非常小的信源符號(hào)序列不予編碼，這樣可能會(huì)造成一定誤差

9、，但當(dāng)信源符號(hào)序列N足夠大，誤差概率非常小 英文電報(bào)信源有32個(gè)符號(hào)，對(duì)每一個(gè)符號(hào)進(jìn)行二元編碼，每個(gè)英文電報(bào)符號(hào)至少要用二元符號(hào)進(jìn)行編碼才能得到唯一可譯碼。q=32r=25logqlr：考慮到符號(hào)出現(xiàn)的概率以及符號(hào)之間的相關(guān)性后，實(shí)際平均每個(gè)英文電報(bào)符號(hào)所提供的信息量約1.4bit，遠(yuǎn)小于5bit，因此定長編碼后，每個(gè)碼字只載1.5bit信息，5個(gè)二進(jìn)制符號(hào)最大能載5bit信息 ，因此，定長編碼的信息傳輸效率低。: (1)對(duì)于不會(huì)出現(xiàn)的符號(hào)序列不予編碼，這樣不會(huì)造成誤差； (2)對(duì)于概率非常小的心愿符號(hào)序列不予編碼，這樣可能會(huì)造成一定誤差，但當(dāng)信源符號(hào)序列N足夠大，誤差概率非常小由于英文信源的

10、極限熵H 1.4bit/信源符號(hào)，所以碼長l滿足l/N 1.4，即平均每個(gè)英文符號(hào)只需要近似1.4個(gè)二元碼符號(hào)來表示，從而提高了信息傳輸效率定長編碼定理定長編碼定理 由L個(gè)符號(hào)組成的，每個(gè)符號(hào)的熵為HL(X)的無記憶平穩(wěn)信源符號(hào)序列(X1,X2,Xl,XL)，可用KL個(gè)符號(hào)Y1,Y2,Yk,YKL (每個(gè)符號(hào)有m中可能值)進(jìn)行定長編碼。，譯碼幾乎必定出錯(cuò)足夠大時(shí)值。而當(dāng)則譯碼差錯(cuò)一定是有限時(shí)反之，當(dāng)；差錯(cuò)小于足夠大時(shí)，必可使以馬則當(dāng)只要對(duì)任意L,2)(logLKL,)(logLK0,0,LLXHmXHmLL同樣適同樣適用于平用于平穩(wěn)有記穩(wěn)有記憶信源，憶信源，將式中將式中的的H(S)改稱極改稱極

11、限熵即限熵即可。可。必須越長。序列長度，則信源越小，編碼效率又要高率可得出：當(dāng)允許錯(cuò)誤概其中須滿足長度信源序列率小于任一給定的正數(shù)并且允許的譯碼錯(cuò)誤概要達(dá)到最佳編碼效率和信源熵的條件下已知方差L(X)H)(1)1 (X)H)I(xD)I(xD :L,)I(xDL222L2iiiL編碼效率息量；編碼后能載荷的最大信表示平均每個(gè)信源符號(hào)最佳編碼效率為編碼效率為定義，設(shè)碼字長為為的個(gè)數(shù)碼，碼符號(hào)集中碼符號(hào)的符號(hào)序列進(jìn)行定長編對(duì)信源的長為的離散無記憶信源，若設(shè)熵為logm(X)H(X)Hlogm(X)H(X)H ,(X)HLLLLLLlLlKlmL。，求，誤碼錯(cuò)誤概率要求編碼效率設(shè)離散無記憶信源L10

12、0.9,04. 005. 006. 007. 01 . 01 . 018. 04 . 0PX6-87654321aaaaaaaa87622222812283. 2L8110108 . 9100.287.82)(L )(82. 7)()(log)()(28. 09 . 0)()(H7.1122.83bit/83. 2%9055. 2KK)(H1L/55. 2logH(X)XbitXHppxIDXXHXbitXbitppiiiiiii所以，為信源序列的自信息方差根據(jù)種可能性有進(jìn)行定長二元編碼，共即每個(gè)符號(hào)用符號(hào)得，據(jù)若取符號(hào)信源熵。，求，要求設(shè)離散無記憶信源N100.96,4143PS5-21ss

13、75-2222221104.13100.040.96(0.811)0.4715NH(X)14715. 0)()(log)()I(xD,/0.81134log43log441H(X)所以因自信息的方差信源符號(hào)比特解：信源熵XHxpxpiiii.,1047實(shí)際中很難實(shí)現(xiàn)才能實(shí)現(xiàn)給定的要求以上信源序列長度長達(dá) 變長碼及變長信源編碼定理什么樣的碼是唯一可譯碼或即時(shí)碼？ Kraft不等式和McMillan不等式給出了即時(shí)碼和唯一可譯碼的碼長條件。變變長長碼碼信源符號(hào)信源符號(hào)Si概率分布概率分布碼碼1碼碼2碼碼3碼碼4S11/20011S21/411101001S31/80000100001S41/811

14、0110000001非奇異碼唯一可譯碼唯一可譯碼即時(shí)碼克拉夫特Kraft不等式1 ,C,X,S121q212121qilqrqirlllxxxsss存在的充要條件是則即時(shí)碼碼長分別為的碼為對(duì)信源進(jìn)行編碼，得到碼符號(hào)集為設(shè)信源符號(hào)集為McMillan不等式1,C,X,S121q212121qilqrqirlllxxxsss要條件是則唯一可譯碼存在的充碼長分別為的碼為對(duì)信源進(jìn)行編碼，得到碼符號(hào)集為設(shè)信源符號(hào)集為單個(gè)符號(hào)變長編碼定理1log)(HKlog)(HK mH(X),mXmX滿足下列不等式：其碼字平均長度一種無失真編碼方式，一定存在編碼，進(jìn)制碼元進(jìn)行變長每個(gè)信源符號(hào)用號(hào)熵為若離散無記憶信源的

15、符離散平穩(wěn)無記憶序列變長編碼定理為任意小正數(shù)式中滿足下列不等式：使平均信息率法方必存在一種無失真編碼無記憶信源的離散平穩(wěn)對(duì)于平均符號(hào)熵為(X)HK(X)HK,(X)HLLLmmXmXmXmXlogLKK1log)(LHKlog)(LHK1log)(HKlog)(HLLLLL已知平均輸出信息率為滿足：平均碼字長度M進(jìn)制碼元作變長編碼，序列長度為L個(gè)信源符號(hào)編碼效率LmXHXHKXHLLLlog)()()(KXHmLKXHLLL)(1log)(11碼的剩余度：編碼效率：衡量各種編碼方法與最佳碼的差距衡量各種編碼方法與最佳碼的差距在二元無噪無損信道中：在二元無噪無損信道中信息傳輸率：KXHL)(KX

16、HRL)(單位是比特單位是比特/碼符號(hào)碼符號(hào)無單位無單位舉例源的信息傳輸率。次、三次、四次擴(kuò)展信求：其信息傳輸率及二概率空間為有一離散無記憶信源的4143PX :21aa將信道中平均每個(gè)符號(hào)所能傳送的信息量定義為信道的信息傳輸率R 下表所示進(jìn)行編碼，其即時(shí)碼如的二次擴(kuò)展信源若對(duì)信源二元碼符號(hào)輸出的信息傳輸率編碼效率信源符號(hào)二元碼符號(hào)平均碼長。來構(gòu)造即時(shí)碼，用二元碼符號(hào)符號(hào)信源熵為221XX0.811bit/R811. 0)(H/1K1, 0100.811bit/34log43log441H(X) KXaa序列序列序列概率序列概率即時(shí)碼即時(shí)碼a1a19/160a1a23/1610a2a13/16

17、110a2a21/16111編碼效率編碼效率：信源的平均符號(hào)熵是采用了平均符號(hào)碼長來編碼后得到的效率。二元碼編碼后的信息傳輸率和編碼效率在數(shù)值上是相等的二元碼符號(hào)四次擴(kuò)展信源二元碼符號(hào)三次擴(kuò)展信源同樣的方法：二元碼符號(hào)輸出的信息效率編碼效率信源符號(hào)二元碼符號(hào)為：每單個(gè)符號(hào)的平均碼長信源序列二元碼符號(hào)碼字平均長度為0.991bit/R 0.991 0.985bit/R 0.985 0.961bit/R0.961270.81132/32272KK/16273161316321631169K32322222若對(duì)這一信源采用定長二元碼編碼，要求編碼效率達(dá)到96%，允許譯碼錯(cuò)誤概率51075222212

18、2221013. 41004. 0)96. 0(0.811)0.4715L)(4715. 0)()(log)(為所需要的信源序列長度自信息的方差為iiibitXHppX定長碼需要的信源序列長，使得碼表很大，且總存在譯碼差錯(cuò)；而變長碼編碼效率達(dá)到96%時(shí)，只需要L=2，而且可實(shí)現(xiàn)無失真編碼，編碼后的信息傳輸率R也越來越接近無噪 無損二元信道的信道容量C=1bit/符號(hào)通過對(duì)擴(kuò)展信源進(jìn)行編通過對(duì)擴(kuò)展信源進(jìn)行編碼，可以提高編碼后的碼，可以提高編碼后的信道的信息傳輸率信道的信息傳輸率最佳變長編碼 香農(nóng)編碼方法 費(fèi)諾編碼方法 哈夫曼編碼方法 凡是能載荷一定的信息量，且碼字的平均長度最短，可分離的變長碼的

19、碼字集合稱為。 下面介紹幾種最佳變長編碼均為統(tǒng)計(jì)匹配編碼，都是對(duì)出現(xiàn)概率較高的信源符號(hào)編短碼，而對(duì)出現(xiàn)概率較小的信源符號(hào)編長碼，從而使，達(dá)到最佳編碼的目的。香農(nóng)編碼niinnxpxpxpxpxxx121211)(,)(.)()(.設(shè)有離散無記憶信源設(shè)有離散無記憶信源香農(nóng)編碼方法的步驟香農(nóng)編碼方法的步驟a) 按信源符號(hào)的概率從大到小的順序排隊(duì)設(shè)設(shè))(.)()(21nxpxpxpb) 按下式依次計(jì)算每個(gè)信源符號(hào)的二元碼碼長iKnixpKii, 2, 1)(1logc)為了變成唯一可譯碼，計(jì)算第i個(gè)消息的累加概率nixpPikki, 2 , 1)(11d) 將累加概率變成二進(jìn)制小數(shù)，取小數(shù)點(diǎn)后 數(shù)作

20、為第i各信源符號(hào)的碼字iK舉例01. 010. 015. 017. 018. 019. 020. 0)(7654321aaaaaaaXPX設(shè)設(shè)有一單符號(hào)離散無記憶信源有一單符號(hào)離散無記憶信源試試對(duì)該信源編二進(jìn)制香農(nóng)碼。對(duì)該信源編二進(jìn)制香農(nóng)碼。解答：信源消息符號(hào)信源消息符號(hào)ai符號(hào)概率符號(hào)概率p(ai)累加概率累加概率Pi-logp(ai)碼字長度碼字長度Ki 碼字碼字a10.2002.343000a20.190.22.413001a30.180.392.483011a40.170.572.563100a50.150.742.743101a60.100.893.3441110a70.010.99

21、6.6671111110nixpKii,2, 1)(1lognixpPikki, 2 , 1)(1171/14.3)( iiiKapK符號(hào)碼元平均碼長碼符號(hào)編碼后信息傳輸率bit/834. 014. 362. 2)( KXHR62. 2)(XH%44.83)(KXH費(fèi)諾編碼a) 按信源符號(hào)的概率從大到小的順序排隊(duì))(.)()(21nxpxpxpb) 將依次排列的信源符號(hào)按概率值分為兩大組，使兩大組概率之和近似相同，并對(duì)各組賦予一個(gè)二進(jìn)制碼元”0”和”1”；依次重復(fù)上述操作，直到每個(gè)組只剩下一個(gè)信源符號(hào)為止。c) 信源符號(hào)所對(duì)應(yīng)的碼字即為費(fèi)諾碼費(fèi)諾碼。舉例與香農(nóng)編碼例子相同消息消息符號(hào)符號(hào)ai符

22、號(hào)概符號(hào)概率率p(ai)第一次第一次分組分組第二次第二次分組分組第三次第三次分組分組第四次第四次分組分組二元二元碼字碼字碼長碼長Kia10.2000002a20.19100103a30.1810113a40.1710102a50.15101103a60.101011104a70.0111111471/74.2)( iiiKapK符號(hào)碼元平均碼長碼符號(hào)編碼后信息傳輸率bit/953. 074. 262. 2)( KXHR費(fèi)諾費(fèi)諾碼比碼比香農(nóng)香農(nóng)碼的碼的平均平均碼長碼長小，小，消息消息傳輸傳輸速率速率大，大，編碼編碼效率效率高！高！哈夫曼編碼a) 按信源符號(hào)的概率從大到小的順序排隊(duì))(.)()(2

23、1nxpxpxpb) 取兩個(gè)概率最小的字母分別配以”0”和”1”兩個(gè)碼元，并將這兩個(gè)概率相加作為一個(gè)新字母的概率，與未分配的二進(jìn)制符號(hào)的字母重新排隊(duì)；對(duì)重排后的兩個(gè)概率最小符號(hào)重復(fù)上述操作。依次重復(fù)上述操作，直到最后兩個(gè)符號(hào)配以0和1為止。c) 從最后一級(jí)開始，向前返回得到各個(gè)信源符號(hào)所對(duì)應(yīng)的碼元序列，即相應(yīng)的碼字。舉例與香農(nóng)編碼例子相同消息消息符號(hào)符號(hào)ai符號(hào)概率符號(hào)概率p(ai)編碼過程編碼過程二元二元碼字碼字碼長碼長Kia10.200.20 0.26 0.350.390.61102a20.190.19 0.20 0.260.350.39112a30.180.18 0.19 0.200.2

24、60003a40.170.17 0.18 0.190013a50.150.15 0.170103a60.100.1101104a70.0101114010101010101每次相 加時(shí)都將“0”和“1”賦與相加的兩個(gè)概率，由該符號(hào)開始一直走到最后的“1”， 將路線上所遇到的“0”和“1”按最低位到最高位的順序排好，就是該符號(hào)的霍夫曼編碼?？偨Y(jié)71/72.2)( iiiKapK符號(hào)碼元平均碼長碼符號(hào)編碼后信息傳輸率bit/96. 072. 262. 2)( KXHR編碼編碼平均碼長平均碼長信息傳輸率信息傳輸率香農(nóng)碼3.140.831費(fèi)諾碼2.740.953霍夫曼編碼2.720.96 上述幾種編碼

25、都是針對(duì)離散無記憶信源的單個(gè)信源符號(hào)的編碼，因此在編碼時(shí)沒有考慮信源符號(hào)之間的相關(guān)性?；舴蚵a是最佳碼，但實(shí)際使用時(shí)霍夫曼編碼的設(shè)備還是比較復(fù)雜的。一般只適用于已知其統(tǒng)計(jì)特性的信源。若信源的統(tǒng)計(jì)特性不知或發(fā)生變化時(shí)，則采用所謂的通用編碼方法?；舴蚵幋a霍夫曼編碼游程編碼：用一個(gè)符號(hào)值或串長表示連續(xù)出現(xiàn)的信源符號(hào)(這些連續(xù)出現(xiàn)的信源符號(hào)構(gòu)成了一段連續(xù)的“游程”)，使碼符號(hào)序列長度少于原始信源符號(hào)序。符號(hào)碼標(biāo)識(shí)碼游程長度：二元序列000101110010001 變換成游程序列31132131 0游程和1游程是交替出現(xiàn)的 范圍范圍：游程編碼只適用于二元序列，對(duì)于多元信源，一般不直接利用游程編碼。算術(shù)

26、編碼：從全序列出發(fā)，將各信源序列的概率映射到0，1區(qū)間上，使每個(gè)序列對(duì)應(yīng)著區(qū)間內(nèi)的一點(diǎn)，也就是一個(gè)二進(jìn)制的小數(shù)。這些點(diǎn)把0，1區(qū)間分成許多小段，每段的長度等于某一序列的概率。再在段內(nèi)取一個(gè)二進(jìn)制小數(shù)，其長度可與該序列的概率匹配，達(dá)到高效率編碼的目的。：進(jìn)行算術(shù)編碼。對(duì)符號(hào)序列信源符號(hào)集431432143211 . 0)(, 1 . 0)(, 2 . 0)(, 6 . 0)(,Saaaapapapapaaaa第一個(gè)符號(hào)a1的概率區(qū)間前兩個(gè)符號(hào)a1a3的概率區(qū)間符號(hào)a1a3a4的概率區(qū)間)()()()()()()(rpspsrprFspsFsrF設(shè)N長信源符號(hào)序列s的概率p(s)和累積概率F(s)

27、;遞推出遞推出N+1長信源符號(hào)序列sr的概率p(sr)和累積概率F(sr);r為新添加的符號(hào))(10001001)100010001. 0(0.534)F(8006. 01log)(1log0.534)F()()F()()F()F(006. 01 . 01 . 06 . 0)(210431431311431431431注意最后一位有進(jìn)位。所以編碼碼字為小數(shù)：將累加概率變成二進(jìn)制碼長累加概率的概率符號(hào)序列aaasplaaapaapaaaaaaapaaaLZW編碼 對(duì)于統(tǒng)計(jì)特性不可知時(shí)，需要用到具有自適應(yīng)性能的通用編碼方法，LZW編碼就是一種基于字典的編碼方法。LZW編碼步驟編碼步驟如下：1、初始化字典，讀入一個(gè)字符放入W中。2、讀入一個(gè)字符K：1不存在字符K可讀：輸出W對(duì)應(yīng)的字碼。結(jié)束編碼。2WK在字典中：將K加入到W末尾。3WK不在字典中：將字碼W輸出，然后將WK加入字典，并令W為K。LZW編碼LZW解碼步驟如下：1、初始化字典，讀入一個(gè)字碼W。2、讀入一個(gè)字碼K：1不存在字碼K可讀：輸出W對(duì)應(yīng)的字符（串）。結(jié)束解碼。2存在字碼K可讀：在W對(duì)應(yīng)的字符（串）末尾加入字碼K的第一個(gè)字符，形成的字符串加入字典。然后輸出W對(duì)應(yīng)的字符（串），把K的值給W。字符串字符串索引索引字符串字符串索引索引a0HLZW-CLEAR2Hb1HL