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

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

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

返回重發(fā)

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

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

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

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

000–晴111–雨 就能檢測(cè)兩個(gè)以下錯(cuò)碼，或糾正一個(gè)錯(cuò)碼。

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

其中，n－碼組總長(zhǎng)度，

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

r=n–k

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

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

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

a5

a4

a3

a2

a1

a0表示這7個(gè)碼元，用S1S2

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

a5

a4

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

a5

a4

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

a5

a4

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

a1

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

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

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

（模2）

將上式簡(jiǎn)寫(xiě)為

HAT=0T

或AHT=0

HAT=0T

式中， －稱(chēng)為監(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)該是線(xiàn)性無(wú)關(guān)的，否則將得不到r個(gè)線(xiàn)性無(wú)關(guān)的監(jiān)督關(guān)系式。若一個(gè)矩陣能寫(xiě)成典型陣形式[PIr]，則其各行一定是線(xiàn)性無(wú)關(guān)的。生成矩陣?yán)? 可以寫(xiě)為 上式兩端分別轉(zhuǎn)置后，可以變成式中，Q為k

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

將Q的左邊加上一個(gè)k階單位方陣，稱(chēng)為生成矩陣： －生成矩陣

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

E就是錯(cuò)碼的行矩陣

---稱(chēng)為錯(cuò)誤圖樣 式中，

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

若ei

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

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

AHT=0

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

BHT=0

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

BHT=S

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

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

S=EHT

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

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

將上兩式相加，得出

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

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

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

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

an-3…a0

an-1) (an-3

an-4…an-1

an-2) …… (a0

an-1…a2

a1)

仍然是該編碼中的碼組。多項(xiàng)式表示法 一個(gè)長(zhǎng)度為n的碼組(an-1

an-2…a0)可以表示成

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

1+1=2

0(模2)， 1+2=3

1(模2)，2

3=6

0(模2)

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

m

p(模n)

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

x3+1x4+x2+1

x4+x

x2+x+1

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

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

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

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

，xk-1g(x)都是碼組，而且這k個(gè)碼組是線(xiàn)性無(wú)關(guān)的。因此它們可以用來(lái)構(gòu)成此循環(huán)碼的生成矩陣G。在循環(huán)碼中除全“0”碼組外，再?zèng)]有連續(xù)k位均為“0”的碼組。否則，在經(jīng)過(guò)若干次循環(huán)移位后將得到k位信息位全為“0”，但監(jiān)督位不全為“0”的一個(gè)碼組。這在線(xiàn)性碼中顯然是不可能的。因此，g(x)必須是一個(gè)常數(shù)項(xiàng)不為“0”的(n-k)次多項(xiàng)式，而且這個(gè)g(x)還是這種(n,k)碼中次數(shù)為(n–k)的唯一一個(gè)多項(xiàng)式。因?yàn)槿绻袃蓚€(gè)，則由碼的封閉性，把這兩個(gè)相加也應(yīng)該是一個(gè)碼組，且此碼組多項(xiàng)式的次數(shù)將小于(n–k)，即連續(xù)“0”的個(gè)數(shù)多于(k–1)。顯然，這是與前面的結(jié)論矛盾的。我們稱(chēng)這唯一的(n–k)次多項(xiàng)式g(x)為碼的生成多項(xiàng)式。一旦確定了g(x)，則整個(gè)(n,k)循環(huán)碼就被確定了。因此，循環(huán)碼的生成矩陣G可以寫(xiě)成例： 上表中的編碼為(7,3)循環(huán)碼，n=7,k=3,n–k=4，其中唯一的一個(gè)(n–k)=4次碼多項(xiàng)式代表的碼組是第二碼組0010111，與它對(duì)應(yīng)的碼多項(xiàng)式，即生成多項(xiàng)式，為

g(x)=x4+x2+x+1。

g(x)=x4+x2+x+1即“10111”

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

T(x)=h(x)

g(x)

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

T

(x)=g(x)

由于碼組T

(x)是一個(gè)(n–k)次多項(xiàng)式，故xkT

(x)是一個(gè)n次多項(xiàng)式。由 可知，xk

T

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

g(x)和T

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

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

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

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