信息論與編碼

1、信息論與編碼-循環(huán)碼上次課小結(jié)： 線性分組碼的一些概念：域、矢量空間、線性 分組碼； 生成矩陣和校驗(yàn)矩陣 伴隨式與譯碼：伴隨式的定義、標(biāo)準(zhǔn)陣列譯碼 表。信息論與編碼-循環(huán)碼 循環(huán)碼是線性分組碼中最重要的一類碼。 循環(huán)碼的特點(diǎn)是：碼集C中任意一個(gè)碼字經(jīng)循環(huán)移位后仍然是碼字。 由于構(gòu)成碼集C的k維n重矢量空間的基底也一定是碼字，因此，k個(gè)基底可以是同一個(gè)基底經(jīng)循環(huán)移位得到。所以，只用一個(gè)基底就可以表示一個(gè)碼的特征，也就不需要用矩陣來(lái)描述。信息論與編碼-循環(huán)碼描述循環(huán)碼的重要的數(shù)學(xué)工具是多項(xiàng)式。設(shè)一個(gè)碼字為 ，可以用一個(gè)稱為碼多項(xiàng)式的多項(xiàng)式來(lái)表示，多項(xiàng)式的系數(shù)就是碼字的各個(gè)碼元的值，指數(shù)項(xiàng)表示碼元在

