【正文】 ()(1 xhxgx n ??)1m o d (0)1)(()()()()()( ????? nn xxxmxhxgxmxhxC信息論與編碼 循環(huán)碼 循環(huán)碼是線性分組碼的一種。對(duì)于線性分組碼，可以用生成矩陣來(lái)描述。具體到循環(huán)碼，則簡(jiǎn)化為生成多項(xiàng)式。因此也一定可以用生成矩陣來(lái)描述循環(huán)碼。 所謂生成矩陣，就是碼空間的一組基底。而生成多項(xiàng)式及其移位后的一組多項(xiàng)式，就可以作為一組基底，因此，如果循環(huán)碼的生成多項(xiàng)式為 1)( 111 ????? ????? xgxgxxg knknkn ?信息論與編碼 循環(huán)碼 則生成矩陣為 這種形式的生成矩陣不是系統(tǒng)形式的。如果要生成系統(tǒng)形式的生成矩陣，則第 l行應(yīng)是多項(xiàng)式 ??????????????????????????????????????1000000100101100010010001)()()()(12112121121121???????????????????ggggggggggggGxgxxgxgxxgxknknknknkk信息論與編碼 循環(huán)碼 這里， 是 除以 g(x)的余式，因?yàn)? 所以 由于 g(x)是碼字，所以 也是碼字，因此 也一定是碼字，可以作為基底。 klxRx lln ,2,1),( ????)(xRl lnx ?)()()( xRxgxQx llln ???)()()( xgxQxRx llln ???)()( xgxQ l)( xRx lln ??信息論與編碼 循環(huán)碼 實(shí)際上，可以由生成多項(xiàng)式直接得到系統(tǒng)碼。因?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)式。這個(gè)多項(xiàng)式應(yīng)該是用 g(x)除 ，得到的余式 r(x)（商為 Q(x)），即 也就是說(shuō)，得到的碼多項(xiàng)式為 由于 g(x)是碼多項(xiàng)式，因此 Q(x)g(x)也是碼字，這樣由信息多項(xiàng)式得到的碼字一定是系統(tǒng)碼。 )( xmx kn?)()()()( xrxgxQxmx kn ???)()()()( xgxQxrxmx kn ???信息論與編碼 循環(huán)碼 歸納起來(lái)，我們可以得到由信息組得到對(duì)應(yīng)系統(tǒng)碼字的方法是： （ 1）由信息組得到信息多項(xiàng)式，將信息多項(xiàng)式 乘以 ； （ 2）用 g(x)除 ，得到余式 r(x)； （ 3）將 r(x)加在 后面，得到碼多項(xiàng)式，從而得到其對(duì)應(yīng)的碼字（碼多項(xiàng)式的系數(shù)）。 )(xmknx ?)( xmx kn ?)( xmx kn ?信息論與編碼 循環(huán)碼 例題： （ 7， 4）循環(huán)碼的生成多項(xiàng)式為 求（ 1）該循環(huán)碼系統(tǒng)形式的生成矩陣； （ 2）對(duì)于給定的信息組（ 1001），求其對(duì)應(yīng)的系統(tǒng)形式的碼字。 1)( 3 ??? xxxg信息論與編碼 循環(huán)碼 解 ： （ 1）生成矩陣 將生成多項(xiàng)式及其對(duì)應(yīng)的循環(huán)移位多項(xiàng)式作為基底，得到一般形式的生成矩陣為 ???????????1101000011010000110100001101G信息論與編碼 循環(huán)碼 ? 系統(tǒng)形式的生成矩陣：一種辦法是將一般形式的生成矩陣通過(guò)行變換和列置換，得到系統(tǒng)形式； 通過(guò)矩陣運(yùn)算 :將矩陣第 3,4行加到第 1行 : 將矩陣第 4行加到第 2行 ?????????????1101000011010011100101010001G信息論與編碼 循環(huán)碼 另一種方法： 第一行，前四列為 1000，對(duì)應(yīng)的多項(xiàng)式為 ，除以生成多項(xiàng)式 ，得余式為 ，所以對(duì)應(yīng)的后三列為 101； 同樣的辦法，可以得到第二行為 0100111；第三行為 0010110；第四行為 0001011； 因此，得到系統(tǒng)形式的生成矩陣。 6x1)( 3 ??? xxxg1)( 2 ?? xxr信息論與編碼 循環(huán)碼 （ 2）對(duì)應(yīng)信息組（ 1001）的碼字，可以由生成矩陣得到，也可以直接得到，即用信息組多項(xiàng)式 乘以 得到 ，除以碼多項(xiàng)式 ，得余式為 ，因此，碼多項(xiàng)式為 對(duì)應(yīng)的碼字為： 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)碼編碼電路實(shí)現(xiàn)的硬件結(jié)構(gòu)圖 用除法器實(shí)現(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)的項(xiàng)對(duì)應(yīng)，左到右分別對(duì)應(yīng) 1， x, x2 和 x3 。正常做除法時(shí)， m(x)應(yīng)從除法器最左端 (對(duì)應(yīng) g(x)常數(shù)項(xiàng) 1)進(jìn)入。如 m(x)右移一位，則應(yīng)從 g(x)一次項(xiàng) x的位置進(jìn)入，相當(dāng)于作 xm(x)運(yùn)算再去做除法。 信息論與編碼 循環(huán)碼 ? m(x)從 xnk =x3 的位置進(jìn)入，相當(dāng)于作 xnk m(x)運(yùn)算再去除以 g(x)。每編一個(gè)碼需化 n=7拍時(shí)間。前 4拍時(shí)開(kāi)關(guān) k1 ， k2 在位置 1，消息位先 m3 再 m2,m1,m0 依次輸入除法器做 xnk m(x) / g(x)運(yùn)算，同時(shí)依次該 4個(gè)碼元輸出。 信息論與編碼 循環(huán)碼 到第 4拍完成時(shí)，除法器移存里的數(shù)據(jù)就是余式系數(shù)。 后 3拍消息停止輸入 (空 3拍 )， k1 ， k2 倒向位置 2，移存器斷開(kāi)反饋后不再起除法器而僅起一般移存器作用，其中的數(shù)據(jù)分 3拍依次移出，作為第 5到第 7循環(huán)碼校驗(yàn)位的輸出 。 信息論與編碼 循環(huán)碼 信息論與編碼 循環(huán)碼 乘法電路 已知兩多項(xiàng)式相乘為 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 可用下圖所示的電路完成上述運(yùn)算過(guò)程 。 該電路由 r個(gè)存貯單元組成的 r 級(jí)移位寄存器 ， 至多 r個(gè)模 q相加器和至多 (r+1)個(gè)模 q常乘器所組成 。 信息論與編碼 循環(huán)碼 乘 B(x)運(yùn)算電路 信息論與編碼 循環(huán)碼 ?工作開(kāi)始時(shí)， r級(jí)移位存貯器中的存數(shù)全清洗為 0， 且規(guī)定被乘多