信息論與編碼(第三章)-160329-講課教材

*1信息論與編碼

曹雪虹，張宗橙編

北京郵電大學(xué)出版社

北京工商大學(xué)計算機(jī)與信息工程學(xué)院廉小親*北京工商大學(xué)計算機(jī)與信息工程學(xué)院信息論與編碼2第3章無失真信源編碼3.1編碼的定義3.2定長編碼定理3.3變長編碼定理3.4最佳編碼

3.4.1香農(nóng)編碼方法

3.4.2費(fèi)諾編碼方法

3.4.3哈夫曼編碼方法習(xí)題*北京工商大學(xué)計算機(jī)與信息工程學(xué)院信息論與編碼3引言

編碼信源編碼信道編碼無失真信源編碼限失真信源編碼主要用于連續(xù)信源或模擬信號，如語音、圖像等適用于離散信源或數(shù)字信號，如文件傳真等*北京工商大學(xué)計算機(jī)與信息工程學(xué)院信息論與編碼43.1編碼的定義信道信宿信源圖1簡單的通信系統(tǒng)模型X∈{x1,x2}二元信道（可傳輸?shù)姆枮?,1）信源編碼信源解碼*北京工商大學(xué)計算機(jī)與信息工程學(xué)院信息論與編碼53.1編碼的定義編碼：設(shè)信源X輸出的符號集｛x1,x2,x3,x4｝，將信源發(fā)出的符號xi轉(zhuǎn)換成0，1符號組成的碼符號序列(碼字)。問題提出：如何用0,1符號組成的碼符號序列來表示xi？信道信源解碼信宿信源圖2復(fù)雜的通信系統(tǒng)模型X∈{00,01,10,11}信源編碼二元信道（可傳輸?shù)姆枮?,1）X∈{x1,x2,x3,x4}*北京工商大學(xué)計算機(jī)與信息工程學(xué)院信息論與編碼63.1編碼的定義信源符號xi符號出現(xiàn)的概率p(xi)碼1碼2碼3碼4碼5x11/4001100x21/41110100101x31/4000010000110x41/411011000000111表3-1不同碼字*北京工商大學(xué)計算機(jī)與信息工程學(xué)院信息論與編碼73.1編碼的定義信源符號xi符號出現(xiàn)的概率p(xi)碼1碼2碼3碼4碼5x11/4001100x21/41110100101x31/4000010000110x41/411011000000111表3-1不同碼字*北京工商大學(xué)計算機(jī)與信息工程學(xué)院信息論與編碼83.1編碼的定義信源符號xi符號出現(xiàn)的概率p(xi)碼1碼2碼3碼4碼5x11/4001100x21/41110100101x31/4000010000110x41/411011000000111表3-1不同碼字奇異碼1、引出奇異碼和非奇異碼的概念。*北京工商大學(xué)計算機(jī)與信息工程學(xué)院信息論與編碼93.1編碼的定義信源符號xi符號出現(xiàn)的概率p(xi)碼1碼2碼3碼4碼5x11/4001100x21/41110100101x31/4000010000110x41/411011000000111表3-1不同碼字1、引出奇異碼和非奇異碼的概念。非奇異碼*北京工商大學(xué)計算機(jī)與信息工程學(xué)院信息論與編碼103.1編碼的定義信源符號xi符號出現(xiàn)的概率p(xi)碼1碼2碼3碼4碼5x11/4001100x21/41110100101x31/4000010000110x41/411011000000111表3-1不同碼字非奇異碼1、引出奇異碼和非奇異碼的概念。*北京工商大學(xué)計算機(jī)與信息工程學(xué)院信息論與編碼113.1編碼的定義信源符號xi符號出現(xiàn)的概率p(xi)碼1碼2碼3碼4碼5x11/4001100x21/41110100101x31/4000010000110x41/411011000000111表3-1不同碼字非奇異碼1、引出奇異碼和非奇異碼、唯一可譯碼和非唯一可譯碼的概念。2、唯一可譯碼必須滿足什么條件？*北京工商大學(xué)計算機(jī)與信息工程學(xué)院信息論與編碼123.1編碼的定義信源符號xi符號出現(xiàn)的概率p(xi)碼1碼2碼3碼4碼5x11/4001100x21/41110100101x31/4000010000110x41/411011000000111表3-1不同碼字非奇異碼，非唯一可譯碼1、引出奇異碼和非奇異碼、唯一可譯碼和非唯一可譯碼的概念。2、唯一可譯碼必須滿足什么條件？*北京工商大學(xué)計算機(jī)與信息工程學(xué)院信息論與編碼133.1編碼的定義信源符號xi符號出現(xiàn)的概率p(xi)碼1碼2碼3碼4碼5x11/4001100x21/41110100101x31/4000010000110x41/411011000000111表3-1不同碼字1、引出奇異碼和非奇異碼、唯一可譯碼和非唯一可譯碼的概念。2、唯一可譯碼必須滿足什么條件？非奇異碼，唯一可譯碼*北京工商大學(xué)計算機(jī)與信息工程學(xué)院信息論與編碼143.1編碼的定義信源符號xi符號出現(xiàn)的概率p(xi)碼1碼2碼3碼4碼5x11/4001100x21/41110100101x31/4000010000110x41/411011000000111表3-1不同碼字1、引出奇異碼和非奇異碼、唯一可譯碼和非唯一可譯碼的概念。2、唯一可譯碼必須滿足什么條件？非奇異碼，唯一可譯碼、非即時碼*北京工商大學(xué)計算機(jī)與信息工程學(xué)院信息論與編碼153.1編碼的定義信源符號xi符號出現(xiàn)的概率p(xi)碼1碼2碼3碼4碼5x11/4001100x21/41110100101x31/4000010000110x41/411011000000111表3-1不同碼字1、引出奇異碼和非奇異碼、唯一可譯碼和非唯一可譯碼的概念。2、唯一可譯碼必須滿足什么條件？非奇異碼唯一可譯碼即時碼*北京工商大學(xué)計算機(jī)與信息工程學(xué)院信息論與編碼163.1編碼的定義信源符號xi符號出現(xiàn)的概率p(xi)碼1碼2碼3碼4碼5x11/4001100x21/41110100101x31/4000010000110x41/411011000000111表3-1不同碼字1、引出奇異碼和非奇異碼、唯一可譯碼和非唯一可譯碼、非即時碼和即時碼及延長碼的概念。2、唯一可譯碼必須滿足什么條件？*北京工商大學(xué)計算機(jī)與信息工程學(xué)院信息論與編碼173.1編碼的定義信源符號xi符號出現(xiàn)的概率p(xi)碼1碼2碼3碼4碼5x11/4001100x21/41110100101x31/4000010000110x41/411011000000111表3-1不同碼字1、引出奇異碼和非奇異碼、唯一可譯碼和非唯一可譯碼、非即時碼和即時碼及延長碼的概念。2、唯一可譯碼必須滿足什么條件？非奇異碼唯一可譯碼即時碼*北京工商大學(xué)計算機(jī)與信息工程學(xué)院信息論與編碼183.1編碼的定義信源符號xi符號出現(xiàn)的概率p(xi)碼1碼2碼3碼4碼5x11/4001100x21/41110100101x31/4000010000110x41/411011000000111表3-1不同碼字1、引出奇異碼和非奇異碼、唯一可譯碼和非唯一可譯碼、非即時碼和即時碼及延長碼的概念。

