差錯控制編碼

差錯控制編碼和線性分組碼

§11.1

基本概念§11.2分組碼

§11.3循環(huán)碼

一、什么是差錯控制編碼及為什么引入差錯控制編碼？§11.1基本概念

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

差錯控制編碼的基本思路：

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

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

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

3、混合方式（HEC）結(jié)合前向糾錯和ARQ的系統(tǒng)，在糾錯能力范圍內(nèi)，自動糾正錯誤，超出糾錯范圍則要求發(fā)送端重新發(fā)送。它是一種折中的方案。1、隨機差錯：差錯的出現(xiàn)是隨機的，一般而言差錯出現(xiàn)的位置是隨機分布的。這種情況一般是由信道的加性隨機噪聲引起的。一般將這種信道稱為隨機信道。2、突發(fā)差錯：差錯的出現(xiàn)是一連串出現(xiàn)的。這種情況如移動通信中信號在某一段時間內(nèi)發(fā)生衰落，造成一串差錯；光盤上的一條劃痕等等。這樣的信道我們稱之為突發(fā)信道。3、混合差錯：既有突發(fā)錯誤又有隨機差錯的情況。這種信道稱之為混合信道。三、信道發(fā)生差錯的幾種模式四、差錯控制編碼分類按功能分檢錯碼糾錯碼糾刪碼（發(fā)現(xiàn)不可糾正的錯誤時，可發(fā)出指示或刪除）按信息碼元和監(jiān)督碼元之間的校驗關(guān)系分線性碼非線性碼按信息碼元和監(jiān)督碼元之間的約束方式分分組碼卷積碼分組碼：將k個信息比特編成n個比特的碼字，共有個碼字。所有傳輸時前后碼字之間毫無關(guān)系。==平均每個碼字所攜帶的信息比特率。編碼速率=卷積碼：也是將k個信息比特編成n個比特，但是前后的N個碼字之間是相互關(guān)聯(lián)。個碼字組成一個分組碼。按信息碼元在編碼后是否保持原來的形式不變系統(tǒng)碼非系統(tǒng)碼按糾正錯誤的類型分糾正隨機錯誤的碼糾正突發(fā)錯誤的碼按構(gòu)造差錯控制編碼的數(shù)學(xué)方法分代數(shù)碼幾何碼算術(shù)碼按每個碼元取值不同分二進制碼多進制碼糾錯碼建立在香農(nóng)理論基礎(chǔ)上香農(nóng)信道編碼定理存在噪聲干擾的信道，若信道容量為C，只要發(fā)送端以低于C的速率R發(fā)送信息（R為輸入到編碼器的二進制碼元速率），則一定存在一種編碼方式，使編碼的錯誤概率隨著碼長n的增加將按指數(shù)下降到任一的值，即五、有擾離散信道編碼定理稱為誤差指數(shù)。

結(jié)論1、如碼長及發(fā)送信息速率一定，可以通過增大信道容量，使P減小。2、如在信道容量及發(fā)送信息速率一定，可以通過增加碼長，使錯誤概率指數(shù)下降。E（R）CC1C2R六、檢錯和糾錯的基本原理如用三位二進制編碼來代表八個字母

000 A 100 E 001 B 101 F 010 C 110 G 011 D 111 H不管哪一位發(fā)生錯誤，都會使傳輸字母錯誤如用三位字母傳四個字母

000 A 011 B 101 C 110 D發(fā)生一位錯誤，準用碼字將變成禁用碼字，接收端就能知道出錯，但是不能糾錯。差錯控制編碼如用三位字母傳二個字母

000 A 111 B 檢兩個以下錯誤，糾正一個錯誤。結(jié)論具有檢錯或糾錯的碼組，其所用的比特數(shù)必須大于信息碼組原來的比特數(shù) －>引入多余度。碼重、碼距碼重(weight)一個碼組中“1”的數(shù)目碼距(distance)兩個碼組之間對應(yīng)位置上1、0不同的位數(shù)，又叫漢明(Hamming)距。

10110碼重：3 011002距離：3檢錯、糾錯能力為檢查出

個錯誤，要求最小碼距為為糾正個錯誤，要求最小碼距為為糾正個錯誤，同時檢查出個錯誤，要求最小碼距為

分組碼表示：(n,k) n:幀長 k/n:編碼效率特點監(jiān)督碼只用來監(jiān)督本幀中的信息位分類線性碼－信息碼與監(jiān)督碼之間為線性關(guān)系非線性碼－不存在線性關(guān)系

