【正文】 式子 ， 我們討論除法電路的工作過(guò)程 。 信息論與編碼 循環(huán)碼 乘 B(x)運(yùn)算電路 信息論與編碼 循環(huán)碼 ?工作開(kāi)始時(shí)， r級(jí)移位存貯器中的存數(shù)全清洗為 0， 且規(guī)定被乘多項(xiàng)式 A(x)的高次項(xiàng)系數(shù) ak首先送入電路， 電路的工作過(guò)程如下： (1) 當(dāng) A(x)的最高次系數(shù) ak首先送入時(shí) ， 乘積C(x)的最高次項(xiàng) xk+r的系數(shù) akbr就出現(xiàn)在輸出端 ， 同時(shí) ak存入移存器的第一級(jí) (最左一級(jí) )。如 m(x)右移一位，則應(yīng)從 g(x)一次項(xiàng) x的位置進(jìn)入，相當(dāng)于作 xm(x)運(yùn)算再去做除法。 klxRx lln ,2,1),( ????)(xRl lnx ?)()()( xRxgxQx llln ???)()()( xgxQxRx llln ???)()( xgxQ l)( xRx lln ??信息論與編碼 循環(huán)碼 實(shí)際上，可以由生成多項(xiàng)式直接得到系統(tǒng)碼。 因此，由 g(x)生成的（ n， k）碼和由 h(x)生成的（ n， k）碼互為對(duì)偶碼。 反之，如果 g(x)是 的（ nk）次因子，則 g(x)一定是（ n， k）循環(huán)碼的生成多項(xiàng)式。 k2信息論與編碼 循環(huán)碼 信息論與編碼 循環(huán)碼 因此，設(shè) 對(duì)應(yīng)一個(gè)碼字，則其線(xiàn)性組合： 其中， A(x)是任意多項(xiàng)式， 是一個(gè)碼多項(xiàng)式。 ? 由于構(gòu)成碼集 C的 k維 n重矢量空間的基底也一定是碼字，因此， k個(gè)基底可以是同一個(gè)基底經(jīng)循環(huán)移位得到。所以，只用一個(gè)基底就可以表示一個(gè)碼的特征，也就不需要用矩陣來(lái)描述。也就是說(shuō)， 任意一個(gè)碼多項(xiàng)式與一個(gè)多項(xiàng)式之積，仍然是一個(gè)碼多項(xiàng)式 。 1?nx 1|)( ?nxxg)()(1 xhxgx n ??1?nx信息論與編碼 循環(huán)碼 ? （ n， k）循環(huán)碼的構(gòu)造方法為： （ 1）對(duì) 做因式分解，找出其（ nk）次因子； （ 2）以該（ nk）次因子為生成多項(xiàng)式 g(x)，與信息多項(xiàng)式 m(x)相乘，得到的多項(xiàng)式C(x)=m(x)g(x)即為碼多項(xiàng)式。 1?nx )()(1 xhxgx n ??)1m o d (0)1)(()()()()()( ????? nn xxxmxhxgxmxhxC信息論與編碼 循環(huán)碼 循環(huán)碼是線(xiàn)性分組碼的一種。因?yàn)橄到y(tǒng)碼中，信息位占據(jù)了碼字的前 k個(gè)位置，而信息多項(xiàng)式為 如果用 乘以 m(x)，得到 如果在其后加上 nk比特的校驗(yàn)位，就構(gòu)成了碼字 . 012211)( mxmxmxmxm kkkk ????? ???? ?knx ?knknnknkkn xmxmxmxmxmx ???????? ????? 0112211)( ?信息論與編碼 循環(huán)碼 也就是說(shuō)，要在上面的多項(xiàng)式后面加上次數(shù)底 于 nk的多項(xiàng)式。 信息論與編碼 循環(huán)碼 ? m(x)從 xnk =x3 的位置進(jìn)入，相當(dāng)于作 xnk m(x)運(yùn)算再去除以 g(x)。 信息論與編碼 循環(huán)碼 (2) A(x)的第二個(gè)系數(shù) ak1送入電路時(shí) ,ak由第一級(jí)輸出送入第二級(jí) ,同時(shí)與 b r1相乘和 ak1 br相加后送到輸出端 ,這就是 C(x)的 x k+r1項(xiàng)系數(shù)akb r1+ak1 br。 信息論與編碼 循環(huán)碼 (1) 開(kāi)始運(yùn)算時(shí) r級(jí)移存器中的存數(shù)全部清為0。 因?yàn)樵?GF(2)中， 1 的逆元仍為 1， 相加和相減相同， 所以 b1r與 bi常乘器均為一條閉合線(xiàn)。 信息論與編碼 循環(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ò)程如下表所示 。 信息論與編碼 BCH碼和 RS碼 BCH碼 ? BCH（ Bose： ChaudhuriHocquenghem）碼是循環(huán)碼中一大子類(lèi)，它可以是二進(jìn)制碼，也可以是非二進(jìn)制碼。由關(guān)系式 n=2m1算出 m，查表找到 m次本原多項(xiàng)式P(x)，用它產(chǎn)生一個(gè) GF(2m)擴(kuò)域 2。 若 m＝ 8即 256進(jìn)制，可以將整個(gè) 8比特字節(jié)變?yōu)?RS碼的一個(gè)碼元。對(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)，就不一定能糾正了。 一般來(lái)講，每縮短一位，碼字?jǐn)?shù)目減少一半。 信息論與編碼 碼的擴(kuò)展和縮短 例 5－ 4－ 6 用于 HDLC， ， ISDN和 7號(hào)信令的 CRC－ ITU－ T循環(huán)冗余校驗(yàn)碼的生成多項(xiàng)式為 1)(51216 ???? xxxxgCRC n－ k＝ 16位 r(x) 信息 k－ i位 0～ 15次 16～ ni1次 低次 高次 (先發(fā) ) 帶 CRC的幀結(jié)構(gòu) 信息論與編碼 碼的擴(kuò)展和縮短 根據(jù)循環(huán)碼定義， g （ x）必定是 的因式，而 g（ x）＝ 是本原多項(xiàng)式，它所能整除的 中 n的最小值是 2161，所以， g(x)生成的循環(huán)碼是一個(gè)（ 65535， 65519）循環(huán)碼 將該碼所有前 i位為零的碼字去除前 i位后集合在一起就構(gòu)成（ n－ i， k－ i）縮短循環(huán)碼，表現(xiàn)為 k－i信息位加上 16位 CRC組成長(zhǎng)度（ n－ i）的一個(gè)幀。 信息論與編碼 碼的擴(kuò)展和縮短 接收端校驗(yàn)時(shí)，只要將整個(gè)幀除以 g（ x）檢查余式是否為零即可。除法器的結(jié)構(gòu)與圖 5－4－ 4（ b）所示相同，只是接收序列由最左端而不是從 處輸入而已。 151216 ??? xxx1?nx1?nx信息論與編碼 碼的擴(kuò)展和縮短 g（ x）本身也是碼字，而且是最輕的碼字，所以本碼的 能糾一個(gè)錯(cuò)誤（ t＝ 1）或檢 3個(gè)差錯(cuò)。 信息論與編碼 碼的擴(kuò)展和縮短 ? 這樣，縮短循環(huán)碼的編、譯碼可以借用循環(huán)碼的方法，將消息多項(xiàng)式 m(x)乘以 后 除以 g(x) 即可，所不同的是這里的消息多項(xiàng)式 m(x)由 (ki)項(xiàng)組成而不是 k項(xiàng)組成。常用的方法有： 增信，刪余，增余，刪信，及組合 信息論與編碼 碼的擴(kuò)展和縮短 ?擴(kuò)展碼 設(shè) C是一個(gè)最小距離為 d的二進(jìn)制［ n,k,d］線(xiàn)性分組碼， 它的碼字有奇數(shù)重量也有偶數(shù)重量。碼重多項(xiàng)式第 i次項(xiàng)的系數(shù)（重量為 i的碼字個(gè)數(shù)）是 ? RS碼之所以重要，原因之一是該碼的距離特性好，是（ MDC）碼。計(jì)算這些最小多項(xiàng)式的最小公倍式，得到生成多項(xiàng)式為 g(x)=LCM(m1(x), m2(x), …, m t2(x)) 4. 得到 BCH碼字 c(x)=m(x)g(x) 信息論與編碼 BCH碼和 RS碼 ?例 設(shè)計(jì)一個(gè) n=7的二元本原 BCH碼，求出不同糾錯(cuò)能力下的生成多項(xiàng)式。 12 ?? mnmtkn ??12m in ?? td12 ?m信息論與編碼 BCH碼和 RS碼 ? BCH碼的基本特點(diǎn)是其生成多項(xiàng)式 g(x)包含 2t個(gè)連續(xù)冪次的根。 信息論與編碼 循環(huán)碼 圖 5 10 乘 (x3+x+1)除 (x2+1)電路 信息論與編碼 循環(huán)碼 電路運(yùn)算過(guò)程表