北郵信通院信息論第七章

第7章

有噪信道編碼信息與通信工程學院許文俊第7章有噪信道編碼

本章主要內(nèi)容：

1.概述

2.常用譯碼準則

3.費諾(Fano)不等式

4.序列的最佳譯碼準則

5.有噪信道編碼定理

§7.1概述

為提高傳輸?shù)目煽啃?，必須進行信道編碼。信道編碼就是按一定的規(guī)則給信源輸出序列增加某些冗余符號，使其變成滿足一定數(shù)學規(guī)律的碼序列（或碼字），再經(jīng)信道進行傳輸。（注意：與信源編碼比較）信道譯碼就是按與編碼器同樣的數(shù)學規(guī)律去掉接收序列中的冗余符號,恢復信源消息序列。一般地說，所加的冗余符號越多，糾錯能力就越強，但傳輸效率降低。因此在信道編碼中明顯體現(xiàn)了傳輸有效性與可靠性的矛盾。在數(shù)據(jù)傳輸系統(tǒng)中譯碼過程總要比編碼過程復雜,這樣采用的譯碼算法對系統(tǒng)的性能影響很大。

本節(jié)主要內(nèi)容：

1.錯誤概率

2.譯碼（判決）規(guī)則7.1.1錯誤概率

●兩種錯誤概率的描述：誤碼率和誤字率。誤碼率是指傳輸碼元出錯概率（對二進制也稱誤比特率）.

誤字率是指碼字出錯概率。

●一個碼字一般由多個碼元構(gòu)成，任何一個或多個碼元出錯

都使得碼字出錯。所以對同一通信系統(tǒng)，誤字率總比誤碼率高?！皴e誤概率的大小與信噪比大小有關(guān)。信噪比大，則錯誤概率小；反之信噪比小，則錯誤概率大。

●錯誤概率還與譯碼規(guī)則的選擇有關(guān)。適當?shù)剡x擇譯碼規(guī)則使平均錯誤概率最小是提高傳輸可靠性的重要措施之一。7.1.2譯碼（判決）規(guī)則1.單符號譯碼規(guī)則設(shè)信道的輸入與輸出分別為X和Y，，分別取自符號集A和B，且，定義譯碼（判決）規(guī)則為對于所有（7.1.1） 含義：當接收到就判定發(fā)送符號是因此，每一個信道輸出都必須有一個信道輸入與之對應(yīng)。所以譯碼（判決）規(guī)則是一個有唯一結(jié)果的函數(shù)。2．錯誤概率的計算設(shè)信道的轉(zhuǎn)移概率為，采用的譯碼規(guī)則為：對于所有（7.1.2）（7.1.2）式可簡記為。在接收到的條件下，若實際上發(fā)送的是，則譯碼正確，反之就出現(xiàn)差錯。因此滿足譯碼規(guī)則（7.1.2）的條件錯誤率為：正確率為：所以平均錯誤率為：（7.1.3）（7.1.3）式的含義是，如果輸出y與未被y作為譯碼結(jié)果的輸入同時出現(xiàn)就屬于譯碼錯誤。還可計算平均正確率為（7.1.4）

§7.2常用譯碼準則

為提高可靠性，所采用的譯碼準則都應(yīng)該使平均錯誤概率最小。最常用的就是最大后驗概率譯碼準則和最大似然譯碼準則。本節(jié)主要內(nèi)容：

1.最大后驗概率譯碼準則

2.最大似然譯碼準則7.2.1最大后驗概率譯碼準則對所有

i，當滿足

（7.2.1）時，則選擇譯碼函數(shù)為F(y)=a*，稱此準則為最大后驗概率(MAP，MaximumaPosteriori)準則。MAP準則就是將具有最大后驗概率的信道輸入符號作為譯碼輸出。由（7.2.1）式，得所以，對所有i，當（7.2.2）時，則選擇譯碼函數(shù)為F(y)=a*。其中，為似然比，（7.2.2）式表示的是似然比檢驗?？梢姡琈AP準則可歸結(jié)為似然比檢驗。

