信息論基礎(chǔ)：第四章 無失真信源編碼

1、信息傳輸系統(tǒng) 消息消息第二章:信息量第三章信道與信道容量第四章:無失真信源編碼第四章 無失真信源編碼信源編碼的概念 信源編碼的模型等長(zhǎng)編碼變長(zhǎng)編碼香農(nóng)費(fèi)諾艾利斯編碼霍夫曼編碼費(fèi)諾編碼信源編碼的概念 要把信源的信息高速度、高質(zhì)量地通過信道傳送給信宿，一般要通過信源編碼和信道編碼來完成。 研究信源編碼：只考慮有效性，不考慮可靠性信源編碼的概念 信源編碼的作用 例： 信源發(fā)送符號(hào)為 是，否 信道中能夠傳輸?shù)姆?hào)為0，1 符號(hào)變換：用信道能傳輸?shù)姆?hào)來代表信源發(fā)出的消息，使信源適合于信道的傳輸。信源編碼的概念 例：電報(bào)： 1：母親患癌癥，情況危急，請(qǐng)速歸。 2：母病危速歸例： 信源發(fā)送符號(hào)為 是，否

2、方案1： 0，1 方案2： 000，111 有效傳輸(冗余度壓縮)減少信源的剩余度 在不失真的條件下，用盡可能少的符號(hào)來傳送信源信息，提高信息傳送率。信源編碼的概念 一般而言，編碼就是用數(shù)字形式表示消息的過程。編碼實(shí)質(zhì)上是對(duì)要處理的源數(shù)據(jù)按一定的規(guī)則進(jìn)行變換。這些數(shù)學(xué)方法和變換策略的目的都是力圖用盡可能少的符號(hào)或位來表示較多、較長(zhǎng)的符號(hào)及消息。 具體來說，信源編碼就是根據(jù)信源的統(tǒng)計(jì)特性，對(duì)信源發(fā)出的消息進(jìn)行編碼。信源編碼的概念 對(duì)于離散信源，如果信源的統(tǒng)計(jì)特性已知，便可直接進(jìn)行編碼。 對(duì)于連續(xù)信源，應(yīng)根據(jù)采樣定理將連續(xù)信號(hào)離散化。連續(xù)信號(hào)經(jīng)過采樣和量化就變成了離散信號(hào)。將離散信號(hào)按一定規(guī)律與一

3、組代碼相對(duì)應(yīng)就是編碼 。無失真信源編碼的基本概念 根據(jù)能否在解碼后完全準(zhǔn)確的恢復(fù)出原始消息(信息熵是否變換)，將信源編碼分為無失真信源編碼和率失真信源編碼.信源編碼模型設(shè)信源概率空間為對(duì)此信源進(jìn)行二進(jìn)制編碼。 編碼的過程就是建立 之間元素的對(duì)應(yīng)關(guān)系。 和編碼的定義 如果一種編碼方案 如果信源連續(xù)發(fā)送S1S2S3三個(gè)符號(hào)，則該信源編碼的輸出為000110編碼的定義 假定這樣的碼經(jīng)信道傳輸，在接收端收到以“0”“1”為符號(hào)的序列。如000110 如果一種編碼方案 將此序列進(jìn)行譯碼，能唯一地恢復(fù)原來的消息序列。S1S1S1S3信源編碼模型 信源空間為： 編碼符號(hào)表為，用 的符號(hào)對(duì)消息 進(jìn)行編碼。消息

4、 與由 的符號(hào)組成的符號(hào)序列相對(duì)應(yīng)，用公式表示為信源編碼模型叫做對(duì)應(yīng)消息 的碼字。稱為碼元。 稱為 的字長(zhǎng)。 無失真信源編碼的基本概念碼的分類二元碼：碼符號(hào)集為 ，所有碼字都是由0、1組成的二元符號(hào)序列。r進(jìn)制碼元：碼元符號(hào)集為 ， 所有碼字都是由0、1.r-1組成的r進(jìn)制數(shù)字序列。信源符號(hào)碼1碼2S1000S2111S3102S4113碼的分類根據(jù)編碼后碼字的長(zhǎng)度信源符號(hào)碼1碼2碼3碼4S1000001S21101110S310000100S41111111000碼的分類根據(jù)碼字的情況信源符號(hào)碼1碼2碼3碼4S1000001S20101110S310000100S41111111000根據(jù)譯

