通信原理第9章-差錯控制編碼課件培訓講學

通信原理第9章--差錯控制編碼課件

二進制數字信號在傳輸中發(fā)生的錯誤，主要有兩種類型：隨機錯誤和突發(fā)錯誤。隨機錯誤的特點是碼元間的錯誤互相獨立，即每個碼元的錯誤概率與它前后碼元的錯誤與否是無關的。突發(fā)錯誤則不然，一個碼元的錯誤往往影響前后碼元的錯誤概率?；蛘哒f，一個碼元產生錯誤，則后面幾個碼元都可能發(fā)生錯誤。在實際信道中，上述兩種錯誤形式往往兼而有之。移動通信的傳輸信道屬于變參信道，它不僅會引起隨機錯誤，而更重要的是造成突發(fā)錯誤。能發(fā)現錯誤的編碼叫檢錯碼；能糾正錯誤的編碼叫糾錯碼。一般說來，糾錯碼一定能檢錯。反過來，檢錯碼不一定能糾錯。或者說，同一個碼，檢錯能力比糾錯能力強。二、差錯控制方式在數字通信系統(tǒng)中，利用糾錯碼或檢錯碼進行差錯控制的方式有3種：檢錯重發(fā)、前向糾錯和混合糾錯，它們的系統(tǒng)構成如圖9-1所示，圖中有斜線的方框圖表示在該端檢出錯誤。1．檢錯控制方式

檢錯重發(fā)又稱自動請求重傳方式，記作ARQ(AutomaticRepeatRequest)。發(fā)送端發(fā)出能夠發(fā)現（檢測）錯誤的碼，接收端收到通過信道傳來的碼后，在譯碼器根據該碼的編碼規(guī)則，判決收到的碼序列中有無錯誤產生，如果發(fā)現錯誤，則通過反向信道把這一判決結果反饋給發(fā)端。然后，發(fā)端根據這些判決信號，把接收端認為有錯誤的信息再次傳送，直到接收端認為正確接收為止。

從上可知，應用ARQ方式必須有一反饋信道，一般較適用于一個用戶對一個用戶（點對點）的通信，且要求信源能夠控制，系統(tǒng)收發(fā)兩端必須互相配合、密切協(xié)作。由于反饋重發(fā)的次數與信道干擾情況有關，若信道干擾很頻繁，則系統(tǒng)經常處于重發(fā)消息的狀態(tài)，因此這種方式傳送消息的連貫性和實時性較差。該方式的優(yōu)點是：編譯碼設備簡單；在一定的多余度碼元下，檢錯碼的檢錯能力比糾錯碼的糾錯能力要高得多，因此這種系統(tǒng)的適應性很強，特別適應于短波、散射、有線等干擾情況特別復雜的信道中。2．前向糾錯方式

前向糾錯方式記作FEC（ForwordError-Correction)。發(fā)送端發(fā)送能夠被糾錯的碼，接收端收到這些碼后，通過糾錯譯碼器不僅能夠自動地發(fā)現錯誤，而且能自動地糾正接受碼字傳輸中的錯誤。這種方式的優(yōu)點是不需要反饋信道，能進行一個用戶對多個用戶的同播通信，譯碼實時性較好。其缺點是譯碼設備比較復雜，所選用的糾錯碼必須與信道的干擾情況相匹配，因此對信道的適應性較差。編碼效率低。但由于這種方式能同播，特別適用于軍用通信。

3．混合糾錯方式

混合糾錯方式記作HEC(HybridError-Correction)是FEC和ARQ方式的結合，這種方式是發(fā)送端發(fā)送的碼不僅能夠被檢測出錯誤，而且還具有一定的糾錯能力。接收端收到碼后，首先檢查差錯情況，如果在糾錯碼的糾錯能力范圍以內，則自動糾錯，如果錯誤過多，超過了碼的糾錯能力，但能檢測出來，則接收端通過反饋信道，要求發(fā)端重新傳送有錯的消息。這種方式具有自動糾錯和檢錯重發(fā)的優(yōu)點，并可達到較低的誤碼率。因此，在實際中的應用越來越廣。

