循環(huán)碼的譯碼

循環(huán)碼的譯碼第一頁，共九十九頁，2022年，8月28日§6.1循環(huán)碼譯碼的一般原理

設(shè)發(fā)送的碼字是C(x)=(cn-1xn-1+…+c1x+c0)(今后不再嚴(yán)格區(qū)分碼字與碼多項(xiàng)式)，通過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)生的錯誤圖樣，應(yīng)當(dāng)指出，上述這些式中的ci、ri、ei均是GF(q)中的元素，也就是我們這里僅討論硬判決時(shí)的譯碼方法。

第二頁，共九十九頁，2022年，8月28日

譯碼器的主要任務(wù)就是如何從R(x)中得到正確的估計(jì)錯誤圖樣ê(x)=E(x)，然后得到C(x)，并由此得到信息組m(x)。如同所有線性分組碼的譯碼一樣，循環(huán)碼的譯碼也分為以下3步：

(1)計(jì)算R(x)的伴隨式S(x)；

(2)根據(jù)伴隨式S(x)找出估計(jì)錯誤圖樣ê(x)；第三頁，共九十九頁，2022年，8月28日

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

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

0)，信道產(chǎn)生的錯誤圖樣為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第五頁，共九十九頁，2022年，8月28日

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

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

可知伴隨式S僅與錯誤圖樣有關(guān)，而與發(fā)送的碼字無關(guān)，由它可計(jì)算出錯誤圖樣E。第六頁，共九十九頁，2022年，8月28日

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

xn-1=g(x)h(x)，g(x)=n-k。該碼的一致校驗(yàn)矩陣由式(5.1.9)可知為第七頁，共九十九頁，2022年，8月28日所以第八頁，共九十九頁，2022年，8月28日

由此式可知相應(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)除后所得的余式。

第九頁，共九十九頁，2022年，8月28日

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

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

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

第十頁，共九十九頁，2022年，8月28日證明由伴隨式定義可知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))第十一頁，共九十九頁，2022年，8月28日

推論6.1.1xjR(x)的伴隨式Sj(x)≡xjS(x)(modg(x))，j=0，1，…，n-1。而任意多項(xiàng)式a(x)乘R(x)所對應(yīng)的伴隨式

Sa(x)≡a(x)S(x)(modg(x))(6.1.5)第十二頁，共九十九頁，2022年，8月28日

在q進(jìn)制時(shí)，若碼要糾正≤t個錯誤，則錯誤圖樣代表共有(6.1.6)

個。譯碼時(shí)，只要知道此代表圖樣的伴隨式，該類其它錯誤圖樣的伴隨式都可由此代表圖樣伴隨式在伴隨式計(jì)算電路中得到。這樣，就使得循環(huán)碼譯碼器的錯誤圖樣識別電路大為簡化，由原來識別(6.1.7)個圖樣減少到N1個。第十三頁，共九十九頁，2022年，8月28日

例如二進(jìn)制碼，n=63，t=4，由式(6.1.6)和式(6.1.7)計(jì)算譯碼器所需識別的錯誤圖樣個數(shù)如表6-1所示。

表6-1N1，N2比較表第十四頁，共九十九頁，2022年，8月28日

例6.1二進(jìn)制［7，4，3］循環(huán)漢明碼，它的g(x)=x3+x+1，相應(yīng)的校驗(yàn)矩陣第十五頁，共九十九頁，2022年，8月28日

由式(6.1.6)知，構(gòu)造此譯碼器的錯誤圖樣識別電路時(shí)，只要識別一個圖樣E6=(1000000)就夠了，該圖樣的伴隨式就是H的第一列(101)?？芍R別E6錯誤圖樣的識別電路就是一個檢測伴隨式是否是(101)的電路。由此可得如圖6-1所示的譯碼電路。圖中的伴隨式計(jì)算電路就是一個g(x)=x3+x+1的除法電路，而有3個輸入端的與門和反相器，組成了識別(101)的伴隨式識別器。第十六頁，共九十九頁，2022年，8月28日圖6-1［7，4，3］循環(huán)漢明碼譯碼器第十七頁，共九十九頁，2022年，8月28日

