第5章信源編碼

編碼信息傳輸需要解決的兩個問題：在不失真或允許一定失真的條件下，如何用盡可能少的信息率來傳送信源信息？在信道受干擾的情況下，如何增加信號的抗干擾能力，同時又使得信息傳輸率最大？有效性和可靠性提高抗干擾能力（降低失真或錯誤概率）往往是以降低信息傳輸率為代價的；反之，要提高信息傳輸率常常又會使抗干擾能力減弱。信源編碼信道編碼2/2/20231編碼編碼的分類信道編碼：以提高信息傳輸?shù)目煽啃詾槟康牡木幋a通常通過增加信源的冗余度來實現(xiàn)。采用的一般方法是增大碼率/帶寬。密碼：以提高通信系統(tǒng)的安全性為目的的編碼通常通過加密和解密來實現(xiàn)。從信息論的觀點出發(fā)，“加密”可視為增熵的過程，“解密”可視為減熵的過程。第一極限定理第三極限定理第二極限定理2/2/20232編碼信源編碼：以提高通信系統(tǒng)的有效性為目的的編碼信源符號之間存在分布不均勻和相關(guān)性，使得信源存在冗余度。主要任務(wù)：減少冗余，提高編碼效率。即用較少的碼率傳送較多的信息，使單位時間內(nèi)傳送的平均信息量增加，從而提高通信的有效性。針對信源輸出符號序列的統(tǒng)計特性，尋找一定的方法把信源輸出符號序列變換為最短的碼字序列。解除相關(guān)性：使序列中的各個符號盡可能地互相獨立概率均勻化：使編碼中各個符號出現(xiàn)的概率盡可能地相等2/2/20233編碼無失真編碼定理可逆編碼的基礎(chǔ)。當信源符號轉(zhuǎn)換成代碼后，可從代碼無失真地恢復原符號。適用于離散信源/數(shù)字信號編碼。限失真編碼定理對于連續(xù)信源，編成代碼后就無法無失真地恢復原來的連續(xù)值，因為取值可以有無限多個。此時只能根據(jù)限失真編碼定理進行限失真編碼。適用于連續(xù)信源/模擬信號編碼。2/2/20234第5章信源編碼5.1編碼的定義5.2無失真信源編碼5.3限失真信源編碼定理5.4常用信源編碼方法簡介定長編碼定理變長編碼定理最佳變長編碼游程編碼、算術(shù)編碼2/2/20235編碼的定義編碼器輸入端為原始信源X=(X1X2…Xl…XL)，其符號集為A，即Xl∈{a1,a2,…ai,…an}信道所能傳輸?shù)姆柤疊={b1,b2,…bj,…bm}編碼器的功能是用符號集B中的元素，將原始信源的符號序列Xi變換為相應(yīng)的符號序列Yj=(Y1Y2…Yj…YKL)編碼器L長序列KL長碼字2/2/20236編碼的定義設(shè)信源輸出的符號序列長度為1，即信源符號集為X={x1,x2,…xi,…xn}，信源概率空間為二元信道是常用的一種信道，其基本符號集為{0,1}若將信源X通過一個二元信道傳輸，就必須把信源符號xi變換成由0,1符號組成的碼符號序列，即編碼。信源符號信源符號出現(xiàn)概率碼表碼1碼2x1p(x1)000x2p(x2)0101x3p(x3)10001x4p(x4)11111分組碼：每個符號序列Xi依照固定的碼表映射成一個符號序列Yj2/2/20237術(shù)語碼字：碼長：碼元：碼：編碼：編碼器L長序列KL長碼字變換后的各個符號序列Yj碼字Yj的長度（符號數(shù)）KL組成碼字Yj的各位代碼符號bj所有碼字的集合全部Xi←→Yj的映射關(guān)系信源符號符號概率碼表碼1碼2x1p(x1)000x2p(x2)0101x3p(x3)10001x4p(x4)111112/2/20238編碼的定義定長碼和變長碼定長碼：所有碼字的長度都相同變長碼：可變長度碼，碼中的碼字長短不一信源符號

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