2、唯一可譯碼必須滿足什么條件？*北京工商大學(xué)計算機(jī)與信息工程學(xué)院信息論與編碼193.1編碼的定義信源符號xi符號出現(xiàn)的概率p(xi)碼1碼2碼3碼4碼5x11/4001100x21/41110100101x31/4000010000110x41/411011000000111表3-1不同碼字1、引出奇異碼和非奇異碼、唯一可譯碼和非唯一可譯碼、非即時碼和即時碼及延長碼、定長碼和可變長度碼的概念。

2、唯一可譯碼必須滿足什么條件？*北京工商大學(xué)計算機(jī)與信息工程學(xué)院信息論與編碼203.1編碼的定義信源符號xi符號出現(xiàn)的概率p(xi)碼1碼2碼3碼4碼5x11/4001100x21/41110100101x31/4000010000110x41/411011000000111表3-1不同碼字1、引出奇異碼和非奇異碼、唯一可譯碼和非唯一可譯碼、非即時碼和即時碼及延長碼、定長碼和可變長度碼的概念。

2、唯一可譯碼必須滿足什么條件？3、引入平均碼長的概念。*北京工商大學(xué)計算機(jī)與信息工程學(xué)院信息論與編碼213.1編碼的定義信源符號xi符號出現(xiàn)的概率p(xi)碼1碼2碼3碼4碼5x11/4001100x21/41110100101x31/4000010000110x41/411011000000111表3-1不同碼字3、引入平均碼長的概念。平均碼長=2平均碼長=2.5*北京工商大學(xué)計算機(jī)與信息工程學(xué)院信息論與編碼223.1編碼的定義信源符號xi符號出現(xiàn)的概率p(xi)碼1碼2碼3碼4碼5x18/16001100x24/161110100101x33/16000010000110x41/1611011000000111表3-1不同碼字3、引入平均碼長的概念。平均碼長=2平均碼長=29/16*北京工商大學(xué)計算機(jī)與信息工程學(xué)院信息論與編碼233.1編碼的定義信源符號xi符號出現(xiàn)的概率p(xi)碼1碼2碼3碼4碼5x11/16001100x23/161110100101x34/16000010000110x48/1611011000000111表3-1不同碼字3、引入平均碼長的概念。平均碼長=2平均碼長=51/16*北京工商大學(xué)計算機(jī)與信息工程學(xué)院信息論與編碼243.1編碼的定義信源符號xi符號出現(xiàn)的概率p(xi)碼1碼2碼3-1碼4-1碼5x11/16001000000100x23/16111010000101x34/160000100110x48/1611011111表3-1不同碼字3、引入平均碼長的概念說明：符號概率不等時變長編碼的必要性。

