信息論與編碼技術(shù)(Matlab實(shí)現(xiàn))課件ch5

第5章無失真信源編碼5.1編碼的基本概念5.2無失真信源編碼定理5.3實(shí)用的無失真信源編碼方法

.信息論要解決的問題通信的實(shí)質(zhì)是信息的傳輸。而高速度、高質(zhì)量地傳送信息是信息傳輸?shù)幕締栴}。將信源信息通過信道傳送給信宿，怎樣才能做到盡可能不失真而又快速呢？這就需要解決兩個(gè)問題：第一，在不失真或允許一定失真的條件下，如何用盡可能少的符號來傳送信源信息；第二，在信道受干擾的情況下，如何增加信號的抗干擾能力，同時(shí)又使得信息傳輸率最大。為了解決這兩個(gè)問題，就要引入信源編碼和信道編碼。第5章無失真信源編碼信源編碼的目的：提高通信有效性；如何實(shí)現(xiàn)：壓縮信源冗余度采用的一般方法：

壓縮每個(gè)信源符號的平均比特?cái)?shù)或信源的碼率，同樣多的信息用較少的比特?cái)?shù)來傳送，使單位時(shí)間內(nèi)傳送的平均信息量增加，從而提高通信的有效性。

.信源編碼的目的與途徑第5章無失真信源編碼.信道編碼的目的與途徑信道編碼的目的：提高通信可靠性；如何實(shí)現(xiàn)：增加信源冗余度采用的一般方法：增大碼率或帶寬調(diào)制無失真信源編碼定理

——離散信源或數(shù)字信號編碼的基礎(chǔ)先失真信源編碼定理

——連續(xù)信源或模擬信號編碼的基礎(chǔ).信源編碼定理第5章無失真信源編碼.信源編碼家族離散信源編碼連續(xù)信源編碼相關(guān)信源編碼變換編碼降低(壓縮)信源冗余度解除相關(guān)性概率均勻化衡量指標(biāo)編碼信息率編碼效率.離散信源編碼的途徑第5章無失真信源編碼5.1編碼的基本概念5.1.1編碼器的定義 5.1.2即時(shí)碼的碼樹構(gòu)造法 5.1.3唯一可譯碼與克拉夫特不等式 5.1.4碼性能評價(jià)參數(shù) 5.1.1編碼器的定義編碼實(shí)質(zhì)上是對信源的原始符號按一定的數(shù)學(xué)規(guī)則進(jìn)行的一種變換。

輸入：輸出：碼字碼符號/碼元圖5.1.1無失真信源編碼器例5.1.1如果信源輸出的符號序列長度為1，即信源輸出符號集信源概率空間假設(shè)信道為二元信道，即信道的符號集為{0，1}。若將信源X通過該二元信道傳輸，就必須把信源符號xi

