线性分组码的编码与译码.doc

实践教学大学计算机与通信学院2014年秋季学期计算机通信课程设计 题 目： 线性分组码(9，4)码的编译码仿真设计 专业班级： 姓 名： 学 号： 指导教师： 成 绩： 摘要该系统是（9，4）线性分组码的编码和译码的实现，它可以对输入的四位的信息码进行线性分组码编码，对于接收到的九位码字可以进行译码，从而译出四位信息码。当接收到的九位码字中有一位发生错误时，可以纠正这一位错码；当接收到的码字有两位发生错误时，只能纠正一位错误，但同时能检测出另一位错误不能纠正。只有特定位有两位错误时，才能纠正两位错误。这样就译出正确的信息码组，整个过程是用MATLAB语言实现的。关键词：编码; 译码; 纠错1目录摘要1目录21. 信道编码概述21.1信道模型21.2 抗干扰信道编码定理及逆定理31.3 检错与纠错的基本原理41.4 限失真编码定理52.线性分组码的编码62.1 生成矩阵62.2 校验矩阵92.3 伴随式与译码103. 线性分组码编码的Matlab仿真123.1 程序流程图123.2 程序执行结果123.2 线性分组码译码的Matlab仿真133.3结果分析15参考文献16总结17致 谢18附录192前言由于计算机、卫星通信及高速数据网的飞速发展，数据的交换、处理和存储技术得到了广泛的应用，数字信号在传输中往往由于各种原因，使得在传送的数据流中产生误码，从而使接收端产生图象跳跃、不连续、出现马赛克等现象，人们对数据传输和存储系统的可靠性提出来了越来越高的要求，经过长时间的努力，通过编译码来控制差错、提高可靠性的方式在信道传输中得到了大量的使用和发展，并形成了一门新的技术叫做纠错编码技术，纠错编码按其码字结构形式和对信息序列处理方式的不同分为两大类：分组码和卷积码。目前，绝大多数的数字计算机和数字通信系统中广泛采用二进制形式的码。而线性分组码具有编译码简单，封闭性好等特点，采用差错控制编码技术是提高数字通信可靠性的有效方法，是目前较为流行的差错控制编码技术。对线性分组码的讨论都在有限域GF(2)上进行，域中元素为0,1,域中元素计算为模二加法和模二乘法。分组码是一组固定长度的码组，可表示为（n , k），通常它用于前向纠错。在分组码中，监督位被加到信息位之后，形成新的码。在编码时，k个信息位被编为n位码组长度，而n-k个监督位的作用就是实现检错与纠错。对于长度为n的二进制线性分组码，它有种2n可能的码组，从2n种码组中，可以选择M=2k个码组（kn）组成一种码。这样，一个k比特信息的线性分组码可以映射到一个长度为n码组上，该码组是从M=2k个码组构成的码集中选出来的，这样剩下的码组就可以对这个分组码进行检错或纠错。251. 信道编码概述1.1信道模型信息必须首先转换成能在信道中传输或存储的信息后才能通过信道传送给收信者。在信息传输过程中，噪声或干扰主要是从信道引入的，它使信息通过信道传输后产生错误和失真。因此信道的输入和输出之间一般不是确定的函数关系，而是统计依赖的关系。只要知道信道的输入信号、输出信号以及它们之间的统计依赖关系，就可以确定信道的全部特性。信道的种类很多，这里只研究无反馈、固定参数的单用户离散信道。1离散信道的数学模型离散信道的数学模型一般如图6.1所示。图中输入和输出信号用随机矢量表示，输入信号为X= (X1, X2, XN)，输出信号为Y= (Y1, Y2, YN)；每个随机变量Xi和Yi又分别取值于符号集A=a1, a2, , ar和B=b1, b2, , bs，其中r不一定等于s；条件概率P(y|x) 描述了输入信号和输出信号之间的统计依赖关系，反映了信道的统计特性。YX信道 图1.1 离散信道模型根据信道的统计特性即条件概率P(y|x) 的不同，离散信道可以分为三种情况：（1）无干扰信道。信道中没有随机干扰或干扰很小，输出信号与输入信号之间有确定的一一对应的关系。（2）有干扰无记忆信道。实际信道中常有干扰，即输出符号与输入符号之间没有确定的对应关系。若信道任一时刻的输出符号只统计依赖于对应时刻的输入符号，而与非对应时刻的输入符号及其他任何时刻的输出符号无关，则这种信道称为无记忆信道。（3）有干扰有记忆信道。这是更一般的情况，既有干扰又有记忆，实际信道往往是这种类型。在这一类信道中某一瞬间的输出符号不但与对应时刻的输入符号有关，而且与此前其他时刻信道的输入符号及输出符号有关，这样的信道称为有记忆信道。2单符号离散信道的数学模型 单符号离散信道的输入变量为，取值于a1, a2, , ar，输出变量为，取值于b1, b2, , bs，并有条件概率P(y|x)= P(y=bj|x=ai)= P(bj |ai) (i=1,2,r；j=1,2,s)这一组条件概率称为信道的传递概率或转移概率。因为信道中有干扰（噪声）存在，信道输入为x=ai时，输出是哪一个符号y，事先无法确定。但信道输出一定是b1, b2, , bs中的一个，即有 (i=1,2,r) (1-1) 由于信道的干扰使输入符号x在传输中发生错误，所以可以用传递概率P(bj|ai)来描述干扰影响的大小。因此，一般简单的单符号离散信道的数学模型可以用概率空间加以描述。另外，也可以用图来描述，如图1.2所示。 图1.2 单符号离散信道定义1.1 已知发送符号为ai，通过信道传输接收到的符号为bj的概率P(bj|ai)称为前向概率。已知信道输出端接收到的符号为bj，而发送符号为ai的概率P(ai|bj)，称为后向概率。有时，也把P(ai)称为输入符号的先验概率（即在接收到一个输出符号以前输入符号的概率），而对应地把P(ai|bj)称为输入符号的后验概率（在接收到一个输出符号以后输入符号的概率）。为了讨论方便，下面列出本章讨论中常用的一些关于联合概率和条件概率的关系： (1) 设输入和输出符号的联合概率为P(x= ai, y= bj)=P(ai bj)，则有 (2) （）。 (3) 根据贝叶斯定律，可得后验概率与先验概率之间的关系 （） （） 1.2 抗干扰信道编码定理及逆定理定理1.1 有噪信道编码定理设离散无记忆信道X,P(y|x),Y, P(y|x)为信道传递概率，其信道容量为C。当信息传输率RC时，则无论码长n多长，均找不到一种编码2nR，使译码错误概率任意小。定理1.1和定理1.2统称为申农第二定理，它是一个关于有效编码的存在性定理，它具有根本性的重要意义，它说明错误概率趋于零的好码是存在的。它有助于指导各种通信系统的设计，有助于评价各种通信系统及编码的效率。申农1948年发表申农第二定理后，科学家就致力于研究信道中的各种易于实现的实际编码方法，赋予码以各种形式的代数结构，出现了各种形式的代数编码、卷积码、循环码等。1.3 检错与纠错的基本原理在申农第二定理发表后，很长一段时间内人们都在探寻能够简单、有效地编码和译码的好码。由此形成了一整套纠错码理论。在此只简单地介绍检错和纠错的一些基本概念及基本原理。在信息处理过程中，为了保持数据的正确性应对信息进行编码使其具有检错纠错能力，这种编码称为语法信息编码。它的基本思想是引入剩余度，在传输的信息码元后增加一些多余的码元，以使信息损失或错误后仍能在接收端恢复。通常将要处理的信息称为原信息，将原信息转化为数字信息后再进行存储、传输等处理过程称为传送。工程上最容易实现的是二元数字信息（或二元码信息）的传送。所谓二元数字信息就是由二元数域F2=0,1中的数字0与1组成的数组或向量。定义1.3 设X=(x1, x2, xn)，Y=(y1, y2, yn)，xiF2，yiF2，i=1, n，称X和Y对应分量不相等的分量个数为X和Y的汉明（Hamming）距离，记为d(X, Y)。记则d(X, Y)= d(x1, y1)+ d(x2, y2)+ d(xn, yn)容易证明以下定理。定理1.4 设X和Y是长为n的二元码字，则（1）（非负且有界性）（2）d(X, Y)=0当且仅当X=Y（自反性）（3）d(X, Y)= d(Y, X)（对称性）（4）（三角不等式）1.4 限失真编码定理申农第一定理和申农第二定理指明：无论是无噪声信道还是有噪声信道，只要信道的信息传输率小于信道容量，总能找到一种编码，在信道上以任意小的错误概率和任意接近信道容量的信息传输率传输信息。反之，若信道信息传输率大于信道容量，一定不能使传输错误概率任意小，传输必然失真。实际上，人们并不需要完全无失真地恢复信息，只是要求在一定保真度下，近似恢复信源输出的信息。比如，人类主要是通过视觉和听觉获取信息，人的视觉大多数情况下对于25帧以上的图像就认为是连续的，通常人们只需传送每秒25帧的图像就能满足通过视觉感知信息的要求，而不必占用更大的信息传输率。而大多数人只能听到几千赫兹到十几千赫兹，即便是训练有素的音乐家，一般也不过能听到20千赫兹的声音。所以，在实际生活中，通常只是要求在保证一定质量的前提下在信宿近似地再现信源输出的信息，或者说在保真度准则下，允许信源输出的信息到达信宿时有一定的失真。对于给定的信源，在允许的失真条件下，信源熵所能压缩的极限理论值是多少？申农（Shannon）的重要论文“保真度准则下的离散信源编码定理”论述了在限定范围内的信源编码定理。限失真信源编码的信息率失真理论是信号量化、模数转换、频带压缩和数据压缩的理论基础，在图像处理、数字通信等领域得到广泛的应用。所谓信道产生的失真d(xn, ym)是指：当信道输入为xn时，输出得到的是ym，其差异或损失，称为译码失真，可描述为而平均译码失真则是如果要求平均译码失真小于某个给定值，即也就是对P(Y|X)施加一定的限制。把满足上式的那些P(Y|X)记为PD，在集合PD中寻找一个P(Y|X)使I(Y|X)极小，把这个极小值称为在的条件下所必须传送的信息速率，并记为R(D)，即 R(D)=min(X;Y)RD称R(D)为信息率失真函数。它表示信息率与失真量之间的关系。上式表明，在集合PD中，任意一个I(Y|X)值所对应的平均失真都小于或等于。也就是说，在集合PD内，只要I(Y|X) R(D)，就可以达到；但是如果I(Y|X) R(D)，对于任意小的，允许失真值，以及任意足够长的码字长度，则一定存在一种编码方法，使其平均译码失真；反之，若R R(D)，则编码后的平均失真将大于。如果用二进制码符号来进行编码的话，那么在允许失真为的情况下，平均每个信源符号所需二进制码符号数的下限值在数量上等于R(D)。在不允许失真的情况下，平均每个信源符号所需二进制码符号数的下限值在数量上等于H(S)。一般情况下，有R(D)=k+r) flag_in=0; endend% -% - 生成校正子，可选择自动生成或手动输入 -Q_yesOrNo=input(是否自动生成校正子？Y/N:,s);if(Q_yesOrNo=Y) %从数值不会重合的集合中选出校验子的十进制数 Q_randFull=randperm(2r-1); Q_randCheck=zeros(1,k); %初始化k行r列的矩阵Q Q=zeros(k,r); i=1;j=1; %选出可用的校验子（十进制） while(iC%02d,k+r-1:-1:0),8,k+r);disp(校正子与错码位置的对应关系);Q_char=Q_charC Q_charD% -% - 线性分组码内部的函数关系及计算 -Ik=eye(k);%生成k*k的单位矩阵，与Q合成为生成矩阵GG=Ik Q;%生成矩阵P=Q;Ir=eye(r);%生成r*r的单位矩阵，与P合成为监督矩阵HH=P Ir;%监督矩阵% -% - 计算所有的可用码组 -valid_yesOrNo=input(是否要显示所有可用码组?Y/N:,s);if(valid_yesOrNo=Y) %初始化2k行k+r列，与1行k列的矩阵 valid_codes=zeros(2k,k+r); valid_buffer=zeros(1,k); %初始化每行码重数组 weight_array=zeros(1,2k); %遍历可用信息码并输出所有可用码组 for i=1:1:2k %将第i行的十进制数转制为4位二进制数（字符矩阵） valid_binary=dec2bin(i-1,k); for j=1:1:k %将字符转换为数值放入矩阵（行向量）中 valid_buffer(j)=str2double(valid_binary(j); end %将得出的第i行的行向量valid_codes,并得出当前信息码对应全长码字 valid_codes(i,:)=mod(valid_buffer*G,2); %求每行可用码字的码重 weight_array(i)=length(nonzeros(valid_codes(i,:); end disp(最终可用码组：); valid_codes disp(最小码重：); min_weight=min(weight_array(2:2k) %count=1; for i=1:1:2k-1 for j=i+1:1:2k %两两的码距存入数组中 %distance_array(count)=length(nonzeros(valid_codes(i,:)-valid_codes(j,:); distance_array(i,j)=length(nonzeros(valid_codes(i,:)-valid_codes(j,:); %count=count+1; end end %调整码距矩阵 disp(最小码距：); %min_distance=min(min(distance_array) distance_array(find(distance_array=0)=NaN; min(min(distance_array)end% -% - 输入或自动生成码字及校验码字的正确性 -check_yesOrNo=input(是否自动生成要校验的码字？Y/N:,s);if(check_yesOrNo=Y) disp(校验码字); check_code=r