【文章內(nèi)容簡介】 項式 A(x)的高次項系數(shù) ak首先送入電路， 電路的工作過程如下： (1) 當(dāng) A(x)的最高次系數(shù) ak首先送入時 ， 乘積C(x)的最高次項 xk+r的系數(shù) akbr就出現(xiàn)在輸出端 ， 同時 ak存入移存器的第一級 (最左一級 )。 信息論與編碼 循環(huán)碼 (2) A(x)的第二個系數(shù) ak1送入電路時 ,ak由第一級輸出送入第二級 ,同時與 b r1相乘和 ak1 br相加后送到輸出端 ,這就是 C(x)的 x k+r1項系數(shù)akb r1+ak1 br。 此時， 移存器內(nèi)的存貯數(shù)據(jù)為 ak1， ak， 0， 0， … ， 0(自左至右 )。 信息論與編碼 循環(huán)碼 (3) 上述過程重復(fù)進(jìn)行， 直至 k次移位后， A(x)的系數(shù)全部送入移存器。 k+r+1次移位后， 移存器輸出 C(x)的常數(shù)項 a0+b0， 移存器中的內(nèi)容全部恢復(fù)到全為 0 初態(tài)， 乘法 完成。 由上面乘法過程可以看出 ,這種乘法電路完成一次乘法運算 ,共需移位 k+ r+1次 。 信息論與編碼 循環(huán)碼 圖 5 4 另一種乘 B(x)電路 多項式除法電路 GF(q)上的兩多項式 A(x)=akxk+ak1xk1+… +a1x+a0 B(x)=brxr+br1x r1+…+ b1x+b0 由歐幾里德除法可知： A(x)=q(x)B(x)+r(x) 0≤r(x)＜ B(x) 或 r(x)=0 假設(shè) k≥r， 否則 q(x)=0， r(x)=A(x)。 多項式A(x)被 B(x)除的電路如下圖所示 ， 它由 r級移存器 、 至多 r個 GF(q)加法器和至多 r+1個常乘器組成 。 k≥r 信息論與編碼 循環(huán)碼 除 B(x)=brxr+…+ b1x+b0電路 信息論與編碼 循環(huán)碼 為了理解除法電路的工作過程， 下面我們列出 B(x)除 A(x)的豎式運算式子： brxr+b r1 x r1+… +b1x+b0 (除式 ) b1rakxkr+b1r(ak1b1rbr1ak)xkr1+… (商式 ) akxk+ak1xk1+… +a1x+a0 (被除式 ) (akxk+b1rbr1akxk1+… +b0b1rakxkr) (ak1b1rbr1ak)xk1+… +(akrb0b1rak)xkr+… (A) ((ak1b1rbr1ak)xk1+… ) … … (余式 ) 由上面式子 ， 我們討論除法電路的工作過程 。 信息論與編碼 循環(huán)碼 (1) 開始運算時 r級移存器中的存數(shù)全部清為0。 第一個移位節(jié)拍后， 被除多項式 A(x)的最高次項 xk的系數(shù) ak首先進(jìn)入電路的最左一級。 r次移位后 ak進(jìn)入到移存器的最右一級中， 此時自左至右移存器中的內(nèi)容為 akr+1， akr+2， … ， ak1， ak。 信息論與編碼 循環(huán)碼 (2) 第 r+1次移位后 ， ak輸出與 b1r 相乘得到ak b1r ， 這就是商式 q(x)的第一項 xkr的系數(shù) 。 akb1r同時反饋到后面各級寄存器中 (所以稱這種除法電路為線性反饋移存器 )減去 akb1rB(x)， 所以 ， 此時移存器中自左至右的內(nèi)容為 (akrb0b1rak),(akr+1b1b1rak)， … ， (ak1br1 b1rak)， 這相應(yīng)于豎式運算中的第 A項所示的結(jié)果 。 信息論與編碼 循環(huán)碼 ? (3) 依次類推， 經(jīng) k+1 次移位后， 完成了整個除法運算過程。 它的輸出為商式 q(x)， 而移存器中的內(nèi)容就是余式 r(x)的系數(shù) 信息論與編碼 循環(huán)碼 ?例 設(shè)除式 B(x)=x3+x+1， 被除式A(x)=x4+x3+1都是 GF(2)上的多項式， 求 B(x)除 A(x)的電路。 除 B(x)的除法電路如下圖 所示， 它由 3 級移存器和 2 個模 2 相加器組成。 因為在 GF(2)中， 1 的逆元仍為 1， 相加和相減相同， 所以 b1r與 bi常乘器均為一條閉合線。 信息論與編碼 循環(huán)碼 圖 5 7 除 B(x)=x3+x+1電路 信息論與編碼 循環(huán)碼 ?完成上述兩個多項式相除的長除法運算式如下： x+1 (商式 ) x3+x+1 x4+x3 +1 (被除式 ) (除式 ) x4 +x2+x x3+x2+x+1 x3 +x+1 x2 (余式 ) 信息論與編碼 循環(huán)碼 這里 x4+x3+1=(x+1)(x3+x+1)+x2 商為 x+1， 余式為 x2。 下表 5 4 中列出了電路的工作過程 。 顯然 ， r+1=4 次移位后得到商的第一個系數(shù) ， k+1=5 次移位后 ， 就完成了整個除法運算 ， 并在 D0、 D D2組成的移存器中保留了余式 001， 即 x2。 信息論與編碼 循環(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)的相加器組成。 顯然， 該電路就是乘法電路與除法電路的兩種電路的結(jié)合。 如果 H(x)與 G(x)次數(shù)不等， 則只要按 G(x)與 H(x)中最高次數(shù)設(shè)計移存器級數(shù) 即可。 信息論與編碼 循環(huán)碼 圖 5 8 乘 H(x)除 G(x)電路 信息論與編碼 循環(huán)碼 例 設(shè) GF(2)上的 3 個多項式為： A(x)=x4+x+1， H(x)=x2+1， G(x)=x3+x+1 則 A(x)H(x)=(x4+x+1)(x2+1)=x6+x4+x3+x2+x+1 =x3(x3+x+1)+(x2+x+1) =q(x)G(x)+r(x) 可用下圖的電路實現(xiàn)， 該電路的工作過程如下表所示， 移位 A(x)+1=5 次后， 即得到了商式 x3 和余式 x2+x+1。 信息論與編碼 循環(huán)碼 圖 5 9 乘 (x2+1)除 (x3+x+1)電路 信息論與編碼 循環(huán)碼 若 GF(2)上的多項式 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) 該運算可用下圖所示的電路實現(xiàn) ， 它的工