變換成由0，1符號組成的碼符號序列，即要進(jìn)行編碼。n=2,4,8時(shí)，信源符號與碼字的一種可能的一一對應(yīng)關(guān)系為5.1.1編碼器的定義例5.1.2為了傳輸一個(gè)由字母A，B，C，D組成的符號集，把每個(gè)字母編碼成二元碼脈沖序列，以“00”代表A，“01”代表B，“10”代表C，“11”代表D，每個(gè)二元碼脈沖寬度為5ms，（1）不同字母等概率出現(xiàn)時(shí)，計(jì)算傳輸?shù)男畔⑺俾?？?）若每個(gè)字母出現(xiàn)的概率分別為1/5，1/4，1/4，3/10，試計(jì)算傳輸?shù)男畔⑺俾省?.1.1編碼器的定義解：（1）不同字母等概率出現(xiàn)時(shí)，符號集的概率空間為：每個(gè)符號含有的平均信息量即熵為比特/符號（字母）解：現(xiàn)在用兩個(gè)二元碼脈沖代表1個(gè)字母，每個(gè)二元碼脈沖寬度為，則每個(gè)字母占用。一秒內(nèi)可以傳輸?shù)淖帜競€(gè)數(shù)：字母/秒5.1.1編碼器的定義則信息傳輸速率：（2）字母出現(xiàn)概率不同時(shí)，據(jù)題意其概率空間為則此時(shí)每個(gè)字母含有的平均信息量為：比特/秒比特/符號同（1），計(jì)算得傳輸?shù)男畔⑺俾蕿榭偨Y(jié)可見，編碼后信源的信息傳輸率與信源的統(tǒng)計(jì)特性有關(guān)。思考：對對于固定的信源，信源編碼的方式對信源的信息傳輸率有什么影響呢？上例中，對字母A，B，C，D進(jìn)行的由兩個(gè)碼符號組成的等長碼。當(dāng)然，也可以把每個(gè)字母編長度不同的碼字。如碼1和碼2的性能怎么評價(jià)呢？誰最適合給定的信源，使編碼后的信息傳輸率最大呢？它們是否滿足無失真編碼的要求呢？比特/秒/秒5.1.1編碼器的定義無失真碼字的性能除了與信源的統(tǒng)計(jì)特性相關(guān)外，主要由碼符號的類型、碼長決定。圖5.1.2是一個(gè)碼分類圖。5.1.1編碼器的定義圖5.1.2碼符號的類型劃分分組碼與非分組碼:將信源消息分成若干組(符號序列)，對每一組按照固定的碼表映射成一個(gè)碼字，這樣的碼叫分組碼，也叫塊碼。只有分組碼有固定的碼表，而非分組碼中不存在碼表。定長碼和變長碼:固定長度的碼，碼中所有碼字的長度都相同，是定長碼。若碼字的長短不一，則稱為變長碼。奇異碼和非奇異碼：若一組碼中所有碼字都不相同，則稱為非奇異碼。非奇異碼中，信源符號和碼字是一一對應(yīng)的。反之，若一組碼中有相同的碼字，則該碼為奇異碼。奇異碼不可能是無失真的碼字。唯一可譯碼：任意有限長的碼元序列，只能被唯一地分割成一個(gè)個(gè)的碼字，便稱為唯一可譯碼。非即時(shí)碼和即時(shí)碼：唯一可譯碼可分為即時(shí)碼和非即時(shí)碼。如果接收端收到一個(gè)完整的碼字后，不能立即譯碼，還需等下一個(gè)碼開始接收后才能判斷是否可以譯碼，這樣的碼叫做非即時(shí)碼。5.1.1編碼器的定義例5.1.3給定信源:對該信源進(jìn)行二元編碼，如表5.1.1所示。表5.1.1二元信源編碼示例

碼字信源碼1碼2碼3碼4碼5碼6x10000110x2011011100101x3100010100001001x411111110000001111碼1—等長碼，唯一可譯碼，即時(shí)碼碼2、碼3、碼4、碼5和碼6均為變長碼。碼2中的每個(gè)碼字都不相同，為非奇異碼。碼字“00”有兩種譯碼方法，即可以譯成信源符號，又可以譯成，因此碼2是非唯一可譯碼。碼3中有相同的碼字，為奇異碼，一定不是唯一可譯碼例5.1.3表5.1.1二元信源編碼示例

