《信息論與編碼(第二版)》第5章

信源編碼

第5章15.1

編碼的定義5.2

無失真信源編碼5.3限失真信源編碼5.4常用信源編碼方法簡介內(nèi)容25.1編碼的定義3信源編碼：無失真信源編碼—第一極限定理離散信源限失真信源編碼—第三極限定理連續(xù)信源信道編碼

第二極限定理信源編碼在不失真或允許一定失真條件下,如何用盡可能少的符號來傳送信源信息,以便提高信息傳輸率信道編碼在信道受干擾的情況下如何增加信號的抗干擾能力,同時又使得信息傳輸率最大。編碼4編碼的定義信源編碼器碼表信源信道信源編碼:將信源輸出符號,經(jīng)信源編碼器后變換成另外的壓縮符號,然后將壓縮后信息經(jīng)信道傳送給信宿信源符號之間存在分布不均勻和相關(guān)性,使得信源存在冗余度,信源編碼的主要任務(wù)就是減少冗余,提高編碼效率。針對信源輸出符號序列的統(tǒng)計特性,尋找一定的方法把信源輸出符號序列變換為最短的碼字序列。XY5編碼的定義編碼定理證明:必存在一種編碼方法,使代碼的平均長度可任意接近但不能低于符號熵;達到這目標的途徑就是使概率與碼長匹配。統(tǒng)計匹配編碼：根據(jù)信源的不同概率分布而選用與之匹配的編碼,以達到在系統(tǒng)中傳信速率最小。6編碼的定義信源符號

信源符號出現(xiàn)概率

碼表碼0碼1碼2碼3碼4a1p(a1)=1/2000011a2p(a2)=1/40111101001a3p(a3)=1/8100000100001a4p(a4)=1/811110110000001等長碼：碼中所有碼字的長度都相同變長碼：碼中的碼字長短不一非奇異碼：信源符號與碼字是一一對應(yīng)的奇異碼：碼1若碼集為{0,1},所得碼字為二元序列,稱為二元碼例如,信源符號X＝{a1,a2,a3,a4},對應(yīng)不同碼字如表7編碼的定義唯一可譯碼：任意有限長的碼元序列,只能被唯一地分割成一個個的碼字。例：{0,10,11}是一種唯一可譯碼。任意一串有限長碼序列,如100111000,只能被分割成10,0,11,10,0,0。任何其他分割法都會產(chǎn)生一些非定義的碼字。奇異碼不是唯一可譯碼非奇異碼唯一可譯碼—碼3非唯一可譯碼—碼28編碼的定義唯一可譯碼

非即時碼：如果接收端收到一個完整的碼字后不能立即譯碼,還需等下一個碼字開始接收后才能判斷是否可以譯碼即時碼：(非延長碼)(異前綴碼)在譯碼時無需參考后續(xù)的碼符號就能立即作出判斷,譯成對應(yīng)的信源符號。任意一個碼字都不是其它碼字的前綴部分在延長碼中,有的碼是唯一可譯的,取決于碼的總體結(jié)構(gòu)9編碼的定義碼非分組碼分組碼奇異碼非奇異碼

非唯一可譯碼唯一可譯碼非即時碼即時碼

(非延長碼)10碼樹表示各碼字的構(gòu)成A0100000000000001111111011111二進制碼樹2000001111122222三進制碼樹樹根—碼字的起點分成r個樹枝—碼的進制數(shù)終端節(jié)點—碼字1101中間節(jié)點—碼字的一部分節(jié)數(shù)—碼長11碼411110001010010001碼400001110101101110樹碼如果有n個信源符號,那么在碼樹上就要選擇n個終端節(jié)點,用相應(yīng)的r元基本符號表示這些碼字。碼001001111100100任一即時碼都可用樹圖法來表示。當碼字長度給定,即時碼不是唯一的。

1211010001001000碼3對應(yīng)的樹如下圖:編碼的定義該碼樹從根到終端節(jié)點所經(jīng)路徑上每一個中間節(jié)點皆為碼字,因此不滿足前綴條件。雖然碼3不是即時碼,但它是唯一可譯碼。13編碼的定義滿樹：每個節(jié)點上都有r個分枝的樹——等長碼非滿樹：變長碼用樹的概念可導(dǎo)出唯一可譯碼存在的充分和必要條件,即各碼字的長度Ki應(yīng)符合Kraft不等式式中:m是進制數(shù)n是信源符號數(shù)14例：設(shè)二進制碼樹中X=(a1,a2,a3,a4),K1=1,K2=2,K3=2,K4=3,應(yīng)用Kraft不等式,得：不存在滿足這種Ki的唯一可譯碼0001101011011中間節(jié)點如果將各碼字長度改成K1=1,K2=2,K3=3,K4=3,則這樣的碼字就存在唯一可譯碼11115編碼的定義必須注意：Kraft不等式只是用來說明唯一可譯碼是否存在,并不能作為唯一可譯碼的判據(jù)。如碼字{0，10，010，111}雖然滿足Kraft不等式,但它不是唯一可譯碼。165.2無失真信源編碼17無失真信源編碼信源編碼器碼表信源信道信源編碼器輸入的消息序列:X=(X1X2…Xl…XL),Xl∈{a1,…an},

