通信原理-CH11-差錯控制編碼和線性分組碼課件

第十一章差錯控制編碼和線性分組碼第十一章差錯控制編碼和線性分組碼2主要內(nèi)容和重點(diǎn)差錯控制編碼的基本概念線性分組碼性質(zhì)、基本原理校正子監(jiān)督矩陣生成矩陣漢明碼循環(huán)碼概念及性質(zhì)生成多項式生成矩陣與監(jiān)督矩陣編碼器2主要內(nèi)容和重點(diǎn)差錯控制編碼的基本概念32.1引言

為什么要引入差錯控制編碼？什么是差錯控制編碼（信道編碼）？差錯控制編碼的3種方式信道發(fā)生差錯的模式差錯控制編碼的基本原理差錯控制編碼的分類編碼信道及香農(nóng)編碼定理32.1引言為什么要引入差錯控制編碼？42.1引言

為什么要引入差錯控制編碼？在實(shí)際信道上傳輸數(shù)字信號時，由于信道傳輸特性不理想及加性噪聲的影響，接收端所收到的數(shù)字信號不可避免地會發(fā)生錯誤為了在已知信噪比情況下達(dá)到一定的誤比特率指標(biāo)，應(yīng)該合理設(shè)計基帶信號，選擇調(diào)制解調(diào)方式，采用時域、頻域均衡，使誤比特率盡可能降低但若誤比特率仍不能滿足要求，則必須采用信道編碼（即差錯控制編碼），將誤比特率進(jìn)一步降低42.1引言為什么要引入差錯控制編碼？52.1引言

什么是差錯控制編碼差錯控制編碼的基本思路：在發(fā)送端將被傳輸?shù)男畔⒏缴弦恍┍O(jiān)督碼元，這些多余的碼元與信息碼元之間以某種確定的規(guī)則相互關(guān)聯(lián)（約束）接收端按照既定的規(guī)則校驗(yàn)信息碼元與監(jiān)督碼元之間的關(guān)系，一旦傳輸發(fā)生差錯，則信息碼元與監(jiān)督碼元的關(guān)系就受到破壞，從而接收端可以發(fā)現(xiàn)錯誤乃至糾正錯誤差錯控制編碼所要解決的問題：各種編碼和譯碼方法52.1引言什么是差錯控制編碼62.1引言

差錯控制的三種方式檢錯重發(fā)（ARQ）在接收端根據(jù)編碼規(guī)則進(jìn)行檢查，如果發(fā)現(xiàn)規(guī)則被破壞，則通過反向信道要求發(fā)送端重新發(fā)送，直到接收端檢查無誤為止ARQ系統(tǒng)的重發(fā)機(jī)制：停發(fā)等候重發(fā)、返回重發(fā)和選擇重發(fā)需要反饋信道，效率較低，但是性能很好發(fā)收能夠發(fā)現(xiàn)錯誤的碼應(yīng)答信息62.1引言差錯控制的三種方式發(fā)收能夠發(fā)現(xiàn)錯誤的碼應(yīng)答72.1引言

差錯控制的三種方式（續(xù)）前向糾錯（FEC）發(fā)送端發(fā)送能糾正錯誤的編碼，在接收端根據(jù)接收到的碼和編碼規(guī)則，能自動糾正傳輸中的錯誤不需要反饋信道，實(shí)時性好，但是隨著糾錯能力的提高，編譯碼設(shè)備復(fù)雜

發(fā)收可以糾正錯誤的碼72.1引言差錯控制的三種方式（續(xù)）發(fā)收可以糾正錯誤的82.1引言

差錯控制的三種方式（續(xù)）混合方式結(jié)合FEC和ARQ：在糾錯能力范圍內(nèi)，自動糾正錯誤，超出糾錯范圍則要求發(fā)送端重新發(fā)送發(fā)收可以發(fā)現(xiàn)和糾正錯誤的碼應(yīng)答信號82.1引言差錯控制的三種方式（續(xù)）發(fā)收可以發(fā)現(xiàn)和糾正92.1引言

信道發(fā)生差錯的模式隨機(jī)差錯：差錯的出現(xiàn)是隨機(jī)的，差錯出現(xiàn)的位置是隨機(jī)分布的一般由信道的加性隨機(jī)噪聲引起這種信道稱為隨機(jī)信道

突發(fā)差錯：差錯的出現(xiàn)是一連串出現(xiàn)的。這種情況如移動通信中信號在某一段時間內(nèi)發(fā)生衰落，造成一串差錯；光盤上的一條劃痕等等這樣的信道稱之為突發(fā)信道

混合差錯：既有突發(fā)錯誤又有隨機(jī)差錯的情況這種信道稱之為混合信道

92.1引言信道發(fā)生差錯的模式102.1引言

差錯控制編碼的基本原理以差錯重發(fā)編碼來闡述差錯編碼在相同的信噪比情況下為什么會獲得更好的系統(tǒng)性能？例1：假設(shè)發(fā)送的信息0、1等概，采用2PSK方式，則最佳接收的系統(tǒng)誤比特率為，現(xiàn)假設(shè)如果將信息0編碼成00，信息1編碼成11，則在接收端：如果發(fā)送00，收到01、10，知道發(fā)生了差錯，要求發(fā)送端重新傳輸，直到傳送正確為止只有當(dāng)收到11時，我們才錯誤地認(rèn)為當(dāng)前發(fā)送的是1因此在這種情況下發(fā)生譯碼錯誤的概率是同理，如果發(fā)送的是11，只有收到00時才可能發(fā)生錯誤譯碼，因此在這種情況下發(fā)生譯碼錯誤的概率是故采用00、11編碼的系統(tǒng)誤比特率為102.1引言差錯控制編碼的基本原理112.1引言

差錯控制編碼的基本原理（續(xù)）依此類推，可知：采用000、111編碼的ARQ系統(tǒng)誤比特率是多少？采用0000、1111編碼的ARQ系統(tǒng)誤比特率是多少？例2，如例1，如果0、1采用00000、11111編碼，在接收端用如下的譯碼方法，每收到5個比特譯碼一次，采用大數(shù)判決，即5個比特中0的個數(shù)大于1的個數(shù)則譯碼成0，反之譯碼成1；不采用ARQ方式。那么，這種編碼方式就變成了糾錯編碼由于傳輸錯誤當(dāng)接收端收到11000，10100，10010，10001，01100，01010，01001，00110，00101，00011中的任何一種時，都可以自動糾正成00000課外題：請計算在這種情況下的系統(tǒng)性能上述例1、例2的編碼方式叫重復(fù)碼112.1引言差錯控制編碼的基本原理（續(xù)）122.1引言

差錯控制編碼的基本原理（續(xù)）例3，2PSK系統(tǒng)中誤比特率與Es/N0有關(guān)我們看到，重復(fù)碼中假設(shè)傳輸時每個符號的Es/N0相等，因此才得到以上的性能分析對比但是如果我們以Eb/N0的指標(biāo)進(jìn)行比較，則我們看到例1的例2的如果要求各系統(tǒng)在Eb/N0相同的情況下進(jìn)行比較（n重復(fù)碼中用了n倍能量來傳輸一個比特，從每個比特能量的角度來看），則可看到這2種系統(tǒng)性能相近（即獲得相近的編碼增益）122.1引言差錯控制編碼的基本原理（續(xù)）132.1引言

差錯控制編碼的基本原理（續(xù)）當(dāng)x>>1有2PSK系統(tǒng)：2重重復(fù)碼：編碼增益=132.1引言差錯控制編碼的基本原理（續(xù)）142.1引言