在移動通信系統(tǒng)中，幾乎都采用前向糾錯的差錯控制方式。除了上述三種主要方式以外，還有所謂狹義信息反饋系統(tǒng)（IRQ—InformationRepeatRequest）。這種方式是接收端把收到的消息原封不動地通過反饋信道送回發(fā)送端，發(fā)送端比較發(fā)送的與反饋回來的消息，從而發(fā)現錯誤，并且把傳錯部分對應的原消息再次傳送，最后達到使對方正確接收消息的目的。三、糾錯碼的分類１.線性碼與非線性碼

根據糾錯碼各碼組信息和監(jiān)督元的函數關系，可分為線性碼和非線性碼。如果函數關系是線性的，即滿足一組線性方程式，則稱為線性碼，否則為非線性碼。線性碼集合中的所有碼字在加法和乘法運算時是封閉的，而非線性碼則不封閉。換言之，線性碼實際上就是n維線性空間的一個k（k<n）維子空間。目前大量使用的均為線性碼。２．分組碼與卷積碼

根據碼組中監(jiān)督碼元與信息碼元相互關聯的長度，可分為分組碼和卷積碼。分組碼的各碼元僅與本組的信息元有關；卷積碼中的碼元不僅與本組的信息元有關，而且還與前面若干組的信息元有關。分組碼把信息序列以k個碼元分組，通過編碼器將每組的k元信息按一定規(guī)律產生r個多余碼元（稱為校驗元或監(jiān)督元）輸出長為n=k+r的一個碼字（碼組）。因此，每一碼組的r個校驗元僅與本組的信息元有關而與別組無關。分組碼用(n，k)表示，n為碼長，k表示信息位數目。卷積碼將信息序列以k0個碼元分段，通過編碼器輸出長為n0的一段碼組。但是該碼的n0-k0個校驗元不僅與本段的信息源有關，而且也與其前m段的信息源有關，故卷積碼用（n0，k0，m0）表示。３．檢錯碼和糾錯碼

根據碼的用途，可分為檢錯碼和糾錯碼。檢錯碼以檢錯為目的，不一定能糾錯；而糾錯碼以糾錯為目的，一定能檢錯。另外，在分組碼中按照碼的結構特點，可以分為循環(huán)碼和非循環(huán)碼；根據糾（檢）錯誤的類型來分，可以分為糾正隨機錯誤的碼、糾正突發(fā)錯誤的碼和糾正同步錯誤的碼；根據碼元取值的進制來分，可分為二進制碼和多進制碼；等等，這里不一一贅述。四、糾錯編碼的基本原理下面以分組碼為例來說明糾錯碼檢錯和糾錯的基本原理。1．分組碼

分組碼一般可用（n，k）表示。其中，k是每個碼組二進制信息碼元的數目，n是編碼組的碼元總位數，又稱為碼組長度，簡稱碼長。n-k=r為每個碼組中的監(jiān)督碼元數目。簡單地說，分組碼是對每段k位長的信息組以一定的規(guī)則增加r個監(jiān)督元，組成長為n的碼字。在二進制情況下，共有2k個不同的信息組，相應地可得到2k個不同的碼字，稱為許用碼組。其余2n-2k個碼未被選用，稱為禁用碼組。

兩個等長碼組之間相應位取值不同的數目稱為這兩個碼組的漢明（Hamming）距離，簡稱碼距。例如11000與10011之間的距離d=3。碼組集合中任意兩個碼字之間距離的最小值稱為碼的最小距離，用d0表示。最小碼距是碼的一個重要參數，它是衡量碼檢錯、糾錯能力的依據。在分組碼中，非零碼元的數目稱為碼字的漢明重量，簡稱碼重。例如，碼字10110，碼重w=3。

2．檢錯和糾錯能力

我們以重復碼為例，說明為什么糾錯碼能夠檢錯或糾錯。若分組碼碼字中的監(jiān)督元在信息元之后，而且是信息元的簡單重復，則稱該分組碼為重復碼。它是一種簡單實用的檢錯碼，并有一定的糾錯能力。例如（2，1）重復碼，兩個許用碼組是00與11，d0=2，收端譯碼，出現01、10禁用碼組時，可以發(fā)現傳輸中的一位錯誤。如果是（3，1）重復碼，兩個許用碼為000、111，d0=3；當收端出現兩個或三個1時，判為1，否則判為0。此時，可以糾正一個錯誤，或者該碼可以檢出兩個錯誤。