MAP準則是使平均錯誤最小的準則,原因：7.2.2最大似然譯碼準則若輸入符號等概，即p(ai)=1/r

時，（7.2.2）變?yōu)椋簩λ衖,當（7.2.3）則選擇譯碼函數(shù)為F(y)=a*，稱此準則為最大似然譯碼準則。注：1）當輸入符號等概或先驗概率未知時，采用此準則。

2）當輸入符號等概時，最大似然準則等價于最大后驗概率準則。例7.2.1設(shè)信道輸入X取值為(a1,a2,a3),信道輸出Y取值為(b1,b2,b3)，轉(zhuǎn)移概率矩陣如下

求利用最大似然（ML）譯碼準則的判決函數(shù)。解:

每個輸出符號給定，當y=b1時，p(y/a1)=0.5,p(y/a2)=0.2,p(y/a3)=0.3，利用（7.2.3），得判決函數(shù),F(b1)=a1，同理得其它最大似然判決函數(shù)：F(b2)=a3（或F(b2)=a1或F(b2)=a2），F(xiàn)(b3)=a2。兩種準則使用要點：1．MAP準則

i）由轉(zhuǎn)移概率矩陣的每行分別乘p(x)，得到聯(lián)合概率矩陣；

ii）對于每一列（相當于y

固定）找一個最大的概率對應(yīng)的

x

作為譯碼結(jié)果；

iii）所有譯碼結(jié)果所對應(yīng)的聯(lián)合概率的和為正確概率,其他矩陣元素的和為錯誤概率。2．ML準則

i）對轉(zhuǎn)移概率矩陣中每列選擇最大的一個元素對應(yīng)的x作為譯碼結(jié)果；

ii）輸入符號等概時，所有譯碼結(jié)果所對應(yīng)的轉(zhuǎn)移概率的和再乘以1/r

為正確概率，其他矩陣元素的和再乘以1/r為錯誤概率。例7.2.1（續(xù)）求最大似然準則的錯誤率。解：錯誤率PE=1-(0.5+0.3+0.5)/3=0.5667。例7.2.2

已知信道的轉(zhuǎn)移概率矩陣為現(xiàn)有兩種譯碼規(guī)則：規(guī)則A：規(guī)則B：設(shè)輸入等概，求兩種譯碼規(guī)則的錯誤率。解：設(shè)判決函數(shù)為，根據(jù)（7.1.3），得

§7.3費諾(Fano)不等式

主要內(nèi)容：

1.信道疑義度

2.費諾(Fano)不等式

3.序列費諾(Fano)不等式7.3.1信道疑義度設(shè)信道的輸入與輸出分別為X、Y，定義條件熵H(X|Y)為信道疑義度。它包含如下含義：1）信道疑義度表示接收到Y(jié)

條件下X的平均不確定性；2）根據(jù)I(X;Y)=H(X)-H(X|Y)，信道疑義度又表示X經(jīng)信道傳輸信息量的損失；3）接收的不確定性由信道噪聲引起，在無噪情況下，H(X|Y)=0。7.3.2費諾(Fano)不等式設(shè)信道的輸入與輸出分別為X、Y，輸入符號的數(shù)目為r，那么信道疑義度滿足（7．3．1）其中，為平均錯誤率。證：設(shè)譯碼規(guī)則由（7.1.2）確定，那么上式=當下面兩個條件同時成立時，等號成立：i）ii）

上面條件表明，當y給定后判決錯誤的概率相等時，不等式取等號。證畢。注釋：i）無論什么譯碼規(guī)則，費諾不等式成立；譯碼規(guī)則變化只會改變pE的值；ii）信道疑義度由信源、信道及譯碼規(guī)則所限定；因為信源決定p(x)，r，而p(x)，p(y|x)及譯碼規(guī)則決定pE

iii）對不等式的含義的理解：當接收到Y(jié)后，關(guān)于X

平均不確定性的解除可以分成兩步來實現(xiàn)：第1步是確定傳輸是否有錯，解除這種不確定性所需信息量為

H(pE)；第2步是當確定傳輸出錯后，究竟是哪一個錯解除這種不確定性所需最大信息量是log(r-1)。

