《信道編碼中》PPT課件.ppt

《《信道編碼中》PPT課件.ppt》由會員分享，可在線閱讀，更多相關《《信道編碼中》PPT課件.ppt（85頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、第三章 信道編碼 3.4 循環(huán)碼 本節(jié)的主要內(nèi)容 碼多項式 循環(huán)移位的數(shù)學表達 循環(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 外語關鍵詞 上節(jié)回顧：線性分組碼 基本概念 ： 表達方式： (n,k)碼， k是信息位數(shù)， r是監(jiān)督位數(shù)， n=k+r是碼長。 編碼： 已知信

2、息 K（ k位二進序列），求相應碼字的 方法是 C=KG， G叫生成矩陣，是 k行 n列的， 一般 G 具有 Ik Q的形式， Ik 是 k行 k列單位方陣， Q是 k行 r列 的矩陣。 生成矩陣的設計，應使許用碼字之間的最小漢明距 離盡量地大。 譯瑪： 當收到碼字 R時，首先計算伴隨子向量： S=RHT； 若 S=0，則 R=C為正確碼字；若 S 0，則 RC為錯誤碼 字。 這里 H叫一致監(jiān)督矩陣，是 r行 n列的。一般 H具有 P Ir 的形式， Ir 是 r行 r列單位方陣， P是 r行 k列的矩陣， P與 Q互為轉(zhuǎn)置關系 。 糾正 1位錯： 當 S 0時，由 S=RHT 求出 S ，比

3、較 S 與 HT ， HT的那一行與 S相同，相應的錯誤格式向量 E的那 一位就等于 1，于是 R的那一位就是錯誤的。最后根據(jù) C = R E進行將其糾正。 糾正多位錯錯： 當 S 0時，根據(jù) S=RHT = EHT ， 可以預先由 S=EHT計算出各種錯誤格式 E所對應 的伴隨子向量 S，得到 ES對照表。查表就能找 到接收碼字 R（即 S=RHT）所對應的 E。 糾錯能力不等式： 2r Cno+Cn1+Cn2+ Cnt 這是因為伴隨子 S是 1行 r列的向量，它有 2r 種不 同的狀態(tài)，除了用全零態(tài)表示正確碼之外，最多 只能區(qū)別開 2r1種不同的錯誤格式。 r2 引言： 構(gòu)造線性分組碼關鍵

4、是設計出一個好的生成 矩陣，使所有碼字之間的漢明距離盡量大。怎 樣找這樣的矩陣呢？循環(huán)碼的出現(xiàn)提供了一整 套理論和方法，使人們能夠借助數(shù)學工具來尋 找更好的線性分組碼，并由此引發(fā)出一大類很 常用檢、糾錯編譯碼。 3.4 循環(huán)碼 上節(jié)討論過 (7,3) 線性分組碼 : C0=(0000000); C1=(0011101); C2=(0100111); C3=(0111010); C4=(1001110); C5=(1010011); C6=(1101001); C7=(1110100); 不難發(fā)現(xiàn)它們具 有循環(huán)移位特性： C0=(0000000); C1=(0011101); C3=(01110

5、10); C7=(1110100); C6=(1101001); C5=(1010011); C2=(0100111); C4=(1001110); 循環(huán)碼是線性分組碼中的一個子集。 對于循環(huán)碼，有了一個的碼字，按循環(huán) 移位規(guī)律就能寫出 n個碼字。從中選出 k 個來構(gòu)造生成矩陣 G，就能生成全部 2k個 許用碼字。 循環(huán)碼與近代數(shù)學有密切聯(lián)系。使我們 可以借助數(shù)學工具來設計編碼。 3.4.1 碼多項式 二進制自然碼可表達為以 2為底的多項式表達，如： C = (1010111)= =1 26 +0 25 +1 24 +0 23 +1 22 +1 21 +1 20 ； 把底換為 x， 則得到 “

6、 碼多項式 ” ： C (x) = 1x6 +0 x5 +1x4 +0 x3 +1x2 +1x1 +1x0 = x6 + x4 + x2 + x +1 碼長為 n時 ， 可寫 ： C (x) = cn-1 xn-1 + cn-2 xn-2 + + c1 x1 + c0 x0 如三位二元碼的 8個碼字對應的碼多項式為： 000， 001， 010， 011， 100， 101， 110， 111； 0， 1， x , x+1, x2, x2 +1, x2 + x , x2 + x +1 3.4.2 循環(huán)移位的數(shù)學表達 對二進數(shù)，左移一位相當于乘以 2，而將最高位的進位 (2n位 )上的數(shù)碼拿回到

7、 20位，叫做循環(huán)移位， 相當于作 模 2n -1運算。 如： 1011010011 實際是 5 2 mod 7 = 3 碼多項式的 循環(huán)移位，實際是乘 x后作模 xn -1 運算 。 如： 1100010 11000100 100010 1 (x6 +x5 +x) x(x6 +x5 +x) mod (x7-1) = (x7 +x6 +x2) mod (x7-1) = x6 +x2 +1 （ 7, 4） 循環(huán)碼及其碼多項式的循環(huán)移位： 循環(huán)次數(shù) 循環(huán)碼 碼多項式 模 x7-1運算后 0 0001011 x3 +x +1 x3 +x +1 1 0010110 x (x3 +x +1) x4 +x

8、2 +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 3.4.3 循環(huán)碼的生成多項式 (1) 生成多項式的定義和特點 循環(huán)碼的碼多項式中冪次最低的非零多項式叫做生成多 項式，記做 g(x)。 如 (7,4)碼的 x3 +x +1。 有了它， 其它 碼字都可由 xi g(x) 的模 xn-1得到。 生成

9、多項式的常數(shù)項為 1。 否則，通過循環(huán)移位還能繼續(xù) 降低冪次，它就不是冪次最低的多項式了。 生成多項式的冪次為 r。 因為 冪次最低的碼多項式是 信息 為 0001 ,后面跟上 r個監(jiān)督位的那個碼字所對應的碼多 項式，它的最高位是 xr，是 r次的 多項式 。 (2)生成多項式的兩個性質(zhì)： 1 任意碼多項式 T(x)都是生成多項式 g(x) 的倍式 。 證明：（ n, k）循環(huán)碼作為線性分組碼，其生成 矩陣 G是 k行 n列的，可由 k個不同的碼字構(gòu)成： 任給一個信息碼 K = (cn-1cn-2 cn-k)，利用生 成矩陣和公式 C = KG，不難求出它對應的碼字 T(x) = KG = (

10、cn-1cn-2cn-k) = （ cn-1xk-1 + cn-2xk-2 + cn-k） g(x)； 即： T(x) = h (x) g (x)； 表明任意碼多項式 T(x)都應能被 g(x)整除 。 2 生成多項式 g(x)是 xn-1的一個因式 。 證明：因為 g(x)循環(huán)左移 k位 ,即 g(x)乘以 xk后再作 模 xn-1運算 ,應當仍為一個碼多項式。 xk g (x)為 n次多項式，除以 xn-1的商式必為 1， 設余式為 T(x),于是有： 移項即證得： xn-1= g(x)xk h(x)； 即： xk g (x) = xn-1 + T(x) = xn-1 + h(x) g (

11、x) （ 3）生成多項式 g(x)的 確定： 由性質(zhì) 2知， g(x)是 xn-1的一個因式 。可 根據(jù)設 定的碼長 n和監(jiān)督位 r， 將 xn-1因式分解，從中選擇 一個 r次的因子作為 g(x)。 例如： (7, 4) 碼 ， n = 7， k = 4， r = 3； 分解： x7-1 = (x-1) (x3+x+1) (x3+x2+1) g(x) 應是 x7-1 的一個 r = 3次的因子 ， 可取為： g(x) = x3+x+1 或 g(x) = x3+x2+1； 二者任選其一，一旦選定，就不再考慮另一個了。 插件 1： 查表分解 xn-1的方法 （ 1）并非所有的 xn-1都具有 r

12、次的既約 (不能再分解 )的因式。 但只要滿足 n=2r-1， xn-1就具有 r次的既約因式。因此 P194 頁表 4中只列出滿足 n=2m-1的 xn-1的分解情況。 （ 2）不論 n取何值， xn-1總有一個 m0(x)=x+1的因式。 （ 3） xn-1其它因式是 mi(x), i=1,3,5,7 （ 4） mi(x)的表達由 8進制數(shù)給出 ，將它換成二進制自然碼就 是 mi(x)各位的系數(shù)。如 m=5階時， n=31，可分解 x31-1為 ： 第 i=1類因式查表得到 (45)8=(100101)2，表示 m1(x)=x5+x2+1； 第 i=3類因式查表得到 (75)8=(1111

13、01)2， m3(x)=x5+x4+x3+x2+1； 第 i=5類因式查表得到 (67)8=(110111)2， m5(x)=x5+x4+x2+x+1； （ 5）表中并未列出 xn-1所有的因式， 與已列出因式對偶的因 式 都被省略了 。所謂對偶指的是將二進制自然碼高低位倒置 的表達，如： 與 (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； 值得注意的是，有的二

14、進制自然碼本身就是對稱的，如： (11111)2與 (10001)2，高低位倒置后不變 , 不會出現(xiàn)新的因式。 （ 6） xn-1分解為以上因式之積，諸因式中冪次最高為 r。 （ 7） 類序號 i與 n互素的那些因式 mi(x)被稱為本原多項式；類 序號 i與 n可約的那些因式 mi(x)被稱為非本原多項式。如果 n為 素數(shù)，所有的因式都是本原多項式。 例 查表分解 x63-1 因為 26-1=63，所以應查 P194 頁表 4中 m=6階 。 i=1： (103)8=(1000011)2，得知 m1(x)=x6+x+1； 由對偶式 (1100001)2和 187頁表得知 m31(x)=x6+

15、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； 對偶式還是自己。 i=9： (015)8=(1101)2，得知 m9(x)=x3+x2+1； 由對偶式 (1011)2和 187頁表知 m2

16、7(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） x63-1=m0(x)m1(x)m3(x)m5(x)m7(x)m9(x)m11(x) 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)；

17、(1)循環(huán)碼的生成矩陣 求出了生成多項式 g(x)，等于得到了一個碼字，通過 循環(huán)移位不難得到其它碼字。 果然如此簡單嗎？ 實際上，通過循環(huán)移位最多可寫出 n個碼字，得不到全 部碼字，因為 (n,k)碼應當共有 2k個許用碼字。 例如 (7, 4)循環(huán)碼共有 16個許用碼字。 取 g(x)= x3+x+1 ，等于知道了中信息 K=(0001)所對應 的那個碼字： C1=(0001 011)。 3.4.4 循環(huán)碼的編碼 C1經(jīng)過循環(huán)移位只能得到 7個碼字： 序號 信息位 許用碼字 C1 0001 (0001 011) C2 0010 （ 0010 110） C5 0101 （ 0101 100）

18、 C11 1011 （ 1011 000） C6 0110 （ 0110 001） C12 1100 （ 1100 010） C8 1000 （ 1000 101） （ 7,4）共有 16個許用碼字，還缺 9個。 從循環(huán)組中隨便取 4個許用碼字，比如前 4個，用它們 構(gòu)成的生成矩陣為 G1： 再利用 C = KG1 就能求得全部許用碼字。 比如： (0100)G1=(0101100); (1000)G1=(1011000); 然而發(fā)現(xiàn)碼字 不具備信息位在前，監(jiān)督位在后的形式。 原因是 G1不 具備 G=Ik Q的形式，這樣編碼叫 非系統(tǒng)碼， 非系統(tǒng)碼在譯碼時是比較困難的。 實際上，為了構(gòu)造 G

19、=Ik Q 形式的生成矩陣 。 需要如下的 4個碼字： 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 才能排列出 4 4的單位矩陣 Ik。 通過對 C1=(0001 011)的循環(huán)移位可以得到 （ 0010 110）和（ 1000 101)， 但是卻無法得到 (0100 ) 0 1 1 1 1 0 1 0 1 原因何在？ 原來 0100所對應的碼字 （ 0100 111)位于 另一循環(huán)組中 : 第一循環(huán)組 第二循環(huán)組 序號 信息 許用碼字 序號 信息 許用碼字 C1 0001 （ 0001 011) C4 0100 （ 0100 111) C2 0010 （ 0010 110