2、碼字中所處的位置，即對(duì)于二進(jìn)制碼， 。,021cccCnn012211)(cxcxcxcxCnnnn1 , 0ic信息論與編碼-循環(huán)碼當(dāng)C所對(duì)應(yīng)的碼字循環(huán)移位1位后，得到對(duì)應(yīng)的多項(xiàng)式為所以，可以用多項(xiàng)式乘以x來(lái)表示一次循環(huán)移位，因此有：0122110)(cxcxcxcxCnnnn1023121)(nnnnncxcxcxcxC)()(01xxCxC) 1mod(nx021,cccnn循環(huán)移1位1032,nnncccc信息論與編碼-循環(huán)碼以此類推。) 1mod() 1mod() 1mod()()()()()()()()(1-n210121021201nnnnnnxxxxCxxxCxCxCxxxCx

3、CxxCxC位：移位：移位：移 因?yàn)橐粋€(gè)碼字經(jīng)過(guò)n次循環(huán)移位后又變回自身，所以一個(gè)碼字經(jīng)循環(huán)移位最多產(chǎn)生n個(gè)碼字。 而對(duì)于碼長(zhǎng)為n的碼字，共有 個(gè)不同的碼字，因此，不可能由一個(gè)碼字經(jīng)循環(huán)移位得到所有可能的碼字。 但是，可以由一個(gè)基底矢量經(jīng)循環(huán)移位得到所有k個(gè)基底矢量，所有的碼字都可以由這k個(gè)基底的線性組合構(gòu)成。k2信息論與編碼-循環(huán)碼信息論與編碼-循環(huán)碼因此，設(shè) 對(duì)應(yīng)一個(gè)碼字，則其線性組合：其中，A(x)是任意多項(xiàng)式， 是一個(gè)碼多項(xiàng)式。也就是說(shuō)，任意一個(gè)碼多項(xiàng)式與一個(gè)多項(xiàng)式之積，仍然是一個(gè)碼多項(xiàng)式。上述運(yùn)算是在模運(yùn)算的前提下，即)(0 xC)()()()()()()()()(001122100

4、11j0220100 xCxAxCxaxaxaaxCxaxCxaxxCaxCaxCjjj)(0 xC) 1mod(nx信息論與編碼-循環(huán)碼從多項(xiàng)式的性質(zhì)出發(fā)，根據(jù)近世代數(shù)理論，可以得到以下結(jié)論：(1)一個(gè)(n,k)循環(huán)碼的碼多項(xiàng)式是模(xn+1)乘運(yùn)算下多項(xiàng)式交換環(huán)的一個(gè)主理想子環(huán)，反之，多項(xiàng)式交換環(huán)的一個(gè)主理想子環(huán)一定可以產(chǎn)生一個(gè)循環(huán)碼。而主理想子環(huán)中的所有碼多項(xiàng)式都可以由其中一個(gè)元素(碼多項(xiàng)式)的倍式組成，這個(gè)元素稱為該主理想子環(huán)的生成元，或稱它為對(duì)應(yīng)循環(huán)碼的生成多項(xiàng)式。生成多項(xiàng)式不是唯一的，但總有一個(gè)是最低的。信息論與編碼-循環(huán)碼（2）GF(2)上的（n，k）循環(huán)碼中，存在著唯一的一個(gè)次

5、數(shù)最低（n-k次）的首一（即第一項(xiàng)的系數(shù)為1）碼多項(xiàng)式g(x)：使得所有的碼多項(xiàng)式都是g(x)的倍式，即且所有小于n次的g(x)的倍式都是碼多項(xiàng)式。g(x)稱為生成多項(xiàng)式。1)(12211xgxgxgxxgknknkn)()()(xgxmxC信息論與編碼-循環(huán)碼（3）（n，k）循環(huán)碼的生成多項(xiàng)式g(x)一定是 的因子，寫為 ，或 。反之，如果g(x)是 的（n-k）次因子，則g(x)一定是（n，k）循環(huán)碼的生成多項(xiàng)式。1nx1| )(nxxg)()(1xhxgxn1nx信息論與編碼-循環(huán)碼 （n，k）循環(huán)碼的構(gòu)造方法為：（1）對(duì) 做因式分解，找出其（n-k）次因子；（2）以該（n-k）次因子為

6、生成多項(xiàng)式g(x)，與信息多項(xiàng)式m(x)相乘，得到的多項(xiàng)式C(x)=m(x)g(x)即為碼多項(xiàng)式。1nx信息論與編碼-循環(huán)碼例題：研究一個(gè)長(zhǎng)度為7的循環(huán)碼的構(gòu)成方法。解：根據(jù)上面的循環(huán)碼編碼方法，首先對(duì) 做因式分解，得到17x) 1)(1)(1(13237xxxxxx信息論與編碼-循環(huán)碼所以， 的因子共有以下幾種： ：次數(shù)為1（1個(gè)）； ， ：次數(shù)為3（2個(gè)）； ， ：次數(shù)為4（2個(gè)）； ：次數(shù)為6（1個(gè)）；如果給定了n和k，那么只能選用滿足要求的（n-k）次多項(xiàng)式作為生成多項(xiàng)式，本題中沒(méi)有要求k，可以選用不同的多項(xiàng)式做生成多項(xiàng)式，當(dāng)然會(huì)得到不同的碼集。17x) 1( x) 1(23 xx)

7、1(3 xx) 1)(1(23xxx) 1)(1(3xxx) 1)(1(233xxxx信息論與編碼-循環(huán)碼設(shè)選取 為生成多項(xiàng)式，則n-k=3，k=4，所以信息多項(xiàng)式為信息碼組共有16種不同的組合，因此，共有16個(gè)碼字。例如則循環(huán)編碼后的碼多項(xiàng)式為對(duì)應(yīng)的碼字為（0101110）。) 1()(23xxxg1)(32231xmxmxmxm)0110()(0123mmmmmxxxxxxxxxC235232) 1)()(信息論與編碼-循環(huán)碼o 相同地，可以得到不同信息組的時(shí)候的碼字?？梢钥闯?，碼集中有四組碼字循環(huán)信息比特碼字（循環(huán)1）信息比特 碼字（循環(huán)2） 信息比特 碼字 （循環(huán)3和4）0001001

8、0010010001101011111100001101001101001101001101000101000101000111000110001101101100010110101001111100101110101110101110001110011110010110010110010110000101100000001111111信息論與編碼-循環(huán)碼一致校驗(yàn)多項(xiàng)式如果 分解為 ，選g(x)為生成多項(xiàng)式，則h(x)稱為碼的一致校驗(yàn)多項(xiàng)式，階次為k，和校驗(yàn)矩陣類似，校驗(yàn)多項(xiàng)式滿足：當(dāng)然，也可以選擇h(x)為碼生成多項(xiàng)式，則g(x)就是一致校驗(yàn)多項(xiàng)式。因此，由g(x)生成的（n，k）碼和由h(

9、x)生成的（n，k）碼互為對(duì)偶碼。1nx)()(1xhxgxn) 1mod(0) 1)()()()()()(nnxxxmxhxgxmxhxC信息論與編碼-循環(huán)碼循環(huán)碼是線性分組碼的一種。對(duì)于線性分組碼，可以用生成矩陣來(lái)描述。具體到循環(huán)碼，則簡(jiǎn)化為生成多項(xiàng)式。因此也一定可以用生成矩陣來(lái)描述循環(huán)碼。所謂生成矩陣，就是碼空間的一組基底。而生成多項(xiàng)式及其移位后的一組多項(xiàng)式，就可以作為一組基底，因此，如果循環(huán)碼的生成多項(xiàng)式為1)(111xgxgxxgknknkn信息論與編碼-循環(huán)碼則生成矩陣為這種形式的生成矩陣不是系統(tǒng)形式的。如果要生成系統(tǒng)形式的生成矩陣，則第l行應(yīng)是多項(xiàng)式100000010010110

10、0010010001)()()()(12112121121121ggggggggggggGxgxxgxgxxgxknknknknkk信息論與編碼-循環(huán)碼這里， 是 除以g(x)的余式，因?yàn)樗杂捎趃(x)是碼字，所以 也是碼字，因此 也一定是碼字，可以作為基底。klxRxlln, 2 , 1),()(xRllnx)()()(xRxgxQxllln)()()(xgxQxRxllln)()(xgxQl)(xRxlln信息論與編碼-循環(huán)碼實(shí)際上，可以由生成多項(xiàng)式直接得到系統(tǒng)碼。因?yàn)橄到y(tǒng)碼中，信息位占據(jù)了碼字的前k個(gè)位置，而信息多項(xiàng)式為如果用 乘以m(x)，得到如果在其后加上n-k比特的校驗(yàn)位，就構(gòu)成

