《bch编码》由会员分享，可在线阅读，更多相关《bch编码（48页珍藏版）》请在金锄头文库上搜索。
1、2019/8/23,1,编 码 理 论 Coding Theory,周武旸 中国科学技术大学 个人通信与扩频实验室,2019/8/23,2,第三章 BCH码,3.1 引言 3.2 BCH码简述 3.3 有限域 3.4 BCH码的编码 3.5 BCH码的译码 3.6 戈雷(Golay)码 3.7 Reed-Solomon码,2019/8/23,3,3.1 引言,BCH码是一类最重要的循环码，能纠正多个随机错误，它是1959年由Bose、Chaudhuri及Hocquenghem各自独立发现的二元线性循环码，人们用他们的名字字头命名为BCH码。 在前面的讨论中，我们所做的只是构造一个码，然后计算它
2、的最小距离，从而估计出它的纠错能力，而在BCH码中，我们将采用另外一种方法：先说明我们希望它能纠错的个数，然后构造这种码。,2019/8/23,4,3.2 BCH码简述,若循环码的生成多项式具有如下形式： g(x)=LCMm1(x),m3(x),m2t-1(x) 其中LCM表示最小公倍式，t为纠错个数，mi(x)为素多项式，则由此生成的循环码称为BCH码，其最小码距 (d0称为设计码距)，它能纠正t个随机独立差错。 BCH码的码长n=2m-1或是n=2m-1的因子,本原BCH码,非本原BCH码,2019/8/23,5,举例说明,例3.1: BCH(15,5)码，可纠正3个随机独立差错，即t=3
3、 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)=LCMm1(x),m3(x),m5(x) =(x4+x+1)(x4+x3+x2+x+1)(x2+x+1) = x10+x8+x5+x4+x2+x+1,2019/8/23,6,例3.2: BCH(31,16)码，可纠正3个随机独立差错，即t=3 n=31=2m-1, so m=5 查不可约多项式表可得 m1(x)=(45)8=100101=x5+x2+1
4、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,2019/8/23,7,部分不可约多项式表,2019/8/23,8,n 31的本原BCH码,2019/8/23,9,部分非本原BCH码,2019/8/23,10,3.3 有限域,一个元素个数有限的域称为有限域，或者伽罗华域(Galois field); 有限域中元素的个数为一个素数，记为GF(p),其中p为素数； 一个大于1的整数，如果
5、它的正因数只有1和它本身，就叫做素数，否则就叫做合数。 有限域中运算满足 交换律:a+b=b+a, ab=b a 结合律:(a+b)+c=a+(b+c),a(bc)=(ab) c 和分配律:a (b+c)=a b+a c,2019/8/23,11,可以将GF(p)延伸为一个含有pm个元素的域，称为GF(p)的扩展域，表示为GF(pm)，m是一个非零正整数。注意：GF(p)是GF(pm)的子集。 二进制域GF(2)是扩展域GF(2m)的一个子域，类似于实数域是复数域的一个子域一样。除了数字0和1之外，在扩展域中还有特殊的元素，用一个新的符号a表示。GF(2m)中任何非0元素都可由a的幂次表示。,
6、2019/8/23,12,有限元素的集合GF(2m)，只能含有2m个元素，并且对乘法封闭，其约束条件为： 根据这个多项式限制条件，任何幂次等于或超过2m-1的域元素都可降阶为下述幂次小于2m-1的元素： 这样，GF(2m)的元素可表示为：,2019/8/23,13,扩展域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
7、元素。表中的各行是二进制数字序列，代表上式中的系数ai,0、ai,1、ai,2的取值。,2019/8/23,14,多项式为f(x)=1+x+x3的GF(8)的元素与基本元素之间的映射,2019/8/23,15,有限域中两个元素的加法定义为两个多项式中同幂次项系数进行模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，则该多项式是本原的。,2019
8、/8/23,16,例3.3 本原多项式的辨别 (1) p1(x)=1+x+x4 (2) p2(x)=1+x+x2+x3+x4 分析: (1)通过验证这个幂次为m=4的多项式是否能够整除 ,但不能整除1n15范围内的xn+1，就可以确定它是否为本原多项式。经反复计算，p1(x)是本原多项式，p2(x)不是，因为它能整除x5+1。,2019/8/23,17,部分本原多项式,2019/8/23,18,考虑一个本原多项式定义的有限域的例子,选择p(x)=1+x+x3，多项式的幂次为m=3,所以由p(x)所定义的域中包含了2m=23=8个元素。求解p(x)的根就是指找到x使p(x)=0。我们所熟悉的二进
9、制数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,2019/8/23,19,即 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+a
10、2 a7=a*a6=a*(1+a2)=a+a3=1=a0 所以，有限域GF(23)的8个元素为 0,a0,a1,a2,a3,a4,a5,a6,2019/8/23,20,这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,201
11、9/8/23,21,p(x)=1+x+x3, GF(8)加法运算表,2019/8/23,22,p(x)=1+x+x3, GF(8)乘法运算表,2019/8/23,23,如果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)上的本原元。
12、,2019/8/23,24,GF(pm)中，在模p(x)运算下的扩域上，x所表示的元素是本原元。 例如: 用本原多项式p(x)=1+x+x3 来构造GF(8)，设GF(8)上的本原元为a, 通过将a的幂模p(a)得到GF(8)上的所有元素。,2019/8/23,25,定理:设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,2019/8/
13、23,26,例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
14、+1)(x+a2+1)(x+a2+a+1),2019/8/23,27,2019/8/23,28,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)=LCMf1(x),f2(x),f2t(x) 用这种方法设计的码至少能纠t个错误，在很多情况下，这些码能纠多于t个错误！因此d=2t+1称为码的设计距离，其最小距离d* 2t+1。注意：一旦确定了n和t，我们便可以确定BCH码的生成多项式。,20
15、19/8/23,29,例3.6 考虑GF(2)上的本原多项式p(a)=a4+a+1，我们将以此来构造GF(16),设a为本原元。GF(16)上以a的幂表示形式的元素及它们对应的极小多项式为：,2019/8/23,30,我们希望确定纠单错的BCH码的生成多项式，即t=1且n=15。由前面公式可知，一个BCH码的生成多项式由LCMf1(x),f2(x),f2t(x)给出，利用前面的表我们可获得极小多项式f1(x)和f2(x)，于是有： g(x)=LCMf1(x),f2(x) =LCM(x4+x+1), (x4+x+1) =x4+x+1 因为deg g(x)=n-k，可得n-k=4，所以k=11,于
16、是我们得到纠单一错误的BCH(15,11)码的生成多项式。该码的设计距离为d=2t+1=3，可以计算该码的实际最小距离d*也是3。,2019/8/23,31,如果希望纠2个错误，且n=15。则其生成多项式为 g(x)=LCMf1(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。,2019/8/23,32,如果希望纠3个错误，且n=15。则其生成多项式为 g(x)=LCMf1(x),f2(x),f3(x),f4(x),f5(x