20、） 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)

21、過線性變換， 將 G1最下行加到第二行上，將最下面兩行加到第一行上， 也能得到 Ik Q的形式 的系統(tǒng)碼生成矩陣 G: 非系統(tǒng)碼 生成矩陣 系統(tǒng)碼 生成矩陣 線性 變換 得到了系統(tǒng)碼生成矩陣，就可以用 C = KG得到所有碼字。 （ 2）直接計算系統(tǒng)碼的監(jiān)督元 : 以 (7, 4)碼為例，設信息位為 k3 k2 k1 k0，對應的多項式 為： k(x)=k3x3 +k2x2 +k1x +k0； 設監(jiān)督位為 r2 r1 r0， 監(jiān)督位對應的多項式為 : r(x) = r2x2 +r1x +r0 ； 系統(tǒng)碼 碼字 C = (k3 k2 k1 k0 r2 r1 r0)對應的碼多項式為 : C(x)

22、= 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) + r (x) - (1) 根據(jù)生成多項式 性質(zhì) 1， 任何碼多項式一定能被 g(x)整除 ： C (x) mod g(x) =0 即： x r k (x) mod g(x) + r (x) mod g(x) = 0； 移項 ， 并考慮到模 2運算可把負號變正號 ， 于是： r (x) mod g(x) =