平均碼長=2平均碼長=29/16*北京工商大學(xué)計算機(jī)與信息工程學(xué)院信息論與編碼253.1編碼的定義總結(jié)：（1）編碼的定義，引出無失真信源編碼的定義（3）唯一可譯碼必須滿足的條件（2）編碼的分類碼奇異碼非奇異碼非唯一可譯碼唯一可譯碼非即時碼即時碼1）單個符號對應(yīng)不同的碼字（非奇異碼）2）符號序列對應(yīng)的碼元序列在信源譯碼時必須能唯一的分割成所發(fā)的符號序列。（4）符號概率不等時變長編碼的必要性。

*北京工商大學(xué)計算機(jī)與信息工程學(xué)院信息論與編碼263.1編碼的定義定長碼和可變長度碼:固定長度的碼，碼中所有碼字的長度都相同，是定長碼。奇異碼和非奇異碼：若信源符號和碼字是一一對應(yīng)的，則該碼為非奇異碼。反之為奇異碼。唯一可譯碼：任意有限長的碼元序列，只能被唯一地分割成一個個的碼字，便稱為唯一可譯碼。非即時碼和即時碼：如果接收端收到一個完整的碼字后，不能立即譯碼，還需等下一個碼開始接收后才能判斷是否可以譯碼，這樣的碼叫做非即時碼。編碼總結(jié)：*北京工商大學(xué)計算機(jī)與信息工程學(xué)院信息論與編碼273.1編碼的定義碼樹圖及時碼構(gòu)造可通過碼樹來構(gòu)造：00001110*北京工商大學(xué)計算機(jī)與信息工程學(xué)院信息論與編碼283.1編碼的定義用樹的概念可導(dǎo)出唯一可譯碼存在的充分和必要條件，即各碼字的長度Ki應(yīng)符合克勞夫特不等式：式中，m是進(jìn)制數(shù)，n是信源符號數(shù)，Ki是各碼字的長度。*北京工商大學(xué)計算機(jī)與信息工程學(xué)院信息論與編碼293.1編碼的定義例3.1.1設(shè)二進(jìn)制碼樹中X∈｛x1，x2，x3,x4｝，K1=1，K2=2，K3=2，K4=3，應(yīng)用上述判斷定理，可得因此，不存在滿足這種Ki的唯一可譯碼,用樹碼進(jìn)行檢查如右圖。碼字分別為{0，10，11，110}樹碼0001111010011*北京工商大學(xué)計算機(jī)與信息工程學(xué)院信息論與編碼303.1編碼的定義例3.1.1設(shè)二進(jìn)制碼樹中X∈｛x1，x2，x3,x4｝，K1=1，K2=2，K3=3，K4=3，應(yīng)用上述判斷定理，可得因此，存在滿足這種Ki的唯一可譯碼,用樹碼進(jìn)行檢查如下圖。a樹碼000111101001111碼字分別為{0，10，110，111}碼字分別為{0，10，010，111}b樹碼0001101001111110*北京工商大學(xué)計算機(jī)與信息工程學(xué)院信息論與編碼31本節(jié)內(nèi)容回顧作業(yè)：3－1

