講義62循環(huán)碼

1、信息論講義（第六章）6-2 循環(huán)碼(Cyclic Code)循環(huán)碼是線性分組碼的最重要的一類(lèi)碼，它的結(jié)構(gòu)完全建立在有限域多項(xiàng)式的基礎(chǔ)上。它具有兩個(gè)基本特點(diǎn)：一是編碼電路與譯碼電路非常簡(jiǎn)單，易于實(shí)現(xiàn)；二是其代數(shù)性質(zhì)好編碼譯碼分析方便，有一些好的譯碼方法。6-2-1 循環(huán)碼的描述循環(huán)碼定義：一個(gè)(n,k)線性分組碼C，如果碼組中的一個(gè)碼字的循環(huán)移位也是這個(gè)碼組中的一個(gè)碼字，則稱(chēng)C為循環(huán)碼。C(0)=cn-1,cn-2,c1,c0 CC(1)=cn-2,cn-3,c0,cn-1 C稱(chēng)為具有循環(huán)自閉性。循環(huán)碼的多項(xiàng)式描述：循環(huán)碼可以用監(jiān)督矩陣和生成矩陣描述，但更多地用域上多項(xiàng)式來(lái)描述，一個(gè)(n,k)循

2、環(huán)的碼字矢量C(0)用一個(gè)n-1次多項(xiàng)式描述，可以表示為：C(x)= cn-1xn-1+cn-2xn-2+c1x+c0這個(gè)多項(xiàng)式稱(chēng)為碼字多項(xiàng)式。碼字矢量的循環(huán)移位可以用x乘上C(x)后的模xn-1(xn+1)來(lái)表示。xC(x)= x(cn-1xn-1+cn-2xn-2+c1x+c0) = cn-1xn+cn-2xn-1+c1x2+c0 x = cn-2xn-1+c1x2+c0 x+ cn-1 (模xn+1)模xn+1相當(dāng)于xn+1=0；xn=1循環(huán)碼舉例：(7,4)系統(tǒng)循環(huán)碼的編碼及碼字多項(xiàng)式如下表：信息碼字循環(huán)碼字碼字多項(xiàng)式g(x)的倍式倍式編碼00000000 00000000000010

3、001 011x3+x+11000100100010 110x4+x2+xx001000110011 101x4+x3+x2+1x+1001101000100 111x5+x2+x+1x2+1010101010101 100x5+x3+x2x2010001100110 001x5+x4+1x2+x+1011101110111 010x5+x4+x3+xx2+x011010001000 101x6+x2+1x3+x+1101110011001 110x6+x3+x2+xx3+x101010101010 011x6+x4+x+1x3+1100110111011 000x6+x4+x3x310001

4、1001100 010x6+x5+xx3+x2+x111011011101 001x6+x5+x3+1x3+x2+x+1111111101110 100x6+x5+x4+x2x3+x2110011111111 111x6+x5+x4+x3+x2+x+1x3+x2+11101可以看出：每個(gè)碼字的循環(huán)移位仍然屬于這個(gè)碼組，注意：并不是說(shuō)這個(gè)碼組是由一個(gè)碼字的循環(huán)移位構(gòu)成的，本例中是由四個(gè)碼字的循環(huán)移位構(gòu)成的。生成多項(xiàng)式的定義：在一個(gè)(n,k)循環(huán)碼中，有且僅有一個(gè)次數(shù)為n-k=r的碼字多項(xiàng)式，記為：g(x)=xr+gr-1xr-1+g1x+1同時(shí)：每個(gè)碼字多項(xiàng)式都是g(x)的倍式；每個(gè)次數(shù)小于等于

5、n-1的g(x)的倍式必為一個(gè)碼字多項(xiàng)式。這時(shí)稱(chēng)g(x)的(n,k)碼的生成多項(xiàng)式。從上面的例子可見(jiàn)，g(x)=x3+x+1為(7,4)循環(huán)碼的生成多項(xiàng)式。生成多項(xiàng)式的性質(zhì)：§ 循環(huán)碼C中次數(shù)最低的非零碼字多項(xiàng)式是唯一的，其次數(shù)為r=n-k。§ 令g(x)=xr+gr-1xr-1+g1x+g0為一個(gè)(n,k)循環(huán)碼C中最低次數(shù)碼字多項(xiàng)式，則其常數(shù)項(xiàng)必為g0=1。定理1：(n,k)循環(huán)碼的生成多項(xiàng)式g(x)是xn+1的因式。證明：已知g(x)為一個(gè)n-k次多項(xiàng)式，則xkg(x)為一個(gè)n次多項(xiàng)式，則必有：因?yàn)閤kg(x)是g(x)的循環(huán)移位，它也是一個(gè)碼字多項(xiàng)式，所以一定為g(

6、x)的倍式，即有：g(k)(x)為g(x)的循環(huán)移位在模xn+1下的結(jié)果，因此有：g(k)(x)=q(x)g(x)，由上面的關(guān)系式可知：xkg(x)=(xn+1)+g(k)(x)xn+1=xkg(x)+q(x)g(x)=xk+q(x)g(x)因此，g(x)為xn+1的因式。定理2：若g(x)是一個(gè)n-k次多項(xiàng)式，且為xn+1的因式，則g(x)生成一個(gè)(n,k)循環(huán)碼。這個(gè)定理說(shuō)明：xn+1的次數(shù)為n-k的任何一個(gè)因式，均可以生成一個(gè)(n,k)循環(huán)碼。對(duì)于較大的n，xn+1可以有多個(gè)n-k次多項(xiàng)式，產(chǎn)生不同的(n,k)循環(huán)碼，但可能有好有壞。例如：多項(xiàng)式x7+1可以分解為：x7+1=(x3+x+

7、1)(x3+x2+1)(x+1)可以看出有兩種(7,4)循環(huán)碼的生成矩陣 g(x)= (x3+x+1)和g(x)= (x3+x2+1)。還可以產(chǎn)生一種(7,6)循環(huán)碼，6-2-2 循環(huán)碼的編碼方法系統(tǒng)循環(huán)碼的編碼方法：已知循環(huán)碼的生成矩陣可以按以下步驟產(chǎn)生系統(tǒng)循環(huán)碼。首先定義以下多項(xiàng)式：m(x)=mk-1xk-1+mk-2xk-2+m1x+m0 為信息碼字多項(xiàng)式；c(x)=cn-1xn-1+cn-2xn-2+c1x+c0 為循環(huán)碼字多項(xiàng)式；g(x)=xr-1+gr-2xr-2+g1x+1 為生成多項(xiàng)式；系統(tǒng)碼的編碼分為三步：§ 用xn-k乘上m(x);§ 用g(x)除以xn

