北郵信通院信息論第五章

第五章無失真信源編碼－－北京郵電大學(xué)信息與通信工程學(xué)院2/100

一、概述

二、定長碼三、變長碼四、哈夫曼編碼主要內(nèi)容本章主要介紹無失真信源編碼定理與一些重要的無失真信源編碼方法五、幾種實(shí)用的信源編碼方法3/100信源編碼：將信源符號(hào)序列按一定的數(shù)學(xué)規(guī)律映射成由碼符號(hào)組成的碼序列的過程。信源譯碼：根據(jù)碼序列恢復(fù)信源序列的過程。無失真信源編碼：即信源符號(hào)可以通過編碼序列無差錯(cuò)地恢復(fù)。（適用于離散信源的編碼）限失真信源編碼：信源符號(hào)不能通過編碼序列無差錯(cuò)地恢復(fù)。（可以把差錯(cuò)限制在某一個(gè)限度內(nèi)）4/100信源編碼的目的：提高傳輸有效性，即用盡可能短的碼符號(hào)序列來代表信源符號(hào)。無失真信源編碼定理證明了：如果對(duì)信源序列進(jìn)行編碼，當(dāng)序列長度足夠長時(shí)，存在無失真編碼使得傳送每信源符號(hào)所需的比特?cái)?shù)接近信源的熵。因此，采用有效的信源編碼會(huì)使信息傳輸效率得到提高。5/100§5.1概述本節(jié)主要內(nèi)容

一、信源編碼器

二、信源編碼的分類三、分組碼6/100§5.1.1信源編碼器分組碼單符號(hào)信源編碼器編碼器信源序列碼符號(hào)集碼字集合符號(hào)集A7/100信源譯碼器分組碼單符號(hào)譯碼器譯碼器信源序列碼符號(hào)集碼字集合8/100摩爾斯信源編碼器信源編碼器（1）信源符號(hào){英文字母}碼符號(hào)集點(diǎn)、劃、字母間隔、單詞間隔信道基本符號(hào){0，1}

簡單信源編碼器信源編碼器（2）二進(jìn)信道將英文字母變成摩爾斯電碼將摩爾斯電碼變成二進(jìn)碼符號(hào)點(diǎn)劃字母間隔單詞間隔電平+-+++---------二進(jìn)代碼101110000000009/100摩爾斯信源編碼器10/100原信源的N次擴(kuò)展碼將N個(gè)信源符號(hào)編成一個(gè)碼字。相當(dāng)于對(duì)原信源的N次擴(kuò)展源的信源符號(hào)進(jìn)行編碼。例信源X={0,1}的二次擴(kuò)展源X2的符號(hào)集為：{00,01,10,11}。對(duì)X2編碼，即為原信源X的二次擴(kuò)展碼。11/100§5.1.2信源編碼的分類概率匹配編碼：信源符號(hào)的概率已知。通用編碼：信源符號(hào)的概率未知。分組碼：先分組再編碼。在分組碼中，每一個(gè)碼字僅與當(dāng)前輸入的信源符號(hào)組有關(guān)，與其他信源符號(hào)無關(guān)。

包括：定長碼、變長碼（Huffman編碼、費(fèi)諾編碼）非分組碼：碼序列中的符號(hào)與信源序列中的符號(hào)無確定的對(duì)應(yīng)關(guān)系。例如算術(shù)編碼。12/100信源編碼分組碼非分組碼按信源序列和編碼器輸出的關(guān)系先分組再編碼定長碼變長碼每一個(gè)碼字僅與當(dāng)前輸入的信源符號(hào)組有關(guān)編碼器信源序列編碼序列例如算術(shù)編碼就是非分組碼無確定的對(duì)應(yīng)關(guān)系13/100§5.1.3分組碼與非分組碼的顯著區(qū)別：分組碼中包含碼字各碼字都不相同？YN非奇異碼奇異碼唯一可譯不同的消息序列不會(huì)生成相同的碼序列無失真編碼必要條件必要條件14/100即時(shí)碼與非即時(shí)碼只要接收到每個(gè)碼字的最后一個(gè)符號(hào)可立即將該碼字譯出？Y即時(shí)碼N非即時(shí)碼優(yōu)點(diǎn)：譯碼延遲小15/100異前置碼設(shè)為長度為的碼字，即，稱為的前置。一個(gè)碼中無任何碼字是其他碼字的前置異前置碼是唯一可譯碼

