信息論與編碼第5章

1、第五章信源編碼0第五章信源編碼（第十講）（2課時）主要內(nèi)容：（1）編碼的定義（2）無失真信源編碼重點：定長編碼定理、變長編碼定理、最佳變長編碼。難點：定長編碼定理、哈夫曼編碼方法。作業(yè)：5。2，5。4，5。6；說明：本堂課推導內(nèi)容較多，枯燥平淡，不易激發(fā)學生興趣，要注意多討論用途。另外，注意，解題方法。多加一些內(nèi)容豐富知識和理解。通信的實質(zhì)是信息的傳輸。而高速度、高質(zhì)量地傳送信息是信息傳輸?shù)幕締栴}。將信源信息通過信道傳送給信宿，怎樣才

2、能做到盡可能不失真而又快速呢？這就需要解決兩個問題：第一，在不失真或允許一定失真的條件下，如何用盡可能少的符號來傳送信源信息；第二，在信道受干擾的情況下，如何增加信號的抗干擾能力，同時又使得信息傳輸率最大。為了解決這兩個問題，就要引入信源編碼和信道編碼。一般來說，提高抗干擾能力（降低失真或錯誤概率）往往是以降低信息傳輸率為代價的；反之，要提高信息傳輸率常常又會使抗干擾能力減弱。二者是有矛盾的。然而在信息論的編碼定理中，已從理論上證明，至

3、少存在某種最佳的編碼或信息處理方法，能夠解決上述矛盾，做到既可靠又有效地傳輸信息。這些結(jié)論對各種通信系統(tǒng)的設計和估價具有重大的理論指導意義。3.1編碼的定義編碼實質(zhì)上是對信源的原始符號按一定的數(shù)學規(guī)則進行的一種變換。討論無失真信源編碼，可以不考慮干擾問題，所以它的數(shù)學描述比較簡單。圖3.1是一個信源編碼器，它的輸入是信源符號，同時存在另一符號，一般來21qsssS??21rxxxX??說，元素xj是適合信道傳輸?shù)?，稱為碼符號（或者碼元）

4、。編碼器的功能就是將信源符號集中的符號si（或者長為N的信源符號序列）變換成由xj(j=123…r)組成的長度為li的一一對應的序列。輸出的碼符號序列稱為碼字，長度li稱為碼字長度或簡稱碼長。可見，編碼就是從信源符號到碼符號的一種映射。若要實現(xiàn)無失真編碼，則這種映射必須是一一對應的，并且是可逆的。碼符號的分類：下圖是一個碼分類圖??????????????????????即時碼（非延長碼）非即時碼唯一可譯碼非唯一可譯碼非奇異碼奇異碼分組

5、碼非分組碼碼第五章信源編碼2的第一個碼符號來選擇應走的第一條路徑，再根據(jù)收到的第二個符號來選擇應走的第二條路徑，直到走到終端節(jié)點為止，就可以根據(jù)終端節(jié)點，立即判斷出所接收的碼字。然后從樹根繼續(xù)下一個碼字的判斷。這樣，就可以將接收到的一串碼符號序列譯成對應的信源符號序列。?克拉夫特（Kraft）不等式定理3.1對于碼符號為X=x1x2…xr的任意唯一可譯碼，其碼字為W1W2…Wq，所對應的碼長為l1l2…lq，則必定滿足克拉夫特不等式11

6、????qilir反之，若碼長滿足上面的不等式，則一定存在具有這樣碼長的即時碼。注意：克拉夫特不等式只是說明唯一可譯碼是否存在，并不能作為唯一可譯碼的判據(jù)（可以排除，不能肯定）。如0，10，010，111滿足克拉夫特不等式，但卻不是唯一可譯碼。例題：設二進制碼樹中X=x1x2x3x4，對應的l1=1l2=2l3=2l4=3，由上述定理，可得18922222322141?????????????ili因此不存在滿足這種碼長的唯一可譯碼?？?/p>

7、以用樹碼進行檢查。?唯一可譯碼的判斷法（變長）：將碼C中所有可能的尾隨后綴組成一個集合F，當且僅當集合F中沒有包含任一碼字，則可判斷此碼C為唯一可譯碼。集合F的構(gòu)成方法：首先，觀察碼C中最短的碼字是否是其它碼字的前綴，若是，將其所有可能的尾隨后綴排列出。而這些尾隨后綴又有可能是某些碼字的前綴，再將這些尾隨后綴產(chǎn)生的新的尾隨后綴列出，然后再觀察這些新的尾隨后綴是否是某些碼字的前綴，再將產(chǎn)生的尾隨后綴列出，依此下去，直到?jīng)]有一個尾隨后綴是碼

8、字的前綴為止。這樣，首先獲得了由最短的碼字能引起的所有尾隨后綴，接著，按照上述步驟將次短碼字、…等等所有碼字可能產(chǎn)生的尾隨后綴全部列出。由此得到由碼C的所有可能的尾隨后綴的集合F。例題：設碼例題：設碼C=0101100111010111101，根據(jù)上述測試方法，判斷是否是唯一可譯碼。，根據(jù)上述測試方法，判斷是否是唯一可譯碼。解：解：1.先看最短的碼字：先看最短的碼字：“0”，它不是其他碼字前綴，所以沒有尾隨后綴。，它不是其他碼字前綴，所

9、以沒有尾隨后綴。2.再觀察碼字再觀察碼字“10”，它是碼字，它是碼字“1011”的前綴，因此有尾隨后綴。的前綴，因此有尾隨后綴。所以，集合所以，集合F=11，00，10，01，其中，其中“10”為碼字，故碼為碼字，故碼C不是唯一可譯碼。不是唯一可譯碼。3.2定長編碼定理前面已經(jīng)說過，所謂信源編碼，就是將信源符號序列變換成另一個序列（碼字）。設信源輸出符號序列長度為L，碼字的長度為KL，編碼的目的，就是要是信源的信息率最小，也就是說，要用