譯碼器的譯碼過程如下：

(1)開始譯碼時(shí)門開，移存器內(nèi)容全為0。收到的R(x)=r6x6+…+r0，以高次項(xiàng)系數(shù)(r6)至低次項(xiàng)系數(shù)的次序，一方面送入7級緩沖器，一方面送入g(x)除法電路計(jì)算伴隨式。7次移位后，R(x)的系數(shù)全部存入緩存器，g(x)電路也得到了伴隨式S0(x)，此時(shí)門關(guān)，禁止輸入。第十八頁，共九十九頁，2022年，8月28日(2)若S0(x)≡1+x2≡x6

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

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

6由原來的1變成0，或由0變成1，糾正了r6的錯誤：r6+1=c6+e6+1=c6+1+1=c6，得到了原來發(fā)送的碼元。此時(shí)與門的糾錯信號“1”也反饋到伴隨式計(jì)算電路輸入端(圖中虛線所示)，對伴隨式進(jìn)行修正，以消去該錯誤對伴隨式的影響。第十九頁，共九十九頁，2022年，8月28日

這由于

R(x)=rn-1

xn-1+…+r1x+r

0

相應(yīng)的伴隨式是S0(x)。糾錯后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錯是在第n+1次移位進(jìn)行的，所以R′1(x)成為

R1(x)=xR′1(x)≡rn-2

xn-1+…+r0x+rn-1+1(modxn-1)第二十頁，共九十九頁，2022年，8月28日

相應(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。第二十一頁，共九十九頁，2022年，8月28日(3)若E(x)=x5，則S0(x)≡x5≡x2+x+1

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

S1(x)≡xS0(x)≡xE(x)≡x2+1

(modg(x))第二十二頁，共九十九頁，2022年，8月28日

因此再移動一次，與門輸出的糾正信號“1”正好與緩存器輸出的r5=c

5+1相加，得到了c5，從而完成了糾錯。若r5不錯，則重復(fù)上述過程一直到譯完一個碼字為止。該譯碼過程可用表6-2表示，已知R(x)=x6+x+1，E(x)=x4。由該表知，到第10個節(jié)拍，與門輸出一個“1”糾正r4，最后譯碼器輸出碼字(1010011)。第二十三頁，共九十九頁，2022年，8月28日表6-2圖6-1譯碼器譯碼過程第二十四頁，共九十九頁，2022年，8月28日

從上述譯碼過程可知，譯一組碼共需14(2n=14)個節(jié)拍，僅當(dāng)?shù)谝唤M的R(x)移出7級緩存器后，才能接收第二組的R(x)。為了使譯碼連續(xù)，必須再加一個伴隨式計(jì)算電路，如圖6-2。第二十五頁，共九十九頁，2022年，8月28日

圖6-2［7，4］碼完整譯碼器第二十六頁，共九十九頁，2022年，8月28日

開始工作時(shí)，所有移存器的存數(shù)全為0，門1開、門2關(guān)。當(dāng)k=4次移位后，4級緩存器接收了前面的4個信息位(對系統(tǒng)碼而言)，此時(shí)門1關(guān)，并使4級緩沖器停止移位。再移動n-k=3次后，g(x)除法電路得到了伴隨式S0(x)，此時(shí)門2開，把上邊g(x)除法電路中的伴隨式送到下面的伴隨式計(jì)算電路中，隨即門2關(guān)閉，且上邊g(x)除法電路立即清洗為0。門1再次打開，4級緩存器一邊送出第一組的信息，一邊接收第二組R(x)的前k位信息組。與此同時(shí)，上邊伴隨式計(jì)算電路計(jì)算第二組R(x)的伴隨式，而下邊伴隨式計(jì)算電路，對第一組R(x)中的信息元進(jìn)行糾錯。第二十七頁，共九十九頁，2022年，8月28日

