第5章有噪信道編碼

第5章有噪信道編碼第一頁(yè)，共61頁(yè)。問題的提出愿望：信息傳輸多快好省?，F(xiàn)實(shí)：（1）速度：受信道容量的限制，不可能無限大；（第3章）（2）質(zhì)量：受信道噪聲的干擾，傳輸錯(cuò)誤不可避免。衡量信息傳輸可靠性的指標(biāo)：平均差錯(cuò)率Pe。Pe與信道的統(tǒng)計(jì)特性有關(guān)，不可能為零，有時(shí)甚至很大。降低Pe的方法：先對(duì)消息進(jìn)行編碼再送入信道傳送，這種為降低平均差錯(cuò)率而進(jìn)行的編碼稱為信道編碼；在信道輸出端加信道譯碼器進(jìn)行信息還原。香農(nóng)第二編碼定理所給出的結(jié)論：只要信道編碼和譯碼的方法得當(dāng)，就可使平均差錯(cuò)率趨于零。

編碼信道信道編碼器f信道信道譯碼器F第二頁(yè)，共61頁(yè)。各節(jié)內(nèi)容5.1譯碼規(guī)則與錯(cuò)誤概率5.2兩種典型的譯碼規(guī)則5.3平均差錯(cuò)率與信道編碼5.4漢明距離5.5有噪信道編碼定理與逆定理5.6線性分組碼第三頁(yè)，共61頁(yè)。5.1譯碼規(guī)則與錯(cuò)誤概率信道編碼是一個(gè)一一對(duì)應(yīng)的變換或函數(shù)，稱為編碼函數(shù)f；信道譯碼也是一個(gè)函數(shù)，稱為譯碼函數(shù)F。編碼信道信道編碼器f信道信道譯碼器F

由于

是一一對(duì)應(yīng)變換，其反變換

唯一確定。因此，討論譯碼函數(shù)時(shí)，只考慮從中還原出就可以了。DMC信道譯碼F第四頁(yè)，共61頁(yè)。1、譯碼規(guī)則譯碼規(guī)則是由人為制訂的；對(duì)于同一個(gè)信道可制訂出多種譯碼規(guī)則；“好”的譯碼規(guī)則：平均差錯(cuò)率小。DMC信道譯碼F

信道譯碼函數(shù)F，又稱譯碼規(guī)則，是從信道輸出符號(hào)集合B到信道輸入符號(hào)集合A的映射：第五頁(yè)，共61頁(yè)。2、錯(cuò)誤概率平均差錯(cuò)率Pe與譯碼規(guī)則F有關(guān)。DMC信道譯碼F譯碼規(guī)則：bj的譯碼正確概率是后驗(yàn)概率：

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

平均差錯(cuò)率Pe

:第六頁(yè)，共61頁(yè)。平均差錯(cuò)率Pe的計(jì)算公式DMC信道譯碼F譯碼規(guī)則：平均差錯(cuò)率Pe

:當(dāng)輸入等概時(shí)：第七頁(yè)，共61頁(yè)。例：譯碼規(guī)則與平均差錯(cuò)率(1)找出所有可能的譯碼規(guī)則；(2)求出各個(gè)譯碼規(guī)則對(duì)應(yīng)的平均差錯(cuò)率。4種譯碼規(guī)則：F3最好F4最差第八頁(yè)，共61頁(yè)。5.2兩種典型的譯碼規(guī)則兩種典型的譯碼規(guī)則：最佳譯碼規(guī)則、極大似然譯碼規(guī)則

1、最佳譯碼規(guī)則：平均差錯(cuò)率最小的譯碼規(guī)則。DMC信道譯碼F

按“后驗(yàn)概率最大”原則定出，又稱最大后驗(yàn)概率譯碼規(guī)則

按“聯(lián)合概率最大”原則定出，又稱最大聯(lián)合概率譯碼規(guī)則

第九頁(yè)，共61頁(yè)。例：求最佳譯碼規(guī)則求出最佳譯碼規(guī)則及平均差錯(cuò)率。已知的結(jié)論：第十頁(yè)，共61頁(yè)。2、極大似然譯碼規(guī)則DMC信道譯碼F

