差錯控制編碼課件

1、11.1 概述11.2 糾錯編碼的基本原理11.3 糾錯編碼的性能11.4 常用的簡單編碼11.5 線性分組碼11.11 小結(jié)第11章 差錯控制編碼一、信道分類1、隨機信道：錯碼是隨機的，相互之間統(tǒng)計獨立的，如正態(tài)分布白噪聲引起的；2、突發(fā)信道：錯碼是成串集中出現(xiàn)的。如脈沖干擾和信道衰落現(xiàn)象引起的；3、混合信道：11.1 概 述1、檢錯重發(fā)法：需要雙向信道。2、前向糾錯法：不需要反向信道，但糾錯設(shè)備要復(fù)雜一些。3、反饋校驗法：需雙向信道，傳輸效率低。4、檢錯刪除法11.1 概 述二、差錯控制方法三、差錯控制編碼在信息碼元中加入監(jiān)督碼元就稱差錯控制編碼，也稱糾錯編碼。監(jiān)督碼元：在發(fā)送端需要在信息

2、碼元序列中增加一些差錯控制碼元，它們稱為監(jiān)督碼元。不同的編碼方法，有不同的檢錯或糾錯能力。11.1 概 述多余度：就是指增加的監(jiān)督碼元多少。編碼效率(簡稱碼率) ：設(shè)信息碼元數(shù)量為k，則比值k/n 就是碼率。冗余度：監(jiān)督碼元數(shù)(n-k) 和信息碼元數(shù) k 之比。理論上，差錯控制以降低信息傳輸速率為代價換取提高傳輸可靠性。11.1 概 述1、簡述:3種ARQ系統(tǒng)(1)停止等待ARQ系統(tǒng) 四、自動要求重發(fā)系統(tǒng)接收碼組ACKACKNAKACKACKNAKACKt1233455發(fā)送碼組12334556t有錯碼組有錯碼組11.1 概 述(2)拉后ARQ系統(tǒng)接收數(shù)據(jù)有錯碼組有錯碼組910111011122

3CK1NAK5NAK9ACK5發(fā)送數(shù)據(jù)57695214367981011101112重發(fā)碼組重發(fā)碼組11.1 概 述2、ARQ的主要優(yōu)點：（1）監(jiān)督碼元較少即能使誤碼率降到很低，即碼率較高；（2）檢錯的計算復(fù)雜度較低；(3)選擇重發(fā)ARQ系統(tǒng)接收數(shù)據(jù)有錯碼組有錯碼組921436575981011131412發(fā)送數(shù)據(jù)995852143671011131412重發(fā)碼組重發(fā)碼組NAK9ACK1NAK5ACK5ACK911.1 概 述（3）檢錯用的編碼方法和加性干擾的統(tǒng)計特性基本無關(guān)，能適應(yīng)不同特性的信道。3、ARQ的主要缺點：（1）需要雙向信道來重發(fā)，不能用于單向信道，也不能

4、用于一點到多點的通信系統(tǒng)。（2）因為重發(fā)而使ARQ系統(tǒng)的傳輸效率降低。11.1 概 述11.1 概 述（3）在信道干擾嚴(yán)重時，可能發(fā)生因不斷反復(fù)重發(fā)而造成事實上的通信中斷。（4）在要求實時通信的場合，例如電話通信，往往不允許使用ARQ法4、ARQ系統(tǒng)的原理方框圖11.1 概 述（1）發(fā)送端，輸入的信息碼元在編碼器中被分組編碼（加入監(jiān)督碼元）后，除了立即發(fā)送外，還暫存于緩沖存儲器中。11.1 概 述（2）接收端僅當(dāng)解碼器認(rèn)為接收信息碼元正確時，才將信息碼元送給收信者。（3）當(dāng)解碼器未發(fā)現(xiàn)錯碼時，經(jīng)過反向信道發(fā)出不需重發(fā)指令。發(fā)送端收到此指令后，即繼續(xù)發(fā)送后一碼組，發(fā)送端的緩沖存儲器中的內(nèi)容也隨之