奇偶監(jiān)督碼偶監(jiān)督奇監(jiān)督如果以上關(guān)系被破壞，則出現(xiàn)錯誤，因此能檢查出奇數(shù)個錯誤，但不能檢測偶數(shù)個錯誤。 最小碼距為dmin=2這種碼檢錯能力不高，采用什么方法提高呢？七、幾種簡單檢錯碼水平奇偶監(jiān)督碼和水平垂直監(jiān)督碼又叫二維奇偶監(jiān)督碼水平奇偶監(jiān)督碼將碼字按行排成方陣，每行采用奇偶監(jiān)督碼，發(fā)送時按列的順序傳送，接收時仍將碼字排列成發(fā)送時方陣形式，然后按行進行奇偶校驗。在不增加冗余度時，不僅能發(fā)現(xiàn)某一行上奇數(shù)個錯誤，而且也能發(fā)現(xiàn)不大于方陣行數(shù)的突發(fā)錯誤。水平垂直奇偶監(jiān)督碼不僅對行進行奇偶校驗，而且也對列進行奇偶校驗。恒比碼在碼長一定時，“1”碼和“0”碼的比例恒定。已用于電報傳輸中。恒比碼的譯碼可以采用查表方法，檢錯時檢查1的個數(shù)是否為3。

每個漢字用4位阿拉伯數(shù)字表示，每個阿拉伯數(shù)字用5個比特的碼字表示。由于阿拉伯數(shù)字只有10個，因此從32中可能的碼字中挑出C53=10個1的個數(shù)為3個的碼字作為阿拉伯數(shù)字的編碼方式，見下表阿拉伯數(shù)字編碼阿拉伯數(shù)字編碼101011610101211001711100310110801110411010910011500111001101

在國際圖書的發(fā)行中，經(jīng)常用編碼的方式來防止書號在通信過程中發(fā)生錯誤。如《通信原理》的書號是ISBN7-118-01429-X

其中第一位數(shù)字“7”表示“中國”，“118”表示出版社，“01429”表示書名編號，最后一位“X”表示校驗位（它是羅馬數(shù)字10的表示）。這里所采用的校驗方式如下所示：71180429X=1078917172123324271524415879102134176176(模11)=0。編碼的應(yīng)用：ISBN國際統(tǒng)一圖書編號§11.1基本概念§11.2分組碼

§11.3循環(huán)碼

差錯控制編碼和線性分組碼（n，k）中許用碼字（組）為2k個。定義線性分組碼的加法為模2加，乘法為二進制乘法。即1+1=0、1+0=1、0+1=1、0+0=01x1=1,1x0=0,0x0=0,0x1=0且碼字與碼字的運算是各個相應(yīng)比特位上符合上述二進制加法運算規(guī)則。一、線性分組碼的基本概念1、線性分組碼的性質(zhì)（n，k）線性分組碼的性質(zhì)：封閉性。任意兩個碼組的和還是許用的碼組。碼的最小距離等于非零碼的最小碼重。所謂的線性分組碼就是信息位和校驗位之間的監(jiān)督關(guān)系是線性的。所謂線性就是監(jiān)督位能表示成信息的線性和形式。

2、碼的校驗矩陣和生成矩陣碼的校驗矩陣（監(jiān)督矩陣）偶校驗碼的構(gòu)成：

對于偶校驗碼的監(jiān)督關(guān)系：如果S=1，則認為傳輸時出錯；S=0，則認為無誤傳輸。上式稱為監(jiān)督關(guān)系，S稱為校驗子。問題：為了能糾一位錯，k位信息至少需要多少位的監(jiān)督信息，如何設(shè)計？如果校驗子有兩位，則可以有四種組合，可以表示4種不同的信息，如果用其中的一種表示無錯，則其它3種可以表示錯誤的種類（或位置），為了能糾一個錯，至少要求監(jiān)督位數(shù)應(yīng)滿足：如果取k=4，則可以確定n>=7。因此，可以用3個校驗子來確定傳輸?shù)?個位置是否出錯。假設(shè)傳輸時的碼字為，如果與錯碼的位置對應(yīng)如下：錯碼位置錯碼位置001101010110100111011000

無錯可得

在發(fā)送端編碼時，信息位的取值取決于輸入的信息比特，因此它們是隨機變化的。監(jiān)督位應(yīng)根據(jù)信息位的取值按監(jiān)督關(guān)系來確定，即監(jiān)督位應(yīng)該使上三式的取值為0。因此，給出信息位后，根據(jù)上式可以算出監(jiān)督位，從而得到（7，4）的所有碼組。0000000100011100010111001100001010110100100011110101100101001101100001010110111010100110011111010001110001111111

