BCH码简介

BCH码是一类最重要的循环码,能纠正多个随机错误,它是1959年由Bose、Chaudhuri及Hocquenghem各自独立发现的二元线性循环码,人们用他们的名字字头命名为BCH码。在前面的讨论中,我们所做的只是构造一个码,然后计算它的最小距离,从而估计出它的纠错能力,而在BCH码中,我们将采用另外一种方法:先说明我们希望它能纠错的个数,然后构造这种码。
展开查看详情

1. 第三章 BCH码 2013/4/11 1

2. 本章内容  有限域  BCH码的编码  BCH码的译码  戈雷(Golay)码  Reed-Solomon码 2013/4/11 2

3. 3.1 引言 • BCH码是一类最重要的循环码,能纠正多个随机错误,它是 1959年由Bose、Chaudhuri及Hocquenghem各自独立发现的 二元线性循环码,人们用他们的名字字头命名为BCH码。 • 在前面的讨论中,我们所做的只是构造一个码,然后计算它 的最小距离,从而估计出它的纠错能力,而在BCH码中,我 们将采用另外一种方法:先说明我们希望它能纠错的个数, 然后构造这种码。 2013/4/11 3

4. 3.2 BCH码简述 • 若循环码的生成多项式具有如下形式: g(x)=LCM[m1(x),m3(x),…,m2t-1(x)] 其中LCM表示最小公倍式,t为纠错个数,mi(x)为素多项式, 则由此生成的循环码称为BCH码,其最小码距d≥d0=2t+1 (d0称为设计码距),它能纠正t个随机独立差错。 • BCH码的码长n=2m-1或是n=2m-1的因子 本原BCH码 非本原BCH码 2013/4/11 4

5.• 例3.1: BCH(15,5)码,可纠正3个随机独立差错,即t=3 d ≥ d0 = 2t+1 = 7 n=15=2m-1, so m=4 查不可约多项式表可得 m1(x)=(23)8=010011=x4+x+1 m3(x)=(37)8=011111=x4+x3+x2+x+1 m5(x)=(07)8=000111=x2+x+1 这样 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 2013/4/11 5

6. 例3.2: BCH(31,16)码,可纠正3个随机独立差错,即t=3 d≥d0=2t+1=7 n=31=2m-1, so m=5 查不可约多项式表可得 m1(x)=(45)8=100101=x5+x2+1 m3(x)=(75)8=111101=x5+x4+x3+x2+1 m5(x)=(67)8=110111=x5+x4+x2+x+1 这样 g(x)=LCM[m1(x),m3(x),m5(x)] = x15+x11+x10+x9+x8+x7+x5+x3+x2+x+1 2013/4/11 6

7.• 部分不可约多项式表 2阶 1 7 3阶 1 13 4阶 1 23 3 37 5 07 5阶 1 45 3 75 5 67 2013/4/11 7

8. n≤ 31的本原BCH码 n k t g(x) 7 4 1 13 15 11 1 23 15 7 2 721 15 5 3 2467 31 26 1 45 31 21 2 3551 31 16 3 107657 31 11 5 5423325 31 6 7 313365047 2013/4/11 8

9. 部分非本原BCH码 n k d g(x) 17 9 5 727 21 16 3 43 21 12 5 1663 21 6 7 126357 21 4 9 643215 23 12 7 5343 25 5 5 4102041 27 9 3 1001001 27 7 6 7007007 33 6 7 3043 2013/4/11 9

10. 3.3 有限域 • 一个元素个数有限的域称为有限域,或者伽罗华域(Galois field); • 有限域中元素的个数为一个素数,记为GF(p),其中p为素数; • 一个大于1的整数,如果它的正因数只有1和它本身,就叫做 素数,否则就叫做合数。 • 有限域中运算满足 – 交换律:a+b=b+a, a·b=b ·a – 结合律:(a+b)+c=a+(b+c),a·(b·c)=(a·b) ·c – 和分配律:a ·(b+c)=a ·b+a ·c 2013/4/11 10

