线性码及其应用幻灯片.ppt
《线性码及其应用幻灯片.ppt》由会员分享,可在线阅读,更多相关《线性码及其应用幻灯片.ppt(37页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、线性码及其应用第1页,共37页,编辑于2022年,星期一定义2 码字X=x1x2xn的汉明重量是码字中非零码元的位数,用W(X)表示。例如:W(1001)=2,W(11010)=3由定义1和定义2知 D(X,Y)=W(X-Y)定义3 一组码字C包括若干码字C1,C2,Cn,所有这些码字相互间码距的最小的数值,称为该码组的最小码距d(简称码距d)。d=minD(Ci,Cj)=minW(Ci-Cj)i,j 1,2,N,i j 例如 C=(0111100,1011011,1101001)d=3说明:为尽量避免码字受到干扰而出错,总是希望码字间有尽可能大的距离,最小码距代表了一个码组中最不利的情况。从
2、安全出发,往往选用最小码距来分析码的检错纠错能力。第2页,共37页,编辑于2022年,星期一第二节第二节 检错能力与纠错能力检错能力与纠错能力1、码距为1时,能保证码字的唯一性,但不能检错和纠错。2、码距为2时,能检查出一位错误,但无法纠错。3、码距为3时,能检查出一位或两位错误,并且还可纠正一位错误。例:设码长为3,取000、111作为码字,其余为禁用码字。如接收端收到001,它是禁用码字,知道出错,由于001与000相差一个码元,与111相差两个码元,根据最大似然译码原则将001译为000。最大似然译码原则:当Ci为若干个发送码字中的一个,R为接收码字,若条件概率P(R/Ci)为最大,则认
3、为码字Ci就是发送码字。第3页,共37页,编辑于2022年,星期一结论:结论:(一)、要检出码字中任意e个码元错误,必须使最小码距d满足 d e+1(二)、要纠正码字中任意t个码元错误,必须使最小码距d满足 d 2t+1(三)、要纠正码字中任意t个码元错误,并同时发现e个错误(e t),则最小码距d满足 d t+e+1当码距d=2t+1时,码长为n的一个许用码字中可纠正的错误类型总数为:i=1tC(n,i)许用码字数Q i=0tC(n,i)2n第4页,共37页,编辑于2022年,星期一第三节第三节 寄偶监督码寄偶监督码寄偶监督码是最简单的一种检错码,是目前计算机系统用得最多的一种差错控制码。寄
4、偶监督码的编码方式:是在n-1位信息元Cn-1,Cn-2,C1后面附加1位监督元C0,使得码字中“1”的数目保持为奇数或偶数。奇数监督,对应的监督方程为:Cn-1+Cn-2+C1+C0=1偶数监督,对应的监督方程为:Cn-1+Cn-2+C1+C0=0P169表5-1列出了用七位ASCII码表示的十个数字符号的寄偶校验位。第5页,共37页,编辑于2022年,星期一判别方法:接收端收到编好的寄偶监督码后,用与发送端相同的规则检查“1”的个数是否仍保持奇数或偶数,从而确定传输过程中是否有错误。特点:能发现一位码元或所有奇数位码元出错的情况。但不能纠正任何错误以及发现偶数位码元错误。简单寄偶码的效率高
5、:=n-1n寄偶监督码的实现:1、硬件法:采用模二相加的异或电路。C1C2C3C4C5C6C7C0C0第6页,共37页,编辑于2022年,星期一2、软件法(见P170图5-6的流程图)为了改进差错控制性能,引入二维寄偶监督码(水平-垂直寄偶监督码、方阵码、纵横寄偶监督码)。就是在水平方向进行寄偶监督的同时,再按垂直方向进行一次寄偶监督。如P171图5-7,图5-8(二维水平-斜向寄偶监督码)。二维寄偶监督码特点:能检出每一行或每一列的两位或偶数位错误。可以用水平、垂直两个方向上的监督码元,来确定单个错误码元的位置,从而进行纠正。但它无法检出四个错误码元构成矩形(或平行四边形)四个顶点的错误图样
6、,也无法检出双向成偶的错误图样。第7页,共37页,编辑于2022年,星期一第五节第五节 监督矩阵与生成矩阵监督矩阵与生成矩阵设有待编码的消息序列为M=m1m2mk,对应的信息元序列X1X2Xk。为了进行差错控制,我们按线性代数关系来添加监督码元序列Xk+1Xk+2Xn,则称此码长n,信息元数k的码字序列X1X2Xk|Xk+1Xk+2Xn为线性分组码。记为(n,k),如果其最小码距为d,也可记为(n,k,d)或n,k,d。其中监督元数r=n-k。用线性的监督方程组来表示:a11X1+a12X2+a1kXk=Xk+1a21X1+a22X2+a2kXk=Xk+2ar1X1+ar2X2+arkXk=X
7、n式中加号均表示模二加第8页,共37页,编辑于2022年,星期一或a11X1+a12X2+a1kXk+Xk+1+0+0=0a21X1+a22X2+a2kXk+0+Xk+2+0=0ar1X1+ar2X2+arkXk+0+0+Xn=0若用矩阵表示,则a11 a12 a1k 1 0 0a21 a22 a2k 0 1 0ar1 ar2 ark 0 0 1 X1 X2 Xk Xk+1 Xk=0简写为 HXT=0TH:监督矩阵XT:行矩阵X=X1X2Xn的转置矩阵第9页,共37页,编辑于2022年,星期一例5-1 一个(7,3)码的信息元X1X2X3和监督元X4X5X6X7间的监督方程组为X1+X3+X4
8、=0X1+X2+X3+X5=0X1+X2+X6=0X2+X3+X7=0求出对应信息元的监督元。解:列出各种信息元组合,依据监督方程组求出对应监督元 如下表所示。信息元监督元编成码字0000010100111001011101110000110101111010111000111001010000000000011101010011101110101001110101001111010011110100第10页,共37页,编辑于2022年,星期一还可以写出监督矩阵形式HX =10 1 1 0 0 0 1 1 1 0 1 0 01 1 0 0 0 1 00 1 1 0 0 0 1TX1X2X3X4
9、X5X6X7=0000第11页,共37页,编辑于2022年,星期一说明说明:1、编码中,往往在多种可能的码字排列中,选取少量 的许用码字。2、任意两个码字逐位模二加,可以得到另一个码字。这种特性叫做封闭性。它是线性码的重要特点。3、由封闭性知,两个码字的码距,就是另一个码字 的码重。所以,该组码字的最小码距就等于码字 中码的最小重量。4、监督矩阵H=A|Ir,A为rxk阶矩阵,Ir为r阶单位 阵,r=n-k,H起监督是否是码字的作用。5、在线性码组中,如果有一个码重为W的码字,则 在H中必有与之相应的W列相加等于0,固称此W 列线性相关。如果要求码组的最小码距为d,即要求 码字的最小码重为d,
10、则H中至少有d列相加之和为 0,任意小于或等于d-1列线性无关。第12页,共37页,编辑于2022年,星期一例如:例题中0011101是码字,码重为4,它应该满足监督方程组。即HXT=10 1 1 0 0 0 1 1 1 0 1 0 01 1 0 0 0 1 00 1 1 0 0 0 10011101=1101+1000+0100+0001=0000第13页,共37页,编辑于2022年,星期一下面讨论一下监督矩阵H与生成矩阵G的关系。HXT=A|IrX1X2XkXk+1Xk+2Xn=0T或AX1X2Xk+IrXk+1Xk+2Xk=0T则Xk+1Xk+2Xn=-AX1X2Xk=-Amkm1m2令
11、X1X2Xk=Ikmkm1m2第14页,共37页,编辑于2022年,星期一X1X2Xk=Ik-Am1m2mk两边取转置得X=MGX,M为行矩阵的形式;G=Ik|-AT称为生成矩阵。利用G可由M直接生成码X。以前面的例题为例,知道A,可求出-A T =11 1 00 1 1 11 1 0 1Ik=10 00 1 00 0 1设有信息元组m1m2m3=101则由X=MG求出对应码字1010011G=1 0 0 1 1 1 00 1 0 0 1 1 10 0 1 1 1 0 1可以观察G的三行分别是例5-1求出的第5,3,2个码字第15页,共37页,编辑于2022年,星期一这三个码字组成的G,能使求
12、出的码字信息元在前,监督元在后,即构成的是系统码。如选其他三个码字组合成G,得出的码字信息元与监督元将是交错排列,即非系统码。由H=A|In-k,G=Ik|-A T则HG =A|In-k =A-A=0TIk-A由这个等式可知G的每一行都是一个码字。生成矩阵G和监督矩阵H的关系:一个(n,k)码字的监督矩阵H,正好是另一个(n,n-k)=(n,r)码字的生成矩阵G,反之亦然。我们称(n,n-k)码是(n,k)码的对偶码。可以用下面这个图反映G和H的关系(注意理解)第16页,共37页,编辑于2022年,星期一1 0 0 1 1 1 00 1 0 0 1 1 00 0 1 1 1 0 11 0 1
13、1 0 0 01 1 1 0 1 0 01 1 0 0 0 1 00 0 1 0 0 0 1krkr此处有H(7,4)=G(7,3)或H(7,3)=G(7,4)如H(7,4)=G(7,3)=1 0 0 1 1 1 00 1 0 0 1 1 00 0 1 1 1 0 1可以通过矩阵变换将上面矩阵化为典型监督矩阵形式第17页,共37页,编辑于2022年,星期一第六节第六节 伴随式与标准阵列伴随式与标准阵列设发送的码序列X=X1X2XiXn接收的码序列Y=Y1Y2YiYn两者的差别 E=Y-X=e1e2eien称为差错序列或错误图样用监督矩阵来校验接收到的码字时,有HY =H(X+E)=HX +HE
14、TTTT =HET(X是码字,HX =0)T令S =HY =HETTT则S=EHTS称为伴随式,或校验子,用它来检查接收码字中的错误。P182-184用例5-1的监督矩阵为例讨论了接收端可能遇到的几种错误情况,可以看出一种码的检错和纠错能力受码距的限制,超过此限度就会检不出错误,或者造成误判。注意S是一个r维的行矩阵第18页,共37页,编辑于2022年,星期一标准阵列问题:标准阵列问题:设有一个(n,k)线性码,它共有2 个码字C0,C1,C2,C -1。将它排列成下表所示形式。其中零码矢C0放在第一列,它的下面放置各种错误图样。当监督元有n-k个时,在C0下放有2 -1个错误图样。在C0以后
15、各码字C1,C2,C2 -1的同一列下,各放置一些元素,这些元素为该列码字与相应行的错误图样模二相加而成。我们称同一行的这些元素为陪集,C0下面那些错误图样称为陪集首。每一行对应着唯一的一个伴随式。如果将标准阵列预先存储在接收端,则当接收到某个错误码字序列时,可以按照相应的陪集位于哪一列,而依据最大似然法则将其译成该列之首的那个码字。k2kn-kk注意理解下表中错误图样与伴随式的关系。第19页,共37页,编辑于2022年,星期一C0 C1 C2 C2 -1 伴随式SkE2 E2+C1 E2+C2 E2+C2 -1kE3 E3+C1 E3+C2 E3+C2 -1kE2 E2 +C1 E2 +C2
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 线性 及其 应用 幻灯片
限制150内