11、了碼字.012211)(mxmxmxmxmkkkkknxknknnknkknxmxmxmxmxmx0112211)(信息論與編碼-循環(huán)碼也就是說(shuō)，要在上面的多項(xiàng)式后面加上次數(shù)底于n-k的多項(xiàng)式。這個(gè)多項(xiàng)式應(yīng)該是用g(x)除 ，得到的余式r(x)（商為Q(x)），即也就是說(shuō)，得到的碼多項(xiàng)式為由于g(x)是碼多項(xiàng)式，因此Q(x)g(x)也是碼字，這樣由信息多項(xiàng)式得到的碼字一定是系統(tǒng)碼。)(xmxkn)()()()(xrxgxQxmxkn)()()()(xgxQxrxmxkn信息論與編碼-循環(huán)碼歸納起來(lái)，我們可以得到由信息組得到對(duì)應(yīng)系統(tǒng)碼字的方法是：（1）由信息組得到信息多項(xiàng)式，將信息多項(xiàng)式 乘以

12、；（2）用g(x)除 ，得到余式r(x)；（3）將r(x)加在 后面，得到碼多項(xiàng)式，從而得到其對(duì)應(yīng)的碼字（碼多項(xiàng)式的系數(shù)）。)(xmknx)(xmxkn)(xmxkn信息論與編碼-循環(huán)碼例題： （7，4）循環(huán)碼的生成多項(xiàng)式為求（1）該循環(huán)碼系統(tǒng)形式的生成矩陣；（2）對(duì)于給定的信息組（1001），求其對(duì)應(yīng)的系統(tǒng)形式的碼字。1)(3xxxg信息論與編碼-循環(huán)碼解： （1）生成矩陣 將生成多項(xiàng)式及其對(duì)應(yīng)的循環(huán)移位多項(xiàng)式作為基底，得到一般形式的生成矩陣為1101000011010000110100001101G信息論與編碼-循環(huán)碼o 系統(tǒng)形式的生成矩陣：一種辦法是將一般形式的生成矩陣通過(guò)行變換和列置換

13、，得到系統(tǒng)形式； 通過(guò)矩陣運(yùn)算:將矩陣第3,4行加到第1行: 將矩陣第4行加到第2行1101000011010011100101010001G信息論與編碼-循環(huán)碼另一種方法：第一行，前四列為1000，對(duì)應(yīng)的多項(xiàng)式為 ，除以生成多項(xiàng)式 ，得余式為 ，所以對(duì)應(yīng)的后三列為101；同樣的辦法，可以得到第二行為0100111；第三行為0010110；第四行為0001011；因此，得到系統(tǒng)形式的生成矩陣。6x1)(3xxxg1)(2 xxr信息論與編碼-循環(huán)碼（2）對(duì)應(yīng)信息組（1001）的碼字，可以由生成矩陣得到，也可以直接得到，即用信息組多項(xiàng)式 乘以得到 ，除以碼多項(xiàng)式 ，得余式為 ，因此，碼多項(xiàng)式為對(duì)

14、應(yīng)的碼字為：10011101)(3012233xmxmxmxmxm3xxkn36)(xxxmxkn1)(3xxxgxxxr2)(xxxxxrxmxxCkn236)()()(信息論與編碼-循環(huán)碼DDD1xX32循環(huán)碼編碼電路實(shí)現(xiàn)的硬件結(jié)構(gòu)圖 用除法器實(shí)現(xiàn)(7,4)循環(huán)碼編碼器11k2k1(m0,m1,m2,m3)o 帶反饋移存器構(gòu)成除以g(x)=x3+x+1的除法電路，反饋線的位置與g(x)的項(xiàng)對(duì)應(yīng)，左到右分別對(duì)應(yīng)1，x, x2 和x3 。正常做除法時(shí)，m(x)應(yīng)從除法器最左端(對(duì)應(yīng)g(x)常數(shù)項(xiàng)1)進(jìn)入。如m(x)右移一位，則應(yīng)從g(x)一次項(xiàng)x的位置進(jìn)入，相當(dāng)于作xm(x)運(yùn)算再去做除法。

15、信息論與編碼-循環(huán)碼o m(x)從xn-k =x3 的位置進(jìn)入，相當(dāng)于作xn-k m(x)運(yùn)算再去除以g(x)。每編一個(gè)碼需化n=7拍時(shí)間。前4拍時(shí)開(kāi)關(guān)k1 ，k2 在位置1，消息位先m3 再m2,m1,m0 依次輸入除法器做xn-k m(x) / g(x)運(yùn)算，同時(shí)依次該4個(gè)碼元輸出。 信息論與編碼-循環(huán)碼 到第4拍完成時(shí)，除法器移存里的數(shù)據(jù)就是余式系數(shù)。 后3拍消息停止輸入(空3拍)，k1 ，k2 倒向位置2，移存器斷開(kāi)反饋后不再起除法器而僅起一般移存器作用，其中的數(shù)據(jù)分3拍依次移出，作為第5到第7循環(huán)碼校驗(yàn)位的輸出。信息論與編碼-循環(huán)碼信息論與編碼-循環(huán)碼乘法電路已知兩多項(xiàng)式相乘為 C(

16、x)=A(x)B(x) =akbrxk+r+(akb r-1+ak-1br)xk+r-1 +(akb r-2+ak-1b r-1+ak-2br)xk+r-2+ +(akb r-i+ak-1b r-(i-1)+ak-ibr)xk+r-i+ +(a1b0+a0b1)x+a0b0 可用下圖所示的電路完成上述運(yùn)算過(guò)程。 該電路由r個(gè)存貯單元組成的r 級(jí)移位寄存器， 至多r個(gè)模q相加器和至多(r+1)個(gè)模q常乘器所組成。 信息論與編碼-循環(huán)碼乘B(x)運(yùn)算電路 信息論與編碼-循環(huán)碼o 工作開(kāi)始時(shí)， r級(jí)移位存貯器中的存數(shù)全清洗為 0， 且規(guī)定被乘多項(xiàng)式A(x)的高次項(xiàng)系數(shù)ak首先送入電路， 電路的工作過(guò)

17、程如下： (1) 當(dāng)A(x)的最高次系數(shù)ak首先送入時(shí)， 乘積C(x)的最高次項(xiàng)xk+r的系數(shù)akbr就出現(xiàn)在輸出端， 同時(shí)ak存入移存器的第一級(jí)(最左一級(jí))。 信息論與編碼-循環(huán)碼 (2) A(x)的第二個(gè)系數(shù)ak-1送入電路時(shí),ak由第一級(jí)輸出送入第二級(jí),同時(shí)與b r-1相乘和ak-1 br相加后送到輸出端,這就是C(x)的x k+r-1項(xiàng)系數(shù)akb r-1+ak-1 br。 此時(shí)， 移存器內(nèi)的存貯數(shù)據(jù)為ak-1， ak， 0， 0， ， 0(自左至右)。 信息論與編碼-循環(huán)碼(3) 上述過(guò)程重復(fù)進(jìn)行， 直至k次移位后， A(x)的系數(shù)全部送入移存器。k+r+1次移位后， 移存器輸出C(x

18、)的常數(shù)項(xiàng)a0+b0， 移存器中的內(nèi)容全部恢復(fù)到全為 0 初態(tài)， 乘法 完成。 由上面乘法過(guò)程可以看出,這種乘法電路完成一次乘法運(yùn)算,共需移位k+ r+1次。 信息論與編碼-循環(huán)碼圖 5 - 4 另一種乘B(x)電路 多項(xiàng)式除法電路 GF(q)上的兩多項(xiàng)式 A(x)=akxk+ak-1xk-1+a1x+a0 B(x)=brxr+br-1x r-1+b1x+b0 由歐幾里德除法可知： A(x)=q(x)B(x)+r(x) 0r(x)B(x) 或 r(x)=0假設(shè)kr， 否則q(x)=0， r(x)=A(x)。 多項(xiàng)式A(x)被B(x)除的電路如下圖所示， 它由r級(jí)移存器、 至多r個(gè)GF(q)加法

19、器和至多r+1個(gè)常乘器組成。 kr信息論與編碼-循環(huán)碼 除B(x)=brxr+b1x+b0電路 信息論與編碼-循環(huán)碼 為了理解除法電路的工作過(guò)程， 下面我們列出B(x)除A(x)的豎式運(yùn)算式子： brxr+b r-1 x r-1+b1x+b0 (除式)b-1rakxk-r+b-1r(ak-1-b-1rbr-1ak)xk-r-1+ (商式) akxk+ak-1xk-1+a1x+a0 (被除式) -(akxk+b-1rbr-1akxk-1+b0b-1rakxk-r) (ak-1-b-1rbr-1ak)xk-1+(ak-r-b0b-1rak)xk-r+(A) -(ak-1-b-1rbr-1ak)xk

20、-1+) (余式) 由上面式子， 我們討論除法電路的工作過(guò)程。 信息論與編碼-循環(huán)碼 (1) 開(kāi)始運(yùn)算時(shí)r級(jí)移存器中的存數(shù)全部清為0。 第一個(gè)移位節(jié)拍后， 被除多項(xiàng)式 A(x)的最高次項(xiàng)xk的系數(shù)ak首先進(jìn)入電路的最左一級(jí)。 r次移位后ak進(jìn)入到移存器的最右一級(jí)中， 此時(shí)自左至右移存器中的內(nèi)容為ak-r+1， ak-r+2， ， ak-1， ak。 信息論與編碼-循環(huán)碼 (2) 第r+1次移位后， ak輸出與b-1r 相乘得到ak b-1r ， 這就是商式q(x)的第一項(xiàng)xk-r的系數(shù)。 akb-1r同時(shí)反饋到后面各級(jí)寄存器中(所以稱這種除法電路為線性反饋移存器)減去akb-1rB(x)， 所

