信息論與編碼課件第5章

1、信源編碼信源編碼 5.1 編碼的定義5.2 無(wú)失真信源編碼5.3 限失真信源編碼5.4 常用信源編碼方法簡(jiǎn)介23 信源編碼： 無(wú)失真信源編碼第一極限定理 限失真信源編碼第三極限定理 信道編碼 第二極限定理1）信源編碼 在不失真或允許一定失真條件下,如何用盡可能少的符號(hào)來(lái)傳送信源信息,以便2）信道編碼 在信道受干擾的情況下如何增加信號(hào)的,同時(shí)又使得信息傳輸率最大，提高信息提高信息的準(zhǔn)確率的準(zhǔn)確率。4信源編碼器碼表信源信道2、信源編碼: 定義：將信源輸出符號(hào),經(jīng)信源編碼器后變換成另外的壓縮符號(hào),然后將壓縮后信息經(jīng)信道傳送給信宿 -作用：信源符號(hào)之間存在分布不均勻和相關(guān)性, 使得信 源存在冗余度,信

2、源編碼的主要作用就是 減少冗余,提高編碼效率。 -目地：針對(duì)信源輸出符號(hào)序列的統(tǒng)計(jì)特性,尋找 一定的方法把信源輸出符號(hào)序列變換為的 碼字序列。XY5信源符號(hào) 信源符號(hào)出現(xiàn)概率 碼 表（分組碼） 碼0碼1碼2碼3碼4a1p(a1)=1/2000011a2p(a2)=1/40111101001a3p(a3)=1/8100000100001a4p(a4)=1/811110110000001-信源每個(gè)符號(hào)序列xi=x1 x2 xL按照固定的碼表映射成一個(gè)碼字yi叫做分組碼，只有分組碼才有對(duì)應(yīng)的碼表，非分組碼沒(méi)有碼表。-若碼集為0,1,所得碼字為二元序列,稱(chēng)為二元碼例,信源符號(hào)Xa1,a2,a3,a4,

