第六章循環(huán)碼譯碼第一頁(yè)，共102頁(yè)?！?.1循環(huán)碼譯碼的一般原理

設(shè)發(fā)送的碼字是C(x)=(cn-1xn-1+…+c1x+c0)(今后不再嚴(yán)格區(qū)分碼字與碼多項(xiàng)式)，通過(guò)q進(jìn)制輸入和輸出的信道后，譯碼器輸入端得到的是R(x)=C(x)+E(x)=(rn-1

xn-1+…+r1x+r0)ri=ci+ei式中，E(x)=(en-1xn-1+…+e1x+e0)是信道產(chǎn)生的錯(cuò)誤圖樣，應(yīng)當(dāng)指出，上述這些式中的ci、ri、ei均是GF(q)中的元素，也就是我們這里僅討論硬判決時(shí)的譯碼方法。

第二頁(yè)，共102頁(yè)。

譯碼器的主要任務(wù)就是如何從R(x)中得到正確的估計(jì)錯(cuò)誤圖樣ê(x)=E(x)，然后得到C(x)，并由此得到信息組m(x)。如同所有線性分組碼的譯碼一樣，循環(huán)碼的譯碼也分為以下3步：(1)計(jì)算R(x)的伴隨式S(x)；(2)根據(jù)伴隨式S(x)找出估計(jì)錯(cuò)誤圖樣ê(x)；第三頁(yè)，共102頁(yè)。

(3)R(x)-ê(x)=，得到譯碼器輸出的估值碼字，并送出譯碼器給用戶。若=C，則譯碼正確，否則譯碼錯(cuò)誤。如果是非系統(tǒng)碼，則還必須由中得到估值信息組；如果是系統(tǒng)碼，這一步可省略。由于循環(huán)碼的循環(huán)特性，在上述各步運(yùn)算中，往往比非循環(huán)碼的計(jì)算要簡(jiǎn)單。第四頁(yè)，共102頁(yè)。

一、伴隨式計(jì)算和錯(cuò)誤的檢測(cè)設(shè)發(fā)送的碼字C=(cn-1，cn-2，…，c1，c

0)，信道產(chǎn)生的錯(cuò)誤圖樣為E=(en-1，en-2，…，e1，e0)，譯碼器收到的n重

R=C+E=(cn-1+en-1，cn-2+en-2，…，

c1+e1，c

0+e0)=(rn-1，rn-2，…，r1，r0)ri=ci+ei第五頁(yè)，共102頁(yè)。

由伴隨式定義可知，相應(yīng)的伴隨式是

S=R·HT=(C+E)HT=EHT

可知伴隨式S僅與錯(cuò)誤圖樣有關(guān)，而與發(fā)送的碼字無(wú)關(guān)，由它可計(jì)算出錯(cuò)誤圖樣E。第六頁(yè)，共102頁(yè)。

設(shè)［n，k］循環(huán)碼的生成多項(xiàng)式為g(x)，且

xn-1=g(x)h(x)，g(x)=n-k。該碼的一致校驗(yàn)矩陣由式(5.1.9)可知為第七頁(yè)，共102頁(yè)。所以第八頁(yè)，共102頁(yè)。

由此式可知相應(yīng)的多項(xiàng)式表示為S(x)≡C(x)+E(x)≡R(x)≡E(x)

(modg(x))(6.1.1)

或

S(x)=Rg(x)+g(x)q(x)=Eg(x)+g(x)q1(x)(6.1.2)

式中，Rg(x)和Eg(x)分別是R(x)和E(x)被g(x)除后所得的余式。

第九頁(yè)，共102頁(yè)。

二、伴隨式計(jì)算電路性質(zhì)及一般譯碼器用g(x)除法電路計(jì)算伴隨式的電路(伴隨式計(jì)算電路)有如下一個(gè)很重要的特點(diǎn)。

定理6.1.1若S(x)是R(x)的伴隨式，則R(x)的循環(huán)移位xR(x)(在模xn-1運(yùn)算下)的伴隨式S1(x)，是S(x)在伴隨式計(jì)算電路中無(wú)輸入時(shí)(自發(fā)運(yùn)算)右移一位的結(jié)果，即

S1(x)≡xS(x)(modg(x))(6.1.3)

第十頁(yè)，共102頁(yè)。證明由伴隨式定義可知xR(x)之伴隨式為S1(x)≡xR(x)

(modg(x))=xRg(x)+q1(x)g(x)(6.1.4)由式(6.1.2)可知：xS(x)=xRg(x)+xq(x)g(x)該式減去式(6.1.4)可得：xS(x)-S1(x)=g(x)(xq(x)-q1(x))≡0