碼表碼0碼1碼2碼3碼4x1p(x1)=1/2000011x2p(x2)=1/40111101001x3p(x3)=1/8100000100001x4p(x4)=1/8111101100000012/2/20239編碼的定義奇異碼和非奇異碼奇異碼：一組碼中有相同的碼字。如碼1非奇異碼：信源符號和碼字一一對應(yīng)，所有碼字都不相同。唯一可譯碼任意有限長的碼元序列，只能被唯一地分割成一個個的碼字，便稱為唯一可譯碼。奇異碼不是唯一可譯碼，而非奇異碼中有非唯一可譯碼（如碼2）和唯一可譯碼（如碼3）。2/2/202310編碼的定義非即時碼和即時碼非即時碼：指接收端收到一個完整的碼字后，不能立即譯碼，還需等下一個碼字開始接收后才能判斷是否可以譯碼。如碼3即時碼：無須考慮后續(xù)的碼符號，即可從碼元序列中譯出碼字。如碼4唯一可譯碼成為即時碼的充分條件是：其中任何一個碼字都不是其他碼字的前綴。2/2/202311編碼的定義碼非分組碼分組碼奇異碼非奇異碼非唯一可譯碼唯一可譯碼非即時碼即時碼（非延長碼）所有的碼非奇異碼唯一可譯碼即時碼2/2/202312碼樹碼樹用來表示各碼字的構(gòu)成。A0100000000000011111111111樹根—碼字的起點分成r個樹枝—碼的進制數(shù)中間節(jié)點—生出樹枝終端節(jié)點—碼字11012/2/202313碼樹碼樹用來表示各碼字的構(gòu)成。01200000111112222200212/2/202314碼樹中間節(jié)點不安排碼字，只在終端節(jié)點安排碼字每個終端節(jié)點對應(yīng)的碼字由從根節(jié)點出發(fā)到終端節(jié)點走過的路徑上所對應(yīng)的符號組成當?shù)趇階的節(jié)點作為終端節(jié)點，且分配碼字，則碼字的碼長為i按樹圖法構(gòu)成的碼一定滿足即時碼的定義樹碼的各個分支都延伸到最后一級端點，則稱為滿樹，否則為非滿樹

滿樹碼是定長碼，非滿樹碼是變長碼2/2/202315碼樹克勞夫特不等式唯一可譯碼存在的充分和必要條件為：各碼字的長度Ki應(yīng)滿足下式。m是進制數(shù)，n是信源消息數(shù)注意：克拉夫特不等式只是說明唯一可譯碼是否存在，并不能作為唯一可譯碼的判據(jù)。2/2/202316例題設(shè)二進制碼樹中X={x1,x2,x3,x4}，K1=1,K2=2,K3=2,K4=3，由上述定理，可得因此不存在滿足這種碼長的唯一可譯碼。001101011110如果將各碼字長度改成K1=1,K2=2,K3=3,K4=3，則

存在滿足這種碼長的唯一可譯碼。111中間節(jié)點2/2/202317唯一可譯碼的判斷法將碼C中所有可能的尾隨后綴組成一個集合F，當且僅當集合F中沒有包含任一碼字，則可判斷此碼C為唯一可譯碼。集合F的構(gòu)成方法首先觀察碼C中最短的碼字是否是其它碼字的前綴。若是，將其所有可能的尾隨后綴排列出。而這些尾隨后綴又有可能是某些碼字的前綴（或者某些碼字是這些尾隨后綴的前綴），再將這些尾隨后綴產(chǎn)生的新的尾隨后綴列出。依此下去，直到?jīng)]有一個尾隨后綴是碼字的前綴為止。按照上述步驟將次短碼字、…等等所有碼字可能產(chǎn)生的尾隨后綴全部列出。最終得到碼C的所有可能的尾隨后綴的集合F。2/2/202318例題例：設(shè)碼C={0,10,1100,1110,1011,1101}，根據(jù)上述測試方法，判斷是否是唯一可譯碼解：1.先看最短的碼字：“0”，它不是其他碼字前綴，所以沒有尾隨后綴。 2.再觀察次短碼字“10”，它是碼字“1011”的前綴，因此有尾隨后綴“11”?！?1”是碼字“1100”、“1110”和“1101”的前綴，得到后綴“00”、“10”和“01”?！?”是新尾隨后綴“00”和“01”的前綴，產(chǎn)生后綴“0”和“1”，“1”又產(chǎn)生新后綴“100”、“110”、“011”和“101”…… 最終得到集合F={11,00,10,01,0,1,100,110,011,101}。 其中“10”、“0”為碼字，故碼C不是唯一可譯碼。…101110……101110……101110…2/2/202319唯一可譯碼判斷方法和步驟首先，觀察是否是奇異碼。若是，一定不是唯一可譯碼。其次，計算碼長是否滿足Kraft不等式。若不滿足，一定不是唯一可譯碼。按照樹圖的構(gòu)造法則，若能將碼畫成碼樹則是即時碼，也就是唯一可譯碼。按尾隨后綴法進行判斷。只有尾隨后綴法能確切判斷是否是唯一可譯碼2/2/202320唯一可譯碼判斷方法和步驟奇異碼？不是YKraftNN不是Y碼樹是YN尾隨后綴法2/2/202321第5章信源編碼5.1編碼的定義5.2無失真信源編碼5.3限失真信源編碼定理5.4常用信源編碼方法簡介2/2/202322有mKL種可能的組合無失真信源編碼設(shè)信源符號序列的長度為L變換成由KL個符號組成的碼序列（碼字）有nL種序列組合有nL種信源消息有mKL種可能的碼字2/2/202323無失真信源編碼變換要求能夠無失真或無差錯地從Y恢復X，也就是能正確地進行反變換或譯碼傳送Y時所需要的信息率最小信息率Yk有m種可能值，平均每個符號輸出的最大信息量為log2m，KL長碼字的最大信息量為KLlog2m。用該碼字表示L長的信源序列，送出一個信源符號所需要的信息率平均為Y所能編成的碼字的個數(shù)找到使最小的編碼方式編碼前的信息量＝編碼后的信息量2/2/202324定長編碼在定長編碼中，各碼字的碼長相等，即K為定值。編碼器輸入X=(X1X2…Xl…XL),

