第8章-差錯控制技術(shù)

第8章差錯控制技術(shù)§8.1差錯控制的常用方法§8.2糾錯編碼§8.3常用的簡單編碼§8.4線性分組碼§8.5循環(huán)碼§8.6m序列§8.1差錯控制的常用方法自動請求重發(fā)（ARQ）

停發(fā)等待重發(fā)

返回重發(fā)

選擇重發(fā)前向糾錯（FEC）混合糾錯（HEC）反饋檢驗（IRQ）自動請求重發(fā)優(yōu)點：譯碼設(shè)備簡單，對突發(fā)錯誤和信道干擾較嚴(yán)重時比較有效。缺點：需要反饋信道，實時性差。前向糾錯優(yōu)點：使用糾錯碼和單向信道，發(fā)送端無需設(shè)置緩沖器。缺點：設(shè)備復(fù)雜、成本高?；旌霞m錯特點：實時性和譯碼復(fù)雜性方面是前向糾錯和檢錯重發(fā)方式的折衷，可達(dá)到較低的誤碼率，較適合于環(huán)路延遲大的高速數(shù)據(jù)傳輸系統(tǒng)。反饋校驗優(yōu)點：設(shè)備簡單，可以糾正任何錯誤缺點：會引入較大的時延。舉例：有一種由3個二進(jìn)制碼元構(gòu)成的編碼，它共有23=8種 不同的可能碼組：

000–晴001–云010–陰011–雨

100–雪101–霜110–霧111–雹 這時，若一個碼組中發(fā)生錯碼，則將收到錯誤信息。若在此8種碼組中僅允許使用4種來傳送天氣，例如：令

000–晴011–云101–陰110–雨 為許用碼組，其他4種不允許使用，稱為禁用碼組。 這時，接收端有可能發(fā)現(xiàn)（檢測到）碼組中的一個錯碼。這種編碼只能檢測錯碼，不能糾正錯碼。若規(guī)定只許用兩個碼組：例如

000–晴111–雨 就能檢測兩個以下錯碼，或糾正一個錯碼。

糾錯編碼的基本原理8分組碼概念分組碼＝信息位＋監(jiān)督位分組碼符號：(n,k)

其中，n－碼組總長度，

k－信息碼元數(shù)目。

r=n–k

－監(jiān)督碼元數(shù)目。 右表中的碼組為(3,2)碼。分組碼的一般結(jié)構(gòu)：分組碼的參數(shù)：碼重：碼組內(nèi)“1”的個數(shù)碼距：兩碼組中對應(yīng)位取值不同的位數(shù)，又稱漢明距離最小碼距(d0)：各碼組間的最小距離信息位監(jiān)督位晴000云011陰101雨110k個信息位r個監(jiān)督位an-1an-2...arar-1an-2...a0t碼長n=k+r分組碼的結(jié)構(gòu)9碼距的幾何意義：以n=3的編碼為例一般而言，碼距是n維空間中單位正多面體頂點之間的漢明距離。(0,0,0)(0,0,1)(1,0,1)(1,0,0)(1,1,0)(0,1,0)(0,1,1)(1,1,1)a2a0a1碼距與糾檢錯能力的關(guān)系為了檢測t個隨機錯誤，則要求碼組的最小距離距為

碼距與糾檢錯能力的關(guān)系為了糾正t個隨機錯誤，則要求碼組的最小距離為碼距與糾檢錯能力的關(guān)系糾正t個隨機錯碼，同時檢測e個隨機錯誤，則要求碼組的最小距離為(e≥t)14常用的簡單編碼奇偶校驗碼群計數(shù)碼恒比碼正反碼線性分組碼代數(shù)碼－利用代數(shù)關(guān)系式產(chǎn)生監(jiān)督位的編碼線性分組碼－代數(shù)碼的一種，其監(jiān)督位和信息位的關(guān)系由線性代數(shù)方程決定漢明碼－一種能夠糾正一個錯碼的線性分組碼校正子： 在偶數(shù)監(jiān)督碼中，計算 實際上就是計算 并檢驗S是否等于0。 S稱為校正子監(jiān)督關(guān)系式：糾錯基本原理中，S只有兩種取值，故只能表示有錯和無錯，而不能進(jìn)一步指明錯碼的位置。若此碼組長度增加一位，則能增加一個監(jiān)督關(guān)系式。這樣，就能得到兩個校正子。兩個校正子的可能取值有4種組合，即00，01，10，11，故能表示4種不同的信息。若用其中一種組合表示無錯碼，則還有其他3種組合可以用于指明一個錯碼的3種不同位置。從而可以有糾錯能力。一般而言，若有r個監(jiān)督關(guān)系式，則r個校正子可以指明一個錯碼的(2r–1)個不同位置。當(dāng)校正子可以指明的錯碼位置數(shù)目等于或大于碼組長度n時，才能夠糾正碼組中任何一個位置上的錯碼，即要求漢明碼例：要求設(shè)計一個能夠糾正1個錯碼的分組碼(n,k)，給定的碼組中有4個信息位，即k=4。由 這時要求監(jiān)督位數(shù)r