圖7.3.1費諾不等式示意圖圖7.3.1為費諾不等式示意圖。圖中，曲線下面的區(qū)域為信道疑義度被限定的區(qū)域?，F(xiàn)求曲線的極大值。僅當即時等式成立。由于當時，有。7.3.3序列費諾(Fano)不等式

(教材無)若信道的輸入與輸出為多維隨機變量和，定義

（7．3．2）其中，是第個符號出錯的概率，則Fano不等式成立：（7．3．3）其中r為輸入符號集中元素的個數(shù)。證：利用引理4，有

利用（7．3．1）式，有

§7.4序列的最佳譯碼準則

主要內(nèi)容：

1.漢明距離

2.序列最大似然譯碼7.4.1漢明距離設(shè)兩碼字為，定義它們的漢明距離為（7.4.1）其中，為模二加運算。例如，碼字和碼字的漢明距離為6。一個碼字集合中任意兩碼的漢明距離最小值，稱為碼的最小距離，用dmin來表示。7.4.2序列最大似然譯碼

設(shè)信道的輸入與輸出分別為多維隨機矢量集合：，其中，序列；分別取自符號集A和B，且，，其中，，。

如果對于所有k，滿足 （7.4.2）那么就選擇譯碼函數(shù)為，稱為序列的最大似然譯碼準則。轉(zhuǎn)移概率稱為似然函數(shù)。與單符號情況相同，當消息序列等概或概率未知時用最大似然譯碼準則。定理7.4.1

對于無記憶二元對稱信道，最大似然譯碼準則等價于最小漢明距離準則。證：設(shè)信道的輸入與輸出分別為序列，似然函數(shù)為（7.4.3）設(shè)的漢明距離為，如果出錯，那么與不同，從而使?jié)h明距離增加1。又根據(jù)二元對稱信道的特性，有其中，所以（7.4.3）式變?yōu)槿?shù)，得（7.4.4）因為n

是定值，當信道固定后，p也是定值，而又有，所以，當d

最小時可使（7.4.4）的值最大。這樣對于固定的，選擇的所有可能的輸入序列，將與漢明距離最小的序列x作為譯碼輸出，這種譯碼方法也稱為最小漢明距離準則。證畢。例7.4.1

對等概信源符號0和1進行重復碼編碼，對應(yīng)的碼字為000，111；編碼序列通過錯誤概率為p

（≤1/2）的二元對稱信道傳輸，接收端利用最大似然譯碼準則；求譯碼錯誤率pE。解：此時可利用最小漢明距離準則。二元對稱信道三次擴展信道轉(zhuǎn)移矩陣為：

YX

000001010011100101110111000(1-p)3(1-p)2p(1-p)2p(1-p)p2(1-p)2p(1-p)p2(1-p)p2

p3111

p3(1-p)p2(1-p)p2(1-p)2p(1-p)p2(1-p)2p(1-p)2p(1-p)3判決000000000111000111111111分別計算y

的每一個可能序列與000和111的漢明距離，將漢明距離小的輸入序列作為譯碼輸出。例如，接收為010，與000的距離為1，而和111的距離為2，所以譯碼輸出為000；依次類推，得到表中的下面一行。通過計算，得正確率：1-pE=(1-p)3+3(1-p)2p，錯誤率：pE=p3+3(1-p)p2。P133例7.3P134(n,k)線性分組碼的碼率P135例7.5P136定理7.2例7.6

§7.5有噪信道編碼定理

設(shè)有一離散無記憶平穩(wěn)信道的容量為C，則只要信息傳輸率R<C，總存在一種編碼，使當碼序列長度n足夠長時，譯碼錯誤概率pE任意??；反之，當信息傳輸率R>C時，對任何編碼方式，譯碼差錯率大于0。（香農(nóng)第二定理)(與香農(nóng)第一定理的比較，P93)

定理的證明見附錄.下面重點對定理的含義進行說明。

圖7.5.1為編碼器與信道模型圖，這里考慮的是分組信道編碼。假定由信源發(fā)出M