21、以， 此時(shí)移存器中自左至右的內(nèi)容為(ak-r-b0b-1rak),(ak-r+1-b1b-1rak)， ， (ak-1-br-1 b-1rak)， 這相應(yīng)于豎式運(yùn)算中的第A項(xiàng)所示的結(jié)果。 信息論與編碼-循環(huán)碼o (3) 依次類推， 經(jīng)k+1 次移位后， 完成了整個(gè)除法運(yùn)算過(guò)程。 它的輸出為商式q(x)， 而移存器中的內(nèi)容就是余式r(x)的系數(shù)信息論與編碼-循環(huán)碼o 例 設(shè)除式B(x)=x3+x+1， 被除式A(x)=x4+x3+1都是GF(2)上的多項(xiàng)式， 求B(x)除A(x)的電路。 除B(x)的除法電路如下圖 所示， 它由 3 級(jí)移存器和 2 個(gè)模 2 相加器組成。 因?yàn)樵贕F(2)中，

22、1 的逆元仍為 1， 相加和相減相同， 所以b-1r與-bi常乘器均為一條閉合線。 信息論與編碼-循環(huán)碼圖 5 - 7 除B(x)=x3+x+1電路 信息論與編碼-循環(huán)碼o 完成上述兩個(gè)多項(xiàng)式相除的長(zhǎng)除法運(yùn)算式如下： x+1 (商式) x3+x+1 x4+x3 +1 (被除式) (除式) x4 +x2+x x3+x2+x+1 x3 +x+1 x2 (余式)信息論與編碼-循環(huán)碼 這里 x4+x3+1=(x+1)(x3+x+1)+x2 商為x+1， 余式為x2。 下表 5 - 4 中列出了電路的工作過(guò)程。 顯然， r+1=4 次移位后得到商的第一個(gè)系數(shù)， k+1=5 次移位后， 就完成了整個(gè)除法運(yùn)

