《信息与编码课件教材》由会员分享，可在线阅读，更多相关《信息与编码课件教材（43页珍藏版）》请在金锄头文库上搜索。
1、第九章 BCH、Reed-Solomon码及其同类码 第九章 BCH、Reed-Solomon码 及其同类码 9.1 引言 9.2 具有循环码特性的BCH码 9.3 BCH码的译码，第一部分：关键方程 9.4 多项式的欧几里得算法 9.5 BCH码的译码，第二部分：算法 9.6 Reed-Solomon码 9.7 出现删除时的译码 9.8 (23,12)Golay码 9.1 引言 回顾 码长为n=2m-1的汉明码的一致校验矩阵： H = v0 v1 . vn-1 其中(v0,v1,.,vn-1)是Vm=GF(2m)中2m-1个非零 列矢量的某个排列。矩阵H具有mn，意味 着m个一致校验比特来纠
2、正一个错误。 设想 这个矩阵为码长为n、纠正两个错误的码的 一致校验矩阵。 9.1 引言 处理 可以将对应关系viwi看成是一个函数 w=f(v). 函数f的要求 设伴随式s=(s1,s2,.,s2m)=(s1,s2) 全零错误图案对应的伴随式s=(0,0) 单个错误图案对应的伴随式s=(vi,f(vi) 两个错误图案对应的伴随式s=(vi+vj,f(vi)+f(vj) 9.1 引言 函数f的要求 根据7.3中的结论，纠正两个错误的码，必须 让这些伴随式都不相同。故 f(0)=0 u+v=s1 f(u)+f(v)=s2 9.1 引言 如何选取f f为线性变换不能满足要求 f为二次函数也不能满足
3、要求 f(v)=v3可以满足要求 上式中的i是GF(2m)中的一个标量 9.1 引言 定理9.1 设(0,1,.,n-1)是GF(2m)中n个不同元素的一 个排列。并设t是一个(n-1)/2的正整数。则 tn矩阵 是一个二进制(n,k)码的一致校验矩阵，这个 码能够纠正所有重量t的错误图案，它的维 数kn-mt。 9.1 引言 BCH码 定理9.1所描述的这类码称为BCH码，以纪 念它的发明者Bose,Ray-Chaudhuri和 Hocquenghem。 该码的重要性在于：存在有效的编码，特别 是存在有效的译码。 9.2 具有循环码特性的BCH码 回顾 一个码长为n=2m-1能纠正一个错误的
4、汉明码 ，H中的列元素i经过适当的排列，构成循 环汉明码。（1, , 2,., n-1） 一个码长为n=2m-1、纠正t个错误的BCH码的 定义：C=(C0,C1,.,Cn-1)是一个码字的充分必 要条件是：Ci ij=0,j=1,3,.,2t-1 等价条件： Ci ij=0,j=1,2,.,2t 9.2 具有循环码特性的BCH码 循环码特性的BCH码 如果把这些元素也同样经过适当排列也可以 构成循环码（1, , 2,., n-1） C=(C0,C1,.,Cn-1)是一个码字的充分必要条件 Ci ij=0,j=1,3,.,2t-1 引进生成函数C(x),则码字条件为 C(j)=0,j=1,3,
5、.,2t-1 可以发现CR(j)=0,j=1,3,.,2t-1.说明它是一个 循环码。 9.2 具有循环码特性的BCH码 生成多项式g(x) 由于g(x)是码中次数最低的码多项式,即 g()=g(3)=.=g(2t-1)=0中最低次数多项式。 g(x)是子集A=, 3,., 2t-1在GF(2)上的最小多 项式。 定义A共轭类:A*=2 i:A,i0，则 9.2 具有循环码特性的BCH码 定理9.2 码长为n的纠正t个错误的BCH码是循环的，生 成多项式由上式给出。码的维数为n-deg(g),即 k=n=|A*|,其中A*是GF(2m)中A=, 3,., 2t- 1的共轭类的集合。 9.2 具
6、有循环码特性的BCH码 例9.1 一个码长为15、纠正3个错误的BCH码。令是 GF(16)中的一个本原元，生成多项式是集合 A=,3,5的最小多项式。 的共轭类为(, 2, 4, 8); 3的共轭类为(3, 6, 12, 9); 5的共轭类为(5, 10); A*=,2,3,4,5,6,8,9,10,12 维数k=15-10=5 9.2 具有循环码特性的BCH码 例9.1 为了计算具体的g(x),引进不可约多项式 m(x)=x4+x+1. 的最小多项式为x4+x+1 3的最小多项式为x4+x3+x2+x+1 5的最小多项式为x2+x+1 g(x)=(x4+x+1)(x4+x3+x2+x+1)
7、(x2+x+1) 9.3 BCH码的译码， 第一部分：关键方程 基础知识 令F是一个含有n阶单位本原元的域。 1-xn=0n-1(1- ix) V=(V0,V1,.,Vn-1) 9.3 BCH码的译码， 第一部分：关键方程 基础知识 如果用生成函数描述，则有 傅里叶变换特性 9.3 BCH码的译码， 第一部分：关键方程 定理9.3(BCH论证) 设V是一个非零矢量， 具有如下性质：含有m个连续 的0分量，即 则V的重量m+1。 9.3 BCH码的译码， 第一部分：关键方程 定义 矢量V的支持集 位置多项式 i阶穿孔多项式 数值多项式 9.3 BCH码的译码， 第一部分：关键方程 引理 gcd(
8、v(x),v(x)=1 定理9.4(关键方程) 对于一个固定的矢量V，多项式满足： 推论1 对于每个iI,我们有: 推论1说明,V的时域坐标可由V(x)和V(x)有效地恢 复 9.3 BCH码的译码， 第一部分：关键方程 推论2 对于任意下标j,我们有: 推论2说明,如果知道前几个坐标,其余的就可以 仅由V(x)通过一个简单的递归运算来恢复. 9.3 BCH码的译码， 第一部分：关键方程 例9.2 验正关键方程及推论 GF(16)中本元 满足4= +1，考虑矢量 V=(0,0, 2,0,0,0,0, 7,0,0,0,0,0,0,0) 9.3 BCH码的译码， 第一部分：关键方程 BCH码译码讨
9、论 设C=(C0,C1,.,Cn-1)是码长为n、纠正t个错误的BCH码中 的一个码字，接收到R=(R0,R1,.,Rn-1),错误图案 E=R-C=(E0,E1,.,En-1) 9.3 BCH码的译码， 第一部分：关键方程 BCH码译码讨论 9.4 多项式的欧几里德算法 求最大公约数gcd的线性组合算法 gcd(a(x),b(x)=d(x) u(x)a(x)+v(x)b(x)=d(x) 初始条件： u-1(x)=1,v-1(x)=0,r-1(x)=a(x) u0(x)=0,v0(x)=1,r0(x)=b(x) 递推公式： ri-2(x)=qi(x)ri-1(x)+ri(x),deg ri d
10、eg ri-1 ui(x)=ui-2(x)-qi(x)ui-1(x) vi(x)=vi-2(x)-qi(x)vi-1(x) 9.4 多项式的欧几里德算法 最大公约数gcd的线性组合算法 rn+1(x)=0 un(x)a(x)+vn(x)b(x)=rn(x)=d(x) 性质： vi ri-1 - vi-1ri=(-1)ia 0i n+1 uiri-1 - ui-1ri=(-1)ib 0i n+1 uivi-1 ui-1vi = (-1)i+1 0i n+1 ui a + vi b = ri -1i n+1 deg(ui)=deg(ri-1)=deg(b) 1i n+1 deg(vi)=deg(r
11、i-1)=deg(a) 0i n+1 9.4 多项式的欧几里德算法 例9.3 算法实例 在GF(2)中，a(x)=x8,b(x)=x6+x4+x2+x+1。 iuivi余式ri商qi -1x8 001 x6+x4+x2+x+1 11x2+1x3+x+1 x2+1 2x3+1x5+x3+x2x2x3+1 3x4+x+1x6+x4+x3+x2+1x+1x 4x5+x4+x3+x2x7+x6+x3+x+11x+1 5x6+x4+x2+x+10x+1 9.4 多项式的欧几里德算法 从性质中发现 vi(x)b(x)=ri(x) mod a(x) deg vi+deg rideg a 引理2 将两个欧几里
12、德算法应用于两个多项式a(x)、 b(x).给定整数0,0,满足+=deg(a)-1，则 存在唯一标号j,使得： deg(vj) deg(rj) 9.4 多项式的欧几里德算法 定理9.5 设a(x)、b(x)、v(x)、r(x)是非零多项式，满足： v(x)b(x)r(x) mod a(x) deg v(x)+deg r(x)deg a(x) vj(x)和rj(x)是对a(x)和b(x)通过欧几里德算法时产 生的序列。则存在唯一标号j,0jn,和一个多项 式(x),使得： v(x)=(x) vj(x) r(x) =(x) rj(x) 9.4 多项式的欧几里德算法 定义(vj(x),rj(x)=
13、Euclid(a(x),b(x),) 如果(a(x),b(x)是一对非零多项式,满足deg a(x)deg b(x)，而(,)是一对使+=deg a(x)- 1成立的非负实数， Euclid(a(x),b(x),)是这 样的程序：当(a(x),b(x)应用欧几里德算法时 ，该程序返回唯一一对多项式(vj(x),rj(x),其 中deg vj(x),deg rj(x) 9.4 多项式的欧几里德算法 定理9.6 设a(x)、b(x)、v(x)、r(x)是非零多项式，满足： v(x)b(x)r(x) mod a(x) deg v(x),deg r(x) (,)是一对使+=deg a(x)-1成立的非
14、负实数. (vj(x),rj(x)是由Euclid(a(x),b(x),)返回的一对多项式 。则存在一个多项式(x),使得： v(x)=(x) vj(x) r(x) =(x) rj(x) 9.4 多项式的欧几里德算法 例9.4 a(x)=x8,b(x)=x6+x4+x2+x+1 9.5 BCH码的译码,第二部分：算法 R=(R0,R1,.,Rn-1) C=(C0.C1,.,Cn-1) R=C+E 第一步：计算伴随式 第二步：求解(x)、(x) 第三步：由(x)、(x)确定错误图案E 第四步：由E恢复C 9.5 BCH码的译码,第二部分：算法 第一步：计算伴随式 9.5 BCH码的译码,第二部分
15、：算法 第二步：通过关键方程(x)S(x)= (x) mod x2t求解 (x)、(x) 这是可以求解的,因为 deg (x)t, deg (x) t-1,故deg (x)+ deg (x) deg a(x) 由Euclid(a(x),b(x),)返回(v(x),r(x) 这里a(x)=x2t,b(x)=S(x), =t, =t-1. (x)=(x)v(x),(x)=(x)r(x) 利用gcd(x), (x)=1,因此(x)为常数 利用(0)=1,得到 (x)=v(x)/v(0) (x)=r(x)/v(0) 9.5 BCH码的译码,第二部分：算法 第三步：由(x)、(x)确定错误图案E 时域方法： 频域方法：利用定理9.4的推论2由前2t个分 量恢复整个矢量，进而得到错误矢量 9.5 BCH码的译码,第二部分：算法 例9.5 考虑码长为15,纠正3个错误的BCH