差錯控制編碼的分類根據(jù)差錯控制編碼的功能不同檢錯碼、糾錯碼、糾刪碼（兼檢錯、糾錯）根據(jù)信息位和校驗(yàn)位的檢驗(yàn)關(guān)系線性碼（存在線性關(guān)系）和非線性碼按信息碼元在編碼后是否保持原來的形式系統(tǒng)碼：保持不變非系統(tǒng)碼：信息碼元改變了原有的信號形式按糾正錯誤的類型：糾正隨機(jī)錯誤的碼：用于隨機(jī)錯誤的信道糾正突發(fā)錯誤的碼：用于突發(fā)信道142.1引言差錯控制編碼的分類152.1引言

差錯控制編碼的分類（續(xù)）根據(jù)信息碼元和監(jiān)督碼元的約束方式：分組碼：監(jiān)督碼元僅與本碼組的信息碼元有關(guān)卷積碼：監(jiān)督碼元還與前面碼組的信息碼元有約束關(guān)系分組碼：將k個信息比特編成n個比特的碼字，共有2k個碼字。所有個碼字組成一個分組碼。傳輸時前后碼字之間毫無關(guān)系卷積碼：也是將k個信息比特編成n個比特的碼字，但是前后的N個碼字之間相互關(guān)聯(lián)編碼速率=平均每個碼字所攜帶的信息比特率

152.1引言差錯控制編碼的分類（續(xù)）162.1引言

編碼信道所謂的編碼信道就是將調(diào)制解調(diào)包括在信道內(nèi)的一種模型上的等效。即如果研究編碼和譯碼，完全可以將調(diào)制、解調(diào)與信道合起來等效成一個等效的信道，這種信道就稱之為編碼信道源編碼調(diào)制信道解調(diào)譯碼宿162.1引言編碼信道源編碼調(diào)制信道解調(diào)譯碼宿172.1引言

編碼信道（續(xù)）根據(jù)調(diào)制解調(diào)的不同輸入和輸出具有不同的類型離散無記憶對稱二進(jìn)制輸入二進(jìn)制輸出信道（BSC）這種情況相應(yīng)于2進(jìn)制調(diào)制解調(diào)+判決離散無記憶二進(jìn)制輸入多進(jìn)制輸出信道對應(yīng)于2進(jìn)制輸入，量化后輸出的情況，即所謂的軟譯碼離散無記憶多進(jìn)制輸入多進(jìn)制輸出對應(yīng)于多進(jìn)制輸入、量化后輸出離散無記憶二進(jìn)制輸入連續(xù)輸出對應(yīng)于二進(jìn)制輸入，模擬輸出（未判決、未量化）172.1引言編碼信道（續(xù)）182.1引言

香農(nóng)有擾離散信道的編碼定理對于一個給定的有擾信道，若信道的容量為C，只要發(fā)送端以低于C的速率R發(fā)送信息（R為編碼器的輸入二進(jìn)制碼元速率），則一定存在一種編碼方法，使編碼錯誤概率P隨著碼長n的增加，按指數(shù)下降到任意小的值，表示為其中E(R)稱為誤差指數(shù)結(jié)論：n和R一定情況下，為減小P，可增大C在C及R一定的情況下，增加n，可以使P指數(shù)下降。從實(shí)際的角度看，這時設(shè)備復(fù)雜性和譯碼延時也隨之增加

E（R）

C0C1C2R182.1引言香農(nóng)有擾離散信道的編碼定理

E（R）19

2.2糾錯編碼的基本原理主要內(nèi)容碼重、碼距最小碼距碼的糾錯、檢錯性能192.2糾錯編碼的基本原理主要內(nèi)容20

2.2糾錯編碼的基本原理分組碼將k個比特編成n個比特一組的碼字（碼組），記為（n，k）碼由于輸入有2k種組合，因此（n，k）碼應(yīng)該有2k個碼字碼重、碼距碼重：碼字中1的個數(shù)。如碼字11000的碼重為2碼距：碼字C1與碼字C2之間不同的比特數(shù)（又稱漢明距）202.2糾錯編碼的基本原理分組碼將k個比特編成n個21

2.2糾錯編碼的基本原理最小碼距所用碼字中任何兩個碼字之間的碼距的最小值，用dmin表示碼的糾錯、檢錯性能：由最小碼距決定為了檢測e個錯誤，要求最小碼距為了糾正t個錯誤，要求最小碼距為了糾正t個錯誤，同時檢測e個錯誤，要求最小碼距212.2糾錯編碼的基本原理最小碼距22糾錯碼的抗干擾能力完全取決于許用碼字之間的距離，碼的最小距離越大，說明碼字間的最小差別越大，抗干擾能力就越強(qiáng)

2.2糾錯編碼的基本原理22糾錯碼的抗干擾能力完全取決于許用碼字之間的距離，碼的最小23

2.3常用的簡單編碼

奇偶監(jiān)督碼（奇偶校驗(yàn)）設(shè)奇偶監(jiān)督碼的碼字表示為：則偶校驗(yàn)碼：（即偶數(shù)個1）奇校驗(yàn)碼：（即奇數(shù)個1）可見這種碼的最小碼距為2，只能檢1個錯232.3常用的簡單編碼奇偶監(jiān)督碼（奇偶校驗(yàn)）24

奇偶監(jiān)督碼的編碼可以用軟件實(shí)現(xiàn)，也可用硬件電路實(shí)現(xiàn)

如果碼組B無錯，B＝A，則M＝0；如果碼組B有單個（或奇數(shù)個）錯誤，則M＝1

2.3常用的簡單編碼

24奇偶監(jiān)督碼的編碼可以用軟件實(shí)現(xiàn)，也可用硬件電路實(shí)25

2.3常用的簡單編碼

二維奇偶監(jiān)督碼提高奇偶校驗(yàn)碼對突發(fā)錯誤的檢測能力將若干奇偶校驗(yàn)碼排成若干行，然后對每列進(jìn)行奇偶校驗(yàn)，放在最后一行。傳輸時按照列順序進(jìn)行傳輸，在接收端又按照行的順序檢驗(yàn)是否差錯由于突發(fā)錯誤是成串發(fā)生的，經(jīng)過傳輸后錯誤被分散（交織編碼+奇偶校驗(yàn)）移動通信中的信道衰落造成突發(fā)錯誤，因此傳輸前，先將輸入的信息比特交織，將突發(fā)錯誤盡可能分散成隨機(jī)錯誤，然后用其它編碼方式來糾正隨機(jī)的錯誤252.3常用的簡單編碼二維奇偶監(jiān)督碼26

2.3常用的簡單編碼

恒比碼每個碼組中的1的個數(shù)都一樣電傳機(jī)傳輸漢字時每個漢字用4位阿拉伯?dāng)?shù)字表示，每個阿拉伯?dāng)?shù)字用5個比特的碼字表示。由于阿拉伯?dāng)?shù)字只有10個，因此從32中可能的碼字中挑出=10個1的個數(shù)為3的碼字作為阿拉伯?dāng)?shù)字的編碼方式譯碼可以采用查表方法，檢錯時檢查1的個數(shù)是否為3一般用在電傳、電報阿拉伯?dāng)?shù)字編碼阿拉伯?dāng)?shù)字編碼101011610101211001711100310110801110411010910011500111001101262.3常用的簡單編碼恒比碼阿拉伯?dāng)?shù)字編碼阿拉伯27

2.3常用的簡單編碼