3。若取r=3，則n=k+r=7?，F(xiàn)在用a6

a5

a4

a3

a2

a1

a0表示這7個碼元，用S1S2

S3表示校正子，則這3個校正子恰好能夠指明23–1=7個錯碼的位置。若規(guī)定校正子和錯碼位置的關(guān)系如下表，則僅當(dāng)在a6

a5

a4

a2位置上有錯碼時，校正子S1的值才等于1；否則S1的值為零。這就意味著a6

a5

a4

a2四個碼元構(gòu)成偶數(shù)監(jiān)督關(guān)系：同理，有在編碼時，信息位a6

a5

a4

a3的值決定于輸入信號，它們是隨機的。監(jiān)督位a2

a1

a0是按監(jiān)督關(guān)系確定的，應(yīng)該保證上列3式中的校正子等于0，即有 給定信息位后，為了 計算監(jiān)督位，上式可 以改寫為 按照上式計算結(jié)果為19在接收端解碼時，對于每個接收碼組，先按式 計算出校正子S1，S2和S3，然后按照表 判斷錯碼的位置。 例：若接收碼組為0000011，則按上三式計算得到：S1=0，S2=1，S3=1。這樣，由上表可知，錯碼位置在a3。20上例中的漢明碼是(7,4)碼，其最小碼距d0=3。由式可知，此碼能夠檢測2個錯碼，或糾正1個錯碼。漢明碼的碼率：

當(dāng)r(或n)很大時，上式趨近于1。所以漢明碼是一種高效編碼。分組碼的一般原理線性分組碼的監(jiān)督位和信息位的關(guān)系 可以改寫為 上式中，已經(jīng)將“

”簡寫成“+”。監(jiān)督矩陣 上式可以寫成矩陣形式：

（模2）

將上式簡寫為

HAT=0T

或AHT=0

HAT=0T

式中， －稱為監(jiān)督矩陣監(jiān)督矩陣的性質(zhì)監(jiān)督矩陣H確定碼組中的信息位和監(jiān)督位的關(guān)系。H的行數(shù)就是監(jiān)督關(guān)系式的數(shù)目，即監(jiān)督位數(shù)r

。H的每行中“1”的位置表示相應(yīng)的碼元參與監(jiān)督關(guān)系。

H可以分成兩部分，例如 －典型監(jiān)督矩陣式中，P為r

k階矩陣，Ir為r

r階單位方陣。

A=[a6

a5

a4

a3

a2

a1

a0]

0=[000]24H矩陣的各行應(yīng)該是線性無關(guān)的，否則將得不到r個線性無關(guān)的監(jiān)督關(guān)系式。若一個矩陣能寫成典型陣形式[PIr]，則其各行一定是線性無關(guān)的。生成矩陣?yán)? 可以寫為 上式兩端分別轉(zhuǎn)置后，可以變成式中，Q為k

r階矩陣，是P的轉(zhuǎn)置，即Q=PT

將Q的左邊加上一個k階單位方陣，稱為生成矩陣： －生成矩陣

G稱為生成矩陣，因為可以用它產(chǎn)生整個碼組A，即有生成矩陣的性質(zhì)具有[IkQ]形式的生成矩陣稱為典型生成矩陣。由典型生成矩陣得出的碼組A中，信息位的位置不變，監(jiān)督位附加于其后。這種形式的碼組稱為系統(tǒng)碼。矩陣G的各行也必須是線性無關(guān)的。如果已有k個線性無關(guān)的碼組，則可以將其用來作為生成矩陣G，并由它生成其余碼組。錯誤圖樣 設(shè)：發(fā)送碼組A是一個n列的行矩陣： 接收碼組是一個n列的行矩陣B： 令接收碼組和發(fā)送碼組之差為

E就是錯碼的行矩陣

---稱為錯誤圖樣 式中，

(i=0,1,…,n-1)

若ei