8、-km(x)，得到模g(x)的余式r(x)§ c(x)=xn-km(x)+r(x)為系統(tǒng)循環(huán)碼的碼字多項(xiàng)式。例題1：(7,4)循環(huán)碼的生成多項(xiàng)式為g(x)=x3+x+1求m=1010的循環(huán)碼。解：m(x)=x3+x, xn-k=x3;xn-km(x)=x3(x3+x)=x6+x4r(x)=x+1C(x)=xn-km(x)+r(x)=x6+x4+x+1C=1010 011例題2：(7,3)循環(huán)碼的生成多項(xiàng)式為g(x)=x4+x3+x2+1=(x+1)(x3+x+1)求：m=010的循環(huán)碼字C解：m(x)=x; xn-km(x)=x4x=x5C(x)=x5+x2+x+1C=010 011

9、1非系統(tǒng)循環(huán)碼的編碼方法：已知循環(huán)碼的生成矩陣，可以方便的求出非系統(tǒng)循環(huán)碼，C(x)=m(x)g(x)例如：m=1101 g(x)=x3+x+1C(x)=(x3+x2+1)(x3+x+1)=x6+x4+x3+x5+x3+x2+x3+x+1=x6+x5+x4+x3+x2+x+1C=1111111m=0101; c(x)=(x2+1)(x3+x+1)=x5+x3+x2+x3+x+1=x5+x2+x+1C=0100111循環(huán)碼的生成矩陣：循環(huán)碼可以用域上多項(xiàng)式描述，也可以用生成矩陣描述。已知g(x)為循環(huán)碼C中的一個(gè)碼字多項(xiàng)式，由循環(huán)碼的循環(huán)特性可知，可以證明：在(n,k)循環(huán)碼的碼字多項(xiàng)式中，g(

10、x),xg(x),xk-1g(x)等k個(gè)碼字多項(xiàng)式必是線性無(wú)關(guān)（相互獨(dú)立的）的。根據(jù)線性空間的特性，可知，它們是一個(gè)k維子空間的基底，即由它們的線性組合可以生成這個(gè)k維子空間的2k個(gè)碼字。再根據(jù)線性分組碼生成矩陣的定義，它的行向量是由k個(gè)線性無(wú)關(guān)的碼字構(gòu)成的，可以得到(n,k)循環(huán)碼的一個(gè)多項(xiàng)式矩陣為：G(x)=xk-1g(x)xk-2g(x)g(x)相應(yīng)的生成矩陣為G=gn-kgn-k-1g1g00000gn-kgn-k-1g1g00000gn-kgn-k-1g1g0由這個(gè)基本關(guān)系式可以看出，當(dāng)輸入信息碼字矢量為(mk-1,mk-2,m0)時(shí)，相應(yīng)的碼字多項(xiàng)式為：C(x)=(mk-1,mk-

11、2,m0)G(x) =(mk-1xk-1+mk-2xk-2+m0)g(x) =m(x)g(x)利用這種方法產(chǎn)生的循環(huán)碼為非系統(tǒng)循環(huán)碼，因?yàn)?，G(x)為非標(biāo)準(zhǔn)型生成矩陣，（非典型生成矩陣）。這個(gè)非標(biāo)準(zhǔn)型生成矩陣可以通過(guò)矩陣的初等變換轉(zhuǎn)換為標(biāo)準(zhǔn)型生成矩陣?？梢酝ㄟ^(guò)以下例子說(shuō)明。例題：已知(7,4)循環(huán)碼的生成多項(xiàng)式為g(x)=x3+x+1，其非標(biāo)準(zhǔn)型生成矩陣為：G(x)=x3g(x)=x6+x4+x3=1011000x2g(x)x5+x3+x20101100xg(x)x4+x2+x0010110g(x)x3+x+10001011利用不同的矩陣變換可以得到不同的標(biāo)準(zhǔn)型生成矩陣。這種變換包括：

12、7; 列換位；§ 初等行變換；通過(guò)以上兩種方法，可以得到標(biāo)準(zhǔn)型生成矩陣：G=1000111010010100101100001011只使用初等行變換可以得到標(biāo)準(zhǔn)生成矩陣：G=1000101010011100101100001011可知標(biāo)準(zhǔn)型生成矩陣是不唯一的。6-2-3 校驗(yàn)子與循環(huán)碼的譯碼原理設(shè)發(fā)送的碼字多項(xiàng)式位C(x)，錯(cuò)誤圖樣多項(xiàng)式位E(x)，則接收碼字多項(xiàng)式為：R(x)=C(x)+E(x)譯碼器的工作過(guò)程為：§ 由接收碼字多項(xiàng)式R(x)計(jì)算校驗(yàn)子多項(xiàng)式S(x);§ 根據(jù)校驗(yàn)子多項(xiàng)式S(x)計(jì)算錯(cuò)誤圖樣多項(xiàng)式E(x);§ 利用R(x)-E(x)=C