ISBN國際統(tǒng)一圖書編號國際圖書的發(fā)行中，用編碼的方式來防止書號在通信過程中發(fā)生錯誤如《通信原理》的書號是ISBN7-118-01429-X其中第一位數(shù)字“7”表示“中國”，“118”表示出版社，“01429”表示書名編號，最后一位“X”表示校驗(yàn)位（它是羅馬數(shù)字10的表示）所采用的校驗(yàn)方式如下所示：711801429X=10789171718222433437152441587698122155198198(模11)=0272.3常用的簡單編碼ISBN國際統(tǒng)一圖書編號282.4線性分組碼差錯編碼的重點(diǎn)：各種編碼和譯碼的方法主要內(nèi)容性質(zhì)基本原理校驗(yàn)矩陣（監(jiān)督矩陣）生成矩陣校正子（伴隨式）漢明碼282.4線性分組碼差錯編碼的重點(diǎn)：各種編碼和譯碼的方法292.4線性分組碼定義：將信息碼分組，為每組信息位附加若干監(jiān)督位，且信息位和監(jiān)督位間的關(guān)系可由線性方程組表示的編碼即可用線性方程組表述碼的規(guī)律性的分組碼線性分組碼（n，k）的性質(zhì)許用碼字（組）為2k個定義線性分組碼的加法為模2加，乘法為二進(jìn)制乘法。即有1+1=0、1+0=1、0+1=1、0+0=01x1=1,1x0=0,0x0=0,0x1=0且碼字與碼字的運(yùn)算是各相應(yīng)比特位上符合上述二進(jìn)制加法運(yùn)算規(guī)則292.4線性分組碼定義：302.4線性分組碼線性分組碼（n，k）的性質(zhì)（續(xù)）群：集合G上定義了一種加法運(yùn)算，如果該運(yùn)算符合以下4條公理，則稱G是該運(yùn)算的一個群封閉性：任何a、b屬于G，有a*b屬于G單位元：G中存在一個元素e滿足e*a=a有逆元：任何a屬于G，存在b屬于G滿足a*b=e結(jié)合率成立：a*(b*c)=(a*b)*c線性分組碼的性質(zhì)：封閉性。任意兩個許用碼組的和仍是一個許用碼組最小碼距等于非零碼的最小碼重302.4線性分組碼線性分組碼（n，k）的性質(zhì)（續(xù)）312.4線性分組碼基本原理(n,k)碼：碼長n，信息位數(shù)為k，則監(jiān)督位數(shù)r=n-k校正子（伴隨式）S：為了檢測傳輸過程中是否有錯，將接收到的碼組代入監(jiān)督方程式所得到的結(jié)果以（7，4）線性分組碼為例，說明（n，k）碼的基本原理7碼元a6a5a4a3a2a1a0，信息碼元a6a5a4a3，監(jiān)督碼元a2a1a0校正子S1S2S3與信息碼元及監(jiān)督碼元之間的關(guān)系為312.4線性分組碼基本原理322.4線性分組碼基本原理（續(xù)）3個校正子可以指示23-1=7種錯誤圖樣，如表所示可知，（7，4）碼可糾正一位錯誤在編碼時a2a1a0應(yīng)根據(jù)監(jiān)督方程確定：S1S2S3001010100011101110111000誤碼位置a0a1a2a3a4a5a6無誤322.4線性分組碼基本原理（續(xù)）S1S2S300101332.4線性分組碼基本原理（續(xù)）由此可得16個許用碼組信息位監(jiān)督位信息位監(jiān)督位a6a5a4a3a2a1a0a6a5a4a3a2a1a00000000100011100010111001100001010110100100011110101100101001101100001010110111010100110011111010001110001111111332.4線性分組碼基本原理（續(xù)）信息位監(jiān)督位信息位監(jiān)督342.4線性分組碼基本原理（續(xù)）接收端收到每個碼組后，計算出S1、S2和S3，如不全為0，則查表確定誤碼的位置，予以糾正如，接收碼組為0000011，可算得S1S2S3＝011，查表知a3錯（7，4）碼：dmin=3，能糾正1個誤碼或檢測2個誤碼(n,k)線性分組碼：r=n-k個監(jiān)督碼元，有r個校正子，可以指示2r-1個誤碼圖樣當(dāng)2r-1≥n（即2r≥k+r+1）時，就可糾正1位或1位以上的錯誤編碼效率（編碼速率）：k/n=(2r-r-1)/(2r-1)=1-r/n342.4線性分組碼基本原理（續(xù)）352.4線性分組碼校驗(yàn)矩陣（監(jiān)督矩陣）監(jiān)督碼元與信息碼元之間的關(guān)系可表示為監(jiān)督方程形式，上例（7，4）碼的監(jiān)督方程為簡記為HAT＝0T

或AHT＝0

352.4線性分組碼校驗(yàn)矩陣（監(jiān)督矩陣）362.4線性分組碼校驗(yàn)矩陣（監(jiān)督矩陣）（續(xù)）稱H為監(jiān)督矩陣設(shè)收到的碼組為B，則校正子S＝HBT故可根據(jù)H及誤碼圖樣表構(gòu)成差錯控制譯碼器典型形式監(jiān)督矩陣H＝[PIr]其中，P為r×k階矩陣，Ir為r×r階單位方陣各行線性無關(guān)非典型形式監(jiān)督矩陣可以經(jīng)過行運(yùn)算化為典型形式由典型形式監(jiān)督矩陣及信息碼元可算出各監(jiān)督碼元362.4線性分組碼校驗(yàn)矩陣（監(jiān)督矩陣）（續(xù)）372.4線性分組碼生成矩陣監(jiān)督碼元與信息碼元之間的關(guān)系還可表示為生成方程形式上述（7，4）碼的生成方程為稱G為生成矩陣，由生成矩陣G可構(gòu)造差錯控制編碼器372.4線性分組碼生成矩陣382.4線性分組碼生成矩陣（續(xù)）典型生成矩陣GG＝[IkQ]其中，Q＝PT為k×r階矩陣，Ik為k×k階單位方陣P＝QT由典型生成矩陣G可以得到系統(tǒng)碼各行線性無關(guān)非典型形式生成矩陣可以經(jīng)過行運(yùn)算化為典型形式382.4線性分組碼生成矩陣（續(xù)）392.4線性分組碼校正子（伴隨式）發(fā)送碼組A在傳輸過程中可能發(fā)生誤碼設(shè)接收到的碼組為B＝[bn-1bn-2

…b0]則錯誤圖樣E=B-A，或B=A+E其中，E=[en-1en-2

…e0]校正子為S=BHT=(A+E)HT=AHT+EHT=EHTS與E間有確定的關(guān)系392.4線性分組碼校正子（伴隨式）402.4線性分組碼漢明碼上述方法構(gòu)造的糾正單個錯誤的線性分組碼特點(diǎn)碼長：n＝2m－1信息碼位：k=2m-m-1監(jiān)督碼位：r=n-k=m最小碼距：d=3糾錯能力：t=1402.4線性分組碼漢明碼412.5循環(huán)碼概念、性質(zhì)和多項式表示生成多項式生成矩陣與監(jiān)督矩陣編碼器412.5循環(huán)碼概念、性質(zhì)和多項式表示422.5循環(huán)碼概念及性質(zhì)線性分組碼中最重要的一種子類，比較成熟特點(diǎn)代數(shù)結(jié)構(gòu)清晰：有嚴(yán)格的代數(shù)理論基礎(chǔ)性能較好：可糾隨機(jī)錯誤和突發(fā)錯誤編譯碼簡單：特殊的代數(shù)性質(zhì)有助于按照要求的糾錯能力構(gòu)造，并且簡化譯碼算法易于實(shí)現(xiàn)：很容易用帶反饋的移位寄存器實(shí)現(xiàn)目前的計算機(jī)糾錯系統(tǒng)中廣泛使用的線性分組碼422.5循環(huán)碼概念及性質(zhì)432.5循環(huán)碼概念及性質(zhì)（續(xù)）例：設(shè)（7，4）漢明碼C的校驗(yàn)矩陣和生成矩陣為得到16個碼組是：（1000101）（0001011）（0010110）（0101100）（1011000）（0110001）（1100010）（0100111）（1001110）（0011101）（0111010）（1110100）（1101001）（1010011）（1111111）（0000000）可以看到：如果Ci是C的碼組，則它的左右移位都是C的碼組，具有這種特性的線性分組碼稱為循環(huán)碼

