第五章無失真編碼2

1、無失真信源編碼無失真信源編碼n無失真編碼概述n定長信源編碼n變長信源編碼n實用的無失真信源編碼方法舉例5.1無失真編碼器1離散、無失真、無記憶信源編碼的一般模型：總碼組合數(shù)：1()qSSS1()CCCr總組合數(shù)：qNlr入出信源編碼有q個源字母有r個碼字母5.1無失真編碼器2n問題問題：能否進行無失真編碼，怎樣進行無失真編碼若：不考慮信源統(tǒng)計特性：n應(yīng)滿足條件應(yīng)滿足條件： 相互矛盾！ NlNlrr無失真：q有效：qloglogNllqqrNr由結(jié)論結(jié)論：當(dāng)q=r時，lN不有效。當(dāng)l=N時，rq，亦不滿足有效性解決辦法解決辦法：引入信源統(tǒng)計特性。l l5.1無失真編碼器3n考察無失真條件考察無失

2、真條件： 分別表示等概條件下的消息熵 與碼字熵 之比， 考慮信源的實際統(tǒng)計特性（非等概），實際消息熵為： 代入無失真條件得： 此時：即使q=r,只要 就有可能實現(xiàn)l0,0，只要滿足： (l/N)log rH(S)+ 則：當(dāng)N足夠大時，可使譯碼差錯小于， 反之，當(dāng) (l/N)logrH(S)-2 時，譯碼一定出錯。解釋：定長編碼定理給出了信源進行等長編碼所需碼長的理論極限值。 5.3定長編碼定理2-進一步理解n若要求變得的等長碼是唯一可譯的，則必須：n若N1，則：n結(jié)論結(jié)論：對于唯一可譯碼，每個信源符號至少需要用 個碼符號來變換。n當(dāng)采用二元碼編碼時，r2，則：n結(jié)論結(jié)論：對信源進行二元等長編碼

3、時，每個信源符號所需碼長的極限值為 loglogqrloglogqNr1loglog ()Nlqlq bitN log ()q bitloglogNllqqrNr例1：英文電報有32個符號（266），即q=32， 若r=2，N1（即對信源的逐個符號進行二元編碼）， 則：解釋：每個英文電報符號至少需要用5位二元符號編碼問題：第三章：在考慮符號出現(xiàn)的概率和符號間相關(guān)性前提下,每個英文符 號平均攜帶的信息量是1.4bit/符號（ ），5bit/符號， 等長編碼效率極低，如何提高效率？如何體現(xiàn)有效性？loglog325lqBit/符號bitH4 . 1解決方法：考察：字母個數(shù)為n，字母出現(xiàn)非等概，且字

4、母之間相關(guān)長度為L的英文信源，其可能的字母序列總數(shù)為 ；但其中大部分字母序列是無意義的字母組合，而且隨著N的增加，這種無意義序列的總數(shù)越來越大。方法：進行聯(lián)合編碼，即對字母序列編碼，且只對哪些有意義的字母序列編碼，即需編碼的字母序列的總數(shù) ,則平均每個信源符號所需的碼符號個數(shù)可以大大減少，從而提高了傳輸效率。問題：會引入一定的誤差，當(dāng)N足夠長后，誤差可以任意小。NqNq5.3定長編碼定理3證明n考察離散、隨機序列信源的統(tǒng)計特性 漸進等分割性（AEP）nAEP描述： 漸進等分割定理：漸進等分割定理： （熵定理，遍歷性定理） 設(shè) 是離散無記憶信源輸出的一個特定序列，則任給 和 ，總可以找到一個整數(shù)