按“轉(zhuǎn)移概率最大”原則定出，稱為極大似然譯碼規(guī)則。實(shí)際應(yīng)用中，經(jīng)常只知道信道的統(tǒng)計(jì)特性(轉(zhuǎn)移概率)，而不知道信源的統(tǒng)計(jì)特性(輸入概率)，這時(shí)求不出聯(lián)合概率和后驗(yàn)概率，因此無法確定最佳譯碼規(guī)則。既然只知道轉(zhuǎn)移概率，就只能按轉(zhuǎn)移概率的某種約束條件制訂譯碼規(guī)則。按最大轉(zhuǎn)移概率條件來確定的譯碼規(guī)則，稱為極大似然譯碼規(guī)則。第十一頁(yè)，共61頁(yè)。例：極大似然譯碼規(guī)則已知信道轉(zhuǎn)移矩陣，確定譯碼規(guī)則。只已知轉(zhuǎn)移概率，無法找出最佳譯碼規(guī)則，只能采用極大似然譯碼規(guī)則。將轉(zhuǎn)移矩陣各列最大的轉(zhuǎn)移概率標(biāo)出，重寫轉(zhuǎn)移矩陣如下：

按“轉(zhuǎn)移概率最大”原則確定極大似然譯碼規(guī)則：

注：無法求出平均差錯(cuò)率第十二頁(yè)，共61頁(yè)。極大似然譯碼規(guī)則與最佳譯碼規(guī)則

等價(jià)的條件極大似然譯碼規(guī)則最佳譯碼規(guī)則結(jié)論：信道輸入等概時(shí)，極大似然譯碼規(guī)則與最佳譯碼規(guī)則等價(jià)。證明：

輸入等概（1）信道輸入是近似等概的：因?yàn)樾诺狼凹?jí)有信源編碼器存在。（2）極大似然譯碼規(guī)則近似最佳，可以放心使用。

注：第十三頁(yè)，共61頁(yè)。5.3平均差錯(cuò)率與信道編碼Pe與譯碼規(guī)則有關(guān)，即使選擇最佳譯碼規(guī)則，也只能使Pe有限地減小，難以滿足信息傳遞系統(tǒng)的高可靠性要求。要進(jìn)一步降低Pe，必須在傳送之前進(jìn)行信道編碼。DMCDMS二元信源的消息個(gè)數(shù)：熵：

bit/符號(hào)

由于信道輸入等概，這時(shí)極大似然譯碼規(guī)則是最佳的。無信道編碼時(shí)：例：第十四頁(yè)，共61頁(yè)。1、“簡(jiǎn)單重復(fù)”編碼信道譯碼F信道編碼f信道編碼之后的信息率：bit/符號(hào)第十五頁(yè)，共61頁(yè)。信道編碼前后比較

無編碼

bit/符號(hào)“重復(fù)2次”編碼

bit/符號(hào)“重復(fù)”編碼的其它結(jié)果bit/符號(hào)bit/符號(hào)bit/符號(hào)結(jié)論：隨著“重復(fù)”次數(shù)的增加，Pe下降，R也跟著下降。第十六頁(yè)，共61頁(yè)。2、對(duì)符號(hào)串編碼信道譯碼F信道編碼fbit/符號(hào)結(jié)論：增多消息個(gè)數(shù)M會(huì)提高R，但會(huì)使Pe增大。

第十七頁(yè)，共61頁(yè)。信道編碼的有關(guān)結(jié)論及啟示由前面的例子得出的結(jié)論：增加“重復(fù)”次數(shù)N（增大碼長(zhǎng)），會(huì)使Pe下降(好)，但R也跟著下降(不好)。增多消息個(gè)數(shù)M會(huì)提高R(好)，但會(huì)使Pe增大(不好)。

啟示：

增大碼長(zhǎng)N，同時(shí)適當(dāng)增多消息個(gè)數(shù)M，有可能使平均差錯(cuò)率降低到要求的范圍以內(nèi)，而又能使信息率不降低或降低不多。第十八頁(yè)，共61頁(yè)。（N，K）分組碼取M=4、N=5：5次擴(kuò)展信道(5，2)分組碼：碼長(zhǎng)N為5，前2個(gè)碼元是信息位（K），后3個(gè)碼元是校驗(yàn)位。bit/符號(hào)bit/符號(hào)M=4、N=3：第十九頁(yè)，共61頁(yè)。5.4漢明距離上節(jié)討論譯碼時(shí)曾經(jīng)提過，可將接收序列譯為與之最“相似”的輸入序列（碼字）。如何定量描述符號(hào)序列之間的“相似”程度呢？漢明（R.W.Hamming）受距離概念的啟發(fā),在符號(hào)序列之間引入漢明距離，用來定量描述符號(hào)序列之間的“相似”程度。第二十頁(yè)，共61頁(yè)。1、漢明距離的定義與性質(zhì)

