（精选幻灯片）第四章 BCH码-2.ppt

1、通信工程系移动通信教研室,信道编码,2,第四章 BCH码,4.1 BCH码概述 4.2 预备知识：有限域基础 4.3 BCH码的构造 4.4 BCH码的编码 4.5 BCH码的译码,3,4.3 BCH码的构造,BCH码的定义 BCH码的构造 BCH码的校验矩阵 BCH码的距离限*,4,4.3 BCH码的构造,BCH码的定义 对于二元域GF(2)及其扩域GF(2m)，设=i (i=1,2,2m-2)为GF(2m)上的非零元素，如果GF(2)上的多项式g(x)含有,2,d-1等d-1个连续根，则由g(x)生成的循环码称为BCH码。d称为BCH码的设计距离。 BCH码由生成多项式在GF(2m)上的根

2、定义 BCH码的最小距离或纠错能力是可设计的,说明,5,4.3 BCH码的构造,BCH码的定义 本原BCH码与非本原BCH码 如果g(x)的d-1个连续根中含有本原元，则称g(x)生成的BCH码为本原BCH码； 如果g(x)的d-1个连续根均为非本原元，则g(x)生成的BCH码称为非本原BCH码。,6,4.3 BCH码的构造,BCH码的定义 生成多项式与码长： 设Mi(x)和ei(i=1,2,d-1)分别表示d-1个连续根的最小多项式和元素的阶，则BCH码的生成多项式和码长分别为： g(x)=LCMM1(x),M2(x),Md-1(x) n=LCMe1,e2,ed-1,7,4.3 BCH码的构

3、造,BCH码的定义 生成多项式与码长： 设二元BCH码的设计纠错能力为t，则生成多项式g(x)含有,2,2t等2t个连续根。由于i和2i的最小多项式相同，因此二元BCH码的生成多项式为： g(x)=LCMM1(x),M3(x),M2t-1(x),8,4.3 BCH码的构造,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码的构造,BCH码的定义 生成多项式与码长： 定理：设=j为GF

4、(2m)的元素，为本原元，则以,2,2t为根的BCH码的码长为： n=(2m-1)/(2m-1, j) 特别地：当=时，码长n=2m-1,10,4.3 BCH码的构造,BCH码的构造 本原BCH码的构造步骤 1、根据码长n=2m-1确定m，查表找出m次本原多项式p(x)，构造扩域GF(2m) 2、取本原元，根据设计纠错能力t确定g(x)的根： ,2, 3,2t，查表找出根的最小多项式M1(x), M3(x), ,M2t-1(x) 3、计算上述最小多项式的最小公倍式，得到生成多项式g(x)。,11,4.3 BCH码的构造,BCH码的构造 本原BCH码的构造举例 以设计纠错能力t=1,2,3分别构

5、造码长n=15的本原BCH码。 1)、n=15，则m=4，取p(x)=x4+x+1，构造扩域GF(24)。 本原多项式查表,12,4.3 BCH码的构造,BCH码的构造 扩域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码的构造,BCH码的构造 本原BCH码的构造举例 2)、取GF(24)上的本原元 查表

6、获得扩域GF(24)上的共轭根系与最小多项式：,14,4.3 BCH码的构造,BCH码的构造 本原BCH码的构造举例 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码的构造,BCH码的构造-本原BCH码的构造举例 3)、计算BCH码的生成多项式g(x) g(x)=LCMM1(x)M3(x)M2t-

7、1(x) t=1：g(x)以 2为连续根g(x)=M1(x)=x4+x+1 t=2：g(x)以 2 3 4为连续根 g(x)=M1(x)M3(x)=x8+x7+x6+x4+1 t=3：g(x)以 2 3 4 5 6为连续根 g(x)=M1(x)M3(x)M5(x) =x10+x8+x5+x4+x2+x+1,16,4.3 BCH码的构造,BCH码的构造 非本原BCH码的构造步骤 1、确定满足n|(2m-1)的m的最小值，查表找出m次本原多项式p(x)，构造扩域GF(2m) 2、在GF(2m)中找一个n阶元=l，其中l可取(2m-1)/n，根据设计纠错能力t确定g(x)的根：l,2l, 2tl ，

8、查表找出根的最小多项式Ml(x),M3l(x), M(2t-1)l(x) 3、计算上述最小多项式的最小公倍式，得到生成多项式g(x),17,4.3 BCH码的构造,BCH码的构造 非本原BCH码的构造举例 以设计纠错能力t=3构造码长n=21的非本原BCH码。 1)、n=21，则：n2m-1 取m=6，n=21 | (26-1)=63 查表得p(x)=x6+x+1，构造扩域GF(26),18,4.3 BCH码的构造,BCH码的构造 非本原BCH码的构造举例 2)、GF(26)上的n=21阶非本原元63/21=3 当t=3时，g(x)以3 6 9 12 15 18为连续根 查表获得GF(26)上

9、根的最小多项式：,19,4.3 BCH码的构造,非本原BCH码的构造举例:扩域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码的构造,BCH码的构造 非本原BCH码的构造举例 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码的构造,BCH码的校验矩阵 设g(x)是(n,k,d) BCH码的生成多项式，并且g(x)以,2,2t为连续根 设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码的构造,BCH码的校验矩阵

11、由HCT = 0 可得：,H称为用生成多项式的根表示的校验矩阵,cn-1(i)n-1+cn-2(i)n-2+c1i+c0=0,23,4.3 BCH码的构造,BCH码的校验矩阵 由于i和2i属于一个共轭根系，因此校验矩阵H可简化为：,24,4.3 BCH码的构造,BCH码的校验矩阵 BCH码的校验矩阵H中的元素为扩域GF(2m)上的元素，每个元素都可以表示成一个m重的列向量，则H可表示为一个n列mt行的GF(2)上的矩阵。 该矩阵中只有n-k行是线性无关的，这n-k个线性无关的行向量即可构成BCH码的二进制表示的校验矩阵。 BCH码的校验矩阵也可以采用循环码中介绍的方法得到。,25,4.3 BCH码的构造,BCH码的距离限* 作为了解内容仅给出几个结论。 定理1(BCH限)：以,2,d-1为根的BCH码的实际最小距离dTruth至少为d。,26,4.3 BCH码的构造,BCH码的距离限* 定理2：码长为n=2m-1的本原BCH码，如果设计距离d=2h-1，则实际距离dTruth=d。 定理3 ：设计距离为d的二元BCH码，其实际距离dTruth 2d。,27,4.3 BCH码的构造,课下作业： 1、已知本原多项式p(x)=x4+x3+1，构造码长n=15、纠错能力t=2的本原BCH码，给出生成多项式g(x)、校验位个数r、信息位个数k、编码效率R及扩域元素表示的校验矩