Xl∈{a1,…an},輸入的消息總共有nL種可能的組合輸出的碼字Y=(Y1Y2…Yk…YK),Yk∈{b1,…bm}輸出的碼字總共有mK種可能的組合只要碼長K足夠長，即滿足: 則每個信源符號串都可以找到一一對應(yīng)的碼字定長編碼的目的：尋找最小K值2/2/202325例題例如英文電報有27個符號，n=27，L=1，m=2(二元編碼)在考慮了符號出現(xiàn)的概率以及符號之間的依賴性后，實際英文電報符號信源平均每個符號所提供的信息量約等于1.4比特，大大小于5比特。編碼后，5個二元符號只攜帶約1.4比特信息量。定長編碼的信息傳輸效率極低。每個英文電報符號至少要用5位二元符號編碼2/2/202326定長編碼定理定長編碼定理：由L個符號組成的、每個符號的熵為HL(X)的無記憶平穩(wěn)信源符號序列X1X2…Xl…XL，可用KL個符號Y1,Y2,…,Yk,…YKL（每個符號有m種可能值）進行定長編碼。對任意ε>0，δ>0，只要 則當L足夠大時，必可使譯碼差錯小于δ；反之，當 時，譯碼差錯一定是有限值，而當L足夠大時，譯碼幾乎必定出錯。2/2/202327定長編碼定理當編碼器容許的輸出信息率，即每個信源符號所需要的信息率為 時，只要，這種編碼器一定可以做到幾乎無失真，也就是收端的譯碼差錯概率接近于零，條件是所取的符號數(shù)L足夠大。定理的條件可以改寫為KL長碼字所能攜帶的最大信息L長信源序列包含的信息量2/2/202328定長編碼定理定理表明：只要碼字所能攜帶的信息量大于信源序列輸出的信息量，則可以使傳輸幾乎無失真，條件是L足夠大。反之，當時，不可能構(gòu)成無失真的編碼，也就是不可能做一種編碼器，能使收端譯碼時差錯概率趨于零。時，則為臨界狀態(tài)，可能無失真，也可能有失真。2/2/202329例題例：某信源有8種等概率符號，L=1時，信源熵H1(X)=3bit/符號。 若采用二進制編碼，則用3位二進制碼元表示一個信源符號。當信源符號輸出概率不相等時， p(ai)={0.4,0.18,0.1,0.1,0.07,0.06,0.05,0.04} 則H1(X)=2.55bit/符號，即用2.55位二進制碼元代表一個信源符號。 部分信源符號沒有對應(yīng)的碼字，引起差錯。22.55=5.8562/2/202330差錯概率差錯概率式中， 為信源序列的自信息方差，ε為一正數(shù)。當自信息方差和ε均為定值時，只要L足夠大，Pe可以小于任一正數(shù)δ。當信源序列長度L滿足 時，就能達到差錯率要求。2/2/202331編碼效率編碼效率信源的平均符號熵HL(X)，采用平均符號信息率來編碼，所得的效率。最佳編碼效率為編碼定理從理論上給出了編碼效率接近1的理想編碼器的存在，即2/2/202332例題例：設(shè)離散無記憶信源概率空間為信源熵為自信息方差2/2/202333例題要求編碼效率為η＝90%，則要求譯碼錯誤概率 ，得說明：在對編碼效率和譯碼錯誤概率要求不十分苛刻的情況下，仍然需要對非常大數(shù)量的信源符號同時編碼，對存儲或處理技術(shù)要求太高。

