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

《《信道編碼中》PPT課件.ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《《信道編碼中》PPT課件.ppt（85頁珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、第三章 信道編碼 3.4 循環(huán)碼 本節(jié)的主要內(nèi)容 碼多項(xiàng)式 循環(huán)移位的數(shù)學(xué)表達(dá) 循環(huán)碼的生成多項(xiàng)式 循環(huán)碼的編碼 循環(huán)碼的譯碼 編 、 譯碼的電路實(shí)現(xiàn) 循環(huán)碼： cyclic code 碼多項(xiàng)式： code polynomial 生成多項(xiàng)式： generator polynomial 求模運(yùn)算： modular arithmetic 系統(tǒng)碼： systematic（ regular） code 循環(huán)移位運(yùn)算： cycle shift operation 外語關(guān)鍵詞 上節(jié)回顧：線性分組碼 基本概念 ： 表達(dá)方式： (n,k)碼， k是信息位數(shù)， r是監(jiān)督位數(shù)， n=k+r是碼長。 編碼： 已知信

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

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

4、是設(shè)計(jì)出一個(gè)好的生成 矩陣，使所有碼字之間的漢明距離盡量大。怎 樣找這樣的矩陣呢？循環(huán)碼的出現(xiàn)提供了一整 套理論和方法，使人們能夠借助數(shù)學(xué)工具來尋 找更好的線性分組碼，并由此引發(fā)出一大類很 常用檢、糾錯(cuò)編譯碼。 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)碼是線性分組碼中的一個(gè)子集。 對(duì)于循環(huán)碼，有了一個(gè)的碼字，按循環(huán) 移位規(guī)律就能寫出 n個(gè)碼字。從中選出 k 個(gè)來構(gòu)造生成矩陣 G，就能生成全部 2k個(gè) 許用碼字。 循環(huán)碼與近代數(shù)學(xué)有密切聯(lián)系。使我們 可以借助數(shù)學(xué)工具來設(shè)計(jì)編碼。 3.4.1 碼多項(xiàng)式 二進(jìn)制自然碼可表達(dá)為以 2為底的多項(xiàng)式表達(dá)，如： C = (1010111)= =1 26 +0 25 +1 24 +0 23 +1 22 +1 21 +1 20 ； 把底換為 x， 則得到 “

6、 碼多項(xiàng)式 ” ： C (x) = 1x6 +0 x5 +1x4 +0 x3 +1x2 +1x1 +1x0 = x6 + x4 + x2 + x +1 碼長為 n時(shí) ， 可寫 ： C (x) = cn-1 xn-1 + cn-2 xn-2 + + c1 x1 + c0 x0 如三位二元碼的 8個(gè)碼字對(duì)應(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 3.4.2 循環(huán)移位的數(shù)學(xué)表達(dá) 對(duì)二進(jìn)數(shù)，左移一位相當(dāng)于乘以 2，而將最高位的進(jìn)位 (2n位 )上的數(shù)碼拿回到

7、 20位，叫做循環(huán)移位， 相當(dāng)于作 模 2n -1運(yùn)算。 如： 1011010011 實(shí)際是 5 2 mod 7 = 3 碼多項(xiàng)式的 循環(huán)移位，實(shí)際是乘 x后作模 xn -1 運(yùn)算 。 如： 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)碼及其碼多項(xiàng)式的循環(huán)移位： 循環(huán)次數(shù) 循環(huán)碼 碼多項(xiàng)式 模 x7-1運(yùn)算后 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)碼的生成多項(xiàng)式 (1) 生成多項(xiàng)式的定義和特點(diǎn) 循環(huán)碼的碼多項(xiàng)式中冪次最低的非零多項(xiàng)式叫做生成多 項(xiàng)式，記做 g(x)。 如 (7,4)碼的 x3 +x +1。 有了它， 其它 碼字都可由 xi g(x) 的模 xn-1得到。 生成

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

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