432.5循環(huán)碼概念及性質(zhì)（續(xù)）442.5循環(huán)碼概念及性質(zhì)（續(xù)）循環(huán)碼的性質(zhì)：封閉性任何許用碼組的線性和還是許用碼組。由此性質(zhì)可以得到：線性碼都包含全零碼最小碼重就是最小碼距循環(huán)性任何許用的碼組循環(huán)移位后的碼組還是許用碼組

442.5循環(huán)碼概念及性質(zhì)（續(xù)）452.5循環(huán)碼概念及性質(zhì)（續(xù)）多項式表示：目的：用代數(shù)理論的方法研究循環(huán)碼的特性定義：碼的碼多項式如下其中，D為實(shí)變量、其冪次代表移位次數(shù)，GF（2）表示2元域，只有兩種元素0、1，且0、1滿足如下的運(yùn)算規(guī)則：0+0=0，0+1=1，1+0=1，1+1=0（加法）0x0=0，0x1=0，1x0=0，1x1=1。（乘法）

例如：（1011000）的碼多項式為452.5循環(huán)碼概念及性質(zhì)（續(xù)）46左移一位左移位若是長度為n的循環(huán)碼組，則在按模進(jìn)行運(yùn)算后，也是一個循環(huán)碼組，也就是用多項式除后所得之余式，即為所求的碼組2.5循環(huán)碼46左移一位若是長度為n的循環(huán)碼組，則472.5循環(huán)碼生成多項式循環(huán)碼完全由其碼長n和生成多項式g（D）構(gòu)成其中g(shù)（D）是一個能除盡Dn+1的r=n-k階多項式階數(shù)低于n并能被g（D）除盡的一組碼多項式就構(gòu)成一個（n，k）循環(huán)碼即階數(shù)小于或等于n-1且能被g（D）除盡的每個多項式都是循環(huán)碼的許用碼組

信息多項式為M(D),k位，(k-1)次多項式A(D)=M(D)g(D)472.5循環(huán)碼生成多項式482.5循環(huán)碼生成多項式（續(xù)）例如，（7，4）循環(huán)碼的生成多項式則階數(shù)低于n-1能被g（D）除盡的多項式為其中，i=0，1，2，3假設(shè)則對應(yīng)的循環(huán)碼多項式為故對應(yīng)的循環(huán)碼組為（1111111）482.5循環(huán)碼生成多項式（續(xù)）492.5循環(huán)碼生成多項式的構(gòu)造循環(huán)碼多項式表示及循環(huán)性質(zhì)循環(huán)碼中任何碼組的循環(huán)移位還是許用碼組，可以表示成碼多項式的形式定理一：碼組，經(jīng)過移位i位，得到碼組則可以證明：即證明：利用多項式的長除法：可以得證492.5循環(huán)碼生成多項式的構(gòu)造502.5循環(huán)碼生成多項式的構(gòu)造（續(xù)）循環(huán)碼多項式表示及循環(huán)性質(zhì)例：（7，4）循環(huán)碼（1000101）的碼多項式為移位1位后變成將它被除，得到因此，循環(huán)左移一位的余式為其相對應(yīng)的碼組為（0001011），正好是（1000101）循環(huán)左移一位的結(jié)果502.5循環(huán)碼生成多項式的構(gòu)造（續(xù)）512.5循環(huán)碼生成多項式的構(gòu)造（續(xù)）循環(huán)碼多項式的構(gòu)造定理二：（n，k）循環(huán)碼的生成多項式g(D)一定是Dn+1的因式，即反之，如果g(D)是一個n-k次多項式，且除盡Dn+1，則此g(D)一定生成一個（n，k）循環(huán)碼證明：循環(huán)碼的碼組T（D）是g（D）的倍式，因此而生成多項式g(D)本身也是一個碼組，該碼組的多項式次數(shù)為n-k次由定理一，可以知道也是循環(huán)碼組而所以，即g（D）是Dn+1的因式因式分解可以通過計算機(jī)分解的方式分解，也可以通過查表（已經(jīng)作好的因式分解表）得到512.5循環(huán)碼生成多項式的構(gòu)造（續(xù)）522.5循環(huán)碼生成多項式的構(gòu)造（續(xù)）循環(huán)碼多項式的構(gòu)造例，因此，（7，4）循環(huán)碼的生成多項式可以選擇或而（7，3）循環(huán)碼的生成多項式可以選擇或練習(xí)：請驗(yàn)證以下結(jié)論（7，6）循環(huán)碼的生成多項式為D+1，實(shí)際上就是簡單的偶校驗(yàn)碼（7，1）循環(huán)碼的生成多項式為，實(shí)際上是7重重復(fù)碼522.5循環(huán)碼生成多項式的構(gòu)造（續(xù)）532.5循環(huán)碼生成矩陣根據(jù)循環(huán)碼的碼組多項式是生成多項式g（D）的倍式根據(jù)線性碼的生成矩陣的特性，（n，k）碼的生成矩陣實(shí)際上可以由（n，k）碼中k個不相關(guān)的碼組構(gòu)成可以挑選出k個循環(huán)碼組的碼多項式形成非系統(tǒng)碼的生成矩陣系統(tǒng)碼的生成矩陣532.5循環(huán)碼生成矩陣542.5循環(huán)碼生成矩陣非系統(tǒng)碼的生成矩陣輸入信息碼元為時，相應(yīng)的循環(huán)碼組多項式為：由上式得到的碼組不是系統(tǒng)碼542.5循環(huán)碼生成矩陣552.5循環(huán)碼生成矩陣系統(tǒng)碼的生成矩陣系統(tǒng)碼定義：（n，k）系統(tǒng)碼的碼組中前k個比特是信息比特，后n-k個比特是監(jiān)督位問題：已知生成多項式g（D），如何構(gòu)造系統(tǒng)碼的生成矩陣？在系統(tǒng)碼中，碼組應(yīng)該具備如下的形式：同時有由上式可得其中，r（D）的次數(shù)小于等于n-k-1實(shí)際上上式表示了如何生成系統(tǒng)碼，即將信息碼多項式升n-k次，然后以g（D）為模，求出余式r（D）552.5循環(huán)碼生成矩陣562.5循環(huán)碼生成矩陣系統(tǒng)碼的生成矩陣?yán)阂阎?，4）系統(tǒng)循環(huán)碼的生成多項式為求生成矩陣解：系統(tǒng)碼的生成矩陣形式肯定是因此選擇信息多項式為、1

將D3提升n-k=3次，得到D6

，求D6除以g（D）的余式得到因此，系統(tǒng)生成矩陣為表示成矩陣形式，得到562.5循環(huán)碼生成矩陣572.5循環(huán)碼監(jiān)督矩陣由于g（D）能除盡Dn+1，即（1式）這里，稱為生成多項式

