（精選幻燈片）第四章 BCH碼-2.ppt

1、通信工程系移動通信教研室,信道編碼,2,第四章 BCH碼,4.1 BCH碼概述 4.2 預(yù)備知識：有限域基礎(chǔ) 4.3 BCH碼的構(gòu)造 4.4 BCH碼的編碼 4.5 BCH碼的譯碼,3,4.3 BCH碼的構(gòu)造,BCH碼的定義 BCH碼的構(gòu)造 BCH碼的校驗矩陣 BCH碼的距離限*,4,4.3 BCH碼的構(gòu)造,BCH碼的定義 對于二元域GF(2)及其擴域GF(2m)，設(shè)=i (i=1,2,2m-2)為GF(2m)上的非零元素，如果GF(2)上的多項式g(x)含有,2,d-1等d-1個連續(xù)根，則由g(x)生成的循環(huán)碼稱為BCH碼。d稱為BCH碼的設(shè)計距離。 BCH碼由生成多項式在GF(2m)上的根

2、定義 BCH碼的最小距離或糾錯能力是可設(shè)計的,說明,5,4.3 BCH碼的構(gòu)造,BCH碼的定義 本原BCH碼與非本原BCH碼 如果g(x)的d-1個連續(xù)根中含有本原元，則稱g(x)生成的BCH碼為本原BCH碼； 如果g(x)的d-1個連續(xù)根均為非本原元，則g(x)生成的BCH碼稱為非本原BCH碼。,6,4.3 BCH碼的構(gòu)造,BCH碼的定義 生成多項式與碼長： 設(shè)Mi(x)和ei(i=1,2,d-1)分別表示d-1個連續(xù)根的最小多項式和元素的階，則BCH碼的生成多項式和碼長分別為： g(x)=LCMM1(x),M2(x),Md-1(x) n=LCMe1,e2,ed-1,7,4.3 BCH碼的構(gòu)

3、造,BCH碼的定義 生成多項式與碼長： 設(shè)二元BCH碼的設(shè)計糾錯能力為t，則生成多項式g(x)含有,2,2t等2t個連續(xù)根。由于i和2i的最小多項式相同，因此二元BCH碼的生成多項式為： g(x)=LCMM1(x),M3(x),M2t-1(x),8,4.3 BCH碼的構(gòu)造,BCH碼的定義 生成多項式與碼長： GF(2m)上非零元素的階均為2m-1的因子，因此BCH碼的碼長n一定為2m-1的因子。 即：n|2m-1 本原BCH碼的碼長n一定等于2m-1。 非本原BCH碼的碼長n一定小于2m-1且為2m-1的因子。,9,4.3 BCH碼的構(gòu)造,BCH碼的定義 生成多項式與碼長： 定理：設(shè)=j為GF

4、(2m)的元素，為本原元，則以,2,2t為根的BCH碼的碼長為： n=(2m-1)/(2m-1, j) 特別地：當(dāng)=時，碼長n=2m-1,10,4.3 BCH碼的構(gòu)造,BCH碼的構(gòu)造 本原BCH碼的構(gòu)造步驟 1、根據(jù)碼長n=2m-1確定m，查表找出m次本原多項式p(x)，構(gòu)造擴域GF(2m) 2、取本原元，根據(jù)設(shè)計糾錯能力t確定g(x)的根： ,2, 3,2t，查表找出根的最小多項式M1(x), M3(x), ,M2t-1(x) 3、計算上述最小多項式的最小公倍式，得到生成多項式g(x)。,11,4.3 BCH碼的構(gòu)造,BCH碼的構(gòu)造 本原BCH碼的構(gòu)造舉例 以設(shè)計糾錯能力t=1,2,3分別構(gòu)

5、造碼長n=15的本原BCH碼。 1)、n=15，則m=4，取p(x)=x4+x+1，構(gòu)造擴域GF(24)。 本原多項式查表,12,4.3 BCH碼的構(gòu)造,BCH碼的構(gòu)造 擴域GF(24)及非零元素的階： 元素 多項式 階 元素 多項式 階 0 0 7 3+1 15 1 1 1 8 2+1 15 15 9 3+ 5 2 2 15 10 2+1 3 3 3 5 11 3+2+ 15 4 +1 15 12 3+2+1 5 5 2+ 3 13 3+2+1 15 6 3+2 5 14 3+1 15,13,4.3 BCH碼的構(gòu)造,BCH碼的構(gòu)造 本原BCH碼的構(gòu)造舉例 2)、取GF(24)上的本原元 查表

6、獲得擴域GF(24)上的共軛根系與最小多項式：,14,4.3 BCH碼的構(gòu)造,BCH碼的構(gòu)造 本原BCH碼的構(gòu)造舉例 2)、取GF(24)上的本原元 擴域GF(24)上的共軛根系與最小多項式： 共軛根系 最小多項式 0=1 M0(x) = x+1 ,2,4,8 M1(x) = x4+x+1 3,6,9,12 M3(x) = x4+x3+x2+x+1 5,10 M5(x) = x2+x+1 7,11,13,14 M7(x) = x4+x3+1,15,4.3 BCH碼的構(gòu)造,BCH碼的構(gòu)造-本原BCH碼的構(gòu)造舉例 3)、計算BCH碼的生成多項式g(x) g(x)=LCMM1(x)M3(x)M2t-

