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