《編碼理論》課件第7章

第7章循環(huán)碼7.1循環(huán)碼的多項(xiàng)式表述7.2循環(huán)碼的矩陣表述7.3循環(huán)碼的編碼7.4循環(huán)碼的譯碼7.5捕錯(cuò)譯碼及大數(shù)邏輯譯碼7.6

BCH碼7.7

RS碼及Goppa碼 7.1循環(huán)碼的多項(xiàng)式表述

7.1.1基本概念

將—個(gè)n維碼字C＝cn－1cn－2...c1

c0的分量循環(huán)右移一位表示為RC(1)，則RC(1)＝c0cn－1

cn－2…c2

c1

若將C的分量循環(huán)右移i位表示為RC（i），則RC(i)＝ci－1ci－2...c1cocn－1...ci＋1ci

（7-1）如果將碼字C循環(huán)左移1位表示SC（1），則SC（1）＝cn－2cn－3...c1

c0cn－1

同樣如果將碼字C循環(huán)左移i位后就得到：SC（i）＝cn－i－1cn－i－2…，cocn－1…cn－i＋1cn－i

（7-2）不難驗(yàn)證對任意i(0≤i≤n一1)由(7-1)式和(7-2)式定義的左、右循環(huán)移位滿足：RC（n—i）＝SC（i）

可見左、右循環(huán)移位在(7-3)式的含義下是彼此等價(jià)的。今后在不引起混淆的情況下將它們統(tǒng)稱為循環(huán)移位。

設(shè)C是一個(gè)(n，k)線性碼，如果C中的任意一個(gè)碼字經(jīng)任意循環(huán)移位之后仍然是C中的一個(gè)碼字，那么就稱此碼是—個(gè)循環(huán)碼。

循環(huán)碼的描述方式有多種多樣，在不同情況下使用不同的描述方式將有助于問題的深入研究，現(xiàn)在介紹如何用多項(xiàng)式去描述循環(huán)碼。

由于任意一個(gè)n維碼字C＝cn－1cn－2...c1c0都可以用—個(gè)次數(shù)不超過n—1的多項(xiàng)式描述，即:C(x)＝cn—1xn－1＋cn—2xn－2十…十clx＋c0

(7-4)稱C(x)為相應(yīng)碼字的多項(xiàng)式。顯然C與C(x)是一一對應(yīng)的，因此任何一個(gè)GF（2）(n,k)線性分組碼都可以等價(jià)地看作一類由2k個(gè)次數(shù)不超過n一1的多項(xiàng)式組成的集合。

碼字C循環(huán)i次所得的碼多項(xiàng)式為：C（i）(x)＝cn－1－ixn－1＋cn－i－2xn－2＋...＋c0xi＋cn－1xi－1

＋...＋cn－i

(7-5)將式(7-46)乘以x，再除以xn＋1得：（7-6）式(7-6)表明，碼字循環(huán)一次的碼多項(xiàng)式C（1）(x)是原碼多項(xiàng)式C(x)乘x除以xn＋1的余式。寫作：

由此可以推知，C(x)的i次循環(huán)移位C（i）(x)是C(x)乘xi除以xn＋l的余式。即：C1(x)xC(x)mod(xn＋1)C（i）(x)xiC(x)mod(xn＋1)(7-7)循環(huán)碼的碼字的i次循環(huán)移位等效于將碼多項(xiàng)式乘xi后再模xn＋1。式(7-7)揭示了(n，k)線性碼中碼字多項(xiàng)式與碼字循環(huán)移位之間的關(guān)系,它對循環(huán)碼的研究起著重要作用。

定理7-1在以多項(xiàng)式為模的剩余類全體所構(gòu)成的n維線性空間中，其一個(gè)k維子空間是一個(gè)循環(huán)子空間（循環(huán)碼）的充要條件為是一個(gè)理想。

由定理7-1可知，一個(gè)（n，k）循環(huán)碼的碼字多項(xiàng)式都是模運(yùn)算下多項(xiàng)式剩余類環(huán)中的一個(gè)理想，而且一定是一個(gè)主理想子環(huán)。反之，多項(xiàng)式剩余類環(huán)的一個(gè)主理想子環(huán)也一定生成一個(gè)循環(huán)碼。

[例7-1]GF(2)中的（7,3）循環(huán)碼，可由任一個(gè)非零碼字，比如0011101經(jīng)過循環(huán)移位，得到其它6個(gè)非0碼字；也可由相應(yīng)的碼多項(xiàng)式x4十x3＋x2＋l，乘以xi(i＝1，2，…，6)，再模x7＋1運(yùn)算得到其它6個(gè)非0碼多項(xiàng)式。這個(gè)移位過程和相應(yīng)的多項(xiàng)式運(yùn)算如表7-1所示。表7-1(7，3)循環(huán)碼的循環(huán)移位7.1.2循環(huán)碼的生成方法

定理7-2

設(shè)為次數(shù)小于n的多項(xiàng)式集合，本原多項(xiàng)式xn-1。中的一個(gè)碼組C是循環(huán)碼的充分必要條件是C滿足下列條件：(1)(2)

證明：充分性（1）假設(shè)C是中的一個(gè)循環(huán)碼。因?yàn)檠h(huán)碼是線性分組碼的一個(gè)子集，故第一個(gè)條件滿足。

(2)設(shè)

乘以x后對應(yīng)于一個(gè)循環(huán)移位。但因?yàn)橐粋€(gè)循環(huán)碼字的循環(huán)移位還是一個(gè)合法碼字，即x·a(x)∈C，x·(xa(x))∈C,依此類推，所以

也在C中，因每一個(gè)被加數(shù)也在C中。

必要性。假定（1）和（2）都滿足。把r(x)看做一個(gè)常量，則C是線性的。在條件（2）中令r(x)=x，這表明每個(gè)循環(huán)移位都會產(chǎn)生一個(gè)碼字,因此表明C是個(gè)循環(huán)碼。(7－8)下面介紹一種循環(huán)碼的生成方法,即用到目前為止建立起來的數(shù)學(xué)工具如何構(gòu)造循環(huán)碼。設(shè)為次數(shù)小于n的多項(xiàng)式集合，本原多項(xiàng)式f(x)=xn-1,生成一個(gè)循環(huán)碼步驟

(1)在中取一個(gè)多項(xiàng)式;

(2)用中的所有多項(xiàng)式乘以后模

xn-1得到一個(gè)多項(xiàng)式集合;

(3)多項(xiàng)式集合對應(yīng)一個(gè)分組長度為n的循環(huán)碼碼字的集合。

【例7－2】設(shè)GF(2)上的R3中的多項(xiàng)式f(x)=1+x2。一般地,R3中的一個(gè)多項(xiàng)式可以表示為r(x)=r0+r1x+r2x2，其中系數(shù)ri∈GF(2),i=1,2,3。因此，定義在GF(2)上的R3中的多項(xiàng)式有2×２×２=8個(gè)，它們分別為0、1、x、x2、1+x、1+x2、x+x2、1+x+x2。要生成一個(gè)循環(huán)碼，用R3中的這8個(gè)元素去乘以f(x)，然后將結(jié)果模x3-1，得

故只有4個(gè)不同的碼字多項(xiàng)式：｛01+x1+x2x+x2｝，它們對應(yīng)的碼字為｛000011101110｝。7.1.3多項(xiàng)式描述

1.生成多項(xiàng)式

根據(jù)循環(huán)碼的循環(huán)特性，可由一個(gè)碼字的循環(huán)移位得到其它的非0碼字。在(n，k)循環(huán)碼的2k個(gè)碼字中，取前k—1位皆為0的碼字g(x)(其次數(shù)r＝n—k)，再經(jīng)k—1次循環(huán)移位，共得到k個(gè)碼字：g(x)，xg(x)，…,xk－1g(x)。這k個(gè)碼字顯然是相互獨(dú)立的，這就說明，(n，k)循環(huán)碼可由它的一個(gè)(n—k)次碼多項(xiàng)式g(x)來確定，所以說g(x)生成了(n，k)循環(huán)碼，因此稱g(x)為碼的生成多項(xiàng)式，即：

g(x)＝gn－ｋxn－k＋gn－k－1xn－k－1十...十g1x＋go(7-9)2.生成多項(xiàng)式的性質(zhì)

GF(2)中g(shù)(x)有如下的性質(zhì)：

(1)在(n，k)循環(huán)系統(tǒng)碼中存在一個(gè)(n－k)次碼多項(xiàng)式；

因?yàn)樵?k個(gè)信息組中，有一個(gè)信息組為，它的對應(yīng)碼多項(xiàng)式的次數(shù)為n一1一(k一1)＝n－k