碼字信源碼1碼2碼3碼4碼5碼6x10000110x2011011100101x3100010100001001x411111110000001111碼5為即時(shí)碼，一定是唯一可譯碼。碼6為前綴碼，短碼“0”是長碼“01”“001”的前綴，對應(yīng)的后綴分別為“1”，“01”，其中后綴“01”是碼組中單獨(dú)的碼字，因此碼6不是唯一可譯碼。碼符號序列001即可以譯成信源符號x3，又可以譯成x1x2。碼4為唯一可譯碼，也為前綴碼，短碼是長碼的前綴，除去前綴“1”，碼字“10”的后綴“0”、碼字“100”的后綴“00”及碼字“1000”的后綴都不是碼組中的碼字，因此該非即時(shí)碼為唯一可譯碼，這就是前綴后綴判斷法。即時(shí)碼一定是唯一可譯碼。無失真信源編碼要求所編的碼字必須是唯一可譯碼，包含兩層含義，一是要求信源符號與碼字一一對應(yīng)；二是要求碼字的反變換也對應(yīng)唯一的信源符號。否則就會引起譯碼帶來的錯誤和失真。即時(shí)碼作為唯一可譯碼以其較快的譯碼速度得到廣泛的應(yīng)用。那么如何構(gòu)造即時(shí)碼呢？即時(shí)碼的一種簡單構(gòu)造方法是碼樹法。對給定碼字的全體集合來說，可以用碼樹來描述它。如圖5.1.3所示。5.1.2即時(shí)碼的碼樹構(gòu)造法即時(shí)碼的一種簡單構(gòu)造方法是碼樹法。所謂樹，就是既有根、枝，又有節(jié)點(diǎn)，如圖5.1.3所示，最上端A為根節(jié)點(diǎn)，A、B、C、D、E皆為中間節(jié)點(diǎn)，E為終端節(jié)點(diǎn)。對給定碼字的全體集合5.1.2即時(shí)碼的碼樹構(gòu)造法圖5.1.3碼樹結(jié)構(gòu)圖對一個(gè)給定的碼，畫出其對應(yīng)的碼樹，如果有中間節(jié)點(diǎn)安排了碼字，則該碼一定不是即時(shí)碼。這是最簡單的即時(shí)碼判斷方法。對一個(gè)給定的碼，畫出其對應(yīng)的樹，如果有中間節(jié)點(diǎn)安排了碼字，則該碼一定不是即時(shí)碼。例5.1.3中給出的碼組，碼1、碼2和碼5對應(yīng)的碼樹圖分別如圖5.1.4(a)(b)(c)所示。可見，碼1和碼5的各碼字位于樹的終端節(jié)點(diǎn)，滿足即時(shí)碼的條件。(a)碼1(b)碼2(c)碼5圖5.1.4碼1、碼2和碼5對應(yīng)的碼樹5.1.2即時(shí)碼的碼樹構(gòu)造法用碼樹的概念可以判斷、構(gòu)造即時(shí)碼，還可以導(dǎo)出唯一可譯碼存在的充分和必要條件。即各碼字的長度ki應(yīng)符合克拉夫特（Kraft）不等式。定理：對于碼符號為的任意唯一可譯碼，其碼字為，所對應(yīng)的碼長為，則必定滿足Kraft不等式(5.1.1)反之，若碼長滿足上面的不等式，則一定存在具有這樣碼長的唯一可譯碼。式中m為碼符號進(jìn)制數(shù)。Kraft不等式只是說明唯一可譯碼是否存在，并不能作為唯一可譯碼的判據(jù)，但可以作為某碼組不是唯一可譯碼的判據(jù)。如{0,10,11,110}不滿足Kraft不等式，則肯定不是唯一可譯碼；{0，10，010，111}滿足Kraft不等式，但卻不是唯一可譯碼5.1.3唯一可譯碼與克拉夫特不等式例5.1.4設(shè)二進(jìn)制碼樹中X∈｛x1，x2，x3,x4｝，k1=1，k2=2，k3=2，k4=3，應(yīng)用上述判斷定理，可得因此，不存在滿足這種ki的唯一可譯碼,{0,10,11,110}的碼長分布如題，肯定不是唯一可譯碼。{0，10，010，111}滿足克拉夫特不等式，但卻不是唯一可譯碼。因?yàn)椋喝绻盏酱a字“010”，則存在兩種可能的譯碼方法：即可譯為“010”對應(yīng)的信源符號；又可譯為“0”“10”對應(yīng)的信源符號。{0，10，110，111}是滿足該不等式的唯一可譯碼。.5.1.3唯一可譯碼與克拉夫特不等式5.1.3唯一可譯碼與克拉夫特不等式唯一可譯碼的判斷方法：根據(jù)Kraft不等式，結(jié)合前綴后綴法即可以判斷某碼組是否是唯一可譯碼。(1)等長碼為唯一可譯碼的判斷法。等長碼若為非奇異碼，一定是唯一可譯碼。(2)變長碼為唯一可譯碼的判斷法。首先，該變長碼的各碼字長度若不滿足Kraft不等式，則一定不是唯一可譯碼；如果變長碼的各碼字長度滿足Kraft不等式，則進(jìn)一步按照前綴后綴法判斷。將碼C中所有可能的尾隨后綴組成一個(gè)集合F，當(dāng)且僅當(dāng)集合F中沒有包含任一碼字，則可判斷此碼C為唯一可譯碼。練習(xí)：{0，10，010，111}不是唯一可譯碼。{0，10，110，111}是唯一可譯碼。5.1.4碼性能評價(jià)參數(shù)無失真碼字的性能除了與信源的統(tǒng)計(jì)特性相關(guān)外，主要由所編碼字的特性決定。無失真編碼要求所編的碼字是唯一可譯碼，碼組中的各碼字的碼長要滿足Kraft不等式。無失真編碼器的整體性能需要用1.平均碼長2.編碼信息率

3.壓縮比

4.編碼效率

5.信道剩余度評價(jià)。5.1.4碼性能評價(jià)參數(shù)1.平均碼長如果單符號信源概率空間為

對每個(gè)信源符號進(jìn)行無失真信源編碼，對應(yīng)碼字為，所對應(yīng)的碼長為。根據(jù)無失真信源編碼的要求中信源符號與碼字的一一映射關(guān)系，碼字概率空間和碼長概率空間為各碼字長度的數(shù)學(xué)期望，即平均碼長為碼符號/信源符號(5.1.3)上述信源編碼的對象是對單符號信源，因此式(5.1.3)的平均碼長又叫做單符號碼長。5.1.4碼性能評價(jià)參數(shù)1.平均碼長當(dāng)然，大多數(shù)的情況下，可以對單符號信源的N次擴(kuò)展信源進(jìn)行編碼，所編的碼字叫做N次展碼。假設(shè)N次擴(kuò)展信源的概率空間為對每個(gè)信源序列進(jìn)行無失真信源編碼，所對應(yīng)的碼長為