11、x) （ 3）生成多項(xiàng)式 g(x)的 確定： 由性質(zhì) 2知， g(x)是 xn-1的一個(gè)因式 ?？?根據(jù)設(shè) 定的碼長 n和監(jiān)督位 r， 將 xn-1因式分解，從中選擇 一個(gè) r次的因子作為 g(x)。 例如： (7, 4) 碼 ， n = 7， k = 4， r = 3； 分解： x7-1 = (x-1) (x3+x+1) (x3+x2+1) g(x) 應(yīng)是 x7-1 的一個(gè) r = 3次的因子 ， 可取為： g(x) = x3+x+1 或 g(x) = x3+x2+1； 二者任選其一，一旦選定，就不再考慮另一個(gè)了。 插件 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總有一個(gè) m0(x)=x+1的因式。 （ 3） xn-1其它因式是 mi(x), i=1,3,5,7 （ 4） mi(x)的表達(dá)由 8進(jìn)制數(shù)給出 ，將它換成二進(jìn)制自然碼就 是 mi(x)各位的系數(shù)。如 m=5階時(shí)， 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所有的因式， 與已列出因式對(duì)偶的因 式 都被省略了 。所謂對(duì)偶指的是將二進(jìn)制自然碼高低位倒置 的表達(dá)，如： 與 (100101)2對(duì)稱的是 (101001)2，表示 m15(x)=x5+x3+1； 與 (111101)2對(duì)稱的是 (101111)2，表示 m7(x)=x5+x3+x2+x+1； 與 (110111)2對(duì)稱的是 (111011)2，表示 m11(x)=x5+x4+x3+x+1； 值得注意的是，有的二

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

15、x5+1； i=3： (127)8=(1010111)2，得知 m3(x)=x6+x4+x2+x+1； 由對(duì)偶式 (1110101)2和 187頁表知 m15(x)=x6+x5+x4+x2+1； i=5： (147)8=(1100111)2，得知 m5(x)=x6+x5+x2+x+1； 由對(duì)偶式 (1110011)2和 187頁表知 m23(x)=x6+x5+x4+x+1； i=7： (111)8=(1001001)2，得知 m7(x)=x6+x3+1； 對(duì)偶式還是自己。 i=9： (015)8=(1101)2，得知 m9(x)=x3+x2+1； 由對(duì)偶式 (1011)2和 187頁表知 m2

16、7(x)=x3+x+1； i=11： (155)8=(1101101)2，得知 m11(x)=x6+x5+x3+x2+1； 由對(duì)偶式 (1011011)2和 187頁表知 m13(x)=x6+x4+x3+x+1； i=21： (007)8=(111)2，得知 m21(x)=x2+x+1； 其對(duì)偶式仍是自己； 最終結(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)本原多項(xiàng)式是 m1(x), m5(x), m11(x), m13(x), m23(x)和 m31(x)；

17、(1)循環(huán)碼的生成矩陣 求出了生成多項(xiàng)式 g(x)，等于得到了一個(gè)碼字，通過 循環(huán)移位不難得到其它碼字。 果然如此簡單嗎？ 實(shí)際上，通過循環(huán)移位最多可寫出 n個(gè)碼字，得不到全 部碼字，因?yàn)?(n,k)碼應(yīng)當(dāng)共有 2k個(gè)許用碼字。 例如 (7, 4)循環(huán)碼共有 16個(gè)許用碼字。 取 g(x)= x3+x+1 ，等于知道了中信息 K=(0001)所對(duì)應(yīng) 的那個(gè)碼字： C1=(0001 011)。 3.4.4 循環(huán)碼的編碼 C1經(jīng)過循環(huán)移位只能得到 7個(gè)碼字： 序號(hào) 信息位 許用碼字 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個(gè)許用碼字，還缺 9個(gè)。 從循環(huán)組中隨便取 4個(gè)許用碼字，比如前 4個(gè)，用它們 構(gòu)成的生成矩陣為 G1： 再利用 C = KG1 就能求得全部許用碼字。 比如： (0100)G1=(0101100); (1000)G1=(1011000); 然而發(fā)現(xiàn)碼字 不具備信息位在前，監(jiān)督位在后的形式。 原因是 G1不 具備 G=Ik Q的形式，這樣編碼叫 非系統(tǒng)碼， 非系統(tǒng)碼在譯碼時(shí)是比較困難的。 實(shí)際上，為了構(gòu)造 G