(2)在(n，k)循環(huán)碼中，n—k次碼多項(xiàng)式是最低次碼多項(xiàng)式,且gn－k＝1，g0＝1。

若g(x)不是最低次碼多項(xiàng)式，那么設(shè)更低次的碼多項(xiàng)式為g＇(x)，其次數(shù)為n—k—1。g＇(x)的前面k位為0，即k個(gè)信息位全為0，而監(jiān)督位不為0，這對線性碼來說是不可能的。因此g(x)是最低次的碼多項(xiàng)式，且gn－k＝1，g0＝1，否則g(x)經(jīng)n—1次左移循環(huán)后將得到低于n－k次的碼多項(xiàng)式。

(3）在(n，k)循環(huán)碼中，g(x)是唯一的n—k次多項(xiàng)式。

如果存在另一個(gè)n—k次碼多項(xiàng)式，設(shè)為g＇(x)，根據(jù)線性碼的封閉性，則g(x)＋g＇(x)也必為一個(gè)碼多項(xiàng)式。由于g(x)和g＇(x)的次數(shù)相同，它們的和式的n—k次項(xiàng)系數(shù)為0，那么g(x)＋g＇(x)是一個(gè)次數(shù)低于n—k次的碼多項(xiàng)式，在前面已證明g(x)的次數(shù)是最低的，因此g＇(x)不能存在，所以g(x)是唯一的n—k次碼多項(xiàng)式。

(4)在(n，k)循環(huán)碼中，每個(gè)碼多項(xiàng)式C(x)都是g(x)的倍式，而每個(gè)為g(x)倍式且次數(shù)小于或等于n—1的多項(xiàng)式，必是一個(gè)碼多項(xiàng)式。

由定理7-2可知結(jié)論是顯然的。

(5)任意(n，k)循環(huán)碼的生成多項(xiàng)式g(x)一定整除1＋xn。反過來若g(x)是一個(gè)n—k次多項(xiàng)式并且還整除(1＋xn)，那么g(x)一定是某個(gè)循環(huán)碼的生成多項(xiàng)式。

因此，當(dāng)求一個(gè)(n，k)循環(huán)碼時(shí)，只要分解多項(xiàng)式xn＋1，從中取出(n—k)次因式作生成多項(xiàng)式即可。

[例7-3]求(7，3)循環(huán)碼的生成多項(xiàng)式。

分解多項(xiàng)式x7＋1，取其4次因式作生成多項(xiàng)式:

x7十l＝(x＋1)(x3＋x2＋1)(x3＋x＋1)

可將一次和任一個(gè)三次因式的乘積作為生成多項(xiàng)式，因而可任取:

gl(x)＝(x＋1)(x3＋x2＋1)＝x4＋x2＋x＋1

或g2(x)＝(x＋1)(x3＋x＋1)＝x4＋x3＋x2＋1

3.監(jiān)督多項(xiàng)式

如果設(shè)g(x)為(n，k)循環(huán)碼的生成多項(xiàng)式，必為xn＋1的因式，則有:

xn＋1＝h(x)·g(x)

因?yàn)間(x)為n—k次多項(xiàng)式，以g(x)為生成多項(xiàng)式，則生成一個(gè)(n，k)循環(huán)碼，以h(x)為生成多項(xiàng)式，則生成(n，n—k)循環(huán)碼，這兩個(gè)循環(huán)碼互為對偶碼。稱h(x)為(n，k)循環(huán)碼的校驗(yàn)多項(xiàng)式或監(jiān)督多項(xiàng)式,且

h(x)＝hkxk＋hk－１xk－１＋…＋hlx＋ho

（7-10）

7.2循環(huán)碼的矩陣表述

7.2.1生成矩陣

生成多項(xiàng)式可以生成k個(gè)相互獨(dú)立的碼字，這k個(gè)碼字可作為碼生成矩陣的k行，于是得到(n,k)循環(huán)碼的生成矩陣G,即（7-12）

【例7－4】設(shè)（7，4）循環(huán)碼的生成多項(xiàng)式g(x)＝x3＋x＋1，求其生成矩陣G。

解由式(7－12)得:由此生成矩陣G可以生成（7，4）循環(huán)碼的碼字。另利用多項(xiàng)式

C(x)=u(x)g(x)

也可求出對應(yīng)碼字,其中u(x)為信息多項(xiàng)式?！纠?－4】設(shè)（7，4）循環(huán)碼的生成多項(xiàng)式g(x)＝x3＋x＋1，求其生成矩陣G。

解由式(7－12)得:

由此生成矩陣G可以生成（7，4）循環(huán)碼的碼字。另利用多項(xiàng)式

C(x)=u(x)g(x)

也可求出對應(yīng)碼字,其中u(x)為信息多項(xiàng)式。7.2.2監(jiān)督矩陣

循環(huán)碼的校驗(yàn)多項(xiàng)式或監(jiān)督多項(xiàng)式為

h(x)＝hkxk＋hk－１xk－１＋…＋h1x＋h0，則(n，k)循環(huán)碼的監(jiān)督矩陣為(7－13)式中：h*(x)為h(x)的反多項(xiàng)式?！纠?－5】求GF(2)中(7，3)循環(huán)碼的監(jiān)督矩陣。

解因?yàn)閤7＋1＝(x3＋x＋1)(x4＋x2＋x＋1)4次多項(xiàng)式為生成多項(xiàng)式:g(x)＝x4＋x2＋x＋1＝g4x4＋g3x3＋g2x2＋glx＋go

3次多項(xiàng)式則是監(jiān)督多項(xiàng)式：h(x)＝x3＋x＋1＝h3x3＋h2x2＋hlx＋ho

由式(7-13)得(7，3)循環(huán)碼的監(jiān)督矩陣：7.2.3檢錯(cuò)能力

循環(huán)碼特別適合于檢測錯(cuò)誤，一則因它有很強(qiáng)的檢錯(cuò)能力，二則因編碼器和錯(cuò)誤檢測電路都很容易實(shí)現(xiàn)，而且還能檢查出位數(shù)相當(dāng)長的突發(fā)差錯(cuò)。下面簡要討論循環(huán)碼的檢錯(cuò)能力。

(1)能檢出全部單個(gè)錯(cuò)碼。設(shè)碼組中第i位上有單個(gè)錯(cuò)碼，則對應(yīng)的錯(cuò)碼多項(xiàng)式為xi，而任何多于一項(xiàng)的生成多項(xiàng)式，它的x0項(xiàng)為1，因此xi除以g(x)的余數(shù)必定不為0，即能檢出全部單個(gè)錯(cuò)碼。

(2)能檢查全部離散的二位錯(cuò)

設(shè)碼組中第i和第j位錯(cuò)碼，且i<j<n，則錯(cuò)碼多項(xiàng)式為：xj＋xi＝xi（1＋xj－i）。因?yàn)槎嘤谝豁?xiàng)的g(x)必定不能除盡xi，所以，只要選取的g(x)是不能除盡(xj－i十1)，且其階(n－k)>(j－i)，就能檢查出全部二位錯(cuò)碼。

(3)能檢查出全部的奇數(shù)個(gè)錯(cuò)碼。由于具有奇數(shù)項(xiàng)錯(cuò)碼的多項(xiàng)式必不含有因子(x＋1)，所以只要選取的g(x)含有(x＋1)因子，錯(cuò)碼多項(xiàng)式不能被g(x)整除，即能檢出全部奇數(shù)個(gè)錯(cuò)碼。

(4)能檢測所有長度不超過(n－k)的突發(fā)錯(cuò)誤

長度不大于b的突發(fā)錯(cuò)誤的錯(cuò)碼多項(xiàng)式可表示為：E（x）＝xi（eb－1xb－1＋eb－2xb－2＋...＋e1x＋1）＝xiE1(x)(7-14)其中E1(x)為不高于(b－1)項(xiàng)的多項(xiàng)式。如果g(x)不能除盡E(x)，則這種突發(fā)錯(cuò)誤就可檢測出來。由于已知g(x)不能有x作因子，而且多于一項(xiàng)的g(x)必定除不盡xi，因此，只有它能除盡E1(x)才能除盡E(x)。但是g(x)為(n－k)次多項(xiàng)式，而E1(x)的次數(shù)(b－1)只要不超過(n－k－1)次，即g(x)的次數(shù)比E1(x)的高，g(x)就一定除不盡E1(x)。因此，能檢測長度不超過(n－k)的突發(fā)錯(cuò)誤。(5)在突發(fā)長度b大于(n－k)的錯(cuò)誤中，若b＝n－k＋1，則(n，k)循環(huán)碼不能檢測概率為2－(n－k－1)(或能檢測的概率為[1－2－(n－k－1)])；若b>n－k＋1，則不能檢測概率為2－(n－k)(或能檢測的概率為[1—2－(n－k)])。