h(D)稱為監(jiān)督多項式由（1式）知道，572.5循環(huán)碼監(jiān)督矩陣582.5循環(huán)碼監(jiān)督矩陣（續(xù)）所以，如果生成矩陣是則監(jiān)督矩陣為：可以看到，上述兩者滿足582.5循環(huán)碼監(jiān)督矩陣（續(xù)）592.5循環(huán)碼監(jiān)督矩陣（續(xù)）例如，已知（7，3）碼的生成多項式為求生成矩陣和監(jiān)督矩陣解：監(jiān)督多項式為因此，監(jiān)督矩陣為可以驗(yàn)證592.5循環(huán)碼監(jiān)督矩陣（續(xù)）602.5循環(huán)碼編碼器系統(tǒng)循環(huán)碼的編碼器（除法器電路）最容易實(shí)現(xiàn)的方式是將信息碼多項式升n-k次冪后除以生成多項式，然后將所得余式置于升冪后的信息多項式后例1：已知（7，4）系統(tǒng)循環(huán)碼的生成多項式g（D）=

若信息碼為1001，求編碼后的循環(huán)碼解：信息碼多項式因此，編碼后的碼組為（1001011）602.5循環(huán)碼編碼器612.5循環(huán)碼編碼器系統(tǒng)循環(huán)碼的編碼器（除法器電路）多項式除法可以用帶反饋的線性移位寄存器來實(shí)現(xiàn)例2：已知信息碼為列出長除直式和除法電路的工作過程解：除法器的寄存器初始值為000000，輸入順序?yàn)?0110010011011，經(jīng)過6個時鐘后，在第6時刻，開始計算長除式中的第一次除法，輸出為商，寄存器中為余可以從長除式看到，再經(jīng)過8個時刻的計算可以得到該信息碼被g（D）除的余式，在第14時刻，寄存器中的內(nèi)容就是余式612.5循環(huán)碼編碼器622.5循環(huán)碼編碼器系統(tǒng)循環(huán)碼的編碼器（除法器電路）（續(xù)）故可通過該電路構(gòu)造系統(tǒng)循環(huán)碼的編碼器電路如下622.5循環(huán)碼編碼器632.5循環(huán)碼編碼器循環(huán)碼的譯碼用于糾錯目的的循環(huán)碼譯碼器原理：將接收到的碼組進(jìn)行除法運(yùn)算，如果除盡，則說明正確傳輸如果未除盡，則在寄存器中的內(nèi)容就是錯誤圖樣，根據(jù)錯誤圖樣可以確定一種邏輯，來確定差錯的位置譯碼算法比較復(fù)雜，可參見其他參考書用于檢錯目的、然后用ARQ方式的循環(huán)碼譯碼器原理：將接收到的碼組進(jìn)行除法運(yùn)算，如果除盡，則說明傳輸無誤如果未除盡，則表明傳輸出現(xiàn)差錯，要求發(fā)送端重發(fā)用于這種目的的循環(huán)碼經(jīng)常被稱為循環(huán)冗余校驗(yàn)碼，即CRC碼CRC碼的編碼、檢錯電路簡單且易于實(shí)現(xiàn)，因此得到廣泛的應(yīng)用632.5循環(huán)碼編碼器第十一章差錯控制編碼和線性分組碼第十一章差錯控制編碼和線性分組碼65主要內(nèi)容和重點(diǎn)差錯控制編碼的基本概念線性分組碼性質(zhì)、基本原理校正子監(jiān)督矩陣生成矩陣漢明碼循環(huán)碼概念及性質(zhì)生成多項式生成矩陣與監(jiān)督矩陣編碼器2主要內(nèi)容和重點(diǎn)差錯控制編碼的基本概念662.1引言

為什么要引入差錯控制編碼？什么是差錯控制編碼（信道編碼）？差錯控制編碼的3種方式信道發(fā)生差錯的模式差錯控制編碼的基本原理差錯控制編碼的分類編碼信道及香農(nóng)編碼定理32.1引言為什么要引入差錯控制編碼？672.1引言

為什么要引入差錯控制編碼？在實(shí)際信道上傳輸數(shù)字信號時，由于信道傳輸特性不理想及加性噪聲的影響，接收端所收到的數(shù)字信號不可避免地會發(fā)生錯誤為了在已知信噪比情況下達(dá)到一定的誤比特率指標(biāo)，應(yīng)該合理設(shè)計基帶信號，選擇調(diào)制解調(diào)方式，采用時域、頻域均衡，使誤比特率盡可能降低但若誤比特率仍不能滿足要求，則必須采用信道編碼（即差錯控制編碼），將誤比特率進(jìn)一步降低42.1引言為什么要引入差錯控制編碼？682.1引言

什么是差錯控制編碼差錯控制編碼的基本思路：在發(fā)送端將被傳輸?shù)男畔⒏缴弦恍┍O(jiān)督碼元，這些多余的碼元與信息碼元之間以某種確定的規(guī)則相互關(guān)聯(lián)（約束）接收端按照既定的規(guī)則校驗(yàn)信息碼元與監(jiān)督碼元之間的關(guān)系，一旦傳輸發(fā)生差錯，則信息碼元與監(jiān)督碼元的關(guān)系就受到破壞，從而接收端可以發(fā)現(xiàn)錯誤乃至糾正錯誤差錯控制編碼所要解決的問題：各種編碼和譯碼方法52.1引言什么是差錯控制編碼692.1引言

差錯控制的三種方式檢錯重發(fā)（ARQ）在接收端根據(jù)編碼規(guī)則進(jìn)行檢查，如果發(fā)現(xiàn)規(guī)則被破壞，則通過反向信道要求發(fā)送端重新發(fā)送，直到接收端檢查無誤為止ARQ系統(tǒng)的重發(fā)機(jī)制：停發(fā)等候重發(fā)、返回重發(fā)和選擇重發(fā)需要反饋信道，效率較低，但是性能很好發(fā)收能夠發(fā)現(xiàn)錯誤的碼應(yīng)答信息62.1引言差錯控制的三種方式發(fā)收能夠發(fā)現(xiàn)錯誤的碼應(yīng)答702.1引言

差錯控制的三種方式（續(xù)）前向糾錯（FEC）發(fā)送端發(fā)送能糾正錯誤的編碼，在接收端根據(jù)接收到的碼和編碼規(guī)則，能自動糾正傳輸中的錯誤不需要反饋信道，實(shí)時性好，但是隨著糾錯能力的提高，編譯碼設(shè)備復(fù)雜

發(fā)收可以糾正錯誤的碼72.1引言差錯控制的三種方式（續(xù)）發(fā)收可以糾正錯誤的712.1引言

差錯控制的三種方式（續(xù)）混合方式結(jié)合FEC和ARQ：在糾錯能力范圍內(nèi)，自動糾正錯誤，超出糾錯范圍則要求發(fā)送端重新發(fā)送發(fā)收可以發(fā)現(xiàn)和糾正錯誤的碼應(yīng)答信號82.1引言差錯控制的三種方式（續(xù)）發(fā)收可以發(fā)現(xiàn)和糾正722.1引言

信道發(fā)生差錯的模式隨機(jī)差錯：差錯的出現(xiàn)是隨機(jī)的，差錯出現(xiàn)的位置是隨機(jī)分布的一般由信道的加性隨機(jī)噪聲引起這種信道稱為隨機(jī)信道

突發(fā)差錯：差錯的出現(xiàn)是一連串出現(xiàn)的。這種情況如移動通信中信號在某一段時間內(nèi)發(fā)生衰落，造成一串差錯；光盤上的一條劃痕等等這樣的信道稱之為突發(fā)信道

