【正文】 x5 +1x3 +1x1 +1 如： 101→1010→011 實際是 5 2 mod 7 = 3 碼多項式的 循環(huán)移位，實際是乘 x后作模 xn 1運算 。 如 (7,4)碼的 x3 +x +1。g(x) 的模 xn1得到。 否則，通過循環(huán)移位還能繼續(xù)降低冪次，它就不是冪次最低的多項式了。 因為 冪次最低的碼多項式是 信息為 00……01 ,后面跟上 r個監(jiān)督位的那個碼字所對應(yīng)的碼多項式，它的最高位是 xr，是 r次的 多項式 。 證明：（ n, k）循環(huán)碼作為線性分組碼，其生成矩陣 G是 k行 n列的，可由 k個不同的碼字構(gòu)成： 任給一個信息碼 K = (12…… k)，利用生成矩陣和公式 C = K?G，不難求出它對應(yīng)的碼字 T(x) = K = （ 1xk1 + 2xk2 +……+ k） g (x)； 表明任意碼多項式 T(x)都應(yīng)能被 g(x)整除 。 證明：因為 g(x)循環(huán)左移 k位 ,即 g(x)乘以 xk后再作模 xn1運算 ,應(yīng)當(dāng)仍為一個碼多項式。g (x)為 n次多項式，除以 xn1的商式必為 1， 設(shè)余式為 T(x),于是有： 移項即證得： xn1= g(x)g (x) = xn1 + T(x) = xn1 + h(x) 可 根據(jù)設(shè)定的碼長 n和監(jiān)督位 r， 將 xn1因式分解，從中選擇一個 r次的因子作為 g(x)。 插件 1： 查表分解 xn1的方法 （ 1）并非所有的 xn1都具有 r次的既約 (不能再分解 )的因式。因此 P194 頁表 4中只列出滿足 n=2m1的 xn1的分解情況。 （ 3） xn1其它因式是 mi(x), i=1,3,5,7…… （ 4） mi(x)的表達由 8進制數(shù)給出 ，將它換成二進制自然碼就是 mi(x)各位的系數(shù)。所謂對偶指的是將二進制自然碼高低位倒置的表達，如： 與 (100101)2對稱的是 (101001)2，表示 m15(x)=x5+x3+1； 與 (111101)2對稱的是 (101111)2，表示 m7(x)=x5+x3+x2+x+1； 與 (110111)2對稱的是 (111011)2，表示 m11(x)=x5+x4+x3+x+1； 值得注意的是，有的二進制自然碼本身就是對稱的，如：(11111)2與 (10001)2，高低位倒置后不變 , 不會出現(xiàn)新的因式。 （ 7） 類序號 i與 n互素的那些因式 mi(x)被稱為本原多項式；類序號 i與 n可約的那些因式 mi(x)被稱為非本原多項式。 [例 ]查表分解 x631 因為 261=63，所以應(yīng)查 P194 頁表 4中 m=6階 。 i=9： (015)8=(1101)2，得知 m9(x)=x3+x2+1； 由對偶式 (1011)2和 187頁表知 m27(x)=x3+x+1； i=11： (155)8=(1101101)2，得知 m11(x)=x6+x5+x3+x2+1； 由對偶式 (1011011)2和 187頁表知 m13(x)=x6+x4+x3+x+1； i=21： (007)8=(111)2，得知 m21(x)=x2+x+1； 其對偶式仍是自己； 最終結(jié)果： 1） x631=m0(x)m1(x)m3(x)m5(x)m7(x)m9(x)m11(x) 果然如此簡單嗎？ 實際上，通過循環(huán)移位最多可寫出 n個碼字，得不到全部碼字，因為 (n,k)碼應(yīng)當(dāng)共有 2k個許用碼字。 取 g(x)= x3+x+1 ，等于知道了中信息 K=(0001)所對應(yīng)的那個碼字： C1=(0001 011)。 從循環(huán)組中隨便取 4個許用碼字，比如前 4個，用它們構(gòu)成的生成矩陣為 G1： 再利用 C = K?G1 就能求得全部許用碼字。 (1000)?G1=(1011000)。原因是 G1不 具備 G=[Ik Q]的形式，這樣編碼叫 非系統(tǒng)碼，非系統(tǒng)碼在譯碼時是比較困難的。 需要如下的 4個碼字： 1 0 0 0 ??? 0 1 0 0 ??? 0 0 1 0 ??? 0 0 0 1 ??? 才能排列出 4 4的單位矩陣 Ik。 （ 2）直接計算系統(tǒng)碼的監(jiān)督元 : 以 (7, 4)碼為例，設(shè)信息位為 k3 k2 k1 k0，對應(yīng)的多項式為： k(x)=k3x3 +k2x2 +k1x +k0； 設(shè)監(jiān)督位為 r2 r1 r0， 監(jiān)督位對應(yīng)的多項式為 : r(x) = r2x2 +r1x +r0 ； 系統(tǒng)碼 碼字 C = (k3 k2 k1 k0 r2 r1 r0)對應(yīng)的碼多項式為 : C(x) = k3x6 +k2x5 +k1 x4 +k0 x3 + r2 x2 + r1 x +r0 ； = x3 (k3x3 +k2x2 +k1x +k0 ) +(r2x2 +r1x +r0 ) = x3 k(x)+ r(x) 推廣到一般 ， 碼多項式可寫為為： C(x) = x r k (x) mod g(x) ] + [ r (x) mod g(x) ] = 0； 移項 ， 并考慮到模 2運算可把負號變正號 ， 于是： r (x) mod g(x) = x r k (x) mod g(x) (2) 再由公式 (1)就得到了相應(yīng)的碼字。 k (x) = x5, g(x) = x3+x+1； 由 (2): r (x) = x5 mod x3+x+1 = x2 +x +1； 由 (1): C(x) = xr 小結(jié)：循環(huán)碼的編碼步驟： 確定 (n,k)循環(huán)碼的生成多項式：將 xn1分解因 式 ， 從中選擇一個 r次的因子作為 g(x)。 k (x) mod g(x) 計算出它的監(jiān)督位。 [例 2] 求 (7, 3)循環(huán)碼的生成多項式，并為信息 K = (110) 編碼。 k (x) = x4(x2+x)= x6+x5 知 : r (x) = x6+x5 mod x4+x3+x2+1 = x3 +1； (3) ∵ R=(1001)； ∴ C = (1101001)； 或由： g(x) = x4+x3+x2+1 → (0011101) 循環(huán)左移三次得到： C = (1101001)； 循環(huán)碼的譯碼（糾錯） (1) 由接收碼字 R， 寫出其接收碼多項式 R(x)； (2) 求伴隨子多項式 S(x) = R(x) mod g(x)； (3) 若 S(x) = 0（ 即接收碼多項式能被 g(x)整除 ） , 則表明接收碼無誤 。 因 S(x) = [C(x)+E(x)] mod g(x) = E(x) mod g(x)； 為了找到 S(x) 對應(yīng)的 E(x)， 我們可以預(yù)先將糾錯能力 t 位 以內(nèi)的各種錯誤格式 E(x)除以 g(x) 的余式都計算出來，列成一張 S (x)E (x) 對照表，由 S (x) 就能直接查出 E (x)。 [例 3] 已知 (7,4)碼的生成多項式是 g(x) = x3+x+1；請為 R = (0110010)譯碼 。 筆算時是從被除數(shù)的高位開始，依次對除數(shù)求商、求積、求余，然后右移一位，繼續(xù)前述過程，直至到被除數(shù)末尾 。 由于是二進制代碼，商只有 1和 0兩個可能值，積就是除數(shù)本身或是零。最后 留在寄存器中的就是余數(shù) ,上輪余數(shù)的首位被輸出，它的就是商。 k (x) = x5=0100000，除數(shù)是 g(x) = x3+x+1=1011， 相除的過程見表所示。 余數(shù)初值為零，覆蓋值是被除數(shù)減去商與除數(shù)之積。 寄存器最高位 (x2位 )為 0時，移位后除以 g(x)的商必然為 0；寄存器最高位為 1時商必然為 1；因此該位的 輸出的就是商。 模 2加等價于模 2減， 就實現(xiàn)了與寄存器中原先余數(shù)的相減運算。 2. 編碼電路 ： 把輸入的 K(x)從 D0端移到 D2后面，就得到了如圖所 示的實用編碼電路。 然后 P置向下 ， Q開啟 ， 繼續(xù)將寄存器中的余數(shù)輸出；就是接在后面的監(jiān)督 。 k (x)，這樣 就省去了前置的乘以 x3的乘法 (移位 )器。 (3) 無須移位 7次，只要移位 4次，就可以完成求模 運算的工作，接著把 P置下， Q開啟，就可以把 D0D1D2中的余數(shù)，順序接在編碼的后半段上， 形成完整的編碼。 R0R1R2R3R4R5R6 ⊕ K1 ⊕ D0 ⊕ D1 D2 K2 然后，斷開 K1，接通 K2。若 e6位錯，則求余結(jié)果 S = 101，恰使與門有輸出，正好糾正 R6位。 若 e5位錯，則求余得出的 S = (111)，與門無輸出，但經(jīng)過一個節(jié)拍后 D0D1D2變成 (101)，與門變得有輸出，正好輪到緩存器中 R5位的輸出，將它糾正；再繼續(xù)移位，與門又關(guān)閉了。巧就巧在正好輪到 R有錯的那一位輸出時 ， 寄存器恰變?yōu)?101， 與門便輸出糾錯信號 “ 1”， 將該位錯碼糾正 。 當(dāng) R(x)為正確碼時， E(x)是全 0， 除法器求余結(jié)果為 0，與門不會打開， R(x)從緩沖器中原樣輸出。 E(x)為 1的碼位進入運算器的同時也進入 緩沖器，經(jīng)過 7步才能緩沖才能輸出，這時正好與門打開，將其糾正。 k (x) mod g(x) 求出監(jiān)督位，添在信息位后，即得到編碼。 （ 4） 若 S(x) ≠ 0， 表明接收碼有誤 ， 此時應(yīng) 將糾錯能力 t 位以內(nèi)的各種錯誤格式 E(x)除以 g(x) 的余式都計算出來 ， 列成一張 S(x)E(x) 對照表 。 （ 6） 由 C(x) = R(x) + E (x)進行糾錯。 作業(yè)： P114頁： 1 17題 第三章 信道編碼 循環(huán)碼的擴展 本節(jié)的主要內(nèi)容 ?增余漢明碼 ?截短循環(huán)碼 ?循環(huán)冗余校驗碼 ?二元本原 BCH碼 ?二元非本原 BCH碼 增余漢明碼： extended Hamming code 截短循環(huán)碼： shortened cyclic code 循環(huán)冗余校驗碼： Cyclic Redundancy Check Code (CRC) 本原 BCH碼 ： primitive BCH code 非本原 BCH碼 : nonprimitive BCH code 外語關(guān)鍵詞 上節(jié)回顧：循環(huán)碼 基本概念 ： 循環(huán)碼的特點，碼多項式，循環(huán)移位的數(shù)學(xué)表達。 （ 2）通過對 g(x)的循環(huán)移位可獲得其它一些碼多項式。 （ 4） g(x)是 xn1的一個因式。 k (x) mod g(x)； （ 3）寫出相應(yīng)碼字： C(x) = x r 如果給它的每一個許用碼字增加一位奇偶校驗位，使其成為 (n+1, k) 碼，其編碼效率降低不多，但監(jiān)督能力卻得到提高，不僅能糾正 1位錯，還能發(fā)現(xiàn)第 2位錯。 當(dāng)只有一位錯時，