設(shè)錯(cuò)碼多樣式為E(x)＝xiE1(x)，其中式E1(x)的次數(shù)為(b—1)。

因?yàn)镋1(x)中必有x0和xb－1項(xiàng)，所以還應(yīng)有b－2項(xiàng)xj，其中0<j<b－1，這b－2項(xiàng)的系數(shù)為0或1，因此，共有2b－2種不同的多項(xiàng)式E1(x)。只有當(dāng)E1(x)有g(shù)(x)的因子時(shí)，這種錯(cuò)碼才不能被檢測出來，即這時(shí)應(yīng)有：E1(x)＝g(x)Q(x)因?yàn)間(x)為(n—k)次的，所以Q(x)必為b－1－(n－k)次。如b－1＝n－k(即b＝n－k＋1)，則Q(x)＝1。這時(shí)只有一個(gè)E1(x)錯(cuò)誤圖樣是不可檢測的，即E1(x)＝g(x)，所以它占不可檢測的突發(fā)錯(cuò)誤總數(shù)的1/2b－2＝2－（n－k－1），即可作為不能檢測概率。

如果b－1>n－k，那么Q(x)應(yīng)含有x0和xb－1－（n－k）項(xiàng)，其中有b－2－(n－k)項(xiàng)可具有任意的系數(shù)，0或1。所以，Q(x)有2b—2—(n－k)種不可檢測的錯(cuò)碼圖樣，它占的比例為2b-2-(n-k)/2b-2=2-(n-k)，即可作為不能檢測概率。

以上可見循環(huán)碼的檢錯(cuò)能力是很高的。例如采用CRC-16或CRC-CCITT的循環(huán)碼可以查出全部單錯(cuò)、雙錯(cuò)、奇數(shù)位錯(cuò)，全部16位或16位以下突發(fā)錯(cuò)誤，99．997％的17位突發(fā)錯(cuò)碼以及99．998％的18位或更長的突發(fā)錯(cuò)碼。 7.3循環(huán)碼的編碼

7.3.1編碼原理

1.編碼原理

由于生成多項(xiàng)式g(x)和校驗(yàn)多項(xiàng)式h(x)都可以唯一地確定循環(huán)碼，因此編碼方法既可基于g(x)又可基于h(x)。下面僅給出基于生成多項(xiàng)式的具體編碼方案。設(shè)信息多項(xiàng)式:u(x)=uk－1xk－1＋uk－2

xk－2＋…＋uo

（7－16）一個(gè)非系統(tǒng)碼形式的(n，k)循環(huán)碼的碼字多項(xiàng)式C(x)=u(x)g(x),所以非系統(tǒng)碼的編碼可以用一個(gè)乘法器實(shí)現(xiàn)。一個(gè)系統(tǒng)碼形式的(n，k)循環(huán)碼的碼字多項(xiàng)式為C(x)=xn-ku(x)+r(x)=uk－1xn－1＋uk－2xn－2＋…＋uoxn-k+rn-k-1xn-k-1+…+r1x+r0

（7-17）式中：r(x)——監(jiān)督元對應(yīng)的多項(xiàng)式，即r(x)≡xn-ku(x)(modg(x))(7-18)一個(gè)系統(tǒng)碼形式的(n，k)循環(huán)碼的編碼步驟為：

(1)用xn－k乘信息多項(xiàng)式u(x)；

(2)按式(7-18)求余式r(x);

(3)作碼字c(x)=xn-ku(x)＋r(x)。

2.多項(xiàng)式乘法運(yùn)算電路

設(shè)GF(p)域兩個(gè)次數(shù)分別是k次、r次的二元多項(xiàng)式為a(x)和b(x),即a(x)=a0+a1x+…+akxk

(ai∈GF(p);i=0,1,2,…,k)(7-19)(7-20)兩個(gè)多項(xiàng)式相乘得到

（7-21）式(7-21)中系數(shù)的乘法運(yùn)算和加法運(yùn)算都是模p運(yùn)算。從式(7-21)看到，多項(xiàng)式c(x)的最高次項(xiàng)系數(shù)是a(x)、b(x)各自最高次項(xiàng)的乘積，c(x)的次高次項(xiàng)系數(shù)等于a(x)最高次項(xiàng)系數(shù)與b(x)次高次項(xiàng)系數(shù)之積加上b(x)最高次項(xiàng)系數(shù)與a(x)次高次項(xiàng)系數(shù)之積，…，以此類推，c(x)最低次的常數(shù)項(xiàng)等于a(x)常數(shù)項(xiàng)與b(x)常數(shù)項(xiàng)之積。由此想到，如果把a(bǔ)(x)，b(x)和c(x)的系數(shù)單獨(dú)抽出來組成三個(gè)p進(jìn)制序列A，B，C，那么C恰好是A和B的卷積，體現(xiàn)這種關(guān)系的卷積電路也就是所需要的乘法電路，乘法運(yùn)算的電路實(shí)現(xiàn)如圖7-1所示。圖7－1乘法電路

【例7－6】已知GF(2)上的多項(xiàng)式a(x)=x3+x和b(x)=x3+x+1，求它們的乘積c(x)=a(x)b(x)及相應(yīng)的乘法電路。

解分別將a(x)和b(x)的系數(shù)抽出，得到兩個(gè)二進(jìn)制序列A=a3a2a1a0=1010和B=b3b2b1b0=1011。將序列A由高到低依次輸入。隨著時(shí)鐘脈沖的輸入，接著的一步步運(yùn)算(模2)如下：

第1拍：A序列右移一位，此拍的輸出就是c(x)最高次項(xiàng)的系數(shù)c6，是上下對應(yīng)位求積后相加,即c6=a3·b3=1⊙1=1。

第2拍：A序列再右移一位，輸出c5=a3b2+a２b3=1⊙0⊙0⊙1=0。第3拍：A序列再右移一位,輸出c4=a3b1+a2b2+a1b3=1⊙1⊙0⊙0⊙1⊙1=0。

依次類推，直到最后的第7拍，輸出c0=a0b0=1⊙0=0。

7拍中的累計(jì)輸出是C=［c6c5c4c3c2c1c0］=［1001110］，序列對應(yīng)的多項(xiàng)式c(x)是：c(x)=x6+x3+x2+x。

根據(jù)上面的運(yùn)算過程，可設(shè)計(jì)出乘法電路如圖7－2所示。圖7－2乘法電路

【例7－7】已知二元多項(xiàng)式a(x)=1+x+x4和b(x)=1+x2，設(shè)計(jì)其乘法電路。

解c(x)=a(x)b(x)=1+x+x2+x3+x4+x6其電路實(shí)現(xiàn)框圖如圖7－3所示。圖7－3乘法電路實(shí)現(xiàn)框圖

3.多項(xiàng)式除法運(yùn)算電路

設(shè)GF(p)域兩個(gè)次數(shù)分別是n次、r次的多項(xiàng)式a(x)和b(x)為:a(x)=a0+a1x+…+anxn（ai∈GF(p)；i=0,1,2,…,n）n≥r)(7-22)(7-23)兩個(gè)多項(xiàng)式相除得到:(7－24)式中：q(x)——a(x)除以b(x)的商式；r(x)——a(x)除以b(x)的余式。圖7－4多項(xiàng)式除法運(yùn)算電路

【例7－8】已知二元域多項(xiàng)式 及 ，求a(x)除以b(x)的余式r(x)及實(shí)現(xiàn)電路。

解將a(x)除b(x)得商p(x)=x3+1，余數(shù)r(x)=x2。據(jù)此設(shè)計(jì)除法運(yùn)算電路如圖7－5所示。

這是一個(gè)線性反饋移位寄存器。每單位時(shí)間(拍)中，D3的內(nèi)容在輸出的同時(shí)反饋回移存器各位。初始時(shí)移存器D1D2D3=000，其工作過程為：

第1、2、3拍：順序輸入a6=1，a5=0，a4=1(高位先)，輸出000，反饋輸入也是000。第3拍結(jié)束時(shí)，移存器內(nèi)容D1D2D3=101。第4拍：輸入a3=0，移存器D1D2D3的輸出分別是101。Ｄ3的輸出就是除法電路的輸出q3=1，也就是反饋電路的輸入。反饋信號q3通過反饋線將q3·b=1(b0b1b2)=110加到輸入及移存器D1D2輸出端，

運(yùn)算結(jié)果010+110=100就是第4拍結(jié)束時(shí)移存器D1D2D3的值。