碼符號/信源序列(5.1.5)稱為序列碼長，對應(yīng)的單符號碼長為碼符號/信源符號(5.1.6)單符號碼長的物理意義就是平均一個(gè)信源符號對應(yīng)個(gè)碼符號5.1.4碼性能評價(jià)參數(shù)2.編碼信息率單符號信源X的信源熵就是信源的信息傳輸率。若所編碼字的單符號碼長為，則單符號信源的熵等于個(gè)碼符號的熵。當(dāng)信源給定時(shí)，信源的熵確定，而編碼后每個(gè)信源符號平均用個(gè)碼符號來替換。那么，每個(gè)碼符號的平均信息量，即編碼信息率為

bit/碼符號(5.1.7)若傳輸一個(gè)碼符號平均需要t秒鐘，則編碼后信源每秒鐘傳輸?shù)男畔⒘?，即編碼后信源的信息傳輸速率為

bit/s(5.1.8)式(5.1.7)和式(5.1.8)給出了單符號信源編碼的信息傳輸率和信息傳輸速率；5.1.4碼性能評價(jià)參數(shù)3.壓縮比壓縮比是衡量數(shù)據(jù)壓縮程度的指標(biāo)之一。目前常用的壓縮比定義為

(5.1.12)其中LB為源代碼長度，Ld為壓縮后代碼長度，Pr為壓縮比。壓縮比的物理意義是被壓縮掉的數(shù)據(jù)占據(jù)源數(shù)據(jù)的百分比。當(dāng)壓縮比Pr接近100%時(shí)壓縮效果最理想。5.1.4碼性能評價(jià)參數(shù)4.編碼效率與信源信息傳輸效率的定義相類似，編碼后信道中傳輸?shù)氖谴a符號，因?yàn)椴荒芡耆@得碼符號的概率分布，只能按照每個(gè)碼符號等概分布進(jìn)行估算。也就是說，所設(shè)計(jì)的信道要具有傳輸碼符號等概分布時(shí)的最大熵的傳輸能力或手段。定義編碼效率

(5.1.14)對二元碼，m=2帶入式(5.1.14)，可得

(5.1.15)或5.1.4碼性能評價(jià)參數(shù)5.信道剩余度（冗余度）信道剩余度表示信道未被利用的程度，所以是冗余的，信道冗余度定義為

(5.1.16)可見，對于二元信源編碼，編碼效率與編碼信息率大小相同，只是單位不同。平均碼長越短，編碼效率和編碼信息率越高。當(dāng)平均碼長等于信源熵時(shí)，編碼效率達(dá)到上限100%，編碼信息率達(dá)到二元對稱信道的信道容量1，消除信源冗余度實(shí)現(xiàn)了信源與信道的匹配。由上述分析可見，最短的平均碼長與信源的統(tǒng)計(jì)特性有關(guān)，如果某種信源編碼方法的平均碼長最短，可稱之為最佳無失真信源編碼。一般情況下，如何使無失真信源編碼的平均碼長盡可能接近信源熵并可實(shí)現(xiàn)是被關(guān)心的問題，在解決該問題的過程中需要遵循的是無失真信源編碼定理。5.2無失真信源編碼定理 5.2.1定長編碼定理 5.2.2變長編碼定理(香農(nóng)第一定理) 5.2.3最佳變長編碼及MATLAB實(shí)現(xiàn) 5.2無失真信源編碼定理

由5.1節(jié)可知，無失真信源編碼要求所編碼字必須是唯一可譯碼，這樣才能保證無失真或無差錯地從Y恢復(fù)X，也就是能正確地進(jìn)行譯碼；如果進(jìn)一步考慮編碼前后的信息傳輸率變化，無失真信源編碼的編碼信息率的最大值必定不能小于信源的信息率，同時(shí)希望傳送Y時(shí)所需要的信息率最小。

無失真信源編碼的編碼信息率的最大值必定不能小于信源的信息率的數(shù)學(xué)描述為

可寫成即

—該式給出了無失真編碼平均碼長的下界5.2.1定長編碼定理

信源編碼的目的，就是要是信源的信息率最小，也就是說，要用最少的符號來代表信源。在定長編碼中，對每一個(gè)信源序列，KN都是定值，定長編碼定理：由N個(gè)符號組成的、每個(gè)符號熵為的無記憶平穩(wěn)信源符號序列，可用