編碼的含義、編碼的種類。重點(diǎn)強(qiáng)調(diào)以下幾個問題：

1、奇異碼和非奇異碼；定長碼和可變長度碼；唯一可譯碼和唯一可譯碼；非即時碼和即時碼及延長碼的概念。

2、唯一可譯碼必須滿足什么條件？

3、符號概率不等說明可變長度碼編碼的必要性。*北京工商大學(xué)計算機(jī)與信息工程學(xué)院信息論與編碼323.2定長編碼定理定長編碼定理：

由L個符號組成的、每個符號的熵為的無記憶平穩(wěn)信源符號序列，可用KL個符號（每個符號有m種可能值）進(jìn)行定長編碼。對任意ε＞0，δ＞0，只要

則當(dāng)L足夠大時，必可使譯碼差錯小于δ；反之，當(dāng)

時，譯碼差錯一定是有限值，而當(dāng)L足夠大時，譯碼幾乎必定出錯定理證明略。舉例:信源序列X=X1X2（每個Xi可取a1-a4）分別用3、4、5位二元編碼（可傳輸?shù)姆枮?,1）

，說明定理含義。*北京工商大學(xué)計算機(jī)與信息工程學(xué)院信息論與編碼333.2定長編碼定理只要碼字所能攜帶的信息量大于信源序列輸出的信息量，則可以使傳輸幾乎無失真.能達(dá)到差錯率要求,源序列長度L需滿足（由切比雪夫不等式得到的）

定義:編碼效率最佳編碼效率

信源序列的自信息方差*北京工商大學(xué)計算機(jī)與信息工程學(xué)院信息論與編碼343.2定長編碼定理例3-2-1設(shè)離散無記憶信源概率空間為

對該信源進(jìn)行定長二元編碼，要求編碼效率η=90%，并要求譯碼錯誤概率δ≤10-6進(jìn)行能達(dá)到差錯率要求,求信源序列長度L應(yīng)滿足的條件，才能滿足上述要求。

解（1）若對L=1的信源X1進(jìn)行編碼，碼長為3。求η，δ。信源熵：

比特/符號平均碼長：

碼元/信源符號譯碼錯誤概率δ=0.效率：*北京工商大學(xué)計算機(jī)與信息工程學(xué)院信息論與編碼353.2定長編碼定理例3-2-1

解（2）現(xiàn)在要求η

，δ

需要對信源序列進(jìn)行定長二元編碼。信源序列的自信息方差：*北京工商大學(xué)計算機(jī)與信息工程學(xué)院信息論與編碼363.2定長編碼定理例3-2-1

解（2）現(xiàn)在要求η

，δ

需要對信源序列進(jìn)行定長二元編碼。信源序列的編碼效率：無記憶信源有HL(X)=H(X)=2.55說明：當(dāng)L有限時，高傳輸效率的定長編碼往往要引入一定的失真和錯誤。從而引出變長編碼。*北京工商大學(xué)計算機(jī)與信息工程學(xué)院信息論與編碼373.3變長編碼定理單個符號變長編碼定理：

若一離散無記憶信源的符號熵為H(X)，每個信源符號用m進(jìn)制碼元進(jìn)行變長編碼，一定存在一種無失真編碼方法，其碼字平均長度滿足下列不等式

離散平穩(wěn)無記憶序列變長編碼定理（香農(nóng)第一定理）:

對于平均符號熵為HL(X)的離散平穩(wěn)無記憶信源，必存在一種無失真編碼方法，使平均信息率滿足不等式

*北京工商大學(xué)計算機(jī)與信息工程學(xué)院信息論與編碼383.3變長編碼定理設(shè)用m進(jìn)制碼元作變長編碼，序列長度為L個信源符號，序列平均碼字長度滿足下列不等式

已知平均輸出信息率為

編碼效率的下界：碼的剩余度:*北京工商大學(xué)計算機(jī)與信息工程學(xué)院信息論與編碼393.3變長編碼定理例3.3.1設(shè)離散無記憶信源的概率空間如下,求編碼效率?

解:其信源熵為

(1)定長編碼

若用二元定長編碼(0，1)來構(gòu)造一個即時碼：x1→0,x2→1。這時平均碼長

編碼效率為輸出的信息率為

R=0.811比特/二元碼符號*北京工商大學(xué)計算機(jī)與信息工程學(xué)院信息論與編碼403.3變長編碼定理例3.3.1設(shè)離散無記憶信源的概率空間如下,求編碼效率?

解:其信源熵為

