这样,一个k比特信息的线性分组码可以映射到一个长度为n码组上,该码组是从个
码组构成的码集中选出来的,这样剩下的码组就可以对这个分组码进行检错或纠错。
2.码重(汉明重量)
把码组中非零位的数量定义为码重。
3.码距(汉明距离)
两个码组对应位上数字不同的个数称为码组的距离,简称码距。
原则是,让选择的这些码字的码距越长越好。
码组集合中全体码组之间距离中最小的数值称为该码组集合的最小码距。
对于线性分组码来说最小码距等于他的最小重量。
4.最小码距与码的抗干扰能力之间的关系
通过证明(不给出详细的证明过程),可以得到如下的结论,具体如下:
(1)为了检测e个错误,要求最小码距
。
(2)为了纠正t个错误,要求最小码距
。
(3)为了纠正t个错误,同时检测e个错误,要求最小码距
。
最小码距是线性分组码重要的参数,它反映了线性分组码的抗干扰能力。
5.主要性质
(1)封闭性:
任意两个码组之和仍为一许用码组;
(2)有零元:
即全零码;
(3)结合律,交换律成立。
二.编码原理
已知线性分组码的生成矩阵
因为
(1)
所以,由
(1)式可以得到编码方程组:
(2)
(7,3)线性分组码有三位信息码,四位监督码。
三位二进制信息码
可能的八种情况:
000,001,010,011,100,101,110,111。
将信息码代入以上方程组
(2),即可得到监督码,在信息码后面附加上监督码就可得到许用码组,许用码组也就是编码结果,是通过这样的计算从
个码组中挑选出来的
可用的码组,其余的
个码组称为禁用码组。
对于不同的生成矩阵可以得到不同编码方程,也就可以得到不同的的许用码组,任意两个许用码组之和仍为一个许用码组。
通过这条性质,可以检验我们计算出的许用码组的理论值是否正确。
信息码、监督码、许用码组之间的对照关系如下表1所示,由下表既得编码结果的理论值。
表1信息码、监督码、许用码组对照表
信息码C6C5C4
监督码C3C2C1C0
许用码组
000
0000
001
1101
010
0111
011
1010
100
1110
101
0011
110
1001
111
0100
三.译码原理
1.译码原理简述
为了描述数据在传输信道中出现差错的情况,引入错误图样的概念。
错误图样:
接受序列与发送序列之间的差,用E表示。
在错误图样中,0表示对应为没有错误,1表示传输有错。
可见,在译码中,只要设法从接收到的码字R中找到错误图样E,就可恢复发送端发送的码字C,C=R-E,因此,译码的任务就是要找到错误图样E。
首先,假定(7,3)线性分组码中,发送的码字
,接收的码字
,错误图样
。
若
,说明
与
不同,传输过程中
发生了错误。
所以译码的关键在于找到错误图样E。
2.监督矩阵的计算
已知生成矩阵
(3)
其中
是k阶单位方阵,这里
,
(4)
监督矩阵
(5)
(6)
因为
(7)
所以由(4)式可得:
(8)
因此由(5)、(6)、(8)式可得监督矩阵为
(9)
3.伴随式的计算
定义:
其中
;在(7,3)线性分组码中,
。
因为
成立。
所以,伴随式
。
(1)如果接收的码字与发送的码字相同,就是传输中没有差错,此时,错误图样
。
(2)如果接收的码字有一位错误,就有
,这时,S等于H的某一列,也就是其转置矩阵
的某一行。
(3)如果接收到的码字有两个或多个错误时,S与
举证的任意一行都不相等。
四.编译码的软件实现
1.C语言平台简介
C语言是CombinedLanguage(组合语言)的中英混合简称。
是一种计算机程序设计语言。
它既具有高级语言的特点,又具有汇编语言的特点。
它可以作为工作系统设计语言,编写系统应用程序,也可以作为应用程序设计语言,编写不依赖计算机硬件的应用程序。
各类科研都需要用到C语言,具体应用比如单片机以与嵌入式系统开发。
其语言特点如下:
(1)C是中级语言。
它把高级语言的基本结构和语句与低级语言的实用性结合起来。
C语言可以像汇编语言一样对位、字节和地址进行操作,而这三者是计算机最基本的工作单元。
(2)C是结构式语言。
结构式语言的显著特点是代码与数据的分隔化,即程序的各个部分除了必要的信息交流外彼此独立。
这种结构化方式可使程序层次清晰,便于使用、维护以与调试。
C语言是以函数形式提供给用户的,这些函数可方便的调用,并具有多种循环、条件语句控制程序流向,从而使程序完全结构化。
(3)C语言功能齐全。
具有各种各样的数据类型,并引入了指针概念,可使程序效率更高。
另外C语言也具有强大的图形功能,支持多种显示器和驱动器。
(4)C语言适用范围大。
适合于多种操作系统,如Windows、DOS、UNIX等等;也适用于多种机型。
(5)C语言对编写需要硬件进行操作的场合,明显优于其它解释型高级语言,有一些大型应用软件也是用C语言编写的。
2.C语言实现编译码的思想
(n,k)线性分组码原理就是对k位信息码进行编码,产生n-k位的监督码,监督码与信息码之间呈线性关系,使得k位信息码后附带着n-k位的监督码,从而减少传输过程中的差错。
编码思想如下:
(1)根据给定的生成矩阵G,求得监督码与信息码之间呈线性关系即编码方程。
(2)输入信息码,代入上述编码方程中,得到各监督码。
(3)监督码附带在信息码之后,一起输出,即得到编码结果。
对于(7,3)线性分组码来说,译码思想如下:
(1)根据生成矩阵计算出监督矩阵H,由H计算出伴随式S。
(2)如果S=[0,0,0,0],R1无错。
(3)如果S与H的转置矩阵的某一行相等,则有一个错误,找到相应的错误图样E,则正确的接收到的码字R2=R1+E(二进制异或)。
(4)译出的码为R2的前3位。
(5)如果S不等于H转置的任意一行,则有两个或多个错误,不能得到正确的译码结果。
3.整体流程图
图1整体流程图
4.编码流程图
图2编码流程图
5.译码流程图
图3译码流程图
6.基于C语言程序的设计
就(7,3)线性分组码的编码与译码程序如附录所示:
7.运行与结果分析
(1)初始化界面的设计
图4初始化界面图
通过初始化界面,可以选择编码或译码函数。
(2)正确编码的运行结果
只运行编码函数,可得编码结果如下:
图5输入信息码为000时的译码结果示意图
图6输入信息码为001和010时的译码示意图
图7输入信息码为011和100时的译码示意图
图8输入信息码为101和110时的译码结果示意图
图9输入信息码为111时的译码结果示意图
三位信息码C6C5C4可以有八种可能的情况,即000,001,010,011,100,101,110,111。
通过编码部分程序可以得到的编码结果如上图所示。
观察编码结果,与表1对照,运行程序所得的值与理论值完全相同,程序正确。
(3)输入的码中有非二进制码时的处理结果
图10输入信息码有错时的提醒示意图
(4)由生成矩阵计算出监督矩阵H与其转置矩阵HT:
图11监督矩阵与其转置矩阵的计算示意图
由输入的生成矩阵G,得到监督矩阵H并计算其转置矩阵HT,方法见译码原理。
(5)正确译码的运行结果(由于图太多所以下面每种情况只举一个例子)
图12正确译码结果示例示意图
(6)接收的码字有一位错时(8个许用码组每个码组有一位错码的情况有8种,所以接收到的码字有一位错码时共有64种情况。
下图为其中一例。
)
图13接收到的码字有一位错码示例示意图
(7)接收的码字有两位错码(下图为其中一例)
图14接收的码字有两位错示例示意图
总结
这次课程设计历时二个星期多左右,通过这两个星期的学习,发现了自己的很多不足,自己知识的很多漏洞,看到了自己的实践经验还是比较缺乏,理论联系实际的能力还急需提高。
课程设计是培养我们综合运用所学知识,发现、提出、分析和解决实际问题,锻炼实践能力的重要环节,是对学生实际工作能力的具体训练和考察过程。
此次课程设计主要针对线性分组码编码译码提出自己的设计方案,并利用C语言来实现自己的软件设计。
设计中用到了很多计算机通信课程中学到的知识,例如:
差错控制技术等。
由于对所学概念掌握的不准确,原理不是很清晰,虽然条条框框的理论知识一大推,但由于没有经过实践的检验,当正式用时却不知道怎么用,更不知道该往哪用,从而导致在设计的过程中不能抓住重点,不清楚到底该怎么做,使得在设计过程中绕了许多弯路,做了许多的无用功。
设计过程中查阅了大量的有关线性分组码编码与译码的书籍,巩固了以前所学过的知识,而且学到了很多在书本上所没有学到过的知识。
通过这次课程设计使我懂得了理论与实际相结合的必要性,只有理论知识是远远不够的,它更多的只是用来应付考试,而当正真实际操作时却是困难重重,所以只有把所学的理论知识与实践相结合起来,并从理论中得出结论,才能真正为社会服务,从而提高自己的实际动手能力和独立思考的能力。
在设计过程中遇到的问题,可以说得是很多,例如刚开始时,对线性分组码的理解不是很透彻,不知道其编码与译码的方法;后来刚熟悉了原理,却因为对C语言知识掌握不扎实,编写不出来正确的程序,以致又花费了好多时间继续学习C语言编程和上网查找相关资料,导致恶性循环,待编好程序时已费了很多功夫,这毕竟跟平时的理论知识有着很大的关联,故在以后的学习中一定要稳扎稳打,深刻理解理论知识,为今后的实践性活动打下坚实的基础,以免到时又像这次一样再费周折;同时在设计的过程中发现了自己的不足之处,对以前所学过的知识理解得不够深刻,掌握得不够牢固。
总之,通过这次课程设计之后,我发现自己的不足之处还很多,我下去以后一定把以前所学过的知识重新温故。
对我而言,知识上的收获重要,精神上的丰收更加可喜。
让我知道了学无止境的道理。
我们每一个人永远不能满足于现有的成就,人生就像在爬山,一座山峰的后面还有更高的山峰在等着你。
挫折是一份财富,经历是一份拥有。
这次课程设计必将成为我人生旅途上一个非常美好的回忆!
衷心的向各位老师致以崇高的敬意,谢谢老师!
附录:
参考程序
/*这是(7,3)线性分组码的编译码与验证程序*/
#include
#include
#include
/*函数声明*/
voidBegin();
voidCode();
voidDecoding();
/*主函数*/
main()
{
printf("\n这是(7,3)线性分组码的编译码与验证的软件设计:
\n");
printf("\n");
Begin();
}
voidBegin()
{
charch;
fflush(stdin);
printf("-----------------------------------------\n");
printf("\n");
printf("--输入'c'代表编码函数Code--");
printf("\n");
printf("\n");
printf("--输入'd'代表译码函数Decoding--");
printf("\n");
printf("\n");
printf("-----------------------------------------\n");
ch=getchar();
if(ch=='c')Code();
elseif(ch=='d')Decoding();
}
voidCode()
{
intC1[3],C2[7];
inti;
printf("输入三位信息码:
\n");
for(i=0;i<3;i++)
scanf("%d",&C1[i]);
for(i=0;i<3;i++)
if(C1[i]!
=0&&C1[i]!
=1)
{
printf("输入的信息码有错,请检查后重新选择输入\n");
Begin();
}
for(i=0;i<3;i++)
C2[i]=C1[i];
C2[3]=C1[0]+C1[2];
C2[4]=C1[0]+C1[1]+C1[2];
C2[5]=C1[0]+C1[1];
C2[6]=C1[1]+C1[2];
for(i=0;i<7;i++)
{
if(C2[i]==2)C2[i]=0;
elseif(C2[i]==3)C2[i]=1;
}
printf("编码结果为:
\n");
for(i=0;i<7;i++)
printf("%d",C2[i]);
printf("\n");
printf("______________________________________________\n");
Begin();
}
voidDecoding()
{
intG[3][7],P[3][4],Q[4][3],R1[7],HT[7][3],R2[7],C[3];
intH[4][7]={0},S[4]={0},E[7]={0};
inti,j,n,k,t=0;
printf("\n输入生成矩阵G:
\n");
for(i=0;i<3;i++)
for(j=0;j<7;j++)
scanf("%d",&G[i][j]);
printf("\n计算出矩阵P:
\n");
for(i=0;i<3;i++)
for(j=3;j<7;j++)
P[i][j-3]=G[i][j];
for(i=0;i<3;i++)
for(j=0;j<4;j++)
printf("%20d",P[i][j]);
printf("\n");
printf("计算出矩阵Q:
\n");
for(i=0;i<3;i++)
for(j=0;j<4;j++)
Q[j][i]=P[i][j];
for(i=0;i<4;i++)
{
for(j=0;j<3;j++)
printf("%26d",Q[i][j]);
printf("");
}
printf("\n");
printf("计算监督矩阵H:
\n");
for(i=0;i<4;i++)
for(j=0;j<3;j++)
H[i][j]=Q[i][j];
for(i=0;i<4;i++)
{
j=3;
H[i][i+j]=1;
}
for(i=0;i<4;i++)
{
for(j=0;j<7;j++)
printf("%11d",H[i][j]);
printf("");
}
printf("\n");
printf("计算H的转置矩阵HT:
\n");
for(i=0;i<4;i++)
for(j=0;j<7;j++)
HT[j][i]=H[i][j];
for(i=0;i<7;i++)
for(j=0;j<4;j++)
printf("%20d",HT[i][j]);
printf("\n");
printf("输入接收到的码字R1:
\n");
for(i=0;i<7;i++)
scanf("%d",&R1[i]);
printf("计算伴随式S:
\n");
for(i=0;i<4;i++)
for(j=0;j<7;j++)
S[i]=S[i]+R1[j]*HT[j][i];
for(i=0;i<4;i++)
{
if(S[i]%2==0)S[i]=0;
elseif(S[i]%2==1)S[i]=1;
}
for(i=0;i<4;i++)
printf("%2d",S[i]);
printf("\n______________________________________________\n");
for(i=0;i<4;i++)
t=t+S[i];
/*当S=0时,接收端认为传输无错。
但是实际上,也可能存在多个错误,把此事的错误成为不可就错误。
*/
if(t==0)
{
printf("接收端认为接受的码字R1无错,此时错误图样E为:
");
for(i=0;i<7;i++)
printf("%2d",E[i]);
for(i=0;i<7;i++)
{
R2[i]=R1[i]+E[i];
if(R2[i]==2)R2[i]=0;
}
for(i=0;i<3;i++)
C[i]=R2[i];
printf("\n译码结果C为:
\n");
for(i=0;i<3;i++)
printf("%2d",C[i]);
printf("\n______________________________________________\n");
}
if(t!
=0)
{for(k=0;k<7;k++)
for(j=0,n=0;j<4;j++)
if(S[j]==HT[k][j])
{
n++;
/*S=HT中的某一行时,有一个错误或者多个错误。
若是一个错误,系统可以正确纠正,若是多个错误,按此方法纠错,会做出错误纠正。
*/
while(n==4)
{
E[k]=1;
printf("此时接受的码字有一个错误,错误图样E为:
\n");
for(i=0;i<7;i++)
printf("%2d",E[i]);
for(i=0;i<7;i++)
{
R2[i]=R1[i]+E[i];
if(R2[i]==2)R2[i]=0;
}
for(i=0;i<3;i++)
C[i]=R2[i];
printf("\n译码结果C为:
\n");
for(i=0;i<3;i++)
printf("%2d",C[i]);
printf("\n______________________________________________\n");
Begin();
break;
}
}
}
/*S!
=HT中的任意一行时,系统只能检错不能纠错。
*/
while(k==7)
{
printf("\n此时接收到的码字有错,但不能确定错误图样。
\n");
printf("\n______________________________________________\n");
Begin();
break;
}
}
参考文献
[1]潘新民著.计算机通信技术[M].电子工业出版社.2007,8.
[2]樊昌信著.通信原理[M].国防工业出版社.1999,10.
[3]孙丽华著.信息论与纠错编码[M].电子工业出版社.2005,3.
[4]谭浩强著.C程序设计(第二版).清华大学出版社.1999,12.
[5]王连相著.C/C++程序设计教程.中国铁道出版社.2006,8.