第7章差錯控制技術(shù)7.1差錯控制技術(shù)概述7.2差錯控制方法7.3常用檢錯碼7.4循環(huán)碼7.5卷積碼本章小結(jié)

7.1差錯控制技術(shù)概述

7.1.1差錯控制的基本原理

在二進制編碼中，1位二進制編碼可表示2種不同的狀態(tài)，2位二進制編碼可表示4種不同的狀態(tài)，n位二進制編碼可以表示2n種不同的狀態(tài)。在n位二進制編碼的2n種不同的狀態(tài)中，能表示有用信息的碼組稱為許用碼組，不能表示有用信息的碼組稱為禁用碼組?，F(xiàn)以3位二進制編碼構(gòu)成的碼組集合{000,001,010,011,100,101,110,111}為例，分三種情況討論。

（1）情況1。

若8個狀態(tài)都表示有用信息，即均是許用碼組，則其中任一碼字出錯都將變成另一個碼字，于是，接收端無法識別哪個出錯。（2）情況2。若只取4個狀態(tài)，則取000、011、101、110表示許用碼組，001、100、010、111表示禁用碼組。如果000中錯1位，那么可能變?yōu)?01、100、010中的任一個，而這三個均是禁用碼組，可知傳輸出錯。當(dāng)000出現(xiàn)三個錯誤時，將變?yōu)?11，也是禁用碼；當(dāng)000出現(xiàn)兩個錯誤時，將變?yōu)?11、110、101，它們均是許用碼，可見在接收端無法發(fā)現(xiàn)錯誤。從上述分析可以看出，采用這種方法可以發(fā)現(xiàn)部分差錯，但不能糾錯。又如，在接收端收到100，盡管可以知道是一個錯碼，但000、101和110在發(fā)生一位錯碼的情況下均可以是100。（3）情況3。若要糾正錯碼，就需增加冗余。如果僅取000和111表示許用碼組，其他為禁用碼組，那么可以檢驗出2個錯碼，并能糾正1個錯碼。例如，收到100時，若只有一個錯碼，則可以判斷錯碼在第一位，并糾正為000，因為111的任何一位誤碼均不會為100，而可能為011、101或110；但若假設(shè)誤碼數(shù)不超過2位，則存在兩種可能，即000錯1位和111錯2位，均可能變?yōu)?00，因此只能檢測出錯誤，而無法糾錯。7.1.2差錯控制編碼的特性與能力

差錯控制編碼的能力與差錯控制編碼的特性有關(guān)。編碼的特性主要包括碼字的漢明重量、碼間距離和最小碼距。我們用C表示由許多碼元Ci(0≤i≤n－1)構(gòu)成的碼字，碼字中碼元的個數(shù)用n表示。以下先介紹漢明重量、碼間距離和最小碼距的概念。

1.碼字的漢明重量(HammingWeight)

碼字C=Cn－1Cn－2…C0的漢明重量是指碼字中非零碼元的個數(shù)，用HW(C)表示。例如，1101的漢明重量為3（可寫成HW(1101)=3），HW(110101)=4。

2.碼間距離(d)

碼間距離又稱為海明距離，是指一碼組集合中任意兩個碼字之間的對應(yīng)位上碼元不同的個數(shù)，用d表示，可表示為

式中，Ci、Cj分別表示碼組集合中的任意兩個碼組（碼字），Ci=Cin－1Cin－2…Ci0。例如，對于兩個碼字1101和0111，=1+0+1+0=2d(10101,11010)=4。

3.最小碼距

在一個碼組集合(C1，C2，…，CN）中，各碼字之間的距離可能是不相同的，就稱該碼組集合中最小的碼距為最小碼距，用d0表示。例如，對于碼組集合(0111100,1011011,1101001)，d(0111100,1011011)=5，d(0111100,1101001)=4，d(1011011,1101001)=3，于是最小碼距d0=3。在分析一組碼字（碼組）的檢錯糾錯能力時，總用最小碼距d0來衡量，這是一種最不利的情況。在3位二進制碼中，把8個碼字的許用碼變?yōu)?個碼字許用碼就具有了糾錯能力，這是因為這8個碼字的d0=1，而在{000，001,101,110}中，它們的d0=2，在{000,111}中它們的d0=3。由此可見，碼組集合中的最小碼距d0不同，糾錯檢錯的能力不同，碼組集合中的最小碼距越大，其糾錯檢錯的能力也就越強。