異前置碼與即時(shí)碼是等價(jià)的逗號(hào)碼用一個(gè)特定的碼符號(hào)表示所有碼字的結(jié)尾逗號(hào)碼是唯一可譯碼16/100例設(shè)信源符號(hào)集為{a,b,c,d},采用6種分組編碼如下表，分析每一個(gè)碼的唯一可譯性5.1符號(hào)

碼A碼B碼C碼D碼E碼Fa

0

0

00

0

1

0b

0

1

01

10

01

01c

1

10

10

110

001

011d

10

11

11

1110001

0111非奇異唯一可譯10bac等長異前置碼逗號(hào)碼0表示開頭即時(shí)碼17/100一些結(jié)論變長碼定長碼只要非奇異，就唯一可譯非奇異且異前置就唯一可譯速率變化

設(shè)置緩沖器速率恒定

不需緩沖器受誤碼影響大,逗號(hào)碼除外碼長已知

容易同步容易產(chǎn)生差錯(cuò)傳播無差錯(cuò)傳播18/100碼樹碼樹是表示信源編碼碼字的重要工具之一葉子根節(jié)點(diǎn)

19/100例一個(gè)碼C包含4個(gè)碼字：{1,01,000,001},試用碼樹來表示5.2采用二進(jìn)制碼樹解：R100011（1）（01）（001）（000）20/100一些結(jié)論非奇異碼字總能與碼樹建立一一對(duì)應(yīng)的關(guān)系在碼樹中，n階節(jié)點(diǎn)的個(gè)數(shù)最多為例：2進(jìn)碼樹中，n階節(jié)點(diǎn)數(shù)目最多為21/100§5.2定長碼本節(jié)主要內(nèi)容一、無失真編碼條件二、信源序列分組定理三、定長碼信源編碼定理22/100§5.2.1無失真編碼條件對(duì)于定長碼,只要非奇異就唯一可譯。這就要求碼字的數(shù)目不少于被編碼的信源序列的個(gè)數(shù)設(shè)信源X包含q個(gè)符號(hào)，碼符號(hào)集包含的符號(hào)數(shù)為r單信源符號(hào)編碼：碼長N長信源符號(hào)序列編碼（N次擴(kuò)展碼）平均每個(gè)信源符號(hào)所需碼符號(hào)數(shù)23/100例英文字母26個(gè)加1個(gè)空格可看成共27個(gè)符號(hào)的信源。如對(duì)單符號(hào)進(jìn)行編碼：但是，如果采用適當(dāng)?shù)男旁淳幋a，理論上每信源符號(hào)所需二進(jìn)碼符號(hào)數(shù)可以遠(yuǎn)小于上面的值，在理想情況下可以壓縮到接近信源的熵1.4左右。本節(jié)就是從理論上證明這種壓縮是可以實(shí)現(xiàn)的。24/100§5.2.2信源序列分組定理定理5.2.1離散無記憶信源{使得{①②所有序列出現(xiàn)概率之和小于序列出現(xiàn)的概率滿足：(5.2.3)25/100證：我們先證明（5.2.3）式。設(shè)信源符號(hào)集為，各符號(hào)出現(xiàn)的概率分別為，為長度為的序列，為中符號(hào)出現(xiàn)的次數(shù)。將信源序列按下列原則分成兩：、，其中，

：（5.2.4）

：其它}

根據(jù)大數(shù)定律，當(dāng)序列足夠長時(shí)，信源符號(hào)出現(xiàn)的次數(shù)接近。因此，中的序列的符號(hào)出

現(xiàn)的次數(shù)符合大數(shù)定律，稱典型序列。

26/100從（5.2.4）中可以看出，隨的不同而改變。設(shè)，則對(duì)于中的信源符號(hào)，有

或，其中由于信源是無記憶的，所以的概率為＝，的自信息負(fù)值為：27/100所以選擇，使得（5.2.5）則式（5.2.3）成立。28/100下面證明定理的后半部分。設(shè)，根據(jù)（5.2.3）式，有

（5.2.6）因?yàn)樾旁词菬o記憶的，所以，得到（5.2.7）將（5.2.7）代入（5.2.6），得

（5.2.8）29/100令,可得,所以根據(jù)Chebyshev不等式：，其中為隨機(jī)變量；這樣就得到：（5.2.9）其中，，所以，（5.2.10）30/100其中，自信息的方差