(2)變長編碼假定信源序列的長度為L=2,其即時碼如下表。

序列序列概率即時碼

x1x1

9/16

x1x2

x2x1

x2x2

1/16

3/16

3/16*北京工商大學(xué)計算機(jī)與信息工程學(xué)院信息論與編碼413.3變長編碼定理例3.3.1設(shè)離散無記憶信源的概率空間如下,求編碼效率?

解:其信源熵為

(2)變長編碼假定信源序列的長度為L=2,其即時碼如下表。

序列序列概率即時碼

x1x1

9/160

x1x2

x2x1

x2x2

1/16

3/16

3/16

111

110

10*北京工商大學(xué)計算機(jī)與信息工程學(xué)院信息論與編碼423.3變長編碼定理例3.3.1設(shè)離散無記憶信源的概率空間如下,求編碼效率?

解:(2)變長編碼

這個碼的碼字平均長度

編碼效率為

輸出的信息率為R=0.961比特/二元碼符號*北京工商大學(xué)計算機(jī)與信息工程學(xué)院信息論與編碼433.3變長編碼定理例3.3.1設(shè)離散無記憶信源的概率空間如下,求編碼效率?

解:(2)變長編碼

將信源序列的長度增加，L＝3或L=4，對這些信源序列X進(jìn)行編碼，并求出其編碼效率為

信息傳輸率分別為：

R3＝0.985比特／二元碼符號

R4＝0.991比特／二元碼符號*北京工商大學(xué)計算機(jī)與信息工程學(xué)院信息論與編碼443.3變長編碼定理例3.3.1設(shè)離散無記憶信源的概率空間如下,求編碼效率?

解:討論

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

。則自信息的方差:

所需要的信源序列長度*北京工商大學(xué)計算機(jī)與信息工程學(xué)院信息論與編碼453.4最佳編碼(1)最佳碼定義是什么?

凡是能載荷一定的信息量，且碼字的平均長度最短，可分離的變長碼的碼字集合都可稱為最佳碼。

(2)最佳編碼思想是什么?

將概率大的信息符號編以短的碼字，概率小的符號編以長的碼字，使得平均碼字長度最短。

(3)最佳碼的編碼主要方法有哪些?

香農(nóng)（Shannon）、費(fèi)諾（Fano）、哈夫曼（Huffman）編碼等。

*北京工商大學(xué)計算機(jī)與信息工程學(xué)院信息論與編碼463.4最佳編碼3.4.1香農(nóng)編碼方法香農(nóng)第一定理指出，選擇每個碼字的長度Ki滿足下式I(xi)≤Ki＜I(xi)+1，這種編碼方法稱為香農(nóng)編碼。編碼方法如下：(1)

將信源消息符號概率按大小依次排列

(2)

確定滿足下列不等式的整數(shù)碼長Ki：(3)

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

將累加概率Pi變換成二進(jìn)制數(shù)。(5)

取Pi二進(jìn)數(shù)的小數(shù)點(diǎn)后Ki位即為該消息符號的二進(jìn)制碼字。*北京工商大學(xué)計算機(jī)與信息工程學(xué)院信息論與編碼473.4最佳編碼3.4.1香農(nóng)編碼方法例3-4-1設(shè)信源共7個符號消息，其概率和累加概率如表3-4-1所示。*北京工商大學(xué)計算機(jī)與信息工程學(xué)院信息論與編碼48xiP(xi)Pi-logp2(xi)Ki碼字x1x2x3x4x5x6x70.200.190.180.170.150.100.0100.20.390.570.740.890.992.342.412.482.562.743.346.66333334700000101110010111101111110*北京工商大學(xué)計算機(jī)與信息工程學(xué)院信息論與編碼493.4.2費(fèi)諾編碼方法編碼過程如下：

(1)將信源消息符號按其出現(xiàn)的概率大小依次排列：

p(x1)≥p(x2)≥…≥p(xn)。(2)將依次排列的信源符號按概率值分為兩大組，使兩個組的概率之和近于相同，并對各組賦予一個二進(jìn)制碼元“0”和“1”。(3)將每一大組的信源符號進(jìn)一步再分成兩組，使劃分后的兩個組的概率之和近于相同，并又賦予兩個組一個二進(jìn)制符號“0”和“1”。(4)如此重復(fù)，直至每個組只剩下一個信源符號為止。(5)信源符號所對應(yīng)的碼字即為費(fèi)諾碼。*北京工商大學(xué)計算機(jī)與信息工程學(xué)院信息論與編碼503.4.3哈夫曼編碼方法編碼過程如下：