5、更新一、糾（檢）錯舉例1、三位二進制碼有8種不同的組合，可以表示8種不同的天氣，無法發(fā)現(xiàn)錯誤。此時編碼效率為100。2、若只用其中四種來傳送信息（4種天氣），接收端就有可能發(fā)現(xiàn)一個錯碼，但如果錯兩位，11.2糾錯編碼的基本原理就是許用碼組，不能發(fā)現(xiàn)錯誤。且這種碼只能發(fā)現(xiàn)錯誤（檢錯），不能糾錯。此時編碼效率2/3。3、若只用2種來傳送信息，000和111，就可以檢2個錯，糾一個錯。此時編碼效率為1/3。11.2糾錯編碼的基本原理二、分組碼的一般概念1、分組碼的表示信息位監(jiān)督位晴云陰雨000110110110這種信息碼分組，為每組信息碼附加若干監(jiān)督碼的編碼集合，稱為分組碼。且監(jiān)督位僅監(jiān)督本碼組中的

6、碼元。11.2糾錯編碼的基本原理2、分組碼的一般結(jié)構(gòu)分組碼一般用（n,k）表示，k是二進制信息碼的數(shù)目，n是編碼組的總位數(shù)，稱為碼長，n-k=r是監(jiān)督碼位數(shù)。11.2糾錯編碼的基本原理最小碼距：某種編碼中各個碼組間距離最小值稱為最小碼距d0。與糾、檢錯能力有關(guān)。碼組重量：把“1”的數(shù)目稱為碼組重量；碼組距離：把兩個碼組中對應(yīng)位上數(shù)字不同的位數(shù)稱為碼距，又稱“Hamming”距離。3、一般概念11.2糾錯編碼的基本原理每個碼組的3個碼元值(a1, a2, a3)就是此立方體各頂點的坐標(biāo)。而上述碼距概念在此圖中就對應(yīng)于各頂點之間沿立方體各邊行走的幾何距離。11.2糾錯編碼的基本原理(0,0,0)(

7、0,0,1)(1,0,1)(1,0,0)(1,1,0)(0,1,0)(0,1,1)(1,1,1)a2a0a14、最小碼距d0與糾、檢錯能力的關(guān)系（1）為檢測e個錯碼，要求最小碼距d0e+10123BA漢明距離ed011.2糾錯編碼的基本原理(2)為了糾正t個錯碼，要求最小碼距d0 2t + 1BtA漢明距離012345td0(3)為糾正t個錯碼，同時檢測e個錯碼， d0 e+t + 1（et)11.2糾錯編碼的基本原理BtA漢明距離012345td011.2糾錯編碼的基本原理圖中碼組A和B之間距離為5。當(dāng)錯碼位數(shù)超過糾錯能力時，該碼組立即進入另一碼組的圓內(nèi)而被錯誤地“糾正”了。所以，發(fā)生e個錯

8、誤之后所處的位置，與其他碼組（譬如碼組B）的糾錯圓圈至少距離等于1，要求最小碼距ABe1tt漢明距離這種糾錯和檢錯結(jié)合的工作方式簡稱糾檢結(jié)合。11.2糾錯編碼的基本原理11.3 糾錯編碼的性能一、系統(tǒng)帶寬和信噪比的矛盾：為了減少接收錯誤碼元數(shù)量，需要在發(fā)送信息碼元序列中加入監(jiān)督碼元。這樣作的結(jié)果增大了系統(tǒng)帶寬。系統(tǒng)帶寬的增大將引起系統(tǒng)中噪聲功率增大，使信噪比下降。一般說來，采用糾錯編碼后，誤碼率總是能夠得到很大改善的。10-610-510-410-310-210-1編碼后PeCDEAB信噪比 (dB)11.3 糾錯編碼的性能二、編碼性能舉例圖中A點，在采用糾錯編碼后，誤碼率降至約410-5，圖