5、 ，使當(dāng) 時，有：Nssss.21000N0NN 1| )(|)(logSHPNsP引入：漸進等分割性（引入：漸進等分割性（AEP）5.3定長編碼定理4 AEP物理意義任何一個離散隨機序列信源當(dāng)序列長度時,信源序列會產(chǎn)生兩極分化.大概率事件集合 與小概率事件集合 n對于 有性質(zhì): (信源熵) (大概率事件熵) (等概率) n對于 有性質(zhì): 由此可見，信源編碼只需對信源中少數(shù)少數(shù)落入典型大概率事件的集合的符號進行編碼即可 。 而 對大 多 數(shù)大 多 數(shù)屬 于 非 典 型 小 概 率 事 件 集 合 中 的 信 源 符 號 無 需 編 碼 ,且 。 AAA1)A(pLimL121(,)()kMnH

6、 PPPH PPM/1PPM1A0)A(pLimL0)(AP信源序列集合AALS5.3定長編碼定理5 AEP證明n集合 和 中的序列分別稱為 典型序列和 非典型序列n可以證明：對于任意小的正數(shù) ， ，當(dāng)N足夠大時，n 表示 中所有 典型序列的集合n 表示 集合中序列的個數(shù)個數(shù)n還可以證明：對于任意小的正數(shù) ， ，當(dāng)N足夠大時，n 表示序列 出現(xiàn)的概率n由切比雪夫不等式可得：n 表示S中每個符號攜帶的信息量的n 方差 AA00( )( )(1)2| 2N H SN H SAA|ANSA0Ai ( ) ( )2( ) 2N H SN H SiP)(iPi2( ) 1NP A 2nAEP結(jié)論：當(dāng)L足

7、夠大時，n所有 典型序列出現(xiàn)的概率近似相等，即 典型序列為漸進等概序列n可粗略認(rèn)為 典型序列出現(xiàn)的概率為n所有 典型序列的概率和接近為1，即nAEP應(yīng)用：n提出、證明都是基于離散無記憶序列信源 n平穩(wěn)遍歷信源有類似結(jié)果n體現(xiàn)信源統(tǒng)計特性n用以證明定長編碼定理1)(Ap( )2NH S5.3定長編碼定理5 證明n定長編碼定理證明思路：n將取自S，長為N的信源符號序列分為集合 和n只對集合 中的序列進行一一對應(yīng)的等長編碼n此時的誤差為 ，計算誤差n可見當(dāng) ，且 (K/L)log mH(S)+ 時，n幾個概念：n編碼信息率： （編碼后后平均每個信源符號能載荷的最大信息率）n編碼效率： （編碼前后前后

8、平均每個信源符號能載荷的最大信息率之比）AAA)(APPE0EPNloglNRrRSH)(22P eN5.3定長編碼定理6（物理意義）n結(jié)論：n可推廣至離散、非平穩(wěn)無記憶信源和有記憶信源情況n只要碼字傳輸?shù)男畔⒘看笥谛旁葱蛄袛y帶的信息量，總可以實現(xiàn)幾乎無失真編碼(l/N)logrH(S)+( )logH SlNr二元碼時，r2：( )( )( )( )llNNH SlNH SH SH SRl最佳等長碼時：5.3定長編碼定理7（實際應(yīng)用問題）n編譯碼同步問題n問題：如何使譯碼端知道碼字起點n解決辦法：1、每個碼字加短同步前綴 2、每若干碼字加較長同步前綴n分組長度與編譯碼復(fù)雜性、編譯碼延時等等關(guān)

9、系n問題：要實現(xiàn)有效，源序列分組很長，使得編譯碼 復(fù)雜性和延時增加n解決辦法：目前沒有理想到解決辦法n定長信源編碼的理論意義遠(yuǎn)大于其實用價值5.3定長編碼定理8（舉例)例2：設(shè)有一簡單離散信源：q=2對其進行近似于無失真的等長編碼，若要求其編碼效率為96%，差錯率低于10-5，試求符號聯(lián)合編碼長度N=？解： 由編碼效率：即： 再由:可見,信源序列長度需要4100萬個符號,才能達到上述要求,這顯然是不現(xiàn)實的.一般來說：當(dāng)一般來說：當(dāng)N有限時，高傳輸效率的等長碼往往要引入一定的失真和錯誤，它不有限時，高傳輸效率的等長碼往往要引入一定的失真和錯誤，它不能象變長編碼那樣可以實現(xiàn)真正的無失真編碼能象變長

