第9章差錯控制編碼9.1差錯控制編碼的基本概念9.2糾錯碼的基本原理9.3奇偶校驗碼9.4線性分組碼9.5校正子S與糾錯(譯碼)電路9.6循環(huán)碼9.7卷積碼簡介

9.1差錯控制編碼的基本概念

信源編碼、調(diào)制與解調(diào)和信道編碼(又稱差錯控制編碼或糾錯碼)已成為現(xiàn)代通信的三大技術(shù)。本書前八章的內(nèi)容較系統(tǒng)地介紹了信源編碼(如PCM編碼、增量調(diào)制編碼)、調(diào)制技術(shù)(如ASK、FSK和PSK等)以及通信的基本原理與知識。在本章中，我們將要介紹現(xiàn)代通信中的信道編碼技術(shù)。信源編碼與信道編碼之間的關(guān)系比較如下：

信源編碼：去掉信源的冗余度，用以提高有效性；

信道編碼：按一定規(guī)則加入冗余度(稱監(jiān)督碼元)，用以提高可靠性。在現(xiàn)代通信技術(shù)中，有效性和可靠性是兩個最為重要的指標(biāo)，它們之間相互矛盾，兩者不可兼得。因此，人們需要依據(jù)香農(nóng)信息論和編碼理論，設(shè)計出較優(yōu)化的通信系統(tǒng)，以滿足有效性和可靠性的要求。

在提高可靠性方面，傳統(tǒng)的方法是通過加大發(fā)射功率來提高信噪比或降低誤碼率。然而，這種方法是非常有限的，主要原因是現(xiàn)代通信系統(tǒng)既是頻帶受限又是功率受限的，尤其是現(xiàn)代移動通信系統(tǒng)。因此，單靠通過加大發(fā)射功率來提高通信的接收質(zhì)量辦法是不能解決根本問題的，人們必須尋找新的方法，信道編碼正是在這種技術(shù)背景下提出來的，它起源于20世紀(jì)50年代，到70年代趨于成熟。差錯控制編碼的基本原理是，在發(fā)送端被傳輸?shù)男糯a序列上附加一些監(jiān)督碼元，與信息碼元之間以某種確定的規(guī)則相互關(guān)聯(lián)(約束)。接收端則按照約定的規(guī)則，檢驗信息碼元與監(jiān)督碼元之間的關(guān)系，一旦傳輸過程中發(fā)生差錯就可以發(fā)現(xiàn)錯誤，并可糾正錯誤。最常用的差錯控制方式主要有：

(1)檢錯重發(fā)(簡稱ARQ)，發(fā)送端發(fā)出經(jīng)過差錯控制編碼的碼組，接收端如果檢測出收到的信碼中有誤碼，則通過反向信道通知發(fā)送端重發(fā)，直到正確接收為止。

(2)前向糾錯(簡稱FEC)，在發(fā)送端發(fā)送經(jīng)過差錯控制編碼的碼組，接收端能夠發(fā)現(xiàn)并糾正錯碼。不需要反向信道，延時小、實時性好，但電路要復(fù)雜一些。

(3)混合糾錯(簡稱HEC)，是前向糾錯和檢錯重發(fā)方式的結(jié)合。接收端不但有糾正錯誤的能力，對超出糾錯能力的誤碼也有檢測能力，在實時性和譯碼復(fù)雜性方面是前向糾錯和檢錯重發(fā)方式的折中。差錯控制編碼分類主要有：

①根據(jù)差錯控制碼的功能分類，可分為檢錯碼、糾錯碼和糾刪碼；

②根據(jù)信息碼元和監(jiān)督碼元之間的檢驗關(guān)系分類，可分為線性碼和非線性碼；

③根據(jù)信息碼元和監(jiān)督碼元之間的約束方式分類，可分為分組碼、循環(huán)碼和卷積碼；

④根據(jù)信息碼編碼后是否保持原有形式分類，可分為系統(tǒng)碼和非系統(tǒng)碼；

⑤根據(jù)糾錯的類型分類，可分為糾正隨機錯的碼和糾正突發(fā)錯的碼；

⑥根據(jù)糾錯碼的數(shù)學(xué)構(gòu)造分類，可分為代數(shù)碼、幾何碼和算術(shù)碼。

本章介紹其中的一部分內(nèi)容，主要包括線性分組碼、循環(huán)碼和卷積碼等。

9.2糾錯碼的基本原理

本節(jié)首先介紹糾錯編碼的基本原理。先舉例簡要說明其基本原理：三位二進制碼元共有8種可能的組合，假設(shè)這8種碼組都可傳遞消息(均為可用碼組)。若在傳輸過程中，其中的任一碼組發(fā)生一個或多個錯誤，則將會變成另一種碼組。由于每一種碼組都可能出現(xiàn)，沒有多余的信息量，接收端不可能發(fā)現(xiàn)錯誤。若只選其中000、011、101、110這4種碼組來傳送消息，另外的4種碼組在編碼后的發(fā)送碼元中是不可能出現(xiàn)的，稱為禁用碼組。接收端一旦發(fā)現(xiàn)這些禁用碼組，表明傳輸過程中發(fā)生了錯誤，這就是糾錯碼最基本的原理。在上例中，只需用兩位碼組就能夠傳輸4種不同的符號，多增加的那位為監(jiān)督位。這種將信息碼分組并為每組信碼附加若干監(jiān)督碼的編碼，稱為分組碼。分組碼一般用(n，k)表示，n是碼組長度，k是信息碼元的數(shù)量，r=n－k是監(jiān)督碼元的數(shù)量。