KN個(gè)符號（每個(gè)符號有m種可能值）進(jìn)行定長編碼。對任意，只要

(5.2.4)則當(dāng)N足夠大時(shí)，必可使譯碼差錯小于；即可實(shí)現(xiàn)幾乎無失真編碼，反之，當(dāng)

(5.2.5)時(shí)，譯碼差錯一定是有限值（即不可能實(shí)現(xiàn)無失真編碼），當(dāng)N足夠大時(shí)，譯碼幾乎必定出錯（譯碼錯誤概率近似等于1）。這就是單符號信源無失真定長編碼定理。5.2.1定長編碼定理 定長編碼定理是在平穩(wěn)無記憶信源的條件下論證的，但它同樣適用于平穩(wěn)有記憶信源，只是要求有記憶信源的極限熵存在即可。對于平穩(wěn)有記憶信源，定理中的兩個(gè)不等式中的應(yīng)改為極限熵。對二元編碼，m=2，式(5.2.5)成為：

(5.2.6)可見定理給出了等長編碼時(shí)平均每個(gè)信源符號所需的二元碼符號的理論極限，這個(gè)極限值由信源熵決定。式(5.2.4)可改寫為

(5.2.7)由等長編碼定理可知，只要碼字傳輸?shù)男畔⒘看笥谛旁葱蛄袛y帶的信息量，總可以實(shí)現(xiàn)幾乎無失真的編碼。條件是所取的符號數(shù)N足夠大。5.2.1定長編碼定理 例如某單符號信源有8種等概率符號，信源熵最大值為

bit/符號即該信源符號肯定可以用K=3個(gè)二元碼符號進(jìn)行無失真編碼。但是，當(dāng)信源符號概率不相等時(shí)，若

，則信源熵為

bit/符號(5.2.8)小于3bit，用K=2.55個(gè)二元碼符號表示信源時(shí)，只有種可能碼字，信源的8個(gè)符號中還有部分符號沒有對應(yīng)的碼字，就只能用其它碼字代替，因而引起差錯。差錯發(fā)生的可能性取決于這些沒有對應(yīng)碼字的信源符號出現(xiàn)的概率。當(dāng)N足夠大時(shí)，有些符號序列發(fā)生的概率變得很小，使得差錯概率達(dá)到足夠小。5.2.1定長編碼定理 無失真信源編碼定理從理論上闡明了編碼效率接近于1的理想編碼器的存在性，它使輸出符號的信息率與信源熵之比接近于1，但要在實(shí)際中實(shí)現(xiàn)，則要求信源符號序列的N非常大，進(jìn)行統(tǒng)一編碼才行，這往往是不現(xiàn)實(shí)的。例5.2.1設(shè)離散無記憶信源概率空間為

信源熵為5.2.1定長編碼定理 例5.2.1設(shè)離散無記憶信源概率空間為

自信息方差為5.2.1定長編碼定理 例5.2.1對信源符號采用定長二元編碼，要求編碼效率，無記憶信源有，因此可以得到。如果要求譯碼錯誤概率，則由此可見，在對編碼效率和譯碼錯誤概率的要求不是十分苛刻的情況下，就需要個(gè)信源符號一起進(jìn)行編碼，這對存儲和處理技術(shù)的要求太高，目前還無法實(shí)現(xiàn)。5.2.1定長編碼定理 例5.2.1如果用3比特來對上述信源的8個(gè)符號進(jìn)行定長二元編碼，N=1，此時(shí)可實(shí)現(xiàn)譯碼無差錯，但編碼效率只有2.55/3=85%。因此，一般說來，當(dāng)信源序列的長度N有限時(shí)，高傳輸效率的定長碼往往要引入一定的失真和譯碼錯誤。解決的辦法是可以采用變長編碼。

5.2.2變長編碼定理(香農(nóng)第一定理)

在變長編碼中，碼長是變化的。對同一信源，其即時(shí)碼或唯一可譯碼可以有許多種。究竟哪一種好呢？從高速傳輸信息的觀點(diǎn)來考慮，當(dāng)然希望選擇由短的碼符號組成的碼字，就是用平均碼長來作為選擇準(zhǔn)則。單個(gè)符號變長編碼定理若一離散無記憶信源的符號熵為H(X)，每個(gè)信源符號用m進(jìn)制碼元進(jìn)行變長編碼，一定存在一種無失真編碼方法，其碼字平均長度滿足下面的不等式

(5.2.14)5.2.2變長編碼定理(香農(nóng)第一定理)