混合差錯：既有突發(fā)錯誤又有隨機(jī)差錯的情況這種信道稱之為混合信道

92.1引言信道發(fā)生差錯的模式732.1引言

差錯控制編碼的基本原理以差錯重發(fā)編碼來闡述差錯編碼在相同的信噪比情況下為什么會獲得更好的系統(tǒng)性能？例1：假設(shè)發(fā)送的信息0、1等概，采用2PSK方式，則最佳接收的系統(tǒng)誤比特率為，現(xiàn)假設(shè)如果將信息0編碼成00，信息1編碼成11，則在接收端：如果發(fā)送00，收到01、10，知道發(fā)生了差錯，要求發(fā)送端重新傳輸，直到傳送正確為止只有當(dāng)收到11時，我們才錯誤地認(rèn)為當(dāng)前發(fā)送的是1因此在這種情況下發(fā)生譯碼錯誤的概率是同理，如果發(fā)送的是11，只有收到00時才可能發(fā)生錯誤譯碼，因此在這種情況下發(fā)生譯碼錯誤的概率是故采用00、11編碼的系統(tǒng)誤比特率為102.1引言差錯控制編碼的基本原理742.1引言

差錯控制編碼的基本原理（續(xù)）依此類推，可知：采用000、111編碼的ARQ系統(tǒng)誤比特率是多少？采用0000、1111編碼的ARQ系統(tǒng)誤比特率是多少？例2，如例1，如果0、1采用00000、11111編碼，在接收端用如下的譯碼方法，每收到5個比特譯碼一次，采用大數(shù)判決，即5個比特中0的個數(shù)大于1的個數(shù)則譯碼成0，反之譯碼成1；不采用ARQ方式。那么，這種編碼方式就變成了糾錯編碼由于傳輸錯誤當(dāng)接收端收到11000，10100，10010，10001，01100，01010，01001，00110，00101，00011中的任何一種時，都可以自動糾正成00000課外題：請計算在這種情況下的系統(tǒng)性能上述例1、例2的編碼方式叫重復(fù)碼112.1引言差錯控制編碼的基本原理（續(xù)）752.1引言

差錯控制編碼的基本原理（續(xù)）例3，2PSK系統(tǒng)中誤比特率與Es/N0有關(guān)我們看到，重復(fù)碼中假設(shè)傳輸時每個符號的Es/N0相等，因此才得到以上的性能分析對比但是如果我們以Eb/N0的指標(biāo)進(jìn)行比較，則我們看到例1的例2的如果要求各系統(tǒng)在Eb/N0相同的情況下進(jìn)行比較（n重復(fù)碼中用了n倍能量來傳輸一個比特，從每個比特能量的角度來看），則可看到這2種系統(tǒng)性能相近（即獲得相近的編碼增益）122.1引言差錯控制編碼的基本原理（續(xù)）762.1引言

差錯控制編碼的基本原理（續(xù)）當(dāng)x>>1有2PSK系統(tǒng)：2重重復(fù)碼：編碼增益=132.1引言差錯控制編碼的基本原理（續(xù)）772.1引言

差錯控制編碼的分類根據(jù)差錯控制編碼的功能不同檢錯碼、糾錯碼、糾刪碼（兼檢錯、糾錯）根據(jù)信息位和校驗(yàn)位的檢驗(yàn)關(guān)系線性碼（存在線性關(guān)系）和非線性碼按信息碼元在編碼后是否保持原來的形式系統(tǒng)碼：保持不變非系統(tǒng)碼：信息碼元改變了原有的信號形式按糾正錯誤的類型：糾正隨機(jī)錯誤的碼：用于隨機(jī)錯誤的信道糾正突發(fā)錯誤的碼：用于突發(fā)信道142.1引言差錯控制編碼的分類782.1引言

差錯控制編碼的分類（續(xù)）根據(jù)信息碼元和監(jiān)督碼元的約束方式：分組碼：監(jiān)督碼元僅與本碼組的信息碼元有關(guān)卷積碼：監(jiān)督碼元還與前面碼組的信息碼元有約束關(guān)系分組碼：將k個信息比特編成n個比特的碼字，共有2k個碼字。所有個碼字組成一個分組碼。傳輸時前后碼字之間毫無關(guān)系卷積碼：也是將k個信息比特編成n個比特的碼字，但是前后的N個碼字之間相互關(guān)聯(lián)編碼速率=平均每個碼字所攜帶的信息比特率

152.1引言差錯控制編碼的分類（續(xù)）792.1引言

編碼信道所謂的編碼信道就是將調(diào)制解調(diào)包括在信道內(nèi)的一種模型上的等效。即如果研究編碼和譯碼，完全可以將調(diào)制、解調(diào)與信道合起來等效成一個等效的信道，這種信道就稱之為編碼信道源編碼調(diào)制信道解調(diào)譯碼宿162.1引言編碼信道源編碼調(diào)制信道解調(diào)譯碼宿802.1引言

編碼信道（續(xù)）根據(jù)調(diào)制解調(diào)的不同輸入和輸出具有不同的類型離散無記憶對稱二進(jìn)制輸入二進(jìn)制輸出信道（BSC）這種情況相應(yīng)于2進(jìn)制調(diào)制解調(diào)+判決離散無記憶二進(jìn)制輸入多進(jìn)制輸出信道對應(yīng)于2進(jìn)制輸入，量化后輸出的情況，即所謂的軟譯碼離散無記憶多進(jìn)制輸入多進(jìn)制輸出對應(yīng)于多進(jìn)制輸入、量化后輸出離散無記憶二進(jìn)制輸入連續(xù)輸出對應(yīng)于二進(jìn)制輸入，模擬輸出（未判決、未量化）172.1引言編碼信道（續(xù)）812.1引言

香農(nóng)有擾離散信道的編碼定理對于一個給定的有擾信道，若信道的容量為C，只要發(fā)送端以低于C的速率R發(fā)送信息（R為編碼器的輸入二進(jìn)制碼元速率），則一定存在一種編碼方法，使編碼錯誤概率P隨著碼長n的增加，按指數(shù)下降到任意小的值，表示為其中E(R)稱為誤差指數(shù)結(jié)論：n和R一定情況下，為減小P，可增大C在C及R一定的情況下，增加n，可以使P指數(shù)下降。從實(shí)際的角度看，這時設(shè)備復(fù)雜性和譯碼延時也隨之增加

E（R）

C0C1C2R182.1引言香農(nóng)有擾離散信道的編碼定理

E（R）82

2.2糾錯編碼的基本原理主要內(nèi)容碼重、碼距最小碼距碼的糾錯、檢錯性能192.2糾錯編碼的基本原理主要內(nèi)容83

2.2糾錯編碼的基本原理分組碼將k個比特編成n個比特一組的碼字（碼組），記為（n，k）碼由于輸入有2k種組合，因此（n，k）碼應(yīng)該有2k個碼字碼重、碼距碼重：碼字中1的個數(shù)。如碼字11000的碼重為2碼距：碼字C1與碼字C2之間不同的比特數(shù)（又稱漢明距）202.2糾錯編碼的基本原理分組碼將k個比特編成n個84

2.2糾錯編碼的基本原理最小碼距所用碼字中任何兩個碼字之間的碼距的最小值，用dmin表示碼的糾錯、檢錯性能：由最小碼距決定為了檢測e個錯誤，要求最小碼距為了糾正t個錯誤，要求最小碼距為了糾正t個錯誤，同時檢測e個錯誤，要求最小碼距212.2糾錯編碼的基本原理最小碼距85糾錯碼的抗干擾能力完全取決于許用碼字之間的距離，碼的最小距離越大，說明碼字間的最小差別越大，抗干擾能力就越強(qiáng)