23、x r k (x) mod g(x)； 因為 r (x) 是 r-1次多項式 ， g(x) 是 r 次多項式 ， 所以 r (x) mod g(x)= r (x) 得到直接 計算系統(tǒng)碼碼字監(jiān)督多項式的公式是 ： r (x) = x r k (x) mod g(x) -(2) 再由公式 (1)就得到了相應的碼字。 例 1求 (7, 4)循環(huán)碼中信息位 K = (0100) 對應的碼字： 解： k(x) = x2, r = 3, xr k (x) = x5, g(x) = x3+x+1； 由 (2): r (x) = x5 mod x3+x+1 = x2 +x +1； 由 (1): C(x) =

24、xr k (x) + r(x) = x5 + x2 + x +1； C = (0100111)； 同法可得到所有 16個信息 (00001111) 的碼字。 小結(jié)：循環(huán)碼的編碼步驟： 1、 確定 (n,k)循環(huán)碼的生成多項式：將 xn-1分解因 式 ， 從中選擇一個 r次的因子作為 g(x)。 2、根據(jù)信息 K， 由 r (x) = x r k (x) mod g(x) 計算 出它的監(jiān)督位。 3、由 信息位 + 監(jiān)督位 直接寫出編碼 C； 4、間接編碼方法： 由 g(x)得到一個碼字，循環(huán)移 位得到 k個碼字，寫出生成矩陣，通過線性變換 得到系統(tǒng)碼生成矩陣 G，最后由生成方程 C = KG 求

25、出相應碼字。 例 2 求 (7, 3)循環(huán)碼的生成多項式，并為信息 K = (110) 編碼。 解： ( 1) n=7, k=3, r=4 由： x7-1 = (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 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)左移三次

26、得到： C = (1101001)； 3.4.5 循環(huán)碼的譯碼（糾錯） (1) 由接收碼字 R， 寫出其接收碼多項式 R(x)； (2) 求伴隨子多項式 S(x) = R(x) mod g(x)； (3) 若 S(x) = 0（ 即接收碼多項式能被 g(x)整除 ） , 則表明接收碼無誤 。 (4) 若 S(x) 0， 表明接收碼有誤 ， 此時定義 錯誤格式多項式： E(x) = en-1xn-1+en-2xn-2+ +e2x2+ e1x+ e0； (5) 由 S(x) 求 對應的 E(x)。 因 S(x) = C(x)+E(x) mod g(x) = E(x) mod g(x)； 為了找到

27、S(x) 對應的 E(x)， 我們可以預先將 糾錯能力 t 位 以內(nèi)的各種錯誤格式 E(x)除以 g(x) 的余式都計算出來，列成一張 S (x)-E (x) 對照表， 由 S (x) 就能直接查出 E (x)。 (6) 糾錯譯碼： 由 C(x) = R(x) + E (x)就能寫出譯碼 C。 例 3 已知 (7,4)碼的生成多項式是 g(x) = x3+x+1；請為 R = (0110010)譯碼 。 解： 設接收碼為 R = (r6 r5 r4 r3 r2 r1 r0 )；由 S(x) = E(x) mod g(x)； 可列出 S(x)E(x) 對照表： 當 R = (0110010)時

28、， 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 計算機中對公式的計算其實仍歸結(jié)為數(shù)值計算，對所有的 賦值都能正確得到結(jié)果，就等于對公式的計算。 筆算時是從被除數(shù)的高位開始，依次對除數(shù)求商、求積、

