信息論與編碼理論第6章 無失真信源編碼

信息論與編碼理論

第6章無失真信源編碼6.1編碼的基本概念

6.1.1編碼器和譯碼器符號(hào)碼1碼2碼3碼4碼5u1000011u20110110110u3100000001100u411011100011000例對(duì)碼1，如果S=u2u4u1，則X=0111006.1.2碼的分類符號(hào)碼1碼2碼3碼4碼5u1000011u20110110110u3100000001100u411011100011000等長碼：所有碼子長度相同變長碼：碼子的長度不同奇異碼：至少兩個(gè)符號(hào)的編碼相同非奇異碼：所有碼子均不相同非唯一可譯碼：譯碼時(shí)會(huì)產(chǎn)生歧義唯一可譯碼：譯碼時(shí)不會(huì)產(chǎn)生歧義即時(shí)碼：不需要知道下一個(gè)碼子的符號(hào)就能譯碼非即時(shí)碼：需要知道下一個(gè)碼子的符號(hào)才能譯碼（碼1）（碼2、碼3、碼4、碼5）（碼3）（碼1、碼2、碼4、碼5）（碼1、碼4）（碼5）（碼2）（碼1、碼4、碼5）6.1.3N次（階）擴(kuò)展碼將待編碼的符號(hào)進(jìn)行N次擴(kuò)展例如下面的兩個(gè)例子，ACD編碼成為001011/0001111的形式，均為3階擴(kuò)展碼。3次擴(kuò)展符號(hào)共有43=64個(gè)ABCD00011011ABCD0010011113次擴(kuò)展符號(hào)3次擴(kuò)展碼3次擴(kuò)展符號(hào)3次擴(kuò)展碼AAA000……AAB0001DDB11111101AAC00001DDC111111001……DDD1111111116.2“無失真”的本質(zhì)無失真信源編碼：編碼時(shí)沒有信息丟失，譯碼器可以精確恢復(fù)編碼之前的消息。無失真信源編碼又叫“無損壓縮”無失真信源編碼的基本問題是研究如何用最少的比特?cái)?shù)去表示離散信源的熵值，也就是如何找出最佳編碼方案編碼之前的信息量=編碼之后的信息量信源的信息量就是信源熵（信源的平均自信息量）6.3定長碼1次擴(kuò)展碼有n個(gè)信源符號(hào)，r個(gè)碼符號(hào)，碼長l，則要求n≤rlN次擴(kuò)展碼要求nN≤rl兩邊同時(shí)取對(duì)數(shù)得到Nlogn≤llogr，因此還可以引入一個(gè)概念：編碼速率

bit/符號(hào)編碼速率的含義：平均每個(gè)信源符號(hào)用多少個(gè)二進(jìn)制碼符號(hào)表示編碼效率：

=H(U)/R’，其中H(U)是擴(kuò)展之前信源的熵。編碼效率的含義：每個(gè)信源符號(hào)帶有的信息量（即理論上平均每個(gè)信源符號(hào)用多少個(gè)二進(jìn)制碼表示）除以實(shí)際上用的碼符號(hào)的個(gè)數(shù)，即效率例如：S={A,B,C},分別編碼為00,01,10，等概率出現(xiàn)，N=2,SN={AA,…,CC}，對(duì)SN進(jìn)行二元編碼，則r=2，編碼方式如下，則l=4。那么，SN的編碼速率為R=(4log2)/2=2SN的編碼效率為