9、中B點。這樣，不增大發(fā)送功率就能降低誤碼率約一個半數(shù)量級11.3 糾錯編碼的性能若保持誤碼率在10-5，圖中C點，約需要信噪比Eb/n0=10.5 dB。在采用這種編碼時，約需要信噪比7.5 dB，圖中D點。可以節(jié)省功率2dB。通常稱這2dB為編碼增益。傳輸速率和Eb/n0的關(guān)系：對于給定的傳輸系統(tǒng)11.3 糾錯編碼的性能式中，RB為碼元速率。若希望提高傳輸速率，由上式看出勢必使信噪比下降，誤碼率增大。假設(shè)系統(tǒng)誤碼率希望下降，付出的代價仍是帶寬增大三、差錯控制編碼的效用可見用糾錯編碼，可使誤碼率下降幾個數(shù)量級。在突發(fā)信道中，糾錯編碼的效用不如隨機信道明顯。11.3 糾錯編碼的性能11.4.1

10、奇偶監(jiān)督碼奇數(shù)監(jiān)督碼和偶數(shù)監(jiān)督碼。無論信息位有多少，監(jiān)督位只有一位。在接收端同樣進行模二加檢測。11.4 簡單的實用編碼11.4.2 二維奇偶監(jiān)督碼又稱方陣碼，是把奇偶監(jiān)督碼的若干碼組排列成矩陣，每一碼組寫成一行，再對每列進行二維監(jiān)督。11.4 簡單的實用編碼這種碼可能檢測出偶數(shù)個錯誤，按列的方向可能檢測出來。有一些偶數(shù)錯碼不可能檢測出來，如構(gòu)成矩形的4個錯碼就不行。適于檢測突發(fā)錯誤，常成串出現(xiàn)，在某一行出現(xiàn)較多。還可以糾錯，如只有一行中有奇數(shù)個錯時，能定位錯碼位置糾正。11.4 簡單的實用編碼11.4.3 恒比碼每個碼組中均含有相同數(shù)目的“1”（和“0”）。那么“1”和“0”的數(shù)目之比恒定。

11、檢測時，只要看接收到的碼中“1”的數(shù)目是否對。由于長度為5的碼組共有25=32種，有22組禁用碼，多余度較高。下圖所示11.4 簡單的實用編碼11.4 簡單的實用編碼11.4.4 正反碼電報通信中，n=10，信息位k=5，監(jiān)督位r=5。（1）信息位中有奇數(shù)個“1”時，監(jiān)督位是信息位的簡單重復(fù)；（2）信息位中有偶數(shù)個“1”時，監(jiān)督位是信息位的反碼；11.4 簡單的實用編碼（3）解碼方法：先將信息位和監(jiān)督位按模2加，得到一個5位的合成碼組，即產(chǎn)生一個校驗碼組。若接收到的信息位有奇數(shù)個“1”，則合成碼組就是校驗碼組；若有偶數(shù)個“1”，則取合成碼的反碼為校驗碼組。11.4 簡單的實用編碼11.4 簡單

12、的實用編碼校驗碼組的組成錯碼情況1全為“0”無錯碼2有4個“1”和1個“0”信息碼中有1位錯碼，其位置對應(yīng)校驗碼組中“0”的位置3有4個“0”和1個“1”監(jiān)督碼中有1位錯碼，其位置對應(yīng)校驗碼組中“1”的位置4其他組成錯碼多于1個例如，若發(fā)送碼組為1100111001，接收碼組中無錯碼，則合成碼組應(yīng)為00000。無錯。一、代數(shù)碼建立在代數(shù)學(xué)基礎(chǔ)上的編碼稱為代數(shù)碼，常見的是線性碼。其中的信息位和監(jiān)督位是由一些線性代數(shù)方程聯(lián)系著的。二、漢明碼是一種能夠糾正一位錯碼且編碼效率較高的線性分組碼。11.5 線性分組碼1、構(gòu)造原理在偶數(shù)監(jiān)督碼中，使用了一位監(jiān)督位a0，它和信息位an-1，a1構(gòu)成代數(shù)式：在接

