【正文】 ()(1 xhxgx n ??)1m o d (0)1)(()()()()()( ????? nn xxxmxhxgxmxhxC信息論與編碼 循環(huán)碼 循環(huán)碼是線性分組碼的一種。對于線性分組碼，可以用生成矩陣來描述。具體到循環(huán)碼，則簡化為生成多項式。因此也一定可以用生成矩陣來描述循環(huán)碼。 所謂生成矩陣，就是碼空間的一組基底。而生成多項式及其移位后的一組多項式，就可以作為一組基底，因此，如果循環(huán)碼的生成多項式為 1)( 111 ????? ????? xgxgxxg knknkn ?信息論與編碼 循環(huán)碼 則生成矩陣為 這種形式的生成矩陣不是系統(tǒng)形式的。如果要生成系統(tǒng)形式的生成矩陣，則第 l行應是多項式 ??????????????????????????????????????1000000100101100010010001)()()()(12112121121121???????????????????ggggggggggggGxgxxgxgxxgxknknknknkk信息論與編碼 循環(huán)碼 這里， 是 除以 g(x)的余式，因為 所以 由于 g(x)是碼字，所以 也是碼字，因此 也一定是碼字，可以作為基底。 klxRx lln ,2,1),( ????)(xRl lnx ?)()()( xRxgxQx llln ???)()()( xgxQxRx llln ???)()( xgxQ l)( xRx lln ??信息論與編碼 循環(huán)碼 實際上，可以由生成多項式直接得到系統(tǒng)碼。因為系統(tǒng)碼中，信息位占據(jù)了碼字的前 k個位置，而信息多項式為 如果用 乘以 m(x)，得到 如果在其后加上 nk比特的校驗位，就構(gòu)成了碼字 . 012211)( mxmxmxmxm kkkk ????? ???? ?knx ?knknnknkkn xmxmxmxmxmx ???????? ????? 0112211)( ?信息論與編碼 循環(huán)碼 也就是說，要在上面的多項式后面加上次數(shù)底 于 nk的多項式。這個多項式應該是用 g(x)除 ，得到的余式 r(x)（商為 Q(x)），即 也就是說，得到的碼多項式為 由于 g(x)是碼多項式，因此 Q(x)g(x)也是碼字，這樣由信息多項式得到的碼字一定是系統(tǒng)碼。 )( xmx kn?)()()()( xrxgxQxmx kn ???)()()()( xgxQxrxmx kn ???信息論與編碼 循環(huán)碼 歸納起來，我們可以得到由信息組得到對應系統(tǒng)碼字的方法是： （ 1）由信息組得到信息多項式，將信息多項式 乘以 ； （ 2）用 g(x)除 ，得到余式 r(x)； （ 3）將 r(x)加在 后面，得到碼多項式，從而得到其對應的碼字（碼多項式的系數(shù)）。 )(xmknx ?)( xmx kn ?)( xmx kn ?信息論與編碼 循環(huán)碼 例題： （ 7， 4）循環(huán)碼的生成多項式為 求（ 1）該循環(huán)碼系統(tǒng)形式的生成矩陣； （ 2）對于給定的信息組（ 1001），求其對應的系統(tǒng)形式的碼字。 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)形式的生成矩陣。 6x1)( 3 ??? xxxg1)( 2 ?? xxr信息論與編碼 循環(huán)碼 （ 2）對應信息組（ 1001）的碼字，可以由生成矩陣得到，也可以直接得到，即用信息組多項式 乘以 得到 ，除以碼多項式 ，得余式為 ，因此，碼多項式為 對應的碼字為： 1001110 1)( 3012233 ?????? xmxmxmxmxm3xx kn ??36)( xxxmx kn ???1)( 3 ??? xxxg xxxr ?? 2)(xxxxxrxmxxC kn ?????? ? 236)()()(信息論與編碼 循環(huán)碼 D D D 1 x X3 2 循環(huán)碼編碼電路實現(xiàn)的硬件結(jié)構(gòu)圖 用除法器實現(xiàn) (7,4)循環(huán)碼編碼器 1 1 k2 k1 (m0,m1,m2,m3) 信息論與編碼 循環(huán)碼 ?帶反饋移存器構(gòu)成除以 g(x)=x3+x+1的除法電路，反饋線的位置與 g(x)的項對應，左到右分別對應 1， x, x2 和 x3 。正常做除法時， m(x)應從除法器最左端 (對應 g(x)常數(shù)項 1)進入。如 m(x)右移一位，則應從 g(x)一次項 x的位置進入，相當于作 xm(x)運算再去做除法。 信息論與編碼 循環(huán)碼 ? m(x)從 xnk =x3 的位置進入，相當于作 xnk m(x)運算再去除以 g(x)。每編一個碼需化 n=7拍時間。前 4拍時開關 k1 ， k2 在位置 1，消息位先 m3 再 m2,m1,m0 依次輸入除法器做 xnk m(x) / g(x)運算，同時依次該 4個碼元輸出。 信息論與編碼 循環(huán)碼 到第 4拍完成時，除法器移存里的數(shù)據(jù)就是余式系數(shù)。 后 3拍消息停止輸入 (空 3拍 )， k1 ， k2 倒向位置 2，移存器斷開反饋后不再起除法器而僅起一般移存器作用，其中的數(shù)據(jù)分 3拍依次移出，作為第 5到第 7循環(huán)碼校驗位的輸出 。 信息論與編碼 循環(huán)碼 信息論與編碼 循環(huán)碼 乘法電路 已知兩多項式相乘為 C(x)=A(x)B(x) =akbrxk+r+(akb r1+ak1br)xk+r1 +(akb r2+ak1b r1+ak2br)xk+r2+… +(akb ri+ak1b r(i1)+…+akibr)xk+ri+… +(a1b0+a0b1)x+a0b0 可用下圖所示的電路完成上述運算過程 。 該電路由 r個存貯單元組成的 r 級移位寄存器 ， 至多 r個模 q相加器和至多 (r+1)個模 q常乘器所組成 。 信息論與編碼 循環(huán)碼 乘 B(x)運算電路 信息論與編碼 循環(huán)碼 ?工作開始時， r級移位存貯器中的存數(shù)全清洗為 0， 且規(guī)定被乘多