2/2/202334變長編碼定理在變長編碼中，碼長K是變化的。我們可根據(jù)信源各個符號的統(tǒng)計特性，概率大的符號用短碼，概率小的用較長的碼，這樣在大量信源符號編成碼后平均每個信源符號所需的輸出符號數(shù)就可以降低，從而提高編碼效率。2/2/202335變長編碼定理單個符號變長編碼定理若一離散無記憶信源的符號熵為H(X)，每個信源符號用m進制碼元進行變長編碼，一定存在一種無失真編碼方法，其碼字平均長度滿足下列不等式2/2/202336變長編碼定理離散平穩(wěn)無記憶序列變長編碼定理對于平均符號熵為HL(X)的離散平穩(wěn)無記憶信源，必存在一種無失真編碼方法，使平均信息率滿足不等式其中，ε為任意小正數(shù)。2/2/202337變長編碼定理編碼效率的下界編碼效率總是小于1的，可以用它來衡量各種編碼方法的優(yōu)劣。碼的剩余度：衡量各種編碼方法與最佳碼的差距如上例中，H(X)=2.55比特/符號，若m=2，η=90%，則用變長編碼來達到相當高的編碼效率，一般所要求的符號長度L可以比定長編碼小得多。2/2/202338例題例：設(shè)離散無記憶信源的概率空間為信源熵：若用二元定長編碼(0,1)來構(gòu)造一個即時碼: x1→0,x2→1，則平均碼長為編碼效率為輸出的信息率為R代表平均每個碼元攜帶的信息量，即編碼后信道的信息傳輸率。在二元無噪無損信道中，R＝η2/2/202339例題對長度為L=2的信源序列進行變長編碼，其即時碼如表所示。平均碼長為序列序列概率即時碼x1x1x1x2x2x1x2x29/163/163/161/16010110111每個符號的平均碼長為編碼效率為信息傳輸率為2/2/202340例題增加信源序列長度為L＝3或L=4編碼效率分別為信息傳輸率分別為如果對該信源采用定長二元碼編碼，要求編碼效率達到96％時，允許譯碼錯誤概率δ≤10-5自信息方差為所需要的信源序列長度為2/2/202341最佳編碼最佳碼（緊致碼）對于某個給定信源，在所有可能的唯一可譯碼中平均碼長最短的碼。最佳碼可能不止一個。平均碼長為了使平均碼長最短，將概率大的信息符號編以短的碼字，概率小的符號編以長的碼字。2/2/202342香農(nóng)編碼方法香農(nóng)第一定理指出了平均碼長與信源之間的關(guān)系，同時也指出了可以通過編碼使平均碼長達到極限值。香農(nóng)第一定理指出，選擇每個碼字的長度Ki滿足就可以得到這種碼。這種編碼方法稱為香農(nóng)編碼。2/2/202343香農(nóng)編碼步驟將信源消息符號按其概率從大到小排列確定滿足下列不等式的整數(shù)碼長Ki令P1=0，計算第i個消息的累加概率將累加概率Pi變換成二進制數(shù)，取小數(shù)點后Ki位為該消息的碼字2/2/202344例題例題：有一單符號離散無記憶信源，對該信源編二進制香農(nóng)碼。信源消息符號概率累加概率-logp(xi)碼長碼字x10.4x20.3

x30.2