三、擴(kuò)展?jié)h明碼的譯碼［2m，2m-1-m，4］擴(kuò)展?jié)h明碼是由［2m-1，2m-1-m，3］漢明碼加一個全校驗(yàn)位得到。它的碼字(cn-1，…，c0，c∞)中前n個碼元(cn-1，…，c0)是漢明碼的一個碼字，c∞是全校驗(yàn)位。擴(kuò)展?jié)h明碼的碼長是8的整數(shù)倍，特別適用于計(jì)算機(jī)或微機(jī)組成的數(shù)據(jù)處理或數(shù)據(jù)傳輸系統(tǒng)中。第二十八頁，共九十九頁，2022年，8月28日

擴(kuò)展?jié)h明碼能糾正一個錯誤同時(shí)發(fā)現(xiàn)兩個錯誤，雖然它不是循環(huán)碼，但它譯碼電路的主要部分與循環(huán)漢明碼的譯碼器相同，只要加上檢錯電路即可。如［8，4，4］擴(kuò)展碼，只要在［7，4，3］循環(huán)漢明碼譯碼器中，加一個檢錯電路即成，如圖6-4。圖中，(a)部分的電路基本上與圖6-1同，是循環(huán)漢明碼的譯碼器，不同的是多加了一個全校驗(yàn)位檢查電路，它由一個級移存器加一個模2加法器組成。圖中，(b)部分電路是一個檢錯電路。該譯碼器的譯碼過程如下：

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

6，r

5，r4，r3)存入4級緩存器中，它就是待糾錯的4個信息元。移動7次后門1關(guān)，R(x)的前7個碼元(r6，r5，r4，r3，r2，r1，r0)，已全部送入［7，4，3］碼所決定的伴隨式計(jì)算電路中，得到了伴隨式(s2，s1，s0)。第8次移位后，在全校驗(yàn)位檢查電路中得到了全校驗(yàn)的結(jié)果s∞，此時(shí)譯碼器不再輸入。第三十一頁，共九十九頁，2022年，8月28日(2)當(dāng)s∞=0、(s0，s1，s2)=(000)時(shí)，譯碼器認(rèn)為接收R(x)無誤，把4級緩存器中的信息元輸出。

(3)當(dāng)s∞=1、(s0，s1，s2)≠(000)時(shí)，譯碼器認(rèn)為有一個錯誤，此時(shí)糾錯部分的譯碼電路，按上面講的漢明碼的方法進(jìn)行糾錯譯碼，4次移位后已全部輸出已糾正過的信息元。第三十二頁，共九十九頁，2022年，8月28日(4)s∞=0、(s0，s1，s2)≠(000)，譯碼器認(rèn)為出現(xiàn)了偶數(shù)個錯誤，錯誤告警電路輸出一信號給用戶，表示檢測到錯誤。

(5)s∞=1、(s0，s1，s2)全為0時(shí)，譯碼器認(rèn)為出現(xiàn)了一個以上的奇數(shù)個錯誤，錯誤告警電路也輸出一個信號給用戶。當(dāng)然，為了使譯碼連續(xù)，在圖6-4的(a)部分電路中，也必須有兩個伴隨式計(jì)算電路，這與圖6-2相同。

第三十三頁，共九十九頁，2022年，8月28日

［2m-1，2m-2-m，4］增余刪信漢明碼的譯碼電路與擴(kuò)展?jié)h明碼的譯碼電路基本相同，只不過全校驗(yàn)位的結(jié)果s∞也要輸入到錯誤圖樣的識別電路與門中，對［7，3，4］碼來說就是輸入到圖6-4(a)中有3個輸入端的與門，如虛線所示，其它情況相同。第三十四頁，共九十九頁，2022年，8月28日

四、縮短循環(huán)碼的譯碼縮短i個信息位的［n-i，k-i］縮短循環(huán)碼，是在［n，k］循環(huán)碼中選前i個信息位為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ǔ)上作如下修正：第三十五頁，共九十九頁，2022年，8月28日(1)k級緩存器改為k-i級；

