的条件下,信源所需输出数据就可以达到压缩。
信息传输的目标是高效率、高质量地传输信息,而高效率和高质量又常常相矛盾。
本章分析的几个编码定理表明:
通过适当的编码可以把高效率(传输信息的速率无限接近于信道容量)和高质量(传输信息的差错无限接近于零或者失真低于规定的允许值)完美地结合起来。
2.线性分组码的编码
生成矩阵
线性分组码(n,k)中许用码字(组)为2k个。
定义线性分组码的加法为模二加法,乘法为二进制乘法。
即1+1=0、1+0=1、0+1=1、0+0=0;1×1=1、1×0=0、0×0=0、0×1=0。
且码字
与码字
的运算在各个相应比特位上符合上述二进制加法运算规则。
线性分组码具有如下性质(n,k)的性质:
1、封闭性。
任意两个码组的和还是许用的码组。
2、码的最小距离等于非零码的最小码重。
对于码组长度为n、信息码元为k位、监督码元为r=n-k位的分组码,常记作(n,k)码,如果满足2r-1≥n,则有可能构造出纠正一位或一位以上错误的线性码。
下面我们通过(9,4)分组码的例子来说明如何具体构造这种线性码。
设分组码(n,k)中,k=4,为能纠正一位误码,要求r≥5。
现取r=5,则n=k+r=9。
该例子中,信息组为(c5c6c7c8),码字为(c8c7c6c5c4c3c2c1c0).当已知信息组时,按以下规则得到四个校验元,即
C4=c5+c6
C3=c7+c8
C2=c4+c6+c8(式)
C1=c5+c7
C0=c5+c6+c7+c8
这组方程称为校验方程。
(9,4)线性分组码有24(16)个许用码字或合法码字,另有29-24个禁用码字。
发送方发送的是许用码字,若接收方收到的是禁用码字,则说明传输中发生了错误。
为了深化对线性分组码的理论分析,可将其与线性空间联系起来。
由于每个码字都是一个二进制的n重,及二进制n维线性空间Vn中的一个矢量,因此码字又称为码矢。
线性分组码的一个重要参数是码率r=k/n,它说明在一个码字中信息位所占的比重,r越大,说明信息位所占比重越大,码的传输信息的有效性越高。
由于(n,k)线性分组,线性分组码的2k个码字组成了n维线性空间Vn的一个K维子空间。
因此这2k个码字完全可由k个线性无关的矢量所组成。
设此k个矢量为c1,c2,…,ck,有生成矩阵形式为
G=
(3-2)
(n,k)码字中的任一码字ci,均可由这组基底的线性组合生成,即
ci=mi ·G=[mn-1mn-2…mn-k]·G
式中,mi =[mn-1mn-2…mn-k]是k个信息元组成的信息组。
表3-1(9,4)线性分组码
信息组
码字
0000
000000000
0001
000100011
0010
001010101
0011
001111100
0100
0
0101
01011101
0110
0
0111
0
1000
0
1001
11
1010
11
1011
0
1100
0
1101
1
1110
0
1111
1
对于表3-1给出的(9,4)线性分组码,可将写成矩阵形式
[c8c7c6c5c4c3c2c1]=[c8c7c6c5]·
故(9,4)码的生成矩阵为
G=
可以看到,从(9,4)码的码字中,挑选出k=4个线性无关的码字作为码的一组基底,用c=m·G计算得码字。
一个系统码的生成矩阵G,其左边k行k列应是一个k阶单位方阵Ik,因此生成矩阵G表示为
G=[IkP](3-3)
式中,P是一个k×(n-k)阶矩阵。
校验矩阵
表3-1所示的(9,4)线性分组码的四个校验元由式(3-1)所示的线性方程组决定的。
把(3-1)移相,有
C4+c5+c6=0
C3+c7+c8=0
C2+c4+c6+c8=0
C1+c5+c7=0
C0+c5+c6+c7+c8=0
=
上式的矩阵形式为
这里的四行七列矩阵称为(9,4)码的一致校验矩阵,用H表示,即
H=(3-5)
由H矩阵得到(n,k)线性分组码的每一码字
(i=1,2,…,2k),都必须满足由H矩阵各行所确定的线性方程组,即
。
(9,34)码的生成矩阵G中每一行及其线性组合都是(n,k)码的码字,所以有G·HT=0。
由G和H构成的行生成的空间互为零空间,即G和H彼此正交。
H=[PTIr]其右边r行r列组成一个单位方阵。
伴随式与译码
码的距离及纠检错能力
1.码的距离
两个码字之间,对应位取之不同的个数,称为汉明距离,用d表示。
一个吗的最小距离dmin定义为dmin=min{d(ci,cj),i≠j,ci,cj∈(n,k)},两个码字之间的距离表示了它们之间差别的大小。
距离越大,两个码字的差别越大,则传送时从一个码字错成另一码字的可能性越小。
码的最小距离愈大,其抗干扰能力愈强。
2.线性码的纠检错能力
对于任一个(n,k)线性分组码,
(1)若要在码字内检测出e个错误,则要求码的最小距离d≥e+1;
(2)纠正t个错误,则要求码的最小距离d≥2t+1;(3)纠正t个错误同时检测e(≥t)个错误,则要求d≥t+e+1;
伴随式与译码
假设接收端收到的码字为B,那么它和原来发送端发送的码字A之间就有可能存在着误差。
即在码组A={a6a5a4a3a2a1a0}中的任意一位就有可能出错。
这样我们在接收端接收到一个码组是就有可能判断错发送端原来应该要表达的意思。
为了描述数据在传输信道中出现错误的情况,引入了错误图样E,在错误图样中,0代表对应位没有传错,1代表传输错误。
实际上错误图样E就是收序列与发送序列的差。
所以在译码中用接收到的码字B模尔加错误图样E就可以得到发送端的正确码字A。
因此译码的过程就是要找到错误图样E。
定义:
校正子S
S=B*H
=(A+E)*H
=A*H
+E*H
=E*H
因为A是编得的正确码字。
根据前面所叙述,它和监督矩阵的转置相乘为0。
显然,S仅与错误图样有关,它们之间是一一对应的关系。
找到了校正子S,也就可以找到E。
而与发送的码字无关。
若E=0,则S=0;因此根据S是否为0可进行码字的检错。
如果接收码字B中只有一位码元发生错误,又设错误在第i位。
即Ei-1=1,其他的Ei均为0。
在后面的译码程序中,建立了一个校正子S与错误图样E对应的表。
也就是收到一个B序列,就可以通过计算得到一个校正子,而每一个校正子都对应着一个错误图样E,再通过B模尔加上E,就可以得到正确的码字A。
因为在不同的错误序列B中,同一位码元错误时对应的E是一样的,所以可以利用0000000这个正确的码字让它每位依次错误,来求得它的八个校正子。
而这时的矩阵B就是错误图样E。
这样就算得了8个校正子S。
而这时的错误序列B,就是错误图样E,所以有:
E与S都已经得到,这时就可以建立一个表来将它们一一对应起来。
3.线性分组码编码的Matlab仿真
程序流程图
线性分组码编码的Matlab仿真程序流程图如下:
图5-1-1线性分组码编码的Matlab仿真程序流程图
程序执行结果
形成Q矩阵的程序执行结果如下:
图5-1-2形成Q矩阵的程序执行结果
生成可用码组的程序执行结果如下:
图3-1-3生成可用码组的程序执行结果
线性分组码译码的Matlab仿真
程序流程图
线性分组码译码的Matlab仿真程序流程图如下:
图3-2-1线性分组码译码的Matlab仿真程序流程图
程序执行结果
输出无错时显示图如下:
图3-2-2输出无错时显示图
有一位错误输入时的显示图如下:
图3-2-3有一位错误输入时的显示图
有两位错误输入时的显示图如下:
图3-2-4有两位错误输入时的显示图
结果分析
输入无错时的结果分析
由图5-1输出编码结果和正确输入时显示图所示的结果可以看出编码的结果的八种情况和在推导过程中运算的结果是一致的,可以见得程序的编码过程是正确的。
对于译码过程而言,当界面显示“请输入要校验的码字(9位):
”,然后从提示符后输入:
000000000,由于输入的接收码组与编码后的码字一致,它提取了每个码组的前四位,即信息位,由结果看出译码过程是正确的,并没有出现错译的情况,可见程序的译码片段是正确的。
输入一位错误时的结果分析
对于纠错过程而言,当界面显示“请输入要校验的码字(9位):
”。
然后从提示符后输入:
000000001,由图5-2有一位错误输入时的显示图所知,接收码组的第五位发生了错误,经程序纠检错误后改正了接收序列的错误,并且正确译出了信息位。
可见程序的纠错功能也是可以实现的,以上结果进一步证实了,系统译码程序的正确性。
输入错误时的结果分析
当输入B=001000010时,校正子是01110,检测不出错误。
参考文献
[1]孙丽华编.信息论与纠错编码.电子工业出版社.2005,3
[2]郭文彬桑林编.通信原理-基于MATLAB的计算机仿真.北京邮电大学出版社.
[3]苏金明阮沈勇编.MATLAB实用教程(第二版).电子工业出版社.
[4]徐东艳孟晓刚编.MATLAB函数库查询词典.中国铁道出版社.
[5]潘新民编.计算机通信技术.电子工业出版社.
[6]吴玲达李国辉杨冰等编.计算机通信原理与技术.国防科技大学出版社.
总结
通过对线性分组码中的线性分组码的编译码编程实现,了解到线性分组码的构成方式是把信息序列分成每k个码元一段,并由这k个码元按一定规则产生r个校验位,组成长度为n=k+r的码字,用(n,k)表示。
信息码元与校验位之间为线性关系。
并且知道了线性分组码的编码过程信息码元与校验位之间的线性关系实现起来是十分简单的.
对于码组长度为n、信息码元为k位、监督码元为r=n-k位的分组码,如果满足2r-1≥n,则有可能构造出纠正一位或一位以上错误的线性码。
就像本设计的(9,4)分组码的(n,k)中,n=9,k=4,r≥4能纠正一位误码,检测到两位误码。
运用MATLAB语言进行编程,可以较明显的知道编码的过程和译码时出现的错误,码字的最小距离是3时,可以纠正一位错误,当输入特定的两位错误时,该码字还可以纠正这两位错误,这种情况在编程结果的命令窗口中可以明显看到。
线性分组码具有编译码简单,封闭性好等特点,采用差错控制编码技术是提高数字通信可靠性的有效方法,是目前较为流行的差错控制编码技术之一。
致谢
这里,我要郑重地感谢我们的课程设计指导老师。
正是他的耐心指导才让我们能够顺利的完成此次课程设计,在此说声谢谢!
在此,我也要感谢我们的小组成员,以及所有帮助我完成嵌入式程序设计论文的同学们。
在这次的线性分组码课程设计中,老师和同学们在设计思路和设计步骤上给了我很大的帮助,帮我解答疑难问题,给我提供资料,给我提供查阅资料的信息,引导我该如何去思考问题,教会我解决问题的方法。
同时又鼓励我自己学习,老师给我的不仅是知识,是帮助,更是学习的信心和智慧,在这里衷心感谢老师的耐心细心和一丝不苟的帮助。
同时也感谢和我一起课设的同学,这是我们共同努力的结果,衷心的感谢大家对我的帮助和支持。
希望在以后的学习中我们共同学习与成长。
附录
代码
%---初始化k,r,满足分配条件----
flag_in=1;%输入条件标记,若满足条件则跳出循环,否则就一直输入(默认不满足)
while(flag_in)
k=4;
r=5;
i