【正文】 環(huán)碼的生成多項式為 求（ 1）該循環(huán)碼系統(tǒng)形式的生成矩陣； （ 2）對于給定的信息組（ 1001），求其對應的系統(tǒng)形式的碼字。 klxRx lln ,2,1),( ????)(xRl lnx ?)()()( xRxgxQx llln ???)()()( xgxQxRx llln ???)()( xgxQ l)( xRx lln ??信息論與編碼 循環(huán)碼 實際上，可以由生成多項式直接得到系統(tǒng)碼。因此也一定可以用生成矩陣來描述循環(huán)碼。 因此，由 g(x)生成的（ n， k）碼和由 h(x)生成的（ n， k）碼互為對偶碼。 17 ?x)1( ?x)1( 23 ?? xx )1( 3 ?? xx)1)(1( 23 ??? xxx )1)(1( 3 ??? xxx)1)(1( 233 ???? xxxx信息論與編碼 循環(huán)碼 設(shè)選取 為生成多項式，則 nk=3， k=4，所以信息多項式為 信息碼組共有 16種不同的組合，因此，共有 16個碼字。 反之，如果 g(x)是 的（ nk）次因子，則 g(x)一定是（ n， k）循環(huán)碼的生成多項式。生成多項式不是唯一的，但總有一個是最低的。 k2信息論與編碼 循環(huán)碼 信息論與編碼 循環(huán)碼 因此，設(shè) 對應一個碼字，則其線性組合： 其中， A(x)是任意多項式， 是一個碼多項式。 ],[ 021 cccC nn ????012211)( cxcxcxcxC nnnn ????? ???? ?}1,0{?ic信息論與編碼 循環(huán)碼 當 C所對應的碼字循環(huán)移位 1位后，得到對應的多項式為 所以，可以用多項式乘以 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)碼 以此類推。 ? 由于構(gòu)成碼集 C的 k維 n重矢量空間的基底也一定是碼字，因此， k個基底可以是同一個基底經(jīng)循環(huán)移位得到。信息論與編碼 循環(huán)碼 上次課小結(jié)： ? 線性分組碼的一些概念：域、矢量空間、線性 分組碼； ? 生成矩陣和校驗矩陣 ? 伴隨式與譯碼：伴隨式的定義、標準陣列譯碼 表。所以，只用一個基底就可以表示一個碼的特征，也就不需要用矩陣來描述。 )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)碼 （ 2） GF(2)上的（ n， k）循環(huán)碼中，存在著唯一的一個次數(shù)最低（ nk次）的首一（即第一項的系數(shù)為 1）碼多項式 g(x)： 使得所有的碼多項式都是 g(x)的倍式，即 且所有小于 n次的 g(x)的倍式都是碼多項式。 1?nx 1|)( ?nxxg)()(1 xhxgx n ??1?nx信息論與編碼 循環(huán)碼 ? （ n， k）循環(huán)碼的構(gòu)造方法為： （ 1）對 做因式分解，找出其（ nk）次因子； （ 2）以該（ nk）次因子為生成多項式 g(x)，與信息多項式 m(x)相乘，得到的多項式C(x)=m(x)g(x)即為碼多項式。 例如 則循環(huán)編碼后的碼多項式為 對應的碼字為（ 0101110）。 1?nx )()(1 xhxgx n ??)1m o d (0)1)(()()()()()( ????? nn xxxmxhxgxmxhxC信息論與編碼 循環(huán)碼 循環(huán)碼是線性分組碼的一種。 所謂生成矩陣，就是碼空間的一組基底。因為系統(tǒng)碼中，信息位占據(jù)了碼字的前 k個位置，而信息多項式為 如果用 乘以 m(x)，得到 如果在其后加上 nk比特的校驗位，就構(gòu)成了碼字 . 012211)( mxmxmxmxm kkkk ????? ???? ?knx ?knknnknkkn xmxmxmxmxmx ???????? ????? 0112211)( ?信息論與編碼 循環(huán)碼 也就是說，要在上面的多項式后面加上次數(shù)底 于 nk的多項式。 1)( 3 ??? xxxg信息論與編碼 循環(huán)碼 解 ： （ 1）生成矩陣 將生成多項式及其對應的循環(huán)移位多項式作為基底，得到一般形式的生成矩陣為 ???????????1101000011010000110100001101G信息論與編碼 循環(huán)碼 ? 系統(tǒng)形式的生成矩陣：一種辦法是將一般形式的生成矩陣通過行變換和列置換，得到系統(tǒng)形式； 通過矩陣運算 :將矩陣第 3,4行加到第 1行 : 將矩陣第 4行加到第 2行 ?????????????1101000011010011100101010001G信息論與編碼 循環(huán)碼 另一種方法： 第一行，前四列為 1000，對應的多項式為 ，除以生成多項式 ，得余式為 ，所以對應的后三列為 101； 同樣的辦法，可以得到第二行為 0100111；第三行為 0010110；第四行為 0001011； 因此，得到系統(tǒng)形式的生成矩陣。 信息論與編碼 循環(huán)碼 ? m(x)從 xnk =x3 的位置進入，相當于作 xnk m(x)運算再去除以 g(x)。 后 3拍消息停止輸入 (空 3拍 )， k1 ， k2 倒向位置 2，移存器斷開反饋后不再起除法器而僅起一般移存器作用，其中的數(shù)據(jù)分 3拍依次移出，作為第 5到第 7循環(huán)碼校驗位的輸出 。 信息論與編碼 循環(huán)碼 (2) A(x)的第二個系數(shù) ak1送入電路時 ,ak由第一級輸出送入第二級 ,同時與 b r1相乘和 ak1 br相加后送到輸出端 ,這就是 C(x)的 x k+r1項系數(shù)akb r1+ak1 br。 由上面乘法過程可以看出 ,這種乘法電路完成一次乘法運算 ,共需移位 k+ r+1次 。 信息論與編碼 循環(huán)碼 (1) 開始運算時 r級移存器中的存數(shù)全部清為0。 akb1r同時反饋到后面各級寄存器中 (所以稱這種除法電路為線性反饋移存器 )減去 akb1rB(x)， 所以 ， 此時移存器中自左至右的內(nèi)容為 (akrb0b1rak),(akr+1b1b1rak)， … ， (ak1br1 b1rak)， 這相應于豎式運算中的第 A項所示的結(jié)果 。 因為在 GF(2)中， 1 的逆元仍為 1， 相加和相減相同， 所以 b1r與 bi常乘器均為一條閉合線。 信息論與編碼 循環(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