29、求余，然后右移一位，繼續(xù)前述過程，直至到被除數(shù)末尾 。 現(xiàn)在的道理相同，只不過把除數(shù)固定在電路上（就是反饋 的位置）， 讓被除數(shù)逐位右移通動寄存器，通過反饋電路 實現(xiàn)求商、求積、求余的運算。 由于是二進制代碼，商只 有 1和 0兩個可能值，積就是除數(shù)本身或是零。商為 0時反 饋為 0，被除數(shù)不變；商為 1時反饋為 1，被除數(shù)與除數(shù)相 減，但模二減等于模二加。最后 留在寄存器中的就是余數(shù) , 上輪余數(shù)的首位被輸出，它的就是商。 3.4.6 編、譯碼的電路實現(xiàn) 1. 除法求余電路 ： 設被除數(shù)是 x r k (x) = x5=0100000，除數(shù)是 g(x) = x3+x+1=1011， 相除的過

30、程見表所示。 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ù)。 余數(shù)初值為零，覆蓋值是被除數(shù)減去商與除數(shù)之積。因此 將被除數(shù)諸位推入寄存器中，寄存器兼有減法計算功能， 每次移位后都只計算 3位長的一段。 寄存器最高位 (x2位 )為 0時，移位后除以 g(x)的商必

31、然為 0； 寄存器最高位為 1時商必然為 1；因此該位的 輸出的就是商。 該商被反饋回去，反饋位置是 g(x) 的非 0位，就相當于用商 去乘除數(shù)，其乘積不是 0就是 g(x)。 模 2加等價于模 2減， 就 實現(xiàn)了與寄存器中原先余數(shù)的相減運算。 如果商為 1， 1g(x)的最高位在與原先余數(shù)相減的運算中總 是相抵消的，所以只須考慮其余 3位的反饋即可。 2. 編碼電路 ： 把輸入的 K(x)從 D0端移到 D2后面，就得到了如圖所 示的實用編碼電路。 P D0 D1 D2 輸出 Q 輸入 K K(x) 輸入 D0D1D2 輸出 x3位 0 0 0 0 0 x2位 1 1 1 0 1 x1位

32、0 0 1 1 0 x0位 0 1 1 1 0 1 1 1 首先開關 P置向上 ， 開關 Q閉 合 ， 得到上面四行的數(shù)據(jù)； 輸出的就是信息 K。 然后 P置 向下 ， Q開啟 ， 繼續(xù)將寄存 器中的余數(shù)輸出；就是接在 后面的監(jiān)督 。 電路工作原理 ： (1)在 D2端加入 K(x)，就等于在 D0端加 x r k (x)，這樣 就省去了前置的乘以 x3的乘法 (移位 )器。 (2) 將 Q閉合， P置向上，就可以在進行除法運算的 同時，將信息 K送到輸出，形成編碼的前半段。 (3) 無須移位 7次，只要移位 4次，就可以完成求模 運算的工作，接著把 P置下， Q開啟，就可以把 D0D1D2中

33、的余數(shù)，順序接在編碼的后半段上， 形成完整的編碼。 3、 譯碼電路 ： 首先斷開 K2，接通 K1，利用除法求余電路，把接收碼 字 R(x) 除以 g(x) 的余式，即伴隨子 S (x)計算出來，存 于 D0D1D2中；與此同時， R(x) 也被緩存在 R0R6中。 R0R1R2R3R4R5R6 K1 D0 D1 D2 K2 然后，斷開 K1，接通 K2。 與門設計是對輸入（ 101）有響應。若 e6位錯，則求余 結(jié)果 S = 101，恰使與門有輸出，正好糾正 R6位。此后， 移位繼續(xù)進行， D0D1D2值發(fā)生變化，與門關閉，不再 影響 R5 R0的輸出。 若 e5位錯，則求余得出的 S =

34、(111)，與門無輸出，但 經(jīng)過一個節(jié)拍后 D0D1D2變成 (101)，與門變得有輸出， 正好輪到緩存器中 R5位的輸出，將它糾正；再繼續(xù)移位， 與門又關閉了。 其它位有錯時 ， 同樣引起類似于上述變化的糾錯過程 。 巧就巧在正好輪到 R有錯的那一位輸出時 ， 寄存器恰變 為 101， 與門便輸出糾錯信號 “ 1”， 將該位錯碼糾正 。 如此巧妙的玄機在哪里呢 ? 因為伴隨子 S(x) = R(x) mod g(x)= E(x) mod g(x)，所 以分析電路對 R(x)的作用與分析 E(x)是等價的。 當 R(x)為正確碼時， E(x)是全 0， 除法器求余結(jié)果為 0， 與門不會打開，

35、R(x)從緩沖器中原樣輸出。 當 R(x)有一位不正確時， E(x)的相應位是 1，其它全 0； 除法器求余邏輯是按照 x3+x+1設計的 ,初值為 000,當有 1 輸入時才變?yōu)?100,此后由于輸入全為 0,寄存器則按照 100010 001110011111101 的規(guī)律變化 ,共 7 步變到 101。 E(x)為 1的碼位進入運算器的同時也進入 緩沖器，經(jīng)過 7 步才能緩沖才能輸出，這時正好與門打開，將其糾正。 譯碼電路逐次移位的數(shù)據(jù)變化 錯誤格式 伴隨式 寄存器 繼續(xù)移位 又移位后 糾正位 e(x) S(x) D0D1D2 次數(shù) N D0D1D2 R e6=1 x2 +1 1 0 1

36、 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)碼的基本概念： (1) 碼字的循環(huán)移位 (2) 碼多項式及其兩個重要性質(zhì) (3) 循環(huán)碼的生成多項式 2.循環(huán)碼的編碼： 根據(jù)信息 K，直接由 r (x) = x r k (x) mod g(x) 求出監(jiān)督位，添在信息位后，即得到編碼。 3.循