(modg(x))因此S1(x)≡xS(x)(modg(x))第十一頁(yè)，共102頁(yè)。推論6.1.1xjR(x)的伴隨式Sj(x)≡xjS(x)(modg(x))，j=0，1，…，n-1。而任意多項(xiàng)式a(x)乘R(x)所對(duì)應(yīng)的伴隨式Sa(x)≡a(x)S(x)(modg(x))(6.1.5)第十二頁(yè)，共102頁(yè)。在q進(jìn)制時(shí)，若碼要糾正≤t個(gè)錯(cuò)誤，則錯(cuò)誤圖樣代表共有(6.1.6)個(gè)。譯碼時(shí)，只要知道此代表圖樣的伴隨式，該類其它錯(cuò)誤圖樣的伴隨式都可由此代表圖樣伴隨式在伴隨式計(jì)算電路中得到。這樣，就使得循環(huán)碼譯碼器的錯(cuò)誤圖樣識(shí)別電路大為簡(jiǎn)化，由原來(lái)識(shí)別(6.1.7)個(gè)圖樣減少到N1個(gè)。第十三頁(yè)，共102頁(yè)。例如二進(jìn)制碼，n=63，t=4，由式(6.1.6)和式(6.1.7)計(jì)算譯碼器所需識(shí)別的錯(cuò)誤圖樣個(gè)數(shù)如表6-1所示。表6-1N1，N2比較表第十四頁(yè)，共102頁(yè)。例6.1二進(jìn)制［7，4，3］循環(huán)漢明碼，它的g(x)=x3+x+1，相應(yīng)的校驗(yàn)矩陣第十五頁(yè)，共102頁(yè)。由式(6.1.6)知，構(gòu)造此譯碼器的錯(cuò)誤圖樣識(shí)別電路時(shí)，只要識(shí)別一個(gè)圖樣E6=(1000000)就夠了，該圖樣的伴隨式就是H的第一列(101)?？芍?，識(shí)別E6錯(cuò)誤圖樣的識(shí)別電路就是一個(gè)檢測(cè)伴隨式是否是(101)的電路。由此可得如圖6-1所示的譯碼電路。圖中的伴隨式計(jì)算電路就是一個(gè)g(x)=x3+x+1的除法電路，而有3個(gè)輸入端的與門和反相器，組成了識(shí)別(101)的伴隨式識(shí)別器。第十六頁(yè)，共102頁(yè)。圖6-1［7，4，3］循環(huán)漢明碼譯碼器第十七頁(yè)，共102頁(yè)。譯碼器的譯碼過(guò)程如下：(1)開(kāi)始譯碼時(shí)門開(kāi)，移存器內(nèi)容全為0。收到的R(x)=r6x6+…+r0，以高次項(xiàng)系數(shù)(r6)至低次項(xiàng)系數(shù)的次序，一方面送入7級(jí)緩沖器，一方面送入g(x)除法電路計(jì)算伴隨式。7次移位后，R(x)的系數(shù)全部存入緩存器，g(x)電路也得到了伴隨式S0(x)，此時(shí)門關(guān)，禁止輸入。第十八頁(yè)，共102頁(yè)。(2)若S0(x)≡1+x2≡x6

(modg(x))，說(shuō)明E(x)=x6，

r6位有錯(cuò)，伴隨式計(jì)算(g(x)除法器)電路中的D0、D1、D2存貯的值是(101)，它就是S0(x)=1+x2之系數(shù)。D1的0經(jīng)反相后成了1，與門3個(gè)輸入端全為1，呈打開(kāi)狀態(tài)。這時(shí)譯碼器繼續(xù)移位，r6從緩存器輸出，與門也輸出一個(gè)信號(hào)“1”與r6相加，使r

6由原來(lái)的1變成0，或由0變成1，糾正了r6的錯(cuò)誤：r6+1=c6+e6+1=c6+1+1=c6，得到了原來(lái)發(fā)送的碼元。此時(shí)與門的糾錯(cuò)信號(hào)“1”也反饋到伴隨式計(jì)算電路輸入端(圖中虛線所示)，對(duì)伴隨式進(jìn)行修正，以消去該錯(cuò)誤對(duì)伴隨式的影響。第十九頁(yè)，共102頁(yè)。這由于R(x)=rn-1

xn-1+…+r1x+r

0

相應(yīng)的伴隨式是S0(x)。糾錯(cuò)后R(x)成為R′1(x)=(rn-1+1)xn-1+…+r1x+r0

與R′1(x)相應(yīng)的伴隨式S′1(x)≡S0(x)+xn-1

(modg(x))因?yàn)榧m錯(cuò)是在第n+1次移位進(jìn)行的，所以R′1(x)成為R1(x)=xR′1(x)≡rn-2

xn-1+…+r0x+rn-1+1(modxn-1)第二十頁(yè)，共102頁(yè)。相應(yīng)的伴隨式S1(x)≡xS′1(x)≡xS0(x)+xn≡xS0(x)+1

(modg(x))

由于S1(x)是xR′1(x)的伴隨式，而xS0(x)是xR(x)的伴隨式，也就是xE(x)的伴隨式，因此為了得到真正的xR(x)的伴隨式，就必須從S1(x)中消去“1”，也就是在伴隨式計(jì)算電路輸入端加1。第二十一頁(yè)，共102頁(yè)。(3)若E(x)=x5，則S0(x)≡x5≡x2+x+1

(modg(x))，此時(shí)與門不打開(kāi)，說(shuō)明r6正確。這時(shí)伴隨式計(jì)算電路和緩存器各移位一次，r6輸出，r5移到緩存器最右一級(jí)，伴隨式計(jì)算電路得到的伴隨式是S1(x)≡xS0(x)≡xE(x)≡x2+1

(modg(x))第二十二頁(yè)，共102頁(yè)。因此再移動(dòng)一次，與門輸出的糾正信號(hào)“1”正好與緩存器輸出的r5=c