5、碼恢復(fù)出的序列的情況唯一可譯碼（UDC） 任意有限長(zhǎng)的碼字序列，只能被唯一地分割成一個(gè)個(gè)的碼字，且任一碼字只與唯一一個(gè)信源符號(hào)對(duì)應(yīng)，便稱為唯一可譯碼。又稱單義碼。 非唯一可譯碼碼的分類例：碼的分類例：要保證無失真編碼，必須采用唯一可譯碼。碼的分類信源符號(hào)碼1碼2S10000S20101S31000S41111001110等長(zhǎng)非奇異碼一定是唯一可譯碼。根據(jù)碼字相互關(guān)聯(lián)的情況非續(xù)長(zhǎng)碼 任意一個(gè)碼字都不是另一個(gè)碼字的續(xù)長(zhǎng)，稱為非續(xù)長(zhǎng)碼。換句話說，不能在任意一個(gè)碼字后邊，添上一些碼元構(gòu)成一個(gè)新的碼字。 因此，當(dāng)非續(xù)長(zhǎng)碼碼字的最后一個(gè)碼字出現(xiàn)時(shí)，譯碼器能立即判斷一個(gè)碼字已經(jīng)結(jié)束，可以立即譯碼，又稱即時(shí)碼

6、或立即碼。碼的分類續(xù)長(zhǎng)碼碼的分類信源符號(hào)碼4碼5S101S20101S3011001S41110001結(jié)論： 非續(xù)長(zhǎng)碼一定是單義碼，而單義碼卻不一定是非續(xù)長(zhǎng)碼。 0011101011碼的分類非奇異碼、唯一可譯碼、非續(xù)長(zhǎng)碼的關(guān)系樹圖法樹圖法：所有碼字用碼樹描述出來。碼樹是一棵倒置的樹，最上端是根節(jié)點(diǎn)，從根節(jié)點(diǎn)出發(fā)不斷向下伸出樹枝，分支與碼符號(hào)一一對(duì)應(yīng)。一個(gè)節(jié)點(diǎn)繼續(xù)分支，稱為中間節(jié)點(diǎn)；一個(gè)節(jié)點(diǎn)不再繼續(xù)分支，稱為終端節(jié)點(diǎn)。 將信源符號(hào)對(duì)應(yīng)的節(jié)點(diǎn)用實(shí)心圓表示，從根節(jié)點(diǎn)到這個(gè)節(jié)點(diǎn)經(jīng)過的分支對(duì)應(yīng)的碼符號(hào)序列就是碼字；沒有與信源符號(hào)對(duì)應(yīng)的節(jié)點(diǎn)用空心圓表示對(duì)于碼 和用碼樹表示如下：樹圖法編碼：用樹圖法構(gòu)造非續(xù)

7、長(zhǎng)碼，只要將信源符號(hào)全部對(duì)應(yīng)于終端節(jié)點(diǎn)，而不是中間節(jié)點(diǎn)即可。這樣就可以保證任何一個(gè)碼字都不是其它碼字的前綴 解碼：按照碼符號(hào)的順序，從根節(jié)點(diǎn)依次查詢到終端節(jié)點(diǎn)，就得到對(duì)應(yīng)的信源符號(hào)。再從根節(jié)點(diǎn)對(duì)剩下的碼符號(hào)序列做相同的處理，直到處理完碼符號(hào)序列中所有的碼符號(hào)。非續(xù)長(zhǎng)碼 -樹圖構(gòu)造例：給定編碼符號(hào)表X=0，1，碼字W=W1，W2，W3，W4,字長(zhǎng)分別是n1=1，n2=2 ，n3=n4=3，求非續(xù)長(zhǎng)碼。 非續(xù)長(zhǎng)碼 -樹圖構(gòu)造非續(xù)長(zhǎng)碼 -樹圖構(gòu)造非續(xù)長(zhǎng)碼不是唯一的。全部終端節(jié)點(diǎn)都代表碼字，這種情況叫做用盡的非續(xù)長(zhǎng)碼。單義碼存在定理 設(shè)信源S的符號(hào)集為 ，碼符號(hào)集 ，又設(shè)碼字為 ，其碼長(zhǎng)分別為 。則存