37、環(huán)碼的譯碼 ： （ 1） 由接收碼字 R， 寫出其接收碼多項式 R(x)； （ 2） 求伴隨子多項式 S(x) = R(x) mod g(x)； （ 3） 若 S(x) = 0（ 即接收碼多項式能被 g(x)整除 ） , 則表明 接收碼無誤 。 （ 4） 若 S(x) 0， 表明接收碼有誤 ， 此時應 將糾錯能力 t 位 以內(nèi)的各種錯誤格式 E(x)除以 g(x) 的余式都計算出來 ， 列 成一張 S(x)-E(x) 對照表 。 （ 5）由 S (x) 直接查表得到 E (x)。 （ 6） 由 C(x) = R(x) + E (x)進行糾錯。 思考： 是否任意碼長 n和任意信息位 k都能構(gòu) 成

38、 (n,k)循環(huán)碼？（提示：考慮生成多項 式）。 作業(yè)： P114頁： 14、 17題 第三章 信道編碼 3.5 循環(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碼 : non-primitive BCH code 外語關鍵詞 上節(jié)回顧：循環(huán)碼 基本概念 ：

39、循環(huán)碼的特點，碼多項式，循環(huán)移位的數(shù)學表達。 生成多項式： （ 1）碼多項式中冪次最低（冪次為 r ）常數(shù)項為 1的非 零多項式。 （ 2）通過對 g(x)的循環(huán)移位可獲得其它一些碼多項式。 （ 3）任意碼多項式 T(x)都應能被 g(x)整除。 （ 4） g(x)是 xn-1的一個因式。 循環(huán)碼的編碼： （ 1）分解 xn-1，以獲得生成多項式 g(x)； （ 2）求監(jiān)督多項式： r (x) = x r k (x) mod g(x)； （ 3）寫出相應碼字： C(x) = x r k (x) + r (x)； 循環(huán)碼的譯碼： （ 1） 根據(jù) S(x) = E(x) mod g(x)； 算出糾

40、錯能力 t 位 以內(nèi)的各種錯誤格式 E(x) 的 S (x) 對照表； （ 2） 求接收碼的伴隨子向量 S*(x) = R(x) mod g(x)； （ 3）從對照表中查出 S*(x) 對應的 E*(x) （ 4） C (x) = R (x) + E*(x) 3.5.1 增余漢明碼 漢明碼是能糾正一位錯的完備碼，具有較高的編碼效率。 如果給它的每一個許用碼字增加一位奇偶校驗位，使其 成為 (n+1, k) 碼，其編碼效率降低不多，但監(jiān)督能力卻 得到提高，不僅能糾正 1位錯，還能發(fā)現(xiàn)第 2位錯。 如 (7, 4)碼改為 (8, 4)碼，第 8列的碼元滿足偶校驗關系： c7= c6+c5+c4+c

41、3+c2+c1+c0； 一致監(jiān)督矩陣由 H(7,3)變?yōu)?H(8,4) ： 校驗矩陣增加全 1的一行，當計算 S=RHT時，該 列的計算是 s4= c7+c6+c5+c4+c3+c2+c1+c0,對于 偶校驗，如果是正確碼字結(jié)果必然為 0。 當只有一位錯時， s4必然為 1，而伴隨子 S的其 它各列 與 HT 的某一行相同。 如果出現(xiàn)兩位錯時，由 S=RHT=EHT ，而 E中有兩 列為 1， 致使 s4=e7+e6+e5+e4+e3+e2 +e1 +e0 必然 為 0，就表明有兩個錯。當然，它無法糾正，只 能要求系統(tǒng)重發(fā)。 3.5.2 截短循環(huán)碼 求生成多項式，需要分解 xn-1，但只有 n

42、=2m-1的數(shù)才 能查表分解，這就限制了 n的取值。 其次，并不是任何 xn-1中都能找到 r次的因子。比如 x 5-1 中就不含 r=2和 r=3的因子，難以構(gòu)造 (5,2)碼。 可以從效率較高的（ 7,4）漢明碼出發(fā)，在 (7,4) 碼的 生成矩陣中去掉前兩行和前兩列，剩下的部分構(gòu)成一 個 5 2的矩陣，可以用它來生成 (5,2)碼 。 相對于原來的循環(huán)碼， 信息位與碼長被同步地 減小了 。這樣的編碼稱之為截短循環(huán)碼。 截短循環(huán)碼的普遍表達是 (n-i, k-i)， i是截短位 數(shù)，監(jiān)督位長度 r=(n-i)-(k-i)=n-k不變。 截短循環(huán)碼的引入，擴大了循環(huán)碼的覆蓋范圍， 使人們能根

43、據(jù)所需要的 n、 k值靈活地設計各種 (n-i, k-i)碼。 截短循環(huán)碼具有循環(huán)碼的許多結(jié)構(gòu)特點 ， 監(jiān)督 位沒有變 ， 糾錯能力不變 ， 糾錯方法不變等 。 但由于 “ 截短 ” ， 只取用了循環(huán)組中的部分許 用碼 ， 會使碼組失去循環(huán)移位性 。 3.5.3 循環(huán)冗余校驗碼 (CRC) Cyclic Redundancy Cheek 循環(huán)冗余校驗碼是截短循環(huán)碼的一個典型應用。 在數(shù)據(jù)通信和軟盤 、 光盤存儲器中 ， 常常需要對 較多信息 （ 一個數(shù)據(jù)幀或一個記錄軌道中的數(shù)據(jù) ） 進行差錯監(jiān)督 。 數(shù)據(jù)的長短往往不確定 ， 但校驗 位的長度 r卻是固定的 。 根據(jù) n=2r-1設計出一個 (

44、n, k) 循環(huán)碼后 ， 當信息 長度小于 k時 ， 只要同時截短信息位和碼字的長 度 ， 而保持監(jiān)督位不變 ， 便得到一個 (n-i, k-i ) 截短循環(huán)碼 ， 這就是循環(huán)冗余校驗碼 （ CRC)。 常取 r =16 ，這時 g (x) = x16+x12+x5+1 =10001000000100001(B)=11021(H) g (x)作為最輕的碼字，它的重量為 4，表明該碼組 中最小漢明距離 d 0= 4，能糾正 1位差錯同時還能檢 查到第 2位差錯。 例如信息為 K(x)=4D6F746F(H) ， 則可以在信息后 面添上 CRC監(jiān)督碼： r (x)=x16K(x) mod g(x)