同理得，第5拍輸入a2=1，除法電路輸出q2=D3=0，第5拍結(jié)束時(shí)移存器D1D2D3的值為110；第6拍輸入a1=1，除法電路輸出q1=0，第6拍結(jié)束時(shí)移存器D1D2D3的值為111；第7拍輸入a0=1，除法電路輸出q0=1，第7拍結(jié)束時(shí)移存器D1D2D3的值為001。

第8、9、10拍：中斷反饋(反饋開關(guān)位置從S1變到S2，將移存器內(nèi)容(r0r1r2)逐位輸出(高位先)，每拍一位。從第4拍到第10拍的輸出依次是q3q2q1q0r2r1r0，前4位是商，后3位是余數(shù)。

【例7－9】設(shè)二元多項(xiàng)式a(x)和b(x)分別為a(x)=x5+x4+x2+1和b(x)=x3+x+1，根據(jù)多項(xiàng)式相除的長除法運(yùn)算可得：a(x)=(x2+x+1)b(x)+x2，其中，商多項(xiàng)式q(x)=x2+x+1，余式r(x)=x2。完成上述兩個(gè)多項(xiàng)式相除的運(yùn)算電路如圖7－5所示。圖中移位寄存器的工作過程如表7－2所示。圖7－5除法運(yùn)算電路表7－2例7－9移位寄存器的工作過程

【例7－10】設(shè)a(x)=x4+x+1，b(x)=x3+x2+1，設(shè)計(jì)完成兩個(gè)多項(xiàng)式相除的運(yùn)算電路。

解兩個(gè)多項(xiàng)式相除，商為x+1，余數(shù)為x2，完成上述兩個(gè)多項(xiàng)式相除的運(yùn)算電路如圖7－6所示。

表7－3給出了除法電路的運(yùn)算過程。運(yùn)算開始前所有的觸發(fā)器清零。隨著第一個(gè)時(shí)鐘節(jié)拍的到來，運(yùn)算開始，被除式a(x)的系數(shù)a4a3a2a1a0=10011按節(jié)拍依次輸入，先輸入a4，最后輸入a0，移位寄存器內(nèi)容也隨輸入而不斷改變。運(yùn)算結(jié)束時(shí)，輸出的商為00011，即x+1，移位寄存器中的內(nèi)容D3D2D1=100，即余式為x2。表7－3除法電路的運(yùn)算過程

圖7－6除法電路7.3.2編碼實(shí)現(xiàn)電路

系統(tǒng)循環(huán)碼的編碼方法是：首先將信息元多項(xiàng)式u(x)乘以xn-k成為xn-ku(x),然后將xn-ku(x)除以生成多項(xiàng)式g(x)得到余式r(x)，該余式就是校驗(yàn)元多項(xiàng)式，從而可得碼字多項(xiàng)式c(x)=xn-ku(x)+r(x)。

用電路實(shí)現(xiàn)編碼時(shí)可以采用以g(x)為除式的除法電路。該電路是一個(gè)帶反饋的根據(jù)生成多項(xiàng)式g(x)＝1＋g1x+…＋gn－k－1xn－k－1+xn－k作出的n-k級線性移位寄存器編碼電路，如圖7－7所示。圖7－7

n－k級線性移位寄存器編碼電路編碼運(yùn)算過程如下：

第1步：門打開后，k位信息數(shù)據(jù)u0，u1，…，uk－1移入線路中，同時(shí)送入通信信道。消息從線路的

前端移入（等價(jià)于用xn－k左乘u(x))。一旦k位消息全部移入線路，在寄存器中的n-k個(gè)數(shù)據(jù)就構(gòu)成了余項(xiàng)，它們就是校驗(yàn)數(shù)據(jù)。

第2步：開關(guān)關(guān)上后，斷開反饋連線。

第3步：移出校驗(yàn)元并把它們送入信道。這n-k個(gè)一致校驗(yàn)元b0，b1，…，bn－k－1與k個(gè)信息元一起構(gòu)成一個(gè)完整的碼字。

【例7－11】

(7，4)循環(huán)碼的g(x)=x3+x2+1,試設(shè)計(jì)其編碼電路。給出當(dāng)輸入u(x)=1+x3時(shí)的編碼過程。

解圖7－8所示為生成多項(xiàng)式的編碼電路。該電路在除法電路的基礎(chǔ)上，將輸入信息元組u(x)從n-k個(gè)寄存器的高端送入，相當(dāng)于u(x)乘以xn-k。移位脈沖cp在1～k個(gè)節(jié)拍內(nèi)，S1、S2打向“1”，各信息元直接經(jīng)S1輸出，成為系統(tǒng)碼的前k個(gè)碼元；同時(shí)它們又依次進(jìn)入除法電路，進(jìn)行xn-ku(x)除以g(x)的運(yùn)算。運(yùn)算結(jié)束時(shí)留在移位寄存器中的存數(shù)就是余式r(x)的系數(shù)。然后，cp在(k+1)～n個(gè)節(jié)拍內(nèi)，S1、S2打向“2”，使移位寄存器中的各校驗(yàn)元依次輸出，形成了一個(gè)長為n的碼字。圖7－8

(7，4)循環(huán)碼編碼器電路表7－4

(7，4)循環(huán)碼編碼過程

7.4循環(huán)碼的譯碼

7.4.1譯碼原理

對線性碼進(jìn)行譯碼時(shí)，根據(jù)接收碼字多項(xiàng)式的伴隨式和可糾的錯(cuò)誤圖樣間的一一對應(yīng)關(guān)系，可由伴隨式得到錯(cuò)誤圖樣。循環(huán)碼是線性碼的一個(gè)特殊子類，且由于循環(huán)碼的循環(huán)特性，致使它的譯碼更加簡單易行。循環(huán)碼的譯碼包括以下三個(gè)步驟：計(jì)算接收多項(xiàng)式的伴隨式，求伴隨式對應(yīng)的錯(cuò)誤圖樣，用錯(cuò)誤圖樣譯碼。（7-25）這是由接收碼字相應(yīng)分量直接求和計(jì)算伴隨式的方法，對所有線性碼都是適用的。

2．用k級移存器的伴隨式計(jì)算電路

定理7－3二元線性系統(tǒng)碼中，接收碼字Ｒ的伴隨式S等于對Ｒ的信息部分所計(jì)算的監(jiān)督元(相當(dāng)于對Ｒ的信息部分重新編碼)與接收的監(jiān)督元的矢量和。

證明設(shè)接收碼字R＝［RI|RP］，RI是R的信息部分，它是長度為k的矢量，RP是Ｒ的監(jiān)督元部分，是長為r＝n－k的矢量，監(jiān)督矩陣為H＝［Q|Ir］，Q為r×k階子陣，Ir為r×r階單位子陣。由伴隨式的定義：

Q是H中除單位子陣外的r×k階子陣，所以RIQT是把RI作信息元重新編碼計(jì)算的監(jiān)督元。而Rp為接收的監(jiān)督元。證畢。S＝RHT＝[RI︱RP][Q︱IR]T＝RIQT＋RPIR＝RIQT＋Rp

（7－26）圖7－9用k級移存器實(shí)現(xiàn)的伴隨式計(jì)算電路該電路的工作步驟如下：

(1)門1通，門2、3、4關(guān)，接收碼字R的k位信息部分輸入編碼器。

(2)門1關(guān)，門2、3、4通，接收信息編碼所得的監(jiān)督元與接收監(jiān)督元逐位模2加，得到伴隨式。但這種伴隨式計(jì)算方法只適于線性系統(tǒng)碼。

3．用n－k級移存器的伴隨式計(jì)算電路

設(shè)接收多項(xiàng)式為R(x)，它的信息部分表示為RI(x)，監(jiān)督部分表示為Rp(x)，由定理7－3知：S(x)＝R＇(x)＋Rp(x)(7-27)式中：R′(x)是對RI(x)重新編碼的監(jiān)督元多項(xiàng)式。若碼的生成多項(xiàng)式為g(x)，則S(x)≡RI(x)＋Rp(x)R(x)(modg(x))(7-28)式(7-28)表明，循環(huán)碼接收多項(xiàng)式的伴隨式是接收多項(xiàng)式R(x)除以g(x)的余式。設(shè)E(x)為R(x)的錯(cuò)誤圖樣，那么：R(x)＝C(x)＋E(x)（2-29）但C(x)為g(x)的倍式，所以S(x)≡[C(x)十E(x)]≡

E(x)(modg(x))(7-30)式(7－30)也表明了伴隨式是由錯(cuò)誤圖樣決定的，與具體碼字無關(guān)。應(yīng)該指出，循環(huán)碼伴隨式的表示式(7－28)雖由系統(tǒng)碼推出，但由于伴隨式僅與錯(cuò)誤圖樣有關(guān)，因而對非系統(tǒng)碼也是適用的。圖7-10n—k級移存器的伴隨式計(jì)算電路