定義：兩個(gè)等長(zhǎng)符號(hào)序列和之間的漢明距離，記為，是與之間對(duì)應(yīng)位置上不同符號(hào)的個(gè)數(shù)。例：用漢明距離來度量?jī)蓚€(gè)符號(hào)序列的“相似”程度：

?。号c的相似程度高。

大：與的相似程度低。相似程度的高低是相對(duì)而言的。漢明距離的性質(zhì)（距離公理）：（1）非負(fù)性：，當(dāng)且僅當(dāng)時(shí)等號(hào)成立；（2）對(duì)稱性：（3）三角不等式：第二十一頁(yè)，共61頁(yè)。2、二元序列的漢明距離二元序列漢明重量：二元序列中含“1”的個(gè)數(shù)。為N個(gè)“0”符號(hào)組成的串第二十二頁(yè)，共61頁(yè)。3、碼的相似性最小碼間距離dmin是衡量碼的性能的重要參數(shù)，碼的dmin小：說明有些碼字受干擾后容易變?yōu)榱硪淮a字，譯碼時(shí)就會(huì)出錯(cuò)。進(jìn)行信道編碼時(shí)，只要條件允許，盡量選擇最小碼間距離大一些的碼。等長(zhǎng)碼碼間距離：碼C的最小碼間距離：舉例：第二十三頁(yè)，共61頁(yè)。4、最?。h明）距離譯碼規(guī)則N次擴(kuò)展信道信道譯碼F信道編碼fDMC極大似然譯碼規(guī)則：與漢明距離有何聯(lián)系？

第二十四頁(yè)，共61頁(yè)。信道譯碼F信道譯碼f記：假設(shè)最小（漢明）距離譯碼規(guī)則：

極大似然規(guī)則：第二十五頁(yè)，共61頁(yè)。幾點(diǎn)說明最小距離譯碼規(guī)則可在一般信道中采用，但不一定與極大似然譯碼規(guī)則等價(jià)；對(duì)于二元對(duì)稱信道，若正確概率大于錯(cuò)誤概率，則最小距離譯碼規(guī)則與極大似然譯碼規(guī)則等價(jià)，并且當(dāng)輸入等概時(shí)是最佳的。第二十六頁(yè)，共61頁(yè)。漢明距離與平均差錯(cuò)率前提：二元對(duì)稱信道輸入等概。譯碼函數(shù)：平均差錯(cuò)率：5次擴(kuò)展信道例（5,2）分組碼第二十七頁(yè)，共61頁(yè)。用碼C={00000，01101，10111，11010}傳送信息，若采用最小距離譯碼規(guī)則，那么，當(dāng)收到“11011”、“00010”、“10011”、“01111”以及“00101”時(shí)，分別譯為什么碼字？00000011011011111010110110001010011011110010141342344112312212235最?。h明）距離譯碼規(guī)則：

碼C={00000，01101，10111，11010}的最小漢明距離？假設(shè)碼字等概率分布，求該碼的碼率？第二十八頁(yè)，共61頁(yè)。5.5有噪信道編碼定理與逆定理在有噪信道上傳遞信息，難免會(huì)出現(xiàn)差錯(cuò)；為了降低平均差錯(cuò)率，可將每個(gè)消息重復(fù)傳送若干次，但這樣又降低了信息傳遞的速度。理論問題：是否能找到一種信道編碼方法能同時(shí)保證差錯(cuò)率和信息傳輸速度的要求呢？1948年，香農(nóng)從理論上得出結(jié)論：對(duì)于有噪信道，只要通過足夠復(fù)雜的編碼方法，就能使信息率達(dá)到信道的極限通過能力——信道容量，同時(shí)使平均差錯(cuò)率逼近零。這一結(jié)論稱為香農(nóng)第二編碼定理或有噪信道編碼定理，是有關(guān)信息傳輸?shù)淖罨窘Y(jié)論。第二十九頁(yè)，共61頁(yè)。編碼定理

