ECC-BCH-编码-原理

1、University of Science and Technology of China2021/3/111 3.1 引言引言 BCH码是一类最重要的循环码，能纠正多个码是一类最重要的循环码，能纠正多个 随 机 错 误 ， 它 是随 机 错 误 ， 它 是 1 9 5 9 年 由年 由 B o s e 、 Chaudhuri及及Hocquenghem各自独立发各自独立发 现的二元线性循环码，人们用他们的名字字头现的二元线性循环码，人们用他们的名字字头 命名为命名为BCH码。码。 在前面的讨论中，我们所做的只是构造一个码，在前面的讨论中，我们所做的只是构造一个码， 然后计算它的最小距离，从而估

2、计出它的纠错然后计算它的最小距离，从而估计出它的纠错 能力，而在能力，而在BCH码中，我们将采用另外一种码中，我们将采用另外一种 方法：先说明我们希望它能纠错的个数，然后方法：先说明我们希望它能纠错的个数，然后 构造这种码。构造这种码。 University of Science and Technology of China2021/3/112 3.2 BCH码简述码简述 若循环码的生成多项式具有如下形式：若循环码的生成多项式具有如下形式： g(x)=LCMm1(x),m3(x),m2t-1(x) 其中其中LCM表示最小公倍式，表示最小公倍式，t为纠错个数，为纠错个数， mi(x)为素多项式

3、，则由此生成的循环码称为为素多项式，则由此生成的循环码称为 BCH码，其最小码距码，其最小码距 (d0称为称为 设计码距设计码距)，它能纠正，它能纠正t个随机独立差错。个随机独立差错。 BCH码的码长码的码长n=2m-1或是或是n=2m-1的因子的因子 12 0 tdd 本原本原BCH码码非本原非本原BCH码码 University of Science and Technology of China2021/3/113 举例说明举例说明 例例3.1: BCH(15,5)码，可纠正码，可纠正3个随机独立个随机独立 差错，即差错，即t=3 n=15=2m-1, so m=4 查不可约多项式表可得

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)=LCMm1(x),m3(x),m5(x) =(x4+x+1)(x4+x3+x2+x+1)(x2+x+1) = x10+x8+x5+x4+x2+x+1 713212 0 tdd University of Science and Technology of China2021/3/114 例例3.2: BCH(31,16)码，可纠正码，可纠正3个随机独立个随机独立 差错，即差错，即t=3

5、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)=LCMm1(x),m3(x),m5(x) = x15+x11+x10+x9+x8+x7+x5 +x3+x2+x+1 713212 0 tdd University of Science and Technology of China2021/3/115 部分不可约多项式表部分不可约多项式表 2阶阶17 3阶阶113

6、4阶阶123337507 5阶阶145375567 University of Science and Technology of China2021/3/116 n 31的本原的本原BCH码码 nktg(x) 74113 1511123 1572721 15532467 3126145 312123551 31163107657 311155423325 3167313365047 University of Science and Technology of China2021/3/117 部分非本原部分非本原BCH码码 nkdg(x) 1795727 2116343 211251663

7、2167126357 2149643215 231275343 25554102041 27931001001 27767007007 33673043 University of Science and Technology of China2021/3/118 3.3 有限域有限域 一个元素个数有限的域称为一个元素个数有限的域称为有限域有限域，或者，或者伽罗伽罗 华域华域(Galois field); 有限域中元素的个数为一个素数，记为有限域中元素的个数为一个素数，记为GF(p), 其中其中p为素数；为素数； 一个大于一个大于1的整数，如果它的正因数只有的整数，如果它的正因数只有1和它和它