13、收端解碼時，實際上就是計算11.5 線性分組碼11.5 線性分組碼若S = 0，就認(rèn)為無錯碼；若S = 1，就認(rèn)為有錯碼?，F(xiàn)將上式稱為監(jiān)督關(guān)系式，S稱為校正子。由于校正子S只有兩種取值，故它只能代表有錯和無錯這兩種信息，而不能指出錯碼的位置。若監(jiān)督位增加一位，即變成兩位，則能增加一個類似的監(jiān)督關(guān)系式。11.5 線性分組碼由于兩個校正子的可能值有4中組合： 00，01，10，11，故能表示4種不同的信息。若用其中1種組合表示無錯，則其余3種組合就有可能用來指示一個錯碼的3種不同位置。同理，r個監(jiān)督關(guān)系式能指示1位錯碼的(2r 1)個可能位置。11.5 線性分組碼一般來說，若碼長為n，信息位數(shù)為k

14、，則監(jiān)督位數(shù)rnk。如果希望用r個監(jiān)督位構(gòu)造出r個監(jiān)督關(guān)系式來指示1位錯碼的n種可能位置，則要求下面通過一個例子來說明如何具體構(gòu)造這些監(jiān)督關(guān)系式。2、（7，4）漢明碼設(shè)分組碼(n，k)中k=4，為了糾正一位錯碼，要求r=3，取r=3，則n=k+r=7。用a6 a5 a0表示這7個碼元S1S2S3錯誤位置S1S2S3錯誤位置001a0101a4010a1110a5100a2111a6011a3000無錯11.5 線性分組碼11.5 線性分組碼由表中規(guī)定可見，僅當(dāng)一位錯碼的位置在a2 、a4、a5或a6時，校正子S1為1；否則S1為零。這就意味著a2 、a4、a5和a6四個碼元構(gòu)成偶數(shù)監(jiān)督關(guān)系：1

15、1.5 線性分組碼在發(fā)送端編碼時，信息位a6、a5、a4和a3的值決定于輸入信號，因此它們是隨機的。監(jiān)督位a2、a1和a0應(yīng)根據(jù)信息位的取值按監(jiān)督關(guān)系來確定，即監(jiān)督位應(yīng)使上3式中S1、S2和S3的值為0：如下表所示11.5 線性分組碼信息位a6 a5 a4 a3監(jiān)督位a2 a1 a0信息位a6 a5 a4 a3監(jiān)督位a2 a1 a0000000010001110001011100110000101011010010001111010110010100110110000101011011101010011001111101000111000111111111.5 線性分組碼11.5 線性分組碼例

16、如，若接收碼組為0000011，按上述公式計算可得：S1=0，S2=1，S3=1。由于S1 S2 S3 等于011，故查表可知在a3位有1錯碼。 表中所列的(7, 4)漢明碼的最小碼距d0 = 3。因此，這種碼能夠糾正1個錯碼或檢測2個錯碼。漢明碼是一種高效碼3、線性分組碼的一般原理上述（7，4）漢明碼的d0=3，所以能糾一個錯碼或檢2個錯碼，將信息位和監(jiān)督位的關(guān)系寫成一般方程將上式寫成矩陣形式：11.5 線性分組碼上式還可以簡記為H AT = 0T 或A HT = 011.5 線性分組碼11.5 線性分組碼式中 A = a6 a5 a4 a3 a2 a1 a0 0 = 000右上標(biāo)“T”表示