2.離散平穩(wěn)無記憶序列變長編碼定理（香農(nóng)第一定理）對于平均符號熵為HN(X)的離散平穩(wěn)無記憶信源，必存在一種無失真信源編碼方法，使平均碼長滿足下面的不等式(5.2.14)上面的兩個(gè)定理實(shí)際上是一樣的，可以由第一個(gè)推導(dǎo)出第二個(gè)。對于二元碼，可推出

(5.2.19)

單符號變長編碼定理與符號序列變長編碼定理的關(guān)系單符號變長編碼定理符號序列變長編碼定理5.2.2變長編碼定理(香農(nóng)第一定理)

5.2.2變長編碼定理(香農(nóng)第一定理)

香農(nóng)第一編碼定理給出了碼字的平均長度的下界和上界。但并不是說大于這上界不能構(gòu)成唯一可譯碼，而是因?yàn)榫幋a時(shí)總是希望盡可能短。定理說明當(dāng)平均碼長小于上界時(shí)，唯一可譯碼也存在。也就是說，定理給出的是最佳碼的最短平均碼長，并指出這個(gè)最短的平均碼長與信源熵是有關(guān)的。變長編碼的編碼效率為

(5.2.20)或者例5.2.2設(shè)離散無記憶信源的概率空間為其信源熵為若用二元定長編碼(0，1)來構(gòu)造一個(gè)即時(shí)碼：x1→0,x2→1。這時(shí)平均碼長編碼效率為輸出的信息率為

R=0.811比特/二元碼符號5.2.2變長編碼定理(香農(nóng)第一定理)

如果對這一信源采用定長二元碼編碼，要求編碼效率達(dá)到96%，允許譯碼錯誤概率，則可以算出

(1)自信息方差為

(2)(3)需要的信源序列長度為可以看出，使用定長編碼時(shí)，為了使編碼效率較高(96%），需要對非常長的信源序列進(jìn)行編碼，且總存在譯碼差錯。而使用變長編碼，使編碼效率達(dá)到96%，只要N=2就行了，且可以實(shí)現(xiàn)無失真編碼。當(dāng)然，變長編碼的譯碼相對來說要復(fù)雜一些。5.2.2變長編碼定理(香農(nóng)第一定理)

如何實(shí)現(xiàn)最佳編碼——香農(nóng)第一定理香農(nóng)第一定理給出了信源熵與編碼后的平均碼長之間的關(guān)系，同時(shí)也指出可以通過編碼使平均碼長達(dá)到極限值，因此，香農(nóng)第一定理是一個(gè)極限定理。但定理中并沒有告知如何來構(gòu)造這種碼。最佳碼每個(gè)碼字長度ki滿足：(5.2.21)

5.2.3最佳變長編碼及MATLAB實(shí)現(xiàn)1香農(nóng)編碼方法因?yàn)槠骄a長是各個(gè)碼字長度的概率平均，可以想象，應(yīng)該使出現(xiàn)概率大的信源符號編碼后碼長盡量短一些，出現(xiàn)概率小的信源符號編碼后碼長長一些，保證平均碼長較短。三種編碼方法的出發(fā)點(diǎn)都是如此。這也是變長編碼的思想。香農(nóng)編碼嚴(yán)格意義上來說不是最佳碼。香農(nóng)編碼是采用信源符號的累計(jì)概率分布函數(shù)來分配碼字的。5.2.3最佳變長編碼及MATLAB實(shí)現(xiàn)1香農(nóng)編碼方法(1)將信源消息符號按其出現(xiàn)的概率大小依次排列(2)確定滿足下列不等式的整數(shù)碼長Ki

：

(3)為了編成唯一可譯碼，計(jì)算第i個(gè)消息的累加概率

(4)將累加概率Pi變換成二進(jìn)制數(shù)。(5)取Pi二進(jìn)數(shù)的小數(shù)點(diǎn)后ki位即為該消息符號的二進(jìn)制碼字。5.2.3最佳變長編碼及MATLAB實(shí)現(xiàn)1香農(nóng)編碼方法例5.2.3設(shè)信源共有7個(gè)符號組成，其概率和香農(nóng)編碼過程如表5.2.2所示。5.2.3最佳變長編碼及MATLAB實(shí)現(xiàn)表5.2.2香農(nóng)編碼過程信源符號xi符號概率p(xi)累加概率Pi碼字長度ki碼字x10.2002.343000x20.190.22.413001x30.180.392.483011x40.170.572.563100x50.150.742.743101x60.100.893.3441110x70.010.996.66711111101香農(nóng)編碼方法以i=4為例，累加概率變成二進(jìn)制數(shù)，為0.1001…，，取4位，得第4個(gè)信源符號所編碼字為：100。5.2.3最佳變長編碼及MATLAB實(shí)現(xiàn)1香農(nóng)編碼方法該香農(nóng)編碼的平均碼長為：平均信息傳輸率為編碼效率壓縮之前7個(gè)符號，平均每個(gè)符號需要3個(gè)比特表示，經(jīng)香農(nóng)編碼壓縮之后的平均碼字長度為3.14，因此壓縮比為香農(nóng)編碼的效率不高，實(shí)用意義不大，但對其它編碼方法有很好的理論指導(dǎo)意義5.2.3最佳變長編碼及MATLAB實(shí)現(xiàn)2費(fèi)諾編碼方法費(fèi)諾編碼也不是最佳編碼方法，但有時(shí)可以得到最佳編碼。(1)將信源消息符號按其出現(xiàn)的概率大小依次排列：

