【正文】 許用碼字 C1 0001 （ 0001 011) C4 0100 （ 0100 111) C2 0010 （ 0010 110） C9 1001 （ 1001 110） C5 0101 （ 0101 100） C3 0011 （ 0011 101） C11 1011 （ 1011 000） C7 0111 （ 0111 010） C6 0110 （ 0110 001） C14 1110 （ 1110 100） C12 1100 （ 1100 010） C13 1101 （ 1101 001） C8 1000 （ 1000 101） C10 1010 （ 1010 011） 第三循環(huán)組 第四循環(huán)組 C0 0000 （ 0000 000） C15 1111 （ 1111 111） 直接寫不出系統(tǒng)碼生成矩陣 ， 但 可以經(jīng)過線性變換， 將G1最下行加到第二行上，將最下面兩行加到第一行上，也能得到 [Ik Q]的形式 的系統(tǒng)碼生成矩陣 G: 非系統(tǒng)碼 生成矩陣 系統(tǒng)碼 生成矩陣 線性變換 得到了系統(tǒng)碼生成矩陣，就可以用 C = K?G得到所有碼字。 實際上，為了構(gòu)造 G=[Ik Q] 形式的生成矩陣 。 然而發(fā)現(xiàn)碼字 不具備信息位在前，監(jiān)督位在后的形式。 比如： (0100)?G1=(0101100)。 循環(huán)碼的編碼 C1經(jīng)過循環(huán)移位只能得到 7個碼字： 序號 信息位 許用碼字 C1 0001 (0001 011) C2 0010 （ 0010 110） C5 0101 （ 0101 100） C11 1011 （ 1011 000） C6 0110 （ 0110 001） C12 1100 （ 1100 010） C8 1000 （ 1000 101） （ 7,4）共有 16個許用碼字，還缺 9個。 例如 (7, 4)循環(huán)碼共有 16個許用碼字。m13(x)m15(x)m21(x)m23(x)m27(x)m31(x)； 2)本原多項式是 m1(x), m5(x), m11(x), m13(x), m23(x)和 m31(x)； (1)循環(huán)碼的生成矩陣 求出了生成多項式 g(x)，等于得到了一個碼字，通過循環(huán)移位不難得到其它碼字。 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； 對偶式還是自己。如果 n為素數(shù)，所有的因式都是本原多項式。 （ 6） xn1分解為以上因式之積，諸因式中冪次最高為 r。如 m=5階時， n=31，可分解 x311為 ： 第 i=1類因式查表得到 (45)8=(100101)2，表示 m1(x)=x5+x2+1；第 i=3類因式查表得到 (75)8=(111101)2， m3(x)=x5+x4+x3+x2+1；第 i=5類因式查表得到 (67)8=(110111)2， m5(x)=x5+x4+x2+x+1； （ 5）表中并未列出 xn1所有的因式， 與已列出因式對偶的因式 都被省略了 。 （ 2）不論 n取何值， xn1總有一個 m0(x)=x+1的因式。但只要滿足 n=2r1， xn1就具有 r次的既約因式。 例如： (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； 二者任選其一，一旦選定，就不再考慮另一個了。g (x) （ 3）生成多項式 g(x)的 確定： 由性質(zhì) 2知， g(x)是 xn1的一個因式 。[xk – h(x)]； 即： xk xk 2． 生成多項式 g(x)是 xn1的一個因式 。g(x)； 即： T(x) = h (x) G = (12……k) (2)生成多項式的兩個性質(zhì)： 1． 任意碼多項式 T(x)都是生成多項式 g(x)的倍式 。 生成多項式的冪次為 r。 生成多項式的常數(shù)項為 1。 有了它， 其它碼字都可由 xi 如： 1100010 → 11000100 → 100010 1 (x6 +x5 +x) → x(x6 +x5 +x) mod (x71) = (x7 +x6 +x2) mod (x71) = x6 +x2 +1 （ 7, 4） 循環(huán)碼及其碼多項式的循環(huán)移位： 循環(huán)次數(shù) 循環(huán)碼 碼多項式 模 x71運算后 0 0001011 x3 +x +1 x3 +x +1 1 0010110 x (x3 +x +1) x4 +x2 +x 2 0101100 x2 (x3 +x +1) x5 +x3 +x2 3 1011000 x3 (x3 +x +1) x6 +x4 +x3 4 0110001 x4 (x3 +x +1) x5+x4 +1 5 1100010 x5 (x3 +x +1) x6 +x5 +x 6 1000101 x6 (x3 +x +1) x6 +x2 +1 循環(huán)碼的生成多項式 (1) 生成多項式的定義和特點 循環(huán)碼的碼多項式中冪次最低的非零多項式叫做生成多項式，記做 g(x)。x0 = x6 + x4 + x2 + x +1 碼長為 n時 ， 可寫 ： C (x) = 1 xn1 + 2 xn2 +…… + c1 x1 + c0 x0 如三位二元碼的 8個碼字對應(yī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é)表達 對二進數(shù)，左移一位相當于乘以 2，而將最高位的進位(2n位 )上的數(shù)碼拿回到 20位，叫做循環(huán)移位， 相當于作模 2n 1運算。x2 +1x4 +0x6 +0使我們可以借助數(shù)學(xué)工具來設(shè)計編碼。從中選出 k個來構(gòu)造生成矩陣 G，就能生成全部 2k個許用碼字。 循環(huán)碼是線性分組碼中的一個子集。 C2=(0100111)。 C6=(1101001)。 C3=(0111010)。 不難發(fā)現(xiàn)它們具 有循環(huán)移位特性： C0=(0000000)。 C6=(1101001)。 C4=(1001110)。 C2=(0100111)。 循環(huán)碼 上節(jié)討論過 (7,3) 線性分組碼 : C0=(0000000)。 ?r2引言： 構(gòu)造線性分組碼關(guān)鍵是設(shè)計出一個好的生成矩陣，使所有碼字之間的漢明距離盡量大。HT）所對應(yīng)的 E。HT計算出各種錯誤格式 E所對應(yīng)的伴隨子向量 S，得到 E~S對照表。HT = E最后根據(jù) C = R⊕ E進行將其糾正。 糾正 1位錯： 當 S ≠ 0時，由 S=R 這里 H叫一致監(jiān)督矩陣，是 r行 n列的。 生成矩陣的設(shè)計，應(yīng)使許用碼字之間的最小漢明距離盡量地大。第三章 信道編碼 循環(huán)碼 本節(jié)的主要內(nèi)容 ? 碼多項式 ? 循環(huán)移位的數(shù)學(xué)表達 ? 循環(huán)碼的生成多項式 ? 循環(huán)碼的編碼 ? 循環(huán)碼的譯碼 ? 編 、 譯碼的電路實現(xiàn) 循環(huán)碼： cyclic code 碼多項式： code polynomial 生成多項式： generator polynomial 求模運算： modular arithmetic 系統(tǒng)碼： systematic（ regular） code 循環(huán)移位運算： cycle shift operation 外語關(guān)鍵詞 上節(jié)回顧：線性分組碼 基本概念 ： 表達方式： (n,k)碼， k是信息位數(shù)， r是監(jiān)督位數(shù)，n=k+r是碼長。 編碼： 已知信息 K（ k位二進序列），求相應(yīng)碼字的方法是 C=KG， G叫生成矩陣，是 k行 n列的， 一般 G具有 [Ik Q]的形式， Ik 是 k行 k列單位方陣， Q是 k行 r列的矩陣。 譯瑪： 當收到碼字 R時，首先計算伴隨子向量： S=RHT；若 S=0，則 R=C為正確碼字；若 S ≠ 0，則 R≠C為錯誤碼字。一般 H具有 [P Ir] 的形式， Ir 是 r行 r列單位方陣， P是 r行 k列的矩陣， P與Q互為轉(zhuǎn)置關(guān)系 。HT 求出 S ，比較 S 與HT ， HT的那一行與 S相同，相應(yīng)的錯誤格式向量 E的那一位就等于 1，于是 R的那一位就是錯誤的。 糾正多位錯錯： 當 S ≠ 0時，根據(jù) S=RHT ，可以預(yù)先由 S=E查表就能找到接收碼字 R（即 S=R 糾錯能力不等式： 2r ≥ Cno+Cn1+Cn2+……+ Cnt 這是因為伴隨子 S是 1行 r列的向量，它有 2r 種不同的狀態(tài)，除了用全零態(tài)表示正確碼之外，最多只能區(qū)別開 2r–1種不同的錯誤格式。怎樣找這樣的矩陣呢？循環(huán)碼的出現(xiàn)提供了一整套理論和方法，使人們能夠借助數(shù)學(xué)工具來尋找更好的線性分組碼，并由此引發(fā)出一大類很常用檢、糾錯編譯碼。 C1=(0011101)。 C3=(0111010)。 C5=(1010011)。 C7=(1110100)。 C1=(0011101)。 C7=(1110100)。 C5=(1010011)。 C4=(1001110)。 對于循環(huán)碼，有了一個的碼字，按循環(huán)移位規(guī)律就能寫出 n個碼字。 循環(huán)碼與近代數(shù)學(xué)有密切聯(lián)系。 碼多項式 二進制自然碼可表達為以 2為底的多項式表達，如： C = (1010111)= =1 26 +0 25 +1 24 +0 23 +1 22 +1 21 +1 20 ； 把底換為 x， 則得到 “ 碼多項式 ” ： C (x) = 1