第六章有噪信道編碼需要掌握的內(nèi)容：譯碼規(guī)則與錯(cuò)誤概率的關(guān)系平均差錯(cuò)率與信道編碼的關(guān)系漢明距離有噪信道編碼定理線性分組碼第一節(jié)譯碼規(guī)則與錯(cuò)誤譯碼概率0011信源（信源編碼，信道編碼）譯碼（信源譯碼，信道譯碼）信道信宿一.譯碼規(guī)則譯碼函數(shù)又稱譯碼規(guī)則

注意:

譯碼規(guī)則是人為定的,對于同一個(gè)信道可有多個(gè)不同的譯碼規(guī)則

信道譯碼函數(shù)F是從輸出符號(hào)集合B到輸入符號(hào)集合A的映射定義0.80.20.10.9a1a2b1b2

例如：對于二元信道就可制定若干不同譯碼規(guī)則，如圖所示?！昂谩钡淖g碼規(guī)則的標(biāo)準(zhǔn)是：錯(cuò)誤譯碼概率小譯碼正確---如果接收到bj，按

譯成aj*

，而輸入的剛好是aj*bj的譯碼正確概率為：

bj的譯碼錯(cuò)誤概率為：二.錯(cuò)誤譯碼概率

譯碼錯(cuò)誤概率的統(tǒng)計(jì)平均稱為平均譯碼錯(cuò)誤概率或平均差錯(cuò)率，記為PePe與譯碼規(guī)則F有關(guān)

使Pe小的譯碼規(guī)則F是好的譯碼規(guī)則簡化Pe式為下面的形式：當(dāng)輸入等概:上式可化為：例6-1：

參見下圖，假設(shè)P(a1)=0.4,分別求出4種譯碼規(guī)則所對應(yīng)的平均差錯(cuò)率。0.80.20.10.9a1a2b1b2解：信道輸入概率矩陣和轉(zhuǎn)移矩陣分別為：

轉(zhuǎn)移矩陣各行元素乘以對應(yīng)的輸入概率，得聯(lián)合概率矩陣

譯碼規(guī)則F1對應(yīng)的平均差錯(cuò)率為

其它譯碼規(guī)則對應(yīng)的平均差錯(cuò)率分別為Pe(F2)=0.4 Pe(F3)=0.14 Pe(F4)=0.86四種規(guī)則相比，F(xiàn)3最好，F(xiàn)4最差第二節(jié)兩種典型的譯碼規(guī)則

一.最佳譯碼規(guī)則

平均差錯(cuò)率Pe與譯碼規(guī)則有關(guān)，使Pe達(dá)到最小的譯碼規(guī)則——最佳譯碼規(guī)則。

可以看出：要減小Pe

，必須減小各個(gè)接收符號(hào)的譯碼錯(cuò)誤概率，或者增大各個(gè)接收符號(hào)的譯碼正確概率。確定最佳譯碼規(guī)則的方法：該最佳譯碼規(guī)則稱為最大后驗(yàn)概率譯碼規(guī)則最大后驗(yàn)概率條件可等價(jià)為最大聯(lián)合概率條件,為什么呢?則最佳譯碼規(guī)則又可表示為：最佳譯碼規(guī)則又稱為最大聯(lián)合概率譯碼規(guī)則例6-2

參見下圖，假設(shè)P(a1)=0.4，求最佳譯碼規(guī)則。

0.80.20.10.9a1a2b1b2解：例6-1已經(jīng)求出聯(lián)合概率矩陣，重寫為則最大聯(lián)合概率譯碼規(guī)則為：對應(yīng)的平均差錯(cuò)概率：

——按最大轉(zhuǎn)移概率條件確定的譯碼規(guī)則例6-3：已知信道轉(zhuǎn)移矩陣，試確定譯碼規(guī)則。解：按轉(zhuǎn)移概率最大原則確定極大似然譯碼規(guī)則如下：

二、極大似然譯碼規(guī)則原因是：極大似然譯碼規(guī)則是按最大轉(zhuǎn)移概率條件確定的，即如果輸入等概，則