定理（香農(nóng)第二編碼定理）：若信道是離散、無記憶、平穩(wěn)的，且信道容量為C，只要待傳送的信息率R<C，就一定能找到一種信道編碼方法，使得碼長(zhǎng)足夠大時(shí)，平均差錯(cuò)率任意接近于零。（P152,定理5.3）注：（1）香農(nóng)第二編碼定理實(shí)際上是一個(gè)存在性定理，它指出：在R<C時(shí)，肯定存在一種好的信道編碼方法，能夠編出一種好碼，用這種好碼來傳送消息可使平均差錯(cuò)率逼近零。（2）香農(nóng)并沒有給出能夠找到好碼的具體方法。（3）香農(nóng)第二編碼定理的證明很復(fù)雜，略。第三十頁(yè)，共61頁(yè)。信道編碼逆定理

定理（信道編碼逆定理）：若信道是離散、無記憶、平穩(wěn)的，且信道容量為C，如果信息率R>C，則肯定找不到一種信道編碼方法，使得碼長(zhǎng)足夠大時(shí)，平均差錯(cuò)率任意接近于零。（P154定理5.4）例：若有一等概率分布的二元信源，每秒鐘發(fā)出3個(gè)信源符號(hào)。將此信源的輸出符號(hào)送入某二元無噪無損信道中進(jìn)行傳輸，而信道每秒鐘只傳遞兩個(gè)二元符號(hào)。試問信源能否在此信道中進(jìn)行無差錯(cuò)傳輸？第三十一頁(yè)，共61頁(yè)。5.6線性分組碼信道編碼的目的是為了降低平均差錯(cuò)率，又稱糾錯(cuò)編碼。香農(nóng)第二編碼定理告訴我們，只要信息率小于信道容量，那么就可使平均差錯(cuò)率接近于零，但香農(nóng)并沒有給出切實(shí)可行的實(shí)現(xiàn)方法。香農(nóng)的有噪聲信道定理的意義在于，它告訴我們什么是通過努力可以做到的事情，什么是不可能做到的事情。糾錯(cuò)編碼理論幾乎與信息論同時(shí)創(chuàng)立，創(chuàng)始人是漢明。糾錯(cuò)編碼的基本思路：引入可控冗余，即在信息序列中加入一些冗余碼元（或稱校驗(yàn)碼元）。譯碼：利用碼元之間的相關(guān)性質(zhì)來檢測(cè)錯(cuò)誤和糾正錯(cuò)誤。第三十二頁(yè)，共61頁(yè)。糾錯(cuò)編碼的基本概念分組碼：先將信息序列分成K個(gè)符號(hào)一組，稱為信息組，然后在信息組中加入一些校驗(yàn)碼元組成N長(zhǎng)碼字，由此得到的碼稱為（N，K）分組碼。分組碼中的任一碼字的碼長(zhǎng)為N，所含的信息位數(shù)目為K、校驗(yàn)位數(shù)目為N-K。線性碼：線性碼的最重要性質(zhì)是線性特性，即碼中任意兩個(gè)碼字的和仍為碼字。否則為非線性碼。循環(huán)碼：循環(huán)碼是線性碼的一個(gè)子集。循環(huán)碼中任一碼字循環(huán)移位后仍為該碼的碼字。否則為非循環(huán)碼。第三十三頁(yè)，共61頁(yè)。一致性校驗(yàn)矩陣H1、線性分組碼的生成矩陣和校驗(yàn)矩陣（以（5，2）分組碼為例）碼字長(zhǎng)度N=5：編碼函數(shù)：信息組長(zhǎng)度

K=2：

碼字由信息元的模2線性組合生成，因此是二元線性分組碼，簡(jiǎn)稱為線性碼。

編碼函數(shù)的矩陣表示：校驗(yàn)方程的矩陣表示：生成矩陣G第三十四頁(yè)，共61頁(yè)。二元（N，K）線性碼碼字，N維行陣：信息組，

K維行陣：碼字生成式：校驗(yàn)方程：G：K×N生成矩陣，其元素取值于二元集合