=0，表示該碼元未錯；若ei=1，表示該碼元為錯碼B–A=E(模2)校正子矩陣

B–A=E可以改寫成B=A+E上式表示發(fā)送碼組A與錯碼矩陣E之和等于接收碼組B。例如，若發(fā)送碼組A=[1000111]， 錯碼矩陣E=[0000100]，則 接收碼組B=[1000011]。在接收端解碼時，將接收碼組B代入式

AHT=0

中A的位置進(jìn)行計算。若接收碼組中無錯碼，則B=A。代入后，該式仍成立，即有

BHT=0

只有當(dāng)錯碼未超出檢測能力時，上式才不成立。 假設(shè)，這時該式的右端等于S，即有

BHT=S

將B=A+E代入上式，得到:S=(A+E)HT=AHT+EHT

S=(A+E)HT=AHT+EHT上式右端第一項等于0，所以

S=EHT

－校正子矩陣當(dāng)H確定后，上式中S只與E有關(guān)，而與A無關(guān)。這意味著，S和錯碼E之間有確定的線性變換關(guān)系。 若S和E有一一對應(yīng)關(guān)系，則S將能代表錯碼位置。線性碼的封閉性：若A1和A2是一種線性碼中的兩個碼組，則(A1+A2)仍是其中一個碼組。

『證』若A1和A2是兩個碼組，則有：A1HT=0,A2HT=0

將上兩式相加，得出

A1HT+A2HT=(A1+A2)HT=0

所以(A1+A2)也是一個碼組。 由于線性碼具有封閉性，所以兩個碼組(A1和A2)之間的距離（即對應(yīng)位不同的數(shù)目）必定是另一個碼組(A1+A2)的重量（即“1”的數(shù)目）。因此，碼的最小距離就是碼的最小重量（除全“0”碼組外）。循環(huán)碼

循環(huán)性是指任一碼組循環(huán)一位后仍然是該編碼中的一個碼組。例：一種(7,3)循環(huán)碼的全部碼組如下表中第2碼組向右移一位即得到第5碼組；第5碼組向右移一位即得到第7碼組。一般情況 若(an-1

an-2…a0)是循環(huán)碼的一個碼組，則循環(huán)移位后的碼組： (an-2

an-3…a0

an-1) (an-3

an-4…an-1

an-2) …… (a0

an-1…a2

a1)

仍然是該編碼中的碼組。多項式表示法 一個長度為n的碼組(an-1

an-2…a0)可以表示成

上式中x的值沒有任何意義，僅用它的冪代表碼元的位置。 例：碼組1100101可以表示為31循環(huán)碼的運算整數(shù)的按模運算 在整數(shù)運算中，有模n運算。例如，在模2運算中，有

1+1=2

0(模2)， 1+2=3

1(模2)，2

3=6

0(模2)

等等。 一般說來，若一個整數(shù)m可以表示為 式中，Q為整數(shù)，則在模n運算下，有

m

p(模n)

所以，在模n運算下，一個整數(shù)m等于它被n除得的余數(shù)。碼多項式的按模運算 若任意一個多項式F(x)被一個n次多項式N(x)除，得到商式Q(x)和一個次數(shù)小于n的余式R(x)，即 則在按模N(x)運算下，有 這時，碼多項式系數(shù)仍按模2運算。 例1：x3被(x3+1)除，得到余項1，即 例2： 因為 x

x3+1x4+x2+1

x4+x

x2+x+1

在模2運算中加法和減法一樣。循環(huán)碼的數(shù)學(xué)表示法 在循環(huán)碼中，設(shè)T(x)是一個長度為n的碼組，若 則T

(x)也是該編碼中的一個碼組。

[證]設(shè)一循環(huán)碼為 則有 上式中的T

(x)正是碼組T(x)向左循環(huán)移位i次的結(jié)果。 例：一循環(huán)碼為1100101，即 若給定i=3，則有 上式對應(yīng)的碼組為0101110，它正是T(x)向左移3位的結(jié)果。結(jié)論：一個長為n的循環(huán)碼必定為按模(xn+1)運算的一個余式。循環(huán)碼的生成有了生成矩陣G，就可以由k個信息位得出整個碼組： 例： 式中， 生成矩陣G的每一行都是一個碼組。因此，若能找到k個已知的碼組，就能構(gòu)成矩陣G。如前所述，這k個已知碼組必須是線性不相關(guān)的。在循環(huán)碼中，一個(n,k)碼有2k個不同的碼組。若用g(x)表示其中前(k-1)位皆為“0”的碼組，則g(x)，xg(x)，x2g(x)，