所以當(dāng)信道輸入等概率時(shí)，極大似然譯碼規(guī)則是最佳的。提問:為什么?第三節(jié)信道編碼的編碼原則二元信源和二元對稱信道的模型如下圖所示

DMCX{a1,a2}Y{b1,b2}a1=0a2=1b1=0b2=11-p1-pp=0.01p=0.01DMSU{u1,u2}信源的熵為：H（U）=logM=1比特/符號(hào)信道容量為：C=log2-H(0.99,0.01)=0.92比特/符號(hào)由圖可知：信源與信道之間不加信道編碼，則由于信道輸入等概分布，則極大似然譯碼規(guī)則就是最佳譯碼規(guī)則，根據(jù)信道轉(zhuǎn)移矩陣確定極大似然譯碼規(guī)則為：平均差錯(cuò)率為：提問：傳輸系統(tǒng)的Pe要求控制在10-6以下，而利用譯碼規(guī)則的Pe太高，如何降低平均差錯(cuò)率呢？－－－信道編碼一.簡單重復(fù)編碼

對信源符號(hào)進(jìn)行“重復(fù)2次”編碼:信道編碼f信道譯碼F“重復(fù)2次”編碼規(guī)則為

求出3次擴(kuò)展信道的轉(zhuǎn)移矩陣按極大似然譯碼規(guī)則得譯碼函數(shù)

即：

譯碼差錯(cuò)率為：結(jié)論：信道編碼降低平均錯(cuò)誤率提問：信道編碼對信息傳輸速率有什么影響呢？

信道編碼，或稱為糾錯(cuò)編碼，就是靠增加“冗余”碼元來克服或減輕噪聲影響的。結(jié)論：信道編碼降低了信道的信息傳輸率信道編碼之后的信息率或信道待傳的信息率為無信道編碼的信息率或信道待傳的信息率為

二.對符號(hào)串編碼(矢量編碼）例6-4：二元信源U，若取二元符號(hào)串“00，01，10，11”作為消息，則消息個(gè)數(shù)增加為M=4。提問：此時(shí)平均差錯(cuò)率又發(fā)生怎樣的變化呢？結(jié)論：增加信源消息個(gè)數(shù)，可提高信道的信息傳輸率取碼長N=3，則編碼后的信息率為

R=(log4)/3=2/3比特/碼元碼長N=3，可供選擇的碼字為選擇以下編碼函數(shù)：

根據(jù)信道轉(zhuǎn)移矩陣確定極大似然譯碼規(guī)則為

則平均差錯(cuò)率為：

結(jié)論：增加消息個(gè)數(shù)M與重復(fù)編碼相比，在提高信息率的同時(shí)會(huì)使平均差錯(cuò)率增大。第四節(jié)漢明距離兩個(gè)等長符號(hào)序列x和y之間的漢明距離，記為D(x,y)，是x與y之間對應(yīng)位置上不同符號(hào)的個(gè)數(shù)。解：求漢明距離：

D(x,z)=2;D(y,z)=3因此，z與x的相似程度高于與y的相似程度一.定義例6-5：

x=100111,y=111000,z=111111,比較z與x和y的相似程度。X和Y是二元序列，記為

是等長碼，則C中任意兩個(gè)不同碼字之間的漢明距離或碼間距離為碼C的最小碼間距離定義為二元對稱信道，可以根據(jù)漢明距離來決定譯碼規(guī)則

假如有一個(gè)信源有M個(gè)消息二元對稱信道的輸入符號(hào)集和輸出符號(hào)集分別為A={0，1}和B={0，1}。其N次擴(kuò)展信道的輸入符號(hào)集和輸出符號(hào)集分別為：經(jīng)N次擴(kuò)展信道傳送之后，按極大似然譯碼規(guī)則進(jìn)行譯碼記N長二元符號(hào)串為

由信道無記憶可知轉(zhuǎn)移概率為碼元錯(cuò)誤概率為p，正確概率為

則有：極大似然譯碼規(guī)則等價(jià)為最小漢明距離譯碼規(guī)則

最小距離譯碼規(guī)則可在一般信道中采用，但不一定與極大似然譯碼規(guī)則等價(jià)，只有對于二元對稱信道，它才與極大似然譯碼規(guī)則等價(jià)，并且當(dāng)輸入等概時(shí)是最佳的。

對于二元對稱信道，若輸入等概，無論用什么規(guī)則確定譯碼函數(shù)，與之對應(yīng)的平均差錯(cuò)率都可用漢明距離表示：

結(jié)論：第五節(jié)有噪信道編碼定理一.正定理（香農(nóng)第二定理）若信道是離散、無記憶、平穩(wěn)的，且信道容量為C，只要待傳送的信息率R<C，就一定能找到一種信道編碼方法，使得碼長足夠大時(shí)，平均差錯(cuò)率任意接近于零。二.逆定理若信道是離散、無記憶、平穩(wěn)的，且信道容量為C，只要待傳送的信息率R>C，就一定找不到一種信道編碼方法，使得碼長足夠大時(shí)，平均差錯(cuò)率任意接近于零。

信道編碼定理告訴我們：R<C時(shí)，通過編碼可使平均差錯(cuò)率逼近零；逆定理則說明：R>C時(shí)，無論如何編碼，都不可能使平均差錯(cuò)綠逼近零。因此，信道容量C是確保可靠性傳輸?shù)男畔鬏斅实纳舷?。第六?jié)糾錯(cuò)編碼

