g第5章：信源編碼1

第五章信源編碼通信系統(tǒng)的優(yōu)化模型n信源信源編碼加密信道編碼信源譯碼信道譯碼信道解密信宿密鑰源噪聲密鑰源ULVLULSmCmXnYnC’mS’mVLK1K2本章內(nèi)容離散信源編碼連續(xù)信源編碼5.1離散信源編碼編碼的基本概念碼的分類定長編碼定理變長編碼定理香農(nóng)編碼費諾編碼赫夫曼編碼{a1,a2,…,aK}為信源符號集，序列中每一個符號uml都取自信源符號集。{b1

，b2

，…，bD}是適合信道傳輸?shù)腄個符號，用作信源編碼器的編碼符號。編碼輸出碼字cm=cm1cm2…

cmn，cmk∈{b1

，b2

，…，bD}k=1,2,

…,n，n表示碼字長度，簡稱碼長

信源符號{a1,a2,…,aK}

信道符號（碼符號）{b1,b2,…,bD}

信源編碼器

ui=ui1ui2…

uiL

碼字ci=ci1ci2…

cin

1、編碼的基本概念信源符號集={我,

是,一名，學(xué)生，老師，編碼，理論,…}

信道符號集={I

，am，is,are,a,student,coding,theory,apple,…}如果某次該編碼器的輸入是“我是一名學(xué)生”，即輸入序列ui

=(ui1=“我”，ui2=“是”，ui3=“一名”

，ui4=“學(xué)生”)，編碼器的輸出“Iamastudent”，即輸出序列ci=(ci1=“I”,

ci2=“am”,

ci3

=“a”,

ci4

=“student”)

信源編碼可看成是從信源符號集到碼符號集的一種映射，即將信源符號集中的每個元素（可以是單符號，也可以是符號序列）映射成一個長度為n的碼字。對于同一個信源，編碼方法是多種的?！纠?.1】

用{u1

，u2

，u3，u4，}表示信源的四個消息，碼符號集為{0,1}，表1列出了該信源的幾種不同編碼。表1同一信源的幾種不同編碼2、編碼的分類信源消息各消息概率碼1碼2碼3碼4u1q(u1)000001u2q(u2)1101110u3q(u3)101000100u4q(u4)1111111000碼510100100013.變長碼若碼字集合C中的所有碼字cm(m=1,2,…,M)，其碼長不都相同，稱碼C為變長碼，表1中列出的碼3、碼4和碼5就是變長碼。2.等長碼在一組碼字集合C中的所有碼字cm(m=1,2,…,M)，其碼長都相同，則稱這組碼C為等長碼，表1中列出的碼1、碼2就碼長n=2等長碼一般，可以將碼簡單的分成如下幾類：1.二元碼若碼符號集為{0，1}，則碼字就是二元序列，稱為二元碼,二元碼通過二進(jìn)制信道傳輸，這是數(shù)字通信和計算機(jī)通信中最常見的一種碼，表1列出的5種碼都是二元碼。5.非奇異碼從信源消息到碼字的影射是一一對應(yīng)的，每一個不同的信源消息都用不同的碼字對其編碼，例表1中的碼2、碼3、碼4和碼5都是非奇異碼。4.奇異碼對奇異碼來說，從信源消息到碼字的影射不是一一對應(yīng)的。例表1中的碼1，信源消息u2和u4都用碼字11對其編碼，因此這種碼就是奇異碼，奇異碼不具備惟一可譯性。

6）唯一可譯碼：若碼的任意一串有限長的碼符號序列只能唯一地被譯成所對應(yīng)的信源符號序列，則此碼稱為唯一可譯碼，否則就稱為非唯一可譯碼。等長碼非奇異碼00011011唯一可譯如果接收端收到一個完整的碼字后，不能立即譯碼，還要等下一個碼字開始接收后才能判斷是否可以譯碼，這樣的碼叫做非即時碼。7非即時碼：非奇異碼11010010001001不即時任何一個碼字是其它碼字的延長或前綴如果收到一個完整的碼字以后，就可以立即譯碼，則叫做即時碼。即時碼要求任何一個碼字都不是其他碼字的前綴部分，也叫做異前綴碼。8、即時碼非奇異碼1010010001任何一個碼字不是其它碼字的延長或前綴即時碼01即時即時碼的判決準(zhǔn)則克拉夫特不等式：設(shè)信源為，對其進(jìn)行r元信源編碼，相應(yīng)碼字長度為，則即時碼存在的充要條件是：唯一可譯碼的判決準(zhǔn)則麥克米倫不等式：設(shè)信源為，對其進(jìn)行r元信源編碼，相應(yīng)碼字長度為，則唯一可譯碼存在的充要條件是：不同編碼方式的衡量標(biāo)準(zhǔn)平均碼長：對離散無記憶信源進(jìn)行信源編碼，設(shè)編碼后各個碼字的碼長分別為，則定義該碼的平均碼長為：如果某種編碼方式的平均碼長小于所有其他編碼方式，則該碼稱為緊致碼或最佳碼。編碼信息率(編碼速率)：碼長

表示長為N的信源序列用多少個r進(jìn)制碼符號表示，因此表示平均一個信源符號用多少個r進(jìn)制符號表示，再乘以表示將r進(jìn)制轉(zhuǎn)換成二進(jìn)制編碼效率：含義：理論上平均每個信源符號用多少個二進(jìn)制符號的個數(shù)除以實際上用的二進(jìn)制碼符號的個數(shù)，即表示一種編碼的效率。有時消息太多，不可能或者沒必要給每個消息都分配一個碼字；給多少消息分配碼字可以做到幾乎無失真譯碼？傳送碼字需要一定的信息率，碼字越多，所需的信息率越大。編多少碼字的問題可以轉(zhuǎn)化為對信息率大小的問題；信息率越小越好，最小能小到多少才能做到無失真譯碼呢？這些問題就是信源編碼定理要研究的問題。

碼字與信息率的關(guān)系

信源編碼有定長和變長兩種方法。定長編碼：碼字長度K