23、算， 并在D0、D1、D2組成的移存器中保留了余式001， 即x2。 信息論與編碼-循環(huán)碼B(x) 除x4+x3+1 的運(yùn)算過(guò)程表信息論與編碼-循環(huán)碼 多項(xiàng)式相乘相除電路 GF(q)上的多項(xiàng)式A(x)、 H(x)、 G(x)分別為： A(x)=akxk+ak-1xk-1+a1x+a0 H(x)=hrxr+h r-1 x r-1+h1x+h0 G(x)=grxr+g r-1 x r-1+g1x+g0 若A(x)與H(x)相乘后再用G(x)除， 則 A(x)H(x)=q(x)G(x)+r(x) 0r(x)G(x)， 或 r(x)=0 信息論與編碼-循環(huán)碼 該運(yùn)算可用圖 所示的電路實(shí)現(xiàn)， 它由r級(jí)移

24、存器、 至多有2(r+1)個(gè)GF(q)的常乘器和r+1個(gè)GF(q)的相加器組成。 顯然， 該電路就是乘法電路與除法電路的兩種電路的結(jié)合。 如果H(x)與G(x)次數(shù)不等， 則只要按G(x)與H(x)中最高次數(shù)設(shè)計(jì)移存器級(jí)數(shù) 即可。 信息論與編碼-循環(huán)碼圖 5 - 8 乘H(x)除G(x)電路 信息論與編碼-循環(huán)碼例 設(shè)GF(2)上的 3 個(gè)多項(xiàng)式為： A(x)=x4+x+1，H(x)=x2+1， G(x)=x3+x+1 則 A(x)H(x)=(x4+x+1)(x2+1)=x6+x4+x3+x2+x+1 =x3(x3+x+1)+(x2+x+1) =q(x)G(x)+r(x) 可用下圖的電路實(shí)現(xiàn)，

25、 該電路的工作過(guò)程如下表所示， 移位A(x)+1=5 次后， 即得到了商式x3 和余式x2+x+1。 信息論與編碼-循環(huán)碼 圖 5 - 9 乘(x2+1)除(x3+x+1)電路 信息論與編碼-循環(huán)碼 若GF(2)上的多項(xiàng)式 A(x)=x4+x+1， H(x)=x3+x+1， G(x)=x2+1 則 A(x)H(x)=(x4+x+1)(x3+x+1)=x7+x5+x3+x2+1 =(x5+x+1)(x2+1)+x=q(x)G(x)+r(x) 該運(yùn)算可用下圖所示的電路實(shí)現(xiàn)， 它的工作 過(guò) 程 如 下 表 所 示 。 顯 然 ， 移 位 A(x)+H(x)+1-G(x)=6 次后， 電路即可完成運(yùn)算