{0，1}。H：r×N一致性校驗(yàn)矩陣，其元素取值于二元集合

{0，1}。r=N－

K：校驗(yàn)位數(shù)目。第三十五頁(yè)，共61頁(yè)。二元（N，K）線性碼（續(xù)一）（1）G

的每個(gè)向量都是一個(gè)碼字。

例：(2)二元(N，K)線性碼C={c}可看成一個(gè)N重K維線性空間，G的K個(gè)相互獨(dú)立的行向量是它的一組基底。(3)任意K個(gè)相互獨(dú)立的N長(zhǎng)碼字都可作為N重維碼空間的一組基底，用這個(gè)碼字當(dāng)作行向量組成生成矩陣，即可生成所有碼字。第三十六頁(yè)，共61頁(yè)。二元（7,3）分組碼G1000001010011100101110111碼G2000001010011100101110111碼G3000001010011100101110111碼第三十七頁(yè)，共61頁(yè)。二元（N，K）線性碼（續(xù)二）系統(tǒng)碼：碼字的前（或后）K位照搬信息組的K個(gè)信息元。對(duì)于前K位為信息元的系統(tǒng)碼，生成矩陣G可分塊成：校驗(yàn)方程：gi是碼字，滿足校驗(yàn)方程。驗(yàn)證：例：第三十八頁(yè)，共61頁(yè)。2、漢明距離與碼的糾、檢錯(cuò)能力檢錯(cuò)：譯碼器能檢測(cè)到是否有錯(cuò)誤發(fā)生，碼的檢錯(cuò)能力用檢測(cè)到的錯(cuò)誤位數(shù)td描述；糾錯(cuò)：譯碼器不但能檢測(cè)到是否有錯(cuò)誤發(fā)生，而且能糾正發(fā)生的錯(cuò)誤，碼的糾錯(cuò)能力用糾正錯(cuò)誤的位數(shù)tc描述。無法檢出或糾正的錯(cuò)誤：碼字出錯(cuò)而變?yōu)榱硪淮a字。這種情況最易發(fā)生在較為相似的碼字之間。碼的糾、檢錯(cuò)能力與碼的最小漢明距離關(guān)系密切，具體結(jié)論如下：(1)一個(gè)碼能夠檢測(cè)出td個(gè)錯(cuò)誤的充要條件：dmin≥td+1(2)一個(gè)碼能夠糾正tc個(gè)錯(cuò)誤的充要條件：dmin≥2tc+1(3)一個(gè)碼能夠糾正tc個(gè)錯(cuò)誤，同時(shí)又能夠檢測(cè)出td個(gè)錯(cuò)誤的充要條件：dmin>2tc+1和dmin≥tc+td+1第三十九頁(yè)，共61頁(yè)。二元線性分組碼的最小漢明距離

結(jié)論：二元線性分組碼的最小漢明距離等于該碼非零碼字的最小漢明重量。例：C={00000,01101,10111,11010}，求最小漢明距離。Wmin=3dmin=Wmin=3第四十頁(yè)，共61頁(yè)。例“重復(fù)2次”編碼的檢錯(cuò)和糾錯(cuò)能力“重復(fù)2次”編碼：0→000，1→111碼字：C={000，111}，dmin=3接收序列譯碼0000001Error010Error011Error100Error101Error110Error1111檢錯(cuò)：接收序列譯碼00000010010001111000101111011111糾錯(cuò)：第四十一頁(yè)，共61頁(yè)。例比較(5，2)線性碼和“重復(fù)2次”碼(5，2)線性碼：信息組m碼字c0000000010110110101111111010

與“重復(fù)2次”碼的最小漢明距離相同，因此，檢、糾錯(cuò)能力相同：能檢出2個(gè)錯(cuò)誤或糾正1個(gè)錯(cuò)誤?！爸貜?fù)2次”碼：(5，2)線性碼：bit/符號(hào)bit/符號(hào)第四十二頁(yè)，共61頁(yè)。3、線性碼的伴隨式與伴隨式譯碼考慮二元序列情形，若發(fā)送碼字為c，則接收序列y可表示成：差錯(cuò)圖樣e：當(dāng)碼字第i位發(fā)生錯(cuò)誤時(shí)，ei=1，否則ei=0。譯碼：由接收序列y來確定發(fā)送碼字c。若能確定差錯(cuò)圖樣e，就可得到碼字c的估計(jì)值：校驗(yàn)方程：伴隨式：表明有錯(cuò)誤存在