從上面的例子中，可以看出：碼的最小距離d0直接關系著碼的檢錯和糾錯能力；任一（n，k）分組碼，若要在碼字內檢測e個隨機錯誤，則要求碼的最小距離：

d0

≥e+1要糾正t個隨機錯誤，則要求碼的最小距離：

d0≥2t+1要糾正t個錯誤同時檢測e個錯誤（e≥t），則要求碼的最小距離：

d0≥t+e+13．編碼效率

采用差錯控制編碼是提高了通信系統(tǒng)的可靠性，但是以降低有效性為代價換來的。通常定義編碼效率R來衡量有效性：

R=k/n其中，k是一個碼組中信息元的個數，n為碼長。對糾錯碼的基本要求是：檢錯和糾錯能力盡量強；編碼效率盡量高；編碼規(guī)律盡量簡單。實際中要根據具體指標要求，保證有一定糾、檢錯能力和編碼效率，并且易于實現。第二節(jié)常用的幾種簡單分組碼

糾錯編碼的種類很多，較早出現的、應用較多的大多屬于分組碼。本節(jié)僅介紹其中一些較為常用的簡單編碼。一、奇偶監(jiān)督碼

奇偶監(jiān)督碼是在原信息碼后面附加一個監(jiān)督元，使得碼組中“1”的個數是奇數或偶數?；蛘哒f，它是含一個監(jiān)督元，碼重為奇數或偶數的（n，n-1）系統(tǒng)分組碼。奇偶監(jiān)督碼又分為奇監(jiān)督碼和偶監(jiān)督碼。

設碼字A=〔an-1，an-2，a1，a0〕，對偶監(jiān)督碼有

(9-1)

式中an-1，an-2，…a1為信息元，a0為監(jiān)督元。由于該碼的每一個碼字均按同一規(guī)則構成式（9-1），故又稱為一致監(jiān)督碼。接收端譯碼時，按式（9-1）將碼組中的碼元模二相加，若結果為“0”就認為無錯（包括有偶數個錯誤）；結果為“1”，就可斷定該碼組經傳輸后有奇數個錯誤。奇監(jiān)督碼情況相似，只是碼組中“1”的數目為奇數，即滿足條件

而檢錯能力與偶監(jiān)督碼相同。奇偶監(jiān)督碼的編碼效率為R=（n-1）/n，奇偶校驗碼的編碼率是最高的。

二維奇偶監(jiān)督碼把上述奇偶監(jiān)督碼的若干碼組排列成矩陣，每一碼組寫成一行，然后再按列的方向增加第二維監(jiān)督位，設a01a02××××××a0m為m行奇偶監(jiān)督位；cn-1

cn-2××××××

c0為按列進行第二次編碼所增加的監(jiān)督位，它們構成了一監(jiān)督位行。由此組成的二維奇偶監(jiān)督碼陣如下：

二、二維奇偶監(jiān)督碼an-11

an-11…a11a01an-12

an-12…a12a02…an-1man-1m…

a1ma0mcn-1

cn-2…

c1c0

這種碼有可能檢測偶數個錯誤。因為每行的監(jiān)督位雖然不能用于檢測本行中的偶數個錯誤，但按列的方向有可能由cn-1、cn-2××××××、c0等監(jiān)督位檢測出來。有一些偶數錯碼不可能檢測出，例如，構成矩形的四個錯碼就檢測不出來,比如陣列中的an-22,a12,an-2m,a1m。這種二維奇偶監(jiān)督碼適于檢測突發(fā)錯誤。前述的一維奇偶監(jiān)督碼一般只適于檢測隨機錯誤。二維奇偶監(jiān)督碼不僅可用來檢錯，還可以用于糾錯。例如，當碼組中僅在一行中有奇數個錯誤時，則能夠確定錯碼的位置，從而糾正它。an-11

an-11…a11a01an-12

an-12…a12a02…an-1man-1m…

a1ma0mcn-1

cn-2…

c1c0三、恒比碼

碼字中1的數目與0的數目保持恒定比例的碼稱為恒比碼。由于恒比碼中，每個碼組均含有相同數目的1和0，因此恒比碼又稱等重碼，定1碼。這種碼在檢測時，通過計算接收碼元中1的數目是否正確，就知道有無錯誤。