13、(x)計(jì)算譯碼器輸出的估計(jì)值。發(fā)送碼字多項(xiàng)式為：C(x)=cn-1xn-1+cn-2xn-2+c1x+c0接收碼字多項(xiàng)式為；R(x)=rn-1xn-1+rn-2xn-2+r1x+r0校驗(yàn)子多項(xiàng)式為：E(x)=en-1xn-1+en-2xn-2+e1x+e0由R(x)=C(x)+E(x)可知：ri=ci+eI i=0,1,n-1這時(shí)定義校驗(yàn)子多項(xiàng)式為： 模g(x)即：S(x)E(x)R(x) 模g(x)也就是說(shuō)，接收碼字多項(xiàng)式除以g(x)的余式多項(xiàng)式為校驗(yàn)子多項(xiàng)式。如果：S(x)=0，表示接收碼字無(wú)錯(cuò)；如果：S(x)0,表示接收碼字有錯(cuò)；(n,k)循環(huán)碼的校驗(yàn)子多項(xiàng)式的一般表達(dá)式為：S(x)=s

14、r-1xr-1+sr-2xr-2+s1x+s0即校驗(yàn)子多項(xiàng)式S(x)為一個(gè)r-1次多項(xiàng)式。其校驗(yàn)子矢量為：S=sr-1,sr-2,s1,s0它共有2r個(gè)狀態(tài)，當(dāng)2rn+1時(shí)，即可以糾一位錯(cuò)。例題：(7,4)循環(huán)碼的校驗(yàn)子及譯碼，已知：(7,4)循環(huán)碼的生成矩陣為g(x)=x3+x+1考慮接收碼字不錯(cuò)或只錯(cuò)一位時(shí)的校驗(yàn)子多項(xiàng)式。發(fā)送碼字多項(xiàng)式為：C(x)=cn-1xn-1+cn-2xn-2+c1x+c0接收碼字多項(xiàng)式為；R(x)=rn-1xn-1+rn-2xn-2+r1x+r0校驗(yàn)子多項(xiàng)式為：E(x)=en-1xn-1+en-2xn-2+e1x+e0eiE(x)S(x)s2,s1,s0錯(cuò)誤情況0

15、00000無(wú)錯(cuò)e0=111001r0e1=1xx010r1e2=1x2x2100r2e3=1x3x+1011r3e4=1x4x2+x110r4e5=1x5x2+x+1111r5e6=1x6x2+1101r6這個(gè)表給出了接收碼字不出錯(cuò)或只錯(cuò)一位時(shí)校驗(yàn)子多項(xiàng)式和校驗(yàn)子矢量的結(jié)果。根據(jù)這個(gè)表可以進(jìn)行譯碼。例如：發(fā)送碼字為：C=0010110，接收碼字為：R=0011110，表明r3錯(cuò)。接收碼字多項(xiàng)式為：R(x)=x4+x3+x2+x, g(x)=x3+x+1，校驗(yàn)子多項(xiàng)式為： 模g(x)S(x)=x+1 s2,s1,s0=011 查表可知r3出錯(cuò)。已知(7,4)循環(huán)碼的最小漢明距離dmin=3，只能

16、糾一位錯(cuò)，當(dāng)接收碼字出現(xiàn)兩位錯(cuò)時(shí)將不能糾正。例如：發(fā)送碼字為：C=0010111，接收碼字為：R=0011111，表明r3和r0錯(cuò)。R(x)=x4+x3+x2+x+1S(x)=x; s2,s1,s0=010，根據(jù)校驗(yàn)子表可知，譯碼器判為r1錯(cuò)，這時(shí)產(chǎn)生譯碼錯(cuò)碼。6-2-4 循環(huán)碼的編碼電路根據(jù)循環(huán)碼的編碼方法，可知編碼電路應(yīng)當(dāng)是一個(gè)多項(xiàng)式的除法電路，它是碼字多項(xiàng)式的循環(huán)一位后除以生成多項(xiàng)式。系統(tǒng)碼編碼器：為了構(gòu)成系統(tǒng)碼，可知C(x)=xn-km(x)+r(x)r(x)=xn-km(x)/g(x) 模g(x)以(7,4)漢明碼為例：g(x)=x3+x+1編碼器電路如圖所示：它由n-k級(jí)移位寄存器

17、構(gòu)成。門(mén)1門(mén)2D22D1D0或門(mén)C(x)C(x)輸入m(x)這是一個(gè)由n-k=3級(jí)移位寄存器及加法器、或門(mén)和門(mén)控電路構(gòu)成的。§ 移位寄存器的初始狀態(tài)為全0，門(mén)1開(kāi)，門(mén)2關(guān)。信息碼元以m3,m2,m1,m0依次輸入編碼器。信息碼元一方面通過(guò)或門(mén)輸出，另一方面送入除法電路。在除法電路的右端輸入m(x)相當(dāng)于完成了循環(huán)移位n-k=3位。§ 四次移位后，信息碼元已輸出，形成了系統(tǒng)循環(huán)碼的前四位信息位。同時(shí)寄存器中存放的就是余式多項(xiàng)式的系數(shù)，從右到左分別是(c2,c1,c0)。§ 門(mén)1關(guān)，門(mén)2開(kāi)，經(jīng)三次移位，這三個(gè)監(jiān)督位從編碼器輸出。§ 門(mén)1開(kāi)，門(mén)2關(guān)，進(jìn)行第二個(gè)

18、碼字的編碼。m=1001, C=1001 110的編碼過(guò)程如下表：時(shí)鐘信息碼字寄存器內(nèi)容輸出碼字D0D1D20000111101200110301110410111500116000170000(7,3)循環(huán)碼的生成矩陣為：g(x)=x4+x3+x2+1其編碼電路為：門(mén)1D2D3D1門(mén)2D0或門(mén)C(x)輸入m(x)由于n-k=r=4所以編碼器有四級(jí)移位寄存器。非系統(tǒng)循環(huán)碼編碼電路：非系統(tǒng)循環(huán)碼的產(chǎn)生為：C(x)=m(x)g(x),可知其編碼器為如下：D0D1D2m(x)例如m=1110，編出的循環(huán)碼字為：C=1100001C(x)=m(x)g(x)=(x3+x2+x)(x3+x+1)=x6+x

