信息论与编码第八章1

第8章纠错编码8.2纠错编码的分类8.1纠错编码的基本概念8.3线性分组码8.4循环码8.1纠错编码的基本概念信道编码提高数字通信可靠性

数字信号在信道的传输过程中,由于实际信道的传输特性不理想以及存在加性噪声,在接收端往往会产生误码。信源编码提高数字信号有效性

将信源的模拟信号转变为数字信号

降低数码率,压缩传输频带(数据压缩)目的在于提高通信（或存储）的可靠性，减低误码率。从原理上看，构造信道码的基本思路是根据一定的规律在待发送的信息码元中人为地加入一定的多余码元(称为监督码)，以引入最小的多余度为代价来换取最好的抗干扰性能。设有m个不同的信息序列，每个不同的序列由k（k<n)位（信息位），它由码元组成。[C]为编码器的输出，称为码字矢量，它由n位码元组成，其中有k位信息元，r=n-k位监督元。假设信源信息是二进制数字序列，将信源编码其的输出序列构成长度为n的段，记为C定义8.1对于二元符号表上的分组码C，由表示消息序列的长度为n的m个二元序列构成的集合，称为二元分组码。定义8.2对于2k个n长码字全体构成的分组码，其码字中的k位称为信息位，n-k位称为校验位或监督位。线性分组码：监督元与信息元之间的关系可用一组线性方程组来描述的(n,k)分组码。编码效率：一个组中信息所占的比重。k：信息码元的数目n：编码组码元的总数目n=k+rr：监督码元的数目定义8.3若（n，k）分组码中k个信息位同原始k个信息位相同，且位于n长码字的前（或后）k位，为校验位位于其后（或前），则称该分组码为系统码，否则为非系统码。定义8.4两个序列之间的汉明距离定义为两个序列之间对应位不同的位数。例如：α和β为码组X中的两个不同码字，X为一个长度为N的二元码组，其中：

α=[a1,a2,……aN]ai∈{0,1}

β=[b1,b2,……bN]bi∈{0,1}

则α与β的汉明距离为：

d=0表明为全同码，d=N表明为全异码码的最小汉明距离是衡量码的纠、检错能力的重要参数，码的最小距离越大，其纠、检错能力越强。最小码距：在一个码字集合中，任何两个码字之间的汉明距离组成一个元素集合，D(α,β),这个集合中的最小值称为这个码字集合的最小汉明距离，简称最小码距，记为：dmin。

dmin=min{d(α,β)α,β∈X

α≠β}定义8.5对于码C中的某一码字，其非零元素的个数称为该码字的汉明重量。对于二元码，其码字的重量是码字中1的个数。若码字

，其重量可以表示为：如码字

，其重量为5。8.2纠错编码分类根据信息码元与监督码元之间的关系，纠错码分为线性码和非线性码。

线性码——信息码元与监督码元之间呈线性关系，它们的关系可用一组线性代数方程联系起来。非线性码——信息码元与监督校元之间不存在线性关系。按照对信息码元处理的方法的不同，纠错码分为分组码和卷积码。

分组码----把信息序列以每k个码元分组，然后把每组k个信息元按一定规律产生r个多余的监督码元，输出序列每组长为n=k+r，则每一码字的r个校验元只与本码字的k个信息位有关，与别的码字的信息位无关，通常记分组码为(n,k)。其中分组码又可分循环码和非循环码：对循环码而言，其码书的特点是，若将其全部码字分成若干组，则每组中任一码字中码元循环移位后仍是这组的码字；对非循环码来说，任一码字中的码元循环移位后不一定再是该码书中的码字。卷积码----把信息序列以每k0(通常较小)个码元分段，编码器输出该段的监督码元r=n-k0

不但与本段的k0个信息元有关，而且还与其前面L段的信息码元有关，故记卷积码为(n,k0,L)。从功能上看，信道编码可分为检错(可以发现错误)码与纠错(不仅能发现而且能自动纠正)码两类，纠错码一定能检错，检错码不一定能纠错，平常所说的纠错码是两者的统称。发送端的信道编码器将信息码组编成具有一定纠错能力的码。接收端信道译码器对接收码字进行译码,若传输中产生的差错数目在码的纠错能力之内时,译码器对差错进行定位并加以纠正。1、前向纠错(FEC)：发端发送检错码，收端译码器判断当前码字传输是否出错；当有错时按某种协议通过一个反向信道请求发送端重传已发送的码字(全部或部分)。2、自动请求重发(ARQ)：是FEC与ARQ方式的结合。发端发送同时具有自动纠错和检测能力的码组,收端收到码组后,检查差错情况,如果差错在码的纠错能力以内,则自动进行纠正。如果信道干扰很严重,错误很多,超过了码的纠错能力,但能检测出来,则经反馈信道请求发端重发这组数据。3、混合纠错(HEC)4、信息反馈(IRQ)：收端把收到的数据,原封不动地通过反馈信道送回到发端,发端比较发的数据与反馈来的数据,从而发现错误,并且把错误的消息再次传送,直到发端没有发现错误为止。8.3线性分组码线性分组码是编码方式是将信息序列进行分组，称为信息组，每个信息组由相继的k位信息组成，然后按照一定编码规则，把信息组成n为二进制数字序列，形成码字。它的基本关系一个码字包括独立的信息元和监督元，其监督元与信息元之间是一种代数关系，如果这种代数关系为线性的则称为线性分组码。8.3.1校验矩阵与生成矩阵分组码信息序列码字M=(mk-1…m0)C=(cn-1…c0){M}{C}f