定理7－4設(shè)S(x)為接收碼字R(x)的伴隨式，則R(x)的循環(huán)移位xR(x)(modxn+1)的伴隨式S（1）(x)等于伴隨式S(x)的循環(huán)移位xS(x)(modg(x)),即S（1）(x)≡xS(x)(modg(x))（7－31）證明由伴隨式計(jì)算式(7－28)知S(x)≡R(x)(modg(x))x（1）S(x)xR(x)(modg(x))對上式兩邊作同余運(yùn)算得（7－32）令（7－33）即用R（1）(x)表示R(x)循環(huán)移位一次xR(x)(mod（xn＋1）)的碼多項(xiàng)式。對式(7-33)進(jìn)行模g(x)運(yùn)算，則得到R(x)循環(huán)移位xR(x)的伴隨式（7－34）考慮到式(7-32)，則有證畢7.4.3梅吉特譯碼

循環(huán)碼的譯碼基本上按線性分組碼的譯碼步驟進(jìn)行，其循環(huán)位移特性使譯碼電路大為簡化。通用的循環(huán)碼譯碼器如圖7－11所示。包括三個(gè)部分：

(1)伴隨式計(jì)算電路，可根據(jù)實(shí)際情況選取不同的伴隨式電路。

(2)錯(cuò)誤圖樣檢測器,是一個(gè)組合邏輯電路，其作用是將伴隨式譯為錯(cuò)誤圖樣。它是這樣設(shè)計(jì)的：當(dāng)且僅當(dāng)錯(cuò)誤圖樣是一個(gè)可糾的錯(cuò)誤圖樣，并且此錯(cuò)誤圖樣包含最高階位上的一個(gè)錯(cuò)誤時(shí)，伴隨式計(jì)算電路計(jì)算得到的伴隨式才使檢測電路輸出為“1”。也就是說，如果錯(cuò)誤圖樣檢測器輸出為“1”，則認(rèn)為最高階位上接收符號是錯(cuò)誤的，應(yīng)該予以糾正；如果檢測器輸出“0”，則認(rèn)為最高階位上的接收符號是正確的，不必糾正。對于碼字中任何位置上的錯(cuò)誤，通過碼多項(xiàng)式和伴隨式同時(shí)循環(huán)移位，當(dāng)錯(cuò)誤符號移到最高階位上時(shí)，伴隨式則使檢測器輸出為“1”，將其錯(cuò)誤糾正。因而通過循環(huán)移位后，能使可糾錯(cuò)誤圖樣中的全部錯(cuò)誤都得到糾正。

(3)接收碼多項(xiàng)式緩存器和模2加糾錯(cuò)電路。圖7－11通用循環(huán)碼譯碼器整個(gè)譯碼電路的工作過程如下：

(1)將接收碼多項(xiàng)式移入伴隨式計(jì)算電路，計(jì)算出伴隨式,同時(shí)將接收碼多項(xiàng)式移入緩存器。

(2)將伴隨式寫入錯(cuò)誤圖樣檢測器，并在檢測器中循環(huán)移位(modg(x))，同時(shí)將接收碼多項(xiàng)式移出緩存器，當(dāng)檢測器輸出“1”時(shí)，表示緩存器此時(shí)刻的輸出符號是錯(cuò)誤的，并將錯(cuò)誤糾正。同時(shí)檢測器輸出反饋到伴隨式計(jì)算電路的輸入端，去修改伴隨式，從而消除該錯(cuò)誤對伴隨式所產(chǎn)生的影響。直到接收碼多項(xiàng)式全部移出緩存器，該接收碼多項(xiàng)式糾錯(cuò)完畢。若最后伴隨式寄存器中為全“0”，則表示錯(cuò)誤全部被糾正；否則，檢出了不可糾的錯(cuò)誤圖樣。

【例7－12】已知g(x)=x3+x+1,畫出二進(jìn)制(7，4，3)漢明循環(huán)碼的梅吉特譯碼電路。

解漢明碼糾錯(cuò)能力為t=1，可糾正的差錯(cuò)圖樣有7個(gè)：E(x)=1,x,x2,x3,x4,x5,x6（重量為1)。采用梅吉特譯碼器時(shí)，只要能糾正一個(gè)可糾正差錯(cuò)圖樣，比如E=［1000000］或多項(xiàng)式E(x)=x6，就可以通過該可糾正圖樣的循環(huán)糾正同類的其他差錯(cuò)圖樣。由于所有可糾正差錯(cuò)圖樣視為E=［1000000］循環(huán)移位而來，因此設(shè)計(jì)的譯碼邏輯電路只要能識別與E=［1000000］對應(yīng)的伴隨式101或s(x)=x2+1即可,相應(yīng)的電路圖如圖7－12所示。圖7-12循環(huán)碼的梅吉特譯碼電路譯碼邏輯電路由3路與門構(gòu)成，中間1路帶“非”。只有當(dāng)s2s1s0=101時(shí)，與門輸出才為“1”。

假設(shè)差錯(cuò)圖樣是E=［0001000］,即E(x)=x3，在前7個(gè)時(shí)鐘周期，接收碼多項(xiàng)式分兩路同時(shí)輸入g(x)除法器和7級緩存器。第7拍結(jié)束時(shí)，除法器D3D2D1中包含的伴隨式s2s1s0是011。從第8拍到第14拍，輸入端恒為0，除法器在每一時(shí)鐘周期右移作一次除法；7級緩存器則右移一位，與譯碼邏輯電路的輸出模2加后即是譯碼結(jié)果。如果譯碼邏輯電路判斷7級緩存器最高位有錯(cuò)，譯碼邏輯將輸出“1”，在下一拍最高位輸出時(shí)通過模2加對該位作糾正運(yùn)算。例7－12的各節(jié)拍中，除法器保存的伴隨式、譯碼邏輯值及輸出信號如表7－5所示。表7－5梅吉特譯碼器的循環(huán)糾錯(cuò)

表7-5說明:與門輸出由上拍s2s1s0決定,對應(yīng)的差錯(cuò)圖樣r6r5r4r3r2r1r0中的最高位是緩存器下一輸出位。

例7-12中的譯碼器稱為無反饋的梅吉特譯碼器。事實(shí)上，還有一種反饋型的梅吉特譯碼器如圖7-13所示，它能更充分地利用碼的循環(huán)特性(以時(shí)間換電路復(fù)雜性)。與無反饋型相比，它有兩處不同：

(1)n級緩存器能做模運(yùn)算(循環(huán)移位)，使碼字在緩存器中反復(fù)循環(huán)而不丟失；

(2)糾錯(cuò)信息同時(shí)反饋給緩存器里的碼多項(xiàng)式和除法器的伴隨式，使它們能同步地反映糾正后的與的變化情況。圖7-13反饋型的梅吉特譯碼器這些特點(diǎn)使反饋型梅吉特譯碼器能夠多次循環(huán)糾錯(cuò)，從而簡化了差錯(cuò)圖樣識別電路。比如，對于(15，7，5)循環(huán)碼，它應(yīng)該能糾正所有的重量為1和2的差錯(cuò)圖樣，以及部分3重差錯(cuò)。如果用無反饋梅吉特譯碼器，由于是一次糾錯(cuò)(碼字輸入緩存器后逐位輸出并加入糾錯(cuò)信號，糾錯(cuò)過程限在這一個(gè)n拍中完成)，譯碼邏輯必然比較復(fù)雜。如果采用反饋型，可以讓糾錯(cuò)在多次循環(huán)中進(jìn)行。例如，當(dāng)出現(xiàn)一種可糾的3重差錯(cuò)圖樣后，碼字暫不輸出，而是令其在內(nèi)部循環(huán)糾錯(cuò)，此時(shí)k1閉合而k2斷開。如果在第一個(gè)循環(huán)周期糾正了其中一處差錯(cuò)，那么在第二個(gè)循環(huán)周期時(shí)就只剩下包含兩個(gè)差錯(cuò)的圖樣了。再循環(huán)一次，也許就剩下一個(gè)差錯(cuò)的圖樣了。循環(huán)糾錯(cuò)完畢后，把k1斷開而k2閉合，n級緩存器中經(jīng)過糾錯(cuò)的碼字開始輸出。這種方法的譯碼電路只要設(shè)計(jì)得當(dāng)，可比無反饋時(shí)簡單得多。

【例7－13】已知(7，3)循環(huán)碼，當(dāng)碼字傳送出現(xiàn)一個(gè)錯(cuò)誤時(shí)，設(shè)計(jì)譯碼器。