輸入的消息總共有nL種可能的組合輸出的碼字為:Y=(Y1Y2…Yk…YK),Yk∈{b1,…bm}

輸出的碼字總共有mK種可能的組合。XYL長序列K長碼字18無失真信源編碼實現(xiàn)無失真的信源編碼,要求:信源符號X1X2…Xl…XL

是一一對應(yīng)的

碼字Y1Y2…Yk…YK能夠無失真或無差錯地從Y恢復(fù)X,也就是能正確地進行反變換或譯碼

;傳送Y時所需要的信息率最小

信息率最小就是找到一種編碼方式使最小195.2.1定長編碼定理信源編碼器碼表信源信道在定長編碼中,K是定值。我們的目的是尋找最小K值。編碼器輸入X=(X1X2…Xl…XL),

Xl∈{a1,…an},

輸入的消息總共有nL種可能的組合輸出的碼字Y=(Y1Y2…Yk…YK),Yk∈{b1,…bm}

輸出的碼字總共有mK種可能的組合。若對信源進行定長編碼,必須滿足:nL≤mK

XYL長序列K長碼字20定長編碼若對信源進行定長編碼,必須滿足:

只有當K長的碼符號序列數(shù)mK大于或等于信源的符號數(shù)nL時,才可能存在定長非奇異碼。例如英文電報有27個符號,n=27,L=1,m=2(二元編碼)每個英文電報符號至少要用5位二元符號編碼21定長編碼實際英文電報符號信源,在考慮了符號出現(xiàn)的概率以及符號之間的依賴性后,平均每個英文電報符號所提供的信息量約等于1.4比特,大大小于5比特。編碼后5個二元符號只攜帶約1.4比特信息量。定長編碼的信息傳輸效率極低。22定長編碼定理定長編碼定理：由L個符號組成的、每個符號的熵為HL(X)的無記憶平穩(wěn)信源符號序列X1…Xl…XL,可用K個符號Y1…Yk…YK(每個符號有m種可能值)進行定長編碼。對任意ε＞0,δ＞0,只要則當L足夠大時,必可使譯碼差錯小于δ;反之,當時,譯碼差錯一定是有限值,而當L足夠大時,譯碼幾乎必定出錯23定長編碼定理⑴當編碼器容許的輸出信息率,也就是當每個信源符號所必須輸出的碼長是時,只要,這種編碼器一定可以做到幾乎無失真,也就是收端的譯碼差錯概率接近于零,條件是所取的符號數(shù)L足夠大。24⑵將定理的條件改寫成其中：左邊：KL長碼字所能攜帶的最大信息，右邊：L長信源序列攜帶的信息量。上述定理表明:只要碼字所能攜帶的信息量大于信源序列輸出的信息量,則可以使傳輸幾乎無失真,當然條件是L足夠大。反之,當時,不可能構(gòu)成無失真的編碼,也就是不可能做一種編碼器,能使收端譯碼時差錯概率趨于零。

時,則為臨界狀態(tài),可能無失真,也可能有失真。

25定長編碼定理為了衡量編碼效果,定義編碼效率：對定長編碼,若要實現(xiàn)幾乎無失真編碼,則信源長度必須滿足:信源序列的自信息方差26例5-2設(shè)離散無記憶信源概率空間信源熵：方差：若取差錯率δ≤10－6,編碼效率為90%,則L應(yīng)滿足在差錯率和編碼效率要求并不十分苛刻的條件下,就需要L=108個信源符號進行聯(lián)合編碼,這顯然是很難實現(xiàn)的。275.2.2變長編碼定理在變長編碼中碼長K是變化的。我們可根據(jù)信源各個符號的統(tǒng)計特性,如概率大的符號用短碼,概率小的用較長的碼,這樣在大量信源符號編成碼后平均每個信源符號所需的輸出符號數(shù)就可以降低,從而提高編碼效率28變長編碼定理單個符號變長編碼定理：若一離散無記憶信源的符號熵為H(X),每個信源符號用m進制碼元進行變長編碼,一定存在一種無失真編碼方法,其碼字平均長度滿足下列不等式:29變長編碼定理離散平穩(wěn)無記憶序列變長編碼定理對于平均符號熵為HL(X)的離散平穩(wěn)無記憶信源,必存在一種無失真編碼方法,使平均信息率滿足不等式其中ε為任意小正數(shù)30ABCDEFGHIJ·––···–·–·–·····–·––········–––KLMNOPQRST–·–·–··–––·–––·––·––·–·–····–UVWXYZ，.··–···–·–––··––·––––··––··––·–·–·–1234567890·––––··–––···––····–·····–····––···–––··––––·–––––Morse電報字符31變長編碼定理用變長編碼來達到相當高的編碼效率,一般所要求的符號長度L可以比定長編碼小得多。編碼效率的下界：32由若對例5-2用變長碼實現(xiàn),要求η＞90%,用二進制,m＝2,log2m=l。得L=433例5-3設(shè)離散無記憶信源概率空間信源熵：若用二元定長編碼(0,1)來構(gòu)造一個即時碼:a1→0,a2→1平均碼長為編碼效率為輸出的信息效率為34再對長度為L=2的信源序列進行變長編碼,其即時