19、5+16-3 循環(huán)碼的譯碼循環(huán)碼的編碼電路由n-k級(jí)移位寄存器構(gòu)成，比較簡(jiǎn)單，但是循環(huán)碼的譯碼電路就相對(duì)比較復(fù)雜。因此，循環(huán)碼的譯碼方法是研究編碼理論和編碼技術(shù)的重要內(nèi)容。線性分組碼（不僅是循環(huán)碼）的譯碼大體分為兩類(lèi)：一是利用碼字的代數(shù)結(jié)構(gòu)進(jìn)行譯碼，稱(chēng)為代數(shù)譯碼方法。另一類(lèi)不僅利用代數(shù)結(jié)構(gòu)，而且還利用概率理論，稱(chēng)為概率譯碼。這里我們重點(diǎn)介紹代數(shù)譯碼方法，包括捕獲（錯(cuò)）譯碼，大數(shù)邏輯譯碼。6-3-1 梅吉特(Meggit)譯碼器上面我們介紹了循環(huán)碼的校驗(yàn)子（伴隨式）譯碼的基本原理，已知：S(x)=R(x)/g(x) mod g(x)這里首先介紹一個(gè)有關(guān)校驗(yàn)子多項(xiàng)式的重要特性。定理：設(shè)S(x)是接

20、收碼字多項(xiàng)式R(x)的校驗(yàn)子多項(xiàng)式，則R(x)的循環(huán)移位xR(x)mod xn+1的校驗(yàn)子S1(x)是S(x)在g(x)除法電路中無(wú)輸入時(shí)右移一位的結(jié)果。S1(x)xS(x) mod g(x)證明：由校驗(yàn)子多項(xiàng)式的定義可知，S(x)R(x) mod g(x)，兩邊同時(shí)乘以x可得；xS(x)xR(x) mod g(x)這時(shí)如果定義S1(x)xR(x) mod g(x)顯然有S1(x)xS(x) mod g(x)定理的推廣：這個(gè)定理的結(jié)果可以推廣為，對(duì)于任意給定的j=1,2,n-1，必有xjR(x)的校驗(yàn)子多項(xiàng)式為：Sj(x)=xjR(x)/g(x)xjS(x) mod g(x)同時(shí)有任意多項(xiàng)式a

21、(x)乘R(x)所對(duì)應(yīng)的校驗(yàn)子多項(xiàng)式Sa(x)=a(x)R(x)/g(x)a(x)S(x) mod g(x)校驗(yàn)子多項(xiàng)式的這些性質(zhì)，在循環(huán)碼的譯碼中有重要作用。梅吉特譯碼原理：如果：C(x)為循環(huán)碼C中的一個(gè)碼字多項(xiàng)式，則xC(x)mod xn+1也是這個(gè)碼組中的一個(gè)碼字。如果：S(x)為R(x)=C(x)+E(x)的校驗(yàn)子多項(xiàng)式，則xS(x)也必然是xR(x)=xC(x)+xE(x)的校驗(yàn)子多項(xiàng)式。這表明：如果E(x)是一個(gè)譯碼器可以糾正的錯(cuò)誤圖樣（相當(dāng)于譯碼標(biāo)準(zhǔn)陣中的陪集首），則xE(x)也是一個(gè)可以糾正的錯(cuò)誤圖樣，xjE(x) (j=1,2,n-1)也是可以糾正的錯(cuò)誤圖樣。這樣就可以根據(jù)

22、這種循環(huán)關(guān)系，對(duì)錯(cuò)誤圖樣分類(lèi)，將任一錯(cuò)誤圖樣及其所有n-j次的循環(huán)移位歸為一類(lèi)。同一類(lèi)的錯(cuò)誤，可以使用同一個(gè)譯碼單元電路，可以簡(jiǎn)化譯碼器電路的復(fù)雜性。例如：可以將“只錯(cuò)一位”的錯(cuò)誤圖樣(1000),(0100),(0001)歸為一類(lèi)，這樣用一個(gè)錯(cuò)誤圖樣(1000)的校驗(yàn)子S(x)代表這一類(lèi)錯(cuò)誤圖樣的校驗(yàn)子。這樣可以大大減少譯碼器要識(shí)別的錯(cuò)誤圖樣類(lèi)別的個(gè)數(shù)：一個(gè)(n,k)循環(huán)碼，要糾正t位錯(cuò)誤，譯碼器要識(shí)別的錯(cuò)誤圖樣總數(shù)為： 例如(7,4)循環(huán)碼可以糾正一位錯(cuò)，n=7，t=1，Ne=C71=7。而通過(guò)分類(lèi)后，譯碼器需要識(shí)別的錯(cuò)誤圖樣的類(lèi)別數(shù)為：例如(7,4)循環(huán)碼的錯(cuò)誤圖樣類(lèi)別數(shù)為Ng=1。可以

23、看到通過(guò)分類(lèi)識(shí)別，可以簡(jiǎn)化循環(huán)碼譯碼器的復(fù)雜性。例題：(7,4)循環(huán)碼的生成矩陣為g(x)=x3+x+1，通過(guò)前面分析可知，只要接收碼字矢量只錯(cuò)一位，譯碼器總可以正確譯碼。在構(gòu)造此譯碼器的錯(cuò)誤圖樣識(shí)別電路時(shí)，只要識(shí)別一個(gè)錯(cuò)誤圖樣例如，E6=1000000就可以了。這個(gè)錯(cuò)誤圖樣對(duì)應(yīng)的校驗(yàn)子矢量為S=101，由此可以得到一種譯碼器結(jié)構(gòu)如圖：D1D0D2r0 7級(jí)移位寄存器 r6門(mén)C(x)R(x)這個(gè)譯碼器上面是一個(gè)g(x)除法電路，下面是一個(gè)7級(jí)移位寄存器作為緩存器，中間的反相器和一個(gè)與門(mén)組成了(101)校驗(yàn)子識(shí)別電路。譯碼過(guò)程如下：§ 開(kāi)始譯碼時(shí)門(mén)打開(kāi)，移位寄存器內(nèi)容位全0。收到的碼字