45、 = =4D6F746F0000(H) mod 11021(H)= B944(H) 有時也取 32位的 CRC校驗碼，生成多項式為： g(x)=(x16+x15+x2+1)(x16+x2+x+1) 循環(huán)冗余校驗碼不僅實現(xiàn)起來比較簡單，而且具 有很強的檢測能力。它能檢測出： （ 1）絕大部分連續(xù)長度不大于 n-k+1的突發(fā)錯誤。 （ 2）相當一部分連續(xù)長度大于 n-k+1的突發(fā)錯誤。 （ 3）所有與許用碼字漢明距離不大于 d0-1的錯誤。 （ 4）所有奇數(shù)個錯位。 當錯位較少時 ， 它能自動糾正 ， 當差錯超過糾錯 能力時 ， 根據(jù)校驗位很容易進行檢錯 ， 采用重發(fā) 反饋 (ARQ) 方式保證數(shù)

46、據(jù)的正確性 。 1.復數(shù)域中的分解： 分解 xn-1， 相當于求方程 xn-1=0的根 ； 如 x2-1=0的根是 x=1和 x=-1， 則 x2-1=(x-1)(x+1) 同理若 xn-1=0的 n個根是 x = x1 ,x2 , ,xn， 則： xn-1= (x - x1)(x - x2) (x xn)； 顯然，由 xn = 1知 ， 這 n個根應當是 1的 n次方根。 寫 1=1e j 0 ，根據(jù)復數(shù)開方公式： 插件 2： xn-1的因式分解原理 這 n個根模長均為 1，輻角等分單位園的圓周。 令： = e j 2/n ； 則： xk = k ( k=0,1, ， n-1 ) 于是： 結(jié)

47、論：復數(shù)域中 xn-1分解為 n個 1次因式的乘積。 1 0 2 3 n-1 4 2.共厄類： 當 n=2m-1時， xn-1的 n個根 k (k=0,1,2, ,n-1) 按 平方關系 ： k = i,2i,4i,8i,16i ； 可以 分成若干類。 不妨以 n=15, x15-1=0的 15個根為例。 i=1的類包含： 1， 2， 4， 8 這 4個根； 16 =1， 32 =2， 又會重復出現(xiàn) 這 4個根。 i=3的類包含： 3， 6， 12， 24 =9這 4個根； 48 =3， 96 =6， 又會重復出現(xiàn) 這 4個根。 同理得到其它共厄類： 共厄類 根 根的個數(shù) i=1類 1,2,4

48、,8 4個 i=3類 3,6,12,24 =9 4個 i=5類 5,10 2個 i=7類 7,14,28 =13 ,56 =11 4個 i=0類 0=1 1個 結(jié)論： x15-1=0 有 5個共厄類，各個類互不重復， 且恰巧取盡了全部 15個根。 3.xn-1在 GF(2)域中的分解： 因式分解與定義域是密切關聯(lián)的。比如在復數(shù)域中 x2+1=(x+j )(x-j )，但在實數(shù)域中， x2+1已經(jīng)不能再分解了。 GF(2)域只有 0和 1兩個數(shù)字，其它數(shù)是不存在的。 我們來看 x15-1=0的第 i=5類中 5與 10 這 2個 1次因式： 5= e j (5 2)/15= e j 2/3； 1

49、0= e j (10 2)/15= e j 4/3 = e-j 2/3 ； (x -5)(x -10 )= (x -e j 2/3)(x - e-j 2/3 )= = x2 (e j 2/3+e-j 2/3 ) x+1= x2 2cos (2/3) x+1 = x2 + x+1 在 GF(2)域 x2 + x+1已經(jīng)最簡，不能再分解了。 我們把它 叫做 i=5類對應的最小多項式，記作： m5(x)= x2 + x+1； 同理，屬于每個共厄類的各 1次因式相乘，都可得到 GF(2) 域中一個 相應 的 最小多項式 ，其冪次等于 共厄類中根的個數(shù)： m1(x)=(x -)(x 2 )(x 4)(x

50、 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 于是： x15-1=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) 4.本原與非本原 ： (1)本原根與非本原根： xn=1的 n個根 0 =1 ,2, , n-1

51、 可分為 本原根與非 本原根兩種，二者 的 區(qū)別是看 能否由 k 的一切冪次生成 xn=1 的全部根。 下面以 x15=1的部分根為例來說明： 冪次 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 2 3 4 5 6 7 8 9 10 11 12 13 14 1 2 4 6 8 10 12 14 3 5 7 9 11 13 1 3 6 9 12 1 3 6 9 12 1 3 6 9 12 1 5 10 1 5 10 1 5 10 1 5 10 1 5 10 1 7 14 6 13 5 12 4 11 3 10 2 9 8 1 可以看出 ,2 ,7 本原根， 3 ,5 是

52、非本原根。 (2)本原根與非本原根的循環(huán)性： 因為 k是 xn=1的根，所以 (k)n =1，不論本原與非非 本原，任何一個根自乘 n次必然等于 1。 然而，例中第 i=3類中的根 k (k=3,6,9,12)，因為 i值是 n值的因子，每個根 k無須自乘 n =15次，只要自乘 m=n/i=5次，就能回到 0 =1；同理， 第 i=5類中的根 k， 只 要自乘 m=n/i= 3次，就能回到 0 =1。我們 把通過自乘能回 到 0 =1 的最小自乘次數(shù) m叫做該類元素的循環(huán)級。 例中第 i=1類和 i=7類， k值與 n值互素，因而每個根 k因 式都必須自乘 n=15次才能回到 0 =1，表明