解若用一般譯碼器需要識別如0000001，0000010，0000100，0001000，0010000，0100000，1000000等7個(gè)不同的錯(cuò)誤圖樣，但對循環(huán)碼譯碼器來說，可以把這些錯(cuò)誤圖樣歸成一類，譯碼器只要識別其中的一個(gè)錯(cuò)誤圖樣就可以了。若(7，3)循環(huán)碼譯碼器按錯(cuò)誤圖樣1000000設(shè)計(jì)，于是s(x)=e(x)modg(x)=x6mod(x4+x3+x2+1)=x3+x2+x，即s=1110，其譯碼器電路如圖7－14所示。圖7－14例7－13(7，3)循環(huán)碼譯碼器電路表7-6(7，3)循環(huán)碼譯碼過程(1)若在上述碼字傳送時(shí)，錯(cuò)誤圖樣是E=［0001000］，即R=［0110010］，譯碼器工作過程見表7－7。從表7－7中可見，到第7拍結(jié)束時(shí)s不是全0，但也不是1110，說明接收碼字有錯(cuò)，但錯(cuò)誤圖樣不是［1000000］。從第8拍開始g(x)除法電路進(jìn)行自發(fā)運(yùn)算，到第10拍結(jié)束時(shí)得s=1110。然后與門呈開的狀態(tài)并輸出糾錯(cuò)信號M=1,對于R的對應(yīng)位實(shí)施糾錯(cuò),同時(shí)M=1信號使D1～D4清0。表7－7例7－13(7，3)循環(huán)碼譯碼過程(2)將梅吉特譯碼器稍加改動(dòng)，也可以用做縮短循環(huán)碼的譯碼?？s短i個(gè)信息位的(n-i，k-i)縮短循環(huán)碼是在(n，k)循環(huán)碼中選前i個(gè)信息位為0的碼字組成的，其伴隨式的位數(shù)是一樣的。從原理上來說，譯碼時(shí)，只要在前面添上i個(gè)0，就可以用(n，k)循環(huán)碼譯碼器來實(shí)現(xiàn)。如考慮到時(shí)鐘的配合，可以不添0而對(n，k)譯碼器做兩處修改：緩存器長度減小i；除法電路改由第i節(jié)延時(shí)單元輸入，相當(dāng)于求xiR(x)modg(x)。

梅吉特譯碼器是通用循環(huán)碼譯碼器。從原理上說，它可以用于任何循環(huán)碼或縮短循環(huán)碼的譯碼。但實(shí)際上，這種譯碼器的復(fù)雜程度隨糾錯(cuò)能力t的增加而飛快增長。因此，當(dāng)t>3時(shí)，或突發(fā)差錯(cuò)超過每碼字一次時(shí)，一般不使用這種譯碼器。漢明碼的t=1，所有差錯(cuò)圖樣可歸入同一類，因此特別適合采用梅吉特譯碼器。

7.5捕錯(cuò)譯碼及大數(shù)邏輯譯碼

7.5.1捕錯(cuò)譯碼

捕錯(cuò)譯碼是梅吉特通用譯碼法的一種實(shí)用變形，譯碼器的組合邏輯電路比較簡單，對糾正一個(gè)錯(cuò)誤或兩個(gè)錯(cuò)誤的碼用捕錯(cuò)譯碼法譯碼很有效，改進(jìn)的捕錯(cuò)譯碼法(嵩忠雄譯碼法)可用來

糾正兩個(gè)或三個(gè)隨機(jī)錯(cuò)誤的碼。捕錯(cuò)譯碼法一般適用于短碼或低碼率的碼的譯碼，否則將損失一部分糾錯(cuò)能力。然而，捕錯(cuò)譯碼用于糾突發(fā)錯(cuò)誤的碼的譯碼是很有效的。

循環(huán)碼的捕錯(cuò)譯碼的基本思想是利用碼的循環(huán)特性，把錯(cuò)誤全部移到監(jiān)督碼元位置上，這時(shí)錯(cuò)誤圖樣E(x)等于伴隨式S(x)，因而在求得伴隨式后，只需與監(jiān)督位上的碼元相加，就能實(shí)現(xiàn)糾錯(cuò)。假設(shè)(n，k)循環(huán)碼是糾錯(cuò)能力為t的系統(tǒng)碼，它的碼多項(xiàng)式為

其中：cn－1,cn-2，…，cn-k為信息位；cn－k－1，…，c1，c0為監(jiān)督位。

令接收碼字為R(x)，錯(cuò)誤圖樣為C(x)＝cn－1xn—1＋cn－2xn—2＋…＋c1x＋c0循環(huán)碼的伴隨式可表示為：(7-35)假定en－1，…，en－k全為0，即全部錯(cuò)誤限制在n—k個(gè)監(jiān)督位上，則E(x)是一個(gè)小于n—k次的多項(xiàng)式(低于g(x)的次數(shù))，此時(shí)有：(7-36)由式(7-35)和式(7-36)得到E(x)＝S(x)(7-37)對于糾錯(cuò)能力為t的(n，k)循環(huán)碼，要求t個(gè)錯(cuò)誤限制在n-k個(gè)相鄰位上，碼的參數(shù)應(yīng)滿足什么條件，這個(gè)要求才能得到保證呢?t個(gè)錯(cuò)誤限制在n-k個(gè)相鄰位上，等效于要求R(x)中有一個(gè)相鄰k位的無錯(cuò)區(qū)間。若n、k、t滿足

n>t·k

(7-38)那么即使t個(gè)錯(cuò)誤均勻分布，在R(x)中也一定存在相鄰k位無錯(cuò)的區(qū)間。因而糾t個(gè)錯(cuò)誤的(n，k)循環(huán)碼若碼的參數(shù)滿足式(7-38)，通過循環(huán)移位就一定能把R(x)的t個(gè)錯(cuò)誤移到n—k個(gè)監(jiān)督位上。在循環(huán)移位過程中，可用下面的定理判斷t個(gè)錯(cuò)誤是否已全部集中到碼的n—k個(gè)監(jiān)督位上，。

定理7－5設(shè)(n，k)循環(huán)碼的糾錯(cuò)能力為t，如果錯(cuò)誤限制在n-k個(gè)監(jiān)督位上，則伴隨式的重量不大于t;如果在信息位上存在錯(cuò)誤，則伴隨式的重量必大于t。捕錯(cuò)譯碼電路的實(shí)現(xiàn)見有關(guān)文獻(xiàn)。7.5.2改進(jìn)的捕錯(cuò)譯碼

前面討論的捕錯(cuò)譯碼要求接收碼字中的錯(cuò)誤集中在n－k個(gè)相鄰位上，因此，它適用于糾正突發(fā)錯(cuò)誤或一個(gè)和某些兩個(gè)隨機(jī)錯(cuò)誤(條件是n>t·k)的碼。糾正三個(gè)或三個(gè)以上的隨機(jī)錯(cuò)誤的碼一般不滿足n>t·k的條件。然而，改進(jìn)后的捕錯(cuò)譯碼可以用來糾正這樣的錯(cuò)誤圖樣，即每個(gè)錯(cuò)誤圖樣的大部分錯(cuò)誤集中在n-k個(gè)相鄰位上，而只有少數(shù)錯(cuò)誤在此n-k位跨距之外。下面討論由嵩忠雄提出的一種改進(jìn)方案。設(shè)干擾產(chǎn)生的錯(cuò)誤圖樣為E(x)＝en—1xn—1十en—2xn—2＋…＋e0

可分成兩個(gè)部分；接收碼字信息部分中的錯(cuò)誤為：EI(x)＝en－1xn－1＋…＋en－kxn－k接收碼字監(jiān)督部分中的錯(cuò)誤為Ep＝en－k－1xn－k－1＋…＋e0

接收碼字的伴隨式為(7-39)則有:(7-40)令代入式(7-40)得:Ep(x)＝S(x)＋SI(x)(7-41)式(7-41)表明，接收碼字監(jiān)督位上的錯(cuò)誤圖樣等于接收碼字的伴隨式與信息位上錯(cuò)誤的伴隨式之和。如果我們對信息位上可能的錯(cuò)型一個(gè)一個(gè)地進(jìn)行試驗(yàn)，并確定出某一個(gè)為實(shí)際錯(cuò)誤圖樣，那么監(jiān)督位上的錯(cuò)誤圖樣則可由式(7-41)求出，從而求得接收碼字R(x)的錯(cuò)誤圖樣E(x)。由上述可知，改進(jìn)捕錯(cuò)譯碼法的出發(fā)點(diǎn)是先確定接收碼字信息部分中的錯(cuò)誤圖樣。(7-42)(7-43)

若碼的糾錯(cuò)能力為t，且錯(cuò)誤圖樣重量為W[E(x)]≤t，在k個(gè)信息位上的錯(cuò)誤圖樣的重量W[EI(x)]＝W[Xn－kQj(x)]＝W(Qj(x))，則在n—k個(gè)監(jiān)督位上的錯(cuò)誤圖樣Ep（i）