(2)為了與(1)的改動相適應(yīng)，R(x)應(yīng)自動乘以xi，然后再輸入伴隨式計(jì)算電路。如［7，4］循環(huán)漢明碼縮短一位變成［6，3］碼，它的譯碼器就是把圖6-2中的譯碼器作如下變動：R(x)從圖中(A)虛線所示的地方輸入，這相當(dāng)于R(x)自動乘以x，4級緩存器變成3級。第三十六頁，共九十九頁，2022年，8月28日§6.2捕錯譯碼

一、基本工作原理設(shè)碼字C(x)是某一糾t個錯誤的［n，k］循環(huán)碼的碼字，當(dāng)它通過有擾信道到達(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第三十七頁，共九十九頁，2022年，8月28日

分別是在碼字信息組(或前k位)和校驗(yàn)位(或后n-k位)上的錯誤圖樣。若E(x)=n-k-1，即所有≤t個錯誤集中在校驗(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))第三十八頁，共九十九頁，2022年，8月28日

對于糾t個錯誤的循環(huán)碼來說，必須使t個錯誤能連續(xù)地出現(xiàn)在n-k位以內(nèi)，這等價(jià)于要求有連續(xù)k位碼元無錯，或錯誤圖樣中連續(xù)k位的值為0。由于t個錯誤均勻分布在n位上時(shí)最難滿足連續(xù)k位無錯這一要求，因此可以用捕錯方法譯碼的［n，k］循環(huán)碼，n、k、t之間必須滿足下列條件：

k＜n／t

或t＜n／k，或R＜1／t(6.2.1)第三十九頁，共九十九頁，2022年，8月28日

定理6.2.1糾正t個錯誤的GF(q)上的［n，k］循環(huán)碼，捕錯譯碼過程中已把t個錯誤集中在Ri(x)的最低次n-k位以內(nèi)的充要條件是此時(shí)的伴隨式重量

(Si(x))≤t(6.2.2)

證明若錯誤已集中在n-k位低次位碼元段以內(nèi)，則

Si(x)≡xiE(x)=Ei(x)=Eip(x)

(modg(x))Si(x)=Eip(x)第四十頁，共九十九頁，2022年，8月28日

碼只能糾正t個錯誤，若錯誤圖樣E(x)是一個可糾正的錯誤圖樣，則w(E(x))≤t，因而E(x)的循環(huán)移位i次的錯誤圖樣Ei(x)的重量也必小于等于t，所以

w(Si(x))=w(Ei(x))≤t第四十一頁，共九十九頁，2022年，8月28日

反之，若w(Si(x))≤t，則錯誤一定集中在n-k位低次位碼元段內(nèi)。設(shè)錯誤沒有集中在該段以內(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)碼的一個碼字。因而

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第四十二頁，共九十九頁，2022年，8月28日

因?yàn)?/p>

w(Ei(x))≤t

所以

w(-Si(x))≥t+1＞t

由于w(-Si(x))=w(Si(x))，因此上式與假設(shè)w(Si(x))≤t相矛盾，因而錯誤沒有集中在n-k低次位以內(nèi)的反證法假設(shè)不能成立，故錯誤集中在n-k低次位內(nèi)。

第四十三頁，共九十九頁，2022年，8月28日

例6.2二進(jìn)制［15，7，5］循環(huán)碼，生成多項(xiàng)式g(x)=x8+x7+x6+x4+1，能糾正兩個錯誤。

t=2＜15／7

滿足捕錯譯碼的必要條件式(6.2.1)，可以用捕錯譯碼方法譯碼，它的譯碼電路如圖6-5。其譯碼過程如下：第四十四頁，共九十九頁，2022年，8月28日圖6-5［15，7，5］循環(huán)碼捕錯譯碼電路第四十五頁，共九十九頁，2022年，8月28日(1)開始工作時(shí)，所有移存器和緩存器清洗為0，門2、門3開，門1、門4和門5關(guān)閉。n=15次移位后，R(x)的15個碼元全部移入(8+7)=15級緩存器，信息元在前7級，同時(shí)伴隨式計(jì)算電路也完成了伴隨式計(jì)算得到了S0(x)。若S0(x)=0，說明無錯，打開門5，輸出緩存器中的7個信息元。若S0(x)≠0，則進(jìn)行以下各步。