（5.2.11）取，則當(dāng)，31/100總結(jié)對(duì)離散無記憶信源，給定，令取；那么對(duì)長度為N的信源序列，滿足下式的為典型序列，否則為非典型序列。定理說明，當(dāng)N足夠大時(shí)，典型序列的的值接近信源的熵對(duì)于有記憶的馬氏源，定理5.2.1也成立32/100漸進(jìn)均分特性典型序列的概率估計(jì)設(shè)取2為底簡記為:當(dāng)足夠小時(shí)，每個(gè)典型序列的概率接近，其偏差不大于；此時(shí)序列的長度需要很大33/100典型序列的個(gè)數(shù)估計(jì)設(shè)為中序列的個(gè)數(shù)先估計(jì)上界：利用概率估計(jì)的下界再估計(jì)下界：利用概率估計(jì)的上界34/100漸近均分特性當(dāng)取值很小時(shí)（N要求很大），對(duì)于典型序列

含意：當(dāng)長度N足夠大時(shí)：典型序列接近等概率，數(shù)目近似于非典型序列出現(xiàn)的概率接近為零（以概率收斂）35/100結(jié)論設(shè)信源序列數(shù)為，編碼序列數(shù)為。如果每個(gè)信源序列都至少要有一個(gè)碼字，即需要。但是，隨著信源序列長度的增加，基本上是典型序列出現(xiàn)，這樣我們僅考慮對(duì)典型序列的編碼，所以實(shí)際需要個(gè)碼字。而當(dāng)信源的熵小于時(shí)，就會(huì)使得碼字的長度減小。36/100§5.2.3定長碼信源編碼定理定理5.2.2離散無記憶信源的熵為H(X)，碼符號(hào)集的符號(hào)數(shù)為r，將長度為N的信源序列編成長度為l的碼序列。只要滿足：則當(dāng)N足夠大時(shí)，譯碼差錯(cuò)可以任意小(）；若上述不等式不滿足，肯定會(huì)出現(xiàn)譯碼差錯(cuò)。37/100證明思路

在編碼時(shí)，可以使所有典型序列都有對(duì)應(yīng)的碼字，而最壞的情況是所有的非典型序列無對(duì)應(yīng)的碼字。典型序列的個(gè)數(shù)小于正定理38/100證明思路

若不滿足上式逆定理=已知編碼序列條件下信源序列的不確定性，如果無差錯(cuò)譯碼,該不確定性為零。39/100相關(guān)定義定長碼編碼速率它表示編碼后，一個(gè)信源符號(hào)平均所攜帶的最大信息量，也可以理解為傳送一個(gè)信源符號(hào)平均所需的比特?cái)?shù)。壓縮碼率實(shí)際就是減小編碼速率。40/100編碼效率NH(X)表示N長信源序列的所包含的信息量l㏒r表示碼序列所能攜帶的最大信息量。由定理5.3.2可知，當(dāng)N足夠大時(shí)，可以接近1由漸近均分特性，當(dāng)減小時(shí)，增加。壓縮碼率和提高編碼效率是同樣的含義。41/100信息傳輸速率：每個(gè)傳輸符號(hào)所含信息量對(duì)于二進(jìn)編碼，編碼效率與信息傳輸速率數(shù)值相同。42/100相關(guān)結(jié)論無失真信源編碼的另一種表述如果編碼速率，則存在無失真編碼。反之，肯定有失真。43/100編碼效率與熵的關(guān)系信源給定后，若要求編碼效率越高，N越大，要求譯碼差錯(cuò)越低，N值也越大。44/100例5.2.1一離散無記憶信源的模型如下，要求用二元定長碼編碼，已知，試估計(jì)信源序列的最小長度N。信源的熵解：自信息方差{兩種含義不現(xiàn)實(shí)：編碼時(shí)延大，信源要求長45/100結(jié)論要達(dá)到一定誤碼要求，信源序列長度需很長，所以編碼器難于實(shí)現(xiàn)。46/100§5.3變長碼本節(jié)主要內(nèi)容一、異前置碼的性質(zhì)二、變長碼信源編碼定理47/100§5.3.1異前置碼的性質(zhì)R100011（1）（01）（001）（000）變長碼可用非全碼樹來描述。下圖就是一個(gè)異前置碼的碼樹。只有端點(diǎn)（樹葉）對(duì)應(yīng)碼字。對(duì)應(yīng)碼字的端點(diǎn)與根之間不能有其它的節(jié)點(diǎn)作為碼字端點(diǎn)不能向上延伸再構(gòu)成新碼字全碼樹圖中每個(gè)葉子節(jié)點(diǎn)都在最底層，從左至右排列48/100定理5.3.1(Kraft定理)若信源符號(hào)數(shù)為q，碼符號(hào)數(shù)為r，對(duì)信源符號(hào)進(jìn)行編碼，相應(yīng)碼長度為，則異前置碼存在的充要條件是：49/100證明思路

充分性：做一個(gè)階全樹，樹葉總數(shù)取階的任一節(jié)點(diǎn)作為第一個(gè)碼字，去掉的樹葉50/100證明思路

必要性：構(gòu)造一個(gè)碼全樹，最高階為碼字最大長度對(duì)于階為的節(jié)點(diǎn)，占用的樹葉數(shù)為當(dāng)碼滿足Kraft不等式時(shí)，未必就是異前置碼異前置碼并不唯一，例如0,1交換。51/100例5.4.1下表列出了3種變長碼的編碼，并給出了對(duì)應(yīng)每個(gè)碼的所有的碼長和具有同一碼長的碼字的個(gè)數(shù)，其中碼符號(hào)集為{0,1,2,3}。試問對(duì)每個(gè)碼是否存在相應(yīng)的異前置碼？碼字碼個(gè)數(shù)碼長碼1碼2碼3

1

3

2

1

2

3

7

7

3

3

3

3

4

3

3

7

5

4

5

452/100解：利用Kraft不等式來驗(yàn)證。對(duì)于碼1：存在相應(yīng)的異前置碼同理：碼2不存在相應(yīng)的異前置碼；碼3存在相應(yīng)的異前置碼。實(shí)際上，可以用碼樹來驗(yàn)證，方法更簡單。注意：只是存在異前置碼！53/100定理5.3.2證明略若一個(gè)碼是唯一可譯碼且碼字長為則必滿足Kraft不等式，即：q：信源符號(hào)數(shù)r：碼符號(hào)數(shù)54/100推論5.3.1任意唯一可譯碼都可用異前置碼代替，而不改變碼字的任一長度。結(jié)論滿足kraft不等式并不一定唯一可譯，因?yàn)槠娈惔a可能滿足kraft不等式。55/100§5.3.2變長碼信源編碼定理單信源符號(hào)編碼的平均碼長：表示平均每個(gè)信源符號(hào)所需碼符號(hào)的個(gè)數(shù)對(duì)于N次擴(kuò)展源編碼，原信源符號(hào)平均碼長為56/100定理5.3.3單符號(hào)信源變長碼編碼定理給定熵為H(X)的離散無記憶信源X，用r元碼符號(hào)集對(duì)單信源符號(hào)進(jìn)行編碼，則存在唯一可譯碼，其平均碼長滿足：57/100(1)證明不等式前半部證明思路