5+1相加，得到了c5，從而完成了糾錯(cuò)。若r5不錯(cuò)，則重復(fù)上述過(guò)程一直到譯完一個(gè)碼字為止。該譯碼過(guò)程可用表6-2表示，已知R(x)=x6+x+1，E(x)=x4。由該表知，到第10個(gè)節(jié)拍，與門輸出一個(gè)“1”糾正r4，最后譯碼器輸出碼字(1010011)。第二十三頁(yè)，共102頁(yè)。表6-2圖6-1譯碼器譯碼過(guò)程第二十四頁(yè)，共102頁(yè)。從上述譯碼過(guò)程可知，譯一組碼共需14(2n=14)個(gè)節(jié)拍，僅當(dāng)?shù)谝唤M的R(x)移出7級(jí)緩存器后，才能接收第二組的R(x)。為了使譯碼連續(xù)，必須再加一個(gè)伴隨式計(jì)算電路，如圖6-2。第二十五頁(yè)，共102頁(yè)。圖6-2［7，4］碼完整譯碼器第二十六頁(yè)，共102頁(yè)。開(kāi)始工作時(shí)，所有移存器的存數(shù)全為0，門1開(kāi)、門2關(guān)。當(dāng)k=4次移位后，4級(jí)緩存器接收了前面的4個(gè)信息位(對(duì)系統(tǒng)碼而言)，此時(shí)門1關(guān)，并使4級(jí)緩沖器停止移位。再移動(dòng)n-k=3次后，g(x)除法電路得到了伴隨式S0(x)，此時(shí)門2開(kāi)，把上邊g(x)除法電路中的伴隨式送到下面的伴隨式計(jì)算電路中，隨即門2關(guān)閉，且上邊g(x)除法電路立即清洗為0。門1再次打開(kāi)，4級(jí)緩存器一邊送出第一組的信息，一邊接收第二組R(x)的前k位信息組。與此同時(shí)，上邊伴隨式計(jì)算電路計(jì)算第二組R(x)的伴隨式，而下邊伴隨式計(jì)算電路，對(duì)第一組R(x)中的信息元進(jìn)行糾錯(cuò)。第二十七頁(yè)，共102頁(yè)。三、擴(kuò)展?jié)h明碼的譯碼［2m，2m-1-m，4］擴(kuò)展?jié)h明碼是由［2m-1，2m-1-m，3］漢明碼加一個(gè)全校驗(yàn)位得到。它的碼字(cn-1，…，c0，c∞)中前n個(gè)碼元(cn-1，…，c0)是漢明碼的一個(gè)碼字，c∞是全校驗(yàn)位。擴(kuò)展?jié)h明碼的碼長(zhǎng)是8的整數(shù)倍，特別適用于計(jì)算機(jī)或微機(jī)組成的數(shù)據(jù)處理或數(shù)據(jù)傳輸系統(tǒng)中。第二十八頁(yè)，共102頁(yè)。擴(kuò)展?jié)h明碼能糾正一個(gè)錯(cuò)誤同時(shí)發(fā)現(xiàn)兩個(gè)錯(cuò)誤，雖然它不是循環(huán)碼，但它譯碼電路的主要部分與循環(huán)漢明碼的譯碼器相同，只要加上檢錯(cuò)電路即可。如［8，4，4］擴(kuò)展碼，只要在［7，4，3］循環(huán)漢明碼譯碼器中，加一個(gè)檢錯(cuò)電路即成，如圖6-4。圖中，(a)部分的電路基本上與圖6-1同，是循環(huán)漢明碼的譯碼器，不同的是多加了一個(gè)全校驗(yàn)位檢查電路，它由一個(gè)級(jí)移存器加一個(gè)模2加法器組成。圖中，(b)部分電路是一個(gè)檢錯(cuò)電路。該譯碼器的譯碼過(guò)程如下：

第二十九頁(yè)，共102頁(yè)。圖6-4［8，4，4］擴(kuò)展碼譯碼器第三十頁(yè)，共102頁(yè)。(1)開(kāi)始時(shí)所有寄存器中的內(nèi)容為0，門1和門2開(kāi)。移位4次后門2關(guān)，R(x)=r6x6+…+r0+r∞中的前4位(r

6，r

5，r4，r3)存入4級(jí)緩存器中，它就是待糾錯(cuò)的4個(gè)信息元。移動(dòng)7次后門1關(guān)，R(x)的前7個(gè)碼元(r6，r5，r4，r3，r2，r1，r0)，已全部送入［7，4，3］碼所決定的伴隨式計(jì)算電路中，得到了伴隨式(s2，s1，s0)。第8次移位后，在全校驗(yàn)位檢查電路中得到了全校驗(yàn)的結(jié)果s∞，此時(shí)譯碼器不再輸入。第三十一頁(yè)，共102頁(yè)。(2)當(dāng)s∞=0、(s0，s1，s2)=(000)時(shí)，譯碼器認(rèn)為接收R(x)無(wú)誤，把4級(jí)緩存器中的信息元輸出。(3)當(dāng)s∞=1、(s0，s1，s2)≠(000)時(shí)，譯碼器認(rèn)為有一個(gè)錯(cuò)誤，此時(shí)糾錯(cuò)部分的譯碼電路，按上面講的漢明碼的方法進(jìn)行糾錯(cuò)譯碼，4次移位后已全部輸出已糾正過(guò)的信息元。第三十二頁(yè)，共102頁(yè)。(4)s∞=0、(s0，s1，s2)≠(000)，譯碼器認(rèn)為出現(xiàn)了偶數(shù)個(gè)錯(cuò)誤，錯(cuò)誤告警電路輸出一信號(hào)給用戶，表示檢測(cè)到錯(cuò)誤。(5)s∞=1、(s0，s1，s2)全為0時(shí)，譯碼器認(rèn)為出現(xiàn)了一個(gè)以上的奇數(shù)個(gè)錯(cuò)誤，錯(cuò)誤告警電路也輸出一個(gè)信號(hào)給用戶。當(dāng)然，為了使譯碼連續(xù)，在圖6-4的(a)部分電路中，也必須有兩個(gè)伴隨式計(jì)算電路，這與圖6-2相同。

