【文章內(nèi)容簡(jiǎn)介】 到充分利用。 第 4章 無(wú)失真信源編碼 第 4章 無(wú)失真信源編碼 最佳編碼 信源最佳化 所謂信源最佳化就是要改造信源，使其熵值最大化，而信源熵)( XH最大化實(shí)質(zhì)上就是尋 求一種最佳的概率分布。 根據(jù)熵函數(shù)的性質(zhì)，在離散信源情況下，當(dāng)各個(gè)符合間彼此獨(dú)立而出現(xiàn)的概率相等時(shí)，信 源熵達(dá)到最大值。因此，一般的熵值最大化應(yīng)當(dāng)包括兩個(gè)步驟： ( 1 ) 符合獨(dú)立化，解除符號(hào)間的相關(guān)性； ( 2 ) 各符號(hào)概率均勻化。 當(dāng)然，在實(shí)際進(jìn)行概率分布的最佳化時(shí)，要研究具體的情況。例如，假若實(shí)際信源各符號(hào)已 經(jīng)相互獨(dú)立，那么，最佳化過(guò)程需要包含概率分布均勻化這一 過(guò)程。另外，一般解除符號(hào)間的相 關(guān)性，通常是在概率均化之前進(jìn)行的。 下面就來(lái)分別研究使熵值最大化的兩個(gè)步驟。先討論符號(hào)獨(dú)立化的問(wèn)題，再討論概率均勻化 的問(wèn)題。 1. 符號(hào)獨(dú)立化 所謂符號(hào)獨(dú)立化，實(shí)際上就是解除信源各符號(hào)之間相關(guān)性。信源符號(hào)之間的相關(guān)性有強(qiáng)有弱， 因此解除的方法也不一樣。 信源符號(hào)之間的相關(guān)性弱，也就是說(shuō)信源符號(hào)中有相鄰的幾個(gè)符號(hào)之間有相關(guān)性，而 相距較遠(yuǎn)的符號(hào)之間的相關(guān)性可以忽略不計(jì)，這種信源也稱為弱記憶信源或弱相關(guān)信源。 對(duì) 于這種信源，我們可以把相關(guān)性較強(qiáng)的幾個(gè)相鄰符號(hào)看成一個(gè)符號(hào)，這樣大符號(hào)之間的 相關(guān)性 就小得多了，可以近似的看成統(tǒng)計(jì)獨(dú)立。 這種做法實(shí)際上就是把原來(lái)的基本信源空間變成多重空間，在這個(gè)多重空間中，各符 號(hào)基 本上是相互獨(dú)立的。而每一組大符號(hào)包含的原始信源符號(hào)越多，大符號(hào)之間相關(guān)性就 越小，效果 也就越好，但實(shí)現(xiàn)起來(lái)也越復(fù)雜，而且延時(shí)也增加了。因此，不能無(wú)限地增加 空間的重?cái)?shù)，通常 根據(jù)實(shí)際需要確定具體重?cái)?shù)。 例如：有一二元信源序列，序列中各符號(hào)間有相關(guān)性，但僅存在于相鄰兩符號(hào)之間。 于是可 以把相鄰兩個(gè)符號(hào)看成一個(gè)新的大符號(hào)。這樣，新序列變成四元序列。 原信源（一重空間）：二元序列?110 0 0 1 0 1 1 0 1 0 新信源（二重空間）： 四元序列?11,10,10,01,01,00 現(xiàn)在分別計(jì)算一下原信源和新信源的熵。 第 4章 無(wú)失真信源編碼 原始信源序列的熵為條件熵，其值為 )|( nm XXHH ? ? ?? ???2121)|(l o g)(n mnmmn xxpxxp )(l og),(),(l og),(21212121nn mmnmnn mmn xpxxpxxpxxp ? ?? ?? ?? ???? )(l og)(),(l og),(212121nnnmnn mmn xpxpxxpxxp ?? ??? ???? 12 HH ??( 比特 / 符號(hào) ) 其中：2H為新的二重空間的信源熵， H 為原始信源條件熵，1H為原始信源如果無(wú)相關(guān)性時(shí) 的無(wú)條件熵。 因此，新信源（即二重空間）的符號(hào)熵2H為 HHH ?? 12( 比特 / 符號(hào) ) 可見(jiàn)，經(jīng)過(guò)這樣處理，新信源每個(gè)符號(hào)（即大符號(hào)）的熵增加了1H比特。新信源的熵增加了， 從而增加了信息的傳輸效率，這種方法也通常稱為延長(zhǎng)法或合并法。 第 4章 無(wú)失真信源編碼 信源符號(hào)之間的相關(guān)性很強(qiáng)，以至于根據(jù)其中一部分符號(hào)就可以推測(cè)出其余的符號(hào)，這 種信源稱為強(qiáng)記憶信源或強(qiáng)相關(guān)信源。對(duì)于這種信源，由于符號(hào)間很強(qiáng)的相關(guān)性，所以，在 傳送時(shí)，那些可以被預(yù)測(cè)的符號(hào)就無(wú)需傳送，即通過(guò)去掉冗余來(lái)節(jié)省傳輸時(shí)間。 一般來(lái)說(shuō)，完全精確地預(yù)測(cè)總是困難的。我們只能根據(jù)信源的統(tǒng)計(jì)特性近似地預(yù)測(cè)。這時(shí)， 我們不必傳輸序列本身。只需傳送序列的實(shí)際值與預(yù)測(cè)值之差（即預(yù)測(cè)誤差），從而可以節(jié)約 信道容量。或者說(shuō)，由于傳送預(yù)測(cè)誤差在很大程度上解除了符號(hào)間的關(guān)聯(lián)，所以提高了熵速率。 這種方法通常稱為預(yù)測(cè)法。 我們舉一個(gè)線性預(yù)測(cè)的例子。例如：設(shè)信源序列為： ??? ,, 11 ttKtKt xxxx ???? 其中，tx是現(xiàn)在所觀察的符號(hào)，它與前若干個(gè)符號(hào)121 , ????? ttKtKt xxxx有關(guān)， K 為任意整 數(shù)。我們可以根據(jù)這 K 個(gè)符號(hào)來(lái)求tx的預(yù)測(cè)值。 ? ?KtKtttt xxxxfx ?????? ,? 121 ? (4 13 ) 第 4章 無(wú)失真信源編碼 現(xiàn)在選擇適當(dāng)?shù)念A(yù)測(cè)函數(shù)f，使預(yù)測(cè)誤差tt xxε ?? ??最小，在線性預(yù)測(cè)的情況下，函數(shù) f是KtKttt xxxx ????? , 121 ?的某種線性組合，即： KtKttt xaxaxax ??? ??? ?2211? (4 14 ) 最簡(jiǎn)單的情況是只考慮相鄰兩符號(hào)間的預(yù)測(cè)，此時(shí)11? ?? tt xax，預(yù)測(cè)誤差為： ε11 ??? tt xax (4 15 ) 若希望預(yù)測(cè)均方誤差? ? 2112 ??? tt xaxε為最小，也就是使預(yù)測(cè)誤差的功率最小，顯然這與 1a取值有關(guān)。當(dāng)11 ?a時(shí)，即： 1? ?? tt xx 則有： 12122 2?? ??? tttt xxxxε (4 16 ) 其中： 212)0(??? tt xxR—— 序列方差； 第 4章 無(wú)失真信源編碼 1)1( ?? tt xxR——tx與1?tx的相關(guān)函數(shù)； )0()1()1(RRρ ?——tx與1?tx的相關(guān)系數(shù)。 這里的)1(R與)1(ρ均表示tx與1?tx之間的相關(guān)程度，若0)1( ?ρ，則表示不相關(guān)；若1)1( ?ρ， 則表示完全相關(guān)。 由式（ 4 16 ）可見(jiàn)，當(dāng)前后兩符號(hào)間完全相關(guān)時(shí)，預(yù)測(cè)誤差 02 ?ε ，因而預(yù)測(cè)誤差信號(hào)的功 率也為 0 ，即不需要傳送，壓縮了信號(hào)功率，節(jié)約了信道容量。預(yù)測(cè)法應(yīng)用的典型例子就是增量 調(diào)制（ DM ）和差分編碼調(diào)制（ DP C M ）。 2. 概率均勻化 符號(hào)間的相關(guān)性解除以后，就可以再設(shè)法使各符號(hào)的概率均勻化，從而進(jìn)一步去除冗余，提 高 傳信率，使其接近信道容量。使傳輸效率接近于 1 ，采用的方法就是編碼，比較著名的最佳編 碼方法有：山農(nóng) ― 范諾編碼 ( S h a n n o n ― F a n o ) 和霍夫曼編碼 ( H u f f m a n ) 。 作為編碼的基礎(chǔ)，需要先了解一些碼的定義。 第 4章 無(wú)失真信源編碼 第 4章 無(wú)失真信源編碼 碼的相關(guān)定義 1. 同價(jià)代碼 如果二元代碼的兩個(gè)碼元長(zhǎng)度相同，稱為同價(jià)代碼；否則，就是非同價(jià)代碼，如：老式的 莫爾斯電報(bào)碼就是非同價(jià)代碼。 2. 等長(zhǎng)代碼 如果碼字序列 W 中各碼字含有的碼元數(shù)相等，則 W 稱為等長(zhǎng)代碼。 3. 單義代碼 如果對(duì)多個(gè)碼字),( 21 n ?任意組合成的序列再進(jìn)行分割，只能唯一地分割成一個(gè)個(gè)碼 字，則稱 W 為單義代碼。例如，碼字集 W = {l ， 0l ， 00 } 是單義代碼，觀察一串較長(zhǎng)的碼序列，如 0 1 1 1 0 0 1 0 0 0 1 ，則其只能被分成 01 ， 1 ， 1 ， 00 ， 1 ， 00 ， 01 ，其他的分割會(huì)造成禁用碼字，如 0 ， 11 ， 10 等。由于單義代碼分割結(jié)果的唯一性，所以碼字間不需要同步碼。 4. 非續(xù)長(zhǎng)代碼 如果碼字集 W 中任一碼字都不是由其它碼字后面添加碼元構(gòu)成的，則 W 就稱為非續(xù)長(zhǎng)代碼， 否則就是續(xù)長(zhǎng)代碼。例如， W = { 0 ， 1 ， 01 ， 0 1 1 } 就不是非續(xù)長(zhǎng)代碼，因?yàn)?01 是 0 的續(xù)長(zhǎng)， 0 1 1 是 01 的續(xù)長(zhǎng)。 非續(xù)長(zhǎng)代碼一定是單義的，但單義代碼則不一定是非續(xù)長(zhǎng)的。例如， W = { 0 ， 0 1 } 是續(xù)長(zhǎng)碼， 但也是單義的，例如，序列 0 0 1 0 0 0 1 0 1 只能分割成 0 ， 01 ， 0 ， 0 ， 01 ， 01 。 第 4章 無(wú)失真信源編碼 5. 單義代碼的存在定理 由于單義代碼在傳送過(guò)程中不需同步碼，因而實(shí)用上盡可能采用單義代碼，存在單義 代碼的充要條件是： ???min iD1≤ 1 (4 17 ) 其中： D 是碼元集 A 中的碼元個(gè)數(shù)，當(dāng)為二元代碼時(shí)， D =2 ； m 是碼字集 W 中碼字個(gè)數(shù)； in是碼字iW的碼元個(gè)數(shù)。 如果滿足單義代碼的充要條件，則存在至少一種單義代碼，否則就不存在任何單義代碼。 第 4章 無(wú)失真信源編碼 例題： 給定}1 0{ ，?A，},{ 4321 wW ?，其中，碼字4321 , w分別用 l ， 2 ， 2 ， 3 個(gè)碼元 構(gòu)成，問(wèn)是否存在單義代碼 ? 解： 由題可知 2?D ，4?m，11 ?n，22 ?n，23 ?n，34 ?n，根據(jù)式 (4 1 7 ) ，有： 18981414121241?????????in i 因而不存在單義代碼。 如果碼字4321 , w分別用 l ， 2 ， 3 ， 3 個(gè)碼元構(gòu)成，則： 18881814121241?????????in i 可見(jiàn)結(jié)果符合式（ 4 17 ），因而存在單義代碼。 6. 非續(xù)長(zhǎng)代碼的構(gòu)成方法 可以用樹(shù)圖的方法來(lái)構(gòu)成非續(xù)長(zhǎng)代碼，構(gòu)造前應(yīng)先考慮式（ 4 17 ）是否成立。舉一個(gè)例子來(lái) 說(shuō)明。 例題： 用二元代碼 0 ， 1 ，碼字集},{ 4321 wW ?，11 ?n，22 ?n，33 ?n，34 ?n構(gòu)成非續(xù)長(zhǎng) 代碼。 解： 可以按照下列步驟構(gòu)成非續(xù)長(zhǎng)代碼，步驟為： ( 1 ) 從頂點(diǎn)開(kāi)始，畫(huà)出兩條分枝，每條分支代表一個(gè)符號(hào)， 0 或 1 ； 例題中1w中有一個(gè)碼元符號(hào)，可以任選一條分枝的終點(diǎn)代表1w，本例選用左邊的分枝， 記為符號(hào) 0 ，則右邊的分枝為符號(hào) 1 ( 2 ) 從沒(méi)有被選用的分枝終點(diǎn)再畫(huà)出兩條分枝，任意選用一條分枝的終點(diǎn)代表碼字； 本例中選用左邊分枝的終點(diǎn)代表2w，記為符號(hào) 0 ，則右邊的分枝為符號(hào) 1 。 ( 3 ) 繼續(xù)下去，直到所有的碼字集 W 都有終點(diǎn)來(lái)代表為止； 本例中選用左邊的分枝的終點(diǎn)代表3w，記為符號(hào) 0 ，而用右邊分枝的終點(diǎn)代表4w，記為符 號(hào) 1 ，這樣 4 個(gè)碼字表示完畢。 第 4章 無(wú)失真信源編碼 ( 4 ) 從頂點(diǎn)到相應(yīng)的碼字，要經(jīng)過(guò)多少條分枝，