是固定的，相應(yīng)的編碼定理稱為定長信源編碼定理，是尋求最小K值的編碼方法。變長編碼：K是變值，相應(yīng)的編碼定理稱為變長編碼定理。這里的K值最小意味著數(shù)學(xué)期望最小。信源編碼的方法定長編碼定理：一個熵為H(X)的離散無記憶信源X1X2…Xl…XN，若對信源長為N的符號序列進(jìn)行定長編碼，設(shè)碼字是從m個字母的碼符號集中，選取K個碼元組成Y1Y2…Yk…YK。對于任意ε>0，δ>0，只要滿足則當(dāng)N足夠大時，必可使譯碼差錯小于δ，即譯碼錯誤概率能為任意小.反之，若：

則不可能實現(xiàn)無失真編碼，而當(dāng)N足夠大時，譯碼錯誤概率近似等于1.3、定長編碼定理定理中的公式改寫成：Klog2m>NH(X)

Klog2m：表示長為K

的碼符號序列能載荷的最大信息量NH(X)

：代表長為N

的信源序列平均攜帶的信息量平均符號熵。

定長編碼定理告訴我們：只要碼字傳輸?shù)男畔⒘看笥谛旁磾y帶的信息量，總可實現(xiàn)幾乎無失真編碼?？梢宰C明：信源編碼定理從理論上說明了編碼效率接近于1，即：的理想編碼器的存在性，代價是在實際編碼時取無限長的信源符號(N→∞)進(jìn)行統(tǒng)一編碼。說明：定長編碼定理是在平穩(wěn)無記憶離散信源的條件下論證的，但它同樣適用于平穩(wěn)有記憶信源，只是要求有記憶信源的極限熵和極限方差存在即可。對于平穩(wěn)有記憶信源，定理中的熵應(yīng)改為極限熵。[例]：設(shè)單符號信源模型為：其信息熵為：H(X)=2.55（比特／符號）

σ2(x)=1.323若要求編碼效率為η

=90%，即：譯碼差錯率為δ=10－6，則ε=0.28，在差錯率和效率要求都不苛刻的情況下，就必須有1600多萬個信源符號一起編碼，技術(shù)實現(xiàn)非常困難。[例]：離散無記憶信源：其信息熵為：自信息的方差為：若對信源X采取等長二元編碼時，要求η=0.96，δ=10－5信源序列長度需長達(dá)4130萬以上，才能實現(xiàn)給定的要求，這在實際中很難實現(xiàn)。一般來說，當(dāng)N

有限時，高傳輸效率的等長碼往往要引入一定的失真和錯誤，它不能像變長碼那樣可以實現(xiàn)無失真編碼。(1)基本概念(2)碼樹圖(3)變長編碼定理

4、變長編碼定理(1)基本概念變長編碼（不等長編碼）：不等長編碼允許把等長的消息變換成不等長的碼序列。通常把經(jīng)常出現(xiàn)的消息編成短碼，不常出現(xiàn)的消息編成長碼。這樣可使平均碼長最短，從而提高通信效率，代價是增加了編譯碼設(shè)備的復(fù)雜度。例如：在不等長碼字組成的序列中要正確識別每個長度不同的碼字的起點就比等長碼復(fù)雜得多。譯碼延時／譯碼同步：接收到一個不等長碼序列后，有時不能馬上斷定碼字是否真正結(jié)束，因而不能立即譯出該碼，要等到后面的符號收到后才能正確譯出。[例]：碼1：顯然不是惟一可譯碼。x2

和x4

對應(yīng)于同一碼字“11”，碼1

是一個奇異碼。碼2：是非奇異碼，不是惟一可譯碼。當(dāng)收到一串碼符號“01000”時，可將它譯成“x4x3x1”，也可譯為“x4x1x3”，“x1x2x3”或“x1x2x1x1”等，這種碼從單個碼字來看雖然不是奇異的，但從有限長的碼序列來看，它仍然是一個奇異碼。[例]：碼3：雖然是惟一可譯碼，但它要等到下一個“1”收到后才能確定碼字的結(jié)束，譯碼有延時。碼4：既是惟一可譯碼，又沒有譯碼延時。碼字中的符號“1”起了逗點的作用，故稱為逗點碼。即時碼/前綴條件碼/異前置碼/異字頭碼/逗點碼/非延長碼：如果一個碼的任何一個碼字都不是其它碼字的前綴。碼4是即時碼

(2)碼樹圖

m

元（m

進(jìn)制）碼樹圖樹根：最頂部畫一個起始點。樹枝：從根部引出

m

條線段，每條線段都稱為樹枝。一級節(jié)點：自根部起,通過一條樹枝到達(dá)的節(jié)點。一級節(jié)點最多有m

個.n級節(jié)點：通過

n

條樹枝達(dá)到的節(jié)點。最多有mn。終節(jié)點/終端節(jié)點：下面不再有樹枝的節(jié)點。中間節(jié)點：除了樹根和終節(jié)點以外的節(jié)點。聯(lián)枝：串聯(lián)的樹枝。滿樹：在碼樹圖中，當(dāng)每一個碼字的串聯(lián)枝數(shù)都相同時，就是定長碼。此時的碼樹稱為滿樹。

例如：碼長為N的滿樹的終節(jié)點個數(shù)為mN，即可表示mN個碼字。非滿樹：有些樹枝未用時的碼樹。

非滿樹構(gòu)造的就是變長碼。如果每一個碼字都被安排在終節(jié)點上,這種碼就是即時碼。(3)變長編碼定理①變長編碼定理（香農(nóng)第一定理）平均碼長：變長編碼定理：若一離散無記憶信源的平均符號熵為H(X)，對信源符號進(jìn)行

m元變長編碼，一定存在一種無失真編碼方法，其碼字平均長度滿足下列不等式：其平均信息率滿足不等式