一.糾錯(cuò)碼分類（1）根據(jù)信道中的干擾類型，糾錯(cuò)碼分為：

反向重傳糾錯(cuò)檢錯(cuò)編碼檢錯(cuò)譯碼信道CmR反饋前向糾錯(cuò)糾錯(cuò)編碼糾錯(cuò)譯碼信道CmR混合糾錯(cuò)（2）根據(jù)不同的分組方式及隨后的映射關(guān)系，糾錯(cuò)碼分為：分組碼:先將信息序列分成K個(gè)符號(hào)一組，稱為信息組，然后在信息組中加入一些校驗(yàn)碼元組成N長碼字，該碼稱為（N，K）分組碼。（N，K）分組碼中的任一碼字的碼長為N，信息位數(shù)為K，校驗(yàn)位數(shù)為n-k。樹碼:信息序列以每K個(gè)碼元分段，編碼器輸出該段的校驗(yàn)碼元不僅與本段的K個(gè)信息碼元有關(guān)，而且還與前面若干段的信息碼元有關(guān)(3)根據(jù)信息碼元與校驗(yàn)碼元之間是否存在線性關(guān)系，糾錯(cuò)碼分為：

線性碼:非線性碼:線性碼的校驗(yàn)碼元是若干信息碼元的線性組合。線性碼具有很好的數(shù)學(xué)結(jié)構(gòu)，編譯碼比較簡單，性能優(yōu)于具有同樣糾錯(cuò)能力的非線性碼非線性碼的校驗(yàn)碼元與信息碼元不滿足線性關(guān)系1.生成矩陣和校驗(yàn)矩陣

二.線性分組碼有（5，2）分組碼,設(shè)

,其中為信息碼元，為校驗(yàn)碼元假設(shè)校驗(yàn)碼元由下列方程組得到,其中表示模2加.

方程組改寫成矩陣形式有:

令則:式中H稱為一致校驗(yàn)矩陣

為維的單位陣維的一般矩陣為校驗(yàn)矩陣與碼字具有正交性

可知:由校驗(yàn)方程可改寫為:

令，則上述方程組可用矩陣表示：為維矢量，為維矢量，表示信息碼元為維矢量，稱為的生成矩陣

式中為維的單位陣，為維的一般矩陣

寫成分塊矩陣，即生成矩陣與校驗(yàn)矩陣H的關(guān)系為：則有:例6-6：已知一個(gè)線性分組碼的生成矩陣為求生成的線性分組碼以及校驗(yàn)矩陣H.解：由生成矩陣可知信息位有3位，則線性分組碼為（7，3）分組碼，生成矩陣生成的碼字為：由知由知，2.線性分組碼的糾、檢錯(cuò)能力