目前我國電傳通信中普遍采用3：2碼，又稱“5中取3”的恒比碼，即每個碼組長度為5，其中3個“1”。這時可能編成的不同碼組數目等于從5中取3的組合數10，這10個許用碼組恰好可表示10個阿拉伯數字，如表7-1所示。而每個漢字又是以四位十進制數來代表的。實踐證明，采用這種碼后，我國漢字電報的差錯率大為降低。目前國際上通用的ARQ電報通信系統(tǒng)中，采用3：4碼，即“7中取3”的恒比碼。100119011108111007101016001115110104101103110012010111011010碼字數字表9-13：2恆比碼第三節(jié)線性分組碼一、基本概念

線性分組碼在所有可能的分組碼（BlockCode）中只占很少的一部分，然而，它卻幾乎是惟一具有實際價值的分組碼。線性分組碼是所有糾錯編碼中最基本最容易研究的一類碼，它概念清楚，易于理解，而且能方便地反映出各類編碼中廣為使用的一些基本參數和名稱，因此，線性分組碼就成了討論其他各類碼的基礎。在（n，k）分組碼中，若每一個監(jiān)督元都是碼組中某些信息元按模2和得到的，即監(jiān)督元是信息元按線性關系相加而得到的，則稱線性分組碼。或者說，可用線性方程組表述碼規(guī)律性的分組碼稱為線性分組碼。線性分組碼是一類重要的糾錯碼，應用很廣泛。對于偶監(jiān)督碼，使用了一位監(jiān)督位a0，設碼字A=〔an-1，an-2，a1，a0〕，有

在接收端解碼時，實際上就是計算上式S的結果，若結果為1，則認為有錯，結果為0，則認為無錯。式中，S稱為校正子，取值只有兩種，故只能代表有錯和無錯兩種信息，若增加一位監(jiān)督位，則能增加一個類似于上式的監(jiān)督關系式。則有兩個校正子，它們有4中可能值組合，故能表示4種不同信息，則除了表示有無錯信息外，還能有其余可能值來表示錯誤的位置信息。同理，r個監(jiān)督位能只是一位錯碼的2r-1個可能位置。

現以（7，4）分組碼為例來說明線性分組碼的特點。設其碼字為A=〔a6

a5

a4

a3

a2

a1

a0〕，其中前4位是信息元，后3位是監(jiān)督元，可用下列線性方程組來描述該分組碼，產生監(jiān)督元。

顯然，這3個方程是線性無關的。經計算可得（7，4）碼的全部碼字，如表9—2所示。（9-7）11111111500001117100111014011011060101101131010101500111001211001004001101111110001130101010101010010210010019011000111111000800000000監(jiān)督元信息元監(jiān)督元信息元碼字序號碼字序號表9—2（7，4）碼的碼字表不難看出，上述（7，4）線性分組碼的最小碼距d0=3，它能糾正一個錯誤或檢測兩個錯誤。二、監(jiān)督矩陣Ｈ和生成矩陣Ｇ式（9-7）所述（7，4）碼的3個監(jiān)督方程式可以改寫為這組線性方程可用矩陣形式表示為并簡記為其中，AＴ是A的轉置，０Ｔ是O=〔000〕的轉置，ＨＴ是H的轉置。（9-11）

H稱為監(jiān)督矩陣，一旦H給定，信息位和監(jiān)督位之間的關系也就確定了，H為r×n階矩陣，H矩陣每行之間是彼此線性無關的。式（9-11）所示的H矩陣可分成兩部分。（9-10）HAT＝０T或AHＴ＝０（9-12）其中，P為r×k階矩陣，Ir為r×r階單位矩陣，可以寫成H=〔PIr〕形式的監(jiān)督矩陣稱為典型監(jiān)督矩陣。HAT=OT說明H矩陣與碼字的轉置乘積必為零，可以采用來作為判斷接收碼字A是否出錯的依據。=〔PIr〕