H(X)+ε>R≥H(X)，式中ε為任意正數(shù)。多符號情況對于平穩(wěn)無記憶信源來說，當(dāng)信源輸出的是長度為N的消息序列時，容易證明定理中式子可改進(jìn)為：這時的代表平均碼序列長度。證明：多符號情況已知編碼后平均每個信源符號能載荷的最大信息量為（不等長信源編碼信源平均輸出信息率）：對信源進(jìn)行變長編碼一般所要求的信源符號長度N

比定長編碼小的多。①變長編碼定理（香農(nóng)第一定理）信道的信息傳輸率為（從信道的角度看）：編碼效率定義為：二元無損無噪信道中m=2，所以Hm(X)=H(X)[例]：設(shè)單符號信源模型為：其信息熵為：H(X)=2.55（比特/符號）這里m=2，log2m=1要求η>90%，則：[例]：與定長編碼相比，對同一信源，要求編碼效率都達(dá)到90%

時，變長編碼只需N=4

進(jìn)行編碼，而等長碼則要求N

大于1.6875×107。用變長編碼時,N不需要很大就可以達(dá)到相當(dāng)高的編碼效率而且可實現(xiàn)無失真編碼。[例]：離散無記憶信源：其信息熵為：用二元碼符號(0,1)來構(gòu)造一個即時碼：x1→0，x2→1這時平均碼長：編碼效率為：信道信息傳輸率為：R=0.811比特/二元碼符號[例]：為了提高傳輸效率，對無記憶信源X

的二次擴(kuò)展信源X2進(jìn)行編碼，下面給出擴(kuò)展信源X2

及其某一個即時碼：這個碼的平均長度為：信源符號X中每一單個符號的平均碼長為：[例]：其編碼效率為：信息傳輸速率為：編碼復(fù)雜了一些，但信息傳輸率有了提高。對信源X的三次和四次擴(kuò)展信源進(jìn)行編碼，編碼效率為：信息傳輸率為：[例]：與定長碼比較：對于同一信源，要求編碼效率都達(dá)到96%時，變長碼只需對二次擴(kuò)展信源（N=2）進(jìn)行編碼，而等長碼則要求N>4.13×107。結(jié)論用變長碼編碼時，L不需要很大就可以達(dá)到相當(dāng)高的編碼效率，而且可以實現(xiàn)無失真編碼。隨著擴(kuò)展信源次數(shù)的增加，編碼的效率越來越接近于1比特/二元碼符號，達(dá)到信源與信道匹配，使信道得到充分利用。設(shè)離散無記憶信源：5、香農(nóng)編碼二進(jìn)制香農(nóng)碼的編碼步驟如下：將信源符號按概率從大到小的順序排列，為方便起見，令：p(x1)≥p(x2)≥…≥p(xn)

令p(x0)=0，用pa(xj)，j=i+1表示第i個碼字的累加概率，則：確定滿足下列不等式的整數(shù)ki，并令ki為第i個碼字的長度－log2

p(xi)≤ki<1－log2

p(xi)

將pa(xj)用二進(jìn)制表示，并取小數(shù)點后ki

位作為符號xi的編碼。[例6.1.1]：有一單符號離散無記憶信源：對該信源編二進(jìn)制香農(nóng)碼。計算出給定信源香農(nóng)碼的平均碼長：若對上述信源采用等長編碼，要做到無失真譯碼，每個符號至少要用3個比特表示。相比較，香農(nóng)編碼對信源進(jìn)行了壓縮。由離散無記憶信源熵定義，可計算出信源上熵為：對上述信源采用香農(nóng)編碼的信息率為：編碼效率為信源熵和信息率之比。則：可以看出，編碼效率并不是很高。將概率按從大到小的順序排列，令：p(x1)≥p(x2)≥…≥p(xn)按編碼進(jìn)制數(shù)將概率分組，使每組概率盡可能接近或相等。如編二進(jìn)制碼就分成兩組，編m進(jìn)制碼就分成m組。給每一組分配一位碼元。將每一分組再按同樣原則劃分，重復(fù)步驟2和3，直至概率不再可分為止。6、費諾編碼[例6.3.1]：設(shè)有一單符號離散信源對該信源編二進(jìn)制費諾碼。表二進(jìn)制費諾編碼

信源符號

概率

編碼

碼字

碼長

x1

0.25

0

00

2

x2

0.25

0

1

01

2

x3

0.20

0

10

2

x4

0.15

0

110

3

x5

0.10

0

1110

4

x6

0.05

1

1

1

1

1111

4

該信源的熵為：平均碼長為：對上述信源采用費諾編碼的信息率為：編碼效率為：本例中費諾編碼有較高的編碼效率。費諾碼比較適合于每次分組概率都很接近的信源。特別是對每次分組概率都相等的信源進(jìn)行編碼時，可達(dá)到理想的編碼效率。[例6.3.2]：有一單符號離散無記憶信源對該信源編二進(jìn)制費諾碼，編碼過程如下表。信源熵為：H(X)=2.75(比特/符號)平均碼長為：編碼效率為η=1。之所以如此，因為每次所分兩組的概率恰好相等。哈夫曼(Huffman)編碼是一種效率比較高的變長無失真信源編碼方法。7、哈弗曼編碼編碼步驟(1)將信源符號按概率從大到小的順序排列，令：p(x1)≥p(x2)≥…≥p(xn)(2)

