變長(zhǎng)信源編碼定理

7－1變長(zhǎng)信源編碼定理7－2Huffman編碼第七講1對(duì)信源輸出的消息（一個(gè)符號(hào)或者一串符號(hào)）采用不同長(zhǎng)度的碼字表示，則這種編碼方法叫做變長(zhǎng)編碼。一般應(yīng)使出現(xiàn)概率大的消息用較短的碼字表示，出現(xiàn)概率小的消息用較長(zhǎng)的碼字表示，這樣將會(huì)提高編碼效率。

設(shè)信源有q個(gè)符號(hào)，第i個(gè)消息以長(zhǎng)為li的r－元碼表示，當(dāng)信源為無(wú)記憶時(shí)，平均每個(gè)信源號(hào)所需的碼長(zhǎng)為平均碼長(zhǎng)：

7－1變長(zhǎng)信源編碼定理1、基本概念2信源符號(hào)集概率碼A碼B碼C碼Da1a2a3a40.50.250.1250.125001100100110101101110010110111碼A于信源字母集不是一一對(duì)應(yīng)的；碼B雖然與信源字母集一一對(duì)應(yīng)，但仍不是唯一可譯的；碼C和碼D是唯一可譯的。

變長(zhǎng)碼與定長(zhǎng)碼的優(yōu)缺點(diǎn)：同步、譯碼延時(shí)、效率方面。3唯一可譯：對(duì)每個(gè)有限長(zhǎng)的信源序列，相應(yīng)的碼字序列彼此都可無(wú)疑義地區(qū)分開。逗點(diǎn)碼：碼中各碼字都有一特定符號(hào)或符號(hào)組用以指示碼字地起始點(diǎn)。否則為無(wú)逗點(diǎn)碼。上表中碼D是一種逗點(diǎn)碼，碼C是無(wú)逗點(diǎn)碼。字頭（前綴）：對(duì)于碼字為碼字的字頭或前綴。異字頭碼：碼中任何一個(gè)碼字都不是另一個(gè)碼字的字頭。（即時(shí)碼）或稱異前綴碼。碼C是異字頭碼，碼D不是。

異字頭條件保證這類碼的唯一可譯性。并且還有即時(shí)性，收到哪個(gè)碼就可譯碼，無(wú)譯碼延時(shí)。而對(duì)于碼D譯碼時(shí)必須在觀察到下一個(gè)逗點(diǎn)時(shí)才能譯碼。

4各類碼的包含關(guān)系：即時(shí)碼非奇異碼（碼字都不同）所有的碼唯一可譯碼52、Shannon-Fano編碼方法：（異字頭條件碼－樹碼）

對(duì)于r－元樹，最頂部的起始點(diǎn)為樹根，自樹根向下有r個(gè)分支，各個(gè)分支的端點(diǎn)為一級(jí)節(jié)點(diǎn)，二級(jí)節(jié)點(diǎn)最多可能有r2，一般l級(jí)節(jié)點(diǎn)有rl個(gè)。若將從每個(gè)節(jié)點(diǎn)出發(fā)的r個(gè)分支分別標(biāo)以0，1，2，，…，r－1，則每個(gè)l級(jí)節(jié)點(diǎn)需要用l個(gè)r－元數(shù)字表示（也即從樹根到該節(jié)點(diǎn)的路徑）。

根分支C1=0C4=12C5=20C6=21C7=220C8=221C9=222C2=10C3=116若指定某個(gè)l級(jí)節(jié)點(diǎn)表示一個(gè)消息，則該節(jié)點(diǎn)不再向下延伸，其長(zhǎng)度為l，此節(jié)點(diǎn)稱為端節(jié)點(diǎn)。這樣的得到的碼就能保證異字頭條件。如果有K個(gè)消息，就在樹上選擇K個(gè)端節(jié)點(diǎn)，相應(yīng)的r元數(shù)字即為碼字。這樣輸出的碼稱作樹碼，相應(yīng)的圖稱作碼樹，如果碼樹的各分支都延伸到最高級(jí)端點(diǎn)，就稱為滿樹。否則為非滿樹。

我們希望選出的碼集合平均長(zhǎng)度最小。為此希望碼序列的任一符號(hào)承載的信息量最大，我們可使從每個(gè)節(jié)點(diǎn)的r種可能的分支出現(xiàn)的概率近似相等，這將給出一種近似最佳的編碼方法。

7消息概率第一次劃分第二次劃分第三次劃分指定碼組碼長(zhǎng)a1a2a3a4a5a6a7a8a91/31/91/91/91/91/91/271/271/270(1/3)1(1/3)2(1/3)0(1/9)1(1/9)2(1/9)0(1/9)1(1/9)2(1/9)0(1/27)1(1/27)2(1/27)010111220212202212221222223338Kraft不等式：（異字頭條件碼存在的充分必要條件）：長(zhǎng)度為的r元異字頭碼存在的充要條件是：證明：（1）必要性：即時(shí)碼滿足上式。最低層N階的分支數(shù)為第i階節(jié)點(diǎn)作為碼字后，不能伸出分支數(shù)共q個(gè)碼字，總不能伸出的分支數(shù)（2）充分性：不等式意味著存在即時(shí)碼構(gòu)造碼樹：9碼字最后節(jié)點(diǎn)的階的節(jié)點(diǎn)數(shù)碼樹分配長(zhǎng)碼字，階中剩下的節(jié)點(diǎn)依次類推。分配完階后還剩余的節(jié)點(diǎn)為碼樹再分配碼字，階中剩下的節(jié)點(diǎn)10定理：唯一可譯碼必滿足Kraft不等式。

推論：任一唯一可譯碼可用各相應(yīng)碼長(zhǎng)度一樣的異字頭碼代替。