11.• 可以将GF(p)延伸为一个含有pm个元素的域,称为GF(p)的扩展域,表示 为GF(pm),m是一个非零正整数。注意:GF(p)是GF(pm)的子集。 • 二进制域GF(2)是扩展域GF(2m)的一个子域,类似于实数域是复数域的一 个子域一样。除了数字0和1之外,在扩展域中还有特殊的元素,用一个 新的符号a表示。GF(2m)中任何非0元素都可由a的幂次表示。 • 有限元素的集合GF(2m),只能含有2m个元素,并且对乘法封闭,其约束 ( 2 m −1) 条件为: a +1 = 0 • 根据这个多项式限制条件,任何幂次等于或超过2m-1的域元素都可降阶为 下述幂次小于2m-1的元素: ( 2m + n ) ( 2 m −1) n +1 n +1 a =a a =a • 这样,GF(2m)的元素可表示为: 2m − 2 GF ( 2 ) = {0, a , a , a ,, a m 0 1 2 } 11

12. 扩展域GF(2m)中的加法 • 在GF(2m)中,将每个非0元素用多项式ai(x)表示,其系数至少 有一个不为0。对于i=0,1, 2,…,2m-2,有: ai = ai(x) = ai,0+ai,1x+ai,2x2+…+ai,m-1xm-1 • 考虑m=3,有限域表示为GF(23),下表为上式描述的基本元素 {x0,x1,x2}映射为7个元素{ai}和一个0元素。表中的各行是二进 制数字序列,代表上式中的系数ai,0、ai,1、ai,2的取值。 2013/4/11 12

13. 基本元素 x0 x1 x2 0 0 0 0 a0 1 0 0 域 a1 0 1 0 元 a2 0 0 1 素 a3 1 1 0 a4 0 1 1 a5 1 1 1 a6 1 0 1 a7 1 0 0 多项式为f(x)=1+x+x3的GF(8)的元素与基本元素之间的映射 2013/4/11 13

14.• 有限域中两个元素的加法定义为两个多项式中同幂次项系数 进行模2加,即 ai+aj=(ai,0+aj,0)+ (ai,1+aj,1)x+… +(ai,m-1+aj,m-1)xm-1 • 有限域的本原多项式:因为这些函数用来定义有限域GF(2m)。 一个多项式是本原多项式的充要条件:一个m阶的不可约多项 式f(x),如果f(x)整除xn+1的最小正整数n满足n=2m-1,则该多 项式是本原的。 • 例3.3 本原多项式的辨别 (1) p1(x)=1+x+x4 (2) p2(x)=1+x+x2+x3+x4 分析: (1)通过验证这个幂次为m=4的多项式是否能够整除 xn+1,但不能整 除1≤n<15范围内的xn+1,就可以确定它是否为本原多项式。经反复计算, p1(x)是本原多项式,p2(x)不是,因为它能整除x5+1。 2013/4/11 14

15. 部分本原多项式 m m 3 1+x+x3 11 1+x2+x11 4 1+x+x4 12 1+x+x4+x6+x12 5 1+x2+x5 13 1+x+x3+x4+x13 6 1+x+x6 14 1+x+x6+x10+x14 7 1+x3+x7 15 1+x+x15 8 1+x2+x3+x4+x8 16 1+x+x3+x12+x16 9 1+x4+x9 17 1+x3+x17 10 1+x3+x10 18 1+x7+x18 2013/4/11 15

16. 考虑一个本原多项式定义的有限域的例子 • 选择p(x)=1+x+x3,多项式的幂次为m=3,所以由p(x)所定义 的域中包含了2m=23=8个元素。求解p(x)的根就是指找到x 使p(x)=0。我们所熟悉的二进制数0和1不能满足,因为 p(1)=1,p(0)=1 (运用模2运算)。由基本代数学理论我们知 道,对于幂次为m的多项式必然有m个根。对于这个例子, p(x)=0有3个根,由于这3个根不可能位于与p(x)系数相同 的有限域中,而是位于扩展域GF(23)中。用扩展域的元素 a来定义多项式p(x)的根,可写成如下形式:p(a)=0 2013/4/11 16