(1)將n個信源消息符號按其出現(xiàn)的概率大小依次排列，

p(x1)≥p(x2)≥…≥p(xn)

(2)取兩個概率最小的字母分別配以0和1兩碼元，并將這兩個概率相加作為一個新字母的概率，與未分配的二進(jìn)符號的字母重新排隊。(3)對重排后的兩個概率最小符號重復(fù)步驟(2)的過程。

(4)不斷繼續(xù)上述過程，直到最后兩個符號配以0和1為止。

(5)從最后一級開始，向前返回得到各個信源符號所對應(yīng)的碼元序列，即相應(yīng)的碼字。*北京工商大學(xué)計算機(jī)與信息工程學(xué)院信息論與編碼513.4.3哈夫曼編碼方法該哈夫曼碼的平均碼長為：信息傳輸速率：

10

11

000

0111*北京工商大學(xué)計算機(jī)與信息工程學(xué)院信息論與編碼523.4.3哈夫曼編碼方法哈夫曼編碼方法得到的碼并非是唯一的。造成非唯一的原因如下：

每次對信源縮減時，賦予信源最后兩個概率最小的符號，用0和1是可以任意的，所以可以得到不同的哈夫曼碼，但不會影響碼字的長度。對信源進(jìn)行縮減時，兩個概率最小的符號合并后的概率與其它信源符號的概率相同時，這兩者在縮減信源中進(jìn)行概率排序，其位置放置次序是可以任意的，故會得到不同的哈夫曼碼。此時將影響碼字的長度，一般將合并的概率放在上面，這樣可獲得較小的碼方差。*北京工商大學(xué)計算機(jī)與信息工程學(xué)院信息論與編碼533.4.3哈夫曼編碼方法例設(shè)有離散無記憶信源哈夫曼編碼方法1*北京工商大學(xué)計算機(jī)與信息工程學(xué)院信息論與編碼543.4.3哈夫曼編碼方法例設(shè)有離散無記憶信源哈夫曼編碼方法2*北京工商大學(xué)計算機(jī)與信息工程學(xué)院信息論與編碼553.4.3哈夫曼編碼方法哈夫曼碼的平均碼長相等,編碼效率也相等但是兩種碼的質(zhì)量不完全相同，可用碼方差來表示：可見，第二種哈夫曼編碼方法得到的碼方差要比第一種哈夫曼編碼方法得到的碼方差小許多。故第二種哈夫曼碼的質(zhì)量要好。*北京工商大學(xué)計算機(jī)與信息工程學(xué)院信息論與編碼563.4.3哈夫曼編碼方法哈夫曼碼是用概率匹配方法進(jìn)行信源編碼。它有兩個明顯特點(diǎn)：一是哈夫曼碼的編碼方法保證了概率大的符號對應(yīng)于短碼，概率小的符號對應(yīng)于長碼，充分利用了短碼；二是縮減信源的最后二個碼字總是最后一位不同，從而保證了哈夫曼碼是即時碼。作業(yè)：3-2、3-11[1、2、3、4、6、7]3-12(1)（注意：3-12中的1文字描述內(nèi)容、3-11的2-4后加上相應(yīng)碼字）*北京工商大學(xué)計算機(jī)與信息工程學(xué)院信息論與編碼57第4章限失真信源編碼4.1平均失真和信息率失真函數(shù)

4.1.1失真函數(shù)

4.1.2平均失真

4.1.3信息率失真函數(shù)

4.1.4信息率失真函數(shù)的性質(zhì)4.2離散信源和連續(xù)信源的計算4.3限失真信源編碼定理4.4常用信源編碼方法簡介

4.4.1游程編碼

4.4.2算術(shù)編碼

4.4.3矢量量化

4.4.4預(yù)測編碼

4.4.5變換編碼習(xí)題*北京工商大學(xué)計算機(jī)與信息工程學(xué)院信息論與編碼584.1平均失真和信息率失真函數(shù)4.1.1失真函數(shù)失真函數(shù)定義:失真矩陣*北京工商大學(xué)計算機(jī)與信息工程學(xué)院信息論與編碼594.1.1失真函數(shù)

