《無失真信源編碼》PPT課件

《《無失真信源編碼》PPT課件》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、第五章無失真信源編碼本章需要掌握的內(nèi)容：編碼的目的離散無記憶信源的定長編碼離散無記憶信源的變長編碼定理變長編碼的Huffman編碼方法一.信源編碼第一節(jié)信源編碼和碼的類型信源編碼無失真信源編碼限失真信源編碼1.信源編碼的概念編碼：將攜帶信息的一種符號序列按照一定規(guī)則映射成另一種符號序列的變換。信源編碼:根據(jù)信源的統(tǒng)計特性對信源發(fā)出的信息進行編碼。3.編碼器的數(shù)學(xué)模型信源編碼器信源發(fā)出的消息符號集輸出的碼字集合C（代碼組）信道的基本符號集合其中：Wi稱為碼字，如果碼字由N個碼元組成，則碼長為N。稱為碼元,或碼符號2.信源編碼目的壓縮信源剩余度，提高傳輸消息的有效性，

2、把消息變成適合信道傳輸?shù)男盘枴?.二元碼：3.定長碼：8.非同價碼：信道的基本符號集中碼元個數(shù)為2√每個碼元所占的傳輸時間不完全相同7.同價碼：每個碼元所占的傳輸時間相同√6.奇異碼：碼中碼字至少有兩個相同5.非奇異碼：碼中所有的碼字都不相同√4.變長碼：碼中的碼字長短不一碼中所有碼字的長度都相同二.碼的類型1.分組碼：將信源符號集中的每個信源組符號映射成一個固定的碼字例5-1：設(shè)有二元信道的信源編碼器，其概率空間編碼后的結(jié)果：信源符號Si碼1碼2碼3碼4S100000S201011110S3100010000S4111111110定長碼非奇異碼非奇異碼變長碼變長

3、碼奇異碼9.N次擴展碼（類似N次擴展信源）舉例：10.唯一可譯碼：一個分組碼若對任意有限的整數(shù)N,其N次擴展碼均為非奇異碼，則稱為唯一可譯碼?；蛎總€信源符號序列映射成一個固定的碼字，并且代碼組中每個碼字只能唯一地被譯成所對應(yīng)的信源符號序列。11.即時碼：無需考慮后續(xù)的碼符號即可從碼符號序列中譯出碼字，這樣的唯一可譯碼稱為即時碼，又稱非延時碼。*唯一可譯碼要成為即時碼的條件：其中任一碼字都不是其他碼字的前綴即時碼可用樹圖構(gòu)造：樹根一階節(jié)點二階節(jié)點三階節(jié)點(終端節(jié)點)A00011010111001000111110101100011010001(1)樹圖的最頂部的節(jié)點

4、稱為樹根，樹枝的盡頭稱為節(jié)點(2)每個節(jié)點的分支數(shù)等于碼元數(shù)，且各分支分別對應(yīng)一個固定的碼元，各分支伸出方向所對應(yīng)的碼元是統(tǒng)一的，如圖向左伸出為0，向右伸出為1。(3)各碼字分布在碼樹的終端節(jié)點(即不再分支的節(jié)點)。(4)節(jié)點一旦被分配碼字，后邊的枝便要去掉，否則成為非即時碼。有一離散無記憶信源輸出為N長符號序列，信道基本符號r個，信源輸出符號個數(shù)為q，則存在唯一可譯碼的充要條件為：第二節(jié)離散無記憶信源的定長編碼一.離散無記憶信源的唯一可譯碼存在條件結(jié)論:當碼長為l的碼元序列的個數(shù)不小于信源輸出的N長序列的個數(shù)時,才存在唯一可譯碼.由表明:對于定長唯一可譯碼,每個

5、信源輸出的符號序列經(jīng)編碼后的碼字的碼長至少為Nlogq/logr,如果小于Nlogq/logr,則唯一可譯碼不存在.表示平均每個信源符號至少用logq/logr個碼元來表示例5-2：英文電報有32個符號(26個字母加上6個字符),請問對信源符號進行二進制編碼，要想有唯一可譯碼，碼長至少為多少？解：r=2,q=32,N=1，要想有唯一可譯碼，則二、定長編碼定理進行長度為的定長編碼，對用碼元集設(shè)離散無記憶信源的熵為H(S)，其N次擴展對于只要滿足(正定理)則當N足夠大時，幾乎可實現(xiàn)無失真信源編碼，此時譯碼差錯小于δ。反之，若則當N足夠大時，譯碼錯誤概率趨于1(編碼誤差

6、任意大)（逆定理）信源為例5-3：仍以英文電報為例，當認為各符號是等概分布時的熵為，但是考慮相關(guān)性后英文信源的極限熵為那么對它們進行定長編碼時，各自需要的碼長是多少？哪種情況的信息傳輸率高？解：等概時所需的最少碼符號5個，而考慮相關(guān)性時需要的最少碼符號是2個。后一種的信息傳輸率高三.編碼效率η當允許錯誤概率小于δ時，信源符號序列的長度N：為自信息的方差如果為最佳編碼，則例5-4：設(shè)離散無記憶信源求信源序列的長度。對S采取等長二元編碼，要求編碼效率允許錯誤概率一.變長編碼的概念概念：通過編碼后的代碼組中的每個碼字的碼長不盡相等。要實現(xiàn)無失真信源編碼，變長碼必須是唯一

7、可譯碼第三節(jié)離散無記憶信源的變長編碼提問：信源符號數(shù)和碼字長度之間應(yīng)該滿足什么條件才能構(gòu)成唯一可譯碼呢？二.克拉夫特(Kraft)不等式和麥克米倫(McMillan)不等式設(shè)信源符號集為其分別對應(yīng)碼長為l1,l2,…lq，則即時碼存在的充要條件是：對信源進行編碼，相應(yīng)的碼字集為碼符號集為1.Kraft不等式：2.McMillan不等式在滿足kraft不等式的條件下，唯一可譯碼存在的充要條件是：設(shè)S0為原始碼字的集合。再構(gòu)造一系列集合S1,S2,…Sn。構(gòu)造S1,S2,…Sn的方法：1、首先考察S0中所有的碼字。若碼字Wj是碼字Wi的前綴，即Wi=WjA，則將后綴A

8、列為S1中