x40.05x50.05碼字長度：K3=[－log0.2]=3累加概率：Pi=0.70→0.10110…00.40.70.90.951.321.732.324.34.322355000110111100111102/2/202345例題香農(nóng)編碼的平均碼長信源熵編碼效率000111110100000110111100111102/2/202346例題例：設(shè)信源共7個符號消息，其概率和累加概率如下表所示。信源消息概率累加概率-logp(xi)碼長Ki碼字x10.2002.323000x20.190.22.393001x30.180.392.473011x40.170.572.563100x50.150.742.743101x60.100.893.3241110x70.010.996.64711111102/2/202347例題信源符號的平均碼長信源熵平均信息傳輸率2/2/202348費諾編碼方法費諾編碼屬于概率匹配編碼，不是最佳的編碼方法。編碼過程如下：將信源消息符號按其出現(xiàn)的概率依次排列

p(x1)≥p(x2)≥…≥p(xn)按編碼進制數(shù)將概率分組，使每組概率盡可能接近或相等，并為每一組分配一位碼元。如編二進制碼就分成兩組，編m進制碼就分成m組。將每一分組再按同樣原則劃分，重復步驟2，直至概率不再可分為止。信源符號所對應(yīng)的碼字即為費諾碼。2/2/202349費諾編碼方法例：對以下單符號離散信源編二進制費諾碼信源符號xi

符號概率p(xi)第1分組第2分組第3分組碼字碼長x10.4x40.05x50.05x20.3x30.2信源符號xi

符號概率p(xi)第1分組第2分組第3分組第4分組碼字碼長x10.4x20.3x30.2x40.05x50.0501010101000100111011233220101010101011011101111123442/2/202350費諾編碼方法信源熵平均碼長編碼效率費諾碼比較適合于每次分組概率都很接近的信源2/2/202351費諾編碼方法例：有一單符號離散無記憶信源

對該信源編二進制費諾碼。信源符號概率編碼碼字碼長x10.2500002x20.251012x30.1251001003x40.12511013x50.062510011004x60.0625111014x70.06251011104x80.0625111114H(X)=2.75比特/符號平均碼長為2.75碼元/符號編碼效率為η=1每次所分兩組的概率恰好相等2/2/202352哈夫曼編碼方法哈夫曼編碼的步驟將信源消息符號按其出現(xiàn)的概率大小依次排列