(2)將依次排列的信源符號按概率值分為兩大組，使兩個(gè)組的概率之和近于相同，并對各組賦予一個(gè)二進(jìn)制碼元“0”和“1”。(3)將每一大組的信源符號進(jìn)一步再分成兩組，使劃分后的兩個(gè)組的概率之和近于相同，并又賦予兩個(gè)組一個(gè)二進(jìn)制符號“0”和“1”。(4)如此重復(fù)，直至每個(gè)組只剩下一個(gè)信源符號為止。(5)信源符號所對應(yīng)的碼字即為費(fèi)諾碼。5.2.3最佳變長編碼及MATLAB實(shí)現(xiàn)消息符號符號概率第一次分組第二次分組第三次分組第四次分組二元碼字碼長X10.20

0

0

00

21

0010

3X20.19X30.18

1011

3X40.171

010

2X50.15

1

0110

3X60.101

01110

4X70.01

11111

4例5.2.4給定信源的費(fèi)諾編碼過程如表5.2.3所示。表5.2.3費(fèi)諾編碼過程2費(fèi)諾編碼方法該費(fèi)諾碼的平均碼長為信息傳輸率為編碼效率壓縮之前7個(gè)符號，平均每個(gè)符號需要3個(gè)比特表示，經(jīng)費(fèi)諾編碼壓縮之后的平均碼字長度為2.74，因此壓縮比為5.2.3最佳變長編碼及MATLAB實(shí)現(xiàn)3哈夫曼編碼方法1952年哈夫曼提出了一種構(gòu)造最佳碼的方法。它是一種最佳的逐個(gè)符號的編碼方法。(1)將n個(gè)信源消息符號按其出現(xiàn)的概率大小依次排列，(2)取兩個(gè)概率最小的字母分別配以0和1兩碼元，并將這兩個(gè)概率相加作為一個(gè)新字母的概率，與未分配的二進(jìn)符號的字母重新排隊(duì)。(3)對重排后的兩個(gè)概率最小符號重復(fù)步驟(2)的過程。(4)不斷繼續(xù)上述過程，直到最后兩個(gè)符號配以0和1為止(5)從最后一級開始，向前返回得到各個(gè)信源符號所對應(yīng)的碼元序列，即相應(yīng)的碼字。5.2.3最佳變長編碼及MATLAB實(shí)現(xiàn)例5.2.5給定信源的哈夫曼編碼過程如表5.2.4所示。表5.2.4哈夫曼編碼過程5.2.3最佳變長編碼及MATLAB實(shí)現(xiàn)該哈夫曼碼的平均碼長為信息傳輸率壓縮之前7個(gè)符號，平均每個(gè)符號需要3個(gè)比特表示，經(jīng)哈夫曼編碼壓縮之后的平均碼字長度為2.72，因此壓縮比為與香農(nóng)編碼、費(fèi)諾編碼相比，哈夫曼編碼的平均碼長較短，編碼效率和壓縮比較高。5.2.3最佳變長編碼及MATLAB實(shí)現(xiàn)3哈夫曼編碼方法哈夫曼編碼方法得到的碼并非是唯一的。造成非唯一的原因如下：每次對信源縮減時(shí)，賦予信源最后兩個(gè)概率最小的符號，用0和1是可以任意的，所以可以得到不同的哈夫曼碼，但不會影響碼字的長度。對信源進(jìn)行縮減時(shí)，兩個(gè)概率最小的符號合并后的概率與其它信源符號的概率相同時(shí)，這兩者在縮減信源中進(jìn)行概率排序，其位置放置次序是可以任意的，故會得到不同的哈夫曼碼。此時(shí)將影響碼字的長度，一般將合并的概率放在上面，這樣可獲得較小的碼方差。5.2.3最佳變長編碼及MATLAB實(shí)現(xiàn)例5.2.6對信源{0.40.20.20.10.1}進(jìn)行哈夫曼編碼的過程如表5.2.5和表5.2.6所示。兩個(gè)表中合并符號概率與原信源符號概率相同時(shí)，表5.2.5將合并信源符號概率排在上面，表5.2.6將合并信源符號概率放在下面。表5.2.5哈夫曼編碼過程15.2.3最佳變長編碼及MATLAB實(shí)現(xiàn)例5.2.6對信源{0.40.20.20.10.1}進(jìn)行哈夫曼編碼的過程如表5.2.5和表5.2.6所示。兩個(gè)表中合并符號概率與原信源符號概率相同時(shí)，表5.2.5將合并信源符號概率排在上面，表5.2.6將合并信源符號概率放在下面。表5.2.6哈夫曼編碼過程25.2.3最佳變長編碼及MATLAB實(shí)現(xiàn)例5.2.6表5.2.5所編哈夫曼碼字的平均碼長和碼方差為表5.2.6所編哈夫曼碼字的平均碼長和碼方差為可見，將合并概率放在同概率信源符號的上面能提供較小的碼方差。因此哈夫曼編碼中應(yīng)將合并概率放在同概率信源符號的上面，以保證較好的編碼性能。5.2.3最佳變長編碼及MATLAB實(shí)現(xiàn)5.3實(shí)用的無失真信源編碼方法 5.3.1游程編碼及其MATLAB實(shí)現(xiàn) 5.3.2算術(shù)編碼及其MATLAB實(shí)現(xiàn) 5.3.3MH編碼及其MATLAB實(shí)現(xiàn) 5.3.4無損壓縮的JPEG標(biāo)準(zhǔn) 5.3實(shí)用的無失真信源編碼方法 無失真信源編碼主要是用于離散信源或數(shù)字信號，如文字、數(shù)字、數(shù)據(jù)等。它們要求無失真地?cái)?shù)據(jù)壓縮，且無失真地可逆恢復(fù)。目的是為了增加單位時(shí)間內(nèi)傳送的信息量，即提高信息傳輸?shù)男?。香農(nóng)第一定理給出了無失真信源壓縮的理論極限，由定理可知，信源的熵是信源進(jìn)行無失真編碼的理論極限值，存在最佳的無失真信源編碼方法使編碼后信源的信息傳輸率任意接近信源的熵。香農(nóng)第一定理并沒有告知如何找到最佳的無失真信源編碼方法，但是，從降低信源冗余度的途徑考慮，只要尋找到去除信源符號相關(guān)性或者改變信源符號概率分布不均勻性的方法和手段，就能找到最佳無失真信源編碼的具體方法和實(shí)用碼型。游程編碼、算術(shù)編碼和字典碼是針對相關(guān)信源的有效無失真信源編碼方法，屬于非分組碼，尤其適用于二元相關(guān)信源。5.3.1游程編碼及其MATLAB實(shí)現(xiàn) 對二元相關(guān)信源，輸出的信源符號序列中往往會出現(xiàn)多個(gè)“0”或“1”符號，游程編碼尤其適合對這類信源的編碼。游程編碼已在圖文傳真、圖像傳輸?shù)葘?shí)際通信工程技術(shù)中得到應(yīng)用，實(shí)際工程技術(shù)中也常與其它變長編碼方法進(jìn)行聯(lián)合編碼，如哈夫曼編碼、MH編碼等，能進(jìn)一步壓縮信源，提高傳輸效率。游程編碼是無失真信源編碼，它能夠把二元序列編成多元碼。在二元序列中，只有“0”和“1”兩個(gè)碼元，把連續(xù)出現(xiàn)的“0”叫做“0”游程，連續(xù)出現(xiàn)的“1”叫做“1”游程。連續(xù)出現(xiàn)“0”或者“1”碼元的個(gè)數(shù)叫做游程長度(Run-Length，RL)，“0”游程長度記為L(0)，“1”游程長度記為L(1)。這樣，一個(gè)二元序列可以轉(zhuǎn)換成游程序列，游程序列中游程長度一般都用自然數(shù)標(biāo)記。5.3.1游程編碼及其MATLAB實(shí)現(xiàn) 例如，二元序列00011111000000011110001000000可以變換成多元序列3574316。若規(guī)定游程必須從“0”游程開始，則上述變換是可逆的，無失真的。如果連“0”或連“1”非常多，則可以達(dá)到信源壓縮的目的。一般傳輸信道為二元離散信道，游程序列中的各游程長度必須變換成二元碼序列。等長游程編碼就是將游程長度編成二進(jìn)制的自然數(shù)。上例中，，則用三位二進(jìn)制碼來編碼，上例的游程序列對應(yīng)的碼序列為