4.編碼糾錯檢錯能力與最小碼距d0的關(guān)系

差錯控制編碼的抗干擾能力與碼的結(jié)構(gòu)有關(guān)，一種編碼的結(jié)構(gòu)是與它們的碼距有關(guān)的，碼距的長度可以反映出該種編碼方式抗干擾的能力，碼距與糾錯檢錯能力之間的關(guān)系可用如下定理表述。定理7.1.1若一種碼的最小碼距為d0，則它能檢查傳輸差錯個數(shù)（或稱為檢錯能力）e應(yīng)滿足d0≥e+1。

由定理7.1.1可知，對于3位二進制編碼，8個碼字均是許用碼時，d0=1，于是e=0，這說明該碼沒有差錯能力；當(dāng)使用4個碼字時，d0=2，則e=1，說明能查出1個差錯；若取2個碼字時，d0=3，則e=2，說明能查出2個差錯。因此，要想使傳輸?shù)拇a字具有檢錯能力，該碼組集合的最小碼距必須大于或等于2。定理7.1.2若一種碼的最小距離為d0，則它能糾正傳輸差錯的個數(shù)（又稱為糾錯能力）t應(yīng)滿足d0≥2t+1。

定理7.1.3若一種碼的最小距離為d0，則它能檢查e個差錯，同時又能糾正t個以下差錯的條件為d0≥t+e+1。

定理7.1.3說明，當(dāng)傳輸差錯等于或小于t時，該碼可以自動糾正這些差錯，但當(dāng)差錯大于t而又小于e時，該碼只能檢測出錯來。例7.1.1求碼組集合{000,011,101,110}和{000,111}的糾錯檢錯能力。

解

碼組集合{000,001,101,110}的最小距離d0=2，

e=d0－1=1，由定理7.1.1可知，能檢查出一個錯。對于{000,111}，d0=3，e=d0－1=2，可以查出2個錯。由定理

7.1.2可知，t=1，能糾正一個錯。

5.編碼效率

控制差錯編碼需要加入一定的監(jiān)督碼才能進行差錯控制，該編碼方式屬于分組編碼的一種。在編碼時，加入的監(jiān)督碼位數(shù)越多，其糾錯的能力也越強，但同時降低了編碼效率。若碼長用n表示，其中的信息碼的長度為k，監(jiān)督碼的長度為r，則有n=k+r，于是，編碼效率為

7.2差錯控制方法

7.2.1自動請求重發(fā)(ARQ)方式

由于采用檢錯編碼時，系統(tǒng)僅能發(fā)現(xiàn)傳輸錯誤，而不

知道錯誤發(fā)生的確切位置，因此需要采用自動請求重發(fā)工作方式。

接收端根據(jù)校驗序列的編碼規(guī)則判斷所接收的數(shù)據(jù)是否發(fā)生傳輸錯誤，并把判斷結(jié)果通過反饋信道傳送給發(fā)送端。接收端判斷的結(jié)果有三種可能：第一種是肯定確認，即接收端對收到的校驗幀校驗后未發(fā)現(xiàn)錯誤，會向發(fā)送端發(fā)送一個肯定確認信號，用ACK表示，發(fā)送端收到ACK信號后即可知道該幀發(fā)送成功。