(x)的重量為W[(x)]＝W[S（i）(x)＋SIj(x)]≤t－W[Qj(x)]（7-44）所以，當(dāng)式(7-44)對某個(gè)j成立時(shí)，就表示xn－k

Qj(x)是E（i）(x)在信息位上的錯(cuò)誤圖樣。而接收碼字的錯(cuò)誤圖樣為:E(x)＝xn－i

E（i）(x)＝xn－i

[xn－k

Qj(x)＋S（i）(x)＋SIj(x)](7-45)將所求得的錯(cuò)誤圖樣E(x)和R(x)模2加，可使R(x)中的錯(cuò)誤得到糾正。從錯(cuò)誤圖樣的特定結(jié)構(gòu)出發(fā)，由循環(huán)碼的通用譯碼法演變出了捕錯(cuò)譯碼法。而從碼的結(jié)構(gòu)出發(fā)，可導(dǎo)出大數(shù)邏輯譯碼法。這是一種很有效的譯碼方法，具有譯碼設(shè)備簡單，速度快的優(yōu)點(diǎn)，因而得到廣泛的應(yīng)用。7.5.3大數(shù)邏輯譯碼

1.正交一致監(jiān)督和式

設(shè)hj(j＝n-k-1,n-k-2，…，0)是循環(huán)碼的一致監(jiān)督矩陣H的行變量，則H為H＝[hn－k－1hn－k－2…h(huán)0]T又設(shè)C為任一碼字，R＝[rn－1…r0]為接收碼字，其伴隨式ST＝HRT的各分量為：(7-46)式(7－46)稱為接收碼字R的監(jiān)督和式。

若R為一碼字，則sj＝0;若R不是一個(gè)碼字，則sj≠0。

若E＝[en－1

en－2…e0]為R的信道錯(cuò)誤圖樣。由于R＝C＋E,HCT＝0T，所以：(7-47)因此，接收碼字的監(jiān)督和式，實(shí)際上是對信道錯(cuò)誤圖樣進(jìn)行監(jiān)督，而與發(fā)送的具體碼字無關(guān)。在式(7-47)中，若hj,i＝1，則說碼元位ci被監(jiān)督和式sj監(jiān)督。并把sn－k－1,sn－k－2，…，s0稱為監(jiān)督和式組。

若在(n，k)循環(huán)碼的監(jiān)督和式組中，碼元位ci(i＝n－1，n－2，…，0)被J個(gè)(J≤n－k)一致監(jiān)督和式監(jiān)督，而其它碼元位不被一個(gè)以上的監(jiān)督和式監(jiān)督，則稱此J個(gè)監(jiān)督和式為對碼元位ci正交的一致監(jiān)督和式組。

以二元(7，3)循環(huán)碼為例，其監(jiān)督方程為:(7-48)由式(7-48)得新的監(jiān)督方程組:(7-49)

由式(7-49)可見，碼元c6被所有三個(gè)監(jiān)督方程監(jiān)督，而其它任一碼元在三個(gè)監(jiān)督方程中出現(xiàn)不多于1次(可以不出現(xiàn))，因而稱式(7-49)的監(jiān)督方程正交于碼元位c6。將式(7-49)改寫成矩陣形式：令：則H0CT＝0T

稱H0為正交一致監(jiān)督矩陣。其特點(diǎn)是：與正交碼元位對應(yīng)的列為全“1”，其它任一列中“1”的個(gè)數(shù)不多于一個(gè),稱S0＝RHT0為正交伴隨式。由于循環(huán)碼的循環(huán)特性，任意碼字的循環(huán)移位仍是一個(gè)碼字，也滿足正交監(jiān)督矩陣H0。所以對最高階碼元位cn－1正交的碼字C，經(jīng)過一次循環(huán)移位后就變成了對次高階碼元位cn－2正交的碼字C（1）。不難推知，連續(xù)的循環(huán)移位可以得到對碼字的所有碼元達(dá)成正交的監(jiān)督和式。

例如，(7，3)循環(huán)碼的三個(gè)正交監(jiān)督和式為（7-50）

s00，s01，s02構(gòu)成正交伴隨式S0＝s00s01s02。S0經(jīng)過一次循環(huán)移位S0（1）的正交監(jiān)督和式為:（7-51）式(7-50)是正交于最高階碼元上的正交監(jiān)督和式，而式(7-51)是S0經(jīng)過一次循環(huán)移位S0（1）的三個(gè)正交于次高階碼元上的監(jiān)督和式。

2.一步大數(shù)邏輯譯碼法

定理7－6若(n，k)循環(huán)碼可以構(gòu)成j個(gè)正交于最高階位xn－1上的一致監(jiān)督和式，則該碼可以用來糾正t≤j/2錯(cuò)誤的所有錯(cuò)誤圖樣。

由此定理可直接得到：在可構(gòu)成j個(gè)正交監(jiān)督和式的(n，k)循環(huán)碼中，如果在正交位置上含有錯(cuò)誤，則正交伴隨式S0的重量W［S0

］>j/2；如果在正交位置上沒有錯(cuò)誤，則W［S0］≤j/2。因此，譯碼器可用一個(gè)大數(shù)邏輯門來檢測正交伴隨式的重量，當(dāng)W［S0

］>j/2時(shí)，正交位置上有錯(cuò)；當(dāng)W［S0］≤j/2時(shí)，正交位置上無錯(cuò)。即把S0的各分量作為大數(shù)邏輯門的輸入，當(dāng)這些輸入中多數(shù)為“1”時(shí)，正交位置上接收符號是錯(cuò)誤的，大數(shù)邏輯門輸出“1”，將錯(cuò)誤糾正；當(dāng)大數(shù)門的輸入中只有一半或更少個(gè)“1”時(shí)，則正交位置上沒有錯(cuò)誤，大數(shù)門輸出“0”。再利用碼的循環(huán)位移特性，可糾正接收字中所含的全部錯(cuò)誤(錯(cuò)誤個(gè)數(shù)≤j／2)。這種譯碼方法稱為一步大數(shù)邏輯譯碼法。

【例7－14】已知（7，3）循環(huán)碼的三個(gè)正交監(jiān)督和式為（7－52）試設(shè)計(jì)大數(shù)邏輯譯碼電路。

解在式(7－52)所示的方程組中，r6～r0是已知數(shù)，e6～e0是希望求解的未知數(shù)。

如果用解方程組的方法，則可以先用r6～r0計(jì)算e6～e0，這是由3個(gè)方程解7個(gè)未知數(shù)，可知答案不是惟一的。

但是，式(7－52)中除了最高位差錯(cuò)e6被全部3個(gè)方程包含外，其他任何位置的差錯(cuò)ei(i≠6)都僅被一個(gè)方程式所包含。正交一致監(jiān)督和式A=s02s01s00的重量W［A］是：如果有單個(gè)差錯(cuò)發(fā)生在最高位碼元e6上，必有W［A］=3；反之，如果單個(gè)差錯(cuò)發(fā)生在除最高位的其他任何位置，都有W［A］=1?？梢姡ㄟ^計(jì)算正交一致監(jiān)督和式A的重量W［A］，不但能發(fā)覺是否有錯(cuò)，而且可以判斷出單個(gè)差錯(cuò)是否發(fā)生在最高位。如果j>2，說明最高位存在差錯(cuò)(e6=1)；如果j<2，說明差錯(cuò)在其他位置而不在最高位上。這樣，就可以根據(jù)j大于2還是小于2來決定應(yīng)不應(yīng)該給最高位加一個(gè)糾錯(cuò)信號。上面討論的差錯(cuò)判決限于判斷最高位是否有錯(cuò)，而不能判斷其他位是否有錯(cuò)。好在循環(huán)碼碼字的循環(huán)、伴隨式的循環(huán)及差錯(cuò)圖樣的循環(huán)是同步的，只要將碼字循環(huán)一遍，差錯(cuò)圖樣也就會循環(huán)一遍，任何其他位置上的差錯(cuò)在一個(gè)循環(huán)周期里都有機(jī)會處于最高位。因此，在糾錯(cuò)能力范圍內(nèi)，只要保證最高位的差錯(cuò)能被糾正，就能保證其他位置上的差錯(cuò)被糾正。由于判決是根據(jù)j是否大于2作出的，所以稱為“大數(shù)邏輯”或“門限”。圖7－15所示為根據(jù)式(7－52)設(shè)計(jì)的大數(shù)邏輯譯碼器。大數(shù)門是一個(gè)判決電路，j>2時(shí)輸出“1”，否則輸出“0”。在開頭的7拍中，接收碼元送入7級移存器。從第8拍開始，接收碼元逐拍輸出，大數(shù)門也開始工作，對最高位r6的正確與否作出判決，并趁移存器輸出r6之際加上一個(gè)判決(糾錯(cuò))信號“1”或“0”。同時(shí)，轉(zhuǎn)換開關(guān)由S1轉(zhuǎn)向S2，接通反饋而切斷輸入，以實(shí)現(xiàn)碼字循環(huán)。經(jīng)又一個(gè)7拍后，全部碼元譯碼輸出完畢。圖7－15利用接收碼字R的大數(shù)邏輯譯碼