2.2糾錯編碼的基本原理22糾錯碼的抗干擾能力完全取決于許用碼字之間的距離，碼的最小86

2.3常用的簡單編碼

奇偶監(jiān)督碼（奇偶校驗(yàn)）設(shè)奇偶監(jiān)督碼的碼字表示為：則偶校驗(yàn)碼：（即偶數(shù)個1）奇校驗(yàn)碼：（即奇數(shù)個1）可見這種碼的最小碼距為2，只能檢1個錯232.3常用的簡單編碼奇偶監(jiān)督碼（奇偶校驗(yàn)）87

奇偶監(jiān)督碼的編碼可以用軟件實(shí)現(xiàn)，也可用硬件電路實(shí)現(xiàn)

如果碼組B無錯，B＝A，則M＝0；如果碼組B有單個（或奇數(shù)個）錯誤，則M＝1

2.3常用的簡單編碼

24奇偶監(jiān)督碼的編碼可以用軟件實(shí)現(xiàn)，也可用硬件電路實(shí)88

2.3常用的簡單編碼

二維奇偶監(jiān)督碼提高奇偶校驗(yàn)碼對突發(fā)錯誤的檢測能力將若干奇偶校驗(yàn)碼排成若干行，然后對每列進(jìn)行奇偶校驗(yàn)，放在最后一行。傳輸時按照列順序進(jìn)行傳輸，在接收端又按照行的順序檢驗(yàn)是否差錯由于突發(fā)錯誤是成串發(fā)生的，經(jīng)過傳輸后錯誤被分散（交織編碼+奇偶校驗(yàn)）移動通信中的信道衰落造成突發(fā)錯誤，因此傳輸前，先將輸入的信息比特交織，將突發(fā)錯誤盡可能分散成隨機(jī)錯誤，然后用其它編碼方式來糾正隨機(jī)的錯誤252.3常用的簡單編碼二維奇偶監(jiān)督碼89

2.3常用的簡單編碼

恒比碼每個碼組中的1的個數(shù)都一樣電傳機(jī)傳輸漢字時每個漢字用4位阿拉伯?dāng)?shù)字表示，每個阿拉伯?dāng)?shù)字用5個比特的碼字表示。由于阿拉伯?dāng)?shù)字只有10個，因此從32中可能的碼字中挑出=10個1的個數(shù)為3的碼字作為阿拉伯?dāng)?shù)字的編碼方式譯碼可以采用查表方法，檢錯時檢查1的個數(shù)是否為3一般用在電傳、電報阿拉伯?dāng)?shù)字編碼阿拉伯?dāng)?shù)字編碼101011610101211001711100310110801110411010910011500111001101262.3常用的簡單編碼恒比碼阿拉伯?dāng)?shù)字編碼阿拉伯90

2.3常用的簡單編碼

ISBN國際統(tǒng)一圖書編號國際圖書的發(fā)行中，用編碼的方式來防止書號在通信過程中發(fā)生錯誤如《通信原理》的書號是ISBN7-118-01429-X其中第一位數(shù)字“7”表示“中國”，“118”表示出版社，“01429”表示書名編號，最后一位“X”表示校驗(yàn)位（它是羅馬數(shù)字10的表示）所采用的校驗(yàn)方式如下所示：711801429X=10789171718222433437152441587698122155198198(模11)=0272.3常用的簡單編碼ISBN國際統(tǒng)一圖書編號912.4線性分組碼差錯編碼的重點(diǎn)：各種編碼和譯碼的方法主要內(nèi)容性質(zhì)基本原理校驗(yàn)矩陣（監(jiān)督矩陣）生成矩陣校正子（伴隨式）漢明碼282.4線性分組碼差錯編碼的重點(diǎn)：各種編碼和譯碼的方法922.4線性分組碼定義：將信息碼分組，為每組信息位附加若干監(jiān)督位，且信息位和監(jiān)督位間的關(guān)系可由線性方程組表示的編碼即可用線性方程組表述碼的規(guī)律性的分組碼線性分組碼（n，k）的性質(zhì)許用碼字（組）為2k個定義線性分組碼的加法為模2加，乘法為二進(jìn)制乘法。即有1+1=0、1+0=1、0+1=1、0+0=01x1=1,1x0=0,0x0=0,0x1=0且碼字與碼字的運(yùn)算是各相應(yīng)比特位上符合上述二進(jìn)制加法運(yùn)算規(guī)則292.4線性分組碼定義：932.4線性分組碼線性分組碼（n，k）的性質(zhì)（續(xù)）群：集合G上定義了一種加法運(yùn)算，如果該運(yùn)算符合以下4條公理，則稱G是該運(yùn)算的一個群封閉性：任何a、b屬于G，有a*b屬于G單位元：G中存在一個元素e滿足e*a=a有逆元：任何a屬于G，存在b屬于G滿足a*b=e結(jié)合率成立：a*(b*c)=(a*b)*c線性分組碼的性質(zhì)：封閉性。任意兩個許用碼組的和仍是一個許用碼組最小碼距等于非零碼的最小碼重302.4線性分組碼線性分組碼（n，k）的性質(zhì)（續(xù)）942.4線性分組碼基本原理(n,k)碼：碼長n，信息位數(shù)為k，則監(jiān)督位數(shù)r=n-k校正子（伴隨式）S：為了檢測傳輸過程中是否有錯，將接收到的碼組代入監(jiān)督方程式所得到的結(jié)果以（7，4）線性分組碼為例，說明（n，k）碼的基本原理7碼元a6a5a4a3a2a1a0，信息碼元a6a5a4a3，監(jiān)督碼元a2a1a0校正子S1S2S3與信息碼元及監(jiān)督碼元之間的關(guān)系為312.4線性分組碼基本原理952.4線性分組碼基本原理（續(xù)）3個校正子可以指示23-1=7種錯誤圖樣，如表所示可知，（7，4）碼可糾正一位錯誤在編碼時a2a1a0應(yīng)根據(jù)監(jiān)督方程確定：S1S2S3001010100011101110111000誤碼位置a0a1a2a3a4a5a6無誤322.4線性分組碼基本原理（續(xù)）S1S2S300101962.4線性分組碼基本原理（續(xù)）由此可得16個許用碼組信息位監(jiān)督位信息位監(jiān)督位a6a5a4a3a2a1a0a6a5a4a3a2a1a00000000100011100010111001100001010110100100011110101100101001101100001010110111010100110011111010001110001111111332.4線性分組碼基本原理（續(xù)）信息位監(jiān)督位信息位監(jiān)督972.4線性分組碼基本原理（續(xù)）接收端收到每個碼組后，計算出S1、S2和S3，如不全為0，則查表確定誤碼的位置，予以糾正如，接收碼組為0000011，可算得S1S2S3＝011，查表知a3錯（7，4）碼：dmin=3，能糾正1個誤碼或檢測2個誤碼(n,k)線性分組碼：r=n-k個監(jiān)督碼元，有r個校正子，可以指示2r-1個誤碼圖樣當(dāng)2r-1≥n（即2r≥k+r+1）時，就可糾正1位或1位以上的錯誤編碼效率（編碼速率）：k/n=(2r-r-1)/(2r-1)=1-r/n342.4線性分組碼基本原理（續(xù)）982.4線性分組碼校驗(yàn)矩陣（監(jiān)督矩陣）監(jiān)督碼元與信息碼元之間的關(guān)系可表示為監(jiān)督方程形式，上例（7，4）碼的監(jiān)督方程為簡記為HAT＝0T