24、多項(xiàng)式位R(x)=r6x6+r0 由高次到低次分別輸入到7級(jí)緩存器和除法電路，7次移位后，緩存器存入整個(gè)碼字，除法電路S(x)=E(x)/g(x), E(x)=x6得到校驗(yàn)子S0=s2,s1,s0。這時(shí)門(mén)關(guān)上，進(jìn)行譯碼。§ 如果S0(x)=x6=x2+1mod g(x)，這時(shí)101識(shí)別電路輸出為1，表明r6為有錯(cuò)。§ 這時(shí)譯碼器繼續(xù)移位，通過(guò)101識(shí)別電路可以將r6位的錯(cuò)誤糾正。§ 在糾錯(cuò)的同時(shí)，101識(shí)別電路的輸出又反饋到除法電路的輸入端，以消除錯(cuò)誤碼元對(duì)除法電路的下一個(gè)校驗(yàn)子計(jì)算的影響。校驗(yàn)子產(chǎn)生電路開(kāi)始在無(wú)輸入的情況下移位，相當(dāng)以開(kāi)始產(chǎn)生xjS(x)。本電路

25、中，第7次移位后產(chǎn)生了校驗(yàn)子S0，第8次移位時(shí)對(duì)r6進(jìn)行糾正，同時(shí)將101識(shí)別電路的輸出的1輸入到除法電路的輸入端，結(jié)果使除法電路的寄存器狀態(tài)為000，消除了e6的影響。下面我們看一下，利用這個(gè)電路能否糾正其它錯(cuò)誤圖樣的接收碼字。§ 如果E(x)=x5, 表明e5=1或E=0100000，這時(shí)經(jīng)過(guò)前7次移位后得到的校驗(yàn)子多項(xiàng)式為S0(x)=x5=x2+x+1mod g(x)，這時(shí)除法電路的移位寄存器狀態(tài)為111，101識(shí)別電路的輸出為0，說(shuō)明r6正確，不必糾正。§ 第8次移位后，r5移位到緩存器的最右端。同時(shí)校驗(yàn)子除法電路的結(jié)果根據(jù)定理可知：（通過(guò)電路分析也可以看出）S1(

26、x)=xS0(x)=xE(x)=x6=x2+1 mod g(x) 產(chǎn)生101狀態(tài)；這時(shí)101識(shí)別電路輸出1，對(duì)r5進(jìn)行糾正。可以看到，利用循環(huán)碼的循環(huán)特性，可以簡(jiǎn)化譯碼器的復(fù)雜性。從上述譯碼過(guò)程中可以看到，(n,k)循環(huán)碼的譯碼器譯一個(gè)碼字共需要2n次移位，不能實(shí)現(xiàn)連續(xù)譯碼，為了實(shí)現(xiàn)連續(xù)譯碼，可以再加一套除法電路，門(mén)14級(jí)緩存器門(mén)2其工作過(guò)程如下：§ 譯碼前兩個(gè)移位寄存器為全0狀態(tài)，門(mén)1開(kāi)，門(mén)2關(guān)，當(dāng)k=4次移位后，4級(jí)緩存器接收到碼字的前4位信息位。§ 此時(shí)，門(mén)1關(guān)。再移位n-k=3次后，上面的除法電路得到校驗(yàn)子S0(x)，§ 這時(shí)門(mén)2開(kāi)，將上面除法電路得到的校

27、驗(yàn)子送入下面的除法電路，隨即門(mén)2關(guān)閉，且上面的除法電路清0。§ 門(mén)1再次打開(kāi)，4級(jí)緩存器一邊送出第一組信息，一邊接收第二個(gè)碼字的信息位，與此同時(shí)，上面的除法電路計(jì)算第二個(gè)碼字的校驗(yàn)子，下面的除法電路對(duì)第一組碼字進(jìn)行糾錯(cuò)。§ 以上是對(duì)系統(tǒng)碼而設(shè)計(jì)的電路，如果是非系統(tǒng)碼，k級(jí)緩存器應(yīng)改為n級(jí)，而且要在得到的碼字中恢復(fù)信息位。根據(jù)m(x)=C(x)/g(x)，應(yīng)再加一個(gè)除法電路。上面介紹的系統(tǒng)循環(huán)碼的一般譯碼器稱(chēng)為梅吉特譯碼器。6-3-2 捕錯(cuò)譯碼循環(huán)碼的譯碼器的復(fù)雜性主要取決于由校驗(yàn)子確定錯(cuò)誤圖樣的組合邏輯電路的復(fù)雜性，另外一種譯碼方法稱(chēng)為捕錯(cuò)譯碼，其特點(diǎn)是適應(yīng)于糾突發(fā)錯(cuò)誤碼。

28、工作原理：設(shè)C(x)是一個(gè)糾t位錯(cuò)誤的(n,k)系統(tǒng)循環(huán)碼的碼字多項(xiàng)式，而相應(yīng)的接收碼字多項(xiàng)式為：R(x)=C(x)+E(x)，譯碼器得到的校驗(yàn)子多項(xiàng)式為：S(x)=R(x)/g(x)=E(x)/g(x)E(x) mod g(x) EI(x)+EP(x), mod g(x)其中：EI(x)=en-1xn-1+en-2xn-1+en-kxn-kEP(x)=en-k-1xn-k-1+e1x+e0EI(x)為k位信息位的錯(cuò)誤圖樣，EP(x)是n-k=r位監(jiān)督位的錯(cuò)誤圖樣。這時(shí)可以看到：如果：錯(cuò)誤圖樣多項(xiàng)式E(x)的次數(shù)=n-k-1=r-1， 即碼字中的錯(cuò)誤集中在n-k=r監(jiān)督位上， 即en-1=en