個等概率信息，經(jīng)信道編碼后生成M個碼字，其中碼符號集的大小為r，碼長為n；生成的n

長碼字為信道輸入，n長序列為信道輸出。

圖7.5.1編碼器與信道模型圖說明：1．信息傳輸速率為

R=(logM)/n

，表示每個碼符號攜帶的信息量。2．隨機編碼：獨立、隨機地從r

n種信號序列中選取M個長度為n的序列，組成碼字集合。每次選擇允許重復，則選擇的碼字集合種類數(shù)有rnM，每種碼被選擇的概率為r-nM。而且對于每一個n

長序列中的每一個符號也按概率獨立選取。這種編碼方式稱隨機編碼（注意“隨機”僅指選擇方式“隨機”，當選擇后，碼集合便確定）。3.譯碼準則：采用最大似然譯碼準則，或其它譯碼準則，例如聯(lián)合典型序列譯碼。4.譯碼平均錯誤率pE

的估計：由于尋找最佳，即pE

最小時的編碼很困難，所以采用求的方法，即對所有的隨機編碼進行平均若時，任意小，那么至少有一種編碼滿足要求。5.定理僅指出編碼的存在性，并未給出編碼的具體方法。6.定理的意義該定理糾正了人們認為的提高可靠性必須要降低有效性的傳統(tǒng)的觀念，提出高效（接近容量）和高可靠性的編碼是存在的，為信道編碼理論和技術(shù)的研究指明了方向。定理給出了信道編碼的理想極限性能，是信道編碼理論的基礎(chǔ)。7.尋找最佳信道編碼的困難1)要求編碼序列足夠長，“難實現(xiàn)”；2）

很大，“難尋找”；3）采用隨機編碼，“難分析”。8.信道容量是進行可靠傳輸?shù)淖畲笮畔鬏斔俾省?/p>

有噪信道編碼定理的證明1．正定理證明證:利用聯(lián)合典型序列的方法證明。設(shè)離散無記憶平穩(wěn)信道的轉(zhuǎn)移概率為，輸入與輸出分別為序列和，n為序列長度；達到信道容量的輸入概率為，信道輸出為，輸入與輸出的聯(lián)合概率為，設(shè)輸入/輸出序列:

，并設(shè)為序列中取值ij的數(shù)目。我們有

(7.5.1)如果，對每個，那么就稱為典型序列。對任何典型序列，有

(7.5.2)

設(shè)為輸入序列中取值i的符號數(shù)，那么所以，如果是典型序列，那么也是典型序列。同理，如果是典型序列，那么也是典型序列。對于典型序列，有下面的關(guān)系：

(7.5.3)(7.5.4)(7.5.5)對每個典型序列，定義使得為典型序列的的集合為。如果不是典型序列，那么為空集。對于典型序列，根據(jù)(7.5.5)、(7.5.3)，有 ， 所以。設(shè)中元素的個數(shù)為，則所以

(7.5.6)下面，我們選擇一種由M個輸入序列（每個序列的長度為n）組成的碼。并隨機地選擇每個序列中的每一個符號,且每個符號的概率使信道達到容量。譯碼原則采用仙農(nóng)提出的“典型序列”原則：給定一接收序列，選擇唯一的消息，使得碼字在中。如果中不包含任何碼字或包含多于一個的碼字，就拒絕譯碼，此時譯碼出錯。如果編碼器的輸入是消息，那么僅當不是典型序列（即不是典型序列或）或?qū)θ魏纹渌a字，有時，譯碼出錯。設(shè)為典型序列的集合，在隨機編碼集合中，錯誤概率不依賴于消息m，并且序列集合的每一個元素都獨立地以概率選取，所以錯誤率的上界為 (7.5.7)除發(fā)送碼字之外的每個其它碼字獨立于接收序列而每個典型序列的概率最大為，因此利用(7.5.6)，其中，得

(7.5.8)

信息傳輸速率為（比特/符號）。如果

,那么，(7.5.7)中M-1用M代替，得