若把（9-7）補充為下列方程（9-13）并改寫為矩陣形式（9-14）即（9-15）兩邊求轉置，得其中（9-16）稱為生成矩陣，由G和信息碼組就可以產生全部碼字。G為k×r階矩陣，各行也是線性無關的。生成矩陣也可以分兩部分，即(9-17)其中（9-18）Q為k×r階矩陣，Ik

為k階單位陣，可以寫成式（9-17）形式的G

矩陣，稱為典型生成矩陣。非典型形式的生成矩陣經過簡單的行運算也一定可以化為典型生成矩陣形式。G=[IkQ]

三、伴隨式（校正子）S

設發(fā)送碼組，在傳輸過程中可能發(fā)生誤碼。接收碼組B=[bn-1，bn-2…b1，b0]，則收發(fā)碼組之差定義為錯誤圖樣E，也稱為誤差矢量，即

E=B-A

（9-19）其中，且（9-20）式（9-19）也可寫作B=A+E

（9-21）令S=BHT，S稱為伴隨式或校正子，利用AHT=0，得

（9-22）

由此可見，伴隨式S與錯誤圖樣E之間有確定的線性變換關系。接收端譯碼器的任務就是從伴隨式確定錯誤圖樣，然后從接收到的碼字中減去錯誤圖樣。上述（7，4）線性分組碼的伴隨式與錯誤圖樣的對應關系如表9-3所示。S=BHT=（A+E）HT=EHT

00000101010001110111011100000000000001000001000001000001000001000001000001000000/b0b1b2b3b4b5b601234567s2

s1

s0e6

e5

e4

e3e2e1

e0SE錯誤碼位序號表9-3（7，4）碼S與E的對應關系從表9-3中可以看出，伴隨式S的2r形式分別代表A碼無錯和2r

-1種有錯的圖樣。

漢明碼是漢明（Hamming）于1949年提出的能夠糾正單個隨機錯誤的線性分組碼。它有如下參數：碼長：n=2r-1信息位：k=2r-1-r監(jiān)督位：n-k=r,r是不小于3的任意正整數。最小距離：d0=3上述的（7，4）線性分組碼就是一個漢明碼。漢明碼的碼率為R=k/n=(n-r)/n=1-r/n(9-23）若碼長n很長，則R接近1，所以漢明碼是一類高效碼。

第四節(jié)循環(huán)碼

循環(huán)碼（CyclicCode）是一類重要的線性分組碼，它除了具有線性碼的一般性質外，還具有循環(huán)性，即循環(huán)碼許用碼組集合中任一碼字循環(huán)移位所得的碼字仍為該碼組集合中的一個碼字。循環(huán)碼的兩個最引人注目的特點是：可以用反饋線性移位寄存器很容易地實現其編碼和伴隨式計算由于循環(huán)碼有許多固有的代數結構，從而可以找到各種簡單實用的譯碼方法。

目前發(fā)現的許多線性分組碼都與循環(huán)碼密切相關。由于循環(huán)碼具有眾多的良好性質，所以它在理論和實用中都是十分重要的。表9-4中給出一種（7，3）循環(huán)碼全部碼字。在代數理論中，為了便于計算，常用碼多項式表示碼字。（n，k）循環(huán)碼的碼字，其碼多項式（以降冪順序排列）為(9-24)如表9-4中第4號碼字可用多項式

表示。

0000000001110101001110111010100111010100111101001111010001234567

碼字序號表9-4（7，3)循環(huán)碼T(x)=an-1xn-1+an-2xn-2+???+a1x+a0

T4(x)=x6+x3+x2+x

T7(x)=x6+x5+x2+1

第7號碼字可用多項式

表示。

一、生成多項式及生成矩陣

如果一種碼的所有碼多項式都是多項式g(x)的倍式，則稱g(x)為該碼的生成多項式。在(n，k)循環(huán)碼中，任意碼多項式A(x)都是最低次碼多項式的倍式。如表9-4的（7，3）循環(huán)碼中，（9-25）其它碼多項式都是g(x)倍式，即

g(x)=T1(x)=x4+x3+x2+1

T0(x)=0·g(x)T2(x)=(x+1)·g(x)T3(x)=x·g(x)…T7(x)=x2·g(x)0000000001110101001110111010100111010100111101001111010001234567

碼字序號因此，循環(huán)碼中次數最低的多項式（全0碼字除外）就是生成多項式g(x)。可以證明，g(x)是常數項為1的r=n-k次多項式，是