8、 本身，就叫做本身，就叫做素数素数，否则就叫做，否则就叫做合数合数。 有限域中运算满足有限域中运算满足 交换律交换律:a+b=b+a, ab=b a 结合律结合律:(a+b)+c=a+(b+c),a(bc)=(ab) c 和分配律和分配律:a (b+c)=a b+a c University of Science and Technology of China2021/3/119 可以将可以将GF(p)延伸为一个含有延伸为一个含有pm个元素的域，个元素的域， 称为称为GF(p)的扩展域，表示为的扩展域，表示为GF(pm)，m是是 一个非零正整数。注意：一个非零正整数。注意：GF(p)是是GF(

9、pm)的的 子集。子集。 二进制域二进制域GF(2)是扩展域是扩展域GF(2m)的一个子域，的一个子域， 类似于实数域是复数域的一个子域一样。除了类似于实数域是复数域的一个子域一样。除了 数字数字0和和1之外，在扩展域中还有特殊的元素，之外，在扩展域中还有特殊的元素， 用一个新的符号用一个新的符号a表示。表示。GF(2m)中任何非中任何非0 元素都可由元素都可由a的幂次表示。的幂次表示。 University of Science and Technology of China2021/3/1110 有限元素的集合有限元素的集合GF(2m)，只能含有，只能含有2m个元个元 素，并且对乘法封闭，

10、其约束条件为：素，并且对乘法封闭，其约束条件为： 根据这个多项式限制条件，任何幂次等于或超根据这个多项式限制条件，任何幂次等于或超 过过2m-1的域元素都可降阶为下述幂次小于的域元素都可降阶为下述幂次小于 2m-1的元素：的元素： 这样，这样，GF(2m)的元素可表示为：的元素可表示为： 01 )12( m a 11)12()2( nnn aaaa mm , 0)2( 22210 m aaaaGF m University of Science and Technology of China2021/3/1111 扩展域扩展域GF(2m)中的加法中的加法 在在GF(2m)中，将每个非中，将每个

11、非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的取的取 值。值。 University of Science and T

12、echnology of China2021/3/1112 域域 元元 素素 基本元素基本元素 x0 x1x2 0000 a0100 a1010 a2001 a3110 a4011 a5111 a6101 a7100 多项式为多项式为f(x)=1+x+x3的的GF(8)的元素与的元素与 基本元素之间的映射基本元素之间的映射 University of Science and Technology of China2021/3/1113 有限域中两个元素的加法定义为两个多项式中有限域中两个元素的加法定义为两个多项式中 同幂次项系数进行模同幂次项系数进行模2加，即加，即 ai+aj=(ai,0+a

13、j,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，则该多项式是，则该多项式是 本原的。本原的。 University of Science and Technology of China2021/3/1114 例例3.3 本原多项式的辨别本原多项式的辨

14、别 (1) p1(x)=1+x+x4 (2) p2(x)=1+x+x2+x3+x4 分析分析: (1)通过验证这个幂次为通过验证这个幂次为m=4的多项式的多项式 是否能够整除是否能够整除 , 但不能整除但不能整除1n2时所建立的码长为时所建立的码长为n=q-1的的q进制进制BCH 码，称为码，称为RS码。当码。当q=2m(m1)，码元符号，码元符号 取自域取自域GF(2m)的二进制的二进制RS码可用来纠正突码可用来纠正突 发错误。发错误。 输入信息分为输入信息分为k*m比特一组，即每个符号有比特一组，即每个符号有 m比特，比特，k个符号形成一组。个符号形成一组。 University of S

15、cience and Technology of China2021/3/1145 一个可纠一个可纠t个符号错误的个符号错误的RS码，有如下参数码，有如下参数 码长：码长：n=2m-1 符号符号 或或 m(2m-1) bit 信息段：信息段：k 符号符号 或或 km bit 监督段：监督段：n-k=2t 符号符号 或或 m(n-k)=2mt bit 最小码距：最小码距：d=2t+1 符号符号 或或 md=m(2t+1) bit 例例3.8 试构造一个能纠试构造一个能纠3个错误符号，码长个错误符号，码长n=15,m=4的的RS码。码。 解：已知解：已知t=3,n=15,m=4, 所以有所以有 码距：码距：d=2t+1=7个符号个符号(28bit) 监督段：监督段：2t=6个符号个符号(24bit) 信息段：信息段：n-6=9个符号个符号(36bit) 码长：码长：n=15个符号个符号(60bit) 因此该码是因此该码是(15,9)RS码，也可看作是码，也可看作是(60,36)二进制码；二进制码； Univer