第二種是否定確認。接收端收到一個幀后，經(jīng)校驗發(fā)現(xiàn)有錯誤，則回送一個否定確認信號，用NAK表示，發(fā)送端收到NAK信號后必須重發(fā)該幀。第三種是超時重發(fā)。發(fā)送端在發(fā)出一個幀后開始計時，如果在規(guī)定的時間內(nèi)沒有收到該幀的確認信號（ACK或NAK），則認為發(fā)生幀的丟失或確認信號丟失，必須重發(fā)該幀。在傳送數(shù)據(jù)時，發(fā)送需經(jīng)過發(fā)送、等待、確認這三個階段，即所謂的“停等ARQ”。在數(shù)據(jù)幀的發(fā)送中，發(fā)送端每次僅發(fā)送緩沖區(qū)中的一個數(shù)據(jù)幀，并在發(fā)送后立即啟動定時器，等待接收端回送的確認幀。定時器啟動后，如在規(guī)定的時間內(nèi)沒有收到確認信息幀，則認為發(fā)生幀的丟失或確認信號丟失，需要重新發(fā)送。假如在規(guī)定的時間沒有收到確認信息，系統(tǒng)就會自動重發(fā)，重發(fā)會造成重復(fù)幀的現(xiàn)象，即可能發(fā)生沒有出錯的數(shù)據(jù)幀重復(fù)發(fā)送到接收端的情況。

為了解決重復(fù)幀的問題，可在每個數(shù)據(jù)幀的幀頭增加一個發(fā)送序號，當(dāng)收到重復(fù)幀時，根據(jù)序號可將重復(fù)的幀丟

棄掉。為了提高傳輸效率，人們提出了連續(xù)重發(fā)請求(ContinuousARQ)技術(shù)，該技術(shù)的特點是不等待前一幀的確認，而直接發(fā)送下一幀。這樣可能會出現(xiàn)發(fā)送端未發(fā)現(xiàn)出錯之前，就有很多幀到達接收端，而接收端會將這些幀丟棄。為解決連續(xù)重發(fā)請求中出現(xiàn)的問題，人們提出了返回N幀ARQ及選擇性重發(fā)ARQ技術(shù)。

ARQ方式具有以下特點：

（1）只需要少量的冗余碼元就可獲得較高的傳輸可靠性。（2）與前向糾錯相比，復(fù)雜性和成本較低。

（3）ARQ方式要求有反饋信道，因此不能用于單向傳輸和同步傳輸。

（4）控制規(guī)程及控制過程較復(fù)雜，系統(tǒng)重復(fù)傳幀的現(xiàn)象較嚴重，通信效率低，不適合實時性要求高的場合。7.2.2前向糾錯(FEC)方式

FEC是利用糾錯編碼使接收端的譯碼器發(fā)現(xiàn)錯誤并準(zhǔn)確地判斷出出錯的位置，從而能自動糾正的差錯控制方式。

FEC方式具有如下特點：

（1）實時性高，無限反饋信道，特別適合于單向多點同時傳送，控制規(guī)則簡單，但譯碼設(shè)備較復(fù)雜。

（2）糾錯碼的冗余度較高，傳輸效率較低，并且糾錯碼與信道特性要相配合，對信道的要求較高。7.2.3混合糾錯(HEC)方式

混合糾錯方式是由FEC和ARQ兩者結(jié)合而成的差錯控制方

式。它不僅能檢測出錯誤，而且還能在一定程度上糾正錯誤。HFC方式具有如下特點：

（1）可以降低FEC的復(fù)雜度，改善ARQ的連貫性。

（2）通信效率較低，通信的可靠性較高，在衛(wèi)星通信中應(yīng)用廣泛。7.2.4信息反饋(IRQ)方式

信息反饋方式也稱為回程校驗方式，它是在發(fā)送端檢測

錯誤的。其工作過程為，發(fā)送端不對信息進行差錯編碼，而是直接將信息發(fā)送給接收端，接收端收到后，將其存儲起來，再將其通過反饋信道回送給發(fā)送端，由接收端比較并發(fā)現(xiàn)是否出錯。

IRQ方式具有以下特點：

（1）設(shè)備及控制規(guī)程簡單。

（2）需要反饋信道，收發(fā)兩端均需要大容量的存儲設(shè)備來存儲傳輸信息。

（3）傳輸效率低。

7.3常用檢錯碼

7.3.1奇偶校驗碼

1.編碼方法

奇偶校驗編碼只需在信息碼后加1位校驗位（或稱為監(jiān)督位），使碼組中“1”的個數(shù)為奇數(shù)或偶數(shù)。兩者的監(jiān)督方程分別為式中，Cn，Cn－1，…，C1為信息碼元，C0為監(jiān)督碼元。

2.奇偶校驗編碼的特點