，xk-1g(x)都是碼組，而且這k個碼組是線性無關(guān)的。因此它們可以用來構(gòu)成此循環(huán)碼的生成矩陣G。在循環(huán)碼中除全“0”碼組外，再沒有連續(xù)k位均為“0”的碼組。否則，在經(jīng)過若干次循環(huán)移位后將得到k位信息位全為“0”，但監(jiān)督位不全為“0”的一個碼組。這在線性碼中顯然是不可能的。因此，g(x)必須是一個常數(shù)項不為“0”的(n-k)次多項式，而且這個g(x)還是這種(n,k)碼中次數(shù)為(n–k)的唯一一個多項式。因為如果有兩個，則由碼的封閉性，把這兩個相加也應(yīng)該是一個碼組，且此碼組多項式的次數(shù)將小于(n–k)，即連續(xù)“0”的個數(shù)多于(k–1)。顯然，這是與前面的結(jié)論矛盾的。我們稱這唯一的(n–k)次多項式g(x)為碼的生成多項式。一旦確定了g(x)，則整個(n,k)循環(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)=x4+x2+x+1即“10111”

將此g(x)代入上矩陣，得到 或 上式不符合G=[IkQ]形式，所以它不是典型生成矩陣。但它經(jīng)過線性變換后，不難化成典型陣。 此循環(huán)碼組的多項式表示式T(x)： 上式表明，所有碼多項式T(x)都能夠被g(x)整除，而且任意一個次數(shù)不大于(k–1)的多項式乘g(x)都是碼多項式。尋求碼生成多項式因為任意一個循環(huán)碼T(x)都是g(x)的倍式，故它可以寫成

T(x)=h(x)

g(x)

而生成多項式g(x)本身也是一個碼組，即有

T

(x)=g(x)

由于碼組T

(x)是一個(n–k)次多項式，故xkT

(x)是一個n次多項式。由 可知，xk

T

(x)在模(xn+1)運算下也是一個碼組，所以有 上式左端分子和分母都是n次多項式，故相除的商式Q(x)=1。因此，上式可以寫成將T(x)=h(x)

g(x)和T

(x)=g(x)代入 化簡后，得到上式表明，生成多項式g(x)應(yīng)該是(xn+1)的一個因子。例：(x7+1)可以分解為 為了求出(7,3)循環(huán)碼的生成多項式g(x)，需要從上式中找到一個(n–k)=4次的因子。這樣的因子有兩個，即 以上兩式都可以作為生成多項式。 選用的生成多項式不同，產(chǎn)生出的循環(huán)碼碼組也不同。

循環(huán)碼的編碼方法用xn-k乘m(x)。這一運算實際上是在信息碼后附加上(n–k)個“0”。例如，信息碼為110，它寫成多項式為m(x)=x2+x。當(dāng)n–k=7–3=4時，xn-km(x)=x4(x2+x)=x6+x5，它表示碼組1100000。用g(x)除xn-km(x)，得到商Q(x)和余式r(x)，即有 例：若選定g(x)=x4+x2+x+1，則有 上式是用碼多項式表示的運算。它和下式等效：編出的碼組T(x)為：T(x)=xn-km(x)+r(x)

在上例中，T(x)=1100000+101=1100101

循環(huán)碼的解碼方法在檢錯時：當(dāng)接收碼組沒有錯碼時，接收碼組R(x)必定能被g(x)整除，即下式 中余項r(x)應(yīng)為零；否則，有誤碼。當(dāng)接收碼組中的錯碼數(shù)量過多，超出了編碼的檢錯能力時，有錯碼的接收碼組也可能被g(x)整除。這時，錯碼就不能檢出了。在糾錯時：用生成多項式g(x)除接收碼組R(x)，得出余式r(x)。按照余式r(x)，用查表的方法或計算方法得出錯誤圖樣E(x)。從R(x)中減去E(x)，便得到已經(jīng)糾正錯碼的原發(fā)送碼組T(x)。截短循環(huán)碼截短目的： 在設(shè)計時，通常信息位數(shù)k、碼長n和糾錯能力都是預(yù)先給定的。但是，并不一定有恰好滿足這些條件的循環(huán)碼存在。故采用截短碼長截短，得出滿足要求的編碼。截短方法： 設(shè)給定一個(n,k)循環(huán)碼，它共有2k種碼組，現(xiàn)使其前i(0<i<k)個信息位全為“0”，于是它變成僅有2k-i種碼組。然后從中刪去這i位全“0”的信息位