xn+1

的因式。循環(huán)碼的生成矩陣常用多項式的形式來表示，即其中

（9-26）(9-27)g(x)=xr+gr-1xr-1+…g1x+1

例如（7，3）循環(huán)碼，n=7，k=3，r=4，其生成多項式及生成矩陣分別為即

g(x)=T1(x)=x4+x3+x2+1二、監(jiān)督多項式及監(jiān)督矩陣為了便于對循環(huán)編譯碼，通常還定義監(jiān)督多項式，令其中，g(x)是常數項為1的r次多項式，即生成多項式；h(x)是常數項為1的k次多項式，稱為監(jiān)督多項式。同理可得監(jiān)督矩陣H（9-29）（9-28）其中稱為h(x)的逆多項式。

（9-30）例如（7，3）循環(huán)碼，

則g(x)=x4+x3+x2+1

三、編碼方法和電路

在編碼時，首先要根據給定的(n，k)值選定生成多項g(x)，即應在xn+1的因式中選一個r=n-k次多項式作為g(x)。設編碼前的信息多項式m(x)為（9-31）

m(x)的最高冪次為k-1。循環(huán)碼中的所有碼多項式都可被g(x)整除，根據這條原則，就可以對給定的信息進行編碼。用xr（即xn-k）乘m(x)，得到xr·m(x)的次數小于n。用g(x)去除

xr·m(x)

，得到余式R(x)，R(x)的次數必小于g(x)的次數，即小于(n-k)。將此余式加于信息位之后作為監(jiān)督位，即將R(x)與xr.m(x)相加，得到的多項式必為一碼多項式，因為它必能被g(x)整除，且商的次數不大于(k-1)。m(x)=a1+a2x+a3x2+…+akxk-1

因此循環(huán)碼的碼多項式可表示為（9-32）其中xr·m(x)

代表信息位，

R(x)是xr·m(x)與g(x)相除得到的余式，代表監(jiān)督位。編碼電路的主體是生成多項式構成的除法電路，再加上適當的控制電路組成。g(x)=x4+x3+x2+1時，（7，3）循環(huán)碼的編碼電路如圖9-2所示。

圖9-2（7，3）循環(huán)碼的編碼電路T(x)=xr·m(x)+R(x)

g(x)的次數等于移位寄存器的級數；g(x)的x0、x1、x2、…、xr

的非零系數對應移位寄存的反饋抽頭。首先，移位寄存器清零，3位信息元輸入時，門1斷開，門2接通，直接輸出信息元。第3次移位脈沖到來時將除法電路運算所得的余數存入移位寄存器。第4－7次移位時，門2斷開，門1接通，輸出監(jiān)督元。具體編碼過程如表9-5所示，此時輸入信息元110。10010100001000010000斷開接通00004567/11000010111011001接通斷開/1100123輸出移位寄存器D0D1D2D3門2門1輸入移位次序表9-5（7，3）循環(huán)碼的編碼過程四、譯碼方法和電路

接收端譯碼的目的是檢錯和糾錯。由于任一碼多項式T(x)都應能被生成多項式g(x)整除，所以在收端可以將接收碼組R(x)用生成多項式去除。當傳輸中未發(fā)生錯誤時，接收碼組和發(fā)送碼組相同，即T(x)=R(x)，故接收碼組R(x)必定能被g(x)整除。若碼組在傳輸中發(fā)生錯誤，則R(x)≠T(x)，R(x)除以g(x)時除不盡而有余項，所以，可以用余項是否為零來判別碼組中有無誤碼。在接收端為糾錯而采用的譯碼方法自然比檢錯時復雜。同樣，為了能夠糾錯，要求每個可糾正的錯誤圖樣必須與一個特定余式有一一對應關系。圖9-3為（7，3）循環(huán)碼的譯碼電路。圖9-3（7，3）循環(huán)碼譯碼電路解碼器的核心是一個除法電路和緩沖移位寄存器，這里的除法電路與發(fā)送端編碼器中的除法電路相同。譯碼電路的具體糾錯過程這里不再詳述。五、CRC碼