10、編碼那樣可以實現(xiàn)真正的無失真編碼信源符號）/(811. 0log)(21bitppSHiii%96)()(SHSH034.096.096.0811.0811.022722520.47154.1 10(0.034)10PNNP4715. 0)(log221)(22SHppiii412431sspS5.4變長信源編碼n幾個碼類的概念(4)n非奇異碼（奇異碼、單義碼）n唯一可譯碼n前綴碼（即時碼、非延長碼、異前置碼）n最佳碼（緊致碼）nKraft定理n唯一可譯碼存在定理n變長編碼定理（香農(nóng)第一定理）5.4變長信源編碼-1(Kraft定理)n引出n碼樹nKraft定理描述nKraft定理證明略5.4變

11、長信源編碼-2(Kraft定理引出)n問題：尋求實時唯一可譯碼n方法：研究實時唯一可譯碼的碼字可分離條件n引入：“碼樹”概念（直觀）n結(jié)論：通過Kraft定理給出實時唯一可譯碼（前綴碼）存在 的條件碼樹變長碼的樹圖表示將變長碼與碼樹建立“一一對應(yīng)”關(guān)系：樹根碼字起點樹枝數(shù)碼的進制數(shù)節(jié)點碼字或碼字的一部分終止節(jié)點碼字節(jié)數(shù)碼長非滿樹變長碼滿樹等長碼 5.4變長信源編碼-3(Kraft定理)n問題：n比較簡單信源，碼樹方法可直接且直觀構(gòu)造前綴碼n較復(fù)雜信源，直接畫碼樹復(fù)雜且困難n解決方法：n為分析起來特別對含有很多符號種類的復(fù)雜信源更方便尋找一種與上述“樹圖”等效的解析式表達式-Kraft不等式不等

12、式。n結(jié)論： nKraft定理給出碼字可分離或前綴碼存在的充要條件5.4變長信源編碼-4(Kraft定理)n定理：長度為li（i=1,2,n）的r （碼字母表長度）進制前綴碼存在的充要條件為：n證明：略n物理意義：n給定信源個數(shù)q和碼字?jǐn)?shù)r，只要允許碼字長度可以足夠長，就總可以滿足Kraft不等式，從而得到前綴碼11inlir5.4變長信源編碼-5(唯一可譯碼定理)nKraft不等式給出的限制也是所有唯一可譯碼都必須滿足的。n定理描述：n任何唯一可譯碼均滿足Kraft不等式。n結(jié)論：n對任何唯一可譯碼均可在不改變碼字長度的條件下得到相應(yīng)的前綴碼5.4變長編碼定理6n問題：n對于已知信源S可用碼

