【正文】 若 A(x)與 H(x)相乘后再用 G(x)除 ， 則 A(x)H(x)=q(x)G(x)+r(x) 0≤r(x)＜ G(x)， 或 r(x)=0 信息論與編碼 循環(huán)碼 該運(yùn)算可用圖 所示的電路實(shí)現(xiàn)， 它由 r級移存器、 至多有 2(r+1)個 GF(q)的常乘器和r+1個 GF(q)的相加器組成。 信息論與編碼 循環(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) ， 它的工作過程如下表所示 。 信息論與編碼 循環(huán)碼 信息論與編碼 循環(huán)碼 一個碼可以兼有很多的特點(diǎn)，循環(huán)特征僅是其中之一。 信息論與編碼 BCH碼和 RS碼 BCH碼 ? BCH（ Bose： ChaudhuriHocquenghem）碼是循環(huán)碼中一大子類，它可以是二進(jìn)制碼，也可以是非二進(jìn)制碼。 1?nx)1(|)(|)(|)( ?ni xxCxgxm信息論與編碼 BCH碼和 RS碼 ?由近世代數(shù)可進(jìn)一步得知，在二元擴(kuò)域GF(2m)上可把 xn+1分解為如下 n個根的乘積 式中， a是 GF(2m)上本原元， n＝（ 2m－ 1）。由關(guān)系式 n=2m1算出 m，查表找到 m次本原多項(xiàng)式P(x)，用它產(chǎn)生一個 GF(2m)擴(kuò)域 2。 信息論與編碼 BCH碼和 RS碼 2。 若 m＝ 8即 256進(jìn)制，可以將整個 8比特字節(jié)變?yōu)?RS碼的一個碼元。第三是 q進(jìn)制 RS碼得二進(jìn)衍生碼具有良好的抗突發(fā)差錯能力。對于其二進(jìn)制衍生碼，若以二進(jìn)制信號在信道上傳送，突發(fā)差錯長度比特時最多影響到兩個八進(jìn)制符號時，可糾正；若突發(fā)差錯長度等于 5時，可能只影響兩個八進(jìn)制符號，也可能跨三各八進(jìn)制符號，就不一定能糾正了。 若原碼的校驗(yàn)矩陣為 H， 則擴(kuò)展碼 的校驗(yàn)矩陣為 ^C?????????????1. . .1100^??HH［ 2m1， 2m1m， 3］ 漢明碼的擴(kuò)張碼是 ［ 2m， 2m1m， 4］ 碼 ， 它的 中的 H是漢明碼的校驗(yàn) 矩陣 。 一般來講，每縮短一位，碼字?jǐn)?shù)目減少一半。 knx ?信息論與編碼 碼的擴(kuò)展和縮短 CRC： 縮短循環(huán)碼的最大應(yīng)用在于幀校驗(yàn)，這就是在數(shù)據(jù)通信中大家所熟悉的循環(huán)冗余校驗(yàn)碼 (CRC： Cyclic Redundancy Check)。 信息論與編碼 碼的擴(kuò)展和縮短 例 5－ 4－ 6 用于 HDLC， ， ISDN和 7號信令的 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)碼是一個（ 65535， 65519）循環(huán)碼 將該碼所有前 i位為零的碼字去除前 i位后集合在一起就構(gòu)成（ n－ i， k－ i）縮短循環(huán)碼，表現(xiàn)為 k－i信息位加上 16位 CRC組成長度（ n－ i）的一個幀。 4m in ?d信息論與編碼 碼的擴(kuò)展和縮短 將該碼所有前 i位為零的碼字去除前 i位后集合在一起就構(gòu)成（ n－ i， k－ i）縮短循環(huán)碼，表現(xiàn)為 k－ i信息位加上 16位 CRC組成長度（ n－ i）的一個幀。 信息論與編碼 碼的擴(kuò)展和縮短 接收端校驗(yàn)時，只要將整個幀除以 g（ x）檢查余式是否為零即可。如為零，說明傳輸無誤；如余式非零，說明該幀有差錯，須反饋重發(fā)和丟棄。除法器的結(jié)構(gòu)與圖 5－4－ 4（ b）所示相同，只是接收序列由最左端而不是從 處輸入而已。 實(shí)施 CRC編碼時，信息在輸出的同時由位置輸入移存器，相當(dāng)于信息移 16位后即 )(16 xmx再除以 g（ x）。 151216 ??? xxx1?nx1?nx信息論與編碼 碼的擴(kuò)展和縮短 g（ x）本身也是碼字，而且是最輕的碼字，所以本碼的 能糾一個錯誤（ t＝ 1）或檢 3個差錯。如把一幀視為一個碼字，則其校驗(yàn)位長度 n－ k不變而信息位 k和碼長 n是可變的，正符合 (n－ i， k－ i)縮短循環(huán)碼的特點(diǎn)。 信息論與編碼 碼的擴(kuò)展和縮短 ? 這樣，縮短循環(huán)碼的編、譯碼可以借用循環(huán)碼的方法，將消息多項(xiàng)式 m(x)乘以 后 除以 g(x) 即可，所不同的是這里的消息多項(xiàng)式 m(x)由 (ki)項(xiàng)組成而不是 k項(xiàng)組成。 該碼集是原循環(huán)碼碼集的一個子集，子集里所有碼多項(xiàng)式的階數(shù)均小于 ni且能夠被生成多項(xiàng)式 g(x)整除。常用的方法有： 增信，刪余，增余，刪信，及組合 信息論與編碼 碼的擴(kuò)展和縮短 ?擴(kuò)展碼 設(shè) C是一個最小距離為 d的二進(jìn)制［ n,k,d］線性分組碼， 它的碼字有奇數(shù)重量也有偶數(shù)重量。 信息論與編碼 BCH碼和 RS碼 ?例，一個 8進(jìn)制（ 7， 3） RS碼的 a冪次，多項(xiàng)式及三比特組這三種形式的符號集如表 67，寫出相應(yīng)的 RS碼的生成多項(xiàng)式。碼重多項(xiàng)式第 i次項(xiàng)的系數(shù)（重量為 i的碼字個數(shù)）是 ? RS碼之所以重要，原因之一是該碼的距離特性好，是（ MDC）碼。對于給定的 t，求連續(xù)冪次所對應(yīng)的最小多項(xiàng)式的最小公倍式 如 t=1, 連續(xù)冪次為 a,a2,生成多項(xiàng)式為 g(x)=LCM(m1(x),m2(x))=x3+x+1 生成一個 (7,3)BCH碼，即漢明碼 t=2, g(x)=x6+x5+x4+x3+x2+x+1 生成一個 (7,1)BCH碼。計(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ì)一個 n=7的二元本原 BCH碼，求出不同糾錯能力下的生成多項(xiàng)式。 又因其構(gòu)碼方法帶來的譯碼特點(diǎn)，使之可以用伯利坎普（ Berlekamp）迭代譯碼等通用，高效的譯碼算法，以致 BCH碼從 70年代起已成為線性分組碼的主流。 12 ?? mnmtkn ??12m in ?? td12 ?m信息論與編碼 BCH碼和 RS碼 ? BCH碼的基本特點(diǎn)是其生成多項(xiàng)式 g(x)包含 2t個連續(xù)冪次的根。同樣，兼有循環(huán)特征的高萊碼叫作循環(huán)高萊碼，比如用生成多項(xiàng)式 g(x)=x11+x9+x7+x6+x5+x+1 產(chǎn)生的線性（ 23，12）高萊碼就是循環(huán)高萊碼。 信息論與編碼 循環(huán)碼 圖 5 10 乘 (x3+x+1)除 (x2+1)電路 信息論與編碼 循環(huán)碼 電路運(yùn)算過程表 ?循環(huán)碼將生成矩陣簡化為生成多項(xiàng)式，從而將與編碼矩陣對應(yīng)的硬件陣列（平面型）簡化為帶反饋的移存器（直線型）。 如果 H(x)與 G(x)