信源的第一次縮減信源：給兩個概率最小的信源符號p(xn－1)和p(xn)各分配一個碼位“0”和“1”，將這兩個信源符號合并成一個新符號，并用這兩個最小的概率之和作為新符號的概率，結(jié)果得到一個只包含(n－1)個信源符號的新信源，用S1表示。(3)將縮減信源S1的符號仍按概率從大到小順序排列，重復(fù)步驟(2)，得到只含(n－2)個符號的縮減信源S2。(4)重復(fù)上述步驟，直至縮減信源只剩兩個符號為止，此時所剩兩個符號的概率之和必為1。然后從最后一級縮減信源開始，依編碼路徑向前返回，就得到各信源符號所對應(yīng)的碼字。[例]設(shè)單符號離散無記憶信源如下，要求對信源編二進(jìn)制哈夫曼碼。在圖中讀取碼字的時候，一定要從后向前讀，此時編出來的碼字才是可分離的異前置碼。若從前向后讀取碼字，則碼字不可分離。信源熵為：平均碼長為：編碼效率為：若采用定長編碼，碼長K=3，則編碼效率：哈夫曼的編碼效率提高了12.7%。注意：哈夫曼的編法并不唯一。每次對縮減信源兩個概率最小的符號分配“0”和“1”碼元是任意的，所以可得到不同的碼字。只要在各次縮減信源中保持碼元分配的一致性，即能得到可分離碼字。不同的碼元分配，得到的具體碼字不同，但碼長ki不變，平均碼長也不變，所以沒有本質(zhì)區(qū)別；縮減信源時，若合并后的新符號概率與其他符號概率相等，從編碼方法上來說，這幾個符號的次序可任意排列，編出的碼都是正確的，但得到的碼字不相同。不同的編法得到的碼字長度ki也不盡相同。

[例]：單符號離散無記憶信源用兩種不同的方法對其編二進(jìn)制哈夫曼碼。方法一：合并后的新符號排在其它相同概率符號的后面。

方法二：合并后的新符號排在其它相同概率符號的前面。單符號信源編二進(jìn)制哈夫曼碼，編碼效率主要決定于信源熵和平均碼長之比。對相同的信源編碼，其熵是一樣的，采用不同的編法，得到的平均碼長可能不同。平均碼長越短，編碼效率就越高。編法一的平均碼長為：編法二的平均碼長為：可見，本例兩種編法的平均碼長相同，所以編碼效率相同。討論：碼字長度的方差σ2：長度ki與平均碼長之差的平方的數(shù)學(xué)期望，即：編法一碼字長度方差：編法二碼字長度方差：哪種方法更好？比較：第二種編碼方法的碼長方差要小許多。第二種編碼方法的碼長變化較小，比較接近于平均碼長。第一種方法編出的5個碼字有4種不同的碼長；第二種方法編出的碼長只有兩種不同的碼長；第二種編碼方法更簡單、更容易實現(xiàn)，所以更好。結(jié)論：在哈夫曼編碼過程中，對縮減信源符號按概率由大到小的順序重新排列時，應(yīng)使合并后的新符號盡可能排在靠前的位置，這樣可使合并后的新符號重復(fù)編碼次數(shù)減少，使短碼得到充分利用。m進(jìn)制哈夫曼編碼對如下單符號離散無記憶信源編三進(jìn)制哈夫曼碼.m進(jìn)制哈夫曼編碼對m進(jìn)制編碼，可分離的碼字?jǐn)?shù)必為即信源所含有的符號數(shù)為上值，如果不等于，則必須增加s個不用的碼字，此時s<m-1當(dāng)有s個碼字不用時，第一次對最小概率符號分配碼元時就只取(m-s)個，分別配以0,1，…，m-s-1，把這些符號的概率相加作為一個新符號的概率，與其他符號一起重新排列。以后每次就可以取m個符號，分別配以0,1，…，m-1[例]設(shè)單符號離散無記憶信源如下，要求對信源編三進(jìn)制哈夫曼碼。平均碼長為：信息率為：編碼效率為：可見：哈夫曼的編碼效率相當(dāng)高，對編碼器的要求也簡單得多。結(jié)論香農(nóng)碼、費諾碼、哈夫曼碼都考慮了信源的統(tǒng)計特性，使經(jīng)常出現(xiàn)的信源符號對應(yīng)較短的碼字，使信源的平均碼長縮短，從而實現(xiàn)了對信源的壓縮；香農(nóng)碼有系統(tǒng)的、唯一的編碼方法，但在很多情況下編碼效率不是很高;費諾碼和哈夫曼碼的編碼方法都不唯一；費諾碼比較適合于對分組概率相等或接近的信源編碼，費諾碼也可以編m進(jìn)制碼，但m越大，信源的符號數(shù)越多，可能的編碼方案就越多，編碼過程就越復(fù)雜，有時短碼未必能得到充分利用；哈夫曼碼對信源的統(tǒng)計特性沒有特殊要求，編碼效率比較高，對編碼設(shè)備的要求也比較簡單，因此綜合性能優(yōu)于香農(nóng)碼和費諾碼。定理1：對于熵為H(U)的離散無記憶信源，若對其進(jìn)行r元信源編碼，則一定存在一種編碼方式構(gòu)成唯一可譯碼，其平均碼長滿足：6、無失真編碼定理---香農(nóng)第一定理熵除以logr只是為了將熵的單位轉(zhuǎn)換到r進(jìn)制，以保持與平均碼長的單位統(tǒng)一，因此上式可寫成：如果是二元編碼，要構(gòu)成唯一可譯碼，平均碼長要處在信源熵和信源熵加1之間。定理2：無失真信源編碼定理(香農(nóng)第一定理)離散無記憶信源U的N次擴(kuò)展信源UN，對該擴(kuò)展信源UN進(jìn)行r元信源編碼，總可以找到一種編碼方式構(gòu)成唯一可譯碼，使信源UN中每個信源符號(即長度為N的信源序列)所需的平均碼長滿足：5.2限失真信源編碼(1)“消息完全無失真?zhèn)魉汀钡目蓪崿F(xiàn)性信道編碼定理：無論何種信道，只要信息率R小于信道容量C，總能找到一種編碼，使在信道上能以任意小的錯誤概率和任意接近于C的傳輸率來傳送信息。反之，若R>C，則傳輸總要失真。完全無失真?zhèn)魉筒豢蓪崿F(xiàn)實際的信源常常是連續(xù)的，信息率無限大，要無失真?zhèn)魉鸵笮诺廊萘緾