53、這些根的循環(huán)級 m =15 結(jié)論：本原根的冪次與 n互素，所以循環(huán)級等于 n；非 本原根的冪次與 n可約，所以循環(huán)級是 n的因子。 類 根 循環(huán)級 是否本原 最小多項式 i=1 1,2,4,8 15 是 x4 + x+1 i=3 3,6,9 , 12 5 非 x4 +x3 +x2 + x+1 i=5 5,10 3 非 x2 + x+1 i=77,11, 13 , 14 15 是 x4 +x3 +1 i=0 0=1 1 非 x+1 x15-1的根、共厄類及其最小多項式 注意： 各 既 約因式冪次 r 等于該類中根的個數(shù)，它 與該共厄 類的循環(huán)級 m的關系是： 2r mod m=1 (3)本原類與

54、非本原類： 共厄類是以根的平方（即自乘）關系劃分的，自乘不會 改變冪次與 n互素或可約的本性，所以 同一共厄類中的根， 本原屬性相同。 因此， 本原根構(gòu)成的類是本原類，非 本原根構(gòu)成的類是 非本原類。 本原類的類序號 i與 n互素，非本原類的類序號 i 與 n可約。 (4)本原多項式與非本原多項式： 同一類根的一次因式相乘得到該類的最小多項式。 因此， 本原類的最小多項式是本原多項式，非本原類的 最小多項式是非本原多項式 。 這樣就把 xn-1分解得到的因 式也分成了本原與非本原兩種。 (5)非本原多項式的一個性質(zhì)： 以 x15=1為例， 設： =2/15， =e j； 則 i=3類的 4個非

55、本原根為： 3 的輻角 =6/15= 2/5， 6 的輻角 =12/15= 4/5， 9 的輻角 =18/15= 6/5， 12 的輻角 =24/15= 8/5 連同 0 =1, 它們五等份單位圓 , 構(gòu)成 x5=1的 5個根。因此： (x -3) (x - 6) (x - 9) (x - 12 ) = x4 +x3 +x2 + x+1 不僅是 x15 -1的因式，也 是 x5 -1的因式 。 結(jié)論：非本原多項式是不僅是 xn -1的因式，也 xm -1的因 式。 (這里 m是循環(huán)級， n是 m的倍數(shù)） 3 6 9 12 小結(jié)： xn-1有 n個復數(shù)根 k， 它們按平方關系分為若干個共厄類。

56、同一個共厄類的諸根的 1次因式相乘，得到 GF(2)域的一個既 約因式。每類都有 自己的 既約因式，各 既 約因式冪次 r 等于 該類中根的個數(shù)， x n-1就可分解為這些既約因式之積。 同一個共厄類的根有相同的循環(huán)級。循環(huán)級 m等于 n的根是本 原根，循環(huán)級 m等于 n的某個因數(shù) (n/i)的根是非本原根。 本原根所在共厄類的 既 約因式叫做本原多項式，非本原根所 在共厄類的既約因式叫做非本原多項式。反之也可以說，本 原多項式的根是本原根，非本原多項式的根是非本原根。 本原多項式與非本原多項式都是 xn-1的因式，但是非本原多 項式還是 xm-1的因式，這里 m是 n的因子 ( m=n i

57、) 3.5.4 二元本原 BCH碼 因式分解的數(shù)學理論解決了循環(huán)碼的存在問題，并為它 奠定了堅實的基礎。 1.如何構(gòu)造能糾正一位錯的循環(huán)碼多項式？ 根據(jù)因式冪次與循環(huán)級的關系 ，當 n=2r 1時， x n-1 必存 在最高冪次為 r 的本原多項式。可構(gòu)成 糾一位錯的漢明碼。 例如， r =3,4,5,6 時： n=23-1=7： x7-1有 3次本原因式 x3+x+1，得到 (7,4)碼 n=24-1=15： x15-1有 4次本原因式 x4+x+1，得到 (15,11)碼 n=25-1=31： x31-1有 5次本原因式 x5+x2+1，得到 (31,26)碼 n=26-1=63： x63

58、-1有 6次本原因式 x6+x+1，得到 (63,57)碼 2.能不能構(gòu)造能糾正多位錯的循環(huán)碼多項式？ 理論上線性分組碼糾錯位數(shù) t與冗余位 r的關系是 t r/2， 為了糾錯位數(shù)更多一些，監(jiān)督位數(shù) r 就得更大一些 ,也就是 說生成多項式的冪次 r 需要更大一些。 xn -1既然可分解為多個因式，我們不妨取幾個因子的乘積 作為生成多項式，就能增加它的冪次。而幾個因子的乘積 仍然還是 xn-1的因式。 比如 x7-1=（ x+1)(x3+x+1)(x3+x2+1)；取生成多項式： g(x)=(x3+x+1)(x3+x2+1)=x6+x5+x4+x3+x2+x+1 現(xiàn)在監(jiān)督位增加到 r=6，就能

59、構(gòu)成（ 7,1）碼 (即七連重復 碼 )，它可以糾正 3位錯 (因為 26=1+7+21+35)。 又如 x15-1=(x+1)(x4+x+1)(x4+x3+x2+x+1) (x2+x+1)( x4+x3+1) 取生成多項式： g(x)=(x4+x+1)(x4+x3+x2+x+1)(x2+x+1) =x10+x8+x5+x4+x2+x+1 現(xiàn)在監(jiān)督位增加到 r=10，就能構(gòu)成（ 15, 5）碼， 它可以糾正 3位錯。 (因為 2101+15+105+455) 定義： 取 碼長為 n = 2m 1， 取 包括本原多項式在內(nèi) 的若干個因式之積為生成多項式的循環(huán)碼叫做本原 BCH碼。 BCH是能糾正

