信息与编码课件教材

第九章BCH、Reed-Solomon码及其同类码第九章BCH、Reed-Solomon码及其同类码9.1引言9.2具有循环码特性的BCH码9.3BCH码的译码，第一部分：关键方程9.4多项式的欧几里得算法9.5BCH码的译码，第二部分：算法9.6Reed-Solomon码9.7出现删除时的译码9.8(23,12)Golay码9.1引言回顾码长为n=2m-1的汉明码的一致校验矩阵：

H=[v0v1...vn-1]

其中(v0,v1,...,vn-1)是Vm=GF(2m)中2m-1个非零列矢量的某个排列。矩阵H具有m×n，意味着m个一致校验比特来纠正一个错误。设想这个矩阵为码长为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)=0u+v=s1f(u)+f(v)=s29.1引言如何选取ff为线性变换不能满足要求f为二次函数也不能满足要求f(v)=v3可以满足要求上式中的i是GF(2m)中的一个标量9.1引言定理9.1设(

0,

1,...,

n-1)是GF(2m)中n个不同元素的一个排列。并设t是一个≤(n-1)/2的正整数。则t×n矩阵

是一个二进制(n,k)码的一致校验矩阵，这个码能够纠正所有重量≤t的错误图案，它的维数k≥n-mt。9.1引言BCH码定理9.1所描述的这类码称为BCH码，以纪念它的发明者Bose,Ray-Chaudhuri和Hocquenghem。该码的重要性在于：存在有效的编码，特别是存在有效的译码。9.2具有循环码特性的BCH码回顾一个码长为n=2m-1能纠正一个错误的汉明码，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,...,2t9.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,...,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*={β2i:β∈A,i≥0}，则9.2具有循环码特性的BCH码定理9.2

码长为n的纠正t个错误的BCH码是循环的，生成多项式由上式给出。码的维数为n-deg(g),即k=n=|A*|,其中A*是GF(2m)中A={α,α3,...,α2t-1}的共轭类的集合。9.2具有循环码特性的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=59.2具有循环码特性的BCH码例9.1

为了计算具体的g(x),引进不可约多项式m(x)=x4+x+1.α的最小多项式为x4+x+1α3的最小多项式为x4+x3+x2+x+1α5的最小多项式为x2+x+1g(x)=(x4+x+1)(x4+x3+x2+x+1)(x2+x+1)9.3BCH码的译码，

第一部分：关键方程基础知识令F是一个含有n阶单位本原元α的域。

1-xn=∏0n-1(1-αix)V=(V0,V1,...,Vn-1)9.3BCH码的译码，

第一部分：关键方程基础知识 如果用生成函数描述，则有傅里叶变换特性9.3BCH码的译码，

第一部分：关键方程定理9.3(BCH论证)

设V是一个非零矢量，具有如下性质：含有m个连续的0分量，即

则V的重量≥m+1。9.3BCH码的译码，

第一部分：关键方程定义矢量V的支持集位置多项式i阶穿孔多项式数值多项式9.3BCH码的译码，

第一部分：关键方程引理gcd(σv(x),ωv(x))=1定理9.4(关键方程)对于一个固定的矢量V，多项式满足：推论1对于每个i∈I,我们有:推论1说明,V的时域坐标可由σV(x)和ωV(x)有效地恢复..9.3BCH码的译码，

第一部分：关键方程推论2对于任意下标j,我们有:推论2说明,如果知道前几个坐标,其余的就可以仅由σV(x)通过一个简单的递归运算来恢复.9.3BCH码的译码，

第一部分：关键方程例9.2验正关键方程及推论

GF(16)中本元α满足α4=α+1，考虑矢量

V=(0,0,α2,0,0,0,0,α7,0,0,0,0,0,0,0)

9.3BCH码的译码，

第一部分：关键方程BCH码译码讨论设C=(C0,C1,...,Cn-1)是码长为n、纠正t个错误的BCH码中的一个码字，接收到R=(R0,R1,...,Rn-1),错误图案

E=R-C=(E0,E1,...,En-1)9.3BCH码的译码，