19、=Ik Q 形式的生成矩陣 。 需要如下的 4個(gè)碼字： 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 才能排列出 4 4的單位矩陣 Ik。 通過對(duì) C1=(0001 011)的循環(huán)移位可以得到 （ 0010 110）和（ 1000 101)， 但是卻無法得到 (0100 ) 0 1 1 1 1 0 1 0 1 原因何在？ 原來 0100所對(duì)應(yīng)的碼字 （ 0100 111)位于 另一循環(huán)組中 : 第一循環(huán)組 第二循環(huán)組 序號(hào) 信息 許用碼字 序號(hào) 信息 許用碼字 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）直接計(jì)算系統(tǒng)碼的監(jiān)督元 : 以 (7, 4)碼為例，設(shè)信息位為 k3 k2 k1 k0，對(duì)應(yīng)的多項(xiàng)式 為： k(x)=k3x3 +k2x2 +k1x +k0； 設(shè)監(jiān)督位為 r2 r1 r0， 監(jiān)督位對(duì)應(yīng)的多項(xiàng)式為 : r(x) = r2x2 +r1x +r0 ； 系統(tǒng)碼 碼字 C = (k3 k2 k1 k0 r2 r1 r0)對(duì)應(yīng)的碼多項(xiàng)式為 : 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) 推廣到一般 ， 碼多項(xiàng)式可寫為為： C(x) = x r k (x) + r (x) - (1) 根據(jù)生成多項(xiàng)式 性質(zhì) 1， 任何碼多項(xiàng)式一定能被 g(x)整除 ： C (x) mod g(x) =0 即： x r k (x) mod g(x) + r (x) mod g(x) = 0； 移項(xiàng) ， 并考慮到模 2運(yùn)算可把負(fù)號(hào)變正號(hào) ， 于是： r (x) mod g(x) =

23、x r k (x) mod g(x)； 因?yàn)?r (x) 是 r-1次多項(xiàng)式 ， g(x) 是 r 次多項(xiàng)式 ， 所以 r (x) mod g(x)= r (x) 得到直接 計(jì)算系統(tǒng)碼碼字監(jiān)督多項(xiàng)式的公式是 ： r (x) = x r k (x) mod g(x) -(2) 再由公式 (1)就得到了相應(yīng)的碼字。 例 1求 (7, 4)循環(huán)碼中信息位 K = (0100) 對(duì)應(yīng)的碼字： 解： 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個(gè)信息 (00001111) 的碼字。 小結(jié)：循環(huán)碼的編碼步驟： 1、 確定 (n,k)循環(huán)碼的生成多項(xiàng)式：將 xn-1分解因 式 ， 從中選擇一個(gè) r次的因子作為 g(x)。 2、根據(jù)信息 K， 由 r (x) = x r k (x) mod g(x) 計(jì)算 出它的監(jiān)督位。 3、由 信息位 + 監(jiān)督位 直接寫出編碼 C； 4、間接編碼方法： 由 g(x)得到一個(gè)碼字，循環(huán)移 位得到 k個(gè)碼字，寫出生成矩陣，通過線性變換 得到系統(tǒng)碼生成矩陣 G，最后由生成方程 C = KG 求