第三十三頁(yè)，共102頁(yè)。［2m-1，2m-2-m，4］增余刪信漢明碼的譯碼電路與擴(kuò)展?jié)h明碼的譯碼電路基本相同，只不過(guò)全校驗(yàn)位的結(jié)果s∞也要輸入到錯(cuò)誤圖樣的識(shí)別電路與門中，對(duì)［7，3，4］碼來(lái)說(shuō)就是輸入到圖6-4(a)中有3個(gè)輸入端的與門，如虛線所示，其它情況相同。第三十四頁(yè)，共102頁(yè)。四、縮短循環(huán)碼的譯碼縮短i個(gè)信息位的［n-i，k-i］縮短循環(huán)碼，是在［n，k］循環(huán)碼中選前i個(gè)信息位為0的碼字組成。若［n，k］循環(huán)碼的碼字

C(x)=cn-1

xn-1+cn-2

xn-2+…+c0

則［n-i，k-i］縮短循環(huán)碼的碼字C＇(x)=cn-1-ixn-1-i+…+c

0

因此，縮短循環(huán)碼的譯碼器必須在原［n，k］循環(huán)碼譯碼器基礎(chǔ)上作如下修正：第三十五頁(yè)，共102頁(yè)。(1)k級(jí)緩存器改為k-i級(jí)；(2)為了與(1)的改動(dòng)相適應(yīng)，R(x)應(yīng)自動(dòng)乘以xi，然后再輸入伴隨式計(jì)算電路。如［7，4］循環(huán)漢明碼縮短一位變成［6，3］碼，它的譯碼器就是把圖6-2中的譯碼器作如下變動(dòng)：R(x)從圖中(A)虛線所示的地方輸入，這相當(dāng)于R(x)自動(dòng)乘以x，4級(jí)緩存器變成3級(jí)。第三十六頁(yè)，共102頁(yè)?！?.2捕錯(cuò)譯碼

一、基本工作原理設(shè)碼字C(x)是某一糾t個(gè)錯(cuò)誤的［n，k］循環(huán)碼的碼字，當(dāng)它通過(guò)有擾信道到達(dá)接收端譯碼器時(shí)成為R(x)=C(x)+E(x)。相應(yīng)的伴隨式S(x)≡R(x)≡E(x)≡EI(x)+Ep(x)

(modg(x))

式中EI(x)=en-1

xn-1+…+en-kxn-kEp(x)=en-k-1

xn-k-1+…+e0第三十七頁(yè)，共102頁(yè)。

分別是在碼字信息組(或前k位)和校驗(yàn)位(或后n-k位)上的錯(cuò)誤圖樣。若E(x)=n-k-1，即所有≤t個(gè)錯(cuò)誤集中在校驗(yàn)元的n-k位上，則EI(x)=0，E(x)=Ep(x)。Ep(x)的最高次數(shù)是n-k-1，而g(x)=n-k，所以當(dāng)E(x)=Ep(x)被g(x)除后的余式仍為Ep(x)，即

S(x)≡E(x)=Ep(x)(modg(x))第三十八頁(yè)，共102頁(yè)。

對(duì)于糾t個(gè)錯(cuò)誤的循環(huán)碼來(lái)說(shuō)，必須使t個(gè)錯(cuò)誤能連續(xù)地出現(xiàn)在n-k位以內(nèi)，這等價(jià)于要求有連續(xù)k位碼元無(wú)錯(cuò)，或錯(cuò)誤圖樣中連續(xù)k位的值為0。由于t個(gè)錯(cuò)誤均勻分布在n位上時(shí)最難滿足連續(xù)k位無(wú)錯(cuò)這一要求，因此可以用捕錯(cuò)方法譯碼的［n，k］循環(huán)碼，n、k、t之間必須滿足下列條件：k＜n／t或t＜n／k，或R＜1／t(6.2.1)第三十九頁(yè)，共102頁(yè)。

定理6.2.1糾正t個(gè)錯(cuò)誤的GF(q)上的［n，k］循環(huán)碼，捕錯(cuò)譯碼過(guò)程中已把t個(gè)錯(cuò)誤集中在Ri(x)的最低次n-k位以內(nèi)的充要條件是此時(shí)的伴隨式重量(Si(x))≤t(6.2.2)證明若錯(cuò)誤已集中在n-k位低次位碼元段以內(nèi)，則Si(x)≡xiE(x)=Ei(x)=Eip(x)

(modg(x))Si(x)=Eip(x)第四十頁(yè)，共102頁(yè)。碼只能糾正t個(gè)錯(cuò)誤，若錯(cuò)誤圖樣E(x)是一個(gè)可糾正的錯(cuò)誤圖樣，則w(E(x))≤t，因而E(x)的循環(huán)移位i次的錯(cuò)誤圖樣Ei(x)的重量也必小于等于t，所以w(Si(x))=w(Ei(x))≤t第四十一頁(yè)，共102頁(yè)。反之，若w(Si(x))≤t，則錯(cuò)誤一定集中在n-k位低次位碼元段內(nèi)。設(shè)錯(cuò)誤沒(méi)有集中在該段以內(nèi)，則Ei(x)≥(x)g(x)，由此Ei(x)=q(x)g(x)+Si(x)Ei(x)-Si(x)=q(x)g(x)=Ci(x)Ci(x)是g(x)的倍式，由循環(huán)碼性質(zhì)知它必是［n，k］循環(huán)碼的一個(gè)碼字。因而w(Ei(x)+(-Si(x)))=w(C(x))≥d=2t+1由三角不等式(3.1.2)式可知w(Ei(x))+w(-Si(x))≥w(Ei(x)+(-Si(x)))