29、-2=en-k=0；則：EI(x)=0，E(x)=EP(x)。又因?yàn)椋荷啥囗?xiàng)式g(x)的次數(shù)位n-k=r，所以：校驗(yàn)子多項(xiàng)式S(x)=E(x)/g(x)=EP(x), mod g(x)得到的結(jié)論是：對(duì)于具有這樣的錯(cuò)誤圖樣的碼字C(x)，經(jīng)過(guò)循環(huán)移位后，可以使S(x)=E(x)，譯碼過(guò)程就可以變?yōu)椋篊(x)=R(x)-S(x)。(在GF(2)上，減法與加法一樣)要使一個(gè)碼字的錯(cuò)誤碼元全部集中在碼字的后n-k=r位上，只要求錯(cuò)誤碼元集中在任意連續(xù)n-k位上即可。因?yàn)椋捍a字多項(xiàng)式的循環(huán)移位和校驗(yàn)子多項(xiàng)式的循環(huán)移位有一一對(duì)應(yīng)的關(guān)系。捕錯(cuò)譯碼的定義：若接收碼字R(x)對(duì)應(yīng)的校驗(yàn)子多項(xiàng)式為S0(x)，經(jīng)

30、過(guò)i次循環(huán)移位后，xiR(x)=Ri(x)對(duì)應(yīng)的校驗(yàn)子多項(xiàng)式為Si(x)。一旦檢測(cè)出Si(x)的重量W(Si(x)t，就認(rèn)為此時(shí)碼字的錯(cuò)誤碼元已經(jīng)全部集中在xiR(x)=Ri(x)的后n-k位以?xún)?nèi)了。這時(shí)可以由Ri(x)-Si(x)得到已經(jīng)糾錯(cuò)的接收碼字Ci(x)=xiC(x)，但碼字順序不對(duì)，將其再進(jìn)行n-i次循環(huán)移位，即可得到:C(x)=xnC(x)=xn-ixiC(x) 從而糾正了錯(cuò)誤，這種譯碼方法稱(chēng)為捕錯(cuò)譯碼。捕錯(cuò)譯碼的適應(yīng)條件：§ 只有當(dāng)所有小于等于t個(gè)錯(cuò)誤全部集中再連續(xù)n-k=r位以?xún)?nèi)時(shí)，捕錯(cuò)譯碼才有效。§ 當(dāng)碼字的錯(cuò)誤突發(fā)長(zhǎng)度b小于等于(n-k)/2時(shí)，捕錯(cuò)譯

31、碼才有效。例如：(7,4)碼，dmin=3, t=1, n=7, k=4, n-k=3 (n-k)/2=1.5 所以b=1(15,7)碼，dmin=5, t=2, n-k=8, (n-k)/2=4 b=4,§ 如果一個(gè)(n,k)碼可以糾正t位錯(cuò)，使用捕錯(cuò)譯碼的必要條件是：k<n/t或t<n/k；（這個(gè)條件不夠充分）。定理：捕錯(cuò)譯碼的判別條件糾正t位錯(cuò)誤的(n,k)二元循環(huán)碼，捕錯(cuò)譯碼器已經(jīng)把t個(gè)錯(cuò)誤集中在Ri(x)的最低n-k位以?xún)?nèi)的充要條件，是此時(shí)的校驗(yàn)子矢量的漢明重量： W(Si(x)t證明：如果錯(cuò)誤已經(jīng)集中在最低n-k位以?xún)?nèi)，則Si(x)xiE(x)=Ei(x)=E

