【正文】 B(x)除 A(x)的電路。 如果 H(x)與 G(x)次數(shù)不等， 則只要按 G(x)與 H(x)中最高次數(shù)設(shè)計移存器級數(shù) 即可。同樣，兼有循環(huán)特征的高萊碼叫作循環(huán)高萊碼，比如用生成多項式 g(x)=x11+x9+x7+x6+x5+x+1 產(chǎn)生的線性（ 23，12）高萊碼就是循環(huán)高萊碼。 又因其構(gòu)碼方法帶來的譯碼特點，使之可以用伯利坎普（ Berlekamp）迭代譯碼等通用，高效的譯碼算法，以致 BCH碼從 70年代起已成為線性分組碼的主流。對于給定的 t，求連續(xù)冪次所對應(yīng)的最小多項式的最小公倍式 如 t=1, 連續(xù)冪次為 a,a2,生成多項式為 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碼。 信息論與編碼 BCH碼和 RS碼 ?例，一個 8進制（ 7， 3） RS碼的 a冪次，多項式及三比特組這三種形式的符號集如表 67，寫出相應(yīng)的 RS碼的生成多項式。 該碼集是原循環(huán)碼碼集的一個子集，子集里所有碼多項式的階數(shù)均小于 ni且能夠被生成多項式 g(x)整除。如把一幀視為一個碼字，則其校驗位長度 n－ k不變而信息位 k和碼長 n是可變的，正符合 (n－ i， k－ i)縮短循環(huán)碼的特點。 實施 CRC編碼時，信息在輸出的同時由位置輸入移存器，相當于信息移 16位后即 )(16 xmx再除以 g（ x）。如為零，說明傳輸無誤；如余式非零，說明該幀有差錯，須反饋重發(fā)和丟棄。 4m in ?d信息論與編碼 碼的擴展和縮短 將該碼所有前 i位為零的碼字去除前 i位后集合在一起就構(gòu)成（ n－ i， k－ i）縮短循環(huán)碼，表現(xiàn)為 k－ i信息位加上 16位 CRC組成長度（ n－ i）的一個幀。 knx ?信息論與編碼 碼的擴展和縮短 CRC： 縮短循環(huán)碼的最大應(yīng)用在于幀校驗，這就是在數(shù)據(jù)通信中大家所熟悉的循環(huán)冗余校驗碼 (CRC： Cyclic Redundancy Check)。 若原碼的校驗矩陣為 H， 則擴展碼 的校驗矩陣為 ^C?????????????1. . .1100^??HH［ 2m1， 2m1m， 3］ 漢明碼的擴張碼是 ［ 2m， 2m1m， 4］ 碼 ， 它的 中的 H是漢明碼的校驗 矩陣 。第三是 q進制 RS碼得二進衍生碼具有良好的抗突發(fā)差錯能力。 信息論與編碼 BCH碼和 RS碼 2。 1?nx)1(|)(|)(|)( ?ni xxCxgxm信息論與編碼 BCH碼和 RS碼 ?由近世代數(shù)可進一步得知，在二元擴域GF(2m)上可把 xn+1分解為如下 n個根的乘積 式中， a是 GF(2m)上本原元， n＝（ 2m－ 1）。 信息論與編碼 循環(huán)碼 信息論與編碼 循環(huán)碼 一個碼可以兼有很多的特點，循環(huán)特征僅是其中之一。 信息論與編碼 循環(huán)碼 B(x) 除 x4+x3+1 的運算過程表 信息論與編碼 循環(huán)碼 多項式相乘相除電路 GF(q)上的多項式 A(x)、 H(x)、 G(x)分別為： A(x)=akxk+ak1xk1+… +a1x+a0 H(x)=hrxr+h r1 x r1+… +h1x+h0 G(x)=grxr+g r1 x r1+… +g1x+g0 若 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)碼 該運算可用圖 所示的電路實現(xiàn)， 它由 r級移存器、 至多有 2(r+1)個 GF(q)的常乘器和r+1個 GF(q)的相加器組成。 akb1r同時反饋到后面各級寄存器中 (所以稱這種除法電路為線性反饋移存器 )減去 akb1rB(x)， 所以 ， 此時移存器中自左至右的內(nèi)容為 (akrb0b1rak),(akr+1b1b1rak)， … ， (ak1br1 b1rak)， 這相應(yīng)于豎式運算中的第 A項所示的結(jié)果 。 由上面乘法過程可以看出 ,這種乘法電路完成一次乘法運算 ,共需移位 k+ r+1次 。 后 3拍消息停止輸入 (空 3拍 )， k1 ， k2 倒向位置 2，移存器斷開反饋后不再起除法器而僅起一般移存器作用，其中的數(shù)據(jù)分 3拍依次移出，作為第 5到第 7循環(huán)碼校驗位的輸出 。 1)( 3 ??? xxxg信息論與編碼 循環(huán)碼 解 ： （ 1）生成矩陣 將生成多項式及其對應(yīng)的循環(huán)移位多項式作為基底，得到一般形式的生成矩陣為 ???????????1101000011010000110100001101G信息論與編碼 循環(huán)碼 ? 系統(tǒng)形式的生成矩陣：一種辦法是將一般形式的生成矩陣通過行變換和列置換，得到系統(tǒng)形式； 通過矩陣運算 :將矩陣第 3,4行加到第 1行 : 將矩陣第 4行加到第 2行 ?????????????1101000011010011100101010001G信息論與編碼 循環(huán)碼 另一種方法： 第一行，前四列為 1000，對應(yīng)的多項式為 ，除以生成多項式 ，得余式為 ，所以對應(yīng)的后三列為 101； 同樣的辦法，可以得到第二行為 0100111；第三行為 0010110；第四行為 0001011； 因此，得到系統(tǒng)形式的生成矩陣。 所謂生成矩陣，就是碼空間的一組基底。 例如 則循環(huán)編碼后的碼多項式為 對應(yīng)的碼字為（ 0101110）。 信息論與編碼 循環(huán)碼 （ 2） GF(2)上的（ n， k）循環(huán)碼中，存在著唯一的一個次數(shù)最低（ nk次）的首一（即第一項的系數(shù)為 1）碼多項式 g(x)： 使得所有的碼多項式都是 g(x)的倍式，即 且所有小于 n次的 g(x)的倍式都是碼多項式。 )1m o d ()1m o d ()1m o d ()()()()()()()()(1n210121021201???????????nnnnnn xxxxCxxxCxCxCxxxCxCxxCxC???位：移位：移位：移? 因為一個碼字經(jīng)過 n次循環(huán)移位后又變回自身，所以一個碼字經(jīng)循環(huán)移位最多產(chǎn)生 n個碼字。信息論與編碼 循環(huán)碼 上次課小結(jié)： ? 線性分組碼的一些概念：域、矢量空間、線性 分組碼； ? 生成矩陣和校驗矩陣 ? 伴隨式與譯碼：伴隨式的定義、標準陣列譯碼 表。 ],[ 021 cccC nn ????012211)( cxcxcxcxC nnnn ????? ???? ?}1,0{?ic信息論與編碼 循環(huán)碼 當 C所對應(yīng)的碼字循環(huán)移位 1位后，得到對應(yīng)的多項式為 所以，可以用多項式乘以 x來表示一次循環(huán)移位，因此有： 0122110 )( cxcxcxcxC nnnn ????? ???? ?1023121 )( ????? ????? nnnnn cxcxcxcxC ?)()( 01 xxCxC ? )1m o d ( ?nx021 , ccc nn ???循環(huán)移 1位 1032 , ??? nnn cccc ?信息論與編碼 循環(huán)碼 以此類推。生成多項式不是唯一的，但總有一個是最低的。 17 ?x)1( ?x