(ּ)线性分组码有一组信息元的模2线性方程生成，假设k=3，n=7，构成的线性分组码为

C=[c1,c2,c3,c4,c5,c6,c7]式中，c1,c2,c3为信息元c4,c5,c6,c7为校验元校验元可用下列方程组得到校验方程或监督方程改写矩阵形式为令

H=HCT=0或CHT=0H称为一致校验矩阵。定义8.6对于k位信息位n长的线性分组码，可有下面关系存在

C=mG式中C为n维矢量，m为k为矢量，称矩阵G（k×n维）为线性分组码C的生成矩阵。生成矩阵可以写成分块矩阵，即

G=[IP]生成矩阵与校验矩阵的关系：HGT=0或GHT=0校验矩阵可以写成H=[QI]只有当PT=Q或P=QT时等式才成立。生成矩阵可以写成G=[IP]例(6,3)线性分组码，其生成矩阵是求：(1)计算码集，列出信息组与码字的映射关系。(2)将该码系统化处理后，计算系统码码集并列出映射关系。(3)计算系统码的校验矩阵H。若收码r=[100110],检验它是否码字？(4)根据系统码生成矩阵画出编码器电原理图。

解(1)由得

令得信息码字系统码字000000000000000001 011101 001011010 110001 010110011 101100 011101100 111010 100111101 100111 101100110 001011 110001111010110 111010(2)对G作行运算，得系统化后的生成矩阵Gs

m0m1m2c0c1c2输入输出8.3.2线性分组码的纠、检错能力定理8.1对于一个二进制对称信道，若输出为k个等可能的n长码字，则最大后验概率译码准则应为最小汉明距离。定理8.2线性分组码的最小距离等于非零码字的最小重量。定理8.3对于（n，k）线性分组码，设最小距离为dmin，那么有以下结论存在：⑴这组码具有纠正u个错误的充分必要条件是⑵这组码具有检测l个错误的充分必要条件是dmin=2u+1dmin=l+1（3）这组码具纠正t个错误，同时可以发现l（l>t）个错误的充分必要条件是dmin=t+l+1设有m个n长码Xi，i=1，2，…，m,显然n长码字的总数为2n。当发送某一码字的错误码元小于或等于u时，即对接收码字满足d(Xi,Y)≤u接收码字的可能数为对于可能发送的所有m个码字，若能使校正小于或等于u位错误，则接收码字的总个数为并且一定满足8.3.3校验矩阵与最小距离的关系定理8.4对于（n，k）线性分组码，设其校验矩阵为H，若H中的任意t列线性无关，而有t+1列线性相关，则码字的最小距离或最小重量为t+1；若码字的最小重量或最小距离为t+1，则校验矩阵H的任意t列线性无关，而又t+1列线性相关。各列都不相同，任意2列之和不等于0，2列线性无关；任意2列之和一定等于矩阵中某一列，任意3列线性相关。所以该码的最小距离为3，小于n-k

+1=4。8.3.4线性分组码的伴随式为了纠正码字的某位发生的错误，必须使每一位发生错误的标志互不相同，我们称这个标志为伴随式。设发送码字为C，接收码字为Y,校验矩阵为H，令S=YHT或

ST=HYT当S=0时，则接收的Y为一码字，即满足校验方程若S≠0，说明Y不是码字。设发送码字为C＝[c1c2…cn]接受码字应为发送码字与错误图样的和Y＝C+E=[y1y2…yn]S=YHT=(C+E)HT=CHT+EHT因为C是码字，故CHT=0所以有S=EHT当码字的第i位发生错误时，则ei=1，否则ei=0码字在传输过程中，由于干扰和噪声的存在，将产生差错这个差错称为错误图样