我們定義碼組中非零碼元的數(shù)目為碼組的重量，即碼重，定義兩個碼組中對應(yīng)碼位上具有不同二進制碼元的個數(shù)為碼組的距離，即碼距，又稱漢明(Hamming)距離。把一種編碼中各個碼距的最小值，稱為最小碼距d0?？梢杂靡粋€三維立方體來說明上述三位碼組碼距的幾何意義，如圖9-1所示。圖中各頂點分別表示8個碼組，各頂點的坐標(biāo)(a2，a1，a0)表示每一碼組的三個碼元值，而碼距對應(yīng)于從一個頂點沿立方體各邊移到另一個頂點所經(jīng)過的最少邊數(shù)。圖9-1碼距的幾何圖示概括起來，分組碼的基本原理是，把信息碼按k個碼元為一組，并按一定的規(guī)律編碼，產(chǎn)生r個監(jiān)督碼元，形成長度為n=k+r的組碼，稱為碼字，用(n，k)表示，其特點是：

(1)共有2k個不同的碼字，稱為許用碼組；

(2)共有2n－2k個碼字未用，稱為禁用碼組。

正是存在禁用碼組，使得(n，k)碼具有糾錯能力，一般來說，禁用碼越多，漢明距離d0越大，糾錯能力就越強。設(shè)有兩個碼組(碼字)A和B，其距離定義為d(A，B)=∑an

bn,即若兩個碼字A、B之間有m個碼元不同，則其距離為d(A，B)=m。例如：得

對于有多個碼字的情況，碼字之間的最小距離定義為漢明距離，如

一個碼的檢錯與糾錯能力與漢明距離有關(guān)，d0越大，能力越強，可以證明，有如下結(jié)論：

(1)檢測e個隨機錯誤，則要求d0≥e+1；

(2)糾t個隨機錯誤，則要求d0≥2t+1；

(3)糾t個，同時檢測e個(e>t)隨機錯誤，則要求d0≥t+e+1。

與糾錯編碼相對應(yīng)的另一個問題是編碼效率，其定義為R=k/n。

【例9.1】用二進碼表示“晴”和“雨”。試分析用1位、2位和3位時的檢錯及糾錯情況。

解

(1)用1位編碼時，只有信息碼，沒有監(jiān)督碼，該碼為(n，k)=(1，1)，即由于沒有禁用碼組，故出錯時，無法糾正。原因是0→1，或1→0，出錯后的碼組仍為許用碼組，因此沒有監(jiān)督碼時，無任何糾檢錯能力。

(2)加上一位重復(fù)碼(監(jiān)督碼)后，碼字為(n，k)=(2，1)，2位編碼共有4種：a1a0=00，01，10，11。許用碼組的漢明距離d0=2。在傳輸過程中，產(chǎn)生了錯誤，收到的碼組變?yōu)?0，1)或(1，0)，由于它們不屬于許用碼組范圍，故在接收端，可檢出這個錯誤，即可檢出一個隨機錯誤。

(3)加上兩位監(jiān)督碼元,碼字(n,k)=(3,1),全部碼字為

a2a1a0=000，001，010，011，100，101，110，111

許用碼組共2個:許用碼組的漢明距離為d0=3，禁用碼字共6個

a2a1a0=001，010，011，100，101，110能糾一位錯，如圖9-2所示。圖9-2三位編碼的糾錯能力

最后介紹有關(guān)差錯的兩種主要類型。

(1)隨機差錯。主要由加性高斯噪聲等引起，特點是一般只錯一位的可能最大，但哪位出錯則是隨機的，經(jīng)計算得：

錯一位的概率為：Pe(1)=7×10－3

錯二位的概率為：Pe(2)=2.1×10－5

錯三位的概率為：Pe(3)=3.5×10－8

由上述結(jié)果可見，出一位錯的可能性最大。

(2)突發(fā)差錯。連續(xù)的一串碼元出現(xiàn)錯誤，出錯的長度稱為突發(fā)長度。例如，強脈沖信號的干擾會使接收到的信號出現(xiàn)突發(fā)差錯，此外，磁盤上磁粉失落或光盤被劃傷后，也會出現(xiàn)突發(fā)差錯等。

9.3奇偶校驗碼

9.3.1二進制按位運算規(guī)則

對于二進制的按位運算來說，加法，減法，異或三種運算的結(jié)果相同，即(9-1)即“+”、“－”、“”這三種運算可視為相同。(9-1)式是線性分組碼和循環(huán)碼運算的基礎(chǔ)。9.3.2奇偶校驗碼

奇偶校驗(監(jiān)督)碼的碼字為(9-2)可知它是(n，n－1)碼。其中偶校驗碼的編碼規(guī)則為滿足碼字中1的個數(shù)為偶數(shù)，而奇校驗碼的編碼規(guī)則為滿足碼字中1的個數(shù)為奇數(shù)，現(xiàn)以偶校驗為例來進行分析。對于偶校驗碼(9-3)得監(jiān)督碼元a0與信息碼an－1，an－2，…，a1之間的關(guān)系為(9-4)

(9-4)式即為偶校驗碼的編碼規(guī)則。在發(fā)送端，按照(9-4)式來編碼，編碼后的碼字通過信道傳輸。在接收端，按照同一規(guī)則來對接收的碼進行校驗，檢查它在傳輸過程中是否有錯。因此，根據(jù)(9-4)式，可得偶校驗碼的編碼和校驗電路如圖9-3所示。