p(x1)≥p(x2)≥…≥p(xn)取兩個概率最小的符號分別配以0和1，并將這兩個概率相加作為一個新符號的概率，與未分配碼元的符號重新排隊。對重排后的兩個概率最小符號重復步驟2的過程。繼續(xù)上述過程，直到最后兩個符號配以0和1為止。從最后一級開始，向前返回得到各個信源符號所對應(yīng)的碼元序列，即相應(yīng)的碼字。2/2/202353例：設(shè)單符號離散無記憶信源如下，要求對信源編二進制哈夫曼碼。信源符號符號概率編碼過程x10.20x20.19x30.18x40.17x50.15x60.10x70.01010.200.190.180.170.150.110.260.200.190.180.170.350.260.200.190.390.350.260.610.39碼字1011000001010011001110101010101哈夫曼編碼方法0012/2/202354哈夫曼編碼方法信源熵平均碼長編碼效率2/2/202355哈夫曼編碼方法哈夫曼的編法并不惟一每次對信源縮減時，給兩個概率最小的符號分配“0”和“1”是任意的，所以可得到不同的碼字。不同的碼元分配，得到的具體碼字不同，但碼長Ki不變，平均碼長也不變，所以沒有本質(zhì)區(qū)別?？s減信源時，若合并后的新符號概率與其他符號概率相等，從編碼方法上來說，這幾個符號的次序可任意排列，由此編出的碼都是正確的，而得到的碼字卻不相同。不同的編碼方法得到的碼長Ki不盡相同。2/2/202356哈夫曼編碼方法例：設(shè)有離散無記憶信源信源符號符號概率編碼過程x10.4x20.2x30.2x40.1x50.1010.40.20.20.2010.40.40.2010.60.4碼110100000100011碼2001011010011012/2/202357哈夫曼編碼方法平均碼長碼長的方差σ2兩種編法的平均碼長相同,所以編碼效率相同第二種編碼方法的碼長方差較小說明：碼長變化較小，比較接近于平均碼長2/2/202358哈夫曼編碼方法結(jié)論：在哈夫曼編碼過程中，對縮減信源符號按概率由大到小的順序重新排列時，應(yīng)使合并后的新符號盡可能排在靠前的位置，這樣可使合并后的新符號被重復編碼的次數(shù)減少，使短碼得到充分利用。哈夫曼編碼的特點保證了概率小的符號對應(yīng)于長碼，概率大的符號對應(yīng)于短碼，充分利用了短碼?？s減信源的最后兩個碼字的最后一位不同，保證了哈夫曼碼是即時碼。2/2/202359總結(jié)香農(nóng)碼、費諾碼、哈夫曼碼都考慮了信源的統(tǒng)計特性，經(jīng)常出現(xiàn)的信源符號對應(yīng)較短的碼字，使信源的平均碼長縮短，從而實現(xiàn)對信源的壓縮。香農(nóng)碼有系統(tǒng)的、惟一的編碼方法，但在很多情況下編碼效率不是很高。費諾碼和哈夫曼碼的編碼方法都不惟一。費諾碼比較適合于對分組概率相等或接近的信源編碼。哈夫曼碼對信源的統(tǒng)計特性沒有特殊要求，編碼效率比較高，對編碼設(shè)備的要求也比較簡單，因此綜合性能優(yōu)于香農(nóng)碼和費諾碼。2/2/202360例題cabcedeacacdeddaaabaababaaabbacdebaceadaa：16b：7c：6d：6e：5H(X)=2.165bit/符號ASCII碼：320位等長碼：120位費諾碼：91位哈夫曼碼：88位2/2/202361哈夫曼編碼方法例：對信源的二次擴展信源進行哈夫曼編碼。解：二次擴展信源為如果有一個信源序列（60）： abaaabbbbaaaabbbbaabaabbaaaaaaaaaaaabaaaabbaaaaaaaaaaabaaabb經(jīng)過二元哈夫曼編碼，變?yōu)椋?10010111110010111110100111000000110010110000001100111（53）2/2/202362哈夫曼編碼方法序列越長，平均碼長越短，編碼效率越高2/2/202363第5章信源編碼5.1編碼的定義5.2無失真信源編碼5.3限失真信源編碼定理5.4常用信源編碼方法簡介2/2/202364限失真信源編碼定理從信息處理的角度看，無失真信源編碼是保熵的，只是對冗余度進行了壓縮。限失真信源編碼的中心任務(wù)是：在允許的失真范圍內(nèi)，把編碼后的信息率壓縮到最小。編碼后的信息率得到壓縮，屬于熵壓縮編碼。引入熵壓縮編碼的原因：保熵編碼并非總是必需的；保熵編碼并非總是可能的；降低信息率有利于傳輸和處理，因此有必要進行熵壓縮編碼。2/2/202365限失真信源編碼定理設(shè)離散無記憶信源X的信息率失真函數(shù)為R(D)當信息率R＞R(D)時，只要信源序列長度L足夠長，一定存在一種編碼方法，其譯碼失真小于或等于D＋ε，ε為任意小的正數(shù)。反之，若R＜R(D)，則無論采用什么樣的編碼方法，其譯碼失真必大于D。如果是二元信源，則對于任意小的ε＞0，每一個信源符號的平均碼長滿足如下公式：2/2/202366第5章信源編碼5.1編碼的定義5.2無失真信源編碼5.3限失真信源編碼定理5.4常用信源編碼方法簡介2/2/202367游程編碼游程符號序列中某符號連續(xù)重復出現(xiàn)而形成符號串的長度，又稱為游程長度或游長。游程編碼將這種符號序列映射成游程長度和對應(yīng)符號序列的位置的標志序列。如果知道了游程長度和對應(yīng)符號序列的位置的標志序列，就可以完全恢復出原來的符號序列。2/2/202368游程編碼二元序列的游程連續(xù)出現(xiàn)“0”，稱為“0”游程，表示為L(0)。連續(xù)出現(xiàn)“1”，稱為“1”游程，表示為L(1)。若規(guī)定二元序列總是從“0”開始，第一個游程是“0”游程，則第二個游程必為“1”游程，第三個又是“0”游程……用交替出現(xiàn)的“0”游程和“1”游程長度表示任意二元序列。對于隨機序列，游程長度是隨機的其取值可為1,2,3,…，直至無窮。一種一一對應(yīng)的變換，是可逆變換。2/2/202369游程編碼多元序列游程多元序列也可以變換成游程序列，如m元序列可有m種游程。但是變換成游程序列時，需要增加標志位才能區(qū)分游程序列中的“長度”是m種游程中的哪一個的長度，否則，變換就不可逆。增加的標志位可能會抵消壓縮編碼得到的好處。所以，對多元序列進行游程變換的意義不大。2/2/202370游程編碼游程變換減弱了原序列符號間的相關(guān)性。游程變換將二元序列變換成了多元序列，這樣就適合于用其他方法，如哈夫曼編碼，進一步壓縮信源，提高通信效率。首先測定“0”游程長度和“1”游程長度的概率分布，即以游程長度為元素，構(gòu)造一個新的信源。對新的信源(游程序列)進行哈夫曼編碼。2/2/202371例題例：考慮如下比特流11111111111111100000000000000000001111……它由十五個1、十九個0和四個1組成。最大重復次數(shù)為19，可以用5位二進制表示。(01111,1)、(10011,0)、(00100,1)壓縮率：18：38＝1：2.11游程編碼是一種用來縮減重復字符串大小的技術(shù)2/2/202372MH編碼MH編碼是用于黑白文件傳真的數(shù)據(jù)壓縮。傳真一頁A4文件：寬210mm，高297mm分辨率：8點/mm，4線/mm需傳送：210×8×297×4≈2Mbit大多數(shù)傳真機速率：9600bit/s傳送一頁A4文件需要：3.5分鐘MH碼以8幅標準文件樣張作統(tǒng)計，計算出“黑”、“白”各種游程長度的出現(xiàn)概率。2/2/202373MH編碼2/2/202374MH編碼如黑游程長度856＝832＋24，查表得000000100110100000010111例：設(shè)某頁傳真文件中某一掃描行的象素點為：17白－5黑－55白－10黑－1641白數(shù)據(jù)壓縮比：1728：54＝322/2/202375算術(shù)編碼算術(shù)編碼是近十多年來發(fā)展迅速的一種無失真信源編碼，它與最佳的哈夫曼碼相比，理論性能稍加遜色，而實際壓縮率和編碼效率卻往往還優(yōu)于哈夫曼碼，且實現(xiàn)簡單，故很受工程上的重視。算術(shù)編碼不同于哈夫曼碼，它屬于非分組碼。它從全序列出發(fā)，考慮符號之間的關(guān)系來進行編碼。算術(shù)編碼利用了累積概率的概念。算術(shù)碼主要的編碼方法是計算輸入信源符號序列所對應(yīng)的區(qū)間。2/2/202376算術(shù)碼的主要概念把信源輸出序列概率和實數(shù)段[0,1]中的一個數(shù)C聯(lián)系起來。設(shè)信源字母表為{a1,a2}，其概率p(a1)=0.6,p(a2)=0.4將[0,1]分成與概率比例相應(yīng)的區(qū)間，[0,0.6]和[0.6,l]設(shè)信源輸出序列S=S1S2S3…Sn當信源輸出的第一個符號S1