13、符號X進行變長編碼，而且對同一信源編成同一碼符號的前綴碼或惟一可譯碼可有許多種。究竟哪一種最好呢?從高速度傳輸信息的觀點來考慮，當(dāng)然希望選擇由短的碼符號組成的碼字，就是用碼長作為選擇準(zhǔn)則。n引入：碼的平均長度。 離散無記憶平穩(wěn)信源 信源熵率為 碼字母表個數(shù)為r， 則前綴碼平均碼長： ninipppsSsSsSPS11)(SH1( )riiill p a5.4變長編碼定理7n無失真變長信源編碼定理(即香農(nóng)第一定理) ：n 離散無記憶平穩(wěn)信源S，其熵率為 ，并有碼符號X=x1,xr。對信源S進行編碼,總可以找到一種編碼方法，構(gòu)成惟一可譯碼，使信源S中每個信源符號所需的平均碼長滿足: 另一方面,必可

14、以找到前綴碼，使其平均碼長滿足 )(SH( )logHSrl( )log1HSrl5.4變長編碼定理8n定理證明略n物理意義：n又稱無噪信道編碼定理n編碼后的碼符號信源盡可能為等概分布，使每個碼符號平均所含的信息量達到最大n要做到無失真編碼，變換每個信源符號平均所需最少的r元碼元數(shù)就是信源的熵率（以r進制信息量單位測度）n信源的熵率是描述信源每個符號平均所需最少的比特數(shù)n定理說明：n是存在性定理具有理論指導(dǎo)意義n是構(gòu)造性定理設(shè)計出多種具體編碼方法5.4變長編碼定理9編碼效率n變長碼編碼效率：衡量各種編碼方法的優(yōu)略，判斷是否最佳碼。 編碼前平均每個信源符號攜帶的信息量為： 編碼后平均每個信源符號

15、攜帶的最大的信息量為： 定義變長碼編碼效率為：n另一種理解： 最佳碼（極限時）每個信源符號的平均碼長為： 某一方法得到的每個信源符號的平均碼長為： 定義變長碼編碼效率為：loglr( )( )logrHSHSlrl)(SH( )log( )HSrrlHSl( )rHSlll比較：n定長編碼的編碼效率：n變長編碼的編碼效率：注意到： 是指每個信源符號所需的平均碼長，而 也是平均到每個信源符號的碼長，所以它們是一致的，均表示無失真信源編碼的效率。( )( )( )logrlNNHSH SH SRlr( )( )logrHSHSlrlllNn例4：p160例4.4一離散無記憶信源412431sspS

16、其熵為：信源符號）比特/(811.0log4log)(344341SH用二元符號（0，1；r=2）構(gòu)造一個前綴碼：1,021ss此時每個信源符號平均碼長為：1l ()0 .8 1 1HSl編碼效率為：為提高編碼效率，對S的2次擴展信源進行2維聯(lián)合編碼：構(gòu)造一個擴展信源S2的前綴碼：前綴碼 s1s2 9/16 0 s1s23/16 10 s1s2 3/16110 s1s2 1/16111i)(iP此時平均碼長為：2 721 6l此時信源S中每個符號對應(yīng)的平均碼長為：2 72 71 63 22l 編碼效率為：()20 .9 6 1HSl同樣可得：()30 .9 8 5HSl()40 .9 9 1H

17、Sl定長編碼與變長編碼效率比較：例4與例2相比： 同一個信源，當(dāng)要求編碼效率達到96時， 等長碼需要4100萬個信源符號聯(lián)合編碼； 變長碼只需2個符號（二次擴展信源）聯(lián)合編碼；結(jié)論：采用變長編碼，N不需要很大就可以達到相當(dāng)高的編碼效率，而且可以實現(xiàn)無失真編碼。且隨著N的增大，編碼效率越來越接近于1。5.5實用的無失真信源編碼方法舉例1（huffman編碼）nHuffman編碼n編碼方法n特點n應(yīng)用n問題5.5實用的無失真信源編碼方法舉例2（huffman編碼）n編碼方法：例 ： =消息U 概率pi 編碼C U1 1/2 0 0 1 U2 1/4 0 10 1/2 1 U3 1/8 0 110

18、1/4 1 U4 1/8 1 111pis8/18/14/12/14321ssss5.5實用的無失真信源編碼方法舉例3（huffman編碼）編碼規(guī)則： 1)將信源消息U按概率大小排序（由大至?。?2)從最小兩個概率開始編碼，并賦予一定規(guī)則，如下支路小概率為“1”，上支路大概率為“0”。若兩支路概率相等，仍為下支為“1”上支為“0”。 3) 將已編碼兩支路概率合并，重新排隊，編碼。 4) 重復(fù)步驟3）直至合并概率歸一時為止。 5) 從概率歸一端沿樹圖路線逆行至對應(yīng)消息編碼，如U3為“110”。5.5實用的無失真信源編碼方法舉例4（huffman編碼）n例2：5.5實用的無失真信源編碼方法舉例5（huffman編碼）n特點：n編碼不是唯一的n保證了概率大的符號對應(yīng)于短碼，概率小的符號對應(yīng)于長碼，而且短碼得到充分利用n每次縮減信源的最后二個碼字總是最后一位碼元不同，前面各位碼元相同（二元碼情況）n每次縮減信源的最長兩個碼字具有相同碼長這三個特點保證了所得到這三個特點保證了所得到huffman碼一定是最佳碼碼一定是最佳碼5.5實用的無失真信源編碼方法舉例6（huffman編碼）n應(yīng)用應(yīng)用: : n在不同領(lǐng)域得到廣泛應(yīng)用。 n例：International dig