根據(jù)圖9-3，在接收端，首先對接收下來的信號進行校驗，檢驗它是否有錯，校驗規(guī)則仍如(9-3)式。若檢驗結(jié)果滿足(9-3)式，表明傳輸過程無錯，若不滿足(9-3)式，則判為有錯。根據(jù)圖9-3，上述結(jié)果可用校正子S來表示，即(9-5)圖9-3偶校驗碼的編碼和校驗電路利用校正子S作為應(yīng)答信號來通知發(fā)送端：若S=0，表明無錯，若S=0，表明有錯。發(fā)送端則可根據(jù)校正子S的結(jié)果來決定是否需要重發(fā)，即若S=0，表明無錯，不需要重，若S=1，表明有錯，需要重發(fā)。9.3.3奇偶校驗碼小結(jié)

奇偶校驗碼的主要特點是：

(1)奇偶校驗碼可檢測奇數(shù)個錯誤，但無法檢測偶數(shù)個數(shù)錯誤；

(2)由于只有一個監(jiān)督碼和一個校正子S，它只能用于檢錯，不能糾錯。

(3)只能用于檢錯重發(fā)方式。

奇偶校驗碼與下節(jié)將要介紹的線性分組碼的關(guān)系與區(qū)別如下：

(1)奇偶校驗只有一個線性方程，對應(yīng)一個監(jiān)督碼元和一個校正子，而線性分組碼則有多個線性方程(稱之為方程組)，對應(yīng)多個監(jiān)督碼元和多個校正子。

(2)由于奇偶校驗只有一個監(jiān)督碼元和一個校正子，故只能檢錯，不能糾錯，而線性分組碼則有多個監(jiān)督碼元和多個校正子，既可檢錯，又可糾錯。

(3)奇偶校驗與線性分組碼在編碼和譯碼(或檢驗)兩方面有某些相似或類比之處。

9.4線性分組碼

9.4.1(7，4)線性分組碼

本小節(jié)以一種典型的(7,4)碼為例，介紹線性分組碼的一些性質(zhì)與特點。線性碼是代數(shù)碼中較為常見的碼。線性分組碼是分組碼中最重要的一類碼，是討論各類糾錯碼的基礎(chǔ)。它的信息碼和監(jiān)督碼元由線性方程組聯(lián)系起來。它具有封閉性，即任意兩許用碼組按位運算所得到的碼仍為一許用碼組，因而碼的最小距離等于碼的最小重量(全0碼除外)。一個(n，k)線性分組碼，將信息劃分成k個碼元為一段(信息組)，通過編碼器變成長為n個碼元的一個碼組。在二進制情況下，k位碼元共有2k個許用碼組。線性分組碼的編碼問題就是要建立一組線性方程組，即已知k個數(shù)，要求n－k個未知數(shù)。例如(7，4)碼，若a6，a5，a4，a3代表4個信息碼元，a2，a1，a0為三個監(jiān)督碼元，組成(7，4)碼的碼字為(9-6)三個監(jiān)督碼元可由以下線性方程組求得(9-7)其許用碼字為24=16個，禁用碼字為27－24=112個。許用碼字如表9-1所示。

根據(jù)表9-1以及封閉性，這種(7，4)分組碼的許用碼中，除全0碼外，得最小碼重為3，因此漢明距離為d0=3。糾錯能力d0≥2t+1≥t=1，故能糾1位錯。

表9-1線性分組碼的許用碼字9.4.2監(jiān)督矩陣H和生成矩陣G

1．監(jiān)督矩陣H及其物理意義

根據(jù)(9-7)式，可求得其監(jiān)督矩陣H，具體推導(dǎo)過程如下：(9-8)式中A=［a6a5a4a3a2a1a0］為碼字，H為監(jiān)督矩陣，并且是標(biāo)準(zhǔn)監(jiān)督矩陣，具體表達式為(9-9)

監(jiān)督矩陣H的物理意義如下：

(1)在發(fā)送端，可利用監(jiān)督H來進行編碼，因此H

實際上是一種編碼規(guī)則。利用這種編碼規(guī)則，使得H和碼字A滿足AHT=0或HAT=0。

(2)在接收端，可利用H

對經(jīng)信道傳送過來的碼字A進行監(jiān)督或檢測，判斷其正確性。若正確，必滿足AHT=0(或HAT=0)；若不正確，則AHT不為0(或HAT不為0)。

(3)下文中的校正子正是根據(jù)這一原理來判斷接收碼字是否有錯并進行糾錯。

2．生成矩陣G及其物理意義

前面的(9-7)式還可表示為如下形式(9-10)進一步得(9-11)生成矩陣G的物理意義是，由生成矩陣G和信息碼［a6a5a4a3］可生成一個碼字A，故稱之為生成矩陣，(9-11)式很清楚地說明了這一結(jié)果。

3．生成矩陣G和監(jiān)督矩陣H的關(guān)系

由于監(jiān)督矩陣H生成矩陣G均由(9-7)式推導(dǎo)得來，因此，它們之間必存在某種確定的關(guān)系，具體而言，它們可由一個推導(dǎo)出另一個。由(9-9)式得到的監(jiān)督矩陣為(9-12)由(9-10)式得到的生成矩陣為(9-13)顯然，監(jiān)督矩陣H和生成矩陣G的關(guān)系為

P=QT

或Q=PT