檢錯(cuò):

譯碼器能檢測到是否有錯(cuò)誤發(fā)生。碼的檢錯(cuò)能力用檢測到的錯(cuò)誤位數(shù)描述。糾錯(cuò):譯碼器不但能檢測是否有錯(cuò)誤發(fā)生，并能糾正錯(cuò)誤。碼的糾錯(cuò)能力用糾正錯(cuò)誤的位數(shù)描述。碼的糾檢錯(cuò)能力與碼的最小漢明距離密切相關(guān)，具體結(jié)論如下：解：因?yàn)閐min=3=2+1，所以能檢出td=2個(gè)錯(cuò)誤譯碼方法為：

000譯為0，111譯為1，其他置為“錯(cuò)誤”標(biāo)志因?yàn)閐min=3=2*1+1，所以能糾正tc=1個(gè)錯(cuò)誤譯碼方法為：

000，001，010，100譯為0；011，101，110，111譯為1但該碼不能在糾正tc=1個(gè)錯(cuò)誤的同時(shí)又能檢出td=2個(gè)錯(cuò)誤例6-7：簡單重復(fù)2次編碼，編碼規(guī)則為0→000，1→111，碼C={c1,c2}={000,111},dmin=3。試問該碼糾檢錯(cuò)能力如何？例6-8：簡單重復(fù)3次編碼，編碼規(guī)則為0→0000，1→1111碼C={c1,c2}={0000,1111},dmin=4。試問該碼糾檢錯(cuò)能力如何？接收序列譯碼接收序列譯碼0000010000000101001Error001001010Error0011Error10111010001100Error0101Error110110110Error111010111111111解：由dmin=4=3+1，知能檢出td=3個(gè)錯(cuò)誤

譯碼方法為：0000譯為0，1111譯為1，其他置為“錯(cuò)誤”標(biāo)志由dmin=4>2*1+1和dmin=4=1+2+1，知能糾正tc=1個(gè)錯(cuò)誤，同時(shí)能檢出td=2個(gè)錯(cuò)誤，譯碼方法為：例6-9：比較（5，2）線性碼和“重復(fù)2次”碼的糾、檢錯(cuò)能力和信息率。解：由例6-6和第三節(jié)的“簡單重復(fù)編碼”可知：“重復(fù)2次”碼的糾、檢錯(cuò)能力和信息率為：（1）dmin=3，能檢出td=2個(gè)錯(cuò)誤或糾正tc=1個(gè)錯(cuò)誤。（2）R=1/3(比特/碼元)由碼字生成式求出與各信息組對應(yīng)的碼字：

信息組碼字c0000000010110110101111111010（5，2）線性碼的生成矩陣為結(jié)論：（5，2）的信息率比“重復(fù)2次”碼提高了一倍。碼C={c}的最小漢明距離為dmin=3，糾、檢錯(cuò)能力與“重復(fù)2次”碼相同，能檢出td=2個(gè)錯(cuò)誤或糾正tc=1個(gè)錯(cuò)誤。由第三節(jié)的“簡單重復(fù)編碼”可知:R=2/3(比特/碼元)兩者的平均差錯(cuò)率處于同一數(shù)量級，原因是它們的最小漢明距離相同3.伴隨式和伴隨式譯碼若發(fā)送碼字為,則由于在傳輸過程中受到各種干擾，接收序列不一定等于發(fā)送的碼字兩者之間的差異即是出現(xiàn)的差錯(cuò)。差錯(cuò)是多樣化的，定義差錯(cuò)的式樣為差錯(cuò)圖樣則有對于二元序列情形，模2減等同模2加，則有：以及S是傳輸是否出錯(cuò)的標(biāo)志,稱為伴隨式.譯碼時(shí)，需由來確定發(fā)送碼字,若能確定差錯(cuò)