【正文】 出現(xiàn)新的因式。因此 P194 頁表 4中只列出滿足 n=2m1的 xn1的分解情況。可 根據(jù)設(shè)定的碼長 n和監(jiān)督位 r， 將 xn1因式分解，從中選擇一個 r次的因子作為 g(x)。g (x)為 n次多項(xiàng)式，除以 xn1的商式必為 1， 設(shè)余式為 T(x),于是有： 移項(xiàng)即證得： xn1= g(x)g (x)； 表明任意碼多項(xiàng)式 T(x)都應(yīng)能被 g(x)整除 。 證明：（ n, k）循環(huán)碼作為線性分組碼，其生成矩陣 G是 k行 n列的，可由 k個不同的碼字構(gòu)成： 任給一個信息碼 K = (12…… k)，利用生成矩陣和公式 C = K?G，不難求出它對應(yīng)的碼字 T(x) = K 否則，通過循環(huán)移位還能繼續(xù)降低冪次，它就不是冪次最低的多項(xiàng)式了。 如 (7,4)碼的 x3 +x +1。x1 +1x5 +1 循環(huán)碼與近代數(shù)學(xué)有密切聯(lián)系。 C4=(1001110)。 C7=(1110100)。 C7=(1110100)。 C3=(0111010)。怎樣找這樣的矩陣呢？循環(huán)碼的出現(xiàn)提供了一整套理論和方法，使人們能夠借助數(shù)學(xué)工具來尋找更好的線性分組碼，并由此引發(fā)出一大類很常用檢、糾錯編譯碼。查表就能找到接收碼字 R（即 S=R 糾正多位錯錯： 當(dāng) S ≠ 0時，根據(jù) S=R一般 H具有 [P Ir] 的形式， Ir 是 r行 r列單位方陣， P是 r行 k列的矩陣， P與Q互為轉(zhuǎn)置關(guān)系 。 編碼： 已知信息 K（ k位二進(jìn)序列），求相應(yīng)碼字的方法是 C=KG， G叫生成矩陣，是 k行 n列的， 一般 G具有 [Ik Q]的形式， Ik 是 k行 k列單位方陣， Q是 k行 r列的矩陣。 生成矩陣的設(shè)計，應(yīng)使許用碼字之間的最小漢明距離盡量地大。 糾正 1位錯： 當(dāng) S ≠ 0時，由 S=RHT = EHT）所對應(yīng)的 E。 循環(huán)碼 上節(jié)討論過 (7,3) 線性分組碼 : C0=(0000000)。 C4=(1001110)。 不難發(fā)現(xiàn)它們具 有循環(huán)移位特性： C0=(0000000)。 C6=(1101001)。 循環(huán)碼是線性分組碼中的一個子集。使我們可以借助數(shù)學(xué)工具來設(shè)計編碼。x4 +0x0 = x6 + x4 + x2 + x +1 碼長為 n時 ， 可寫 ： C (x) = 1 xn1 + 2 xn2 +…… + c1 x1 + c0 x0 如三位二元碼的 8個碼字對應(yīng)的碼多項(xiàng)式為： 000， 001， 010， 011， 100， 101， 110， 111； 0， 1， x , x+1, x2, x2 +1, x2 + x , x2 + x +1 循環(huán)移位的數(shù)學(xué)表達(dá) 對二進(jìn)數(shù)，左移一位相當(dāng)于乘以 2，而將最高位的進(jìn)位(2n位 )上的數(shù)碼拿回到 20位，叫做循環(huán)移位， 相當(dāng)于作模 2n 1運(yùn)算。 有了它， 其它碼字都可由 xi 生成多項(xiàng)式的冪次為 r。G = (12……k) 2． 生成多項(xiàng)式 g(x)是 xn1的一個因式 。[xk – h(x)]； 即： xk 例如： (7, 4) 碼 ， n = 7， k = 4， r = 3； 分解： x71 = (x1) (x3+x+1) (x3+x2+1) g(x) 應(yīng)是 x71 的一個 r = 3次的因子 ， 可取為： g(x) = x3+x+1 或 g(x) = x3+x2+1； 二者任選其一，一旦選定，就不再考慮另一個了。 （ 2）不論 n取何值， xn1總有一個 m0(x)=x+1的因式。 （ 6） xn1分解為以上因式之積，諸因式中冪次最高為 r。 i=1： (103)8=(1000011)2，得知 m1(x)=x6+x+1； 由對偶式 (1100001)2和 187頁表得知 m31(x)=x6+x5+1； i=3： (127)8=(1010111)2，得知 m3(x)=x6+x4+x2+x+1； 由對偶式 (1110101)2和 187頁表知 m15(x)=x6+x5+x4+x2+1； i=5： (147)8=(1100111)2，得知 m5(x)=x6+x5+x2+x+1； 由對偶式 (1110011)2和 187頁表知 m23(x)=x6+x5+x4+x+1； i=7： (111)8=(1001001)2，得知 m7(x)=x6+x3+1； 對偶式還是自己。 例如 (7, 4)循環(huán)碼共有 16個許用碼字。 比如： (0100)?G1=(0101100)。 實(shí)際上，為了構(gòu)造 G=[Ik Q] 形式的生成矩陣 。 k (x) + r (x) (1) 根據(jù)生成多項(xiàng)式 性質(zhì) 1， 任何碼多項(xiàng)式一定能被 g(x)整除 ： C (x) mod g(x) =0 即： [ x r [例 1]求 (7, 4)循環(huán)碼中信息位 K = (0100) 對應(yīng)的碼字： 解： k(x) = x2, r = 3, xr 根據(jù)信息 K， 由 r (x) = x r 解： ( 1) n=7, k=3, r=4 由： x71 = (x+1) (x3+x+1) (x3+x2+1) ?。? g(x) = (x+1) (x3+x+1) = x4+x3+x2+1； (2)由 : k(x) = x2+x, xr (6) 糾錯譯碼： 由 C(x) = R(x) + E (x)就能寫出譯碼 C。 現(xiàn)在的道理相同，只不過把除數(shù)固定在電路上（就是反饋的位置）， 讓被除數(shù)逐位右移通動寄存器，通過反饋電路實(shí)現(xiàn)求商、求積、求余的運(yùn)算。 編、譯碼的電路實(shí)現(xiàn) 1. 除法求余電路 ： 設(shè)被除數(shù)是 x r因此將被除數(shù)諸位推入寄存器中，寄存器兼有減法計算功能，每次移位后都只計算 3位長的一段。 如果商為 1， 1?g(x)的最高位在與原先余數(shù)相減的運(yùn)算中總是相抵消的，所以只須考慮其余 3位的反饋即可。 電路工作原理 ： (1)在 D2端加入 K(x)，就等于在 D0端加 x r 譯碼電路 ： 首先斷開 K2，接通 K1，利用除法求余電路，把接收碼字 R(x) 除以 g(x) 的余式，即伴隨子 S (x)計算出來，存于 D0D1D2中；與此同時， R(x) 也被緩存在 R0~R6中。此后，移位繼續(xù)進(jìn)行， D0D1D2值發(fā)生變化，與門關(guān)閉，不再影響 R5… R0的輸出。 如此巧妙的玄機(jī)在哪里呢 ? 因?yàn)榘殡S子 S(x) = R(x) mod g(x)= E(x) mod g(x)，所以分析電路對 R(x)的作用與分析 E(x)是等價的。 譯碼電路逐次移位的數(shù)據(jù)變化 錯誤格式 伴隨式 寄存器 繼續(xù)移位 又移位后 糾正位 e(x) S(x) D0D1D2 次數(shù) N D0D1D2 R e6=1 x2 +1 1 0 1 0 1 0 1 R6 e5=1 x2+x+1 1 1 1 1 1 0 1 R5 e4=1 x2 +x 0 1 1 2 1 0 1 R4 e3=1 x +1 1 1 0 3 1 0 1 R3 e2=1 x2 0 0 1 4 1 0 1 R2 e1=1 x 0 1 0 5 1 0 1 R1 e0=1 1 1 0 0 6 1 0 1 R0 本節(jié)要點(diǎn) ： (1) 碼字的循環(huán)移位 (2) 碼多項(xiàng)式及其兩個重要性質(zhì) (3) 循環(huán)碼的生成多項(xiàng)式 ： 根據(jù)信息 K，直接由 r (x) = x r （ 5）由 S (x) 直接查表得到 E (x)。 生成多項(xiàng)式： （ 1）碼多項(xiàng)式中冪次最低（冪次為 r ）常數(shù)項(xiàng)為 1的非 零多項(xiàng)式。 循環(huán)碼的編碼： （ 1）分解 xn1，以獲得生成多項(xiàng)式 g(x)； （ 2）求監(jiān)督多項(xiàng)式： r (x) = x r 如 (7, 4)碼改為 (8, 4)碼，第 8列的碼元滿足偶校驗(yàn)關(guān)系： c7= c6+c5+c4+c3+c2+c1+c0； 一致監(jiān)督矩陣由 H(7,3)變?yōu)?H(8,4) ： 校驗(yàn)矩陣增加全 1的一行，當(dāng)計算 S=RHT時，該列的計算是 s4= c7+c6+c5+c4+c3+c2+c1+c0,對于偶校驗(yàn)，如果是正確碼字結(jié)果必然為 0。 截短循環(huán)碼 求生成多項(xiàng)式，需要分解 xn1，但只有 n=2m1的數(shù)才能查表分解，這就限制了 n的取值。 相對于原來的循環(huán)碼， 信息位與碼長被同步地減小了 。 截短循環(huán)碼具有循環(huán)碼的許多結(jié)構(gòu)特點(diǎn) ， 監(jiān)督位沒有變 ， 糾錯能力不變 ， 糾錯方法不變等 。 數(shù)據(jù)的長短往往不確定 ， 但校驗(yàn)位的長度 r卻是固定的 。(x16+x2+x+1) 循環(huán)冗余校驗(yàn)碼不僅實(shí)現(xiàn)起來比較簡單，而且具有很強(qiáng)的檢測能力。 （ 4）所有奇數(shù)個錯位。e j 不妨以 n=15, x151=0的 15個根為例。 GF(2)域中的分解： 因式分解與定義域是密切關(guān)聯(lián)的。 我們把它 叫做 i=5類對應(yīng)的最小多項(xiàng)式，記作： m5(x)= x2 + x+1； 同理，屬于每個共厄類的各 1次因式相乘，都可得到 GF(2) 域中一個 相應(yīng) 的 最小多項(xiàng)式 ，其冪次等于 共厄類中根的個數(shù)： m1(x)=(x α)(x –α2 )(x –α4)(x –α8 )= x4 + x+1； m3(x)=(x –α3)(x –α6 )(x –α9)(x –α12 )= x4 +x3 +x2 + x+1； m5(x)=(x α5)(x α10 )=x2 + x+1； m7(x)=(x –α7)(x –α11 )(x –α13)(x –α14 )= x4 +x3 +1； m0(x)= (x –α0) = x+1 于是： x151=m0(x)m1(x)m3(x)m5(x)m7(x)= =(x+1)(x4 + x+1)(x4 +x3 +x2 + x+1)(x2 + x+1)(x4 +x3 +1) ： (1)本原根與非本原根： xn=1的 n個根 α0 =1 ,α,α2, ……,α n1 可分為 本原根與非 本原根兩種，二者 的 區(qū)別是看 能否由 αk 的一切冪次生成 xn=1 的全部根。我們 把通過自乘能回到 α0 =1 的最小自乘次數(shù) m叫做該類元素的循環(huán)級。 本原類的類序號 i與 n互素，非本原類的類序號 i與 n可約。