≥2t+1第四十二頁(yè)，共102頁(yè)。因?yàn)閣(Ei(x))≤t所以w(-Si(x))≥t+1＞t由于w(-Si(x))=w(Si(x))，因此上式與假設(shè)w(Si(x))≤t相矛盾，因而錯(cuò)誤沒(méi)有集中在n-k低次位以內(nèi)的反證法假設(shè)不能成立，故錯(cuò)誤集中在n-k低次位內(nèi)。

第四十三頁(yè)，共102頁(yè)。例6.2二進(jìn)制［15，7，5］循環(huán)碼，生成多項(xiàng)式g(x)=x8+x7+x6+x4+1，能糾正兩個(gè)錯(cuò)誤。t=2＜15／7滿足捕錯(cuò)譯碼的必要條件式(6.2.1)，可以用捕錯(cuò)譯碼方法譯碼，它的譯碼電路如圖6-5。其譯碼過(guò)程如下：第四十四頁(yè)，共102頁(yè)。圖6-5［15，7，5］循環(huán)碼捕錯(cuò)譯碼電路第四十五頁(yè)，共102頁(yè)。(1)開(kāi)始工作時(shí)，所有移存器和緩存器清洗為0，門2、門3開(kāi)，門1、門4和門5關(guān)閉。n=15次移位后，R(x)的15個(gè)碼元全部移入(8+7)=15級(jí)緩存器，信息元在前7級(jí)，同時(shí)伴隨式計(jì)算電路也完成了伴隨式計(jì)算得到了S0(x)。若S0(x)=0，說(shuō)明無(wú)錯(cuò)，打開(kāi)門5，輸出緩存器中的7個(gè)信息元。若S0(x)≠0，則進(jìn)行以下各步。

第四十六頁(yè)，共102頁(yè)。(2)此時(shí)門2關(guān)，門1開(kāi)，若w(S0(x))≤2，檢測(cè)電路檢測(cè)到伴隨式的重量≤2，打開(kāi)門4，關(guān)閉門3。(3)若w［S0(x)］＞2，則15級(jí)緩存器和g(x)除法電路都循環(huán)移位一次，并檢查w［S1(x)］的重量，若仍大于2，則繼續(xù)循環(huán)移位。［n，k］循環(huán)碼的一般捕錯(cuò)譯碼器如圖6-6和圖6-7，它們分別稱為第一類和第二類捕錯(cuò)譯碼器。第四十七頁(yè)，共102頁(yè)。圖6-6［n，k］循環(huán)碼的第一類捕錯(cuò)譯碼器第四十八頁(yè)，共102頁(yè)。圖6-7［n，k］循環(huán)碼的第二類捕錯(cuò)譯碼器第四十九頁(yè)，共102頁(yè)。第二類譯碼器與第一類的差別，僅在于第二類譯碼器是把接收到的R(x)自動(dòng)乘以xn-k后，再進(jìn)入g(x)除法電路計(jì)算伴隨式，即R(x)從g(x)電路的最高次位送入。所以

R(x)xn-k≡(rn-1

xn-1+rn-2

xn-2+…+r0)xn-k

≡rn-1

xn-k-1+rn-2

xn-k-2+…+rk+rk-1xn-1

+…+r1xn-k+1+r0xn-k

(mod

xn-1)(6.2.3)第五十頁(yè)，共102頁(yè)。二、捕錯(cuò)譯碼的修正捕錯(cuò)譯碼是假定錯(cuò)誤能集中在n-k段以內(nèi)的前提下進(jìn)行的，要求［n，k］循環(huán)碼必須滿足式(6.2.1)的必要條件。但是，能滿足此條件的糾隨機(jī)錯(cuò)誤的循環(huán)碼很少，只有糾正一個(gè)錯(cuò)誤的循環(huán)漢明碼和［15，7，5］碼等，而絕大部分循環(huán)碼均不滿足?？墒?，有些循環(huán)碼如［15，5，7］碼，［23，12，7］Golay碼及［17，9，5］QR碼等，雖不滿足式(6.2.1)的條件，但k僅比n／t稍大或相等，也就是說(shuō)在譯碼過(guò)程中不能把錯(cuò)誤全部集中在n-k個(gè)碼元段以內(nèi)，而有個(gè)別錯(cuò)誤可能在其它碼元位上。為了解決此問(wèn)題，必須對(duì)捕錯(cuò)譯碼加以適當(dāng)修正。第五十一頁(yè)，共102頁(yè)。譯碼過(guò)程中，若譯碼器能把大部分錯(cuò)誤捕捉到n-k個(gè)碼元段以內(nèi)，同時(shí)使個(gè)別錯(cuò)誤進(jìn)入某幾個(gè)預(yù)先指定的位上，則也能確定此時(shí)的錯(cuò)誤圖樣。當(dāng)然，為了實(shí)現(xiàn)這種運(yùn)算必須附加一些電路，以確定錯(cuò)誤是否在某幾個(gè)指定的位置。第五十二頁(yè)，共102頁(yè)。設(shè)［n，k］循環(huán)碼能糾正t個(gè)錯(cuò)誤，生成多項(xiàng)式是g(x)。譯碼器收到R(x)后，計(jì)算伴隨式S0(x)≡E(x)=EI(x)+Ep(x)≡SI(x)+Ep(x)(mod

g(x))SI(x)≡EI(x)=en-1

xn-1+…+en-kxn-k

(mod

g(x))Ep(x)≡So(x)-SI(x)

(mod

g(x))(6.2.4)第五十三頁(yè)，共102頁(yè)。式中，SI(x)是R(x)前k位(對(duì)系統(tǒng)碼來(lái)說(shuō)就是信息位)碼段中錯(cuò)誤圖樣EI(x)的伴隨式。由上式知，若EI(x)及其SI(x)是已知的，則可根據(jù)式(6.2.4)得到R(x)中后n-k位內(nèi)(校驗(yàn)位)的錯(cuò)誤圖樣Ep(x)，從而確定出原來(lái)的錯(cuò)誤圖樣E(x)=EI(x)+Ep(x)。設(shè){Qj(x)}是次數(shù)小于等于k-1次的二進(jìn)制多項(xiàng)式集合，SIj(x)≡xn-k