CRC是英文名稱CyclicRedundancyCheck的縮寫，意為循環(huán)冗余校驗。前面的分析已經表明，循環(huán)碼的檢錯能力是很強的，而CRC碼便是一種廣泛用于檢錯的循環(huán)碼。CCITT所推薦的，并在高速數據鏈路控制規(guī)程（HDLC）及X.25協(xié)議中所采用的CRC碼是一種（n,n-16）的循環(huán)碼。它的最小距離為4，生成多項式為此碼能檢測長度不大于16的所有突發(fā)錯誤，所有奇數個和2個獨立錯誤以及其它大量錯誤圖樣。這種碼的編碼電路和檢錯電路也都很簡單。g(x)=x16+x12+x5+1

循環(huán)冗余校驗碼（CRC碼）在移動通信中也獲得了廣泛的應用，例如在美國D-AMPS和日本PDC數字蜂窩移動通信系統(tǒng)中，對于數字話音和控制信號的無線傳輸所采用的誤差保護技術之一就應用了CRC碼。

例如在日本的PDC系統(tǒng)中，就采用了如下幾種CRC碼：1）對數字話音振中44個最敏感的有效比特進行7位CRC計算。此CRC生成多項式為2）8位CRC碼，其生成多項式為3）CCITT建議的16位CRC碼。上述第②和第③項的CRC碼用于控制信好的檢錯。g(x)=x7+x6+x5+x4+1g(x)=x8+x7+x4+x3+x+1

FEC系統(tǒng)中除了應用分組碼（BlockCode）外，還廣泛使用卷積碼（ConvolutionalCode）。在同等碼率和相似的糾錯能力下，卷積碼的實現往往比分組碼要簡單，因此在FEC系統(tǒng)中，將越來越多地應用卷積碼。一、基本概念

卷積碼又稱連環(huán)碼，是1955年提出來的一種糾錯碼，它和分組碼有明顯的區(qū)別。（n，k）線性分組碼中，本組r=n–k個監(jiān)督元僅與本組k個信息元有關，與其它各組無關，也就是說分組碼編碼器本身并無記憶性。卷積碼則不同，每個(n，k)碼段（也稱子碼，通常較短）內的n個碼元不僅與該碼段內的信息元有關，而且與前面m段的信息無限元有關。通常稱m為編碼存儲。卷積碼常用符號(n，k，m)表示。第五節(jié)卷積碼圖9-4是（2，1，2）卷積碼的編碼器。它由移位寄存器、模二加法器及開關電路組成。圖9-4卷積碼（2，1，2）編碼器

起始狀態(tài)，各級移位寄存器清零，即S1S2S3為000。S1等于當前輸入數據，而移位寄存器狀態(tài)S2S3存儲以前的數據，輸出碼字C由下式確定（9-33）

當輸入數據D=[11010]時，輸出碼字可以計算出來，具體計算過程如表9-6所示，另外，為了保證全部數據通過寄存器，還必須在數據位后加3個0。

從上述的計算可知，每1位數據，影響（m+1）個輸出子碼，稱（m+1）為編碼約束度。每個子碼有n個碼元，在卷積碼中有約束關系的最大碼長度則為（m+1）n，稱為編碼約束長度。（2，1，2）卷積碼的編碼約束度為3，約束長度為6。aacbcdba狀態(tài)0000111000010111C1C20000100110110100S3S200001011S1表9-6（2，1，2）編碼器的工作過程二、卷積碼的描述

卷積碼同樣也可以用矩陣的方法描述，但較抽象。因此，我們采用圖解的方法直觀描述其編碼過程。常用的圖解法有3種方法：樹圖、狀態(tài)圖和格圖。1．樹圖

樹圖描述的是在任何數據序列輸入時，碼字所有可能的輸出。對應于圖9-4所示的（2，1，2）卷積碼的編碼電路，可以畫出其樹圖如圖9-5所示。圖9-5（2，1，2）碼的樹圖以S1S2S3為000作為起點，用a、b、c和d表示出S3S2的4種可能狀態(tài)：00、01、10和11。若第一位數據S1=0，輸出C1C2=00，從起點通過上支路到達狀態(tài)a，即S3S2=00；若S1=1，輸出C1C2=11，從起點通過下支路到達狀態(tài)b，即S3S2=01；依次類推，可得整個樹圖。輸入不同的信息序列，編碼器就走不同的路徑，輸出不同的碼序列。例如當輸入數據為[11010]時，其路徑如圖9-5中虛線所示，并得到輸出碼序列為[11010100…]，與表9-6的結果一致。2．狀態(tài)圖