3、L=1，即每個(gè)符號(hào)序列長(zhǎng)度為1，即為單符號(hào)序列，對(duì)應(yīng)不同碼字(分組碼）如表-等長(zhǎng)碼：碼中所有碼字的長(zhǎng)度都相同 碼0，碼1，碼2-變長(zhǎng)碼：碼中的碼字長(zhǎng)短不一 碼3，碼4-非奇異碼：信源符號(hào)與碼字是一一對(duì)應(yīng)的，碼0-奇異碼：反之不是一一對(duì)應(yīng)，碼1 任意有限長(zhǎng)的碼元序列,只能被唯一地分割成一個(gè)個(gè)的碼字。 例1：0,10,11是一種唯一可譯碼。 任意一串有限長(zhǎng)碼序列,如100111000,只能被分割成10,0,11,10,0,0。任何其他分割法都會(huì)產(chǎn)生一些非定義的碼字。 例2：10,0,0,01,00是一種非唯一可譯碼。 任意一串有限長(zhǎng)碼序列,如10000100可被分割成10,0,0,01,00 。也

4、可被分割成10,0,00,10,0 。 奇異碼不是唯一可譯碼8l 非即時(shí)碼： (延長(zhǎng)碼) 如果接收端收到一個(gè)完整的碼字后不能立即譯碼,還需等下一個(gè)碼字開(kāi)始接收后才能判斷是否可以譯碼例：碼3是非即時(shí)碼l 即時(shí)碼： (非延長(zhǎng)碼) (異前綴碼) 在譯碼譯碼時(shí)無(wú)需參考后續(xù)的碼符號(hào)就能立即作出判斷,譯成對(duì)應(yīng)的信源符號(hào)。 任意一個(gè)碼字都不是其它碼字的前綴部分例：碼4是即時(shí)碼 在延長(zhǎng)碼中,有的碼是唯一可譯的,取決于碼的總體結(jié)構(gòu)碼非分組碼 分組碼奇異碼 非奇異碼 非唯一可譯碼 唯一可譯碼非即時(shí)碼 即時(shí)碼 (非延長(zhǎng)碼) 106、碼樹(shù) 表示各碼字的構(gòu)成 A0100000000000001111111011111二

5、進(jìn)制碼樹(shù)2000001111122222三進(jìn)制碼樹(shù)樹(shù)根碼字的起點(diǎn) 分成r個(gè)樹(shù)枝碼的進(jìn)制數(shù)終端節(jié)點(diǎn)碼字1101中間節(jié)點(diǎn)碼字的一部分節(jié)數(shù)碼長(zhǎng)碼4111100010100100017、碼字和碼數(shù)的對(duì)應(yīng)關(guān)系 如果有n個(gè)信源符號(hào),那么在碼樹(shù)上就要選擇n個(gè)終端節(jié)點(diǎn),用相應(yīng)的r元基本符號(hào)表示這些碼字。（碼0）碼001001111100100-任一即時(shí)碼（碼4）都可用樹(shù)圖法來(lái)表示。該碼樹(shù)從根到終端節(jié)點(diǎn)所經(jīng)路徑上每一個(gè)中間節(jié)點(diǎn)都不為碼字,因此滿(mǎn)足異前綴條件。11010001001000 碼3（非即時(shí)碼）對(duì)應(yīng)的樹(shù)如下圖: 該碼樹(shù)從根到終端節(jié)點(diǎn)所經(jīng)路徑上每一個(gè)中間節(jié)點(diǎn)皆為碼字,因此不滿(mǎn)足異前綴條件。 雖然碼3不是即

6、時(shí)碼,但它是唯一可譯碼。 13 滿(mǎn)樹(shù)： 每個(gè)節(jié)點(diǎn)上都有r個(gè)分枝的樹(shù)等長(zhǎng)碼例：二進(jìn)制碼樹(shù)例：二進(jìn)制碼樹(shù) 非滿(mǎn)樹(shù)： 每個(gè)節(jié)點(diǎn)上都不一定有同樣的r個(gè)分枝的樹(shù)-變長(zhǎng)碼例：三進(jìn)制碼樹(shù)例：三進(jìn)制碼樹(shù) 用樹(shù)的概念可導(dǎo)出唯一可譯碼存在的充分和必要條件,即各碼字的長(zhǎng)度Ki應(yīng)符合Kraft不等式m是進(jìn)制數(shù)（分的叉）n是信源符號(hào)數(shù)（終端節(jié)點(diǎn)個(gè)數(shù)）K為各個(gè)碼字的長(zhǎng)度（樹(shù)的節(jié)數(shù)）11niKim 例：設(shè)二進(jìn)制碼樹(shù)中X=(a1 , a2 , a3 , a4), K1=1,K2=2,K3=2,K4=3,應(yīng)用Kraft不等式,得： 這樣的碼字不存在唯一可譯碼 0001101011011中間節(jié)點(diǎn) 如果將各碼字長(zhǎng)度改成K1=1,K

7、2=2,K3=3,K4=3,則18922222322141iKi122222332141iKi這樣的碼字就存在唯一可譯碼 11115 Kraft不等式只是用來(lái)說(shuō)明唯一可譯碼是否存在,并不能作為唯一可譯碼的判斷依據(jù)。即：唯一可譯碼滿(mǎn)足Kraft不等式，但是滿(mǎn)足Kraft不等式的不一定是唯一可譯碼 如碼字0，10，010，111雖然滿(mǎn)足Kraft不等式,但它不是唯一可譯碼。1617信源編碼器碼表信源信道 信源編碼器輸入的消息序列: 序列長(zhǎng)度：序列長(zhǎng)度：X=(X1 X2Xl XL), 每個(gè)消息取值范圍： Xla1,an, 輸入的消息總共有nL種可能的組合 輸出的碼字為: 序列長(zhǎng)度：序列長(zhǎng)度：Y=(Y

8、1 Y2 Yk YKL ) , 每個(gè)碼字的取值范圍： Ykb1,bm 輸出的碼字總共有mKL種可能的組合。XYL長(zhǎng)序列KL長(zhǎng)碼字182、實(shí)現(xiàn)的信源編碼,要求: 能夠無(wú)失真或無(wú)差錯(cuò)地從碼字Y恢復(fù)信息X,也就是能正確地進(jìn)行反變換或譯碼 ; -傳送Y時(shí)所需要的信息率最小 _logLKKmL即就是找到一種編碼方式使得即就是找到一種編碼方式使得傳送Y時(shí)信息率信息率（即碼字長(zhǎng)度滿(mǎn)足的條件）：（即碼字長(zhǎng)度滿(mǎn)足的條件）：最小最小logloglogLLmYKmYKmL為中 每 個(gè) 碼 字 的 信 息 量為 所 有 碼 字的 信 息 量為 平 均 傳 送 一 個(gè) 信 息 所 需 要 的 信 息 量1、在定長(zhǎng)編碼中

9、,每個(gè)碼字長(zhǎng)度相等kL=K是定值。無(wú)失真要求： -信源符號(hào)和碼字一一對(duì)應(yīng)的；正變換一一對(duì)應(yīng) -碼字和信源符號(hào)也是一一對(duì)應(yīng)的； 逆變換也一 一對(duì)應(yīng)2、無(wú)失真的定長(zhǎng)碼碼字長(zhǎng)度滿(mǎn)足的必要條件： -我們的目的是尋找最小K值。 編碼器輸入X=(X1 X2Xl XL), Xla1,an, 輸入的消息總共有nL種可能的組合 輸出的碼字Y=(Y1 Y2 Yk YK ) , Ykb1,bm 輸出的碼字總共有mK種可能的組合。 -若對(duì)信源進(jìn)行定長(zhǎng)無(wú)失真編碼,必須滿(mǎn)足(一對(duì)多）: nLmK 3、無(wú)失真的定長(zhǎng)碼碼字長(zhǎng)度滿(mǎn)足的必要條件和等價(jià)條件：mnLKmnKLloglog或 此時(shí)才可能存在定長(zhǎng)非奇異碼（即無(wú)失真的定長(zhǎng)

10、碼）。 例如英文電報(bào)有27個(gè)符號(hào),n=27,L=1,m=2(二元編碼)527logloglog222mnLK每個(gè)英文電報(bào)符號(hào)至少要用5位二元符號(hào)編碼，才存在定長(zhǎng)奇異碼，即27個(gè)信息符號(hào)需要32個(gè)碼字4、定長(zhǎng)編碼定理： 由L個(gè)符號(hào)組成的、每個(gè)符號(hào)的熵為HL(X)的無(wú)記憶平穩(wěn)信源符號(hào)序列X1XlXL,可用 K個(gè)符號(hào)Y1YkYK(每個(gè)符號(hào)有m種可能值)進(jìn)行定長(zhǎng)編碼。對(duì)任意0,0,只要 則當(dāng)L足夠大時(shí),必可使譯碼差錯(cuò)小于; 反之,當(dāng) 時(shí),譯碼差錯(cuò)一定是有限值,而當(dāng)L足夠大時(shí),譯碼幾乎必定出錯(cuò) log(X)LKKmHLlog(X)2LKKmHL22當(dāng)編碼器容許的輸出信息率,也就是當(dāng)每個(gè)信源符號(hào)所必須輸出

11、的長(zhǎng)度是 時(shí),只要 ,即平均每個(gè)碼字?jǐn)y帶的信息量大于信源符號(hào)熵，這種編碼器一定可以做到幾乎無(wú)失真,也就是收端的譯碼差錯(cuò)概率接近于零,條件是所取的符號(hào)數(shù)L足夠大。_logLKKmL)(_XHKL23將定理的條件改寫(xiě)成其中：左邊：KL長(zhǎng)碼字所能攜帶的最大信息， 右邊：L長(zhǎng)信源序列攜帶的信息量。即所有碼字?jǐn)y帶的信息量大于信源熵log ( )( )LLKmLHXH X24 上述定理表明:平均每個(gè)碼字?jǐn)y帶的信息量大于信源符號(hào)平均每個(gè)碼字?jǐn)y帶的信息量大于信源符號(hào)熵熵 ；或者所有碼字所能攜帶的信息；或者所有碼字所能攜帶的信息量大于信源熵量大于信源熵 ,則可以使傳輸幾則可以使傳輸幾乎無(wú)失真乎無(wú)失真,當(dāng)然條件是