第四十六頁，共九十九頁，2022年，8月28日(2)此時(shí)門2關(guān)，門1開，若w(S0(x))≤2，檢測電路檢測到伴隨式的重量≤2，打開門4，關(guān)閉門3。

(3)若w［S0(x)］＞2，則15級緩存器和g(x)除法電路都循環(huán)移位一次，并檢查w［S1(x)］的重量，若仍大于2，則繼續(xù)循環(huán)移位。［n，k］循環(huán)碼的一般捕錯譯碼器如圖6-6和圖6-7，它們分別稱為第一類和第二類捕錯譯碼器。第四十七頁，共九十九頁，2022年，8月28日圖6-6［n，k］循環(huán)碼的第一類捕錯譯碼器第四十八頁，共九十九頁，2022年，8月28日圖6-7［n，k］循環(huán)碼的第二類捕錯譯碼器第四十九頁，共九十九頁，2022年，8月28日

第二類譯碼器與第一類的差別，僅在于第二類譯碼器是把接收到的R(x)自動乘以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)第五十頁，共九十九頁，2022年，8月28日

二、捕錯譯碼的修正捕錯譯碼是假定錯誤能集中在n-k段以內(nèi)的前提下進(jìn)行的，要求［n，k］循環(huán)碼必須滿足式(6.2.1)的必要條件。但是，能滿足此條件的糾隨機(jī)錯誤的循環(huán)碼很少，只有糾正一個錯誤的循環(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稍大或相等，也就是說在譯碼過程中不能把錯誤全部集中在n-k個碼元段以內(nèi)，而有個別錯誤可能在其它碼元位上。為了解決此問題，必須對捕錯譯碼加以適當(dāng)修正。第五十一頁，共九十九頁，2022年，8月28日

譯碼過程中，若譯碼器能把大部分錯誤捕捉到n-k個碼元段以內(nèi)，同時(shí)使個別錯誤進(jìn)入某幾個預(yù)先指定的位上，則也能確定此時(shí)的錯誤圖樣。當(dāng)然，為了實(shí)現(xiàn)這種運(yùn)算必須附加一些電路，以確定錯誤是否在某幾個指定的位置。第五十二頁，共九十九頁，2022年，8月28日

設(shè)［n，k］循環(huán)碼能糾正t個錯誤，生成多項(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)第五十三頁，共九十九頁，2022年，8月28日

式中，SI(x)是R(x)前k位(對系統(tǒng)碼來說就是信息位)碼段中錯誤圖樣EI(x)的伴隨式。由上式知，若EI(x)及其SI(x)是已知的，則可根據(jù)式(6.2.4)得到R(x)中后n-k位內(nèi)(校驗(yàn)位)的錯誤圖樣Ep(x)，從而確定出原來的錯誤圖樣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，…第五十四頁，共九十九頁，2022年，8月28日

是xn-k

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

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

(6.2.5)第五十五頁，共九十九頁，2022年，8月28日

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

由{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))第五十七頁，共九十九頁，2022年，8月28日圖6-8［23，12］碼修正捕錯譯碼器第五十八頁，共九十九頁，2022年，8月28日(1)開始時(shí)所有移存器中的存數(shù)均清洗為0，開關(guān)K1、K2和K5接至D=0的位置，K3和K4接至E=0的位置。接收到的R(x)一方面送入23(=11+12)級緩存器中，一方面送入伴隨式計(jì)算電路計(jì)算伴隨式。23次移位后，得到伴隨式

S0(x)=s10x10+s9x9+…+s0