8、在單義碼的必要條件是： 滿足Kraft不等式，即 其中，q是碼字的個(gè)數(shù)，r是編碼符號(hào)表的碼元個(gè)數(shù)，ni 是字長(zhǎng)。若上式成立，就一定能構(gòu)造一個(gè)r進(jìn)制的唯一可譯碼。例：給定編碼符號(hào)表X=0，1，碼字W=W1，W2，W3，W4 = 0，01，10，011,分別由1，2，2，3個(gè)碼元構(gòu)成的碼字單義碼存在定理按照不等式可知，q=4，r=2，n1=1，n2=2 ，n3=2 ，n4=3 ，代入Kraft不等式左邊得單義碼存在定理 如W改為為0，10，110，111， 即n1=1，n2=2 ，n3=3 ，n4=3 如W改為為0，01，110，011， 即n1=1，n2=2 ，n3=3 ，n4=3 單義碼存在定

9、理 碼字不滿足克拉夫特不等式，則肯定不是唯一可譯碼。碼字滿足克拉夫特不等式，并不一定是唯一可譯碼，只是說存在這樣的碼長(zhǎng)條件的唯一可譯碼。 例： 接受為0110 0，10，110，111 0，01，110，011 等長(zhǎng)編碼等長(zhǎng)碼：各個(gè)碼字碼長(zhǎng)都相等的碼 可以編碼成 有效性： 更好 可靠性： 更好，提供糾錯(cuò)功能對(duì)于等長(zhǎng)碼，如果是非奇異碼，那么一定是唯一可譯碼等長(zhǎng)編碼 信源符號(hào)集有2個(gè)符號(hào)，可以用 編碼，碼長(zhǎng)為1； 信源符號(hào)有4個(gè)，碼長(zhǎng)為1就不行了，必須用碼長(zhǎng)為2的等長(zhǎng)碼 設(shè)信源符號(hào)集中有符號(hào)q個(gè)；用二元碼進(jìn)行編碼，碼長(zhǎng)為 ，能夠提供的最多碼字為 個(gè)，因此要滿足等長(zhǎng)碼碼長(zhǎng)不能無限制縮短。 用 準(zhǔn)則編

10、解碼過程非常簡(jiǎn)單，但是編碼效率非常低，有效性很差。主要原因是沒有考慮到信源符號(hào)間的相關(guān)性。等長(zhǎng)編碼 如：英文電報(bào)由26個(gè)字母和6個(gè)標(biāo)點(diǎn)符號(hào)組成，共32個(gè)信源符號(hào)。用2元等長(zhǎng)碼編碼，傳輸一個(gè)字母或標(biāo)點(diǎn)，用5個(gè)2元碼符號(hào)，而5個(gè)2元碼符號(hào)能夠傳輸?shù)淖畲笮畔⒘渴?bit。實(shí)際統(tǒng)計(jì)，每個(gè)英文字符包含信息量1.4bit 等長(zhǎng)編碼N次擴(kuò)展碼：擴(kuò)展前，一個(gè)信源符號(hào)編碼成一個(gè)碼字。N次擴(kuò)展碼，就是把N個(gè)信源符號(hào)組成的序列，變換成N個(gè)碼字組成的序列N次等長(zhǎng)擴(kuò)展碼 如信源符號(hào)集 碼字為2次擴(kuò)展后信源符號(hào)集2次擴(kuò)展碼為N次等長(zhǎng)擴(kuò)展碼 進(jìn)行N次擴(kuò)展，共有 個(gè)信源符號(hào)， 需要 ， 平均到擴(kuò)展前每一個(gè)信源符號(hào)， 這樣看來

