线性分组码的编译码软件设计.docx
《线性分组码的编译码软件设计.docx》由会员分享，可在线阅读，更多相关《线性分组码的编译码软件设计.docx（20页珍藏版）》请在冰点文库上搜索。
线性分组码的编译码软件设计
摘要
线性分组码一种重要的差错控制编码，它编码与译码电路比较简单，纠错能力也较强，是实际应用中比较流行的差错控制编码方法之一。
本文以（7,3）线性分组码为例，在设计中已给定生成矩阵G，针对（7,3）线性分组码，运用C语言编译软件，实现了对输入序列的编码、译码以及对输入接收码组的查错和纠错，该软件程序系统简单易懂，实用性强，不失为一个满足实际需求和课设要求的系统。
关键词：
差错控制，线性分组码，编译码；
前言
随着社会经济的迅速发展和科学技术的全面进步，计算机事业的飞速发展，以计算机与通信技术为基础的信息系统正处于蓬勃发展的时期，随着经济文化水平的显著提高，人们对生活质量及工作软件的要求也越来越高。
计算机通信是一种以数据通信形式出现，在计算机与计算机之间或计算机与终端设备之间进行信息传递的方式。
它是现代计算机技术与通信技术相融合的产物，在军队指挥自动化系统、武器控制系统、信息处理系统、决策分析系统、情报检索系统以及办公自动化系统等领域得到了广泛应用。
计算机通信系统是经典的数字通信系统，它是计算机技术和通信技术结合的产物，一方面通信网络为计算机之间的数据传递和交换提供必要的设施和手段；另一方面，数字计算机技术的发展渗透到通信技术中，又提高了通信网络的各种性能，二者相互渗透、互相促进、共同发展。
由于计算机、卫星通信及高速数据网的飞速发展，数据的交换、处理和存储技术得到了广泛的应用，数字信号在传输中往往由于各种原因，使得在传送的数据流中产生误码，从而使接收端产生图象跳跃、不连续、出现马赛克等现象，人们对数据传输和存储系统的可靠性提出来了越来越高的要求，经过长时间的努力，通过编译码来控制差错、提高可靠性的方式在信道传输中得到了大量的使用和发展，并形成了一门新的技术叫做纠错编码技术，纠错编码按其码字结构形式和对信息序列处理方式的不同分为两大类：
分组码和卷积码，本课程设计主要针对一个包含二进制序列的文档中的数据进行（7,3）线性分组码的编译码，并借助C语言软件，通过编写源程序文件，运行后对系统进行结果分析分析。
目录
第一章设计目标1
第二章线性分组码的基本原理1
2.1差错控制技术概述1
2.2差错控制原理2
2.3线性分组码3
2.4线性分组码的纠检错能力3
第三章（7,3）线性分组码的编码4
3.1（7,3）线性分组码的生成矩阵4
3.2（7,3）线性分组码的监督矩阵5
第四章（7,3）线性分组码的译码6
4.1校正子与错误图样6
4.2线性分组码C语言程序代码7
4.3线性分组码编译码流程框图11
4.4运行结果分析14
第五章C语言软件简介16
5.1C语言软件概述16
5.2C语言软件的特点16
5.3C语言软件的优点17
总结17
参考文献18
第一章设计目标
计算机通信是一种以数据通信形式出现，在计算机与计算机之间或计算机与终端设备之间进行信息传递的方式。
它是现代计算机技术与通信技术相融合的产物，在军队指挥自动化系统、武器控制系统、信息处理系统、决策分析系统、情报检索系统以及办公自动化系统等领域得到了广泛应用。
随着计算机、卫星通信及高速数据网的飞速发展，数据的交换、处理和存储技术得到了广泛应用，人们对数据传输和存储系统的可靠性提出了越来越高的要求。
因此，如何控制差错、提高数据传输和存储的可靠性，成为现代数字通信系统设计工作者所面临的重要课题，线性分组码是差错控制编码的重要一种，线性分组码的编码与译码电路比较简单，纠错能力也较强，是实际应用中比较流行的差错控制编码方法之一。
在本次课程设计中，要设计一个（7，3）线性分组码的编译码程序，最基本的是要具备对输入的信息码进行编码，让它具有抗干扰的能力，同时，还要让它具有对接收到的整个码组中提取信息码组的功能，但是，在实际的通信系统中，由于信道传输特性不理想以及加性噪声的影响，接收到的信息中不可避免地会发生错误，影响通信系统的传输可靠性，因而，本设计还要让该程序具有纠正错误的能力，当接收到的码组中有一位码，发生错误时可以检测到这一位错码，并且可以纠正这一位错码，并且让系统从纠正后的码组中提取正确的信息码组，针对给定的矩阵，完成如下的工作：
1完成对任意信息序列的编码
2根据生成矩阵，形成监督矩阵
3根据得到的监督矩阵，得到伴随式，并根据它进行译
4验证工作的正确性
第二章线性分组码的基本原理
2.1差错控制技术概述
数字信号在传输过程中，由于受到干扰的影响，码元波形将变坏，接收端收到后可能发生错误判决，由乘性干扰引起的码间串扰，一般采用均衡的办法纠正。
加性干扰的影响一般从合理选择调制制度解调方法以及发送功率等方面考虑，使加性干扰不足以影响达到误码率要求。
在仍不能满足要求时，为减少错误、提高通信质量还采用检错、纠错技术，即差错控制措施。
差错控制的主要方法是将数据以某种形式编码。
差错控制的核心为：
抗干扰编码，简称差错控制编码。
差错控制编码分为检错码、纠错码两大类。
它在码元间建立了某种数学约束关系，并且对特定的信道总存在某种纠错编码信号以实现最小的能量或最小的带宽或最小的时间代价获得最小的数据传输差错。
对于不同信道，采用不同类型的差错控制技术。
差错控制技术主要有：
1）检错重发：
在发送码元序列中加入差错控制码元，接收端利用这些码元检测到有错码时，利用反向信道通知发送端，要求发送端重发，知道正确接收为止。
2）前向纠错：
前向纠错是利用接收端在发送码元序列中加入的差错控制码元，不但能够发现错码，还能够将错码恢复其正确值。
3）反馈校验：
不需要在发送序列中加入差错控制码元，接收端接收到的码元原封不动的转发会发送端。
在发送端将他和原发送码元逐一比较，若发现有不同，就认为接收端接受的序列有错码，发送端立即从发。
4）检错删除：
在接收端发现错码后，立即将其删除，不要求重发。
这种方法只适合在少数特定系统中，在那里发送码元有大量的多余度，删除部分接收码元不影响应用。
2.2差错控制原理
将信息码分组，并为每个信息组附加若干监督的编码，称为“分组码”。
在分组码中，监督码元仅监督本组码中的信息码元。
分组码一般用符号（n）、（k）表示，其中k是每组码二进制信息码元的数目。
n是码组的总位数，又称为码组的长度。
r=n-k为每个码组中的监督码元数目，或称监督位数目。
k位二进制数构成的码组集合为
种不同的码组，若
组都为有用码组，其中任意码组出现错误都将变成另一码组，则接收端无法检测识别哪一组出错。
若只取部分码组为有用码组，则在传输过程中如接收端接收到的码组为非许用码组即禁用码组时，则可知传输错误。
以3位二进制数构成的码组为例，它共有8种不同的可能组合，若将其全部用来表示天气，则可以表示8种不同天气，例如：
000晴、001云、010阴、011雨、100雪、101霜、110雾、111雹。
其中任一码组在传输中若发生一个或多个错误，则将变成另一个信息码组。
这时接收端无法发现错误。
若在上述8种码组中秩序使用4种来传达天气，例如：
000晴、011云、101阴、110雨。
这时，虽然只能传达4种不同的天气，但是接收端却可能发现码组中的一个错码。
如000错码一位，则接受码组将变成100或010或011.这三种码组都为禁用码组，故接收端认为接收码错误。
要想能够纠正错误，需增加冗余度。
2.3线性分组码
线性分组码是一类奇偶校验码，它可以由（n，k）形式表示，编码器将一个k比特信息分组（信息矢量）转变为一个更长的由给定元素符号集组成的n比特编码分组，当这个符号集包含两个元素（0和1），与二进制相对，称为二进制编码。
分组码是对每段k位长的信息组，以一定规则增加r=n-k个检验元，组成长为n的序列：
，称这个序列为码字。
在二进制情况下，信息组总共有
个（q进制为
个），因此通过编码器后，相应的码字也有
个，称这
个码字集合为（n,k）分组码。
n长序列的可能排列总共有
种。
称被选取的
个n重为许用码组，其余
个为禁用码组，称R=k/n为码率。
那么对于（7，3）码即为用7位长的序列表示3位信息码，7位长序列的可能排列总共有
个。
许用码组有
个，其余
个禁用码组，码率为R=3/7=42.86%。
对于长度为n的二进制分组码，可以表示成（n，k），通常用于前向纠错。
在分组码中，监督位加到信息位之后，形成新码，在编码中，k个信息位，被编为n位长度，（n-k）个监督码的作用是实现检错和纠错。
2.4线性分组码的纠检错能力
在分组码中，我们把码组C中非零分量（对二进制来说，即1分量）的数目定义为码组C的汉明重量。
两个码组对应位上数字不同的个数称为码组的距离，简称码距，也称汉明距离。
对（n，k）线性码来说，
个码字中所有可能码字之间的汉明距离中最小的距离称为该码的最小汉明距离，用dmin表示。
而对于线性分组码来说，线性分组码的最小距离等于它的最小重量。
一个线性分组码码的最小距离dmin和码的抗干扰能力有如下关系：
1）若要检测m个错码，要求最小距离dmin≥m+1
2）若要纠正t个错码，要求最小距离dmin≥2t+1
3）若要纠正t个错码同时检测m个（m>t）错码，要求码的最小距离dmin≥m+t+1
由上可知，一个（n,k）线性分组码有两个重要参数。
一个是它的最小距离dmin，它反映了码的抗干扰能力，dmin越大，码的纠错或检错能力越强；另一个是码率R=k/n，它表示信息位在码组中所占的比重，R越大，说明信息位占的比重越高，故码的有效性越高。
显然，我们希望构造一个R高且dmin大的码，但实际上这两者是矛盾的。
编码的主要任务就是如何找到一种方法，在满足一定R的条件下，使dmin尽可能地大。
在此选择在课堂上涉及到的（7,3）线性分组码进行编程，完成对任意信息序列的编码。
第三章（7,3）线性分组码的编码
3.1（7,3）线性分组码的生成矩阵
选用码组的信息组为
，码字为
。
当已知信息组时，按以下规则得到四个校验元，即
（1）
这组方程称为校验方程。
（7,3）码有许用码组有
个，其余
个禁用码组，码率为R=3/7=42.86%。
发送方发送的是许用码字，若接收方收到的是禁用码字，则说明传输中发生了错误。
为了深化对线性分组码的理论分析，可将其与线性空间联系起来。
由于每个码字都是一个二进制的n重，即二进制n维线性空间中的一个矢量，因此码字又称为码矢。
线性分组码的一个重要参数是码率R=k/n,它说明在一个码字中信息位所占的比重，R越大，说明信息位所占比重越大，码的传输信息的有效性越高。
由于（n,k）线性分组，线性分组码的
个码字组成了n维线性空间的一个k维子空间。
因此这
个码字完全可由k个线性无关的矢量所组成。
设此k个矢量为
，有生成矩阵形式为：
（2）
（n,k）码字中的任一码字
均可由这组基底的线性组合生成，即：
Ci=[CnCn-1Cn-2……Cn-k]·G（3）
上式中[CnCn-1Cn-2……Cn-k]是k个信息元组成的信息组。
表3-1按上式编出的（7，3）码
信息组
码字
000
0000000
001
0010011
010
0100110
011
0110101
100
1001100
101
1011111
110
1101010
111
1111001
对于表3-1给出的（7,3）线性分组码，可将其写成矩阵形式：
（4）
其中，（7,3）线性分组码的生成矩阵为
（5）
3.2（7,3）线性分组码的监督矩阵
（7,3）线性分组码的四个校验元由式
（1）所示的线性方程组决定的，把
（1）式移相有：
（6）
上式的矩阵形式为：
（7）
这里的四行七列矩阵称为（7,3）线性分组码的一致监督矩阵（一致校验矩阵），用H表示，即：
（8）
第四章（7,3）线性分组码的译码
译码器的功能按系统设计要求分为检错译码和纠错译码两种，对于纠错译码，其工作又分为译码成功和译码失败两种状态。
译码成功是只译码器能够在达到译码码字差错概率最小条件下输出一个确切的码字。
译码失败是指译码器不能输出一个确切的码字，通常此时的译码器输出y与检错译码输出相同。
4.1校正子与错误图样
假设接收端收到的码字为R，那么它和原来发送端发送的码字C之间就有可能存在着误差。
即在码组C=[C6C5C4C3C2C1C0]中的任意一位就有可能出错。
这样我们在接收端接收到一个码组是就有可能判断错发送端原来应该要表达的意思。
为了描述数据在传输信道中出现错误的情况，引入了错误图样E，在错误图样中，0代表对应位没有传错，1代表传输错误。
实际上错误图样E就是收序列与发送序列的差。
所以在译码中用接收到的码字R模二加错误图样E就可以得到发送端的正确码字C。
因此译码的过程就是要找到错误图样E。
定义：
校正子S=CHT=（R+E）HT=RHT+EHT=EHT（9）
因为C是编得的正确码字，根据前面所叙述，它和监督矩阵的转置相乘为0。
显然，S仅与错误图样有关，它们之间是一一对应的关系。
找到了校正子S，也就可以找到E。
而与发送的码字无关。
若E=0，则S=0；因此根据S是否为0可进行码字的检错。
如果接收码字R中只有一位码元发生错误，又设错误在第i位。
即
其他的
均为0。
在后面的译码程序中，建立了一个校正子S与错误图样E对应的表。
也就是收到一个R序列，就可以通过计算得到一个校正子，而每一个校正子都对应着一个错误图样E，再通过R模尔加上E，就可以得到正确的码字C。
因为在不同的错误序列R中，同一位码元错误时对应的E是一样的，所以可以利用0000000这个正确的码字让它每位依次错误，来求得它的八个校正子。
而这时的矩阵R就是错误图样E。
这样就算得了8个校正子S。
而这时的错误序列R，就是错误图样E，所以有：
E与S都已经得到，这时就可以建立一个表来将它们一一对应起来了。
H矩阵与（n,k）码的任何一个许用码字进行相乘的结果必等于0。
若不属于许用码字，或有传输差错，且差错位数在（n,k）码纠错能力内，则运算结果将为非0值，此时，可以纠错或检错重发，校正子和错码位置的关系如下：
表4-1校正子和错码的位置关系
S1S2S3
错码位置
S1S2S3
错码位置
001
a0
101
a4
010
a1
110
a5
100
a2
111
a6
011
a3
000
无错码
4.2线性分组码C语言程序代码
#include"stdio.h"
#include"conio.h"
#include"stdlib.h"
main（）
{
inti,j,k,u,m,n,r,B=0,p,t;
intInput[100],h[10]={0},g[10]={0};
inta[10][10],b[10][10],s[10][10],R[10][10];
intG[3][7]={{1,0,0,1,1,1,0},{0,1,0,0,1,1,1},{0,0,1,1,1,0,1}};
intH[4][7]={{1,0,1,1,0,0,0},{1,1,1,0,1,0,0},{1,1,0,0,0,1,0},{0,1,1,0,0,0,1}};
intM[7][4]={{1,1,1,0},{0,1,1,1},{1,1,0,1},{1,0,0,0},{0,1,0,0},{0,0,1,0},{0,0,0,1}};
//生成矩阵G
printf（"给定的生成矩阵G:
\n"）;
for（i=0;i<3;i++）
{for（j=0;j<7;j++）
{printf（"%3d",G[i][j]）;
}printf（"\n"）;
}
//监督矩阵H
printf（"由此可得监督矩阵H:
\n"）;
for（i=0;i<4;i++）
{for（j=0;j<7;j++）
{printf（"%3d",H[i][j]）;
}printf（"\n"）;
}
//监督矩阵的转置矩阵M
printf（"监督矩阵的转置矩阵M:
\n"）;
for（i=0;i<7;i++）
{for（j=0;j<4;j++）
{printf（"%3d",M[i][j]）;
}printf（"\n"）;
}
//编码部分
printf（"请输入信息码,以数字2作为结束!
\n"）;
for（i=0;;i++）
{scanf（"%d",&Input[i]）;
if（Input[i]==2）break;
}
u=i;p=u%3;switch（p）
{
case0:
{u=u/3;printf（"共输入%d位，补0位!
\n",u*3）;break;}
case1:
{Input[i]=0;Input[i+1]=0;u=i+2;u=u/3;
printf（"共输入%d位，补两位!
\n",u*3-2）;break;}
default:
{Input[i]=0;u=i+1;u=u/3;printf（"共输入%d位，补一位!
\n",u*3-1）;break;}
}
i=0;
for（m=0;m{for（n=0;n<3;n++,i++）a[m][n]=Input[i];
}
for（m=0;m{for（n=0;n<3;n++）
{printf（"%3d",a[m][n]）;
}printf（"\n"）;
}printf（"编码矩阵:
\n"）;
for（m=0;m{for（r=0;r<7;r++）
{for（n=0;n<3;n++）
{B+=（a[m][n]*G[n][r]）;
}if（B==2）B=0;if（B==3）B=1;b[m][r]=B;B=0;
}
}
for（m=0;m{for（r=0;r<7;r++）
{printf（"%3d",b[m][r]）;
}printf（"\n"）;
}
//译码部分
for（m=0;m{for（i=0;i<4;i++）
{for（r=0;r<7;r++）
{B+=（b[m][r]*M[r][i]）;
}if（B%2==0）B=0;
elseB=1;s[m][i]=B;B=0;
}}
printf（"伴随式为:
\n"）;
for（m=0;m{for（i=0;i<4;i++）
{printf（"%3d",s[m][i]）;
}printf（"\n"）;
}printf（"伴随式为0,因此没有误码!
\n\n"）;printf（"还原信息码:
\n"）;
for（m=0;m{for（r=0;r<3;r++）
{printf（"%3d",b[m][r]）;
}printf（"\n"）;
}printf（"\n"）;t=getch（）;printf（"****验证部分!
****\n"）;t=1;
while（t!
=2）
{p=1;while（p）
{printf（"请输入码组,每组位数为7的倍数,以2作为结束!
\n"）;for（i=0;;i++）
{scanf（"%d",&Input[i]）;if（Input[i]==2）break;
}if（i%7==0）p=0;else{p=1;printf（"输入不是7的倍数!
请重新输入!
\n"）;}
}
u=i/7;i=0;for（m=0;m{for（n=0;n<7;n++,i++）R[m][n]=Input[i];
}printf（"您的输入为:
\n"）;
for（m=0;m{for（n=0;n<7;n++）
{printf（"%3d",R[m][n]）;
}printf（"\n"）;
}
for（m=0;m{
for（i=0;i<4;i++）
{for（r=0;r<7;r++）
{B+=（R[m][r]*M[r][i]）;
}
if（B%2==1）B=1;elseB=0;s[m][i]=B;B=0;
}
}
printf（"伴随式为:
\n"）;
for（m=0;m{for（i=0;i<4;i++）
{printf（"%3d",s[m][i]）;
}
printf（"\n"）;
}r=0;p=0;B=0;j=0;k=0;for（m=0;m{B=（s[m][0]*1000）+（s[m][1]*100）+（s[m][2]*10）+（s[m][3]）;
if（B==0）printf（"第%d行正确!
\n",（m+1））;elseif（B==1110）
{r=0;
printf（"第%d行,第%d个有误!
\n",（m+1）,（r+1））;
}
elseif（B==111）{r=1;printf（"第%d行,第%d个误!
\n",（m+1）,（r+1））;}
elseif（B==1101）{r=2;printf（"第%d行,第%d个误!
\n",（m+1）,（r+1））;}
elseif（B==1000）{r=3;printf（"第%d行,第%d个误!
\n",（m+1）,（r+1））;}
elseif（B==100）{r=4;printf（"第%d行,第%d个误!
\n",（m+1）,（r+1））;}
elseif（B==10）{r=5;printf（"第%d行,第%d个有误!
\n",（m+1）,（r+1））;}
elseif（B==1）{r=6;printf（"第%d行,第%d个有误!
\n",（m+1）,（r+1））;}
else{printf（"第%d行出错码数等于或大于2个!
\n",（m+1））;p=1;}
if（B!
=0&&p!
=1）
{printf（"修改后的编码\n"）;
R[m][r]+=1;if（R[m][r]==2）R[m][r]=0;for（k=0;k<7;k++）
{printf（"%3d",R[m][k]）;
}
printf（"\n"）;printf（"还原正确的信息码为:
\n"）;for（k=0;k<3;k++）
{printf（"%3d",R[m][k]）;
}printf（"\n"）;
}B=0;
}
printf（"输入数字2结束验证!
按其他键继续验证!
\n"）;
scanf（"%d",&t）;
}
printf（"\n"）;
}
4.3线性分组码编译码流程框图
4.4运行结果分析
图1打开程序显示图
打开程序时显示出给定的生成矩阵G，以及由此可得的监督矩阵H，并显示出监督矩阵的转置矩阵M。
图2自动编码译码显示图
当输入数组
时，数组与生成矩阵G相乘可得编码矩阵。
因为计算机运行没有传输干扰问题，因此编码矩阵即为理想的接受矩阵。
接受矩阵与矩阵M相乘即可得出伴随式，伴随式为零可以得出接受无误，因此可以还原出输入的信息码。
图3验证部分显示图
在许用码组中选出三组，
将第一行第3个数修改为0，第三行第2个和第3个数修改为1。
即输入
作为接受矩阵，用以验证译码检错，纠错能力。
因为已知最小海明距离为3，即能检查出两个错误以及能纠正一个错误。
计算出伴随式，由第一行[1101]与
升级会员 