17. 即 1+a+a3=0 a3=1+a 这意味着a3可以表示为更低阶a项的加权和。 类似地有: a4=a*a3=a*(1+a)=a+a2 a5=a*a4=a*(a+a2)=a2+a3=1+a+a2 a6=a*a5=a*(1+a+a2)=a+a2+a3=1+a2 a7=a*a6=a*(1+a2)=a+a3=1=a0 所以,有限域GF(23)的8个元素为 {0,a0,a1,a2,a3,a4,a5,a6} 2013/4/11 17

18.• 这8个元素中哪些是p(x)=0的3个根呢?我们可通过枚举 找到! p(a0)=1, a0不是 p(a1)=1+a+a3=0, a1是 p(a2)=1+a2+a6=1+a0=0, a2是 p(a3)=1+a3+a9=1+a3+a2=1+a5=a4, a3不是 p(a4)=1+a4+a12=1+a4+a5=1+a0=0, a4是 同理可计算p(a5)、p(a6)都不等于0,所以p(x)=1+x+x3的 3个根是a, a2, a4 2013/4/11 18

19. p(x)=1+x+x3, GF(8)加法运算表 + a0 a1 a2 a3 a4 a5 a6 a0 0 a3 a6 a1 a5 a4 a2 a1 a3 0 a4 a0 a2 a6 a5 a2 a6 a4 0 a5 a1 a3 a0 a3 a1 a0 a5 0 a6 a2 a4 a4 a5 a2 a1 a6 0 a0 a3 a5 a4 a6 a3 a2 a0 0 a1 a6 a2 a5 a0 a4 a3 a1 0 2013/4/11 19

20. p(x)=1+x+x3, GF(8)乘法运算表 × a0 a1 a2 a3 a4 a5 a6 a0 a0 a1 a2 a3 a4 a5 a6 a1 a1 a2 a3 a4 a5 a6 a0 a2 a2 a3 a4 a5 a6 a0 a1 a3 a3 a4 a5 a6 a0 a1 a2 a4 a4 a5 a6 a0 a1 a2 a3 a5 a5 a6 a0 a1 a2 a3 a4 a6 a6 a0 a1 a2 a3 a4 a5 2013/4/11 20

21.• 如果GF(p)上的所有元素(除0外)都可表示为某元素a的幂, 则a称为GF(p)上的本原元。 • 例3.4 考虑GF(5),因为p=5是个素数,模算数可以进行。 考虑该域上的元素2, 20=1(mod 5)=1, 21=2(mod 5)=2 22=4(mod 5)=4, 23=8(mod 5)=3 因此,所有GF(5)上的非零元素,即{1,2,3,4}都可以表示成 2的幂,故2是GF(5)上的本原元;大家可以验证,3也是 GF(5)上的本原元。 2013/4/11 21

22.• GF(pm)中,在模p(x)运算下的扩域上,x所表示的元素是本原 元。 • 例如: 用本原多项式p(x)=1+x+x3 来构造GF(8),设GF(8)上的 本原元为a, 通过将a的幂模p(a)得到GF(8)上的所有元素。 a的幂 GF(8)上的元素 a0 1 a1 a a2 a2 a3 a+1 a4 a2+a a5 a2+a+1 a6 a2+1 2013/4/11 22

23.• 定 理 : 设 b1,b2,…,bp-1 为 GF(p) 上 的 非 零 域 元 素 , 则 xp-1+1 =(x+b1)(x+b2)…(x+bp-1) • 从循环码知识我们知道,为了找到分组长度为n的循环码的 生成多项式,首先分解xn+1,因此xn+1可以表示为多个因子的 乘积,即 xn+1=f1(x)f2(x)…fw(x) • 在扩展域GF(pm)中,n=pm-1 2013/4/11 23