17、將矩陣轉(zhuǎn)置。只要監(jiān)督矩陣H給定，編碼時監(jiān)督位和信息位的關(guān)系就完全確定了。11.5 線性分組碼H矩陣的性質(zhì)：1) H的行數(shù)就是監(jiān)督關(guān)系式的數(shù)目，它等于監(jiān)督位的數(shù)目r。H的每行中“1”的位置表示相應(yīng)碼元之間存在的監(jiān)督關(guān)系。例如，H的第一行1110100表示監(jiān)督位a2是由a6 a5 a4之和決定的。H矩陣可以分成兩部分，例如11.5 線性分組碼式中，P為rk階矩陣，Ir為rr階單位方陣。我們將具有P Ir形式的H矩陣稱為典型陣。2) 由代數(shù)理論可知，H矩陣的各行應(yīng)該是線性無關(guān)的，否則將得11.5 線性分組碼不到 r個線性無關(guān)的監(jiān)督關(guān)系式，從而也得不到 r個獨立的監(jiān)督位。若一矩陣能寫成典型陣形式P I

18、r，則其各行一定是線性無關(guān)的。因為容易驗證Ir的各行是線性無關(guān)的，故P Ir的各行也是線性無關(guān)的。11.5 線性分組碼G矩陣：上面漢明碼例中的監(jiān)督位公式為也可以改寫成矩陣形式：11.5 線性分組碼或?qū)懗墒街?，Q為一個kr階矩陣，它為P的轉(zhuǎn)置，即 Q = PT上式表示，在信息位給定后，用信息位的行矩陣乘矩陣Q就產(chǎn)生出監(jiān)督位。11.5 線性分組碼我們將Q的左邊加上1個k k階單位方陣，就構(gòu)成1個矩陣GG稱為生成矩陣，因為由它可以產(chǎn)生整個碼組，即有11.5 線性分組碼因此，如果找到了碼的生成矩陣G，則編碼的方法就完全確定了。具有IkQ形式的生成矩陣稱為典型生成矩陣。由典型生成矩陣得出的碼組A中，信息

19、位的位置不變，監(jiān)督位附加于其后。這種形式的碼稱為系統(tǒng)碼。 生成矩陣G的性質(zhì)：G矩陣的各行是線性無關(guān)的。任一碼組A都是G的各行的線性組合。若G的各行有線性相關(guān)的，則不可能由G生成2k種不同的碼組。2) 實際上，G的各行本身就是一個碼組。因此如果已有k個線性無關(guān)的碼組，則可以作為生成矩陣G，并由它生成其余碼組。11.5 線性分組碼4、接收碼組的檢驗：A為一n列的行矩陣，是發(fā)送碼組；B為一n列的行矩陣，是收到碼組；發(fā)送和接收碼組之差為：BAE （模2）11.5 線性分組碼11.5 線性分組碼因此，若ei = 0，表示該接收碼元無錯；若ei = 1，則表示該接收碼元有錯。 B A = E 可以改寫成

20、B = A + E錯碼矩陣有時也稱為錯誤圖樣。校正子S:當(dāng)接收碼組有錯時，E0，將B當(dāng)作A代入公式(A HT = 0)后，該式不一定成立。假設(shè)這時該式的右端為S，即 B HT = SS = (A + E) HT=AH T+EHT由于AHT = 0，所以S = EHT式中S稱為校正子。它能用來指示錯碼的位置。11.5 線性分組碼5、線性碼的封閉性即一種信息碼中的任意兩個碼組之和仍為這種碼中的一個碼組。所以兩個碼組之間的距離必定是另一個碼組的重量。因此，碼的最小距離就是碼的最小重量（除全“0”碼組外）。11.5 線性分組碼11.6 循環(huán)碼11.6.1 循環(huán)碼原理循環(huán)性：循環(huán)性是指任一碼組循環(huán)一位（