(7.5.9)選擇,那么(7.5.9)變?yōu)?對于任何，我們選擇n足夠大，使得且，那么對于足夠大的n，有。因為這對于在所有碼集合中平均都成立，所以至少存在一種編碼使結(jié)論成立。這里的錯誤概率是誤字率，而誤符號率不大于誤字率，所以只要沒有錯誤傳播，誤符號率就會任意小。2．逆定理的證明當信息傳輸率R>C時，傳輸錯誤率必大于0。證:

仍然證明DMC情況。對于圖7.5.1，由數(shù)據(jù)處理定理有，，因為信道無記憶

,所以，即:根據(jù)Fano不等式，有

(7.5.10)將，代入(7.5.10)，得

(7.5.11)這里為信息傳輸速率。當時,(7.5.11)的右邊大于零，所以不為0，即出現(xiàn)譯碼差錯無失真信源信道編碼定理（信源信道編碼定理）設(shè)有一離散無記憶平穩(wěn)信道的每秒容量為C，一個離散信源每秒的熵為H，那么，如果H<C，總存在一種編碼系統(tǒng)，使得信源的輸出以任意小的錯誤概率通過信道傳輸；反之，如果H>C時，對任何編碼系統(tǒng)，譯碼差錯率p>0。(P144,例7.9)

§7.6接近信道編碼性能界限的編碼

l

Turbo碼

l

LDPC碼

7.6.1

Turbo碼

l

Berrou等人于1993年提出；

l

信道編碼理論研究的重要里程碑；

1.Turbo碼性能:

l

在AWGN信道；

l

BPSK調(diào)制的1/2碼率；

l

采用65536的隨機交織器；

l

18次迭代譯碼；

l

在誤碼率時；

l

所需信噪比為（突破了截止速率的2.5dB,也遠低于級聯(lián)碼所需的1.6dB，仙農(nóng)限為0dB）

2.Turbo碼的編譯碼原理l

卷積碼與隨機交織器巧妙地結(jié)合，實現(xiàn)了隨機編碼的思想；l

采用軟輸出迭代譯碼來逼近最大似然譯碼。l

編碼器：兩個并聯(lián)系統(tǒng)卷積碼的輸入之間采用隨機交織器l

框圖如圖7.6.1：

圖7.6.1Turbo碼編碼器框圖

l

編碼器工作原理:*信息序列u經(jīng)過一個N位交織器，形成新序列u1；*u與u1分別進入兩個分量編碼器（RSC1和RSC2）（兩個分量編碼器結(jié)構(gòu)相同），生成序列x1和x2；*x1和x2經(jīng)過刪余（鑿孔）器，周期性的刪除一些校驗位，形成校驗序列x‘；*u與x‘經(jīng)過復用生成Turbo碼序列x。l

譯碼器工作原理: *譯碼器基本結(jié)構(gòu)如圖7.6.2，兩個軟輸入軟輸出譯碼器

DEC1，DEC2經(jīng)交織器串聯(lián)構(gòu)成。

圖7.6.2Turbo碼譯碼器框圖*交織器與編碼器中使用相同；*譯碼迭代過程：

DEC1對最佳RSC1譯碼，產(chǎn)生u中的似然信息，并將其中的新信息經(jīng)交織器送到DEC2；

DEC2將此信息作為先驗信息，對RSC2最佳譯碼，產(chǎn)生交織后的似然比信息，并將其中的外信息經(jīng)解交織器送到DEC1。*經(jīng)多次迭代后，進行硬判決，得到信息估計序列。

l

交織器 *目的：盡量隨機地重新分配突發(fā)錯誤，使信息位之間的相關(guān)性降低使編碼后碼字的距離譜細化，改變碼字的距離特性*常用交織器：Cyclic-T，Random-T，S-random等l

常用算法：

MAP（最大后驗概率）算法：

SOVA（軟輸出Viterbi算法）算法3．Turbo碼的缺點：當信噪比很大時，譯碼錯誤率趨于平緩（地板效應(yīng)）4．Turbo碼的應(yīng)用

l

由美國空間數(shù)據(jù)系統(tǒng)顧問委員會作為深空通信標準；

l

第三代移動通信系統(tǒng)（IMT-2000）的數(shù)據(jù)信道編碼方案：