60、多位錯的循環(huán)碼。 3.能不能根據(jù)糾錯位數(shù) t來設計生成多項式？ 進一步的研究得知，給定 t 就能 決定在 xn-1中選取哪些因式。 設 t 是所設計的糾錯位數(shù)， mi(x) 是 xn-1的因式，這里 i =1,3,5,7 ， 則生成多項式： 式中： LCM 表示求最小公倍式。 這種碼長為 n = 2m-1，生成多項式由上述公式定義的循環(huán)碼， 叫做本原 BCH碼。 這是更具實際意義的定義。 P195頁表 5給出了 n255 的所有本原 BCH碼的碼長、信息位、 糾錯位數(shù)，并以 8進制方式給出了生成多項式。 例 1 構(gòu)造碼長為 15， 分別能糾正 1位 、 2位 、 3位和 4位錯 的本原 BCH

61、碼生成多項式 。 解：查最小多項式系數(shù)表 （ 參見附錄二表 4)知： x15-1= 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） t =1時： 2t-1=1， g(x) = LCM m1(x) = (x4+x+1) ；得到 (15,11)碼 。 （ 2） t =2時： 2t-1=3， g(x) =LCM m1(x) m3(x) = =(x4+x+1)(x4+x3+x2+x+1)=x8+x7+x6+ x4+x+1； 得到 （ 15,7） 碼 。 （ 3） t =3時： 2t-1

62、=5， g(x)=LCM m1(x)m3(x)m5(x) =(x4+x+1)(x4+x3+x2+x+1)(x2+x+1) =x10+x8+x5+ x4+x2 +x+1； 得到 （ 15,5） 碼 。 （ 4） t =4時： 2t-1=7， g(x) =LCM m1(x) m3(x) m5(x) m7(x) =(x4+x+1)(x4+x3+x2+x+1)(x2+x+1)(x4+x3+1) =x14+x13+x12+x11+x10+x9+x8 +x7+x6+x5+x4+x3+x2 +x+1； 得到 （ 15,1） 碼 ， 即 15連重復碼 。 3.5.5 二元非本原 BCH碼 本原 BCH碼在碼長

63、 n給定的條件下，通過增大監(jiān)督位數(shù) r 來提高糾錯能力。這樣必然導致編碼效率 k/n降低。 如果在糾錯能力不變（即 r不變）的條件下減小 n值，是 否有可能得到編碼效率較高且能糾多位錯的編碼呢？非 本原的 BCH碼就是這樣的編碼。 因為非本原多項式的共厄類 i與 n可約， m是它的循環(huán)級 ， 根據(jù)數(shù)學理論， xm-1的因式分解中就能包含 共厄類 i 相 應的那個非本原多項式。以此非本原多項式為生成多項 式，可得到的碼長為 m循環(huán)碼， r 沒變， 碼長 m卻比 n小 多了，使效率大大提高。 比如： x15-1= m0(x)m1(x) m3(x) m5(x) m7(x) = (x+1)(x4+x+

64、1) (x4+x3+x2+x+1) (x2+x+1) (x4+x3+1) 式中： m3(x)= x4+x3+x2+x+1是非本原多項式 ， 因 15/3=5， 所以 m3(x)也是 x5-1的因式；以此為 生成多項式 ， 可得到 （ 5,1） 碼 。 m5(x)= x2+x+1也是非本原多項式 ， 因 15/5=3， 所以它是 x3-1的因式；作為生成多項式 ， 得到 （ 3,1） 碼 。 又如 ， n=28-1=255， x255-1中有一個 8次的非本原多項式 m15(x)=x8+x7+x6+x4+x2+x+1。 因為 n/i =255/15=17， 所以 x17-1中會包含這個 8次的因

65、子 。 由此可構(gòu)造 (17,9)碼 。 由糾錯不等式 2r=256大于 C017+C117+C217=154不難知道 ， 線 性分組循環(huán)碼 (17,9)可糾正兩位錯 。 冗余利用率 t/r達到 1/4， 可糾錯比值 t/n達到 2/17， 編碼效率 k/n超過 50%。 利用非本原 BCH碼 ， 人們構(gòu)造了不少好碼 。 (23,12) 和 (47,24) 碼 ， 效率超過 50%， 分別可以糾正 t=3和 t=5位錯誤 碼元 。 特別是 (23,12)叫 Golay碼 ， 是迄今為止人們所找到 的少有的能糾正多個錯誤的完備碼 。 表 3.11 某些非本原 BCH碼的生成多項式 r i n/i

66、k t d0 以 8進數(shù)表示 g (x) 6 3 21 12 2 5 (127)(15) 8 15 17 9 2 5 (727) 9 7 73 46 4 9 (1210)(1027)(1401) 10 31 33 22 2 5 (3043)(3) 10 31 33 13 4 9 (3043)(3777) 11 89 23 12 3 7 (5343) 12 63 65 53 2 5 (10761) 12 63 65 40 4 9 (13535)(10761)(3) 23 178481 47 24 5 11 (43073357) 例 2 構(gòu)造碼長為 21， 分別能糾正 1位 、 2位和 5位錯的非本 原 BCH碼生成多項式 。 解： 21不是 2m-1的數(shù) ， 但它是 26-1=63的因子 ， 與 63有公因 子 3。 由 187頁表查到相應的 5類非本原多項式是： m3(x)= x6+x4+x2+x+1 m9(x)= x3+x2+1 m15(x)= x6+x5+x4+x2+1 （ 與 m3(x)對偶 ） m21(x)= x2+x+1 m27(x)= x3+x+1 （ 與 m9(x)對偶