等式成立條件即58/100(2)證明不等式后半部證明思路

{59/100定理5.3.4有限序列信源變長碼編碼定理證明略若對(duì)長度為N的離散無記憶信源序列進(jìn)行編碼，則存在唯一可譯碼，且使每信源符號(hào)平均碼長滿足：且對(duì)任何唯一可譯碼左邊不等式都要滿足。60/100定理5.3.5證明略

對(duì)于離散平穩(wěn)遍歷馬氏源，有：61/100定理5.3.6仙農(nóng)第一定理證明思路：

若對(duì)任意信源X的N次擴(kuò)展源進(jìn)行編碼，當(dāng)N足夠大時(shí)，總能找到唯一可譯的r進(jìn)編碼，使得X的平均碼長任意接近信源的熵利用定理(5.3.5)的不等式，就可得到定理的結(jié)果62/100相關(guān)定義編碼速率：編碼效率：信息傳輸速率：編碼剩余度：63/100對(duì)所有唯一可譯碼都要滿足無需一定滿足，但存在這種關(guān)系，通常希望越小越好一些結(jié)論平均碼長的上、下界時(shí)，，此時(shí)：各信源符號(hào)出現(xiàn)概率為li為整數(shù)每碼元平均所帶信息量為,碼元符號(hào)獨(dú)立且等概64/100例5.3.2用例5.2.1的信源模型，i)對(duì)單信源符號(hào)進(jìn)行二元編碼，即，求平均碼長和編碼效率；ii）編成2次擴(kuò)展碼，信源序列與碼序列的映射關(guān)系為：求平均碼長和編碼效率。解：1)65/100信源序列的概率：2)且：與例5.2.1相比，可以看出，為得到同樣編碼效率所用的編碼符號(hào)數(shù)比定長碼小得多。因此容易達(dá)到高的編碼效率，是變長碼的顯著優(yōu)點(diǎn)。66/100§5.4哈夫曼編碼本節(jié)主要內(nèi)容一、二元哈夫曼編碼二、多元哈夫曼編碼三、馬氏源的編碼67/100定理5.4.1任意對(duì)于一個(gè)含q個(gè)符號(hào)的信源，存在最優(yōu)的二進(jìn)制碼，其中有兩個(gè)最長的碼字有相同的長度且僅最后一個(gè)碼位有別，即其中一個(gè)的最末尾是0，而另一個(gè)的最末尾是1（或者相反）若一個(gè)唯一可譯碼的平均碼長小于所有其它唯一可譯碼，則稱該碼為最優(yōu)碼(或緊致碼)。應(yīng)注意：最優(yōu)是唯一可譯碼之間的比較，因此它的平均碼長未必達(dá)到編碼定理的下界?！?.4.1二元哈夫曼編碼68/100證明思路：首先證明對(duì)于最優(yōu)碼，概率小的符號(hào)對(duì)應(yīng)長度長的碼字。證明最長的碼字有兩個(gè)長度相同，且只有最后一位不同。一個(gè)最優(yōu)碼唯一可譯滿足Kraft不等式存在與其同樣碼長的異前置碼69/100二元最優(yōu)異前置碼的構(gòu)造方法設(shè)信源S為，對(duì)應(yīng)的碼字為將概率最小的兩個(gè)碼符號(hào)合并，從而產(chǎn)生新的信源S‘