24.• 例3.5 考虑GF(2)和它的扩展域GF(8)。这里p=2,m=3,对x7+1 进行分解 x7+1=(x+1)(x3+x+1)(x3+x2+1) 同时我们知道,GF(8)中的非零元素为1, a , a+1, a2, a2+1, a2+a, a2+a+1,因此我们可以写为 x7+1=(x+1)(x+a)(x+a+1)(x+a2)(x+a2+1)(x+a2+a)(x+a2+a+1) =(x+1)[(x+a)(x+a2)(x+a2+a)][(x+a+1)(x+a2+1)(x+a2+a+1)] 而在GF(8)上,有 x3+x+1= (x+a)(x+a2)(x+a2+a) x3+x2+1=(x+a+1)(x+a2+1)(x+a2+a+1) 2013/4/11 24

25. 元素用a的幂 极小多项式fi(x) 对应的根 表示 x+1 1 a0 x3+x+1 a,a2和a2+a a1,a2,a4 x3+x2+1 a+1,a2+1和a2+a+1 a3,a6,a5 2013/4/11 25

26. 3.4 BCH码的编码 • 对一个分组长度n=pm-1、确定可纠t个错误的BCH码的生成 多项式的步骤: 1. 选取一个次数为m的素多项式并构造GF(pm) 2. 求ai,i=0,1,2,…n-2的极小多项式fi(x) 3. 可纠t个错误的码的生成多项式为 g(x)=LCM[f1(x),f2(x),…,f2t(x)] 用这种方法设计的码至少能纠t个错误,在很多情况下,这些 码能纠多于t个错误!!因此d=2t+1称为码的设计距离,其 最小距离d*≥ 2t+1。注意:一旦确定了n和t,我们便可以确 定BCH码的生成多项式。 2013/4/11 26

27.• 例3.6 考虑GF(2)上的本原多项式p(a)=a4+a+1,我们将以此来构造 GF(16),设a为本原元。GF(16)上以a的幂表示形式的元素及它们对 应的极小多项式为: a的幂 GF(16)的元素 极小多项式 a0 1 x+1 a1 a x4+x+1 a2 a2 x4+x+1 a3 a3 x4+x3+x2+x+1 a4 a+1 x4+x+1 a5 a2+a x2+x+1 a6 a3+a2 x4+x3+x2+x+1 a7 a3+a+1 x4+x3+1 a8 a2+1 x4+x+1 a9 a3+a x4+x3+x2+x+1 a10 a2+a+1 x2+x+1 a11 a3+a2+a x4+x3+1 a12 a3+a2+a+1 x4+x3+x2+x+1 a13 a3+a2+1 x4+x3+1 a14 2013/4/11 a3+1 x4+x3+1 27

28.• 我们希望确定纠单错的BCH码的生成多项式,即t=1且n=15。 由前面公式可知,一个BCH码的生成多项式由 LCM[f1(x),f2(x),…,f2t(x)]给出,利用前面的表我们可获得极 小多项式f1(x)和f2(x),于是有: g(x)=LCM[f1(x),f2(x)] =LCM[(x4+x+1), (x4+x+1)] =x4+x+1 因为deg g(x)=n-k,可得n-k=4,所以k=11,于是我们得到纠单 一错误的BCH(15,11)码的生成多项式。该码的设计距离为 d=2t+1=3,可以计算该码的实际最小距离d*也是3。 2013/4/11 28

29.如果希望纠2个错误,且n=15。则其生成多项式为 g(x)=LCM[f1(x),f2(x),f3(x),f4(x)] =LCM[(x4+x+1),(x4+x+1), (x4+x3+x2+x+1),(x4+x+1)] = (x4+x+1)(x4+x3+x2+x+1) = x8+x7+x6+x4+1 因为deg g(x)=n-k=8,所以k=7,于是我们得到纠2个错误的 BCH(15,7)码的生成多项式。该码的设计距离为d=2t+1=5, 可以计算该码的实际最小距离d*也是5。 2013/4/11 29