分組碼（1）漢明碼：能糾一位錯誤(7,4)

分組碼（2）在接收端，按如下規(guī)律運算分組碼（3）分組碼的監(jiān)督方程矩陣形式分組碼（4）監(jiān)督矩陣H矩陣稱為典型形式，各行一定是線性無關(guān)的。而一個非典型形式的經(jīng)過運算可以化成典型形式，通過監(jiān)督矩陣可以知道監(jiān)督碼和信息碼的監(jiān)督關(guān)系。只要監(jiān)督矩陣確定，則編碼時信息位與監(jiān)督位的關(guān)系就確定了。因此，線性分組碼的設(shè)計實際上是如何設(shè)計監(jiān)督矩陣的問題。分組碼（5）生成矩陣

，通過生成矩陣可以得到生成碼組。如果輸入碼組為0011分組碼（6）由這種方式得到的生成矩陣稱為典型生成矩陣，由它產(chǎn)生的分組碼必定為系統(tǒng)碼，也就是信息碼字保持不變，監(jiān)督位附加其后，每行一定是線性無關(guān)的，每行都是一個生成碼組。因此，如果知道生成矩陣同樣可以確定編碼的碼組。這對所有的線性碼都是一樣的。假設(shè)信息位為，如果編碼后的碼組為如下形式：，其中

是監(jiān)督位，則稱這種碼為系統(tǒng)碼。

即系統(tǒng)碼經(jīng)過編碼后的碼組中前k個就是信息位，后n-k是監(jiān)督位。只有系統(tǒng)碼才有關(guān)系系統(tǒng)碼和非系統(tǒng)碼都有性質(zhì)：

校驗子S

假設(shè)我們發(fā)送的碼組為A，接收到的碼組為B，則B=A+E如果我們能在接收端確定E，那么我們就能夠通過接收到的B來譯碼得到A，即A=B+E。如何得到E呢？因此，如果我們將接收到的B按照設(shè)計的監(jiān)督關(guān)系進行運算，我們可以得到，S稱為錯誤圖樣。如果設(shè)計使S的不同組合與錯誤E一一對應(yīng)，則我們可以利用錯誤圖樣得到E，從而進行糾錯譯碼。在（7，4）碼的設(shè)計中，我們就是運用了這樣的基本原理。漢明碼

漢明碼監(jiān)督位為位，因此它可以組成個可能情況，其中一個為無錯。因此可以監(jiān)督碼位共 要糾正一個錯誤，必須滿足 最小碼距如果r位監(jiān)督位所組成的校正子碼組與誤碼圖樣一一對應(yīng)，這種碼組稱為完備碼（取等號時）擴展?jié)h明碼如果在漢明碼基礎(chǔ)上，再加上一位對所有碼字進行校驗的監(jiān)督位監(jiān)督碼字由r

位增加到

r+1位信息位不變碼長 碼結(jié)構(gòu)糾1位錯，檢測2位錯如（8，4），（16，11）

擴展?jié)h明碼矩陣

如(7,4)－>(8,4)縮短漢明碼(n,k)－>(n-s,k-s)如(15,11)－>(12,8)

監(jiān)督矩陣Hs是將原H的前3列去掉縮短漢明碼的最小碼距至少和原來碼的碼距相同，因為監(jiān)督位沒有變?？s短漢明碼能糾t個錯誤的(n,k)應(yīng)滿足

取等號時為完備碼不同結(jié)構(gòu)的線性碼其糾錯能力不同，能力和dmin有關(guān)，dmin越大越好。第十一章差錯控制編碼

§11.1基本概念§11.2分組碼

§11.3循環(huán)碼

§11.3循環(huán)碼(Cycliccode)

1957年發(fā)現(xiàn)特點線性分組碼循環(huán)性——任一許用碼字經(jīng)過循環(huán)移位后，得到的碼組仍為一個許用碼組如是循環(huán)碼的一許用碼組

則也是一許用碼組

設(shè)（7，4）漢明碼C的生成矩陣和校驗矩陣為：得到16個碼組是：（1000101）（0001011）（0010110）（0101100）（1011000）（0110001）（1100010）（0100111）（1001110）（0011101）（0111010）（1110100）（1101001）（1010011）（1111111）（0000000）由以上這些碼組可以看到：如果是C的碼組，則它的左右移位都是C的碼組，具有這種特性的線性分組碼稱為循環(huán)碼。

循環(huán)碼的性質(zhì)：1、封閉性：任何許用碼組的線性和還是許用碼組。由此性質(zhì)可以得到：線性碼都包含全零碼。最小碼重就是最小碼距。

