第5章有噪信道編碼

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

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

由于

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

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

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

bj的譯碼錯誤概率：

平均差錯率Pe

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

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

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

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

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

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

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

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

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

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

輸入等概（1）信道輸入是近似等概的：因為信道前級有信源編碼器存在。（2）極大似然譯碼規(guī)則近似最佳，可以放心使用。

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

bit/符號

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

無編碼

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

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

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

啟示：

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

定義：兩個等長符號序列和之間的漢明距離，記為，是與之間對應(yīng)位置上不同符號的個數(shù)。例：用漢明距離來度量兩個符號序列的“相似”程度：

?。号c的相似程度高。

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

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

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

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

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

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

K=2：

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

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

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

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

{0，1}。r=N－

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

的每個向量都是一個碼字。

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

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

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

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

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

bj的譯碼錯誤概率：

平均差錯率Pe

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