Qj(x)

(mod

g(x))Ij=0，1，…第五十四頁(yè)，共102頁(yè)。是xn-k

Qj(x)的伴隨式，即如果在前k位上錯(cuò)誤圖樣EI(x)=xn-k

Qj(x)，則SIj(x)就是它的伴隨式。因此，如果任何一個(gè)重量≤t的錯(cuò)誤圖樣E(x)，或它的i次循環(huán)移位xiE(x)=Ei(x)，在前k位碼段內(nèi)與{Qj(x)}中的任一個(gè)相一致，則把此時(shí)的SIj(x)與此時(shí)Ei(x)的伴隨式Si(x)相減，由式(6.2.4)知：

(6.2.5)第五十五頁(yè)，共102頁(yè)。例6.3［23，12，7］Golay碼，它的生成多項(xiàng)式g(x)=x11+x10+x6+x5+x4+x2+1。該碼若用循環(huán)碼的其它方法譯碼比較復(fù)雜，但用修正捕錯(cuò)譯碼則比較簡(jiǎn)單。該碼的n、k與t之間關(guān)系不滿足式(6.2.1)，不能用捕錯(cuò)譯碼，必須用修正方法。首先選擇在前k位中的覆蓋多項(xiàng)式集合{Qj(x)}，經(jīng)分析可知應(yīng)選{0，x5，x6}〔2〕。其中，x5，x6是特定在信息位置上的錯(cuò)誤(對(duì)系統(tǒng)碼而言)，而0表示錯(cuò)誤能全部集中在后n-k位內(nèi)，不需要在前k位上指定錯(cuò)誤的情況。第五十六頁(yè)，共102頁(yè)。由{0，x5，x6}可得：xn-kQ1(x)=x110=0xn-kQ2(x)=x11x5=x16xn-kQ3(x)=x11x6=x17由此得到相應(yīng)的

(x)=0

(mod

g(x))

(x)≡x16≡x9+x8+x6+x5+x2+x

(mod

g(x))

(x)≡x17≡x10+x9+x7+x6+x3+x2

(mod

g(x))第五十七頁(yè)，共102頁(yè)。圖6-8［23，12］碼修正捕錯(cuò)譯碼器第五十八頁(yè)，共102頁(yè)。(1)開(kāi)始時(shí)所有移存器中的存數(shù)均清洗為0，開(kāi)關(guān)K1、K2和K5接至D=0的位置，K3和K4接至E=0的位置。接收到的R(x)一方面送入23(=11+12)級(jí)緩存器中，一方面送入伴隨式計(jì)算電路計(jì)算伴隨式。23次移位后，得到伴隨式S0(x)=s10x10+s9x9+…+s0

把它送至3個(gè)錯(cuò)誤圖樣檢測(cè)電路；第五十九頁(yè)，共102頁(yè)。(2)開(kāi)關(guān)K1、K2和K5接到D=1的位置，K3和K4仍在E=0的位置，由錯(cuò)誤圖樣檢測(cè)電路檢測(cè)可糾正的錯(cuò)誤圖樣：①若w(S0(x))≤3，認(rèn)為錯(cuò)誤全在后11位中，且錯(cuò)誤圖樣就是S0(x)，此時(shí)T1=1導(dǎo)致E′=1，K3和K4接至E=1位置，并在移位過(guò)程中對(duì)11級(jí)緩存器的輸出進(jìn)行糾錯(cuò)。第六十頁(yè)，共102頁(yè)。②若w(S0(x)-SI1(x))≤2，則

S0(x)-SI1(x)=(s10x10+s9x9+…+s1x+s0)-(x9+x8+x6+x5+x2+x)

=s10x10+s9x9+s8x8+s7x7+s6x6+s5x5

+s4x4+s3x3+s2x2+s1x+s0第六十一頁(yè)，共102頁(yè)。③若w(S0(x)-SI2(x))≤2，則S0(x)-SI2(x)=(s10x10+s9x9+…+s1x+s0)-(x10+x9+x7+x6+x3+x2)

=s10x10+s9x9+s8x8+s7x7+s6x6+s5x5

+s4x4+s3x3+s2x2+s1x+s0第六十二頁(yè)，共102頁(yè)。④若w(S0(x))＞3，或w(S0(x)-SI1(x))＞2，或w(S0(x)-SI2(x))＞2，則進(jìn)行下一步；(3)把23級(jí)緩存器和伴隨式計(jì)算電路同時(shí)循環(huán)移位一次，對(duì)新得到的伴隨式S1(x)，進(jìn)行如同第(2)步的檢查；