例設(shè)信源符號X∈｛0，1｝,編碼器輸出符號Y∈｛0,1,2｝,規(guī)定失真函數(shù)為d(0,0)＝d(1,1)＝0;d(0,1)＝d(1,0)=1;d(0,2)＝d(1,2)＝0.5,求失真矩陣。解:由式得失真矩陣*北京工商大學(xué)計算機(jī)與信息工程學(xué)院信息論與編碼604.1.1失真函數(shù)常用失真函數(shù)均方失真：絕對失真：相對失真：

誤碼失真：失真函數(shù)的定義的推廣*北京工商大學(xué)計算機(jī)與信息工程學(xué)院信息論與編碼614.1.2平均失真平均失真對于連續(xù)隨機(jī)變量的平均失真*北京工商大學(xué)計算機(jī)與信息工程學(xué)院信息論與編碼624.1.3信息率失真函數(shù)D允許信道（D允許的試驗(yàn)信道）對于離散無記憶信道信息率失真函數(shù)R(D)對于離散無記憶信源等效試驗(yàn)信道*北京工商大學(xué)計算機(jī)與信息工程學(xué)院信息論與編碼634.1.3信息率失真函數(shù)例設(shè)信源的符號表為A=｛a1,a2,…,a2n｝,概率分布為p(ai)＝1/2n，i＝1，2，…，2n，失真函數(shù)規(guī)定為由信源概率分布可求出信源熵為設(shè)想采用下面的編碼方案：平均失真D為等效試驗(yàn)信道*北京工商大學(xué)計算機(jī)與信息工程學(xué)院信息論與編碼644.1.3信息率失真函數(shù)由該信道模型知，它是一個確定信道由互信息公式可得

I(X;Y)=H(Y)-H(Y/X)=H(Y)信道輸出概率分布為所以概率分布為則輸出熵H(Y)為*北京工商大學(xué)計算機(jī)與信息工程學(xué)院信息論與編碼654.1.4信息率失真函數(shù)的性質(zhì)1.R(D)函數(shù)的定義域

R(D)的定義域?yàn)镈∈［0，Dmax］2.R(D)函數(shù)的下凸性和連續(xù)性3.R(D)函數(shù)的單調(diào)遞減性例:R(D)在定義域內(nèi)是下凸的,連續(xù)的。R(D)的單調(diào)遞減性可以作如下理解：容許的失真度越大，所要求的信息率越小。*北京工商大學(xué)計算機(jī)與信息工程學(xué)院信息論與編碼664.1.4信息率失真函數(shù)的性質(zhì)得出如下結(jié)論：R(D)是非負(fù)的實(shí)數(shù)，即R(D)≥0。其定義域?yàn)?～Dmax，其值為0～H(X)。當(dāng)D＞Dmax時,R(D)≡0。R(D)是關(guān)于D的下凸函數(shù)，因而也是關(guān)于D的連續(xù)函數(shù)。R(D)是關(guān)于D的嚴(yán)格遞減函數(shù)。*北京工商大學(xué)計算機(jī)與信息工程學(xué)院信息論與編碼674.2離散信源和連續(xù)信源的計算某些特殊情況下R(D)的表示式為：率失真函數(shù)*北京工商大學(xué)計算機(jī)與信息工程學(xué)院信息論與編碼684.2離散信源和連續(xù)信源的計算例4.2.1設(shè)輸入輸出符號表為X=Y=｛0，1｝，輸入概率分布p(x)=｛p，1-p｝，0＜p≤1/2，失真矩陣為

求信息率失真函數(shù)R(D).

解:簡記

(1)按下式解方程

解得*北京工商大學(xué)計算機(jī)與信息工程學(xué)院信息論與編碼694.2離散信源和連續(xù)信源的計算(2)按下式解方程解得(3)得轉(zhuǎn)移概率分布*北京工商大學(xué)計算機(jī)與信息工程學(xué)院信息論與編碼704.2離散信源和連續(xù)信源的計算(4)求s(s=logα)*北京工商大學(xué)計算機(jī)與信息工程學(xué)院信息論與編碼714.2離散信源和連續(xù)信源的計算(5)計算R(D)，將上面各式代入，則有(D)=H(p)-H(D)，p為參數(shù)*北京工商大學(xué)計算機(jī)與信息工程學(xué)院信息論與編碼724.3限失真信源編碼定理限失真信源編碼定理：設(shè)離散無記憶信源X的信息率失真函數(shù)R(D)，則當(dāng)信息率R＞R(D)，只要信源序列長度L足夠長，一定存在一種編碼方法，其譯碼失真小于或等于D+ε，ε為任意小的正數(shù)；反之，若R＜R(D)，則無論采用什么樣的編碼方法，其譯碼失真必大于D。如果是二元信源，對于任意小的ε＞0，每一個信源符號的平均碼長滿足如下公式在失真限度內(nèi)使信息率任意接近R(D)的編碼方法存在。*北京工商大學(xué)計算機(jī)與信息工程學(xué)院信息論與編碼734.4常用信源編碼方法簡介4.4.1游程編碼游程長度在二元序列中，只有兩種符號，即“0”和“1”，這些符號可連續(xù)出現(xiàn)，連“0”這一段稱為“0”游程，連“1”這一段稱為“1”游程。它們的長度分別稱為游程長度L(0)和L(1).