奇偶校驗編碼的優(yōu)點是操作簡單，冗余度低，編碼效率高；缺點是奇校驗只能發(fā)現(xiàn)奇數(shù)個錯誤，不能發(fā)現(xiàn)偶數(shù)個

錯誤。7.3.2恒比碼

恒比碼是指碼字中所含“1”的個數(shù)相同的碼。由于碼長一定，則碼字中“1”和“0”的個數(shù)之比是恒定的，所以稱該種編碼方式為恒比碼。碼字中“1”的個數(shù)稱為碼重。

1.編碼方法

在恒比碼中，只需保持碼字中“1”和“0”的比例恒定即可。在接收端，只要判斷“1”的個數(shù)是否正確便可判斷傳輸是否

正確。我國的電傳機傳輸漢字時是采用“保護電碼”來進行的，該碼為5中取3的恒定碼，碼的長度為5，碼中“1”的個數(shù)

為3，“0”的個數(shù)為2。5位碼組成的碼組集合的碼字共有

25=32個，而5中取3的恒定碼共有C35=5!/(5－3)!3!=10,

恰好可以表示10個狀態(tài)，即可表示0~9共10個阿拉伯?dāng)?shù)字，并用它拼成漢字。我國的“保護電碼”比國際電碼的抗干擾能力強。一般情況下，從“n中取m（n>m）”恒比碼的碼字數(shù)

目為可見，恒比碼實際上是用n比特傳送了lbCmn比特信息量，如用“5中取3”的恒比碼來傳送數(shù)據(jù)，每個碼字的信息量為lb10=3.3(bit)，而5位二進制碼的每個碼字的信息量為lb25=5(bit)，也就是說用5－3.3=1.7的信息量作為檢驗碼而“浪費”的。恒比碼的編碼效率為“5中取3”的恒比碼編碼效率為η=3.3／5=0.66。在國際無線電報中，采用7位編碼，碼字中有3個1，共有C37=35個，可表示26個英文字母和其他一些符號。

2.特點

恒比碼所具有的優(yōu)點是編碼簡單，糾錯能力比奇偶校驗碼要強，適用于電傳機或其他鍵盤設(shè)備；缺點是不適用隨機二進制序列的編碼。

恒比碼必能發(fā)現(xiàn)錯誤的類型只有一種情況，即“1”錯為“0”的數(shù)目恰好是“0”錯為“1”的數(shù)目。7.3.3矩陣校驗碼

1.編碼方法

將若干個所要傳送的數(shù)字序列編排成一個矩陣，矩陣中的每一行為一個碼字，在每一行的最后加上一個監(jiān)督碼元，進行奇偶校驗，矩陣中的每一列則由不同碼字相同位置的碼元組成，在每列的最后也加上一個監(jiān)督碼元，進行奇偶校驗,如圖7.3.1所示。圖7.3.1矩陣碼組成圖7.3.1中，a10,…,am0為m行奇偶監(jiān)督碼中的m個監(jiān)督位，cn－1，…，c0為按列進行監(jiān)督的n列奇偶校驗的n個監(jiān)

督位。

這種碼有可能檢測出偶數(shù)個錯誤。因為每行的監(jiān)督位a10,…，am0雖然不能用于檢測本行中的偶數(shù)個錯誤，但按列有可能由cn－1,…，c0監(jiān)督出來。有一些偶數(shù)個錯誤不可能檢測出來，譬如a1n－2,a11,a2n－2,a21所構(gòu)成的4個錯碼。如數(shù)字序列11010101001010110011001110101010，現(xiàn)

將8位作為一個碼字，編成一個矩陣，每個碼字采用奇校驗，則編碼結(jié)果如圖7.3.2所示。圖7.3.2編矩陣碼結(jié)果

2.特點

這種二維奇偶監(jiān)督碼適于檢測突發(fā)錯碼。因為這種突發(fā)錯碼常常成串出現(xiàn)，隨后有較長一段無錯區(qū)間，所以在某一行出現(xiàn)多個奇偶錯碼的機會較多，而這種矩陣碼正適合于檢測這類突發(fā)錯誤。