25、出相應(yīng)碼字。 例 2 求 (7, 3)循環(huán)碼的生成多項(xiàng)式，并為信息 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)碼的譯碼（糾錯(cuò)） (1) 由接收碼字 R， 寫出其接收碼多項(xiàng)式 R(x)； (2) 求伴隨子多項(xiàng)式 S(x) = R(x) mod g(x)； (3) 若 S(x) = 0（ 即接收碼多項(xiàng)式能被 g(x)整除 ） , 則表明接收碼無誤 。 (4) 若 S(x) 0， 表明接收碼有誤 ， 此時(shí)定義 錯(cuò)誤格式多項(xiàng)式： E(x) = en-1xn-1+en-2xn-2+ +e2x2+ e1x+ e0； (5) 由 S(x) 求 對(duì)應(yīng)的 E(x)。 因 S(x) = C(x)+E(x) mod g(x) = E(x) mod g(x)； 為了找到

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

28、， R(x) = x5+x4+x； S (x)=（ x5+x4+x） mod（ x3+x+1） = x+1； 查表知： E(x) = x3； 糾錯(cuò)： 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ì)算機(jī)中對(duì)公式的計(jì)算其實(shí)仍歸結(jié)為數(shù)值計(jì)算，對(duì)所有的 賦值都能正確得到結(jié)果，就等于對(duì)公式的計(jì)算。 筆算時(shí)是從被除數(shù)的高位開始，依次對(duì)除數(shù)求商、求積、

29、求余，然后右移一位，繼續(xù)前述過程，直至到被除數(shù)末尾 。 現(xiàn)在的道理相同，只不過把除數(shù)固定在電路上（就是反饋 的位置）， 讓被除數(shù)逐位右移通動(dòng)寄存器，通過反饋電路 實(shí)現(xiàn)求商、求積、求余的運(yùn)算。 由于是二進(jìn)制代碼，商只 有 1和 0兩個(gè)可能值，積就是除數(shù)本身或是零。商為 0時(shí)反 饋為 0，被除數(shù)不變；商為 1時(shí)反饋為 1，被除數(shù)與除數(shù)相 減，但模二減等于模二加。最后 留在寄存器中的就是余數(shù) , 上輪余數(shù)的首位被輸出，它的就是商。 3.4.6 編、譯碼的電路實(shí)現(xiàn) 1. 除法求余電路 ： 設(shè)被除數(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次多項(xiàng)式，余數(shù)至多 2次，故可取 3位寄 存器來存放余數(shù)。 余數(shù)初值為零，覆蓋值是被除數(shù)減去商與除數(shù)之積。因此 將被除數(shù)諸位推入寄存器中，寄存器兼有減法計(jì)算功能， 每次移位后都只計(jì)算 3位長的一段。 寄存器最高位 (x2位 )為 0時(shí)，移位后除以 g(x)的商必

31、然為 0； 寄存器最高位為 1時(shí)商必然為 1；因此該位的 輸出的就是商。 該商被反饋回去，反饋位置是 g(x) 的非 0位，就相當(dāng)于用商 去乘除數(shù)，其乘積不是 0就是 g(x)。 模 2加等價(jià)于模 2減， 就 實(shí)現(xiàn)了與寄存器中原先余數(shù)的相減運(yùn)算。 如果商為 1， 1g(x)的最高位在與原先余數(shù)相減的運(yùn)算中總 是相抵消的，所以只須考慮其余 3位的反饋即可。 2. 編碼電路 ： 把輸入的 K(x)從 D0端移到 D2后面，就得到了如圖所 示的實(shí)用編碼電路。 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 首先開關(guān) P置向上 ， 開關(guān) Q閉 合 ， 得到上面四行的數(shù)據(jù)； 輸出的就是信息 K。 然后 P置 向下 ， Q開啟 ， 繼續(xù)將寄存 器中的余數(shù)輸出；就是接在 后面的監(jiān)督 。 電路工作原理 ： (1)在 D2端加入 K(x)，就等于在 D0端加 x r k (x)，這樣 就省去了前置的乘以 x3的乘法 (移位 )器。 (2) 將 Q閉合， P置向上，就可以在進(jìn)行除法運(yùn)算的 同時(shí)，將信息 K送到輸出，形成編碼的前半段。 (3) 無須移位 7次，只要移位 4次，就可以完成求模 運(yùn)算的工作，接著把 P置下， Q開啟，就可以把 D0D1D2中

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

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

35、R(x)從緩沖器中原樣輸出。 當(dāng) R(x)有一位不正確時(shí)， E(x)的相應(yīng)位是 1，其它全 0； 除法器求余邏輯是按照 x3+x+1設(shè)計(jì)的 ,初值為 000,當(dāng)有 1 輸入時(shí)才變?yōu)?100,此后由于輸入全為 0,寄存器則按照 100010 001110011111101 的規(guī)律變化 ,共 7 步變到 101。 E(x)為 1的碼位進(jìn)入運(yùn)算器的同時(shí)也進(jìn)入 緩沖器，經(jīng)過 7 步才能緩沖才能輸出，這時(shí)正好與門打開，將其糾正。 譯碼電路逐次移位的數(shù)據(jù)變化 錯(cuò)誤格式 伴隨式 寄存器 繼續(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é)要點(diǎn) 1.循環(huán)碼的基本概念： (1) 碼字的循環(huán)移位 (2) 碼多項(xiàng)式及其兩個(gè)重要性質(zhì) (3) 循環(huán)碼的生成多項(xiàng)式 2.循環(huán)碼的編碼： 根據(jù)信息 K，直接由 r (x) = x r k (x) mod g(x) 求出監(jiān)督位，添在信息位后，即得到編碼。 3.循

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