(9-14)由此可見，可由H求G，或由G求H。9.4.3(7，4)碼編碼電路

根據(jù)(9-7)式，得其編碼電路如圖9-4所示。

【例9.2】設(shè)(7,3)線性分組碼的監(jiān)督矩陣為試解答下列問題：

(1)監(jiān)督碼元與信息碼元之間的關(guān)系表達式。

(2)列出所有的許用碼組。圖9-4(7,3)碼的編碼電路

(3)求漢明距離，能糾幾位錯？

(4)畫出編碼器電路。

解

(1)由于H矩陣不是標(biāo)準(zhǔn)矩陣，經(jīng)初等變換后得標(biāo)準(zhǔn)矩陣為得監(jiān)督碼元與信息碼元之間的關(guān)系為

(2)全部許用碼組為

(3)根據(jù)許用碼組，得漢明距離為d0=4，能糾1位錯，并同時檢測2位錯。

(4)編碼電路如例9.2圖所示。例9.2圖

9.5校正子S與糾錯(譯碼)電路

9.5.1校正子S與糾錯原理

分析(9-7)式表示的(7,4)碼如何利用校正子S進行糾錯。

設(shè)發(fā)送碼字為A=［an－1，an－2，…，a1，a0］，由于傳輸過程中可能會發(fā)生錯誤，接收碼字變?yōu)锽=[bn－1，bn－2,…,b1，b0］，定義收發(fā)碼字之差為錯誤圖樣E，也稱為誤差矢量，即

E=B－A

或B=A+E

(9-15)

其中E=［en－1，en－2，…，e1，e0］，并且有(9-16)注意到接收端譯碼規(guī)則與發(fā)送端編碼規(guī)則應(yīng)相同。若發(fā)送端的編碼規(guī)則為

AHT=0

(9-17)

在接收端按同一規(guī)則接收信號，并考慮到發(fā)送端的編碼規(guī)則為AHT=0，得

BHT=［A+E］HT=AHT+EHT=EHT

(9-18)

在接收端，利用誤差信號E來進行校正和糾錯，因此，令接收端的S校正子為

(9-19)根據(jù)(9-19)式得校正子S與錯誤圖樣E以及收到的碼字B之間的關(guān)系為(9-20)(EHT=BHT)上式說明了以下兩點：

(1)若誤差e={e6，e5，e4，e3，e2，e1，e0}=0，則s={s2，s1，s0}=0，表明傳輸正確，不需校正。

(2)若誤差e={e6，e5，e4，e3，e2，e1，e0}≠0，則s={s2，s1，s0}≠0，表明傳輸不正確，需校正。根據(jù)(9-20)式，得錯誤碼位與校正子S輸出關(guān)系如表9-2所示?？芍猄校正子有8種形式，分別表示收到的碼字B無錯以及有23－1=7種錯誤，因此，校正子與錯誤碼位有確定關(guān)系。注意到收和發(fā)兩端按同一規(guī)則編碼和譯碼，故接收端所收到的信號B必滿足BHT=EHT。表9-2錯誤碼位與校正子S輸出之間的關(guān)系9.5.2(7，4)碼的糾錯(譯碼)電路

根據(jù)表9-2，利用3-8譯碼器和異或器，可設(shè)計(7,4)碼糾錯電路。首先，根據(jù)表9-2，選取3-8譯碼器，邏輯電路如圖9-5所示，真值表如表9-3所示。其次，利用3-8譯碼器和異或器，得(7,4)碼糾錯(譯碼)電路如圖9-6所示，它由校正子S產(chǎn)生電路、3—8譯碼器、異或糾錯電路和出錯指示電路四部分組成，注意到圖中只需對信息碼b6b5b4b3糾錯，而監(jiān)督碼元b2b1b0在接收端已不再需要，也就不必再糾錯了。最后，還應(yīng)注意到圖9-6中接收到的信號為B而不是E。在前面已提到，由于發(fā)送端和接收端的編碼和譯碼均按照同一規(guī)則進行，必滿足關(guān)系式BHT=EHT，因此，校正子S表達式為S=BHT=EHT。圖9-53—8譯碼器的邏輯電路圖

表9-33—8譯碼器的真值表圖9-6(7,4)碼糾錯(譯碼)電路

9.6循環(huán)碼

本節(jié)的主要內(nèi)容有以下幾個方面：

(1)循環(huán)碼及其基本性質(zhì)；

(2)如何用多項式來表示一個循環(huán)碼；

(3)在線性分組碼中，我們通過線性代數(shù)的方法求出了生成矩陣G和監(jiān)督矩陣H。在循環(huán)碼中，我們需要用碼多項式的方法求出循環(huán)碼的生成矩陣G和監(jiān)督矩陣H；

(4)循環(huán)碼的編碼規(guī)則與編碼方法；

(5)循環(huán)碼的編碼電路；

(6)循環(huán)碼的譯碼以及譯碼電路的組成與譯碼原理。9.6.1循環(huán)碼及其基本性質(zhì)

循環(huán)碼的基本性質(zhì)是：

(1)是線性碼。

(2)具有循環(huán)性。即碼組中的任一碼字循環(huán)移位所得碼字仍是該碼組中的一個碼字。

(3)封閉性。對任意兩個碼字的(異或)運算所得碼字仍屬于該碼組中的一個碼字。

(4)循環(huán)碼的碼字可用碼多項式表示。

現(xiàn)舉例說明用碼多項式表示循環(huán)碼。一種用生成多項式g(x)=T1(x)=

x4+x3+x2+1產(chǎn)生的(7,3)循環(huán)碼的許用碼字，如表9-4所示，若用碼多項式表示，其一般形式為

T(x)=an－1xn－1+an－2xn－2+…+a1x+a0

(9-21)

例如，表9-4中碼字4的多項式為T4(x)=x6+x3+x2+x，同理有T5(x)=x6+x4+x+1等。

表9-4用g(x)=x4+x3+x2+1產(chǎn)生(7，3)循環(huán)碼的許用碼字表9.6.2生成多項式和生成矩陣

1．生成多項式g(x)

若一種碼的所有碼字多項式都是某個多項式g(x)的倍式，則稱g(x)為該碼的生成多項式。例如在表9-4所示的(7,3)循環(huán)碼中，生成多項式為g(x)=T1(x)=x4+x3+x2+1，可以證明，所有碼字T(x)都是生成多項式g(x)=T1(x)=x4+x3+x2+1的倍式。因此，生成多項式g(x)對循環(huán)碼來說十分重要。

2．生成多項式g(x)的獲取及性質(zhì)

(1)可以證明，在循環(huán)碼中，除全0碼外，次數(shù)最低的碼多項式就是生成多項式。

(2)生成多項式g(x)是常數(shù)項為1的r次多項式，其中碼長為n=k+r，k為信息碼的位數(shù)，r為監(jiān)督碼元位數(shù)，即生成多項式具體形式為g(x)=xr+gr－1xr－1+gr－2xr－2+…+g1x+1，g(x)中的各個系數(shù)gi(i=r－1，r－2，…，1)取值為0或1。

(3)生成多項式是xn+1的一個因式。

3．生成矩陣G(x)及其與生成多項式的關(guān)系

生成矩陣G(x)與生成多項式g(x)的關(guān)系為(9-22)例如，對于前述的(7，3)循環(huán)碼，其生成多項式為g(x)=x4+x3+x2+1，則(9-23)對于(7，3)循環(huán)碼，類似于線性分組碼中的(9-11)式，可直接寫出碼多項式與生成矩陣、信息碼的關(guān)系為

T=［a6a5a4］G(9-24)需要注意的是，式中的G應(yīng)為標(biāo)準(zhǔn)生成矩陣。這一方法可推廣到(n，k)循環(huán)碼。(9-24)式說明可由信息碼和生成矩陣生成循環(huán)碼，這就是生成矩陣和生成多項式最基本的物理意義。

【例9.3】設(shè)(7，3)循環(huán)碼的生成多項式為g(x)=x4+x2+x+1，試根據(jù)(9-24)式列出所有的許用碼字。

解首先應(yīng)得出標(biāo)準(zhǔn)生成矩陣：其次，根據(jù)(9-24)式，得最后得表9-5所示的(7，3)循環(huán)碼的所有許用碼字表。

表9-5用g(x)=x4+x2+x+1

產(chǎn)生循環(huán)碼對應(yīng)的許用碼字表9.6.3監(jiān)督多項式、逆多項式和監(jiān)督矩陣

1．監(jiān)督多項式h(x)

監(jiān)督多項式h(x)的定義為(9-25)它是常數(shù)項為1的k次多項式。

2．h(x)的逆多項式h*(x)

h(x)的逆多項式h*(x)的定義為

h*(x)=xk+h1xk－1+h2xk－2+…+hk－1x+1(9-26)

只要求出了h(x)，利用h(x)的系數(shù)即可求出h*(x)。例如(7，3)循環(huán)碼，已知g(x)=x4+x3+x2+1,則(9-27)

3．監(jiān)督矩陣H(x)(9-28)例如，g(x)=x4+x3+x2+1表示的(7，3)循環(huán)碼的H(x)為(9-29)(監(jiān)督矩陣)

4．循環(huán)碼中監(jiān)督矩陣H與生成矩陣G關(guān)系

由于循環(huán)碼中監(jiān)督矩陣H與生成矩陣G均由同一循環(huán)碼導(dǎo)出，故它們之間存在某種確定的關(guān)系，例如，在(7,3)循環(huán)碼中，根據(jù)(9-24)式和(9-29)式，得(9-30)(9-31)得H和G的關(guān)系為P=QT或Q=PT。因此,只需求得其中的H(或G),可利用上述關(guān)系求得G(或H)，與線性分組碼的情況是類似的。9.6.4循環(huán)碼的編碼方法與編碼電路

1．循環(huán)碼除法電路的一般形式

設(shè)生成多項式為g(x)=xr+gr－1xr－1+gr－2xr－2+…+g1x+1，用g(x)對輸入作除法運算，得對應(yīng)的除法電路如圖9-7所示。由圖9-7易知Di(i=r－1，r－2，…，1)為位移寄存器，為異或電路。除法電路中各個部分的功能為：圖9-7用g(x)對輸入信號作除法運算的電路

【例9.4】已知g(x)=x4+x3+x2+1，試畫出對輸入信號作除法運算的電路。

解根據(jù)圖9-7所示的規(guī)則，得除法電路如例9.4圖所示。

【例9.5】已知g(x)=x4+x2+x+1，試畫出對輸入信號作除法運算的電路。

解根據(jù)圖9-7所示的規(guī)則，得除法電路如例9.5圖所示。例9.4圖例9.5圖

2．循環(huán)碼的編碼規(guī)則

以(7，3)循環(huán)碼為例，設(shè)碼字為(9-32)

編碼規(guī)則如下：

(1)根據(jù)給定的信息碼，可求得其碼多項式m(x)，其最高次數(shù)為k－1；

(2)用xr乘m(x)(相當(dāng)于左移r位)，得xr·m(x)；

(3)用g(x)除xr·m(x)，得商式Q(x)和余式R(x)，即xr·m(x)=g(x)·Q(x)+R(x);

(4)前面提及，循環(huán)碼都是生成多項式的倍式，故最后可求得循環(huán)碼的碼多項式為

T(x)=g(x)·Q(x)=xr·m(x)+R(x)(9-33)

(5)很顯然，循環(huán)碼的碼多項式T(x)能夠被g(x)除盡，這就是循環(huán)碼的編碼規(guī)則；

(6)當(dāng)接收端收到碼字T(x)后，首先用與發(fā)送端相同的g(x)除收到的碼字，若能除盡，表明沒有出錯，若不能除盡(余數(shù)不為0)，表明有錯，最后利用余數(shù)的特征對出錯的位進行糾錯。

3．編碼電路的組成與工作原理

以(7，3)碼為例說明編碼電路的組成與工作原理。若生成多項式為g(x)=x4+x2+x+1，得編碼電路如圖9-8所示。工作過程與原理如下：

(1)當(dāng)S1接位置1，S2接通時，一方面，將信息碼直接輸出，另一方面，除法電路對輸入信息碼作除法運算，余數(shù)保存在4個移位寄存器中。

(2)碼輸入完成后，除法運算也已完成，此時，S1接位置2，S2斷開，寄存器中余數(shù)跟在信息碼的后面接著輸出，完成循環(huán)碼編碼，當(dāng)四位余數(shù)全部輸出完后，寄存器的狀態(tài)也全部為0。注意，要等到四位余數(shù)全部輸出完后，才能重新輸入下一個信息碼。

(3)由上述分析知，循環(huán)碼是按編碼規(guī)則T(x)=g(x)·Q(x)=xr·m(x)+R(x)編碼的。圖9-8生成多項式為g(x)=x4+x2+x+1的(7,3)循環(huán)碼編碼電路

4．編碼電路的工作原理分析

根據(jù)(9-33)式，若輸入信息碼m=a6a5a4，用生成多項式g(x)=x4+x2+x+1除x4·m(x)，得余多項式R(x)=x4·m(x)/g(x)，余數(shù)R與信息碼m的對應(yīng)關(guān)系如表9-6所示。由此可知，表9-6與表9-5的信號是一致的。

表9-6輸入信息碼m與余數(shù)R的對應(yīng)關(guān)系根據(jù)圖9-8所示的電路，設(shè)寄存器D3D2D1D0對應(yīng)的當(dāng)前狀態(tài)為Qn4Qn3Qn2Qn1，次態(tài)為Q4n+1Q3n+1Q2n+1Q1n+1，則它們之間滿足如下狀態(tài)方程:由狀態(tài)方程，進一步得寄存器中的余數(shù)與輸入信息碼之間的邏輯關(guān)系如表9-7所示。由此可知，表9-6與表9-7的結(jié)果是一致的。表9-7寄存器中的余數(shù)與輸入信息碼之間的邏輯關(guān)系9.6.5循環(huán)碼的譯碼電路與譯碼原理

1．循環(huán)碼的譯碼電路

對應(yīng)圖9-8的譯碼電路如圖9-9所示。該電路接收到的碼多項式為T(x)，二進制形式為T=a6a5a4a3a2a1a0，對應(yīng)多項式為T(x)=a6x6+a5x5+a4x4+a3x3+a2x2+a1x1+a0x0，碼字最高位對應(yīng)a6，最低位對應(yīng)a0，按高位先到低位后到的順序輸入緩存器。整個循環(huán)碼譯碼電路由7級緩存器、除法電路、切換開關(guān)S、反饋移位寄存器及輸出和校正信號產(chǎn)生器、校正電路(即異或器)五大部分組成。實際上圖中的除法器與反饋移位寄存器可合并成一個電路，但從講解原理的角度來看，將其分成兩個部分更清楚。圖9-9生成多項式為g(x)=x4+x2+x+1的(7，3)循環(huán)碼的譯碼電路譯碼電路中各個部分的工作原理及功能如下：

(1)7級緩存器(延時器)。它起到延時的作用，能使校正信號正好對準(zhǔn)所需校正的碼元，由于有7位碼a6a5a4a3a2a1a0，故需要有7個緩存器(延時器)。

(2)譯碼器中的除法電路。它與發(fā)送端編碼器的除法電路一致，用于檢查收到的碼字是否正確，若收到碼字能被除法器除盡，余數(shù)為0，表明無錯，若除不盡，余數(shù)不為0，表明有錯，并將余數(shù)送入反饋移位寄存器。在進行多項式除法運算時需注意以下兩點：

①將收到碼字T(x)乘以xr之后，再除以g(x)。具體而言，為得到正確的余多項式，應(yīng)作運算x4T(x)/g(x)，余數(shù)最高位放在寄存器R4中，余數(shù)最低位放在寄存器R1中。②在一般情況下，余數(shù)的位數(shù)應(yīng)與寄存器的個數(shù)相等。對于圖9-9，有4個寄存器，故余數(shù)應(yīng)為4位。例如，若求得余多項式為x2+1，則對應(yīng)的余數(shù)應(yīng)為0101。

(3)切換開關(guān)S。在圖9-9中，碼字長度為7，隨著一個碼字的7個碼元全部移進緩存器后，除法電路也就完成了對這個碼字的除法運算，余數(shù)存放在4個寄存器R4、R3、R2、R1中。一旦對整個碼字的除法運算結(jié)束，開關(guān)S就接通，將余數(shù)送入反饋移位寄存器，緊接著開關(guān)S又斷開，并將除法電路中所有寄存器都清零(清零電路在圖中未畫出)，再對下一個碼字作除法運算，運算結(jié)束后，S再次接通，所有寄存器再次清零，依此重復(fù)下去。

(4)反饋移位寄存器及輸出和校正信號產(chǎn)生器。它利用除法電路送來的余數(shù)來產(chǎn)生S校正信號，主要由反饋移位寄存器、反饋移位寄存器的輸出和與門3個部分組成。反饋移位寄存器的輸出信號為Qn4Qn3Qn2Qn1，通過非門和與門產(chǎn)生校正信號

。反饋移位寄存器是核心部件，下面將對其進行詳細分析。

(5)校正電路。它由一個異或器組成。若S=1，表明所收到的對應(yīng)的碼元有錯，可利用異或器對其校正；若S=0，表明無錯，異或的結(jié)果，則保持原碼元不變。

2．反饋移位寄存器的狀態(tài)方程、狀態(tài)轉(zhuǎn)換表和狀態(tài)轉(zhuǎn)換圖

根據(jù)圖9-9，得反饋移位寄存器的狀態(tài)方程為(9-34)由(9-34)式，得反饋移位寄存器的狀態(tài)轉(zhuǎn)換表如表9-8所示。

表9-8反饋移位寄存器的狀態(tài)轉(zhuǎn)換表

根據(jù)表9-8所示的狀態(tài)轉(zhuǎn)換表，得狀態(tài)轉(zhuǎn)換圖如圖9-10所示。虛框所示部分的循環(huán)用于糾錯。當(dāng)碼元a6出錯時，對應(yīng)反饋移位寄存器產(chǎn)生的輸出信號為Qn4Qn3Qn2Qn1=1000；當(dāng)碼元a5出錯時，對應(yīng)反饋移位寄存器產(chǎn)生的輸出信號為Qn4Qn3Qn2Qn1=0100；…；當(dāng)碼元a0出錯時，對應(yīng)反饋移位寄存器產(chǎn)生的輸出信號為Qn4Qn3Qn2Qn1=0111。將余數(shù)Qn4Qn3Qn2Qn1通過非門和與門后，產(chǎn)生校正信號。最后利用反饋移位寄存器的移位操作，將校正信號S正好對準(zhǔn)緩存器的輸出碼元，從而使得這兩路信號同時到達異或器，對相應(yīng)的錯誤碼元校正。圖9-10反饋移位寄存器的狀態(tài)轉(zhuǎn)換圖

3．譯碼和糾錯原理分析

圖9-8所示編碼電路的生成多項式為g(x)=x4+x2+x+1，得所有的許用碼字如表9-6所示。發(fā)送端與接收端按同一規(guī)則進行編譯碼，譯碼電路如圖9-9所示。分析結(jié)果如下：

(1)經(jīng)傳輸后收到的碼字T(x)如果沒有誤碼，則能被除法電路除盡，余數(shù)為0，除法電路中的4個寄存器R4、R3、R2、R1也都為0，當(dāng)S閉合后，反饋移位寄存器中的R4、R3、R2、R1也都為0，校正信號S=0，不需校正。

(2)在錯1位的情況下，以表9-6中的碼多項式T(x)=x6+x3+x+1為例來說明糾錯原理，其余碼多項式錯1位的情況類似，讀者不難驗證。①若a6有錯，x4(x3+x+1)/(x4+x2+x+1)的余多項式為x3，它對應(yīng)的四位碼為Qn4Qn3Qn2Qn1=1000，根據(jù)圖9-10，不需移位，得,立即對a6糾錯。

②若a5有錯，x4(x6+x5+x3+x+1)/(x4+x2+x+1)的余多項式為x2，它對應(yīng)的四位碼為Qn4Qn3Qn2Qn1=0100，根據(jù)圖9-10，移位一次后，得

，對a5糾錯。

③若a4有錯，x4(x6+x4+x3+x+1)/(x4+x2+x+1)余多項式x，它對應(yīng)四位碼為Qn4Qn3Qn2Qn1=0010，根據(jù)圖9-10，移位兩次后，得，對a4糾錯。④若a3有錯，x4(x6+x+1)/(x4+x2+x+1)的余多項式為1，它所對應(yīng)的四位碼為Qn4Qn3Qn2Qn1=0001，根據(jù)圖9-10，移位三次后，得，對a3糾錯。

⑤若a2有錯，x4(x6+x3+x2+x+1)/(x4+x2+x+1)余多項式為x3+x+1，對應(yīng)四位碼為Qn4Qn3Qn2Qn1=1011，根據(jù)圖9-10，移位四次后，得

，對a2糾錯。

⑥若a1有錯，x4(x6+x3+1)/(x4+x2+x+1)余多項式為x3+x2+x，它所對應(yīng)的四位碼為Qn4Qn3Qn2Qn1=1110，根據(jù)圖9-10，移位五次后，得，對a1糾錯。

⑦若a0有錯,x4(x6+x3+x)/(x4+x2+x+1)余多項式為x2+x+1,它對應(yīng)的四位碼為Qn4Qn3Qn2Qn1=0111，根據(jù)圖9-10，移位六次后，得，對a0糾錯。

【例9.6】已知(7,3)循環(huán)碼的生成多項式為g(x)=x4+x3+x2+1,試設(shè)計其編碼電路和譯碼電路。已知發(fā)送端發(fā)送的正確碼字為T=a6a5a4a3a2a1a0=1110100,若a6有錯,利用它來設(shè)計譯碼器中的校正電路(即反饋移位寄存器的哪些輸出應(yīng)串接非門)。并分析當(dāng)碼字中的a5、a4、a3、a2、a1、a0分別出錯時譯碼器能否正確糾錯，從而論證該譯碼器的設(shè)計是否正確。

解根據(jù)圖9-7所示的規(guī)則，得除法電路如例9.5圖所示。

(1)編碼電路的設(shè)計結(jié)果如例9.6圖(a)所示。例9.6圖(a)

(2)譯碼電路的設(shè)計結(jié)果如例9.6圖(b)所示。其中反饋移位寄存器的哪些輸出端要加非門可由碼元a6發(fā)生錯誤來確定。a6出錯，碼字變成0110100，對應(yīng)的碼多項式為T′(x)=x5+x4+x2，余數(shù)的計算與前面敘述的方法相同，得余多項式為x3→1000，故應(yīng)分別在R1、R2、R3的輸出端口串入一個非門。

(3)根據(jù)圖9.6(b)，得反饋移位寄存器的狀態(tài)方程為得反饋移位寄存器的狀態(tài)轉(zhuǎn)換表如例9.6表(a)所示。例9.6圖(b)

例9.6表(a)反饋移位寄存器的狀態(tài)轉(zhuǎn)換表

根據(jù)例9.6表(a)，得狀態(tài)轉(zhuǎn)換圖如例9.6圖(c)所示。

(4)糾錯的工作原理分析

①當(dāng)a6有錯時，余多項式x3，對應(yīng)余數(shù)1000，不需移位，立即對a6糾錯。

②當(dāng)a5有錯時，余多項式x2，對應(yīng)余數(shù)為0100，移位一次，可對a5糾錯。

③當(dāng)a4有錯時，余多項式x，對應(yīng)余數(shù)為0010，移位二次，可對a4糾錯。

④當(dāng)a3有錯時，余多項式1，對應(yīng)余數(shù)為0001，移位三次，可對a3糾錯。

⑤當(dāng)a2有錯時，余多項式x3+x2+x，對應(yīng)余數(shù)為1110，移位四次，可對a2糾錯。例9.6圖(c)⑥當(dāng)a1有錯時，余多項式x2+x+1，對應(yīng)余數(shù)為0111，移位五次，可對a1糾錯。

⑦當(dāng)a0有錯時，余多項式x3+x2+1，對應(yīng)余數(shù)為1101，移位六次，可對a0糾錯。

*(5)最后用時序邏輯電路的分析方法來驗證上面各個余數(shù)的正確性。根據(jù)例9.6圖(b)，得譯碼器中除法運算器的狀態(tài)方程為根據(jù)上述狀態(tài)方程，可得狀態(tài)轉(zhuǎn)換表如例9.6表(b)所示，進一步得接收碼字與余數(shù)之間的關(guān)系如例9.6表(c)所示。由此可見，用兩者的分析結(jié)果是一致的。

例9.6表(b)狀態(tài)轉(zhuǎn)換表例9.6表(c)接收碼字與余數(shù)之間的關(guān)系9.6.6循環(huán)碼譯碼電路的另一種簡便設(shè)計方法

本節(jié)介紹循環(huán)碼譯碼電路的另一種簡便設(shè)計方法:將收到的循環(huán)碼直接作除法運算。

1.求余

已知循環(huán)碼的生成多項式g(x)=x4+x2+x+1,如何求余數(shù)?首先以表912中的第一個循環(huán)碼為例來說明其余數(shù)的求法,因為第一個循環(huán)碼是最簡單的。其余碼的情況依此類推,可驗證所得的結(jié)果是一致的。

2.根據(jù)對應(yīng)的狀態(tài)轉(zhuǎn)換圖

1）余數(shù)對應(yīng)的狀態(tài)轉(zhuǎn)換圖

根據(jù)前面講到的循環(huán)碼譯碼器,其中7級緩存器的結(jié)構(gòu)如圖9-17所示。

得到余數(shù)對應(yīng)的狀態(tài)轉(zhuǎn)換圖如圖9-18所示。圖9-177級緩存器的結(jié)構(gòu)圖9-18余數(shù)狀態(tài)轉(zhuǎn)換圖

2）狀態(tài)轉(zhuǎn)換表

利用狀態(tài)轉(zhuǎn)換圖得到狀態(tài)轉(zhuǎn)換表，如表9-13所示，表中“X”表示隨意項。

3）卡諾圖

由狀態(tài)轉(zhuǎn)換表得到卡諾圖如圖9-26所示。

4）電路圖

由卡諾圖的結(jié)果得電路圖如圖9-27所示。

表9-13狀態(tài)轉(zhuǎn)換表0000XXXX00010010001001000011XXXX010010000101XXXX0110XXXX01111110100001111001XXXX1010XXXX101100011100XXXX1101XXXX111010111111XXXX圖9-26卡諾圖圖9-27電路圖

圖9-28非門的設(shè)計圖圖9-29循環(huán)碼的譯碼電路

9.7卷積碼簡介

9.7.1卷積碼的基本概念