由于矩陣碼只對構(gòu)成的四角誤碼無法檢測，所以它的檢測能力較強，一些試驗表明，這種碼可以使誤碼率降低至原誤碼率的百萬分之一到萬分之一。7.3.4正反碼

正反碼是一種簡單的能糾錯的碼，該種碼的監(jiān)督位與信息位相同，且監(jiān)督碼與信息碼相同或相反，主要用于單位電碼的前向自動糾錯設(shè)備，能糾正1位錯誤，發(fā)現(xiàn)大部分2位以

上的錯誤。

1.編碼方法

每一個正反碼字由10個碼元組成，其中5位信息碼，5位監(jiān)督碼。當(dāng)信息碼中“1”的個數(shù)為偶數(shù)時，監(jiān)督碼元是信息碼的反碼。例如：

信息碼為10101，監(jiān)督碼為10101，因為信息碼中“1”為奇數(shù)，所以監(jiān)督碼與信息碼相同；構(gòu)成的碼字為1010110101。信息碼為10010，監(jiān)督碼為01101，因為信息碼中“1”為偶數(shù)，所以監(jiān)督碼與信息碼相反；構(gòu)成的碼字為1001001101。

2.譯碼

在接收端，先將所接收碼字中的信息位和監(jiān)督位，按對應(yīng)的位進行模2加，得到一個5位的合成碼,然后用合成碼產(chǎn)生一個校驗碼。若接收碼字中信息碼中“1”的個數(shù)為奇數(shù)，則

合成碼作為校驗碼；如果信息碼中“1”的個數(shù)為偶數(shù)，則校驗碼為合成碼的反碼。最后觀察校驗碼字中“1”的個數(shù)，并根據(jù)表7.3.1中的判決規(guī)則進行判決。例如，發(fā)送碼字為1010110101，接收碼字為1010110101，合成碼為1010110101=00000，由于接收碼字中信息碼“1”的個數(shù)為奇數(shù)個，因此校驗碼為00000，對應(yīng)表7.3.1可看到無錯誤傳輸。

又例如，發(fā)送碼字為1010110101，接收碼字為1110110101，合成碼為11101＋10101=01000，由于接收碼字中信息碼“1”的個數(shù)為偶數(shù)個，因此校驗碼為10111，對應(yīng)表7.3.1可知信息碼有1位錯，位置在校驗碼“0”所對應(yīng)的位置，故可自動糾正為10101。7.3.5線性分組碼

線性分組碼(LinearBlockCodes)是信道編碼中最基本的一類編碼，在線性分組碼中，監(jiān)督碼僅與所在碼組中的信息碼元有關(guān)，且兩者之間是通過預(yù)設(shè)的線性關(guān)系聯(lián)系的。

線性分組碼的構(gòu)成是將信息序列劃分為等長為k位的序列段后，在每段之后附加r位監(jiān)督碼元(ParityCheckbits)，所構(gòu)成的長度為n=k+r的碼組記為(n,k)分組碼。

n位長度二進制碼可編成2n個碼字，但由于信息碼的長度僅為k，即信息碼字的個數(shù)為2k個（稱其為許用碼），所以其他2n－2k個碼字不能表示信息，這些不能表示信息的碼稱為禁用碼。

在(n,k)分組碼中，碼的長度為n，其中表示信息的碼長為k，共有2k個不同的長度為n的碼來對應(yīng)所表示的信息，這些碼構(gòu)成的碼組集合可用數(shù)學(xué)中的“群”來表示，并具有以下性質(zhì)。性質(zhì)1:封閉性,即任意兩個碼字之模2和仍為一個碼字。性質(zhì)2:碼的最小距離等于非零碼的最小重量。

線性分組編碼就是對長度為k的信息碼按照一定規(guī)則加入長度為n－k的監(jiān)督碼的過程，并且所增加的監(jiān)督碼與信息碼的碼元之間構(gòu)成某種線性關(guān)系。以下以(7,4)線性分組碼的編碼

為例來說明其整個編碼過程。

(7,4)碼中，信息碼的長度為4，可用C6C5C4C3來表示，監(jiān)督碼可用C2C1C0來表示，編碼后所形成的線性分組編碼可用C6C5C4C3C2C1C0來表示，監(jiān)督碼元C2、C1、