21、即將最右端的一個碼元移至左端，或反之）以后，仍為該碼中的一個碼組。在下表中給出一種(7, 3)循環(huán)碼的全部碼組。例如，表中的第2碼組向右移一位即得到第5碼組；第6碼組向右移一位即得到第7碼組。 11.6 循環(huán)碼碼組編號信息位監(jiān)督位碼組編號信息位監(jiān)督位a6a5a4a3a2a1a0a6a5a4a3a2a1a0100000005100101120010111610111003010111071100101401110018111001011.6 循環(huán)碼一般說來，若(an-1 an-2 a0)是循環(huán)碼的一個碼組，則循環(huán)移位后的碼組(an-2 an-3 a0 an-1)(an-3 an-4 an-1 a

22、n-2) (a0 an-1 a2 a1)也是該編碼中的碼組。11.6 循環(huán)碼碼多項式碼組的多項式表示法把碼組中各碼元當(dāng)作是一個多項式的系數(shù)，即把一個長度為n的碼組表示成例如，上表中的任意一個碼組可以表示為11.6 循環(huán)碼其中第7個碼組可以表示為這種多項式中，x僅是碼元位置的標(biāo)記，例如上式表示第7碼組中a6、a5、a2和a0為“1”，其他均為0。因此我們并不關(guān)心x的取值。 11.6 循環(huán)碼碼多項式的按模運算若一個整數(shù)m可以表示為式中，Q 整數(shù)，則在模 n 運算下，有m p (模n)即，在模 n 運算下，一個整數(shù)m等于它被 n 除得的余數(shù)。 11.6 循環(huán)碼在碼多項式運算中也有類似的按模運算。若一

23、任意多項式F(x)被一 n 次多項式N (x)除，得到商式Q(x)和一個次數(shù)小于n的余式R(x)，即則寫為11.6 循環(huán)碼這時，碼多項式系數(shù)仍按模2 運算，即系數(shù)只取 0 和1。例如，x3被(x3 + 1)除，得到余項1。所以有同理11.6 循環(huán)碼循環(huán)碼的碼多項式在循環(huán)碼中，若T(x)是一個長為n的許用碼組，則xiT(x)在按模xn + 1運算下，也是該編碼中的一個許用碼組，即若則T (x)也是該編碼中的一個許用碼組。11.6 循環(huán)碼循環(huán)碼的生成矩陣G由上節(jié)中公式可知，有了生成矩陣G，就可以由k個信息位得出整個碼組，而且生成矩陣G的每一行都是一個碼組。由于G是k行n列的矩陣，因此若能找到k個已

24、知碼組，就能構(gòu)成矩陣G。11.6 循環(huán)碼如前所述，這k個已知碼組必須是線性不相關(guān)的。在循環(huán)碼中，一個(n, k)碼有2k個不同的碼組。若用g(x)表示其中前(k-1)位皆為“0”的碼組，則g(x)，x g(x)，x2 g(x)，xk-1 g(x)都是碼組，而且這k個碼組是線性無關(guān)的。因此它們可以用來構(gòu)成此循環(huán)碼的生成矩陣G。11.6 循環(huán)碼在循環(huán)碼中除全“0”碼組外，連“0”的長度最多只能有(k - 1)位。因此，g(x)必須是一個常數(shù)項不為“0”的(n - k)次多項式，而且這個g(x)還是這種(n, k)碼中次數(shù)為(n k)的唯一多項式。我們稱這唯一的(n k)次多項式g(x)為碼的生成多

25、項式。一旦確定了g(x)，則整個(n, k)循環(huán)碼就被確定了。 11.6 循環(huán)碼因此，循環(huán)碼的生成矩陣G可以寫成 例：在上表所給出的(7, 3)循環(huán)碼中，n = 7, k = 3, n k = 4。由此表可見，唯一的一個(n k) = 4次碼多項式代表的碼組是第二碼組0010111，與它相對應(yīng)的碼多項式（即生成多項式）g(x) = x4 + x2 + x + 1。將此g(x)代入上式，得到或11.6 循環(huán)碼11.6 循環(huán)碼如何尋找任一(n, k)循環(huán)碼的生成多項式 由上式可知，任一循環(huán)碼多項式T(x)都是g(x)的倍式，故它可以寫成 T(x) = h(x)g(x)而生成多項式g(x)本身也是一

