第六章有噪聲編碼

第6章有噪信道編碼

第6章有噪信道編碼

內(nèi)容提要本章介紹了信道編碼和譯碼的基本概念，介紹了兩種常用的譯碼準(zhǔn)則：最大后驗(yàn)概率譯碼準(zhǔn)則和極大似然譯碼準(zhǔn)則,還介紹了在這兩種譯碼準(zhǔn)則下錯誤概率的計(jì)算方法。本章還介紹了信道編碼定理及信道編碼逆定理，以及信息論中的一個重要不等式Fnao不等式。

6．1信道編碼的基本概念

將信道用圖6-1所示的模型表示。信道編碼器信道信道譯碼器uxy圖6-1信道模型

信源輸出序列u，經(jīng)信道編碼器編成碼字x=f(u)并輸入信道，由于干擾，信道輸出y，信道譯碼器對y估值得

=F(y)

。

信源編碼以提高傳輸效率作為主要考慮因素，信道編碼以提高傳輸可靠性作為主要考慮因素?！纠?.3】逆重復(fù)碼離散無記憶二進(jìn)制對稱信道，固有誤碼率為p(p<0.5)，信源輸出序列為三位二進(jìn)制數(shù)字。編碼規(guī)則：為提高傳輸效率，僅向信道發(fā)送一位，預(yù)先將信源輸出序列進(jìn)行擇多編碼:圖6-3逆重復(fù)編碼傳輸示意圖

譯碼規(guī)則：將接收的一位符號重復(fù)三次譯出，即若接收到1就譯碼為111，即若接收到0就譯碼為000。信源輸出的三位符號中有兩位或3位是1，信源序列編碼為1，若三位符號中有兩位或3位是0，就將此信源序列編碼為0。計(jì)算差錯概率pe：（1）先設(shè)p=0，計(jì)算這種編碼方法帶來的固有錯誤p1信道輸入符號集

X={000,001,010,011,100,101,110,111}判決輸出符號集Y={000,111}譯碼規(guī)則因?yàn)楹篁?yàn)概率則出錯概率

兩個估值序列也是等概分布的，則每個序列的平均錯誤概率為誤比特率

（2）再設(shè)p≠0，計(jì)算由于信道噪聲引起的錯誤概率p2。因?yàn)槊總€序列有三位二進(jìn)制數(shù)字，但只發(fā)送一位，這一位的出錯概率為p，故序列差錯概率為p，誤比特率（3）總差錯概率（誤比特率）：

6．2譯碼規(guī)則及錯誤概率

信道總不可避免會攙雜噪聲，所以信息在信道傳輸過程中，差錯是不可避免的。選擇合適的譯碼規(guī)則可以彌補(bǔ)信道的不足。1．最大后驗(yàn)概率譯碼準(zhǔn)則發(fā)送碼矢xk，其發(fā)送概率為q(xk)，通過信道轉(zhuǎn)移概率為p(y︱xk)的信道傳輸，接收到矢量y，信道譯碼器輸出通信過程可用圖6－5所示框圖表示。下面介紹兩種典型的譯碼規(guī)則：圖6－5通信過程框圖

當(dāng)估值≠xk時，就產(chǎn)生了誤碼，用（x︱y）表示后驗(yàn)概率，則收到y(tǒng)估錯的概率為 （6-2）

通信總希望錯誤概率最小，由式(6-2)可看出錯誤概率pe

(xk)最小等同于后驗(yàn)概率（xk︱y）最大，這就是最大后驗(yàn)概率譯碼準(zhǔn)則。

{}{xk}{y}信源信道編碼器信道信道譯碼器信宿干擾根據(jù)概率關(guān)系式（6-3）

根據(jù)式（6-3）后驗(yàn)概率（x︱y）最大的就意味著p（x

y）全概率最大，因此最大后驗(yàn)概率譯碼準(zhǔn)則也稱為最大聯(lián)合概率譯碼準(zhǔn)則。【例6.5】信源分布，信道轉(zhuǎn)移概率矩陣，信道輸出符號Y={y1,y2,

y3}，按最大后驗(yàn)概率準(zhǔn)則譯碼。(1)根據(jù)p(xy)=p(y︱x)q(x)算出全概率，用矩陣表示

(2)根據(jù)，算出

[（y）]=[0.380.340.28]

(3)再由算出后驗(yàn)概率，用矩陣表示

(4)按最大后驗(yàn)概率準(zhǔn)則譯碼，在后驗(yàn)概率矩陣中，每列選一最大值（矩陣中帶下劃線的值），譯為

(5)若按最大聯(lián)合概率譯碼準(zhǔn)則譯碼，在全概率矩陣[p(xy)]中每列選一最大值（矩陣中帶下劃線的值），也可譯出。在實(shí)際應(yīng)用中，一般最大信道轉(zhuǎn)移概率來確定估值，即在收到矢量y后，在所有的xm(m=1,2,…,M)中,選一個轉(zhuǎn)移概率p(y︱xm)最大的xm值，作為對y的估值=xk，這一譯碼規(guī)則稱為極大似然譯碼規(guī)則。

2．極大似然譯碼準(zhǔn)則