第六十三頁(yè)，共102頁(yè)。(4)當(dāng)緩存器和伴隨式計(jì)算電路共移位2n次后，譯完了一個(gè)碼字。此時(shí)K1、K2和K5接至D=0的位置，K3和K4接到E=0的位置；(5)送入第二組R(x)，同時(shí)第一組已糾過(guò)錯(cuò)的碼元由23級(jí)緩存器輸出。所以，接收到的R(x)從輸入譯碼器直至輸出完為止，共需移位3n(3×23)次。第六十四頁(yè)，共102頁(yè)。三、覆蓋多項(xiàng)式的數(shù)目與建立無(wú)論是對(duì)二進(jìn)制還是q進(jìn)制碼，修正捕錯(cuò)譯碼器的復(fù)雜性主要決定于覆蓋多項(xiàng)式集合{Qj(x)}中，覆蓋多項(xiàng)式數(shù)目j的多少，若j過(guò)大，則譯碼器太復(fù)雜而不能實(shí)用。對(duì)于一個(gè)特定的循環(huán)碼是否一定能找到覆蓋多項(xiàng)式？若能找到，則應(yīng)如何找{Qj(x)}？最小的j應(yīng)是多少？這些是捕錯(cuò)譯碼能否實(shí)用的關(guān)鍵問(wèn)題。第六十五頁(yè)，共102頁(yè)。對(duì)于滿足式(6.2.1)的碼，也就是錯(cuò)誤能全部集中到連續(xù)的n-k位以內(nèi)，或能保證連續(xù)k位無(wú)錯(cuò)，則覆蓋多項(xiàng)式必定存在，就是Q0(x)=0，j=1；如果碼不滿足式(6.2.1)，但滿足以下關(guān)系式：

R＜2／t或2n／t＞k(6.2.7)第六十六頁(yè)，共102頁(yè)。引理6.2.1對(duì)于糾t個(gè)錯(cuò)誤的GF(q)上的［n，k］循環(huán)碼，當(dāng)且僅當(dāng)R＜2／t時(shí)，覆蓋多項(xiàng)式集合必存在。表6-3〔3，4〕給出了某些二進(jìn)制循環(huán)碼的覆蓋多項(xiàng)式集合及大小，表中僅列出了{(lán)Qj(x)}中除0以外的所有單項(xiàng)式，并且表中還列出了某些t＞3二進(jìn)制循環(huán)碼的覆蓋多項(xiàng)式，有關(guān)尋找這些覆蓋多項(xiàng)式的詳細(xì)討論，請(qǐng)參閱文獻(xiàn)［3、4］。第六十七頁(yè)，共102頁(yè)。表6-3某些二進(jìn)制循環(huán)碼的覆蓋多項(xiàng)式第六十八頁(yè)，共102頁(yè)?！?.3大數(shù)邏輯譯碼原理

循環(huán)碼譯碼器的復(fù)雜性主要決定于碼的代數(shù)結(jié)構(gòu)。糾單個(gè)錯(cuò)誤的漢明碼、糾單個(gè)突發(fā)錯(cuò)誤的循環(huán)碼，以及某些糾錯(cuò)能力較低的碼，可以用以前所介紹的比較簡(jiǎn)單的方法如捕錯(cuò)譯碼。但是，對(duì)絕大多數(shù)糾多個(gè)隨機(jī)錯(cuò)誤的循環(huán)碼來(lái)說(shuō)，卻沒(méi)有如此簡(jiǎn)單的譯碼方法。不過(guò)，有一類循環(huán)碼的子類，碼的結(jié)構(gòu)比較特殊，可以用較簡(jiǎn)單的大數(shù)邏輯方法譯碼，這類碼稱為大數(shù)邏輯可譯碼。第六十九頁(yè)，共102頁(yè)。

大數(shù)邏輯譯碼是1954年里德(Reed)，在譯里德-馬勒爾(Reed-Muller，RM)碼時(shí)提出的一種較簡(jiǎn)單的譯碼方法〔1，2〕?？墒菍?duì)于一般碼長(zhǎng)而言，能用大數(shù)邏輯方法譯碼的大數(shù)邏輯可譯碼，其糾錯(cuò)能力和碼率都稍次于有相同參數(shù)的其它碼如BCH碼，但由于它的譯碼算法和設(shè)備均比相應(yīng)的BCH碼譯碼方法要簡(jiǎn)單，因此在實(shí)際中有較廣的應(yīng)用。第七十頁(yè)，共102頁(yè)。一、大數(shù)邏輯譯碼的基本概念通過(guò)以下例子介紹二進(jìn)制循環(huán)碼的大數(shù)邏輯譯碼的基本思想。［7，3，4］增余刪信漢明碼，它的生成多項(xiàng)式g(x)=(x+1)(x3+x+1)=x4+x3+x2+1，校驗(yàn)矩陣是第七十一頁(yè)，共102頁(yè)。設(shè)接收的n重R=C+E，C=(c6，c5，…，c0)是發(fā)送的碼字，E=(e6，e

5，…，e0)是錯(cuò)誤圖樣。相應(yīng)的伴隨式第七十二頁(yè)，共102頁(yè)。對(duì)伴隨式的分量s0、s1、s2和s3進(jìn)行線性組合，也就是對(duì)H矩陣的行進(jìn)行線性組合，得到以下一組校驗(yàn)方程：

A1=s3=e6+e4+e

3

A2=s1=e6+e

5+e1(6.3.1)A3=s2+s0=e6++e2+e0第七十三頁(yè)，共102頁(yè)。顯然，上述方程的系數(shù)所組成的3個(gè)七重?cái)?shù)組：(1011000)，(1100010)和(1000101)是H行的線性組合，在H的行空間中。用A1、A2和A3代表這3個(gè)七重，則碼字C滿足：

C·AT1=C·AT2=C·AT3=0或(6.3.2)第七十四頁(yè)，共102頁(yè)?？芍?A1=c6+c4+c3=0A2=c6+c5+c1

=0A3=c6+c

2+c0