3.L步大數(shù)邏輯譯碼

一步大數(shù)邏輯譯碼雖然簡單易行，但實(shí)際中一步大數(shù)邏輯可譯碼并不多，且糾錯(cuò)能力也不強(qiáng)。為了擴(kuò)大應(yīng)用范圍，改善糾錯(cuò)能力，人們把正交于某一碼元的概念推廣到正交于某一碼元集合，并通過L步大數(shù)邏輯判斷逐次減少集合中碼元的個(gè)數(shù)，最后完成對某一碼元位的譯碼，這就是L步大數(shù)邏輯譯碼的思路。下面舉例說明。

【例7－15】已知（7，4）漢明碼的校驗(yàn)矩陣為

設(shè)s2、s1、s0分別表示H的第1行、第2行、第3行，試用L步大數(shù)邏輯譯碼。

解：由矩陣第1行、第2行、第3行的行的線性組合，可得一致監(jiān)督和式：

注意到s00與s０１正交于r6+r3，如果r6和r3中只有一位出錯(cuò)，可用大數(shù)門求出。同樣，s02與s03正交于r6+r4，如果r6和r4中只有一位出錯(cuò)，也可用大數(shù)門求出。將這兩個(gè)大數(shù)門的值送入第二級大數(shù)門，只有當(dāng)r6出錯(cuò)時(shí)，輸出第二級大數(shù)門的重量才是2。這一過程用了二步大數(shù)邏輯譯碼：第一步判斷集合r6、r3和r6、r4，是否有錯(cuò)，第二步才判斷r6是否有錯(cuò)。具體的電路實(shí)現(xiàn)如圖7－16所示。圖7－16二步大數(shù)邏輯譯碼電路對于L>2的L步大數(shù)邏輯譯碼，其思路與例7－15相同，只是更復(fù)雜而已。一般說來，譯碼設(shè)備的復(fù)雜性隨L指數(shù)而增加。因此實(shí)際中很少用到L>2。

比較梅吉特譯碼與大數(shù)邏輯譯碼，我們可以看到：

梅吉特譯碼基本上是一種查表法，并能提供最大似然的性能。在實(shí)際中，梅吉特譯碼器限于n-k與t都較小的碼，可以獲得的最大實(shí)際編碼增益約2.5dB(誤比特率105時(shí))。此外，梅吉特譯碼的概念不能直接擴(kuò)充至軟判決，這是它的又一不足之處。

大數(shù)邏輯譯碼簡單易行，但只能用于為數(shù)不多的大數(shù)邏輯可譯碼，其中有些碼具有較大的最小碼距，最大的編碼增益為3.5dB。大數(shù)邏輯譯碼可直接擴(kuò)展到使用軟判決的門限譯碼。

7.6

BCH碼

7.6.1多項(xiàng)式表述

因?yàn)間(x)是xn-1的一個(gè)因子，所以循環(huán)碼的生成多項(xiàng)式可以寫成如下形式：(7-53)其中,f1(x),f2(x),…,fq(x)是以g(x)為根的極小多項(xiàng)式，每一個(gè)極小多項(xiàng)式對應(yīng)于g(x)在擴(kuò)域上的一個(gè)根。設(shè)C(x)為GF(p)的一個(gè)碼字多項(xiàng)式，E(x)為錯(cuò)誤多項(xiàng)式。則接收到的多項(xiàng)式為(7-54)(7-55)對分組長度n，則有（7-56）因此，得到包含q個(gè)方程的方程組，它們只含有錯(cuò)誤圖樣的分量。如果求解該方程組能得到ej，便可以精確地確定錯(cuò)誤圖樣。能否解此方程組決定于g(x)的根的個(gè)數(shù)，即q的值。為了求解錯(cuò)誤圖樣，必須小心選取這q個(gè)方程。如果要設(shè)計(jì)能糾t個(gè)錯(cuò)誤的循環(huán)碼，應(yīng)選擇是方程組對至多t個(gè)非零ej的情況可以求解。

定義伴隨式Si=e(ri)(i=1,2,…,q)。希望選取r1,r2,…,rq使得由S1,S2,…,Sq可以求解t個(gè)錯(cuò)誤。若α是個(gè)本原元，則能糾t個(gè)錯(cuò)誤的ri的集合為｛α1,α2,α3,…,α2t｝。因此，有如下一種能確定糾t個(gè)錯(cuò)誤的BCH碼的生成多項(xiàng)式的簡單方法。對一個(gè)本原分組長度n=pm-1，確定可糾t個(gè)錯(cuò)誤的BCH碼的生成多項(xiàng)式的步驟為：

(1)選取一個(gè)次數(shù)為m的素多項(xiàng)式并構(gòu)造GF(pm)；

(2)求αi(i=1,2,…,q)的極小多項(xiàng)式fi(x)；

(3)可糾t個(gè)錯(cuò)誤的碼的生成多項(xiàng)式為（7-57）用這種方法設(shè)計(jì)的碼至少能糾t個(gè)錯(cuò)誤。但在很多情況下，這些碼所糾的錯(cuò)誤多于t個(gè)。因此，稱d=2t+1(7-58)為碼的設(shè)計(jì)距離，其最小距離為dmin≥2t+1。它的生成多項(xiàng)式次數(shù)等于n-k。

【例7－16】考慮GF(2)上的本原多項(xiàng)式p(z)=z4+z+1，構(gòu)造擴(kuò)域GF(24)。

解設(shè)α=z為本原元。GF(24)上以α的冪形式表示的元素及它們對應(yīng)的極小多項(xiàng)式在表7－8中列出。表7－8

GF(24)上的元素和對應(yīng)的極小多項(xiàng)式

【例7－17】利用表7－8確定糾t個(gè)錯(cuò)誤的BCH碼的生成多項(xiàng)式，即t=1，2，3，4，5，6，7且n=15。

解由式（7－57）可知，一個(gè)BCH碼的生成多項(xiàng)式由lcm［f1(x),f2(x),…,f2t(x)］給出。利用表7－8來獲得極小多項(xiàng)式f1(x)和f2(x)。于是糾單一錯(cuò)誤的BCH碼的生成多項(xiàng)式為因?yàn)閐egg(x)=n-k，可得n-k=4，從而給出k=11,于是得到糾單一錯(cuò)誤的BCH(15，11)碼的生成多項(xiàng)式。該碼的設(shè)計(jì)距離為d=2t+1=3,可以計(jì)算出該碼的實(shí)際最小距離dmin也是3。因此，在此情況下設(shè)計(jì)距離等于最小距離。

確定糾兩個(gè)錯(cuò)誤的BCH碼的生成多項(xiàng)式，即t=2且n=15。該BCH碼的生成多項(xiàng)式為因?yàn)閐egg(x)=n-k，可得n-k=8，從而給出k=7。于是得到糾兩個(gè)錯(cuò)誤的BCH(15，7)碼的生成多項(xiàng)式。該碼的設(shè)計(jì)距離為d=2t+1=5?？梢杂?jì)算該碼的最小距離dmin也是5。因此，在此情況下設(shè)計(jì)距離等于最小距離。

確定糾三個(gè)錯(cuò)誤的二元BCH碼的生成多項(xiàng)式，該BCH碼的生成多項(xiàng)式為表7－10碼長達(dá)25-1的二元BCH碼的生成多項(xiàng)式7.6.2矩陣表述

設(shè)BCH碼的生成多項(xiàng)式g(x)的根為(β,β2,…,β2t)∈GF(2m)，則上述2t個(gè)元素也必然是任一碼字多項(xiàng)式C(x)＝cn－1xn-1＋cn－2xn-2＋…＋c1x＋c0的根，即（7－59）其中i＝1，2，…，2t?？梢詫⑦@些不同i值的方程組寫成矩陣形式:＝０

(7－60）g(x)＝lcm（m1(x)，m2(x)，m3（x），m4（x），…，m2t(x)）＝lcm（m1(x)，m3（x），…，m2t－１(x)在(7-61)式中，可不包括下標(biāo)為偶數(shù)的最小多項(xiàng)式。于是BCH碼的H可簡化成:（7－62）式(7－62)中，若