2、循環(huán)性：任何許用的碼組循環(huán)移位后的碼組還是許用碼組。循環(huán)碼的多項式表示定義：碼的碼多項式如下：例1：（1011000）的碼多項式為碼多項式表示碼組 碼多項式碼組碼多項式左移一位左移位

為許用碼組，則也是許用碼組

碼組左移3位如左移3位后，得是許用碼組循環(huán)碼生成多項式g(D)循環(huán)碼完全由其碼長n和生成多項式構(gòu)成。其中g(shù)（D）是一個能除盡的n-k階多項式。階數(shù)低于n并能被g（D）除盡的一組碼多項式就構(gòu)成一個（n，k）循環(huán)碼。也就是說，階數(shù)小于n-1且能被g（D）除盡的每個多項式都是循環(huán)碼的許用碼組。循環(huán)碼生成多項式g(D)g(D)是D的(n-k)次即r次多項式信息多項式為M(D),k位，(k-1)次多項式g(D)定理.一個(n,k)的二進制循環(huán)碼可以看成是唯一由它的生成多項式產(chǎn)生，即如(7,3)循環(huán)碼，n=7,k=3,r=4如果信息位為010，M(D)=D

生成碼為0111010例如，（7，4）循環(huán)碼的生成多項式則階數(shù)低于n-1能被g（D）除盡的多項式為如下：，則對應(yīng)的循環(huán)碼多項式為

因此，對應(yīng)的循環(huán)碼組為（1111111）。假設(shè)循環(huán)碼生成多項式的構(gòu)造1、循環(huán)碼多項式表示及循環(huán)性質(zhì)循環(huán)碼中任何碼組的循環(huán)移位還是許用碼組。定理一：碼組，經(jīng)過移位位，得到碼組

則可以證明：即例2：（7，4）循環(huán)碼（1000101）的碼多項式為移位1位后變成

將它被除，得到

因此，循環(huán)左移一位的余式為其相對應(yīng)的碼組為（0001011），正好是（1000101）循環(huán)左移一位的結(jié)果。

2、循環(huán)碼多項式的構(gòu)造定理二：（n，k）循環(huán)碼的生成多項式一定是的因式，即

反之，如果是一個n-k次多項式，且除盡則此一定生成一個（n，k）循環(huán)碼。因式分解可以通過計算機分解的方式分解，也可以通過查表（別人已經(jīng)作好的因式分解表）例，因此，（7，4）循環(huán)碼的生成多項式可以選擇或而（7，3）循環(huán)碼的生成多項式可以選擇或

（7，6）循環(huán)碼的生成多項式為D+1，實際上就是簡單的偶校驗碼。（7，1）循環(huán)碼的生成多項式為實際上是7重重復(fù)碼。生成矩陣G(D)由于k位信息位共有個碼組，如果現(xiàn)有信息碼生成k個碼字，且這k個碼組都線性無關(guān)，用這k個碼組作為一個矩陣G的k行構(gòu)成生成矩陣G(D)稱為循環(huán)碼的生成矩陣多項式1、非系統(tǒng)碼的生成矩陣輸入信息碼元為時，相應(yīng)的循環(huán)碼組多項式為：

由上式得到的碼組不是系統(tǒng)碼。例：已知（7，4）循環(huán)碼的生成多項式為求生成矩陣。所以解：(7,3)循環(huán)碼生成矩陣2、系統(tǒng)碼的生成矩陣

系統(tǒng)碼定義：（n，k）系統(tǒng)碼的碼組中前k個比特是信息比特，后n-k個比特是循環(huán)監(jiān)督位。問題：已知生成多項式g（D），如何構(gòu)造系統(tǒng)碼的生成矩陣？系統(tǒng)碼的生成矩陣典型形式非系統(tǒng)碼系統(tǒng)碼(7,3)循環(huán)碼生成矩陣監(jiān)督矩陣在系統(tǒng)碼中，碼組應(yīng)該具備如下的形式：

其中，的次數(shù)小于等于n-k-1。實際上上式表示了如何生成系統(tǒng)碼，即將信息碼多項式升n-k次，然后以g（D）為模，求出余式r（D）。非系統(tǒng)碼系統(tǒng)碼系統(tǒng)碼的碼多項式為例如，(7,4)碼，1011

非系統(tǒng)碼系統(tǒng)碼(7,3)碼例：已知（7，4）系統(tǒng)循環(huán)碼的生成多項式為求生成矩陣。解：系統(tǒng)碼的生成矩陣形式肯定是因此我們選擇信息多項式為