11、并沒有提高編碼效率 考慮到相關(guān)性，不用對(duì)所有 個(gè)信源符號(hào)進(jìn)行編碼，有些信源符號(hào)不可能出現(xiàn)，有些出現(xiàn)的概率非常小。碼長(zhǎng)自然減少了N次等長(zhǎng)擴(kuò)展碼 對(duì)信源擴(kuò)展的次數(shù)越多，利用信源的相關(guān)性就越充分，編出來的碼長(zhǎng)平均到每個(gè)信源符號(hào)上平均碼長(zhǎng)就越短，編碼效率就越高 對(duì)信源做無限次擴(kuò)展之后，能夠?qū)⒕幋a效率提高到一個(gè)極限的程度等長(zhǎng)編碼定理 一個(gè)平穩(wěn)離散信源的信息熵為 ，若對(duì)長(zhǎng)為N的信源符號(hào)序列進(jìn)行等長(zhǎng)編碼，N長(zhǎng)符號(hào)對(duì)應(yīng)的碼長(zhǎng)為 ,設(shè)碼符號(hào)集中有r個(gè)碼符號(hào)。 對(duì)于任意的 ，只要滿足 當(dāng)N足夠大時(shí)，可以實(shí)現(xiàn)幾乎無失真的編碼。反之，則不可能實(shí)現(xiàn)無失真的編碼等長(zhǎng)編碼定理 編碼效率：描述編碼的優(yōu)劣編碼后信息率每個(gè)信源符

12、號(hào)的信息熵 定義編碼效率為碼的冗余度(編碼后的新信源的冗余度）等長(zhǎng)編碼例：離散無記憶信源(DMS)用碼元表X=0,1對(duì)U的單符號(hào)進(jìn)行等長(zhǎng)編碼必須用碼長(zhǎng)為3的等長(zhǎng)碼 要無失真的信息傳輸，必須滿足編碼后信息率每個(gè)信源符號(hào)的信息熵 定義編碼效率為碼的冗余度(編碼后的新信源的冗余度）等長(zhǎng)編碼定理 等長(zhǎng)信源編碼的意義：通過不斷的擴(kuò)展信源進(jìn)行等長(zhǎng)編碼，可以不斷提高編碼效率，當(dāng)擴(kuò)展次數(shù)N很大的時(shí)候，能夠達(dá)到最大的編碼效率 編碼后平均每個(gè)信源符號(hào)對(duì)應(yīng)的碼符號(hào)序列所能攜帶的最大的信息量，一定要大于等于信源本身的信息量等長(zhǎng)編碼的缺陷 會(huì)產(chǎn)生一定的誤差：因?yàn)榘岩恍┬「怕实慕M合去掉，沒有進(jìn)行編碼擴(kuò)展維數(shù)太大：要達(dá)到比

13、較高的編碼效率，擴(kuò)展信源的維數(shù)需要很大 例：信源的概率分布 ，要達(dá)到0.96的編碼效率，錯(cuò)誤率控制在 以內(nèi)，信源需要擴(kuò)展4130萬次，擴(kuò)展后信源符號(hào)數(shù)為 個(gè) 變長(zhǎng)編碼-平均碼長(zhǎng) 對(duì)于變長(zhǎng)編碼，不要求每個(gè)碼字的碼長(zhǎng)都很小,但卻要求整個(gè)碼字集合的平均碼長(zhǎng)較小變長(zhǎng)編碼-平均碼長(zhǎng) 顯然，要是平均碼長(zhǎng)短，除了要縮短每一個(gè)碼字的碼長(zhǎng)外，還要合理的分配長(zhǎng)短碼，使概率較大的信源符號(hào)使用較短的碼，概率較小的信源符號(hào)使用較長(zhǎng)的碼對(duì)于某一信源，若有一個(gè)唯一可譯碼，其平均碼長(zhǎng)小于其它任何唯一可譯碼的平均碼長(zhǎng)，則稱此碼為緊致碼，或最佳碼變長(zhǎng)信源編碼定理（香農(nóng)第一定理)平穩(wěn)信源信息熵為 ，對(duì)長(zhǎng)為N的信源符號(hào)序列進(jìn)行編碼，