7、1(x) t=1：g(x)以 2為連續(xù)根g(x)=M1(x)=x4+x+1 t=2：g(x)以 2 3 4為連續(xù)根 g(x)=M1(x)M3(x)=x8+x7+x6+x4+1 t=3：g(x)以 2 3 4 5 6為連續(xù)根 g(x)=M1(x)M3(x)M5(x) =x10+x8+x5+x4+x2+x+1,16,4.3 BCH碼的構(gòu)造,BCH碼的構(gòu)造 非本原BCH碼的構(gòu)造步驟 1、確定滿足n|(2m-1)的m的最小值，查表找出m次本原多項式p(x)，構(gòu)造擴域GF(2m) 2、在GF(2m)中找一個n階元=l，其中l(wèi)可取(2m-1)/n，根據(jù)設(shè)計糾錯能力t確定g(x)的根：l,2l, 2tl ，

8、查表找出根的最小多項式Ml(x),M3l(x), M(2t-1)l(x) 3、計算上述最小多項式的最小公倍式，得到生成多項式g(x),17,4.3 BCH碼的構(gòu)造,BCH碼的構(gòu)造 非本原BCH碼的構(gòu)造舉例 以設(shè)計糾錯能力t=3構(gòu)造碼長n=21的非本原BCH碼。 1)、n=21，則：n2m-1 取m=6，n=21 | (26-1)=63 查表得p(x)=x6+x+1，構(gòu)造擴域GF(26),18,4.3 BCH碼的構(gòu)造,BCH碼的構(gòu)造 非本原BCH碼的構(gòu)造舉例 2)、GF(26)上的n=21階非本原元63/21=3 當(dāng)t=3時，g(x)以3 6 9 12 15 18為連續(xù)根 查表獲得GF(26)上

9、根的最小多項式：,19,4.3 BCH碼的構(gòu)造,非本原BCH碼的構(gòu)造舉例:擴域GF(26)上的部分元素及其最小多項式： 根元素 最小多項式 M1(x) = x6+x+1 3 M3(x) = x6+x4+x2+x+1 5 M5(x) = x6+x5+x2+x+1 7 M7(x) = x6+x3+1 9 M9(x) = x3+x2+1 11 M11(x) = x6+x5+x3+x2+1 13 M13(x) = x6+x4+x3+x+1 15 M15(x) = x6+x5+x4+x2+1 21 M21(x) = x2+x+1,20,4.3 BCH碼的構(gòu)造,BCH碼的構(gòu)造 非本原BCH碼的構(gòu)造舉例 3

10、)、計算BCH碼的生成多項式g(x) g(x)=M3(x)M9(x)M15(x) =x15+x13+x11+x10+x9+x8 +x7+x5+x4+x3+x2+x+1,21,4.3 BCH碼的構(gòu)造,BCH碼的校驗矩陣 設(shè)g(x)是(n,k,d) BCH碼的生成多項式，并且g(x)以,2,2t為連續(xù)根 設(shè)C(x)=cn-1xn-1+cn-2xn-2+c1x+c0 為該碼的碼多項式 則有：C(x)=m(x)g(x)， 因此，,2,2t也是C(x)的根 即： C(i)= cn-1(i)n-1+cn-2(i)n-2+c1i+c0=0 i=1,2,2t,22,4.3 BCH碼的構(gòu)造,BCH碼的校驗矩陣

11、由HCT = 0 可得：,H稱為用生成多項式的根表示的校驗矩陣,cn-1(i)n-1+cn-2(i)n-2+c1i+c0=0,23,4.3 BCH碼的構(gòu)造,BCH碼的校驗矩陣 由于i和2i屬于一個共軛根系，因此校驗矩陣H可簡化為：,24,4.3 BCH碼的構(gòu)造,BCH碼的校驗矩陣 BCH碼的校驗矩陣H中的元素為擴域GF(2m)上的元素，每個元素都可以表示成一個m重的列向量，則H可表示為一個n列mt行的GF(2)上的矩陣。 該矩陣中只有n-k行是線性無關(guān)的，這n-k個線性無關(guān)的行向量即可構(gòu)成BCH碼的二進制表示的校驗矩陣。 BCH碼的校驗矩陣也可以采用循環(huán)碼中介紹的方法得到。,25,4.3 BCH碼的構(gòu)造,BCH碼的距離限* 作為了解內(nèi)容僅給出幾個結(jié)論。 定理1(BCH限)：以,2,d-1為根的BCH碼的實際最小距離dTruth至少為d。,26,4.3 BCH碼的構(gòu)造,BCH碼的距離限* 定理2：碼長為n=2m-1的本原BCH碼，如果設(shè)計距離d=2h-1，則實際距離dTruth=d。 定理3 ：設(shè)計距離為d的二元BCH碼，其實際距離dTruth 2d。,27,4.3 BCH碼的構(gòu)造,課下作業(yè)： 1、已知本原多項式p(x)=x4+x3+1，構(gòu)造碼長n=15、糾錯能力t=2的本原BCH碼，給出生成多項式g(x)、校驗位個數(shù)r、信息位個數(shù)k、編碼效率R及擴域元素表示的校驗矩