38、 (n,k)循環(huán)碼？（提示：考慮生成多項(xiàng) 式）。 作業(yè)： P114頁： 14、 17題 第三章 信道編碼 3.5 循環(huán)碼的擴(kuò)展 本節(jié)的主要內(nèi)容 增余漢明碼 截短循環(huán)碼 循環(huán)冗余校驗(yàn)碼 二元本原 BCH碼 二元非本原 BCH碼 增余漢明碼： extended Hamming code 截短循環(huán)碼： shortened cyclic code 循環(huán)冗余校驗(yàn)碼： Cyclic Redundancy Check Code (CRC) 本原 BCH碼 ： primitive BCH code 非本原 BCH碼 : non-primitive BCH code 外語關(guān)鍵詞 上節(jié)回顧：循環(huán)碼 基本概念 ：

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

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

41、3+c2+c1+c0； 一致監(jiān)督矩陣由 H(7,3)變?yōu)?H(8,4) ： 校驗(yàn)矩陣增加全 1的一行，當(dāng)計(jì)算 S=RHT時(shí)，該 列的計(jì)算是 s4= c7+c6+c5+c4+c3+c2+c1+c0,對(duì)于 偶校驗(yàn)，如果是正確碼字結(jié)果必然為 0。 當(dāng)只有一位錯(cuò)時(shí)， s4必然為 1，而伴隨子 S的其 它各列 與 HT 的某一行相同。 如果出現(xiàn)兩位錯(cuò)時(shí)，由 S=RHT=EHT ，而 E中有兩 列為 1， 致使 s4=e7+e6+e5+e4+e3+e2 +e1 +e0 必然 為 0，就表明有兩個(gè)錯(cuò)。當(dāng)然，它無法糾正，只 能要求系統(tǒng)重發(fā)。 3.5.2 截短循環(huán)碼 求生成多項(xiàng)式，需要分解 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)成一 個(gè) 5 2的矩陣，可以用它來生成 (5,2)碼 。 相對(duì)于原來的循環(huán)碼， 信息位與碼長被同步地 減小了 。這樣的編碼稱之為截短循環(huán)碼。 截短循環(huán)碼的普遍表達(dá)是 (n-i, k-i)， i是截短位 數(shù)，監(jiān)督位長度 r=(n-i)-(k-i)=n-k不變。 截短循環(huán)碼的引入，擴(kuò)大了循環(huán)碼的覆蓋范圍， 使人們能根

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

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

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

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

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