把它送至3個錯誤圖樣檢測電路；第五十九頁，共九十九頁，2022年，8月28日(2)開關(guān)K1、K2和K5接到D=1的位置，K3

和K4

仍在E=0的位置，由錯誤圖樣檢測電路檢測可糾正的錯誤圖樣：①若w(S0(x))≤3，認(rèn)為錯誤全在后11位中，且錯誤圖樣就是S0(x)，此時(shí)T1=1導(dǎo)致E′=1，K3和K4接至E=1位置，并在移位過程中對11級緩存器的輸出進(jìn)行糾錯。第六十頁，共九十九頁，2022年，8月28日②若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第六十一頁，共九十九頁，2022年，8月28日③若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第六十二頁，共九十九頁，2022年，8月28日④若w(S0(x))＞3，或w(S0(x)-SI1(x))＞2，或w(S0(x)-SI2(x))＞2，則進(jìn)行下一步；

(3)把23級緩存器和伴隨式計(jì)算電路同時(shí)循環(huán)移位一次，對新得到的伴隨式S1(x)，進(jìn)行如同第(2)步的檢查；

第六十三頁，共九十九頁，2022年，8月28日(4)當(dāng)緩存器和伴隨式計(jì)算電路共移位2n次后，譯完了一個碼字。此時(shí)K1、K2和K5接至D=0的位置，K3

和K4

接到E=0的位置；

(5)送入第二組R(x)，同時(shí)第一組已糾過錯的碼元由23級緩存器輸出。所以，接收到的R(x)從輸入譯碼器直至輸出完為止，共需移位3n(3×23)次。第六十四頁，共九十九頁，2022年，8月28日

三、覆蓋多項(xiàng)式的數(shù)目與建立無論是對二進(jìn)制還是q進(jìn)制碼，修正捕錯譯碼器的復(fù)雜性主要決定于覆蓋多項(xiàng)式集合{Qj(x)}中，覆蓋多項(xiàng)式數(shù)目j的多少，若j過大，則譯碼器太復(fù)雜而不能實(shí)用。對于一個特定的循環(huán)碼是否一定能找到覆蓋多項(xiàng)式？若能找到，則應(yīng)如何找{Qj(x)}？最小的j應(yīng)是多少？這些是捕錯譯碼能否實(shí)用的關(guān)鍵問題。第六十五頁，共九十九頁，2022年，8月28日

對于滿足式(6.2.1)的碼，也就是錯誤能全部集中到連續(xù)的n-k位以內(nèi)，或能保證連續(xù)k位無錯，則覆蓋多項(xiàng)式必定存在，就是Q0(x)=0，j=1；如果碼不滿足式(6.2.1)，但滿足以下關(guān)系式：

R＜2／t

或2n／t＞k(6.2.7)第六十六頁，共九十九頁，2022年，8月28日

引理6.2.1對于糾t個錯誤的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ì)討論，請參閱文獻(xiàn)［3、4］。第六十七頁，共九十九頁，2022年，8月28日表6-3某些二進(jìn)制循環(huán)碼的覆蓋多項(xiàng)式第六十八頁，共九十九頁，2022年，8月28日§6.3大數(shù)邏輯譯碼原理

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

大數(shù)邏輯譯碼是1954年里德(Reed)，在譯里德-馬勒爾(Reed-Muller，RM)碼時(shí)提出的一種較簡單的譯碼方法〔1，2〕?？墒菍τ谝话愦a長而言，能用大數(shù)邏輯方法譯碼的大數(shù)邏輯可譯碼，其糾錯能力和碼率都稍次于有相同參數(shù)的其它碼如BCH碼，但由于它的譯碼算法和設(shè)備均比相應(yīng)的BCH碼譯碼方法要簡單，因此在實(shí)際中有較廣的應(yīng)用。第七十頁，共九十九頁，2022年，8月28日