C0與信息碼元C6、C5、

C4及C3構(gòu)成了如下的線性關(guān)系：利用式(7.3.5)可得到(7,4)線性分組碼，其結(jié)果如表7.3.2所示。

7.4循環(huán)碼

7.4.1循環(huán)碼的基本概念

在數(shù)據(jù)通信中，尤其是在計算機通信中，應(yīng)用非常廣泛的一種差錯控制編碼是循環(huán)冗余校驗碼(CRC)。CRC編碼實際上是一種線性分組碼，具有很強的糾錯能力。

1.循環(huán)冗余校驗碼(CRC)的定義

若線性分組碼各碼字中的碼元循環(huán)左移位（或右移位）所形成的碼字仍然是碼組集合中的一個碼字（除全零碼外），則這種碼就稱為循環(huán)碼。如n長度循環(huán)碼中的一個碼為C=Cn－1Cn－2…C1C0,依次循環(huán)位移后得到的碼為各碼字均是循環(huán)碼中的碼組。

2.碼多項式

一個由二進制碼元序列組成的碼組都可以和一個只含有“0”和“1”兩個系數(shù)的多項式建立起一一對應(yīng)的關(guān)系，這個多項式就稱為碼多項式。

一個n位長的二進制序列，它是碼多項式Xn－1到X0的n－1次多項式的系數(shù)。如二進制碼元序列110110所對應(yīng)的碼多項式為把碼組中的碼元當(dāng)作多項式系數(shù)（取0或1），把n長度的碼字寫成最高次方n－1次的多項式：（7.4.1）一個碼字（碼組）與碼多項式是一一對應(yīng)的，如碼組1001101所對應(yīng)的碼多項式為T(X)=X6+X3+X2+1；而碼多項式X5+X4+X2+X對應(yīng)的碼組為110110。二進制碼多項式間可進行加減運算，即進行邏輯上的異或運算。如兩個二進制碼多項式A1(X)、A2(X)間的加減運算為

3.碼多項式的同余

若用X7+1去除X7+X6+X5+X3所得的余式和用X7+1去除X6+X5+X3+1所得的余式相同，即則稱兩個多項式X7+X6+X5+X3和X6+X5+X3+1同余，并記為利用同余的概念可以將循環(huán)碼通過對應(yīng)的碼多項式進行分析處理。在循環(huán)碼中，所有的非零碼都具有循環(huán)特性，即一個碼字可以由另一碼字向左（或向右）循環(huán)位移而得到，對應(yīng)于這種循環(huán)碼多項式也具有循環(huán)特性，即每個碼多項式都可以由一個次數(shù)低的碼多項式得到。

該碼循環(huán)一次的碼多項式是原碼多項式C(x)乘以x，除以xn+1的余式，記為

C1(x)=x·C（x）（modxn+1）推廣下去，C（x）的i次循環(huán)位移Ci（x）是C（x）乘以xi，除以xn+1的余式，即

Ci（x）=xi·C（x）（modxn+1）（7.4.2）

循環(huán)碼是線性分組碼的一種，因此可以應(yīng)用線性分組碼的編譯碼方法。在(n,k)循環(huán)碼集合中，取前k－1位都為零的碼字g(x)，根據(jù)循環(huán)碼的循環(huán)特性，將g(x)進行k－1循環(huán)移位，可得到k個碼字g(x),

