本章内容 ·有限域 ·BCH码的编码 ·BCH码的译码 ·戈雷(Golay)码 ·Reed-Solomon码 2013/4/11 2
2013/4/11 2 本章内容 有限域 BCH码的编码 BCH码的译码 戈雷(Golay)码 Reed-Solomon码
3.1引言 ·BCH码是一类最重要的循环码，能纠正多个随机错误，它是 1959年由Bose、Chaudhuri及Hocquenghem各自独立发现的 二元线性循环码，人们用他们的名字字头命名为BCH码。 。3 在前面的讨论中，我们所做的只是构造一个码，然后计算它 的最小距离，从而估计出它的纠错能力，而在BCH码中，我 们将采用另外一种方法：先说明我们希望它能纠错的个数， 然后构造这种码。 2013/4/11
2013/4/11 3 3.1 引言 • BCH码是一类最重要的循环码，能纠正多个随机错误，它是 1959年由Bose、Chaudhuri及Hocquenghem各自独立发现的 二元线性循环码，人们用他们的名字字头命名为BCH码。 • 在前面的讨论中，我们所做的只是构造一个码，然后计算它 的最小距离，从而估计出它的纠错能力，而在BCH码中，我 们将采用另外一种方法：先说明我们希望它能纠错的个数， 然后构造这种码
3.2BCH码简述 ·若循环码的生成多项式具有如下形式： g()=LCM[m1(),m3(X),m2-1(X)] 其中LCM表示最小公倍式，为纠错个数，m(x)为素多项式， 则由此生成的循环码称为BCH码，其最小码距d≥d=2t+1 (,称为设计码距)，它能纠正t个随机独立差错。 ·BCH码的码长n=2m-1或是n=2m-1的因子 本原BCH码 非本原BCH码 2013/4/11 4
2013/4/11 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码
·例3.1：BCH(15,5)码，可纠正3个随机独立差错，即仁3 d≥d,=2t+1=7 n=15=2m-1,s0m=4 查不可约多项式表可得 m1(x)=(23)g=010011=x4+x+1 m3(x)=(37)g=011111=x4+x3+x2+x+1 m5(x)=(07)8=000111=x2+x+1 这样g(x)=LCM[m1(x),m3(),ms(x】 =(x4+x+1)(x4+x3+x2+x+1)(x2+x+1) =x10+x8+x5+x4+x2+X+1 2013/4/11 5
2013/4/11 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
>例3.2：BCH(31,16)码，可纠正3个随机独立差错，即=3 d2d=2t+1=7 n=31=2m-1,s0m=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(),m3(x),ms(x川 =x15+x11+x10+x9+x8+x7+x5+x3+x2+x+1 2013/4/11 6
2013/4/11 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
·部分不可约多项式表 2阶 1 7 3阶 1 13 4阶 1 23 3 37 5 07 5阶 1 45 3 75 5 67 2013/4/11 7
2013/4/11 7 • 部分不可约多项式表 2阶 1 7 3阶 1 13 4阶 1 23 3 37 5 07 5阶 1 45 3 75 5 67
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
2013/4/11 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
部分非本原BCH码 m 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
2013/4/11 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
3.3有限域 ·一个元素个数有限的域称为有限域，或者伽罗华域(Galois field); ·有限域中元素的个数为一个素数，记为GF(p),其中p为素数； 一个大于1的整数，如果它的正因数只有1和它本身，就叫做 素数，否则就叫做合数。 ·有限域中运算满足 一交换律：a+b=b+a,ab=b"a -结合律：(a+b)+c=a+(b+c),a(bc)=(ab)c -和分配律：a·(b+c)=ab+a·c 2013/4/11 10
2013/4/11 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
·可以将GF(p)延伸为一个含有pm个元素的域，称为GF(p)的扩展域，表示 为GF(pm),m是一个非零正整数。注意：GF(p)是GF(pm)的子集。 二进制域GF(2)是扩展域GF(2m)的一个子域，类似于实数域是复数域的一 个子域一样。除了数字0和1之外，在扩展域中还有特殊的元素，用一个 新的符号a表示。GF(2m)中任何非0元素都可由a的幂次表示。 ·有限元素的集合GF2m),只能含有2m个元素，并且对乘法封闭，其约束 条件为：a2m-10+1=0 ·根据这个多项式限制条件，任何幂次等于或超过2m1的域元素都可降阶为 下述幂次小于2m-1的元素： a2+m）=a2m-1a+l=a2+ ·这样，GF(2m的元素可表示为： GF(2m)={0,a°，a,a2,…,a2m-2} 11
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个元素，并且对乘法封闭，其约束 条件为： • 根据这个多项式限制条件，任何幂次等于或超过2m-1的域元素都可降阶为 下述幂次小于2m-1的元素： • 这样，GF(2m)的元素可表示为： 1 0 (2 1) + = − m a (2 + ) (2 −1) +1 +1 = = n n n a a a a m m (2 ) {0, , , , , } 0 1 2 2 −2 = m GF a a a a m