48、,8 4個(gè) i=3類 3,6,12,24 =9 4個(gè) i=5類 5,10 2個(gè) i=7類 7,14,28 =13 ,56 =11 4個(gè) i=0類 0=1 1個(gè) 結(jié)論： x15-1=0 有 5個(gè)共厄類，各個(gè)類互不重復(fù)， 且恰巧取盡了全部 15個(gè)根。 3.xn-1在 GF(2)域中的分解： 因式分解與定義域是密切關(guān)聯(lián)的。比如在復(fù)數(shù)域中 x2+1=(x+j )(x-j )，但在實(shí)數(shù)域中， x2+1已經(jīng)不能再分解了。 GF(2)域只有 0和 1兩個(gè)數(shù)字，其它數(shù)是不存在的。 我們來看 x15-1=0的第 i=5類中 5與 10 這 2個(gè) 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類對(duì)應(yīng)的最小多項(xiàng)式，記作： m5(x)= x2 + x+1； 同理，屬于每個(gè)共厄類的各 1次因式相乘，都可得到 GF(2) 域中一個(gè) 相應(yīng) 的 最小多項(xiàng)式 ，其冪次等于 共厄類中根的個(gè)數(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個(gè)根 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)性： 因?yàn)?k是 xn=1的根，所以 (k)n =1，不論本原與非非 本原，任何一個(gè)根自乘 n次必然等于 1。 然而，例中第 i=3類中的根 k (k=3,6,9,12)，因?yàn)?i值是 n值的因子，每個(gè)根 k無須自乘 n =15次，只要自乘 m=n/i=5次，就能回到 0 =1；同理， 第 i=5類中的根 k， 只 要自乘 m=n/i= 3次，就能回到 0 =1。我們 把通過自乘能回 到 0 =1 的最小自乘次數(shù) m叫做該類元素的循環(huán)級(jí)。 例中第 i=1類和 i=7類， k值與 n值互素，因而每個(gè)根 k因 式都必須自乘 n=15次才能回到 0 =1，表明

53、這些根的循環(huán)級(jí) m =15 結(jié)論：本原根的冪次與 n互素，所以循環(huán)級(jí)等于 n；非 本原根的冪次與 n可約，所以循環(huán)級(jí)是 n的因子。 類 根 循環(huán)級(jí) 是否本原 最小多項(xiàng)式 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的根、共厄類及其最小多項(xiàng)式 注意： 各 既 約因式冪次 r 等于該類中根的個(gè)數(shù)，它 與該共厄 類的循環(huán)級(jí) m的關(guān)系是： 2r mod m=1 (3)本原類與

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

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個(gè)根。因此： (x -3) (x - 6) (x - 9) (x - 12 ) = x4 +x3 +x2 + x+1 不僅是 x15 -1的因式，也 是 x5 -1的因式 。 結(jié)論：非本原多項(xiàng)式是不僅是 xn -1的因式，也 xm -1的因 式。 (這里 m是循環(huán)級(jí)， n是 m的倍數(shù)） 3 6 9 12 小結(jié)： xn-1有 n個(gè)復(fù)數(shù)根 k， 它們按平方關(guān)系分為若干個(gè)共厄類。

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

57、) 3.5.4 二元本原 BCH碼 因式分解的數(shù)學(xué)理論解決了循環(huán)碼的存在問題，并為它 奠定了堅(jiān)實(shí)的基礎(chǔ)。 1.如何構(gòu)造能糾正一位錯(cuò)的循環(huán)碼多項(xiàng)式？ 根據(jù)因式冪次與循環(huán)級(jí)的關(guān)系 ，當(dāng) n=2r 1時(shí)， x n-1 必存 在最高冪次為 r 的本原多項(xiàng)式?？蓸?gòu)成 糾一位錯(cuò)的漢明碼。 例如， r =3,4,5,6 時(shí)： 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)造能糾正多位錯(cuò)的循環(huán)碼多項(xiàng)式？ 理論上線性分組碼糾錯(cuò)位數(shù) t與冗余位 r的關(guān)系是 t r/2， 為了糾錯(cuò)位數(shù)更多一些，監(jiān)督位數(shù) r 就得更大一些 ,也就是 說生成多項(xiàng)式的冪次 r 需要更大一些。 xn -1既然可分解為多個(gè)因式，我們不妨取幾個(gè)因子的乘積 作為生成多項(xiàng)式，就能增加它的冪次。而幾個(gè)因子的乘積 仍然還是 xn-1的因式。 比如 x7-1=（ x+1)(x3+x+1)(x3+x2+1)；取生成多項(xiàng)式： 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）碼 (即七連重復(fù) 碼 )，它可以糾正 3位錯(cuò) (因?yàn)?26=1+7+21+35)。 又如 x15-1=(x+1)(x4+x+1)(x4+x3+x2+x+1) (x2+x+1)( x4+x3+1) 取生成多項(xiàng)式： 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位錯(cuò)。 (因?yàn)?2101+15+105+455) 定義： 取 碼長為 n = 2m 1， 取 包括本原多項(xiàng)式在內(nèi) 的若干個(gè)因式之積為生成多項(xiàng)式的循環(huán)碼叫做本原 BCH碼。 BCH是能糾正

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