伴隨式譯碼：根據(jù)伴隨式確定差錯(cuò)圖樣，再得到碼字的估計(jì)值。伴隨式譯碼步驟：（1）由接收序列按計(jì)算伴隨式：（2）由伴隨式找出差錯(cuò)圖樣：（3）由得出碼字的估計(jì)值：第四十三頁(yè)，共61頁(yè)。y0y1yn-1s0s1sr-1e0e1en-1c0c1cn-1（n，k）線性分組碼一般譯碼電路S=yHTS=EHT^C=y+E接收矢量緩存器伴隨式計(jì)算電路錯(cuò)誤圖樣產(chǎn)生器n級(jí)移位寄存器輸出伴隨式譯碼第四十四頁(yè)，共61頁(yè)。例：計(jì)算(7,3)碼接收碼字y的伴隨式，確定發(fā)送碼字的估值。（1）設(shè)發(fā)送碼字C=1010011，接收碼字y=1010011，（2）設(shè)發(fā)送碼字C=1010011，接收碼字y=1110011；（3）設(shè)發(fā)送碼字C=1010011，接收碼字y=0011011.例：某(5,2)線性碼的生成矩陣，設(shè)接收碼字y=10101。 請(qǐng)先構(gòu)造該碼的標(biāo)準(zhǔn)陣列譯碼表，然后譯出發(fā)送碼字的估值。第四十五頁(yè)，共61頁(yè)。設(shè)碼為C={11100，01001，10010，00111}（1）求該碼的最小漢明距離；（2）假設(shè)碼字等概率分布，求該碼的碼率；（3）若采用最小距離譯碼規(guī)則，那么，當(dāng)收到“10000”、“01100”以及“00100”時(shí)，分別譯為什么碼字？（4）該碼能檢出幾位錯(cuò)誤？能糾正幾位錯(cuò)誤？第四十六頁(yè)，共61頁(yè)。若信道輸入概率為，試確定最佳譯碼規(guī)則和極大似然譯碼規(guī)則，并計(jì)算出相應(yīng)的平均差錯(cuò)率。

設(shè)有DMS，其轉(zhuǎn)移矩陣為第四十七頁(yè)，共61頁(yè)。通信的有效性問題：即如何通過對(duì)信源進(jìn)行編碼，壓縮信源的多余度，提高傳輸?shù)男省Ｍㄐ诺目煽啃詥栴}：即消息通過信道傳輸時(shí)如何選擇編碼方案以減少差錯(cuò)。通信的可靠性顯然與信道的統(tǒng)計(jì)特性有關(guān)，因?yàn)楦蓴_是造成錯(cuò)誤的主要因素。其次，編碼方法和譯碼方法也將影響信息傳輸?shù)目煽啃?。有噪信道編碼第四十八頁(yè)，共61頁(yè)。5.1譯碼規(guī)則與平均差錯(cuò)率DMC信道譯碼F信道譯碼函數(shù)F，又稱譯碼規(guī)則，是從信道輸出符號(hào)集合B到信道輸入符號(hào)集合A的映射：bj的譯碼正確概率是后驗(yàn)概率：

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

平均差錯(cuò)率Pe

:第四十九頁(yè)，共61頁(yè)。5.2最佳譯碼規(guī)則與極大似然譯碼規(guī)則極大似然譯碼規(guī)則最佳譯碼規(guī)則結(jié)論：信道輸入等概時(shí)，極大似然譯碼規(guī)則與最佳譯碼規(guī)則等價(jià)。DMC信道譯碼F第五十頁(yè)，共61頁(yè)。5.3平均差錯(cuò)率與信道編碼DMCDMS無信源編碼時(shí)：第五十一頁(yè)，共61頁(yè)。1、“簡(jiǎn)單重復(fù)”編碼信道譯碼F信道編碼f信道編碼之后的信息率：bit/符號(hào)第五十二頁(yè)，共61頁(yè)。2、對(duì)符號(hào)串編碼信道譯碼F信道編碼fbit/符號(hào)第五十三頁(yè)，共6