26、， 它的輸出是商 q(x)= (x5+x+1)， 在移存器中保留了余式x。信息論與編碼-循環(huán)碼圖 5 - 10 乘(x3+x+1)除(x2+1)電路信息論與編碼-循環(huán)碼電路運(yùn)算過(guò)程表 o 循環(huán)碼將生成矩陣簡(jiǎn)化為生成多項(xiàng)式，從而將與編碼矩陣對(duì)應(yīng)的硬件陣列（平面型）簡(jiǎn)化為帶反饋的移存器（直線型）。o 針對(duì)循環(huán)碼的特點(diǎn)，在譯碼上也出了許多高效的算法，如捕錯(cuò)譯碼、大數(shù)邏輯譯碼等，限于篇幅，這里不再討論譯碼的問(wèn)題。信息論與編碼-循環(huán)碼信息論與編碼-循環(huán)碼 一個(gè)碼可以兼有很多的特點(diǎn)，循環(huán)特征僅是其中之一。前面講過(guò)的漢明碼也可以兼有循環(huán)特征，這類碼叫循環(huán)漢明碼，其分組長(zhǎng)度是n=2m1,校驗(yàn)位nk=m，而任何

27、碼字的循環(huán)依然是碼字。同樣，兼有循環(huán)特征的高萊碼叫作循環(huán)高萊碼，比如用生成多項(xiàng)式g(x)=x11+x9+x7+x6+x5+x+1 產(chǎn)生的線性（23，12）高萊碼就是循環(huán)高萊碼。在無(wú)線信道上應(yīng)用最廣泛的BCH碼、RS碼也是循環(huán)碼，它們?cè)诰哂醒h(huán)特性的基礎(chǔ)上又兼有另一些特點(diǎn)。信息論與編碼-BCH碼和RS碼BCH碼o BCH（Bose：Chaudhuri-Hocquenghem）碼是循環(huán)碼中一大子類，它可以是二進(jìn)制碼，也可以是非二進(jìn)制碼。二進(jìn)制本原BCH碼具有下列參數(shù)：式中m（m=3）和糾錯(cuò)能力t( )是任意正整數(shù)。12mnmtkn12min td12m信息論與編碼-BCH碼和RS碼o BCH碼的基

28、本特點(diǎn)是其生成多項(xiàng)式g(x)包含2t個(gè)連續(xù)冪次的根。由上面關(guān)于循環(huán)碼的論述可知，若在二元域GF(2)上把 分解為l個(gè)最小多項(xiàng)式m(x)，i1,2,l 之積，其中l(wèi)1個(gè)組成g(x)而剩余的組成h(x)，則包含于g(x)中的最小多項(xiàng)式一定滿足式中“|”表示整除，C（x）表示碼多項(xiàng)式。 1nx) 1( | )(| )(| )(nixxCxgxm信息論與編碼-BCH碼和RS碼o 由近世代數(shù)可進(jìn)一步得知，在二元擴(kuò)域GF(2m)上可把xn+1分解為如下n個(gè)根的乘積式中，a是GF(2m)上本原元，n（2m1）。若對(duì)于每個(gè)j，j1，2，2t，均有即g(x)包含2t個(gè)連續(xù)冪次的根,則由該g(x)生成的循環(huán)碼就是

29、糾錯(cuò)能力不小于t的BCH碼)()()() 1(1210nnaxxxxx11)()(| )liijxmxgax（信息論與編碼-BCH碼和RS碼 BCH的出現(xiàn)為通訊系統(tǒng)設(shè)計(jì)者們?cè)诩m錯(cuò)能力，碼長(zhǎng)和碼率的靈活設(shè)計(jì)上提供了很大的選擇余地，一旦要求的糾錯(cuò)能力t給定，只要算出2t個(gè)連續(xù)冪次的根所對(duì)應(yīng)的多項(xiàng)式作為生成多項(xiàng)式，即可得出糾錯(cuò)能力符合要求的碼。 又因其構(gòu)碼方法帶來(lái)的譯碼特點(diǎn)，使之可以用伯利坎普（Berlekamp）迭代譯碼等通用，高效的譯碼算法，以致BCH碼從70年代起已成為線性分組碼的主流。信息論與編碼-BCH碼和RS碼o 已知碼長(zhǎng)n及糾錯(cuò)能力t，二元本原BCH碼的具體設(shè)計(jì)步驟如下：1。由關(guān)系式n