平均碼長(zhǎng)界定定理（----定理5.7）：[此為單符號(hào)情況！]

任一唯一可譯碼滿足

存在有r元唯一可譯碼，其平均長(zhǎng)度11下界證明：利用Jensen不等式12存在上界證明：構(gòu)造即時(shí)碼：右面對(duì)概率求和，可得結(jié)論：左邊整理，并對(duì)i求和：即為kraft不等式，說(shuō)明存在唯一可譯碼；133、香農(nóng)第一定理：（又稱為變長(zhǎng)編碼定理）設(shè)離散無(wú)記憶信源S包含r個(gè)符號(hào)，信源發(fā)出N重符號(hào)序列，則此信源可發(fā)出個(gè)不同的符號(hào)序列消息，其中第j個(gè)符號(hào)序列消息的出現(xiàn)概率為，其信源編碼后所得的二進(jìn)制代碼組長(zhǎng)度為，代碼組的平均長(zhǎng)度為它滿足：14多余度（冗余度）定義為：當(dāng)N趨于無(wú)限大時(shí)，和H(S)之間的關(guān)系為編碼效率：例：書中例5.4157－2Huffman編碼（最佳編碼方法）

通常稱具有最短的代碼組平均長(zhǎng)度或編碼效率接近于1的信源編碼為最佳編碼。香農(nóng)編碼方法對(duì)于某些信源編碼效率高，但對(duì)有些編碼效率低，因此不是最佳的。Huffman提出的一種異字頭編碼方法，其平均長(zhǎng)度最短，是一種最佳編碼。

給定信源，不失一般性可將各消息按概率由小到大進(jìn)行如下排列：，相應(yīng)的概率為。設(shè)二元碼字為，相應(yīng)的長(zhǎng)度為。

16定理：對(duì)于給定信源，存在有最佳唯一可譯二元碼，其最小概率的兩個(gè)碼字CK-1和CK的長(zhǎng)度最長(zhǎng)且相等，它們之間僅最后一位碼元取值不同（一個(gè)為0，一個(gè)為1）。這一定理暗示了一種編碼方法：即對(duì)于給定信源

可對(duì)的碼字的最后一位指定為1和0，然后作一個(gè)輔助集17其中：對(duì)于新的輔助集合，首先將它按的大小重新排序，而后將概率最小的兩個(gè)消息的碼字隨后一位分別賦予1和0。再構(gòu)造新的輔助集，如此重復(fù)，直到最后的輔助集只有兩個(gè)消息位置。這樣由原來(lái)每個(gè)消息在各輔助集中所參與的最后兩個(gè)元素相應(yīng)的碼元，就可以得到各消息所對(duì)應(yīng)的碼字。

定理：對(duì)于輔助集U’為最佳的碼，對(duì)原始消息集U也是最佳的。18例：01100011可以用碼樹；碼不唯一！19實(shí)用無(wú)失真信源編碼方法

MH編碼（傳真）算術(shù)編碼（對(duì)二元序列編碼，一般方法，未知分布）IZ編碼（LZW）壓縮編碼的碼率，就是壓縮每個(gè)符號(hào)平均bit數(shù)；如果未知統(tǒng)計(jì)特性，則還沒有很好辦法；連續(xù)信源必然有失真，依據(jù)限失真信源編碼定理多媒體信源編碼－－壓縮編碼：文本、音頻、圖象、視頻等?！觥?0關(guān)于信源編碼，可參見：周炯槃，丁曉明編著《信源編碼原理》，1996，北京郵電大學(xué)出版社。

對(duì)于相關(guān)信源，條件熵一般遠(yuǎn)小于無(wú)條件熵。通過預(yù)測(cè)和正交變換的編碼方法，去除符號(hào)之間的相關(guān)性，達(dá)到進(jìn)一步壓縮碼率的目的。（集中到少量碼字，用少的表示多的。）■下面對(duì)正交變換略作解釋：21空間：賦予某些數(shù)學(xué)結(jié)構(gòu)的集合線性空間：在集合中引入線性運(yùn)算（加法和數(shù)乘）線性賦范空間：線性空間中引入元素長(zhǎng)度（范數(shù)）內(nèi)積空間：線性空間中引入內(nèi)積的概念線性空間是線性代數(shù)研究的內(nèi)容；線性賦范空間和內(nèi)積空間是泛函分析研究的內(nèi)容。范數(shù)（Norm）：實(shí)數(shù)域上的線性空間X，其中任意元素對(duì)應(yīng)一個(gè)實(shí)數(shù)（函數(shù)），稱為范數(shù)，滿足下列條件：22同一空間，可以引入不同種類的范數(shù)有了距離的概念，就可以引入極限的概念。例如R2空間中可定義范數(shù)：內(nèi)積：（兩向量之間的關(guān)系，數(shù)量積概念的推廣）設(shè)X為實(shí)線性空間，若對(duì)應(yīng)X中兩個(gè)元素x和y都有一個(gè)實(shí)數(shù)，（x,y）即x和y的內(nèi)積，滿足：

（內(nèi)積的幾何意義是兩向量的夾角，也叫標(biāo)量積）23例如：內(nèi)積空間必是賦范空間，只要令元素的正交：只要它們的內(nèi)積為0。內(nèi)積可以表示元素（信號(hào)）的相似程度。一個(gè)元素可以按一個(gè)正交系展開。算子：將一個(gè)空間X的元素變換到另一個(gè)空間Y的映射。泛函：值域是數(shù)域的算子。（定義域是函數(shù)空間）正交變換：保持范數(shù)不變的線性算子（正交算子）。24信號(hào)處理中常用的有限正交變換：N維空間N空間的正交變換正交變換可用矩陣表示，且這個(gè)矩陣是正交的。