=H(S)/R=log3/2=0.7925AAABACBABBBCCACBCC0000000100100100010101101000100110106.4變長碼變長碼的幾個(gè)衡量指標(biāo)平均碼長：每個(gè)信源符號(hào)平均需用的碼元數(shù)編碼效率：信息傳輸率：平均每個(gè)碼元攜帶的信息量符號(hào)u1u2u3u4碼子010110111碼集{0,1}碼元數(shù)r=2（二元碼）碼長1233概率0.50.250.1250.125信源熵平均碼長編碼效率信息傳輸率對(duì)二元編碼，R=η，但是兩者的含義并不相同：如果將H(U)理解為平均每個(gè)信源符號(hào)攜帶的信息量，則為信息傳輸率R如果將H(U)理解為理論上的平均碼長，則為編碼效率η6.2.4變長碼的特點(diǎn)能夠提高壓縮效果使信道復(fù)雜化信道要?jiǎng)蛩賯鬏數(shù)亲冮L編碼使得信源不勻速解決方法：增加緩沖器符號(hào)定長碼變長碼u1000u20110u310110u4111116.4.3唯一可譯碼和即時(shí)碼的判別兩個(gè)不等式克拉夫特（Kraft）不等式：對(duì)于碼長分別為l1,l2,…,ln的r元碼，存在即時(shí)碼的充要條件是麥克米倫（McMillan）不等式：對(duì)于碼長分別為l1,l2,…,ln的r元碼，存在唯一可譯碼的充要條件是這說明在碼長選擇的條件上，即時(shí)碼與唯一可譯碼是一致的，唯一可譯碼并不比即時(shí)碼有什么更寬松的條件。碼1：碼2、3：碼4、5：符號(hào)碼1碼2碼3碼4碼5u1000011u20110110110u3100000001100u411011100011000奇異碼：至少兩個(gè)符號(hào)的編碼相同非奇異碼：所有碼子均不相同非唯一可譯碼：譯碼時(shí)會(huì)產(chǎn)生歧義唯一可譯碼：譯碼時(shí)不會(huì)產(chǎn)生歧義即時(shí)碼：不需要知道下一個(gè)碼子的符號(hào)就能譯碼非即時(shí)碼：需要知道下一個(gè)碼子的符號(hào)才能譯碼（碼3）（碼1、碼2、碼4、碼5）（碼1、碼4）（碼5）（碼2）（碼1、碼4、碼5）唯一可譯碼判別準(zhǔn)則命題6-1一種碼是唯一可譯碼的充要條件是S1,S2,…中沒有一個(gè)含有S0中的碼字。S0S1S2S3S4S5S6S7abbcdedebaddebcbcdeabbbaddebbbcde即時(shí)碼的判別準(zhǔn)則【命題6-2】

一個(gè)唯一可譯碼成為即時(shí)碼的充要條件是其中任何一個(gè)碼字都不是其他碼字的前綴。即S1本身就是空集6.4.4無失真信源

編碼定理信源編碼中非常關(guān)心碼的平均碼長無失真信源編碼定理（定理6-4，香農(nóng)第一定理）就給出了平均碼長的取值范圍。無失真變長信源編碼定理（香農(nóng)第一定理）。離散無記憶信源U的N次擴(kuò)展信源UN，其熵為H(UN)，對(duì)該信源UN進(jìn)行r元編碼，總可以找到一種編碼方法，構(gòu)成唯一可譯碼，使信源UN中每個(gè)信源符號(hào)所需的平均碼長滿足：或者其中：是N次擴(kuò)展信源的平均碼長X是一個(gè)離散無記憶信源則X的N次擴(kuò)展信源為：其中例如：則離散無記憶信源X的N次擴(kuò)展信源XN的熵等于信源X的熵的N倍，即H(XN)=NH(X)變長信源編碼定理的含義以r=2，N=1為例，則這說明，總可以找到一種唯一可譯碼，它的平均碼長處在信源熵和信源熵加1之間。而且當(dāng)平均碼長小于信源熵的時(shí)候，這種編碼肯定不是唯一可譯碼。還說明編碼效率

最大是100%該定理并未給出這種唯一可譯碼的構(gòu)造方法。6.5霍夫曼碼