30、=2m-1算出m，查表找到m次本原多項(xiàng)式P(x)，用它產(chǎn)生一個(gè)GF(2m)擴(kuò)域2。以本原多項(xiàng)式P(x)的根為本原元a，分別計(jì)算2t個(gè)連續(xù)冪次根a，a2，a2t所對(duì)應(yīng)的二元域上的最小多項(xiàng)式m1(x), m2(x), , m2t(x).3。計(jì)算這些最小多項(xiàng)式的最小公倍式，得到生成多項(xiàng)式為 g(x)=LCM(m1(x), m2(x), , mt2(x)4. 得到BCH碼字 c(x)=m(x)g(x)信息論與編碼-BCH碼和RS碼o 例 設(shè)計(jì)一個(gè)n=7的二元本原BCH碼，求出不同糾錯(cuò)能力下的生成多項(xiàng)式。解：因7=23-1,因此m=3.1.查表找出一個(gè)三次本原多項(xiàng)式，本題為P(x)=x3+x+1然后令a

31、為P(x)的根，生成擴(kuò)域GF(23)的所有元素，見(jiàn)表6-7最大糾錯(cuò)能力為t=3。信息論與編碼-BCH碼和RS碼2。每個(gè)根所對(duì)應(yīng)的最小多項(xiàng)式，由表6-7給出3。對(duì)于給定的t，求連續(xù)冪次所對(duì)應(yīng)的最小多項(xiàng)式的最小公倍式如t=1, 連續(xù)冪次為a,a2,生成多項(xiàng)式為 g(x)=LCM(m1(x),m2(x)=x3+x+1生成一個(gè)(7,3)BCH碼，即漢明碼t=2, g(x)=x6+x5+x4+x3+x2+x+1生成一個(gè)(7,1)BCH碼。t=3, g(x)= x6+x5+x4+x3+x2+x+1糾錯(cuò)能力至少是t.元素 多項(xiàng)式 矢量表示 極小多項(xiàng)式 0 0 000 x a0 1 001 x+1 a1 a

32、010 x3+x+1 a2 a2 100 x3+x+1 a3 a+1 011 x3+x2+1 a4 a2 +a 110 x3+x+1 a5 a2 +a+1 111 x3+x2+1 a6 a2 +1 101 x3+x2+1 x3+x+1生成的GF（23）擴(kuò)域信息論與編碼-BCH碼和RS碼o RS譯碼譯碼RS譯碼（ReedSolomon里德-索羅門碼）屬于BCH碼的一個(gè)子類，是一種q進(jìn)制（q2）的BCH碼，其碼的每個(gè)碼元取值于符號(hào)集0,a0,a1,aq-2 實(shí)用時(shí)通常選取q為2的冪次（q2m），以便一組m個(gè)信息比特可以一一映射到q個(gè)符號(hào)之一，也便于與4，8，16，32，信號(hào)點(diǎn)集的PSK或QAM調(diào)制

33、相適應(yīng)。若m8即256進(jìn)制，可以將整個(gè)8比特字節(jié)變?yōu)镽S碼的一個(gè)碼元。 信息論與編碼-BCH碼和RS碼o 如果用N表示RS碼的碼長(zhǎng)，K表示信息符號(hào)的長(zhǎng)度，NK表示校驗(yàn)符號(hào)碼的長(zhǎng)度，則RS碼的參數(shù)可以用以下式子來(lái)表達(dá) 碼長(zhǎng)n=q-1 校驗(yàn)位n-k=2t 最小距離dmin=n-k+1(MDC碼) 生成多項(xiàng)式g(x)=(x-a)(x-a2)(x-a2t) =an-kxn-k+an-k-1xn-k-1+a1x+a0信息論與編碼-BCH碼和RS碼o RS碼的重量分布是已知的。碼重多項(xiàng)式第i次項(xiàng)的系數(shù)（重量為i的碼字個(gè)數(shù)）是 o RS碼之所以重要，原因之一是該碼的距離特性好，是（MDC）碼。第二是因?yàn)榇嬖?/p>