WCDMA，cdma2000，TD-SCDMA7.6.2LDPC碼1．LDPC碼的性能

l

低密度奇偶校驗(LDPC：lowdensityparitycheck)碼是由Gallager

于1962年提出；

l

Turbo碼只是LDPC碼的一個特例，譯碼算法具有等價性；

l

LDPC碼具有許多比Turbo碼更優(yōu)良的特性： * 糾錯性能優(yōu)于Turbo碼，更接近Shannon限： 碼長為10,000的非規(guī)則的LDPC碼距Shannon限有0.3dB，Chung[5]

等人又發(fā)現(xiàn)非規(guī)則二進制的LDPC碼在碼長N＝107、碼率R＝1/2、AWGN信道，與仙農(nóng)限幾乎相等，僅差0.0045dB，遠遠超過了Turbo碼的性能。 *具有優(yōu)異的分組碼糾錯性能。 *譯碼復雜度低，是時間的線性函數(shù)。 *可并行譯碼*無地板效應(yīng)，最小碼距正比于碼字的長度。

2．LDPC碼的結(jié)構(gòu)

l

LDPC碼的檢驗矩陣H與普通的分組碼的校驗矩陣不同，H的每行和每列中1的個數(shù)很少，即1的密度很小以期望得到較大的最小碼距dmin（這也是LDPC碼名稱的由來）；

l

分為規(guī)則碼和不規(guī)則碼（Gallager最初提出為規(guī)則LDPC碼）；

l

規(guī)定規(guī)則（n,k）LDPC碼的校驗矩陣每列有wc個1，每行有wr=wc(n/m)個1，其中m=n-k，并且wc<<m，即行向量中1的個數(shù)也遠小于零的個數(shù)，從上面的結(jié)果還可以推出wr<<n，即行中1的個數(shù)也遠小于零的個數(shù)。Gallager指出只有wc≥3才能構(gòu)造出好的碼字；

l

如果H中各行和各列中1的個數(shù)不固定，則其對應(yīng)的LDPC碼為非規(guī)則的；

l理論證明，非規(guī)則的LDPC的性能優(yōu)于規(guī)則的LDPC碼。

l 簡單的實例：

例7．6．1

LDPC碼的校驗矩陣H的確定。 列中1的個數(shù)wc=3，對于H中的任意兩列，1在列中同一位置出現(xiàn)的次數(shù)（即兩個列向量1的位置交疊的次數(shù)）最多為一次。在圖中所示的部分H中，可以看出任何一組列向量對應(yīng)元素求和得到的新的向量都不會為零。上述這些特性保證了LDPC碼具有較大的最小碼距dmin。與傳統(tǒng)的分組碼相同，

LDPC碼的生成矩陣G可同對H進行變換得到，若H=[PT|I]，則G=[I|P]。 3．LDPC碼構(gòu)造方法：

l

最直接的方法是構(gòu)造具有上述特性的低密度奇偶校驗矩陣H；

l

隨機地生成全零的矩陣H，然后隨機地將矩陣中每列的wc個元素變?yōu)?，這樣產(chǎn)生的LDPC碼可能是非 規(guī)則的；

l

隨機地產(chǎn)生重量為wc的列向量，并以這些列向量為列組成矩陣H，并盡可能使H的行向量重量相同；

l

隨機生成的矩陣H每列1的個數(shù)為wc，每行1的個數(shù)為

wr，1在列中同一位置出現(xiàn)的次數(shù)至多為一次；

l

應(yīng)該保證H為滿秩矩陣。 4．

LDPC的編碼

l

如果構(gòu)造出了矩陣H，就可以通過變換得到

LDPC碼的生成矩陣G，G=[I|P]；

l

若原始信息序列為u，編碼后序列為c，則進行線性運算c=uG=[I|P]=[u|uP]就可以完成編碼；

l

需要大量的計算，這是因為要滿足H的低密度特性以及獲得較高的編碼增益，一般G的維數(shù)非常大（n非常大），例如，（10000，5000）的LDPC碼，其生成矩陣中的子陣P為