6.5.1二元霍夫曼碼1952年，霍夫曼提出，這是一種最佳碼。二元霍夫曼碼的編碼步驟將信源U的n個(gè)符號(hào)ui按概率p(ui)從大到小排列將兩個(gè)概率最小的符號(hào)合并成一個(gè)新符號(hào)，新符號(hào)的概率為兩個(gè)符號(hào)概率之和，得到只包含n－1個(gè)符號(hào)的縮減信源U1把縮減信源U1的符號(hào)仍按概率從大到小排列，將其中兩個(gè)概率最小的符號(hào)合并成一個(gè)符號(hào)，形成n－2個(gè)符號(hào)的縮減信源U2依次繼續(xù)，直至信源最后只剩下１個(gè)符號(hào)為止將每次合并的兩個(gè)信源符號(hào)分別用0和1碼符號(hào)表示從最后一級(jí)縮減信源開始，向前返回，就得出各信源符號(hào)所對(duì)應(yīng)的碼符號(hào)序列，即得各信源符號(hào)對(duì)應(yīng)的碼字例信源熵：平均碼長：編碼效率：霍夫曼編碼過程例兩種霍夫曼碼信源熵：平均碼長：編碼效率：碼長方差這兩種編碼方式的平均碼長和編碼效率均相同，如何衡量這兩種編碼方式的好壞呢？碼長方差方差小意味著更接近等長碼,更易于傳輸，所以方法(a)要優(yōu)于方法(b)兩個(gè)信號(hào)均值相同，但方差不同。方差可以作為散度，用來度量信號(hào)的分散程度。6.5.2多元霍夫曼碼每次把概率最小的r個(gè)符號(hào)合并成一個(gè)新的符號(hào)，并分別用0,1,…,(r-1)等碼元表示為了使短碼得到充分利用，使平均碼長最短，必須使最后一步的縮減信源有r個(gè)信源符號(hào)因此對(duì)于r元編碼，信源U符號(hào)個(gè)數(shù)n必須滿足：n=(r-1)Q+r

即要求方程n=(r-1)Q+r有解，其中Q為未知數(shù)，是合并的次數(shù)。當(dāng)此方程沒有解時(shí)，可以通過人為增加一些概率為0的符號(hào)來解決。例三元霍夫曼編碼此時(shí)：n=5,m=3，因此n=(m-1)Q+m是有解的，解為Q=1平均碼長：編碼效率：例四元霍夫曼編碼此時(shí)：n=5,m=4，因此n=(m-1)Q+m是無解的，需要增加2個(gè)概率為0的符號(hào)平均碼長：編碼效率：霍夫曼碼的最佳性霍夫曼碼是最佳碼（緊致碼）霍夫曼碼是即時(shí)碼：任一碼子都不是其他碼子的前綴。6.6算術(shù)編碼20世紀(jì)70年代末、80年代初由Rissanen、Pasco和Landon等人發(fā)展起來的編碼方法算術(shù)編碼的思想：用信源符號(hào)對(duì)應(yīng)的概率區(qū)間中的一個(gè)點(diǎn)來表示該信源符號(hào)。但是算術(shù)編碼不是對(duì)信源符號(hào)編碼，而是對(duì)N次擴(kuò)展信源（信源符號(hào)序列）編碼。算術(shù)編碼適合于小消息信源，即n較小的信源。6.6.1算術(shù)編碼基本原理

為什么對(duì)信源序列編碼

（以霍夫曼編碼為例）一次擴(kuò)展二次擴(kuò)展三次擴(kuò)展符號(hào)abaaabbabbaaaaabababaaabbbabbbabbb概率0.70.30.490.210.210.090.3430.1470.1470.1470.0630.0630.0630.027碼子1010100000100110100111000100110101011編碼長度11123322334444平均碼長10.910.90867編碼效率88.1%96.2%96.9%概率區(qū)間6.6.2算術(shù)編碼方法

積累概率的遞推公式信源符號(hào)積累概率定義為信源序列S的積累概率的遞推公式為：F(Sur)=F(S)+p(S)F(ur)p(Sur)=p(S)p(ur)其中F(Sur)：信源序列S添加一個(gè)新的信源符號(hào)ur后所得到的新序列Sur的積累概率p(Sur)：新序列Sur的概率p(S)：信源序列S的概率F(ur)：

信源符號(hào)ur的積累概率p(ur)：信源符號(hào)ur的概率算術(shù)編碼的碼長把信源序列S的編碼取前L位二進(jìn)制小數(shù)，若后面有尾數(shù)就在第L位進(jìn)位如：計(jì)算出的數(shù)值為

0.011011，且L=3，則序列S的二進(jìn)制編碼是100算術(shù)編碼方法）二進(jìn)制算術(shù)編碼的計(jì)算步驟計(jì)算信源符號(hào)的積累概率

設(shè)S＝（空集），F(xiàn)(

)＝0，p(

)＝1計(jì)算序列的積累概率F(Sui)和概率p(Sui)計(jì)算碼長L

將F(S)寫成二進(jìn)制數(shù)的形式，取其小數(shù)點(diǎn)后前L位作為序列S的碼字，若后面有尾數(shù)就在第L位進(jìn)位例