為無窮大；實際信道帶寬是有限的，所以信道容量受限制。要想無失真?zhèn)鬏?，所需的信息率大大超過信道容量R>>C。(2)實際中允許一定程度的失真實際生活中，人們一般并不要求獲得完全無失真的消息，通常只要求近似地再現(xiàn)原始消息，即允許一定的失真存在。打電話：即使語音信號有一些失真，接電話的人也能聽懂。人耳接收信號的帶寬和分辨率是有限的。放電影：理論上需要無窮多幅靜態(tài)畫面，由于人眼的“視覺暫留性”，實際上只要每秒放映24幅靜態(tài)畫面。有些失真沒有必要完全消除。既然允許一定的失真存在，對信息率的要求便可降低。(3)信息率失真理論

信息率失真理論研究的內(nèi)容:信息率與允許失真之間的關(guān)系.

信息率失真函數(shù)香農(nóng)定義了信息率失真函數(shù)

R(D)。

“保真度準(zhǔn)則下的信源編碼定理”指出：在允許一定失真度D的情況下，信源輸出的信息率可壓縮到R(D)。信息率失真理論是量化（模數(shù)轉(zhuǎn)換）、數(shù)模轉(zhuǎn)換、頻帶壓縮和數(shù)據(jù)壓縮的理論基礎(chǔ)。

(3)信息率失真理論信息率失真函數(shù)極小值問題

I(X;Y)

是P(X)

和P(Y/X)

的二元函數(shù)；

在討論信道容量時：規(guī)定了P(Y/X)，I(X;Y)變成了P(X)的函數(shù)。在離散情況下，因為I(X;Y)對p(xi)是上凸函數(shù)，所以變更p(xi)所求極值一定是I(X;Y)的極大值；在連續(xù)情況下，變更信源P(X)求出的也是極大值，但求極值時還要一些其它的限制條件。(3)信息率失真理論信息率失真函數(shù)極小值問題

在討論信息率時：可規(guī)定p(xi)，變更p(yj/xi)來求平均互信息的極值，稱為信道容量對偶問題。由于I(X;Y)是p(yj/xi)的下凸函數(shù)，所求的極值一定是極小值。但若X和Y相互統(tǒng)計獨立（p(yj/xi)=p(yj)），這個極小值就是0，因為I(X;Y)是非負(fù)的，0必為極小值，這樣求極小值就沒意義了。引入一個失真函數(shù)，計算在失真度一定的情況下信息率的極小值就變的有意義了。失真的度量信息率失真函數(shù)離散信源的信息率失真函數(shù)連續(xù)信源的信息率失真函數(shù)限失真信源編碼定理---香農(nóng)第三定理5.2.1信息的度量(1)失真度(2)常用失真函數(shù)(3)平均失真度（1）失真度設(shè)離散無記憶信源為：失真的度量失真度對每一對(xi,yj)，指定一個非負(fù)函數(shù)d(xi,yj)≥0i=1,2,…,n

j=1,2,…,m稱d(xi,yj)

為單個符號的失真度（失真函數(shù)）。表示信源發(fā)出一個符號xi，在接收端再現(xiàn)yj所引起的誤差或失真。失真矩陣失真度還可表示成矩陣的形式稱[D]

為失真矩陣。它是

n×m

階矩陣。連續(xù)信源和連續(xù)信道的失真函數(shù)在連續(xù)信源和連續(xù)信道情況下，失真度定義為：d(x,y)≥0（2）常用的失真函數(shù)第一種：當(dāng)i=j時，X與Y的取值一樣，用Y來代表X就沒有誤差，所以定義失真度為0；當(dāng)i≠j時，用Y代表X就有誤差。這種定義認(rèn)為對所有不同的i和j引起的誤差都一樣，所以定義失真度常數(shù)a。特點：對角線上的元素均為0，對角線以外的其它元素都為常數(shù)a。

漢明失真函數(shù)：

a=1。第二種（平方誤差失真函數(shù)）：d(xi,yj)=(yj－xi)2

失真矩陣：平方誤差失真矩陣。若信源符號代表輸出信號的幅度值，則較大的幅度失真比較小的幅度失真引起的錯誤更為嚴(yán)重,嚴(yán)重程度用平方表示.第三種（絕對失真函數(shù)）：

失真矩陣：絕對失真矩陣。反映信宿接收幅值偏離信源發(fā)出幅值的程度

第四種（相對失真函數(shù)）：

失真矩陣：相對失真矩陣。反映信宿收到信息后主觀感覺上的失真程度

二元對稱信源漢明失真函數(shù)為接收變量失真矩陣為表示：當(dāng)發(fā)送信源符號0(或符號1)而接收后再現(xiàn)的仍是符號0(或符號1)時，則認(rèn)為無失真存在，反之，則認(rèn)為有錯誤存在信源失真函數(shù)為接收變量失真矩陣為信源失真函數(shù)為接收變量失真矩陣為（3）平均失真度平均失真度

d(xi,yj)只能表示兩個特定的具體符號xi和yj之間的失真。

平均失真度：失真度的數(shù)學(xué)期望，即：平均失真度的意義是在平均意義上，從總體上對整個系統(tǒng)失真情況的描述。它是信源統(tǒng)計特性p(xi)

、信道統(tǒng)計特性p(yj/xi)

和失真度d(xi,yj)

的函數(shù)。當(dāng)p(xi)，p(yj/xi)和d(xi,yj)給定后，平均失真度就不是一個隨機(jī)變量了，而是一個確定的量。如果信源和失真度一定，就只是信道統(tǒng)計特性的函數(shù)。信道傳遞概率不同，平均失真度隨之改變。二元等概信源失真函數(shù)為漢明失真函數(shù)通過信道P傳輸失真矩陣為求平均失真度保真度準(zhǔn)則人們所允許的失真指的都是平均意義上的失真。

保真度準(zhǔn)則：規(guī)定平均失真度不能超過某一限定的值D，即，則D就是允許失真的上界。該式稱為保真度準(zhǔn)則。

N次擴(kuò)展信道的平均失真度單符號離散無記憶信源X{x1,x2,…,xn}的N次擴(kuò)展信源XN

=X1X2…XN

，在信道中的傳遞作用相當(dāng)于單符號離散無記憶信道的N次擴(kuò)展信道，輸出也是一個隨機(jī)變量序列YN=Y1Y2…YN