=0得到一組新的校驗(yàn)方程。它們有以下特點(diǎn)：c6含在每一方程之中，c5、c4、c3、c2、c1和c0只含在某一方程中。有這種特點(diǎn)的校驗(yàn)方程稱為正交于c6(或x6、e6)碼元位的正交校驗(yàn)方程(或正交一致校驗(yàn)和式)，由它們的系數(shù)所組成的矩陣H0，稱為正交一致校驗(yàn)矩陣。所以，由式(6.3.2)可得該碼的正交校驗(yàn)矩陣第七十五頁(yè)，共102頁(yè)。第七十六頁(yè)，共102頁(yè)。定義6.3.1若某一特定碼元位(如xn-i)出現(xiàn)在H0矩陣中J行的每一行中，而其它碼元位至多在其中一行出現(xiàn)，則稱H0為正交于該碼元位(xn-i)的正交一致校驗(yàn)矩陣。［7，3，4］碼能糾正一個(gè)錯(cuò)誤同時(shí)發(fā)現(xiàn)兩個(gè)錯(cuò)誤，由上面的H0矩陣或式(6.3.2)可以發(fā)現(xiàn)：第七十七頁(yè)，共102頁(yè)。(1)發(fā)生一個(gè)錯(cuò)誤，且在正交碼元位上：e6=1，則可得A1=1，A2=1，A3=1。

(2)發(fā)生一個(gè)錯(cuò)誤但不在正交碼元位上：e6=0，

ei=1(i取5，4，3，2，1，0中的某一個(gè))，則只有一個(gè)Aj=1(j=1，2，3)，其它兩個(gè)A均為0。(3)發(fā)生兩個(gè)錯(cuò)誤，其中一個(gè)在正交位上，另一個(gè)在其它位(如e5)：e6=1，e5=1，則A1=1，A2=0，A3=1。(4)發(fā)生兩個(gè)錯(cuò)誤，都不在正交位上，設(shè)e5=1，

e4=1，則A1=1，A2=1，A3=0。第七十八頁(yè)，共102頁(yè)。定理6.3.1一個(gè)循環(huán)碼若在任一位上能建立J個(gè)正交一致校驗(yàn)和式，則該碼能糾正t≤［J／2］個(gè)錯(cuò)誤(式中，［x］表示取x的整數(shù)部分)。第七十九頁(yè)，共102頁(yè)。定義6.3.2如果某一碼元位置集合{ci1，ci2，…，cil}的線性組合

ai1ci1+ai2ci2+…+ailcil

在A1，A2，…，AJ的一致校驗(yàn)和式中均出現(xiàn)，而其余碼元位置集合至多在其中一個(gè)校驗(yàn)和式中出現(xiàn)，則說(shuō)A1，A2，…，AJ在集合{ci1，ci2，…，cil}上正交，稱A1，A2，…，AJ是正交于該碼元位置集合的正交一致校驗(yàn)和式，上式中的aij是非0值。

第八十頁(yè)，共102頁(yè)。例如［7，4，3］循環(huán)漢明碼，g(x)=x3+x2+1。它的校驗(yàn)矩陣由S=E·HT=(s2，s1，s0)得到：第八十一頁(yè)，共102頁(yè)。A111=s2=(e6+e4)+e3+e2A112=s1=(e6+e4)+e5+e1(6.3.4)A121=s1=(e6+e5)+e4+e1A122=s2+s0=(e6+e5)+e2+e0(6.3.5)第八十二頁(yè)，共102頁(yè)。組成了J=2組對(duì){(e6，e4)=E11}和對(duì){(e6，e5)=E12}碼元位置集合正交的正交一致校驗(yàn)和式。若碼組中僅出現(xiàn)一個(gè)錯(cuò)誤，則根據(jù)A111和A112中取值是1的個(gè)數(shù)多少，正確譯得(e6+e4)=A11的值。由A121和A122中取值是1的個(gè)數(shù)多少，正確譯得(e6+e5)=A12的值。然后再根據(jù)A11，A12中取值為1的個(gè)數(shù)，譯出x6碼元位是否錯(cuò)誤。如x6碼元位發(fā)生了錯(cuò)誤，e6=1。由式(6.3.4)和式(6.3.5)有：第八十三頁(yè)，共102頁(yè)。A111=(e6+e4)+e3+e

2=1A112=(e6+e

4)+e5+e1=1A121=(e6+e

5)+e4+e1=1A122=(e6+e5)+e

2+e0=1

可得：A11=(e6+e4)=1A12=(e6+e5)=1

第八十四頁(yè)，共102頁(yè)。此兩方程正交于e6，可以根據(jù)A11和A12中取1個(gè)數(shù)的多少，決定出e

6的值。這里A11=A12=1，有兩個(gè)1，所以e6=1。從該例看出，為了譯出一個(gè)碼元需要進(jìn)行兩次大數(shù)判決。每次需要兩個(gè)正交校驗(yàn)和式，第一次是對(duì)碼元位置集合{e6，e4}和{e6，e5}正交，第二次是對(duì)兩個(gè)碼元的位置集中的e6(x6)碼元位正交，所以是兩步大數(shù)邏輯譯碼。［7，4，3］循環(huán)漢明碼就稱為兩步大數(shù)邏輯可譯碼。第八十五頁(yè)，共102頁(yè)。二、大數(shù)邏輯譯碼器大數(shù)邏輯譯碼器分為兩類：Ⅰ型和Ⅱ型，它們沒(méi)有本質(zhì)上的不同。下面先介紹一步大數(shù)邏輯譯碼器，再介紹L步大數(shù)邏輯譯碼器。1．Ⅰ型大數(shù)邏輯譯碼器以［7，3，4］碼的譯碼器為例，說(shuō)明這種類型的一步大數(shù)邏輯譯碼器的構(gòu)成和工作過(guò)程。由式(6.3.1)和式(6.3.2)可知：第八十六頁(yè)，共102頁(yè)。第八十七頁(yè)，共102頁(yè)。圖6-9［7，3，4］碼Ⅰ型大數(shù)