3．平均錯誤概率由（6-2）式是信道輸出y二信道譯碼器估錯的概率，對上式求統(tǒng)計(jì)平均（6-4）（1）求平均錯誤概率pe根據(jù)式（6-4）得=0.01+0.12+0.07+0.12+0.1+0.02=0.44

【例6.6】計(jì)算[例6.5]的平均錯誤概率，若信源等概分布，對其譯碼，并求平均錯誤概率。

例6.5已經(jīng)根據(jù)p(xy)=p(y︱x)q(x)算出全概率，用矩陣表示

解：(2)當(dāng)信源等概分布，按最大似然函數(shù)譯碼準(zhǔn)則譯碼，[例6.5]已給出信道轉(zhuǎn)移概率矩陣在矩陣的每列中選一最大值(矩陣中帶下劃線的值)，譯碼為平均錯誤概率6．3信道編碼定理定理6.1

對于任何離散無記憶信道DMC，存在信息傳輸率為R，長為n的碼，當(dāng)n→∞時，平均差錯概率pe<exp{-nE(R)}→0，式中E(R)為可靠性函數(shù)，E(R)在0<R<C的范圍內(nèi)為正。

上述定理也稱有噪信道編碼定理，即Shannon第二定理。

一．隨機(jī)編碼方法

選用長為n的定長碼，共可構(gòu)成kn個矢量，設(shè)有M個消息待傳（M<kn），每次隨機(jī)地從kn個矢量中抽出M個矢量構(gòu)成一個碼字集合C（允許重復(fù)?。〤

={x1,…,xm,…,x

M}共可構(gòu)成knM個這樣的碼字集合。由隨機(jī)編碼的構(gòu)造方法，得到任何一個碼字的概率相同，且相互獨(dú)立。

式中0

,

1，因?yàn)?

都是任意數(shù)，可取

二．Gallager上界Gallager上界：（6-8）三．隨機(jī)編碼錯誤概率上界

Gallager限僅給出發(fā)送碼矢xk時的錯誤概率上界，通過對上述的隨機(jī)編碼集合求平均，可得到隨機(jī)編碼錯誤概率的上界：

（6-12）（6-12）平均錯誤概率的上界，它雖然是針對離散無記憶信道推出的，但對有記憶的離散輸入、輸出及連續(xù)輸出都適用，只不過在連續(xù)情況下，表示概率密度。

四．離散無記憶信道DMC的錯誤概率上界

在0

R

C的范圍內(nèi)，E

(R)是下降的、下凹的正值函數(shù)，說明E

(R)有界，這樣，當(dāng)時，有exp{-nE

(R)}→0，從而pe

<exp{-n

E

(R)}→0。

五．可靠性函數(shù)E(R)稱E(R)為可靠性函數(shù),也稱隨機(jī)編碼指數(shù)，它與信道轉(zhuǎn)移概率p(y︱x)有關(guān)。R為信息傳輸速率，6．4費(fèi)諾引理及信道編碼逆定理

6.4.1費(fèi)諾不等式

設(shè)信道輸入符號X和輸出符號Y取自同一符號集A={a1,a2,…,ak}，則傳輸過程中的錯誤概率pe和信道疑義度H(X︱Y)之間滿足下列關(guān)系式：H(X︱Y)

H2(pe)+pe

log(k-1)(6-18)上式就是著名的Fano不等式。將Fano不等式推廣到L維矢量情況：設(shè)x=x1,…,xl,…,xL,y=y1,…,yl,…,yL,皆為L維矢量，xl,yl∈A={a1,a2,…,ak}，記pe為錯誤概率，則H(X︱Y)

L[H2(pe)+pe

log(k-1)](6-24)Fano不等式的物理意義：進(jìn)行一次判決后，關(guān)于X的疑義度可分成兩項(xiàng)：(1)是否判對，疑義度為H2(pe)(2)如果判決出錯（概率為pe）,錯在k-1個符號中的哪一個，疑義度不會超log(k-1)。

6.4.2信道編碼逆定理

引理6.1設(shè)u=u1,…,ul,…,uL為L維隨機(jī)矢量，ul

取自同一符號集{U}，則（6-25）式中H(U)表示L維熵，H(U)表示一維熵。即：

H2(pe)+pe

log(k-1)（6-32）式中為信息傳輸率。定理6.2信道編碼逆定理

信道容量C是可靠通信系統(tǒng)信息傳輸率的上界，當(dāng)R

>C，不可能存在任何方法使差錯概率任意小。本章小結(jié)信道輸入碼矢xk∈{

x1,x2,…,xM

}，通過信道轉(zhuǎn)移概率為p(y︱xk)的信道傳輸，輸出矢量y，信道譯碼器估值為＝F(y)，∈{x1,x2,…,xM

}。

最大后驗(yàn)概率譯碼準(zhǔn)則

（︱y）>（xm︱y）

極大似然譯碼準(zhǔn)則

p（y︱）>p（y︱xm）

平均譯碼錯誤概率

信道編碼定理

對于任何離散無記憶信道DMC，存在信息傳輸率為R，長為n的碼，當(dāng)n→∞時，平均差錯概率