。此時輸入共有nN個不同的符號：信道的輸出共有mN個不同的符號：

定義離散無記憶信道{X

P(Y/X)Y}的N次擴(kuò)展信道的輸入序列ai和輸出序列bj之間的失真函數(shù)：定義的說明：離散無記憶信道的N次擴(kuò)展信道輸入輸出之間的失真，等于輸入序列ai中N個信源符號xi1,xi2,…,xiN各自通過信道{X

P(Y/X)Y}，分別輸出對應(yīng)的N個信宿符號yj1,yj2,…,yjN后所引起的N個單符號失真d(xik,yjk)(k=1,2,…,N)之和。

N次離散無記憶擴(kuò)展信源和信道的平均失真度為，則：

“N次擴(kuò)展”與“單符號”平均失真度的關(guān)系由擴(kuò)展信源和擴(kuò)展信道的無記憶性有：

“N次擴(kuò)展”與“單符號”平均失真度的關(guān)系（k=1,2,…,N）是同一信源X在N個不同時刻通過同一信道{X

P(Y/X)Y}所造成的平均失真度，因此都等于單符號信源X通過信道{X

P(Y/X)Y}所造成的平均失真度，即：

結(jié)論說明：離散無記憶N次擴(kuò)展信源通過離散無記憶N次擴(kuò)展信道的平均失真度是單符號信源通過單符號信道的平均失真度的N倍。

N次擴(kuò)展的保真度準(zhǔn)則：離散無記憶N次擴(kuò)展信源通過離散無記憶N次擴(kuò)展信道的保真度準(zhǔn)則為：5.2.2信息率失真函數(shù)(1)試驗信道(2)信息率失真函數(shù)(3)求信息率失真函數(shù)的方法(4)研究信道容量和率失真函數(shù)的意義(5)信息率失真函數(shù)的性質(zhì)(1)試驗信道單符號信源和單符號信道的試驗信道當(dāng)固定信源（P(X)已知），單個符號失真度也給定時，選擇信道使。凡滿足要求的信道稱為D失真許可的試驗信道，簡稱試驗信道。所有試驗信道構(gòu)成的集合用PD

來表示，即：(1)試驗信道

N次擴(kuò)展的試驗信道：對于離散無記憶信源的N次擴(kuò)展信源和離散無記憶信道的N次擴(kuò)展信道，其試驗信道集合PD(N)

為：(2)信息率失真函數(shù)單符號信源和單符號信道的信息率失真函數(shù)

信息率失真函數(shù)（率失真函數(shù)）R(D)

：在信源和失真度給定以后，PD是滿足保真度準(zhǔn)則的試驗信道集合，平均互信息I(X;Y)是信道傳遞概率p(yj/xi)的下凸函數(shù)，所以在PD中一定可以找到某個試驗信道，使I(X;Y)達(dá)到最小，即：在信源給定以后，總希望在允許一定失真的情況下，傳送信源所必須的信息率越小越好。從接收端來看，就是在滿足保真度準(zhǔn)則的條件下，尋找再現(xiàn)信源消息必須的最低平均信息量，即平均互信息的最小值。(2)信息率失真函數(shù)

“N次擴(kuò)展”的信息率失真函數(shù)

“N次擴(kuò)展”的信息率失真函數(shù)RN(D)

：對于離散無記憶信源的N次擴(kuò)展信源和離散無記憶信道的N次擴(kuò)展信道，在所有滿足保真度準(zhǔn)則的N維試驗信道集合中，一定可以尋找到某個信道使平均互信息取最小值：由信源和信道的無記憶性，可以證明：RN(D)=NR(D)(3)求信息率失真函數(shù)的方法對偶問題：平均互信息I(X;Y)既是信源概率分布p(xi)的上凸函數(shù)，又是信道傳遞概率p(yj/xi)的下凸函數(shù)。率失真函數(shù)R(D)是在允許平均失真度D

和信源概率分布p(xi)已給的條件下，求平均互信息的極小值（最?。﹩栴}。而信道容量C

是在信道特性p(yj/xi)已知的條件下求平均互信息的極大值（最大）問題。這兩個問題是對偶問題。(3)求信息率失真函數(shù)的方法求信道容量的方法：信道容量是假定信道固定的前提下，選擇一種試驗信源，使信息率最大。一旦找到了這個信道容量，它就與信源不再有關(guān)，而是信道特性的參量，隨信道特性的變化而變化。(3)求信息率失真函數(shù)的方法求信息率失真函數(shù)的方法：信息率失真函數(shù)R(D)是假定信源給定的情況下，在用戶可以容忍的失真度內(nèi)再現(xiàn)信源消息所必須獲得的最小平均信息量。它反映的是信源可壓縮程度。率失真函數(shù)一旦找到，就與求極值過程中選擇的試驗信道不再有關(guān)，而只是信源特性的參量。不同的信源，其R(D)是不同的。(4)研究信道容量和率失真函數(shù)的意義研究信道容量的意義：在實際應(yīng)用中，研究信道容量是為了解決在已知信道中傳送最大信息率問題。目的是充分利用已給信道，使傳輸?shù)男畔⒘孔畲蠖l(fā)生錯誤的概率任意小，以提高通信的可靠性。這就是信道編碼問題。(4)研究信道容量和率失真函數(shù)的意義

研究信息率失真函數(shù)的意義：研究信息率失真函數(shù)是為了解決在已知信源和允許失真度D的條件下，使信源必須傳送給信宿的信息率最小。即用盡可能少的碼符號盡快地傳送盡可能多的信源消息，以提高通信的有效性。這是信源編碼問題。(5)信息率失真函數(shù)的性質(zhì)(a)率失真函數(shù)的定義域(b)率失真函數(shù)對允許平均失真度的下凸性(c)率失真函數(shù)的單調(diào)遞減和連續(xù)性（5）信息率失真函數(shù)的性質(zhì)(a)率失真函數(shù)的定義域什么是率失真函數(shù)的定義域