E＝[e1e2…en]8.3.5线性分组码的译码当求得错误图样后，其发送码字的估值为若有两个或两个以上错误时，只能检错，不能纠错。在传输过程中，错误个数不超过纠错能力时，伴随式与错误图样有对应关系。假设一组码具有纠正单个错误能力时，且码字在传输过程中只有一个错误，显然错误图样中只有一个为1，所以伴随式为校验矩阵中的某一列。定理8.5若（n，k）线性分组码能纠正u个错误，则其校验位的数目必须满足8.3.6汉明码汉明码是能够纠正一个错误的线性分组码。汉明码有两种构造方式：1、校验矩阵的标准形式即H=[PI]2、校验矩阵的列按二进制的自然顺序从左到右排列的非零列。改进汉明码使它除了具有纠正但个错误外，还能发现两个错误。汉明码的纠错能力t=1，既有二进制的，也有非二进制的。二进制时，汉明码码长n和信息位k服从以下规律：(n,k)=(2m-1,2m-1-m)

其中m=n-k，是正整数。当m＝3、4、5、6、7、8…时，有汉明码(7,4)、(15,11)、(31,26)、(63,57)、(127,120)……。二是校验矩阵的列是按二进制的自然顺序从左到右排列的非零列。对于(7,4)线性分组码，按这种校验矩阵编出的码是非系统码。当发生单个错误时，伴随式是H中与错误位置对应的列，所以伴随式二进制数的值就是错误位置的序列。汉明码只表明了纠正单个错误的能力，但没有发现两个错误的能力。可以改进汉明码，使它除了具有纠正单个错误的能力外，还能发现两个错误。因为当出现一个错误时，其伴随式的最后一位数是1，即[**…*1]形式；当出现两个错误时，其伴随式为某两列之和，故最后一位数为0，即为[**…*0]形式，因为它与H’中的任何一列都不相同，所以与单个错误的伴随式不同，因此具备检查出2个错误的能力。8.4循环码循环码是线性代数分组码，一般记为（n，k）码，其中n为码字长度，k为信息位长度。特点：若C=[c1,c2,…,cn]是一个码字，那么他的循环移位C’=[c2，c3，…,cn,c1]同样也是一个码字。定义8.7对于(n,k)线性分组码，若一个码字为C＝[c1c2

…cn-1

cn

]该码向左循环一位后为：C（1）＝[c2

c3

…cn-1cnc1

]向左再循环i位后为：C（i）＝[ci+1

ci+2

…cn-1cnc1….ci

]若C（i）均为码字，则称这个（n，k）线性分组码为循环码。循环码采用多项式表示C(x)=c1xn-1+c2xn-2

+…+cn-1x+cn循环左移一位：(c1c2

…cn)(c2c3

…cnc1)C0(x)=c1xn-1+c2xn-2

+…+cn-1x+cnC1(x)=

xC0(x)=c2xn-1+c3xn-2+…+cn

x+c1

移1位：C1(x)=xC0(x) mod(xn

+1)

移2位：C2(x)=xC1(x)=x2C0(x)mod(xn+1)

移i位：Ci(x)=xiC0(x) mod(xn+1)比较循环移位的前后，可用如下的多项式运算来表达循环移位根据码空间的封闭性，码字的线性组合仍是码字。码多项式由于（n，k）循环码共有2k个码字，从码组中取出一个前面（k-1）位都是0的码字，用g（x)表示，g(x)＝x

n-k

+gn-k-1x

n-k-1+…+g2x2+g1x+1由xig（x)构成生成矩阵为C(x)=[m1m2…mk]G(x)

码多信息元生成项式矩阵C(x)=m(x)g(x)码多信息生成项式多项式多项式校验多项式多项式xn+1可因式分解为xn+1＝g(x)h(x)的形式；如果g(x)代表(n，k)循环码的生成多项式，则h(x)代表该循环码的一致校验多项式，其阶次为k。h(x)的校验作用表现在：任何码多项式C(x)与h(x)的模xn+1乘积一定等于0，而非码字与h(x)的乘积必不为0。C(x)h(x)=

m(x)g(x)h(x)=

m(x)(xn+1)=0mod(xn+1)次多项式

称为码的校验多项式。设和

系数满足以下关系设即

是

的倒多项式，则校验矩阵可以表示为由于

，故有校验矩阵可表示为例研究一个长度n=7的循环码的构成方法

对(x7+1)作分解，找出n-k次因式。

x7+1＝(x+1)(x3+x2+1)(x3+x+1)，

n-k

因式g(x)对偶式h(x)循环码

1(x+1) (x3+x2+1)(x3+x+1)(7,6)3(x3+x2+1)(x+1)(x3+x+1)(7,4)3(x3+x+1)(x+1)(x3+x2+1)(7,4)4(x+1)(x3+x2+1)(x3+x+1)(7,3)4(x+1)(x3+x+1)(x3+x2+1)(7,3)6(x3+x2+1)(x3+x+1)(x+1) (7,1)构成(7,3)循环码： 选g(x)=(x+1)(x3+x+1)=(x4+x3+x2+1)，则C(x)=m(x)g(x)=(m2x2+m1x+m0)(x4+x3+x2+1)。当输入信息m=(011)时，m(x)=(x+1)，C(x)=(x+

1)(x4＋x3＋x2＋1)=x