求信源序列S=1010的算術(shù)編碼1.計(jì)算信源符號(hào)的積累概率2.設(shè)S＝（空集），F(xiàn)(

)＝0，p(

)＝13.計(jì)算序列的積累概率F(Sui)和概率p(Sui)4.計(jì)算碼長L

5.將F(S)寫成二進(jìn)制數(shù)的形式，取其小數(shù)點(diǎn)后前L位作為序列S的碼字，若后面有尾數(shù)就在第L位進(jìn)位信源符號(hào)的積累概率：F(0)＝0，F(xiàn)(1)＝0.25序列F(S)p(S)L序列的碼字

01F(

1)＝F(

)＋p(

)F(1)＝0＋1×0.25＝(0.01)2p(

1)＝p(

)p(1)＝1×0.75＝(0.11)21

0.010.11F(10)＝F(1)＋p(1)F(0)＝0.01＋0.75×0＝0.01p(10)＝p(1)p(0)＝0.75×0.25＝0.001110

0.010.0011F(101)＝F(10)＋p(10)F(1)＝0.01＋0.0011×0.01＝0.010011p(101)＝p(10)p(1)＝0.0011×0.01＝0.001001101

0.0100110.001001F(1010)＝F(101)＋p(101)F(0)＝0.010011p(1010)＝p(101)p(0)＝0.000010011010

0.0100110.00001001501010例

求S=11111100的算術(shù)編碼6.6.3算術(shù)譯碼方法（1）求出各個(gè)信源符號(hào)的概率區(qū)間和積累概率，并將碼字轉(zhuǎn)換成十進(jìn)制小數(shù)形式；（2）判斷十進(jìn)制小數(shù)所在符號(hào)區(qū)間，翻譯出1個(gè)符號(hào)u；（3）按照公式（6-13）計(jì)算出一個(gè)新的十進(jìn)制小數(shù)；

（6-13）（4）重復(fù)2、3直至全部信源序列被翻譯完為止。例值所在區(qū)間譯得的符號(hào)計(jì)算過程0.3125[0.25,1]10.08333[0,0.25)00.3333[0.25,1]10.1111[0,0.25)06.7LZW編碼信源統(tǒng)計(jì)特性未知時(shí)的無失真信源編碼LZW編碼歷史1977年，以色列學(xué)者蘭佩爾(A.lempel)和奇費(fèi)(J.ziv)提出一種語法解析碼，簡(jiǎn)稱LZ編碼1978年提出了改進(jìn)算法，LZ77和LZ781984年，韋爾奇(T.A.Welch)將LZ78算法修改成一種實(shí)用的算法，后定名為LZW算法6.7.1LZW基本原理LZW編碼算法的基本思想是建立一個(gè)編碼表(轉(zhuǎn)換表)，韋爾奇稱其為串表，該表將輸入字符串映射成定長碼字輸出，通常碼長設(shè)為12bitLZW編碼算法從一個(gè)空符號(hào)串表開始工作，在產(chǎn)生輸出串的同時(shí)動(dòng)態(tài)更新串表，這樣串表就對(duì)應(yīng)產(chǎn)生壓縮信源的特殊性質(zhì)簡(jiǎn)單說，LZW算法就是將待編碼信源序列進(jìn)行分割，每一部分編碼為一個(gè)長度為12bit的0-1串。字符串碼字6.7.2LZW編碼方法將待編碼非空字符串中的所有單個(gè)字符存入串表中，并給每個(gè)符號(hào)賦一個(gè)碼字值讀入第一個(gè)輸入字符，賦給前綴串變量P讀下一個(gè)輸入字符，賦給擴(kuò)展串變量S如果S為空，輸出P，停止；否則執(zhí)行步驟5如果PS不在串表中，則將P

對(duì)應(yīng)的碼字值輸出，將PS存入串表，并分配一個(gè)碼字值，同時(shí)將擴(kuò)展字符S賦給P

；否則將PS賦給P

；重復(fù)步驟3例

XYXYZYXYXYXXXXXXX字符串XYZ碼子1231.將待編碼非空字符串中的所有單個(gè)字符存入串表中，并給每個(gè)符號(hào)賦一個(gè)碼字值2.讀入第一個(gè)輸入字符，賦給前綴串