14、編碼后的平均碼長(zhǎng)為 ，碼符號(hào)有r個(gè)，那么要做到無失真編碼，平均碼長(zhǎng)必須滿足另一方面，一定存在唯一可譯碼，其平均碼長(zhǎng)滿足：即：變長(zhǎng)編碼-變長(zhǎng)信源編碼定理 香農(nóng)第一定理給出了無失真信源編碼的平均碼長(zhǎng)所能達(dá)到的極限值，但是并不是所有的信源編碼方法都能夠達(dá)到這個(gè)極限值。為了衡量各種編碼到達(dá)極限狀況的程度，定義了編碼效率：相應(yīng)的碼的冗余度為：變長(zhǎng)編碼-變長(zhǎng)信源編碼定理【例】信源用0、1構(gòu)成即時(shí)碼等長(zhǎng)編碼變長(zhǎng)編碼-變長(zhǎng)信源編碼定理對(duì)信源進(jìn)行二次擴(kuò)展,并變成編碼變長(zhǎng)編碼-變長(zhǎng)信源編碼定理香農(nóng)第一定理的意義：通過不斷的擴(kuò)展信源進(jìn)行變長(zhǎng)編碼，可以不斷提高編碼效率，當(dāng)擴(kuò)展次數(shù)N很大的時(shí)候，能夠達(dá)到最大的編碼效率

15、編碼后平均每個(gè)信源符號(hào)對(duì)應(yīng)的碼符號(hào)序列所能攜帶的最大的信息量，一定要大于等于信源本身的信息量經(jīng)典編碼方法 霍夫曼（Huffman）編碼香農(nóng)（Shannon）編碼費(fèi)諾（Fano）編碼 霍夫曼（Huffman）編碼 霍夫曼編碼是1952年由霍夫曼提出的一種編碼方法。這種編碼方法的主導(dǎo)思想是根據(jù)源數(shù)據(jù)符號(hào)發(fā)生的概率進(jìn)行編碼。在源數(shù)據(jù)中出現(xiàn)概率越高的符號(hào)，相應(yīng)的碼長(zhǎng)越短；出現(xiàn)概率越小的符號(hào)，其碼長(zhǎng)越長(zhǎng)，從而達(dá)到用盡可能少的碼符號(hào)表示源數(shù)據(jù)。理論表明，在數(shù)據(jù)壓縮中，霍夫曼編碼方法是接近壓縮比上限的一種較好的編碼方法?；舴蚵℉uffman）編碼 霍夫曼編碼及其變種，在壓縮編碼領(lǐng)域中應(yīng)用的非常廣泛。數(shù)字圖

16、像 JPEG運(yùn)動(dòng)圖像 MPEG2、H.261、H.263 通信編碼 Modem ADSL (1)將n個(gè)信源U的各個(gè)符號(hào)ui按概率分布p（ui）以遞減次序排列起來。 霍夫曼（Huffman）編碼 編碼方法 (2)將兩個(gè)概率最小的信源符號(hào)合并成一個(gè)新符號(hào)，新符號(hào)的值為兩個(gè)信源符號(hào)值的和，從而得到只包含n1個(gè)符號(hào)的新信源，稱為U信源的縮減信源U1。 (3)把縮減信源U1的符號(hào)仍按概率以遞減次序排列，然后將其中兩個(gè)概率最小的符號(hào)合并成一個(gè)符號(hào)，這樣又形成了n2個(gè)符號(hào)的縮減信源U2。 霍夫曼（Huffman）編碼 (4)依次繼續(xù)下去，直至信源最后只剩下個(gè)符號(hào)為止。 (5)將每次合并的兩個(gè)信源符號(hào)分別用0