xg(x),…，xk－1g(x)。這k個碼多項式線性無關(guān)，因此可利用這k個多項式相對應(yīng)的碼字作為各行構(gòu)成碼生成矩陣，于是得到(n,k)循環(huán)碼的生成矩陣碼生成矩陣一旦確定，碼也就確定了。式(7.4.3）說明

(n,k)循環(huán)碼可以由它的一個(n,k)次碼多項式g(x)來確定，稱g(x)為碼生成多項式。(n,k)次碼生成多項式g(x)具有下列性質(zhì)： 性質(zhì)1:g(x)是唯一的(n,k)次碼多項式，并且它的次數(shù)最低。

性質(zhì)2:g(x)是xn+1的因式，即xn+1=h(x)g(x)，h(x)稱為監(jiān)督多項式。7.4.2循環(huán)碼的編碼和譯碼

1.編碼方法

循環(huán)碼是由信息碼元和監(jiān)督碼元構(gòu)成的。首先把信息序列分為等長為k的若干個序列段，每信息段附加r位長度的監(jiān)督碼元，從而構(gòu)成長度為n=k+r的循環(huán)碼。循環(huán)碼用(n,k)表示，它也可以用一個n－1次多項式來表示。循環(huán)碼的格式如圖7.4.1所示。圖7.4.1循環(huán)碼的格式一個n位循環(huán)碼由k位信息碼加上r位校驗碼組成，其中

r=n－k。表征循環(huán)碼(CRC)的多項式稱為生成多項式G(X)。

k位二進制碼元加上r位CRC校驗位后，信息位要向左移，這相當(dāng)于A(X)乘上Xτ。XτA(X)除以生成多項式G(X)，得到整數(shù)多項式Q(X)加上余數(shù)多項式R(X)，即從而有利用多項式加減法的性質(zhì)，有

這說明信息多項式A(X)和余數(shù)多項式R(X)可以合并為一個新的多項式C(X)，稱為循環(huán)多項式，該多項式是生成多項式G(X)的整數(shù)Q(X)倍。

2.循環(huán)碼的性質(zhì)

在循環(huán)碼中，n－k次碼多項式有一個且僅有一個生成多

項式G(X)。在循環(huán)碼中，所有碼多項式能被生成多項式G(X)

整除。循環(huán)碼的輸出多項式G(X)是Xn+1的一個因式。

3.CRC校驗碼的生成和校驗

根據(jù)信息序列的分組長度和檢錯能力的要求，每個k位信息段附加r位監(jiān)督碼元構(gòu)成n=k+r位循環(huán)碼，其生成步驟如下：(1)在k位信息碼組的后面加上r個0。r是監(jiān)督碼元的位數(shù)，比生成多項式G(X)的位數(shù)r+1少1位。

(2)采用二進制除法將新的加長的長度為n的碼組用G(X)

來除，所產(chǎn)生的余數(shù)就是CRC校驗碼。

(3)用r個碼元的CRC校驗碼元替代信息段后面附加的r個0，如果余數(shù)的位數(shù)小于r，則在最左端用0補足r位；如果除法運算沒有產(chǎn)生余數(shù)（信息碼組是可以被整除的），則用r

位0作為校驗碼。在接收端進行校驗時，可按以下步驟進行：

第一步，將接收到的數(shù)據(jù)分為若干個長度為n的數(shù)據(jù)段，用G(X)來除。

第二步，如果n位數(shù)據(jù)段能被G(X)整除，則說明該數(shù)據(jù)段在傳送的過程中未發(fā)生差錯，否則，說明傳送過程中出現(xiàn)了差錯。

以下以兩個例子來說明循環(huán)碼的編碼過程。例如，信息碼組為1101，生成多項式為G(X)=X3+X+1，編(7,4)循環(huán)碼。編碼步驟如下：

(1)A(X)=1101為4位二進制碼，需附加r=7－4=3位監(jiān)督碼，在1101后附加000，變?yōu)?101000。

(2)用G(X)=X3+X+1（對應(yīng)的碼組為1011）去除1101000，即將1101000作為被除數(shù)，1011作為除數(shù)，進行除法運算,得到的余數(shù)為1，于是CRC校驗碼為001。

(3)用001替代第一步中的000，最后的編碼為1101001。注意，在進行除法運算時，需要進行減法運算，該減法運算實際上是一個異或運算，如10－01，則結(jié)果為11。

又例如，信息碼組為101，編一個(7,3)的循環(huán)碼。編碼的步驟如下：

（1）確定監(jiān)督碼的碼長，監(jiān)督位的碼長為r=n－k=7－3=4。

（2）確定生成多項式G（X）。根據(jù)循環(huán)碼的性質(zhì)，循環(huán)碼的生成多項式G（X）Xn+1的一個因式，所以生成多項式

G（X）是X7+1的一個因式，而G（X）是n－k=4次因式。對X7+1可分解因式為