34、一種有效的硬判決法，使得在許多需要長(zhǎng)碼得應(yīng)用場(chǎng)合，該碼能夠被實(shí)現(xiàn)。第三是q進(jìn)制RS碼得二進(jìn)衍生碼具有良好的抗突發(fā)差錯(cuò)能力。 qADjiDqinjiijjiminmin1) 1(0) 1( 信息論與編碼-BCH碼和RS碼o 二進(jìn)制衍生碼 對(duì)于一個(gè)q=2m進(jìn)制（n，k）RS碼，如果不用q進(jìn)制調(diào)制發(fā)送，而是將每碼元對(duì)應(yīng)為m比特后以二進(jìn)制發(fā)送,實(shí)際上就是把q進(jìn)制RS碼化作了（mn，mk）二進(jìn)制衍生碼，這樣的二進(jìn)制衍生碼特別適用于糾突發(fā)差錯(cuò)，下面舉例說(shuō)明。 信息論與編碼-BCH碼和RS碼o 例，一個(gè)8進(jìn)制（7，3）RS碼的a冪次，多項(xiàng)式及三比特組這三種形式的符號(hào)集如表6-7，寫出相應(yīng)的RS碼的生成多項(xiàng)式

35、。如輸入的8進(jìn)制信息元為a5a3a1，問(wèn)編出的8進(jìn)制RS碼字是什么，糾錯(cuò)能力如何？解：n=7,k=3,dmin=n-k+1=5,糾錯(cuò)能力t=2，生成多項(xiàng)式為 g(x)=(x-a)(x-a2)(x-a3)(x-a4) =x4+a3x3+x2+ax+a3信息論與編碼-BCH碼和RS碼信息多項(xiàng)式為m(x)=a5x2+a3x+a，對(duì)應(yīng)碼字為c(x)=m(x)g(x)系統(tǒng)碼字為c(x)=xn-km(x)+r(x)=a5x6+a3x5+ax4+a6x3+a4x2+a2x+1 r(x)= xn-km(x) mod g(x)二進(jìn)制衍生碼：信息碼元： a5a3a1(111,011,010)碼字： a5a3aa6

36、a4a21 (111,011,010,101,110,100,001)信息論與編碼-BCH碼和RS碼o 衍生碼就突發(fā)錯(cuò)誤的能力：o 八進(jìn)制RS碼能糾每碼字兩個(gè)字符的差錯(cuò)。對(duì)于其二進(jìn)制衍生碼，若以二進(jìn)制信號(hào)在信道上傳送，突發(fā)差錯(cuò)長(zhǎng)度比特時(shí)最多影響到兩個(gè)八進(jìn)制符號(hào)時(shí)，可糾正；若突發(fā)差錯(cuò)長(zhǎng)度等于5時(shí)，可能只影響兩個(gè)八進(jìn)制符號(hào)，也可能跨三各八進(jìn)制符號(hào)，就不一定能糾正了。o 一般的結(jié)論：若q進(jìn)制（q=2m）RS碼的糾錯(cuò)能力是t個(gè)q進(jìn)制符號(hào)，那么它的二進(jìn)衍生碼能糾正的二進(jìn)制突發(fā)差錯(cuò)長(zhǎng)度b為1) 1(mtb信息論與編碼-碼的擴(kuò)展和縮短o 碼的擴(kuò)展和縮短： 可以通過(guò)增加或刪除信息位或校驗(yàn)位的方法改變碼率，改變

37、糾檢錯(cuò)能力，以滿足不同的需要。常用的方法有：增信，刪余，增余，刪信，及組合信息論與編碼-碼的擴(kuò)展和縮短o 擴(kuò)展碼 設(shè)C是一個(gè)最小距離為d的二進(jìn)制n,k,d線性分組碼， 它的碼字有奇數(shù)重量也有偶數(shù)重量。 若對(duì)每一個(gè)碼字(cn -1,cn -2, ,c1. c0)增加一個(gè)校驗(yàn)元c0， 滿足以下校驗(yàn)關(guān)系： cn-1+cn-2+c1+c0+c0=0 稱c0為全校驗(yàn)位。 若原碼的校驗(yàn)矩陣為H， 則擴(kuò)展碼 的校驗(yàn)矩陣為C1.1100HH2m-1， 2m-1-m， 3漢明碼的擴(kuò)張碼是2m， 2m-1-m， 4碼， 它的 中的H是漢明碼的校驗(yàn) 矩陣。最小碼距由3增加為4H信息論與編碼-碼的擴(kuò)展和縮短信息論與編

38、碼-碼的擴(kuò)展和縮短碼的縮短：縮短循環(huán)碼就是在(n，k)循環(huán)碼的 個(gè)碼字中挑選出前i位均為0的所有碼字，組成一個(gè)新的(n-i, k-i)縮短循環(huán)碼碼集。該碼集是原循環(huán)碼碼集的一個(gè)子集，子集里所有碼多項(xiàng)式的階數(shù)均小于n-i且能夠被生成多項(xiàng)式g(x)整除。反之，次數(shù)小于n-i的所有g(shù)(x)倍式一定包含于該子集中，是(n-i, k-i),縮短循環(huán)碼的一個(gè)碼多項(xiàng)式。一般來(lái)講，每縮短一位，碼字?jǐn)?shù)目減少一半。k2信息論與編碼-碼的擴(kuò)展和縮短knx特點(diǎn)：1. 碼的重量沒(méi)有變，2. 校驗(yàn)位的數(shù)量也沒(méi)有變（n-i-(k-i)=n-k）,因此(n-i,k-i)縮短循環(huán)碼的糾錯(cuò)能力于原來(lái)的（n,k）循環(huán)碼碼完全一樣，3. 碼率R下降了，由k/n變?yōu)?k-i)/(n-i).4. 循環(huán)碼的外部特征在縮短循環(huán)碼中已不復(fù)存在，縮短碼碼字的循環(huán)未必仍是碼字；5. 循環(huán)碼的內(nèi)部特征仍然存在，即所有的碼多項(xiàng)式一定能夠被g(x)整除。信息論與編碼-碼的擴(kuò)展和縮短o 這樣，縮短循