61、碼生成多項(xiàng)式 。 解：查最小多項(xiàng)式系數(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時(shí)： 2t-1=1， g(x) = LCM m1(x) = (x4+x+1) ；得到 (15,11)碼 。 （ 2） t =2時(shí)： 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時(shí)： 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時(shí)： 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連重復(fù)碼 。 3.5.5 二元非本原 BCH碼 本原 BCH碼在碼長

63、 n給定的條件下，通過增大監(jiān)督位數(shù) r 來提高糾錯(cuò)能力。這樣必然導(dǎo)致編碼效率 k/n降低。 如果在糾錯(cuò)能力不變（即 r不變）的條件下減小 n值，是 否有可能得到編碼效率較高且能糾多位錯(cuò)的編碼呢？非 本原的 BCH碼就是這樣的編碼。 因?yàn)榉潜驹囗?xiàng)式的共厄類 i與 n可約， m是它的循環(huán)級(jí) ， 根據(jù)數(shù)學(xué)理論， xm-1的因式分解中就能包含 共厄類 i 相 應(yīng)的那個(gè)非本原多項(xiàng)式。以此非本原多項(xiàng)式為生成多項(xiàng) 式，可得到的碼長為 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是非本原多項(xiàng)式 ， 因 15/3=5， 所以 m3(x)也是 x5-1的因式；以此為 生成多項(xiàng)式 ， 可得到 （ 5,1） 碼 。 m5(x)= x2+x+1也是非本原多項(xiàng)式 ， 因 15/5=3， 所以它是 x3-1的因式；作為生成多項(xiàng)式 ， 得到 （ 3,1） 碼 。 又如 ， n=28-1=255， x255-1中有一個(gè) 8次的非本原多項(xiàng)式 m15(x)=x8+x7+x6+x4+x2+x+1。 因?yàn)?n/i =255/15=17， 所以 x17-1中會(huì)包含這個(gè) 8次的因

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

66、k t d0 以 8進(jìn)數(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位錯(cuò)的非本 原 BCH碼生成多項(xiàng)式 。 解： 21不是 2m-1的數(shù) ， 但它是 26-1=63的因子 ， 與 63有公因 子 3。 由 187頁表查到相應(yīng)的 5類非本原多項(xiàng)式是： m3(x)= x6+x4+x2+x+1 m9(x)= x3+x2+1 m15(x)= x6+x5+x4+x2+1 （ 與 m3(x)對(duì)偶 ） m21(x)= x2+x+1 m27(x)= x3+x+1 （ 與 m9(x)對(duì)偶