率失真函數(shù)的定義域問題就是在信源和失真函數(shù)已知的情況下，討論允許平均失真度D的最小和最大值問題。

D的選取必須根據(jù)固定信源X的統(tǒng)計特性P(X)和選定的失真函數(shù)d(xi,yj)，在平均失真度的可能取值范圍內(nèi)。信源最小平均失真度Dmin

是非負(fù)函數(shù)d(xi,yj)的數(shù)學(xué)期望，也是一個非負(fù)函數(shù)，顯然其下限為0。因此允許平均失真度D的下限也必然是0，這就是不允許有任何失真的情況。允許平均失真度D能否達(dá)到其下限值0，與單個符號的失真函數(shù)有關(guān)。信源最小平均失真度Dmin

信源最小平均失真度Dmin

：對于每一個xi，找出一個yj與之對應(yīng)，使d(xi,yj)最小，不同的xi對應(yīng)的最小d(xi,yj)也不同。這相當(dāng)于在失真矩陣的每一行找出一個最小的d(xi,yj)，各行的最小d(xi,yj)值都不同。對所有這些不同的最小值求數(shù)學(xué)期望，就是信源的最小平均失真度。信源最小平均失真度Dmin

只有當(dāng)失真矩陣的每一行至少有一個0元素時，信源的平均失真度才能達(dá)到下限值0。當(dāng)Dmin=0時（信源不允許任何失真存在），信息率至少應(yīng)等于信源輸出的平均信息量（信源熵），即R(0)=H(X)。連續(xù)信源有。要想無失真的傳送連續(xù)信息，就要求信息率為無窮大。實際信道容量總是有限的，無失真?zhèn)魉瓦@種連續(xù)信息是不可能的。只有當(dāng)允許失真（R(D)為有限值），傳送才是可能的。信源最小平均失真度Dmin[舉例]：刪除信源X取值于{0,1}，Y取值于{0,1,2}，失真矩陣為：滿足最小允許失真度的試驗信道是一個無噪無損的試驗信道：信源最大平均失真度Dmax

信源最大平均失真度Dmax：必須的信息率越小，容忍的失真就越大。當(dāng)R(D)等于0時，對應(yīng)的平均失真最大，也就是函數(shù)R(D)定義域的上界值Dmax

。信息率失真函數(shù)是平均互信息的極小值：當(dāng)R(D)=0時，平均互信息的極小值等于0；當(dāng)D>Dmax時，從數(shù)學(xué)意義上講，因為R(D)是非負(fù)函數(shù)，所以它仍只能等于0。這相當(dāng)于輸入X和輸出Y統(tǒng)計獨立。意味著在接收端收不到信源發(fā)送的任何信息，與信源不發(fā)送任何信息等效?；蛘哒f傳送信源符號的信息率可以壓縮至0。計算Dmax的值令試驗信道特性p(yj/xi)=p(yj)(i=1,2,…,n)這時X和Y相互獨立，等效于通信中斷，因此I(X;Y)=0，即R(D)=0。滿足上式的試驗信道有許多，相應(yīng)地可求出許多平均失真度值，從中選取最小的一個，就是這類平均失真值的下界Dmax。計算Dmax的值上式是用不同的概率分布{p(yj)}對Dj求數(shù)學(xué)期望，取數(shù)學(xué)期望當(dāng)中最小的一個作為Dmax。實際是用p(yj)對Dj進(jìn)行線性分配，使線性分配的結(jié)果最小。當(dāng)p(xi)和d(xi,yj)給定時，必可計算出Dj

，Dj隨j的變化而變化，p(yj)是任選的，只需滿足非負(fù)性和歸一性。若Ds是所有Dj當(dāng)中最小的一個，可取p(ys)=1，其它p(yj)為0，這時Dj的線性分配（數(shù)學(xué)期望）必然最小，即：當(dāng)p(y1)=0，p(y2)=1時，得到最小值：當(dāng)p(y1)=1，p(y2)=0時，得到最小值：結(jié)論

R(D)的定義域為：(Dmin,Dmax)

一般情況下：Dmin=0，R(Dmin)=H(X)

當(dāng)D≥Dmax時：R(D)=0

當(dāng)Dmin<D<Dmax時：0<R(D)<H(X)(b)率失真函數(shù)對允許平均失真度的下凸性對任一0≤θ≤1

和任意平均失真度Dmin

≤

D’

，D’’≤Dmax，

R[θD’+(1－θ)D’’]≤θR(D’)+(1－θ)R(D’’)。(c)率失真函數(shù)的單調(diào)遞減和連續(xù)性R(D)的連續(xù)性：可由平均互信息I(X;Y)是信道傳遞概率p(yj/xi)的連續(xù)性來證明。R(D)單調(diào)遞減性：可以證明，在Dmin<D<Dmax范圍內(nèi)R(D)

單調(diào)遞減。率失真函數(shù)曲線圖說明

R(0)=H(X)

，R(Dmax)=0，決定了曲線邊緣上的兩個點；在

0

和

Dmax之間，R(D)

是單調(diào)遞減的下凸函數(shù)；在連續(xù)信源時，當(dāng)D→0

時，

R(D)→∞

，曲線將不與R(D)

軸相交。5.2.3離散信源的信息率失真函數(shù)(1)離散信源信息率失真函數(shù)的參量表達(dá)式(a)求極小值方法(b)離散信源的信息率失真函數(shù)(c)

參量S

的說明(2)二元及等概率離散信源的信息率失真函數(shù)(a)二元離散信源的率失真函數(shù)(b)信息率失真函數(shù)曲線圖說明(c)二元等概率離散信源的率失真函數(shù)(1)離散信源率失真函數(shù)的參量表達(dá)式(a)求極小值方法已知信源概率分布函數(shù)

p(xi)

和失真度

d(xi,yj)，在滿足保真度準(zhǔn)則的條件下，在試驗信道集合

PD

當(dāng)中選擇