26、個碼組，即有 T(x) = g(x)11.6 循環(huán)碼由于碼組T(x)是一個(n k)次多項式，故xk T(x)是一個n次多項式。由下式可知，xk T(x)在模(xn + 1)運算下也是一個碼組，故可以寫成11.6 循環(huán)碼上式左端分子和分母都是n次多項式，故商式Q(x) = 1。因此，上式可以化成將T(x)和T(x)表示式代入上式，經(jīng)過化簡后得到11.6 循環(huán)碼上式表明，生成多項式g(x)應(yīng)該是(xn + 1)的一個因子。例如，(x7 + 1)可以分解為為了求(7, 3)循環(huán)碼的生成多項式g(x)，需要從上式中找到一個(n k) = 4次的因子。不難看出，這樣的因子有兩個，即11.6 循環(huán)碼以上

27、兩式都可作為生成多項式。不過，選用的生成多項式不同，產(chǎn)生出的循環(huán)碼碼組也不同。11.6 循環(huán)碼11.6.2 循環(huán)碼的編解碼方法循環(huán)碼的編碼方法1、編碼原則在編碼時，首先要根據(jù)給定的(n, k)值選定生成多項式g(x)，即從(xn + 1)的因子中選一個(n - k)次多項式作為g(x)。11.6 循環(huán)碼2、編碼步驟：用xn - k乘m(x)。例如，信息碼為110，它相當(dāng)于m(x) = x2 + x。當(dāng)n k = 7 3 = 4時，xn - k m(x) = x4 (x2 + x) = x6 + x5，它相當(dāng)于1100000。用g(x)除xn - k m(x)，得到商Q(x)和余式r(x)，即1

28、1.6 循環(huán)碼循環(huán)碼的解碼方法1、解碼要求：檢錯和糾錯。（1）檢錯解碼原理：在接收端可以將接收碼組R(x)用原生成多項式g(x)去除。當(dāng)傳輸中未發(fā)生錯誤時，接收碼組與發(fā)送碼組相同，即R(x) = T(x)，故接收碼組R(x)必定能被g(x)整除。11.6 循環(huán)碼（2）糾錯解碼原理：用生成多項式g(x)除接收碼組R(x)，得出余式r(x)。按余式r(x)，用查表的方法或通過某種計算得到錯誤圖樣E(x)；從R(x)中減去E(x)，便得到已經(jīng)糾正錯碼的原發(fā)送碼組T(x)。11.7 卷積碼非分組碼概念：通常它更適用于前向糾錯，因為對于許多實際情況它的性能優(yōu)于分組碼，而且運算較簡單。卷積碼在編碼時雖然也

29、是把k個比特的信息段編成n個比特的碼組，但是監(jiān)督碼元不僅和當(dāng)前的k比特信息段有關(guān)，11.7 卷積碼而且還同前面m = (N 1)個信息段有關(guān)。所以一個碼組中的監(jiān)督碼元監(jiān)督著N個信息段。通常將N稱為編碼約束度，并將nN稱為編碼約束長度。一般說來，對于卷積碼，k 和 n 的值是比較小的整數(shù)。我們將卷積碼記作(n, k, N)。碼率則仍定義為k / n。 11.7 卷積碼11.7.1 卷積碼的基本原理編碼器原理方框圖編碼輸出每次輸入k比特1k1k1k1k 1k2k3kNk 12nNk級移存器n個模2加法器每輸入k比特旋轉(zhuǎn)1周11.7 卷積碼例： (n, k, N) = (3, 1, 3)卷積碼編碼器

30、bi-2bi輸入bibi-1編碼輸出dicieiM2M3M111.7 卷積碼設(shè)輸入信息比特序列是bi-2 bi-1 bi bi+1，則當(dāng)輸入bi時，此編碼器輸出3比特ci di ei，輸入和輸出的關(guān)系如下：11.7 卷積碼在下圖中用虛線示出了信息位bi的監(jiān)督位和各信息位之間的約束關(guān)系。這里的編碼約束長度nN等于9。 ci-2di-2ei-2ci-1di-1ei-1cidieibi-2bi1bitt輸入輸出11.7 卷積碼11.7.2 卷積碼的代數(shù)表述卷積碼也是一種線性碼。一個線性碼完全由一個監(jiān)督矩陣H或生成矩陣G所確定。 監(jiān)督矩陣H假設(shè)上圖中在第1個信息位b1進入編碼器之前，各級移存器都處于“