或AHT＝0

352.4線性分組碼校驗(yàn)矩陣（監(jiān)督矩陣）992.4線性分組碼校驗(yàn)矩陣（監(jiān)督矩陣）（續(xù)）稱H為監(jiān)督矩陣設(shè)收到的碼組為B，則校正子S＝HBT故可根據(jù)H及誤碼圖樣表構(gòu)成差錯控制譯碼器典型形式監(jiān)督矩陣H＝[PIr]其中，P為r×k階矩陣，Ir為r×r階單位方陣各行線性無關(guān)非典型形式監(jiān)督矩陣可以經(jīng)過行運(yùn)算化為典型形式由典型形式監(jiān)督矩陣及信息碼元可算出各監(jiān)督碼元362.4線性分組碼校驗(yàn)矩陣（監(jiān)督矩陣）（續(xù)）1002.4線性分組碼生成矩陣監(jiān)督碼元與信息碼元之間的關(guān)系還可表示為生成方程形式上述（7，4）碼的生成方程為稱G為生成矩陣，由生成矩陣G可構(gòu)造差錯控制編碼器372.4線性分組碼生成矩陣1012.4線性分組碼生成矩陣（續(xù)）典型生成矩陣GG＝[IkQ]其中，Q＝PT為k×r階矩陣，Ik為k×k階單位方陣P＝QT由典型生成矩陣G可以得到系統(tǒng)碼各行線性無關(guān)非典型形式生成矩陣可以經(jīng)過行運(yùn)算化為典型形式382.4線性分組碼生成矩陣（續(xù)）1022.4線性分組碼校正子（伴隨式）發(fā)送碼組A在傳輸過程中可能發(fā)生誤碼設(shè)接收到的碼組為B＝[bn-1bn-2

…b0]則錯誤圖樣E=B-A，或B=A+E其中，E=[en-1en-2

…e0]校正子為S=BHT=(A+E)HT=AHT+EHT=EHTS與E間有確定的關(guān)系392.4線性分組碼校正子（伴隨式）1032.4線性分組碼漢明碼上述方法構(gòu)造的糾正單個錯誤的線性分組碼特點(diǎn)碼長：n＝2m－1信息碼位：k=2m-m-1監(jiān)督碼位：r=n-k=m最小碼距：d=3糾錯能力：t=1402.4線性分組碼漢明碼1042.5循環(huán)碼概念、性質(zhì)和多項式表示生成多項式生成矩陣與監(jiān)督矩陣編碼器412.5循環(huán)碼概念、性質(zhì)和多項式表示1052.5循環(huán)碼概念及性質(zhì)線性分組碼中最重要的一種子類，比較成熟特點(diǎn)代數(shù)結(jié)構(gòu)清晰：有嚴(yán)格的代數(shù)理論基礎(chǔ)性能較好：可糾隨機(jī)錯誤和突發(fā)錯誤編譯碼簡單：特殊的代數(shù)性質(zhì)有助于按照要求的糾錯能力構(gòu)造，并且簡化譯碼算法易于實(shí)現(xiàn)：很容易用帶反饋的移位寄存器實(shí)現(xiàn)目前的計算機(jī)糾錯系統(tǒng)中廣泛使用的線性分組碼422.5循環(huán)碼概念及性質(zhì)1062.5循環(huán)碼概念及性質(zhì)（續(xù)）例：設(shè)（7，4）漢明碼C的校驗(yàn)矩陣和生成矩陣為得到16個碼組是：（1000101）（0001011）（0010110）（0101100）（1011000）（0110001）（1100010）（0100111）（1001110）（0011101）（0111010）（1110100）（1101001）（1010011）（1111111）（0000000）可以看到：如果Ci是C的碼組，則它的左右移位都是C的碼組，具有這種特性的線性分組碼稱為循環(huán)碼

432.5循環(huán)碼概念及性質(zhì)（續(xù)）1072.5循環(huán)碼概念及性質(zhì)（續(xù)）循環(huán)碼的性質(zhì)：封閉性任何許用碼組的線性和還是許用碼組。由此性質(zhì)可以得到：線性碼都包含全零碼最小碼重就是最小碼距循環(huán)性任何許用的碼組循環(huán)移位后的碼組還是許用碼組

442.5循環(huán)碼概念及性質(zhì)（續(xù)）1082.5循環(huán)碼概念及性質(zhì)（續(xù)）多項式表示：目的：用代數(shù)理論的方法研究循環(huán)碼的特性定義：碼的碼多項式如下其中，D為實(shí)變量、其冪次代表移位次數(shù)，GF（2）表示2元域，只有兩種元素0、1，且0、1滿足如下的運(yùn)算規(guī)則：0+0=0，0+1=1，1+0=1，1+1=0（加法）0x0=0，0x1=0，1x0=0，1x1=1。（乘法）

例如：（1011000）的碼多項式為452.5循環(huán)碼概念及性質(zhì)（續(xù)）109左移一位左移位若是長度為n的循環(huán)碼組，則在按模進(jìn)行運(yùn)算后，也是一個循環(huán)碼組，也就是用多項式除后所得之余式，即為所求的碼組2.5循環(huán)碼46左移一位若是長度為n的循環(huán)碼組，則1102.5循環(huán)碼生成多項式循環(huán)碼完全由其碼長n和生成多項式g（D）構(gòu)成其中g(shù)（D）是一個能除盡Dn+1的r=n-k階多項式階數(shù)低于n并能被g（D）除盡的一組碼多項式就構(gòu)成一個（n，k）循環(huán)碼即階數(shù)小于或等于n-1且能被g（D）除盡的每個多項式都是循環(huán)碼的許用碼組

信息多項式為M(D),k位，(k-1)次多項式A(D)=M(D)g(D)472.5循環(huán)碼生成多項式1112.5循環(huán)碼生成多項式（續(xù)）例如，（7，4）循環(huán)碼的生成多項式則階數(shù)低于n-1能被g（D）除盡的多項式為其中，i=0，1，2，3假設(shè)則對應(yīng)的循環(huán)碼多項式為故對應(yīng)的循環(huán)碼組為（1111111）482.5循環(huán)碼生成多項式（續(xù)）1122.5循環(huán)碼生成多項式的構(gòu)造循環(huán)碼多項式表示及循環(huán)性質(zhì)循環(huán)碼中任何碼組的循環(huán)移位還是許用碼組，可以表示成碼多項式的形式定理一：碼組，經(jīng)過移位i位，得到碼組則可以證明：即證明：利用多項式的長除法：可以得證492.5循環(huán)碼生成多項式的構(gòu)造1132.5循環(huán)碼生成多項式的構(gòu)造（續(xù)）循環(huán)碼多項式表示及循環(huán)性質(zhì)例：（7，4）循環(huán)碼（1000101）的碼多項式為移位1位后變成將它被除，得到因此，循環(huán)左移一位的余式為其相對應(yīng)的碼組為（0001011），正好是（1000101）循環(huán)左移一位的結(jié)果502.5循環(huán)碼生成多項式的構(gòu)造（續(xù)）1142.5循環(huán)碼生成多項式的構(gòu)造（續(xù)）循環(huán)碼多項式的構(gòu)造定理二：（n，k）循環(huán)碼的生成多項式g(D)一定是Dn+1的因式，即反之，如果g(D)是一個n-k次多項式，且除盡Dn+1，則此g(D)一定生成