X7+1=（X+1）（X3+X2+1）（X3+X2+1）

從X7+1的因式分解中任意選擇4次因式，我們選擇G(X)=(X+1)(X3+X2+1)，需要注意的是上述的因式分解與嚴格意義上的初等數(shù)學(xué)的因式分解不同，這里執(zhí)行的運算是異或運算，如X+X=0，因此

G(X)=(X+1)(X3+X2+1)=X4+X3+X2+1

所對應(yīng)的碼為11101。

(3)在信息碼組后附加4位0，變?yōu)?010000。

(4)除法運算，并求余。

(5)用余數(shù)0011替代0000，得到最后的編碼為1010011。

4.循環(huán)碼的應(yīng)用及特點

在串行通信中，常常采用CRC-16、CRC-CCITT及CRC-32這3種常用的生成多項式來產(chǎn)生校驗碼。

CRC-16的生成多項式為G(X)=X16+X15+X2+1;

CRC-CCITT的生成多項式為G(X)=X16+X12+X5+1;

CRC-32的生成多項式為G(X)=X32+X26+X23+X22+X16+X12+

X11+X10+X8+X7+X5+X4+X2+X+1。

7.5卷積碼

7.5.1基本原理

卷積碼是一種非分組碼，它的校驗位不僅和本組碼有關(guān)，而且還與前組及前若干組碼有關(guān)，具有連環(huán)監(jiān)督作用，因此卷積碼也稱為連環(huán)碼。

卷積碼的整個編碼過程是環(huán)環(huán)相扣連鎖進行的。編碼時，信息序列分為k0個碼元段，每段在經(jīng)過編碼后變?yōu)閚0

(n0>k0)個碼元的碼組，通常n0和k0都是較小的整數(shù)。編碼器的每個單位時間內(nèi)所輸出的n0個碼元不僅與此時輸入的k0個信息碼元有關(guān)，而且還與之前較長一段時間內(nèi)輸入的信息碼元有關(guān)。圖7.5.1所示為一個簡單的n0=3，

k0=1的卷積編碼器。圖7.5.1n0=3,k0=1的卷積編碼器在每一個單位時間內(nèi)，當(dāng)一個新的信息碼元mj進入編碼器，存儲在存儲器中的碼組向右依次移動一位，此時新的信息碼元一方面直接進入信道，同時前面兩個單位時間內(nèi)輸入的信息碼元mj－1、

mj－2按一定方式進行模2加的運算，得到兩個監(jiān)督碼元Pj1、Pj2后依次隨mj送入信道。由圖7.5.1可知：（7.5.1）若下一個單位時間內(nèi)輸入的信息碼元為mj+1，則它的兩個監(jiān)督碼元為（7.5.2）若輸入的信息碼元為mj、mj+1，則輸出的編碼為mjPj1Pj2

mj+1

P（j+1）1

P（j+1）2。若mjmj+1=11，則輸出為111101。7.5.2編碼和譯碼

1.簡單卷積編碼器

簡單卷積編碼器如圖7.5.2所示。它由兩個移位寄存器R1和R2及一個模2加法器構(gòu)成。圖7.5.2簡單卷積編碼器原理圖移位寄存器按信息碼率的速度進行工作，當(dāng)輸入1位信息碼元時，電子開關(guān)倒換一次，即前半拍接通a端，后半拍接通b端。因此，若輸入信息為a0a1a2a3…，第一拍，從寄存器

R1中移出的為a0，所以a端輸出的是a0；寄存器R2移出的是0（初始值為0），所以b端輸出的為b0=a0+0=a0。

2.解碼器

與圖7.5.2所對應(yīng)的解碼器如圖7.5.3所示。解碼器的輸入端是一個電子開關(guān)，它按節(jié)拍把信息碼元與監(jiān)督碼元分別接到a′端和b′端，3個移位寄存器R1、R2和R3的節(jié)拍為碼元序列節(jié)拍的一半。R1、

R2在信息碼元到達時移位，監(jiān)督碼元到達期間保持原狀態(tài)。寄存器R3在監(jiān)督碼元到達時移位，在信息碼元到達時保持原狀態(tài)。

R1、