第一部分：关键方程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),degri<degri-1ui(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)=0un(x)a(x)+vn(x)b(x)=rn(x)=d(x)性质：Ａviri-1-vi-1ri=(-1)ia 0≤i≤n+1Ｂuiri-1-ui-1ri=(-1)ib 0≤i≤n+1Ｃuivi-1–ui-1vi=(-1)i+1 0≤i≤n+1Ｄuia+vib=ri -1≤i≤n+1Ｅdeg(ui)=deg(ri-1)=deg(b) 1≤i≤n+1Ｆdeg(vi)=deg(ri-1)=deg(a) 0≤i≤n+19.4多项式的欧几里德算法例9.3算法实例在GF(2)中，a(x)=x8,b(x)=x6+x4+x2+x+1。iuivi余式ri商qi-1１０x8001x6+x4+x2+x+111x2+1x3+x+1x2+12x3+1x5+x3+x2x2x3+13x4+x+1x6+x4+x3+x2+1x+1x4x5+x4+x3+x2x7+x6+x3+x+11x+15x6+x4+x2+x+10x+19.4多项式的欧几里德算法从性质中发现vi(x)b(x)=ri(x)moda(x)degvi+deg

ri<dega引理2将两个欧几里德算法应用于两个多项式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)moda(x)degv(x)+deg

r(x)<dega(x)vj(x)和rj(x)是对a(x)和b(x)通过欧几里德算法时产生的序列。则存在唯一标号j,0≤j≤n,和一个多项式λ(x),使得：

v(x)=λ(x)vj(x)

r(x)=λ(x)rj(x)9.4多项式的欧几里德算法定义(vj(x),rj(x))=Euclid(a(x),b(x),μ,ν)

如果(a(x),b(x))是一对非零多项式,满足dega(x)≥deg

b(x)，而(μ,ν)是一对使μ+ν=dega(x)-1成立的非负实数，Euclid(a(x),b(x),μ,ν)是这样的程序：当(a(x),b(x))应用欧几里德算法时，该程序返回唯一一对多项式(vj(x),rj(x)),其中degvj(x)≤μ,deg

rj(x)≤ν9.4多项式的欧几里德算法定理9.6

设a(x)、b(x)、v(x)、r(x)是非零多项式，满足：v(x)b(x)≡r(x)moda(x)degv(x)≤μ,deg

r(x)≤ν(μ,ν)是一对使μ+ν=dega(x)-1成立的非负实数.(vj(x),rj(x))是由Euclid(a(x),b(x),μ,ν)返回的一对多项式。则存在一个多项式λ(x),使得：

v(x)=λ(x)vj(x)

r(x)=λ(x)rj(x)9.4多项式的欧几里德算法例9.4a(x)=x8,b(x)=x6+x4+x2+x+19.5BCH码的译码,第二部分：算法R=(R0,R1,...,Rn-1)C=(C0.C1,...,Cn-1)R=C+E第一步：计算伴随式第二步：求解σ(x)、ω(x)第三步：由σ(x)、ω(x)确定错误图案E第四步：由E恢复C9.5BCH码的译码,第二部分：算法第一步：计算伴随式9.5BCH码的译码,第二部分：算法第二步：通过关键方程σ(x)S(x)=ω(x)modx2t求解σ(x)、ω(x)这是可以求解的,因为degσ(x)≤t,degω(x)≤t-1,故degσ(x)+degω(x)≤dega(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.5BCH码的译码,第二部分：算法第三步：由σ(x)、ω(x)确定错误图案E

时域方法：

频域方法：利用定理9.4的推论2由前2t个分量恢复整个矢量，进而得到错误矢量9.5BCH码的译码,第二部分：算法例9.5考虑码长为15,纠正3个错误的BCH码,它的生成多项式为g(x)=x10+x8+x5+x4+x2+x+1。假设接收矢量R=(110000110110101)。则伴随式分量Sj由Sj=1+αj+α6j+α7j+α9j+α10j+α12j+α14j给出，其中α是GF(16)的本原元。9.6Reed-Solomon码RS码概述BCH码是GF(2)上能纠正多个错误的线性码,它的译码算法需要在更大的域GF(2m)上实现.RS码的符号域与计算域是相同的,它可以很自然地适合于传送信息符号,而不是比特.9.6Reed-Solomon码RS码定义.令F是含有阶数为n的元素α任意域.如果r是一个1到n之间的固定整数,则分量在F中,并且满足

的所有矢量C=(C0,C1,…,Cn-1)组成的集合称为域F上的码长为n、冗余为r的一个Reed-Solomon码。属于这个码的矢量C称为它的码字。9.6Reed-Solomon码定理9.7由RS码定义的码是F上的一个(n,n-r)循环码，它的生成多项式为g(x)=∏rj=1

(x-αj),最小距离dmin=r+1.9.6Reed-Solomon码例9.6GF(8)上的(7,3)Reed-Solomon码如果α是GF(8)中的一个本原元，满足α3=α+1,则该码的生成多项式为g(x)=(x-α)