12、當(dāng)然條件是L足夠大。足夠大。反之反之,當(dāng)當(dāng) 時(shí)時(shí),不可能構(gòu)成無(wú)失真的編碼不可能構(gòu)成無(wú)失真的編碼,也就是不可能做一種編碼器也就是不可能做一種編碼器,能使收端譯碼時(shí)能使收端譯碼時(shí)差錯(cuò)概率趨于零。差錯(cuò)概率趨于零。 時(shí)時(shí),則為則為臨界狀態(tài)臨界狀態(tài),可能無(wú)失真可能無(wú)失真,也可能也可能有失真。有失真。)(_XHKL)(_XHKL_( )LK H Xlog( )LLKm LH X5、編碼效率： -為了衡量編碼效果(),0LHXK 上式為信源的平均符號(hào)熵和采用平均符號(hào)碼字碼長(zhǎng)為 的比率，即編碼的效率。0,)()(XHXHLLK-最佳編碼效果6、定長(zhǎng)無(wú)失真編碼序列長(zhǎng)度L： 對(duì)定長(zhǎng)編碼,若要實(shí)現(xiàn)幾乎無(wú)失真編碼,則

13、信源序列長(zhǎng)度必須滿(mǎn)足:22)( XL )()()(22XHxIEXi信源序列的自信息方差差錯(cuò)率 例5-2設(shè)離散無(wú)記憶信源概率空間04. 005. 006. 007. 01 . 01 . 018. 04 . 087654321aaaaaaaaPX 信源熵： 方差：符號(hào)/55. 2)(log)()(bitxpxpXHiii 若取差錯(cuò)率106,編碼效率為90%,則L應(yīng)滿(mǎn)足22281282. 7)()(log)(bitXHppXiii76222108 . 91028. 082. 7)(XL 在差錯(cuò)率和編碼效率要求并不十分苛刻的條件下,就需要L=108個(gè)信源符號(hào)進(jìn)行聯(lián)合編碼,這顯然是很難實(shí)現(xiàn)的。1、變長(zhǎng)

14、編碼 在變長(zhǎng)編碼中碼長(zhǎng)碼長(zhǎng)KL是變化的。 我們可根據(jù)信源各個(gè)符號(hào)的統(tǒng)計(jì)特性,如概率大的符號(hào)用短碼,概率小的用較長(zhǎng)的碼,這樣在大量信源符號(hào)編成碼后平均每個(gè)信源符號(hào)所需的信息量（輸出符號(hào)數(shù)）就可以降低,從而提高編碼效率292、單個(gè)符號(hào)變長(zhǎng)編碼定理： 若一離散無(wú)記憶信源的符號(hào)熵為H(X),每個(gè)信源符號(hào)用m進(jìn)制碼元進(jìn)行變長(zhǎng)編碼,一定存在一種無(wú)失真編碼方法,其平均碼長(zhǎng) 滿(mǎn)足下列不等式:()()1 loglogLH XH XKmm30LK3、離散平穩(wěn)無(wú)記憶序列變長(zhǎng)編碼定理 對(duì)于平均符號(hào)熵為HL(X)的離散平穩(wěn)無(wú)記憶信源,必存在一種無(wú)失真編碼方法,使平均符號(hào)信息率 滿(mǎn)足不等式 X)()(LLHKXHK其中其

15、中為任意小正數(shù)為任意小正數(shù)4、編碼效率的下界：( P92公式推導(dǎo)) LmXHXHKXHLLLlog)()()(32總結(jié)：總結(jié)：用變長(zhǎng)編碼來(lái)達(dá)到相當(dāng)高的編碼效率,一般所要求的符號(hào)長(zhǎng)度L可以比定長(zhǎng)編碼小得多。 由LmXHXHKXHLLLlog)()()( 若對(duì)例5-2用變長(zhǎng)碼實(shí)現(xiàn), 要求90%,用二進(jìn)制,m2,log2m=l。得L= 4L155. 255. 29 . 033 例5-3設(shè)離散無(wú)記憶信源概率空間414321aaPX 信源熵：符號(hào)/811. 0)(log)()(bitxpxpXHiii 若用二元定長(zhǎng)編碼(0,1)來(lái)構(gòu)造一個(gè)即時(shí)碼: a1 0, a2 1 平均碼長(zhǎng)=平均每個(gè)符號(hào)碼長(zhǎng)為：11KK 編碼效率為811. 0)(KXHL 輸出的信息效率為二元碼符號(hào)/811. 0bitR 34 再對(duì)長(zhǎng)度為L(zhǎng) =2的信源序列進(jìn)行變長(zhǎng)編碼,其即時(shí)碼如表 平均碼長(zhǎng)為29331271233(1616161616K 相當(dāng)于K) 編碼效率為961. 0)(2KXHL 輸出的信息效率二元碼符號(hào)/961. 02bitR a