對于多元序列也存在相應(yīng)的游程序列。例如m元序列中，可有m種游程。連著出現(xiàn)符號ar的游程，其長度L(r)就是“r”游程長度。設(shè)有多元信源序列(x1，x2，…，xm1，y，y，…，y，xm1+1，xm1+2，…xm2，y，y，…其中x是含有信息的代碼，取值于m元符號集A，可稱為信息位；y是冗余位，它們可為全零，即使未曾傳送在收端也能恢復(fù)。這樣的序列可用下列兩個序列來代替：

111，…，100，…，000111，…，111000和

x1，x2，…，xm1，xm1+1，xm1+2，…xm2，…

前一個序列中，用“1”表示信息位，用“0”表示冗余位；后一個序列是取消冗余位后留下的所有信息位。*北京工商大學(xué)計算機(jī)與信息工程學(xué)院信息論與編碼744.4.2算術(shù)編碼算術(shù)編碼的基本思路從全序列出發(fā)，將各信源序列的概率映射到［0，1］區(qū)間上，使每個序列對應(yīng)這區(qū)間內(nèi)的一點(diǎn)，也就是一個二進(jìn)制的小數(shù)。積累概率則例如有一序列S=011，這種三個二元符號的序列可按自然二進(jìn)數(shù)排列，000，001，010，……，則S的積累概率為

P(S)=p(000)+p(001)+p(010)如果S后面接一個“0”，積累概率就成為

P(S0)=p(0000)+p(0001)+p(0010)+p(0011)+p(0100)+p(0101)=p(000)+p(001)+p(010)=P(S)

信源的符號概率和積累概率*北京工商大學(xué)計算機(jī)與信息工程學(xué)院信息論與編碼754.4.2算術(shù)編碼如果S后面接一個“1”，則其積累概率是

P(S1)=p(0000)+p(0001)+p(0010)+p(0011)+p(0100)+p(0101)+p(0110)=P(S)+p(0110)=P(S)+p(S)p0上面兩式可統(tǒng)一寫作一般的遞推公式序列的概率的公式

*北京工商大學(xué)計算機(jī)與信息工程學(xué)院信息論與編碼764.4.2算術(shù)編碼實(shí)用中，采用積累概率P(S)表示碼字C(S)，符號概率p(S)表示狀態(tài)區(qū)間A(S)，則有實(shí)際編碼過程:

先置兩個存儲器C和A，起始時可令其中代表空集。每輸入一個信源符號，存儲器C和A就按照上式更新一次，直至程序結(jié)束，就可將存儲器C的內(nèi)容作為碼字輸出。*北京工商大學(xué)計算機(jī)與信息工程學(xué)院信息論與編碼774.4.2算術(shù)編碼例4.4.1有簡單的四個符號a，b，c，d構(gòu)成序列S=abda，各符號及其對應(yīng)概率如表算術(shù)編解碼過程如下:設(shè)起始狀態(tài)為空序列φ，則A(φ)=1，C(φ)=0。表4-4-1各符號及其對元概率符號符號符號概率pi符號概率pi符號累積概率Pj符號累積概率Pjabcd0.100(1/2)0.010(1/4)0.001(1/8)0.001(1/8)0.0000.1000.1100.111*北京工商大學(xué)計算機(jī)與信息工程學(xué)院信息論與編碼784.4.2算術(shù)編碼算術(shù)碼編碼過程*北京工商大學(xué)計算機(jī)與信息工程學(xué)院信息論與編碼794.4.2算術(shù)編碼據(jù)遞推公式的相反過程譯出符號。具體譯碼順序是后編的先譯，故稱為LIFO算術(shù)碼，步驟如下：C(abda)=0.010111＜01∈［0,0.1)第一個符號為a；放大至［0,1)