第7章-物聯(lián)網(wǎng)通信技術(shù)(曾憲武)LXX2014.7

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

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

7.1.1差錯(cuò)控制的基本原理

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

（1）情況1。

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

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

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

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

2.碼間距離(d)

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

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

3.最小碼距

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

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

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

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

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

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

解

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

e=d0－1=1，由定理7.1.1可知，能檢查出一個(gè)錯(cuò)。對(duì)于{000,111}，d0=3，e=d0－1=2，可以查出2個(gè)錯(cuò)。由定理

7.1.2可知，t=1，能糾正一個(gè)錯(cuò)。

5.編碼效率

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

7.2差錯(cuò)控制方法

7.2.1自動(dòng)請(qǐng)求重發(fā)(ARQ)方式

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

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

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

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

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

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

ARQ方式具有以下特點(diǎn)：

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

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

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

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

FEC方式具有如下特點(diǎn)：

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

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

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

式。它不僅能檢測(cè)出錯(cuò)誤，而且還能在一定程度上糾正錯(cuò)誤。HFC方式具有如下特點(diǎn)：

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

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

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

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

IRQ方式具有以下特點(diǎn)：

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

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

（3）傳輸效率低。

7.3常用檢錯(cuò)碼

7.3.1奇偶校驗(yàn)碼

1.編碼方法

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

2.奇偶校驗(yàn)編碼的特點(diǎn)

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

錯(cuò)誤。7.3.2恒比碼

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

1.編碼方法

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

正確。我國的電傳機(jī)傳輸漢字時(shí)是采用“保護(hù)電碼”來進(jìn)行的，該碼為5中取3的恒定碼，碼的長(zhǎng)度為5，碼中“1”的個(gè)數(shù)

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

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

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

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

2.特點(diǎn)

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

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

1.編碼方法

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

督位。

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

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

2.特點(diǎn)

這種二維奇偶監(jiān)督碼適于檢測(cè)突發(fā)錯(cuò)碼。因?yàn)檫@種突發(fā)錯(cuò)碼常常成串出現(xiàn)，隨后有較長(zhǎng)一段無錯(cuò)區(qū)間，所以在某一行出現(xiàn)多個(gè)奇偶錯(cuò)碼的機(jī)會(huì)較多，而這種矩陣碼正適合于檢測(cè)這類突發(fā)錯(cuò)誤。

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

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

上的錯(cuò)誤。

1.編碼方法

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

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

2.譯碼

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

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

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

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

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

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

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

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

為例來說明其整個(gè)編碼過程。

(7,4)碼中，信息碼的長(zhǎng)度為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ù)通信中，尤其是在計(jì)算機(jī)通信中，應(yīng)用非常廣泛的一種差錯(cuò)控制編碼是循環(huán)冗余校驗(yàn)碼(CRC)。CRC編碼實(shí)際上是一種線性分組碼，具有很強(qiáng)的糾錯(cuò)能力。

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

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

2.碼多項(xiàng)式

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

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

3.碼多項(xiàng)式的同余

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

該碼循環(huán)一次的碼多項(xiàng)式是原碼多項(xiàng)式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)進(jìn)行k－1循環(huán)移位，可得到k個(gè)碼字g(x),

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

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

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

1.編碼方法

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

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

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

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

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

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

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

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

3.CRC校驗(yàn)碼的生成和校驗(yàn)

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

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

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

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

位0作為校驗(yàn)碼。在接收端進(jìn)行校驗(yàn)時(shí)，可按以下步驟進(jìn)行：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

7.5卷積碼

7.5.1基本原理

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

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

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

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

mj－2按一定方式進(jìn)行模2加的運(yùn)算，得到兩個(gè)監(jiān)督碼元Pj1、Pj2后依次隨mj送入信道。由圖7.5.1可知：（7.5.1）若下一個(gè)單位時(shí)間內(nèi)輸入的信息碼元為mj+1，則它的兩個(gè)監(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.簡(jiǎn)單卷積編碼器

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

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

2.解碼器

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

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

R1、