設(shè)，對(duì)應(yīng)的碼字為。對(duì)新信源編碼后，按下面的關(guān)系就可恢復(fù)原來信源的碼字：70/100證明思路：設(shè)若對(duì)信源是最優(yōu)的異前置碼，則對(duì)信源也是最優(yōu)的異前置碼對(duì)S，有71/100一些結(jié)論我們可以采用合并兩個(gè)最小概率符號(hào)的方法，逐步地按這樣的路線去編碼：最后將2字母信源分配0、1符號(hào)；然后可逐步反推到原信源S，從而得到信源的最優(yōu)編碼。這種編碼稱做二元Huffman編碼72/100例5.4.1一信源S的符號(hào)集A=，概率分別為：0.3，0.25，0.25，0.1，0.1；試對(duì)信源符號(hào)進(jìn)行二元Huffman編碼解：依次做信源S’S’’S’’’，最后將0、1符號(hào)分配給S’’’，如下圖：信源符號(hào)

碼字

00

01

10

110

11173/100Huffman編碼方法(1)將信源概率分布按大小依遞減次序排列；合并兩概率最小者，得到信新源；并分配0,1符號(hào)(2)新信源若包含兩個(gè)以上符號(hào)返回（1），否則到（3）(3)從最后一級(jí)向前按順序?qū)懗雒啃旁捶?hào)所對(duì)應(yīng)的碼字74/100例5.4.2一信源S的符號(hào)集A=，概率分別為：0.4，0.2，0.2，0.1，0.1；試對(duì)信源符號(hào)進(jìn)行二元Huffman編碼，并計(jì)算平均碼長和編碼效率解：000110110111兩種計(jì)算方法75/100一些結(jié)論Huffman編碼是最優(yōu)碼（或緊致碼），是異前置碼編碼結(jié)果并不唯一，例如0、1可換，相同概率符號(hào)碼字可換，但平均碼長不變不一定達(dá)到編碼定理下界，達(dá)下界條件為通常適用于多元信源，對(duì)于二元信源，必須采用合并符號(hào)的方法，才能得到較高的編碼效率76/100例例5.4.2還可以用以下的方法編碼：01011011101111不變但碼長的方差改變了000110110111方法1方法277/100一些結(jié)論當(dāng)碼長的方差小時(shí)，編碼器所需緩沖器容量小。因此要盡量減小碼長的方差。方法是：在編碼時(shí)，應(yīng)使合并后的信源符號(hào)位于縮減信源符號(hào)盡可能高的位置上（減少合并次數(shù)）。78/100否則，就利用上式計(jì)算出大于q的最小正整數(shù)s。然后給信源增補(bǔ)零概率符號(hào)，使增補(bǔ)后的信源符號(hào)總數(shù)為s。編碼后，去掉這些零概率符號(hào)所對(duì)應(yīng)的碼字，其余碼字為所需碼字通過觀察可知，要使編碼的平均碼長最短，對(duì)應(yīng)的碼樹要構(gòu)成滿樹是必要條件。對(duì)于r元哈霍夫曼編碼，從第n階的1個(gè)節(jié)點(diǎn)到n+1階節(jié)點(diǎn)，增加的數(shù)目為r-1。因此，達(dá)到滿樹時(shí)，總的樹葉數(shù)為：§5.4.2多元哈夫曼編碼非負(fù)整數(shù)碼樹圖中每個(gè)中間節(jié)點(diǎn)后續(xù)的枝數(shù)為m時(shí)稱滿樹;79/100例5.4.3一信源S的符號(hào)集A=概率分別為：0.4,0.2,0.1,0.1,0.05,0.05,0.05,0.05