31、0”狀態(tài)，則監(jiān)督位di、ei和信息位bi之間的關(guān)系可以寫為11.7 卷積碼左式可以改寫為11.7 卷積碼與11.5節(jié)公式HAT = 0T對比，可以看出監(jiān)督矩陣為11.7 卷積碼由此例可見，卷積碼的監(jiān)督矩陣H是一個有頭無尾的半無窮矩陣。11.7 卷積碼不難看出，這種截短監(jiān)督矩陣的結(jié)構(gòu)形式如下圖所示：H1 =nn k(n k)N11.7 卷積碼生成矩陣G上例中的輸出碼元序列可以寫成 b1 d1 e1 b2 d2 e2 b3 d3 e3 b4 d4 e4 = b1 b1 b1 b2 b2 (b2 + b1) b3 (b3 + b1) (b3 + b2 + b1) b4 (b4 + b2) (b4 +

32、 b3 + b2) 11.7 卷積碼11.7 卷積碼此碼的生成矩陣G即為上式最右矩陣： 它也是一個半無窮矩陣，其特點是每一行的結(jié)構(gòu)相同，只是比上一行向右退后3列（因現(xiàn)在n = 3）。11.7 卷積碼11.7.3 卷積碼的解碼1、代數(shù)解碼：利用編碼本身的代數(shù)結(jié)構(gòu)進行解碼，不考慮信道的統(tǒng)計特性。大數(shù)邏輯解碼，又稱門限解碼，是卷積碼代數(shù)解碼的最主要一種方法，它也可以應(yīng)用于循環(huán)碼的解碼。大數(shù)邏輯解碼對于約束長度較短的卷積碼最為有效，而且設(shè)備較簡單。2、概率解碼：又稱最大似然解碼。它基于信道的統(tǒng)計特性和卷積碼的特點進行計算。針對無記憶信道提出的序貫解碼就是概率解碼方法之一。另一種概率解碼方法是維特比算法

33、。當(dāng)碼的約束長度較短時，它比序貫解碼算法的效率更高、速度更快，目前得到廣泛的應(yīng)用。11.7 卷積碼11.8 Turbo碼基本原理由于分組碼和卷積碼的復(fù)雜度隨碼組長度或約束度的增大按指數(shù)規(guī)律增長，所以為了提高糾錯能力，人們大多不是單純增大一種碼的長度，而是將兩種或多種簡單的編碼組合成復(fù)合編碼。11.8 Turbo碼Turbo碼的編碼器在兩個并聯(lián)或串聯(lián)的分量碼編碼器之間增加一個交織器，使之具有很大的碼組長度，能在低信噪比條件下得到接近理想的性能。 Turbo碼有兩個分量碼譯碼器，在兩者之間進行迭代譯碼，故整個譯碼過程類似渦輪（turbo）工作，所以又形象地稱為Turbo碼。11.8 Turbo碼RSCC編碼器交織器RSCC編碼器bibic1ic2i編碼器的基本結(jié)構(gòu)：它由一對遞歸系統(tǒng)卷積碼(RSCC)編碼器和一個交織器組成，如下圖所示：11.9 低密度奇偶校驗碼低密度奇偶校驗(LDPC)碼是一種線性分組碼，和Turbo碼同屬于復(fù)合碼類。兩者的性能相近，且兩者的譯碼延遲都相當(dāng)長，所以它們更適用于一些實時性要求不很高的通信。但是LDPC碼比Turbo碼的譯碼簡單，更易實現(xiàn)。11.9 低密度奇偶校驗碼LDPC碼的分類：規(guī)則L