除了用樹圖表示編碼器的工作過程外，還可以用狀態(tài)圖來描述。圖9-6就是該（2，1，2）卷積碼編碼器的狀態(tài)圖。在圖中有4個節(jié)點a、b、c、d，同樣分別表示S3S2的4種可能狀態(tài)。每個節(jié)點有兩條線離開該節(jié)點，實線表示輸入數據為0，虛線表示輸入數據為1，線旁的數字即為輸出碼字。圖9-6（2，1，2）卷積碼的狀態(tài)圖3．格圖

格圖也稱網絡或籬笆圖，它由狀態(tài)圖在時間上展開而得到，如圖9-7所示。圖中畫出所有可能數據輸入時，狀態(tài)轉移的全部可能軌跡，實線表示數據為0，虛線表示數據為1，線旁數字為輸出碼字，節(jié)點表示狀態(tài)。

以上的3種卷積碼的描述方法，不但有助于求解輸出碼字，了解編碼工作過程，而且對研究解碼方法也很有用。圖9-7（2，1，2）卷積碼的格圖三、卷積碼的譯碼

卷積碼的譯碼可分為代數譯碼和概率譯碼兩大類。代數譯碼是利用生成矩陣和監(jiān)督矩陣來譯碼，最主要的方法是大數邏輯譯碼。概率譯碼比較實用的有兩種：維特比譯碼和序列譯碼。目前，概率譯碼已成為卷積碼最主要的譯碼方法。本節(jié)我們將簡要討論維特比譯碼和序列譯碼。1．維特比譯碼

維特比譯碼，它是一種最大似然譯碼算法。最大似然譯碼算法的基本思路是，把接收碼字與所有可能的碼字比較，選擇一種碼距最小的碼字作為解碼輸出。由于接收序列通常很長，所以維特比譯碼對最大似然譯碼做了簡化，即它把接收碼字分段累接處理，每接收一段碼字，計算、比較一次，保留碼距最小的路徑，直至譯完整個序列?，F以上述（2，1，2）卷積碼為例說明維特比譯碼過程。設發(fā)端的信息數據D=[11010000]，由編碼器輸出的碼字C=[1101010010110000]，收端接收的碼序列B=[0101011010010010]，有4位碼元（帶下劃線）差錯。下面參照圖9-7的格狀圖說明譯碼過程。

如圖9-8所示，先選前3個碼作為標準，對到達第3級的4個節(jié)點的8條路徑進行比較，逐步算出每條路徑與接收碼字之間的累計碼距。累計碼距分別用括號內的數字標出，對照后保留一條到達該節(jié)點的碼距較小的路徑作為幸存路徑。再將當前節(jié)點移到第4條級，計算、比較、保留幸存路徑，直至最后得到到達終點的一條幸存路徑，即為解碼路徑，如圖9-8中實線所示。根據該路徑，得到解碼結果。圖9-8維特比譯碼格圖序列譯碼

當卷積碼參量m很大時，可以采用序列譯碼法。其過程如下：譯碼先從碼樹的起始節(jié)點開始，把接收到的第一個子碼的n個碼元與自始節(jié)點出發(fā)的兩條分支按照最小漢明距離進行比較，沿著差異最小的分支走向第二個節(jié)點。在第二個節(jié)點上，譯碼器仍以同樣原理到達下一個節(jié)點，以此類推，最后得到一條路徑。若接收碼組有錯，則自某節(jié)點開始，譯碼器就一直在不正確的路徑中行進，譯碼也一直錯誤。因此，譯碼有一個門限，當接收碼元與譯碼器所走的路徑上的碼元之間的差異總數超過門限值時，譯碼器判定有錯，并且返回試走另一分支。經數次返回找出一條正確的路徑，最后譯碼輸出。當該門限值很小時，序列譯碼的性能接近最大似然譯碼，盡管譯碼時每一次搜索的計算量和所需存儲容量不大，但是其頻繁的返回則要求更大的計算量