一、大數(shù)邏輯譯碼的基本概念通過以下例子介紹二進(jìn)制循環(huán)碼的大數(shù)邏輯譯碼的基本思想。［7，3，4］增余刪信漢明碼，它的生成多項(xiàng)式g(x)=(x+1)(x3+x+1)=x4+x3+x2+1，校驗(yàn)矩陣是第七十一頁，共九十九頁，2022年，8月28日

設(shè)接收的n重R=C+E，C=(c6，c5，…，c0)是發(fā)送的碼字，E=(e6，e

5，…，e0)是錯誤圖樣。相應(yīng)的伴隨式第七十二頁，共九十九頁，2022年，8月28日

對伴隨式的分量s0、s1、s2和s3進(jìn)行線性組合，也就是對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第七十三頁，共九十九頁，2022年，8月28日

顯然，上述方程的系數(shù)所組成的3個七重?cái)?shù)組：(1011000)，(1100010)和(1000101)是H行的線性組合，在H的行空間中。用A1、A2和A3代表這3個七重，則碼字C滿足：

C·AT1=C·AT2=C·AT3=0

或(6.3.2)第七十四頁，共九十九頁，2022年，8月28日

可知: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)矩陣第七十五頁，共九十九頁，2022年，8月28日第七十六頁，共九十九頁，2022年，8月28日

定義6.3.1若某一特定碼元位(如xn-i)出現(xiàn)在H0矩陣中J行的每一行中，而其它碼元位至多在其中一行出現(xiàn)，則稱H0為正交于該碼元位(xn-i)的正交一致校驗(yàn)矩陣。［7，3，4］碼能糾正一個錯誤同時(shí)發(fā)現(xiàn)兩個錯誤，由上面的H0矩陣或式(6.3.2)可以發(fā)現(xiàn)：第七十七頁，共九十九頁，2022年，8月28日(1)發(fā)生一個錯誤，且在正交碼元位上：e6=1，則可得A1=1，A2=1，A3=1。

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

ei=1(i取5，4，3，2，1，0中的某一個)，則只有一個Aj=1(j=1，2，3)，其它兩個A均為0。

(3)發(fā)生兩個錯誤，其中一個在正交位上，另一個在其它位(如e5)：e6=1，e5=1，則A1=1，A2=0，A3=1。

(4)發(fā)生兩個錯誤，都不在正交位上，設(shè)e5=1，

e4=1，則A1=1，A2=1，A3=0。第七十八頁，共九十九頁，2022年，8月28日

定理6.3.1一個循環(huán)碼若在任一位上能建立J個正交一致校驗(yàn)和式，則該碼能糾正t≤［J／2］個錯誤(式中，［x］表示取x的整數(shù)部分)。第七十九頁，共九十九頁，2022年，8月28日

定義6.3.2如果某一碼元位置集合{ci1，ci2，…，cil}的線性組合

ai1ci1+ai2ci2+…+ailcil

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

第八十頁，共九十九頁，2022年，8月28日

例如［7，4，3］循環(huán)漢明碼，g(x)=x3+x2+1。它的校驗(yàn)矩陣由S=E·HT=(s2，s1，s0)得到：第八十一頁，共九十九頁，2022年，8月28日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)第八十二頁，共九十九頁，2022年，8月28日

組成了J=2組對{(e6，e4)=E11}和對{(e6，e5)=E12}碼元位置集合正交的正交一致校驗(yàn)和式。若碼組中僅出現(xiàn)一個錯誤，則根據(jù)A111和A112中取值是1的個數(shù)多少，正確譯得(e6+e4)=A11的值。由A121和A122中取值是1的個數(shù)多少，正確譯得(e6+e5)=A12的值。然后再根據(jù)A11，A12中取值為1的個數(shù)，譯出x6

碼元位是否錯誤。如x6碼元位發(fā)生了錯誤，e6=1。由式(6.3.4)和式(6.3.5)有：第八十三頁，共九十九頁，2022年，8月28日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

第八十四頁，共九十九頁，2022年，8月28日

此兩方程正交于e6，可以根據(jù)A11和A12中取1個數(shù)的多少，決定