=a1時，數(shù)C的值處在[0,0.6]當信源輸出的第一個符號S1

=a2時，數(shù)C的值處在[0.6,l]根據(jù)信源S1的情況，把C所在的段再次按概率比例劃分算術(shù)編碼p(a1)p(a2)00.6100.360.60.841p(a1a1)p(a1a2)p(a2a1)p(a2a2)2/2/202377算術(shù)編碼設(shè)信源符號集A={a1,a2,…,an}，其相應(yīng)概率分布為p(ai)信源符號的累積概率為累積概率Pr+1和Pr都是小于1的正數(shù)，可用[0,1]區(qū)間內(nèi)的兩個點來表示。P1p1P2P3P4p2p3……10pr就是這兩點間的小區(qū)間的長度，如下圖所示：當A={0,1}二元信源時：P(0)=0

;P(1)=p(0)

P(0)P(1)01p(0)p(1)2/2/202378P(0)0P(1)1p(0)設(shè)輸入符號序列S=011p(1)P(0)P(1)p(00)P(01)p(01)P(01)P(1)P(011)p(010)p(011)p(0)=p(00)+p(01)p(01)=p(010)+p(011)歸一律P(0)=0P(01)=p(00)P(011)=P(01)+p(010)算術(shù)編碼2/2/202379算術(shù)編碼令S=01，則010→S0 011→S1輸入序列S1=“011”對應(yīng)的區(qū)間是對區(qū)間[P(S),P(1))進行分割序列S0=“010”對應(yīng)的區(qū)間寬度為A(“010”)=A(“01”)p(0)=A(S)p(0)其對應(yīng)