；試對(duì)信源符號(hào)進(jìn)行3元哈夫曼編碼，并計(jì)算平均碼長和編碼效率解：{信源要增加1個(gè)零概率符號(hào){{80/10081/100決策樹

如果有n個(gè)互斥隨機(jī)事件，概率分別為pi,現(xiàn)用某種測試方法分步對(duì)所選擇的目標(biāo)事件進(jìn)行識(shí)別，要求具有最小的決策平均次數(shù)，相當(dāng)于對(duì)這些事件進(jìn)行Huffman編碼。Huffman編碼的應(yīng)用82/100決策樹舉例例如，甲手中有4張紙牌，點(diǎn)數(shù)分別為1、2、3、4，要求乙猜：乙可以向甲提問題，甲只能用是或否來回答。求乙平均最少問幾個(gè)問題可以猜到紙牌的點(diǎn)數(shù)和相應(yīng)的策略。(1)1、2、3、4的概率均為1/4的決策樹；(2)1、2、3、4的概率分別為1/2、1/4、1/8、1/8的決策樹.首先Huffman編碼；Huffman編碼碼樹變成決策樹。決策的設(shè)計(jì)：每步?jīng)Q策結(jié)果應(yīng)該與節(jié)點(diǎn)分支的概率匹配。83/100第(1)問84/100第(2)問85/100按狀態(tài)編碼根據(jù)馬氏源的特性，當(dāng)前發(fā)出的符號(hào)所含信息量取決于當(dāng)前的狀態(tài)。這個(gè)信息量可能很大也可能很小。例如，一個(gè)馬氏源包含3個(gè)狀態(tài){a，b，c}，每個(gè)狀態(tài)代表一個(gè)輸出符號(hào)，狀態(tài)轉(zhuǎn)移矩陣如下：馬氏源可以采用按狀態(tài)編碼和多個(gè)符號(hào)合并編碼§5.4.3馬氏源的編碼下一個(gè)字母b.c出現(xiàn)等概包含的信息量最大下一個(gè)字母必然出現(xiàn)b包含的信息量為086/100給定一個(gè)初始狀態(tài)對(duì)每個(gè)狀態(tài),根據(jù)轉(zhuǎn)移概率進(jìn)行最優(yōu)編碼，例如Huffman編碼.設(shè)為對(duì)應(yīng)的碼表,其中規(guī)定信源符號(hào)和碼字的對(duì)應(yīng)關(guān)系，記為按狀態(tài)編碼方法87/100編碼過程給定一信源序列，設(shè)初始狀態(tài)用

碼表，查出對(duì)應(yīng)的碼字

作為編碼器輸出，同時(shí)根據(jù)得到下一個(gè)狀態(tài)如此重復(fù)，直到處理完最后一個(gè)信源符號(hào)編碼器輸出為

88/100譯碼過程根據(jù)譯碼器初始狀態(tài)，用碼表查出其中的碼字與序列的前綴的相同部分,設(shè)，則對(duì)應(yīng)的為譯碼器的輸出根據(jù)和確定下一個(gè)狀態(tài)，設(shè)為，則找到碼表中的碼字與序列中的前綴相同的部分，設(shè)

，則對(duì)應(yīng)的為譯碼器的輸出如此重復(fù)，直到最后一個(gè)序列符號(hào)處理完。89/100例5.4.4對(duì)狀態(tài)轉(zhuǎn)移矩陣如下的馬氏源進(jìn)行哈夫曼編碼，并計(jì)算編碼效率。解：在3個(gè)狀態(tài)下的Huffman編碼如下編碼狀態(tài)符號(hào)

a

b

c