32、P(x) mod g(x)Si(x)=EP(x)由于這個(gè)(n,k)碼只能糾t位錯(cuò)，所以，對(duì)于一個(gè)可糾正的錯(cuò)誤圖樣，必有：W(E(x)t而E(x)的循環(huán)移位后，其矢量的漢明重量是不變的，則W(Si(x)=W(Ei(x)t這說(shuō)明：只要能糾t位錯(cuò)的碼已經(jīng)把錯(cuò)誤碼元集中到最低n-k位上，公式W(Si(x)t就一定成立。反之；再證明：如果W(Si(x)t滿(mǎn)足，則錯(cuò)誤碼元就一定集中在最低n-k位碼元內(nèi)了。利用反證法：§ 即當(dāng)W(Si(x)t滿(mǎn)足時(shí)，錯(cuò)誤碼元沒(méi)有集中到碼字的最低n-k位碼元內(nèi)，§ 則必有循環(huán)移位后的錯(cuò)誤圖樣多項(xiàng)式Ei(x)的次數(shù)大于等于g(x)的次數(shù)。§ 進(jìn)而有

33、：Ei(x)=q(x)g(x)+Si(x), 相應(yīng)有：Ci(x)=Ei(x)+Si(x)=q(x)g(x)；這樣組成的Ci(x)為g(x)的倍式，必然為一個(gè)碼字多項(xiàng)式，§ 再由定理，線性分組碼的最小碼距等于非0碼字的最小漢明重量，有：W(Ei(x)+Si(x)=W(Ci(x)d=2t+1 (已知碼字可糾t位錯(cuò))§ 由漢明三角不等式：對(duì)于一個(gè)(n,k)線性分組碼C，C1,C2,C3為C中的三個(gè)碼字，并為C3=C1+C2，這時(shí)有：d(C1,C2)d(C1,C3)+d(C3,C2)，或表示為W(C1+C2)W(C1)+W(C2)§ W(Ei(x)+W(Si(x)W(Ei

34、(x)+Si(x)d=2t+1§ 由已知W(Ei(x)t，所以得出W(Si(x)t+1>t；這與立題假設(shè)W(Si(x)t，矛盾，這說(shuō)明當(dāng)W(Si(x)t時(shí)，錯(cuò)誤碼元不可能不集中在碼字的最低n-k位碼元內(nèi)。定理證畢。例題：已知二元(15,7)循環(huán)碼，生成多項(xiàng)式g(x)=x8+x7+x6+x4+1，dmin=5，其糾錯(cuò)能力為t=2，可以糾兩位錯(cuò)。由t=2<n/k=15/7，滿(mǎn)足捕錯(cuò)譯碼的必要條件，可以用捕錯(cuò)譯碼方法進(jìn)行譯碼。譯碼電路原理圖如下：門(mén)1門(mén)2門(mén)58級(jí)緩存器7級(jí)緩存器門(mén)3門(mén)4W(Si(x)2檢測(cè)電路譯碼過(guò)程如下：§ 譯碼前所有移位寄存器和緩存器都為全0狀態(tài)，

35、門(mén)2，門(mén)3開(kāi)，門(mén)1，門(mén)4，門(mén)5關(guān)。n=15次移位后，接收碼字的R(x)的15個(gè)碼元全部進(jìn)入15級(jí)緩存器，信息元在前7級(jí)，監(jiān)督元在后8級(jí)，同時(shí)進(jìn)入除法電路，得到校驗(yàn)子多項(xiàng)式S0(x)。如果S0(x)=0，說(shuō)明無(wú)錯(cuò)，打開(kāi)門(mén)5，輸出接收碼字。如果S0(x)0，說(shuō)明有錯(cuò)，進(jìn)行以下各步。§ 此時(shí)門(mén)2關(guān)，門(mén)1開(kāi)，如果W(S0(x)2，檢測(cè)電路輸出有效，把門(mén)4打開(kāi)，把門(mén)3關(guān)閉，此時(shí)除法電路移位寄存器中的內(nèi)容就是接收碼字的后8位的錯(cuò)誤圖樣，只要接收碼字只錯(cuò)2位或2位以下，后8位錯(cuò)誤圖樣就等于全部錯(cuò)誤圖樣。這時(shí)移位15次，除法電路的狀態(tài)S0(x)=EP(x)通過(guò)門(mén)4與接收碼字的后8位逐次相加，完成糾錯(cuò)

36、。然后門(mén)1關(guān)，門(mén)5開(kāi)，再移位15次，輸出接收碼字。§ 如果W(S0(x)>2，則15級(jí)緩存器和除法電路都循環(huán)移位一次，再次檢測(cè)，若仍大于2，則繼續(xù)移位，當(dāng)移位I次后，檢測(cè)到W(S0(x)2，則說(shuō)明已經(jīng)檢測(cè)出錯(cuò)誤圖樣已進(jìn)入緩存器的后8位。這時(shí)門(mén)3關(guān)閉，門(mén)4打開(kāi)，繼續(xù)移位n-I次，進(jìn)行糾錯(cuò)。最后門(mén)1關(guān)，門(mén)2，門(mén)5開(kāi)，再移位15次輸出正確的接收碼字。從以上步驟中可以看出，譯碼器完成一個(gè)碼字的譯碼，共需要3n次移位。這里介紹的是捕錯(cuò)譯碼器的基本原理，若要實(shí)現(xiàn)連續(xù)譯碼，還要進(jìn)行一些改進(jìn)，一方面力圖使譯碼器電路簡(jiǎn)單化，另一方面提高譯碼速度，減少移位次數(shù)。6-3-3 大數(shù)邏輯譯碼循環(huán)碼譯碼器

37、的復(fù)雜性取決于碼的代數(shù)結(jié)構(gòu)，對(duì)于一類(lèi)循環(huán)碼來(lái)說(shuō)，有一種比較簡(jiǎn)單的譯碼方法稱(chēng)為大數(shù)邏輯譯碼，1954年由Reed提出。循環(huán)碼的監(jiān)督矩陣描述：前面我們介紹過(guò)，已知循環(huán)碼的生成多項(xiàng)式g(x)，可以得到非系統(tǒng)循環(huán)碼的生成矩陣。G(x)=xk-1g(x)xk-2g(x)g(x)相應(yīng)的生成矩陣為：G=gn-kgn-k-1g1g0000gn-kgn-k-1g1g0000gn-kgn-k-1g1g0根據(jù)循環(huán)碼的生成多項(xiàng)式一定為xn+1的因式，有xn+1=g(x)h(x)=(gn-kxn-k+g1x+g0)(hkxk+h1x+h0)根據(jù)這個(gè)關(guān)系可以看出：gn-khk=1g0h0=1而其它乘積項(xiàng)的系數(shù)為0。即g0

38、h1+g1h0=0g0h2+g1h1+g2h0=0gn-1h0+gn-2h1+gn-khk-1=0根據(jù)生成矩陣與監(jiān)督矩陣的關(guān)系，可知H=h0h1hk0000h0h1hk00000h0h1hkH矩陣為n-k行n列。它完全由h(x)的系數(shù)決定的，h(x)稱(chēng)為循環(huán)碼的校驗(yàn)多項(xiàng)式或稱(chēng)為監(jiān)督多項(xiàng)式。生成矩陣與監(jiān)督矩陣的關(guān)系為：GHT=0例如：(7,4)循環(huán)碼的生成多項(xiàng)式g(x)=x3+x+1，而監(jiān)督多項(xiàng)式為h(x)=x4+x2+x+1。相應(yīng)的生成矩陣和監(jiān)督矩陣分別為：G=1011000010110000101100001011H=111010001110100011101可以驗(yàn)證：GHT=0，還可以看出

39、，這個(gè)監(jiān)督矩陣經(jīng)過(guò)列變換可以變?yōu)橄到y(tǒng)碼的監(jiān)督矩陣，而且就是漢明碼的一致監(jiān)督矩陣。如果將這個(gè)碼的生成矩陣當(dāng)作另一個(gè)碼的監(jiān)督矩陣，而將這個(gè)碼的監(jiān)督矩陣當(dāng)作另一個(gè)碼的生成矩陣，這另一個(gè)碼就是這個(gè)碼的對(duì)偶碼。例如：g(x)=x3+x2+1的(7,4)循環(huán)碼，是g(x)=x4+x3+x2+1的(7,3)循環(huán)碼的對(duì)偶碼，g(x)=x3+x+1的(7,4)循環(huán)碼，是g(x)=x4+x2+x+1的(7,3)循環(huán)碼的對(duì)偶碼。系統(tǒng)循環(huán)碼的生成矩陣與監(jiān)督矩陣：由于循環(huán)碼的生成矩陣的每一行都為一個(gè)碼字，系統(tǒng)循環(huán)碼的生成矩陣的k個(gè)行向量分別為(100),(0100),.(0001)信息碼對(duì)應(yīng)的循環(huán)碼字。因此，已知一個(gè)(

40、n,k)碼的生成多項(xiàng)式，求出這些碼字所對(duì)應(yīng)的監(jiān)督碼元作為行向量的后r位，就可以得到生成矩陣的標(biāo)準(zhǔn)型。用多項(xiàng)式表示的生成多項(xiàng)式的標(biāo)準(zhǔn)型為：G(x)=xn-1r1(x)xn-2r2(x)xn-krk(x)其中r1(x)、r2(x)rk(x)分別為碼字多項(xiàng)式xn-1，xn-2xn-k除以g(x)的余式多項(xiàng)式。生成矩陣標(biāo)準(zhǔn)型為：G=1 0 0r10 1 0r20 0 1rkr1 r2 rk分別為r1(x)、r2(x)rk(x)的向量形式。例如：二元(7,4)循環(huán)碼的生成矩陣的標(biāo)準(zhǔn)型。由g(x)=x3+x+1r1(x)=xn-1/g(x)=x6/g(x)=x2+1 mod g(x) 對(duì)應(yīng)矢量r1=101

41、。r2(x)=xn-2/g(x)=x5/g(x)=x2+x+1 mod g(x) 對(duì)應(yīng)矢量r2=111。r3(x)=xn-3/g(x)=x4/g(x)=x2+x mod g(x) 對(duì)應(yīng)矢量r3=110。r4(x)=xn-4/g(x)=x3/g(x)=x+1 mod g(x) 對(duì)應(yīng)矢量r4=011。得到其生成矩陣的標(biāo)準(zhǔn)型為：G=1000101010011100101100001011看出G=Ik,Q，由GHT=0可得：系統(tǒng)循環(huán)碼的監(jiān)督矩陣為：H=111010001110101101001§ 到這里我們有兩種辦法得到系統(tǒng)線性分組碼的生成矩陣標(biāo)準(zhǔn)型和監(jiān)督矩陣；一種是上面介紹的已知g(x)的

42、方法，另一種是已知非標(biāo)準(zhǔn)型矩陣通過(guò)初等變換的方法。§ H矩陣通過(guò)列換位，可以變?yōu)闃?biāo)準(zhǔn)型；§ G矩陣通過(guò)列換位和初等行變換，可以變?yōu)闃?biāo)準(zhǔn)型。大數(shù)邏輯譯碼的原理：首先通過(guò)一個(gè)例子說(shuō)明大數(shù)邏輯譯碼的基本思想。已知(7,3)線性分組碼的生成多項(xiàng)式為：g(x)=x4+x3+x2+1，得到其監(jiān)督矩陣為：H=1011000111010011000100110001設(shè)發(fā)送碼字矢量為：C=(c6,c5,c4,c3,c2,c1,c0)，錯(cuò)誤圖樣矢量為：E=(e6,e5,e4,e3,e2,e1,e0)，接收碼字為R=C+E。相應(yīng)的校驗(yàn)子為ST=HET=1011000e6=s31110100e5s

43、21100010s10110001e0s0利用這個(gè)方程組的線性組合（變換），得到另一組校驗(yàn)方程：A1=s3=e6+e4+e3A2=s1=e6+e5+e1A3=s2+s0=e6+e2+e0這三個(gè)方程組的系數(shù)構(gòu)成三個(gè)矢量，(1011000),(1100010),(1000101)是H矩陣的行向量的線性組合，對(duì)于發(fā)送碼字C，根據(jù)HCT=0，可知：A1CT=A2CT=A3CT=0，或c6=H0CT=01011000c511000101000101c1c0這樣得到了一個(gè)新的校驗(yàn)方程：c6+c4+c3=0c6+c5+c1=0c6+c2+c0=0構(gòu)造的這個(gè)監(jiān)督方程組有這樣一個(gè)特點(diǎn)：每個(gè)方程中都有c6，而c5,c4,c3,c2,c1,c0則在各方程中只出現(xiàn)一次。有這種特點(diǎn)的監(jiān)督方程稱(chēng)為正交于c6的正交監(jiān)督方程。其系數(shù)矩陣H0稱(chēng)為正交監(jiān)督矩陣。H0=101100011000101000101定義：如果一個(gè)特定的碼元(xn-i)出現(xiàn)在H0矩陣的每個(gè)行，而其它碼元最多在其中一行中出現(xiàn)，則稱(chēng)H0為正交于碼元(xn-i)的正交一致監(jiān)督矩陣。(7,3)循環(huán)碼能夠糾正一位錯(cuò)，同時(shí)檢出兩位錯(cuò)。如果利用這個(gè)正交監(jiān)督矩陣對(duì)接收碼字進(jìn)行校驗(yàn)，可以看到：§ 如果只發(fā)生一位錯(cuò)，且r6錯(cuò)，e6=1，則A1=A2=A3=1;§ 如果