17、和1碼符號(hào)表示。 (6)從最后一級(jí)縮減信源開始，向前返回，就得出各信源符號(hào)所對(duì)應(yīng)的碼符號(hào)序列，即得各信源符號(hào)對(duì)應(yīng)的碼字。 霍夫曼（Huffman）編碼霍夫曼編碼例1編成2元霍夫曼碼，求編碼效率霍夫曼編碼例1霍夫曼編碼例1霍夫曼編碼例1霍夫曼編碼例1消息概率編碼碼長(zhǎng)S10.4002S20.2102S30.2112S40.10103S50.10113例：離散無記憶信源: 對(duì)應(yīng)的霍夫曼編碼如圖所示： 霍夫曼編碼-課堂作業(yè)消息概率編碼碼長(zhǎng)U10.501U20.25102U30.1251103U40.1251113霍夫曼編碼-課堂作業(yè)霍夫曼編碼對(duì)于同一個(gè)信源，霍夫曼編碼的方式有很多種：左分支編0、右分支

18、編1；左分支編1、右分支編0；左右分支混編編出來的平均碼長(zhǎng)都一樣霍夫曼編碼 合并后的新信源符號(hào)與其它信源符號(hào)概率相同時(shí)，合并后的符號(hào)插入到什么位置，編出來的碼也是不一樣的：例1中是將新信源符號(hào)插入到最前面例2將新信源符號(hào)插入到最后面霍夫曼編碼例2編成2元霍夫曼碼，求編碼效率霍夫曼編碼例2霍夫曼編碼例2霍夫曼編碼例2霍夫曼編碼例2消息概率編碼碼長(zhǎng)S10.411S20.2012S30.20003S40.100104S50.100114霍夫曼編碼兩種編碼方式的編碼效率相等。第一種方法只有兩種碼長(zhǎng)：2、3；第二種方法有4種碼長(zhǎng)14第一種方法方差比較小，更接近于等長(zhǎng)碼，更簡(jiǎn)單，更容易實(shí)現(xiàn)霍夫曼編碼擴(kuò)展到

19、r元霍夫曼編碼，只要每次取r個(gè)最小概率的信源符號(hào)即可編成3元霍夫曼碼，求編碼效率霍夫曼編碼例3霍夫曼編碼例3霍夫曼編碼例3消息概率編碼碼長(zhǎng)S10.411S20.221S30.2002S40.1012S50.1022霍夫曼編碼解碼 霍夫曼編碼的所有碼字都在碼樹的終端節(jié)點(diǎn)上，所以霍夫曼碼是即時(shí)碼。 因此霍夫曼碼的解碼可以使用即時(shí)碼的解碼方法。從碼樹的根節(jié)點(diǎn)開始，按碼符號(hào)對(duì)應(yīng)的分支逐步向下，直到找到一個(gè)終端節(jié)點(diǎn)。再從根節(jié)點(diǎn)開始對(duì)剩下的碼符號(hào)序列做相同的處理，直到處理完所有的碼符號(hào)。霍夫曼編碼解碼 解碼100101100011霍夫曼編碼解碼 優(yōu)點(diǎn)就是編碼效率很好，是最佳編碼缺點(diǎn)是容錯(cuò)性能非常差，只要有

20、1位出現(xiàn)了錯(cuò)誤，將可能導(dǎo)致后面的解碼全部錯(cuò)誤或翻譯不出來費(fèi)諾編碼霍夫曼編碼在構(gòu)造碼樹的時(shí)候，是從下層節(jié)點(diǎn)開始，逐級(jí)向上直到根節(jié)點(diǎn)的；而費(fèi)諾編碼正好相反，是由根節(jié)點(diǎn)出發(fā)，直到終端節(jié)點(diǎn)。費(fèi)諾編碼的思想就是使編碼后的碼集盡可能的等概率分布。費(fèi)諾碼不是最佳編碼方法，但是有時(shí)候也能編出最佳碼。費(fèi)諾編碼 將信源符號(hào)按概率大小遞減排列，按照概率之和分為大致相等的r組（2組），分別編以0、1r-1（0、1），再分別對(duì)r個(gè)（2個(gè)）組做相同的處理，直到每個(gè)組只有一個(gè)信源符號(hào)為止。例：求2元費(fèi)諾碼及編碼效率費(fèi)諾編碼費(fèi)諾編碼消息概率編碼碼長(zhǎng)S10.32002S20.22012S30.18102S40.161103S50.0811104S60.0411114課堂練習(xí)離散無記憶