p(yj/xi)，使平均互信息：最小(1)離散信源率失真函數(shù)的參量表達(dá)式(b)離散信源的信息率失真函數(shù)已知平均互信息在(2)的條件限制下求

I(X;Y)的極值，引入拉各朗日乘子

S

和μi(i=1,2,…,n)，構(gòu)造一個新函數(shù)：(1)離散信源率失真函數(shù)的參量表達(dá)式(b)離散信源的信息率失真函數(shù)(1)離散信源率失真函數(shù)的參量表達(dá)式(b)離散信源的信息率失真函數(shù)(1)離散信源率失真函數(shù)的參量表達(dá)式(b)離散信源的信息率失真函數(shù)第一步：求λi(1)離散信源率失真函數(shù)的參量表達(dá)式(b)離散信源的信息率失真函數(shù)第二步：求p(yj)(1)離散信源率失真函數(shù)的參量表達(dá)式(b)離散信源的信息率失真函數(shù)第三步：求p(yj/xi)

將解出的λi和p(yj)代入式(6)，可求得m·n個以S為參量的p(yj/xi)。(1)離散信源率失真函數(shù)的參量表達(dá)式(b)離散信源的信息率失真函數(shù)第四步：求D(S)

將這

m·n

個

p(yj/xi)

代入(2)得到以S為參量的允許平均失真函數(shù)

D(S)。(1)離散信源率失真函數(shù)的參量表達(dá)式(b)離散信源的信息率失真函數(shù)第五步：求R(S)

將這

m·n

個

p(yj/xi)

代入(1)得到以

S為參量的率失真函數(shù)

R(S)。(1)離散信源率失真函數(shù)的參量表達(dá)式(b)離散信源的信息率失真函數(shù)第六步：由于

p(yj)不能是負(fù)值，參量S

的取值有一定的限制。選擇使p(yj)非負(fù)的所有

S，得到

D

和

R

值，可以畫R(D)曲線，如圖4.2.1。(1)離散信源率失真函數(shù)的參量表達(dá)式(c)

參量S

的說明可以證明：參量

S就是R(D)函數(shù)的斜率。參量S的特性：由于R(D)是D的單調(diào)遞減函數(shù)，并且是U型凸函數(shù)，故斜率

S必為負(fù)，且是D的遞增函數(shù)，D從0變到Dmax，S將逐漸增加；當(dāng)D=0時：S的最小值趨于負(fù)無窮（R(D)的斜率）。(1)離散信源率失真函數(shù)的參量表達(dá)式(c)

參量S

的說明當(dāng)D=Dmax

時：S達(dá)到最大；這個最大值也是某一個負(fù)值，極限是0。當(dāng)D>Dmax

時：在D=Dmax

處，除某些特例外，S將從某一個負(fù)值跳到0，S在此點不連續(xù)。在D的定義域[0,Dmax]內(nèi)，除某些特例外，S將是D的連續(xù)函數(shù)。(2)二元及等概率離散信源的信息率失真函數(shù)(a)二元離散信源的率失真函數(shù)設(shè)二元信源

計算率失真函數(shù)R(D)(2)二元及等概率離散信源的信息率失真函數(shù)(a)二元離散信源的率失真函數(shù)先求出Dmax(2)二元及等概率離散信源的信息率失真函數(shù)(a)二元離散信源的率失真函數(shù)第一步：求λi，由式(7)有：(2)二元及等概率離散信源的信息率失真函數(shù)(a)二元離散信源的率失真函數(shù)第二步：求p(yj)，由式(8)有：(2)二元及等概率離散信源的信息率失真函數(shù)(a)二元離散信源的率失真函數(shù)第三步：求p(yj/xi)，由式(6)有：(2)二元及等概率離散信源的信息率失真函數(shù)(a)二元離散信源的率失真函數(shù)第四步：求D(S)，將上述結(jié)果代入式(10)有：(2)二元及等概率離散信源的信息率失真函數(shù)(a)二元離散信源的率失真函數(shù)第五步：求R(S)將上述結(jié)果代入式(11)有：(2)二元及等概率離散信源的信息率失真函數(shù)(a)二元離散信源的率失真函數(shù)第五步：求R(S)對于這種簡單信源，可從

D(S)

解出

S

與

D

的顯式表達(dá)式：(2)二元及等概率離散信源的信息率失真函數(shù)(a)二元離散信源的率失真函數(shù)第五步：求R(S)(2)二元及等概率離散信源的信息率失真函數(shù)(a)二元離散信源的率失真函數(shù)第六步：通過以上步驟計算出來的

R(D)

和S(D)如圖4.2.2。返回目錄(2)二元及等概率離散信源的信息率失真函數(shù)(b)信息率失真函數(shù)曲線圖說明若α=1，把d(xi

,yj)當(dāng)成了誤碼個數(shù)，即X和Y不一致時，認(rèn)為誤了一個碼元，所以：

d(xi

,yj)的數(shù)學(xué)期望就是平均誤碼率。能容忍的失真等效于能容忍的誤碼率。(2)二元及等概率離散信源的信息率失真函數(shù)(b)信息率失真函數(shù)曲線圖說明若R(D)

不僅與

D有關(guān)，還與

p

有關(guān)。概率分布不同，

R(D)

曲線就不一樣。當(dāng)

p=0.25時，如果能容忍的誤碼率也是

0.25，不用傳送信息便可達(dá)到，即R=0，這就是

R(Dmax)=0

的含義.例如：不管信源發(fā)出的是x1還是x2，都把它編成x2，則誤碼率就是信源發(fā)出x1的概率0.25，只送一種符號當(dāng)然就不用傳送信息，即R=0，這就是R(Dmax)=0的含義。(2)二元及等概率離散信源的信息率失真函數(shù)(b)信息率失真函數(shù)曲線圖說明當(dāng)

D相同時，信源越趨于等概率分布，

R(D)

就越大。由最大離散熵定理，信源越趨于等概率分布，其熵越大，即不確定性越大，要去除這不確定性所需的信息傳輸率就越大，而

R(D)

正是去除信源不確定性所必須的信息傳輸率。(2