【正文】 以內(nèi)的各種錯誤格式 E(x) 的 S (x) 對照表； （ 2） 求接收碼的伴隨子向量 S*(x) = R(x) mod g(x)； （ 3）從對照表中查出 S*(x) 對應(yīng)的 E*(x) （ 4） C (x) = R (x) + E*(x) 增余漢明碼 漢明碼是能糾正一位錯的完備碼，具有較高的編碼效率。 循環(huán)碼的編碼： （ 1）分解 xn1，以獲得生成多項式 g(x)； （ 2）求監(jiān)督多項式： r (x) = x r （ 3）任意碼多項式 T(x)都應(yīng)能被 g(x)整除。 生成多項式： （ 1）碼多項式中冪次最低（冪次為 r ）常數(shù)項為 1的非 零多項式。 思考： 是否任意碼長 n和任意信息位 k都能構(gòu)成 (n,k)循環(huán)碼？（提示：考慮生成多項式）。 （ 5）由 S (x) 直接查表得到 E (x)。 ： （ 1） 由接收碼字 R， 寫出其接收碼多項式 R(x)； （ 2） 求伴隨子多項式 S(x) = R(x) mod g(x)； （ 3） 若 S(x) = 0（ 即接收碼多項式能被 g(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é)要點 ： (1) 碼字的循環(huán)移位 (2) 碼多項式及其兩個重要性質(zhì) (3) 循環(huán)碼的生成多項式 ： 根據(jù)信息 K，直接由 r (x) = x r 當(dāng) R(x)有一位不正確時， E(x)的相應(yīng)位是 1，其它全 0；除法器求余邏輯是按照 x3+x+1設(shè)計的 ,初值為 000,當(dāng)有 1輸入時才變?yōu)?100,此后由于輸入全為 0,寄存器則按照100→010 →001→110→011→111→101 的規(guī)律變化 ,共 7步變到 101。 如此巧妙的玄機(jī)在哪里呢 ? 因為伴隨子 S(x) = R(x) mod g(x)= E(x) mod g(x)，所以分析電路對 R(x)的作用與分析 E(x)是等價的。 其它位有錯時 ， 同樣引起類似于上述變化的糾錯過程 。此后，移位繼續(xù)進(jìn)行， D0D1D2值發(fā)生變化，與門關(guān)閉，不再影響 R5… R0的輸出。 與門設(shè)計是對輸入（ 101）有響應(yīng)。 譯碼電路 ： 首先斷開 K2，接通 K1，利用除法求余電路，把接收碼字 R(x) 除以 g(x) 的余式，即伴隨子 S (x)計算出來，存于 D0D1D2中；與此同時， R(x) 也被緩存在 R0~R6中。 (2) 將 Q閉合， P置向上，就可以在進(jìn)行除法運算的 同時，將信息 K送到輸出，形成編碼的前半段。 電路工作原理 ： (1)在 D2端加入 K(x)，就等于在 D0端加 x r P D0 ⊕ D1 D2 ⊕ 輸出 Q 輸入 K K(x) 輸入 D0D1D2 輸出 x3位 0 0 0 0 0 x2位 1 1 1 0 1 x1位 0 0 1 1 0 x0位 0 1 1 1 0 1 1 1 首先開關(guān) P置向上 ， 開關(guān) Q閉合 ， 得到上面四行的數(shù)據(jù)；輸出的就是信息 K。 如果商為 1， 1?g(x)的最高位在與原先余數(shù)相減的運算中總是相抵消的，所以只須考慮其余 3位的反饋即可。 該商被反饋回去，反饋位置是 g(x) 的非 0位，就相當(dāng)于用商去乘除數(shù)，其乘積不是 0就是 g(x)。因此將被除數(shù)諸位推入寄存器中，寄存器兼有減法計算功能，每次移位后都只計算 3位長的一段。 xr K(x) ⊕ D0 ⊕ D1 D2 輸入 輸出 xr K(x) 輸入 D0D1D2 輸出 x6位 0 0 0 0 0 x5位 1 1 0 0 0 x4位 0 0 1 0 0 x3位 0 0 0 1 0 x2位 0 1 1 0 1 x1位 0 0 1 1 0 x0位 0 1 1 1 1 電路原理 : 現(xiàn)在的除數(shù) g(x)是 3次多項式，余數(shù)至多 2次，故可取 3位寄存器來存放余數(shù)。 編、譯碼的電路實現(xiàn) 1. 除法求余電路 ： 設(shè)被除數(shù)是 x r商為 0時反饋為 0，被除數(shù)不變；商為 1時反饋為 1，被除數(shù)與除數(shù)相減，但模二減等于模二加。 現(xiàn)在的道理相同，只不過把除數(shù)固定在電路上（就是反饋的位置）， 讓被除數(shù)逐位右移通動寄存器，通過反饋電路實現(xiàn)求商、求積、求余的運算。 解： 設(shè)接收碼為 R = (r6 r5 r4 r3 r2 r1 r0 )；由 S(x) = E(x) mod g(x)； 可列出 S(x)—E(x) 對照表： 當(dāng) R = (0110010)時 ， R(x) = x5+x4+x； S (x)=（ x5+x4+x） mod（ x3+x+1） = x+1； 查表知： E(x) = x3； 糾錯： C (x) = R (x) + E(x) = x5+x4+x3 +x ； 即： C = (0111010)； 譯碼結(jié)果是 K=0111 誤碼位置 r0 r1 r2 r3 r4 r5 r6 E(x) 1 x x2 x3 x4 x5 x6 S(x) 1 x x2 x+1 x2+x x2+x+1 x2+1 計算機(jī)中對公式的計算其實仍歸結(jié)為數(shù)值計算，對所有的賦值都能正確得到結(jié)果，就等于對公式的計算。 (6) 糾錯譯碼： 由 C(x) = R(x) + E (x)就能寫出譯碼 C。 (4) 若 S(x) ≠ 0， 表明接收碼有誤 ， 此時定義 錯誤格式多項式： E(x) = en1xn1+en2xn2+‥‥ +e2x2+ e1x+ e0； (5) 由 S(x) 求 對應(yīng)的 E(x)。 解： ( 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 由 信息位 + 監(jiān)督位 直接寫出編碼 C； 間接編碼方法： 由 g(x)得到一個碼字，循環(huán)移位得到 k個碼字，寫出生成矩陣，通過線性變換得到系統(tǒng)碼生成矩陣 G，最后由生成方程 C = K?G 求出相應(yīng)碼字。 根據(jù)信息 K， 由 r (x) = x r k (x) + r(x) = x5 + x2 + x +1； ∴ C = (0100111)； 同法可得到所有 16個信息 (0000~1111) 的碼字。 [例 1]求 (7, 4)循環(huán)碼中信息位 K = (0100) 對應(yīng)的碼字： 解： k(x) = x2, r = 3, xr k (x) mod g(x)； 因為 r (x) 是 r1次多項式 ， g(x) 是 r 次多項式 ， 所以 r (x) mod g(x)= r (x) 得到直接 計算系統(tǒng)碼碼字監(jiān)督多項式的公式是 ： r (x) = x r k (x) + r (x) (1) 根據(jù)生成多項式 性質(zhì) 1， 任何碼多項式一定能被 g(x)整除 ： C (x) mod g(x) =0 即： [ x r 通過對 C1=(0001 011)的循環(huán)移位可以得到 （ 0010 110）和（ 1000 101)， 但是卻無法得到 (0100 ???) 0 1 1 1 1 0 1 0 1 原因何在？ 原來 0100所對應(yīng)的碼字 （ 0100 111)位于另一循環(huán)組中 : 第一循環(huán)組 第二循環(huán)組 序號 信息 許用碼字 序號 信息