差错控制编码第二次课详解演示文稿

差错控制编码第二次课详解演示文稿当前第1页\共有49页\编于星期二\22点优选差错控制编码第二次课当前第2页\共有49页\编于星期二\22点在（n,k）码中，为能纠正一位错误要求在（n,k）码中，k=4。为能纠正一位错码，则r至少应为多少？当前第3页\共有49页\编于星期二\22点举例说明如何构造监督关系式：上例中，若取r=3，则n=k+r=7。(7,4)线性分组码（a6a5a4a3a2a1a0)校正子与错码位置的对应关系如表规定(也可以另外规定)。当前第4页\共有49页\编于星期二\22点S1S2S3错码位置S1S2S3错码位置001a0101a4010a1110a5100a2111a6011a3000无错当前第5页\共有49页\编于星期二\22点由表可见，当一错码位置在a2,a4，a5或a6时校正子S1为1；否则S1为0即构成如下关系当前第6页\共有49页\编于星期二\22点由此解出给定信息位后，可直接按上式算出监督位监督方程当前第7页\共有49页\编于星期二\22点信息位监督位信息位监督位a6a5a4a3a2a1a0a6a5a4a3a2a1a00000000100011100010111001100001010110100100011110101100101001101100001010110111010100110011111010001110001111111当前第8页\共有49页\编于星期二\22点2、监督矩阵H和生成矩阵G

改写为当前第9页\共有49页\编于星期二\22点(模2)简记为

或当前第10页\共有49页\编于星期二\22点称为监督矩阵H矩阵的各个行是线性无关的行数=监督位数，列数=码字长度典型阵r行n列当前第11页\共有49页\编于星期二\22点当前第12页\共有49页\编于星期二\22点转置得K行r列当前第13页\共有49页\编于星期二\22点Q=PT，在Q矩阵的左边在加上一个k×k的单位矩阵，就形成了一个新矩阵G：

典型形式生成矩阵K行n列称为生成矩阵生成矩阵G的每一行都是一个码组当前第14页\共有49页\编于星期二\22点G为典型生成矩阵，则得到的码为系统码否则得到的码为非系统码当前第15页\共有49页\编于星期二\22点例【1】已知线性（6，3）码的生成矩阵为

求（1）信息码组为101对应的编码码组（2）所有许用码组、各码组的码重、最小码距和该码的差错控制能力。

当前第16页\共有49页\编于星期二\22点当前第17页\共有49页\编于星期二\22点当前第18页\共有49页\编于星期二\22点例2已知（7，4）码的生成矩阵为：列出所有许用码组并求监督矩阵当前第19页\共有49页\编于星期二\22点例3课后习题9-61、写出监督方程2、由监督方程求出所有许用码组3、求生成矩阵4、最小码距？只用于检错，能检出几位错码？只用于纠错？同时用于检错和纠错？当前第20页\共有49页\编于星期二\22点若发送码组为表示该位接收码元无错；表示该位接收码元有错。3、译码接收码组为二者之差为E称为错误图样当前第21页\共有49页\编于星期二\22点

接收端译码时计算错误图样与校正子之间有确定的关系无错时，S等于零有错，S不等于零。校正子(伴随式)当前第22页\共有49页\编于星期二\22点纠错-----------只纠一位错误时当前第23页\共有49页\编于星期二\22点例4设验证3个接收码组是否发生差错？若在某码组中有错码，错码的校正子是什么？然后再指出发生错码的码字中，哪位有错？且有3个接收码组当前第24页\共有49页\编于星期二\22点解：1）若无错，则错误图样为0，S为0

B1无错B2错B3错2）∵S2=H第1列∴E=[100000]第1位错同理S3=H第3列∴E=[001000]第3位错当前第25页\共有49页\编于星期二\22点例5、已知一（7，4），监督码元和信息码元之间的关系为：求（1）信息码字I=[0011]时的编码码组（2）如果接收的码字B=[1000101]，确定收到的码组是否有错，并纠正。当前第26页\共有49页\编于星期二\22点4、汉明码（1）码长满足（2）最小码距d0=3（3）编码效率当前第27页\共有49页\编于星期二\22点§9.4线性分组码我们把建立在代数学基础上的编码称为代数码。在代数码中，常见的是线性码。线性码中信息位和监督位是由一些线性代数方程联系着的，或者说，线性码是按一组线性方程构成的。

本节将以汉明(Hamming)码为例引入线性分组码的一般原理。当前第28页\共有49页\编于星期二\22点回顾奇偶监督码在接收端解码时，实际上就是在计算若S＝0，认为无错；若S＝1，认为有错。上式称为监督关系式，S称为校正子。S只有两种取值，只能代表有、无错两种信息，不能指出错码位置。如果监督位增加一位，则增加一个监督关系式。两个校正子的可能值有4种组合：00，01，10，11，故能表示4种不同状态。当前第29页\共有49页\编于星期二\22点若用其一种表示无错，则其余3种就可能用来指示一位错码的3种不同位置。同理r个监督关系式能指示一位错码的(2r-1)个可能位置。一般地，若码长为n，信息位数为k，则监督位数r=n-k。如果希望用r个监督位构造出r个监督关系式来指示一位错码的n种可能位置，则要求

2r-1≥n，或者2r≥r+k+1当前第30页\共有49页\编于星期二\22点举例说明如何构造监督关系式：设(n，k)分组码中k=4。为了纠正一位错码，要求监督位数r≥3。若取r=3，则n=k+r=7。校正子与错码位置的对应关系如表9—4规定(也可以另外规定)。S1S2S3错码位置S1S2S3错码位置001a0101a4010a1110a5100a2111a6011a3000无错当前第31页\共有49页\编于星期二\22点由表可见，当一错码在a2,a4，a5或a6时校正子S1为1；否则S1为0.a2,a4，a5和a6构成偶数监督关系。即构成如下关系:同理在发送端编码时，信息位a6a5a4a3的值决定于输入信号，因此它们是随机的。监督值a2a1ao应根据信息位的取值按监督关系来确定．即监督位应使上三式中的值为零(表示编成的码组中应无错码)，由此得到方程组当前第32页\共有49页\编于星期二\22点由此解出给定信息位后，可直接按上式算出监督位，其结果如表9—5所列。当前第33页\共有49页\编于星期二\22点信息位监督位信息位监督位a6a5a4a3a2a1a0a6a5a4a3a2a1a00000000100011100010111001100001010110100100011110101100101001101100001010110111010100110011111010001110001111111当前第34页\共有49页\编于星期二\22点

接收端收到每个码组后，先按监督方程计算出S1、S2、S3，再按表9—4判断错码情况。例：接收0000011，可得：S1S2S3=011。由表9—4可知在a3位有错码。(7，4)汉明码：最小码距d0=3纠一个错码或检测两个错码。编码效率k/n=(2r-1-r)／(2r-1)=I-r／n。当n很大时，则编码效率接近1。当前第35页\共有49页\编于星期二\22点线性分组码的—般原理。线性分组码是指信息位和监督位满足一组线性方程的编码。改写为当前第36页\共有49页\编于星期二\22点(模2)简记为或当前第37页\共有49页\编于星期二\22点称为监督矩阵H矩阵的各个行是线性无关的行数=监督位数，列数=码字长度典型阵当前第38页\共有49页\编于星期二\22点当前第39页\共有49页\编于星期二\22点转置得其中：矩阵P当前第40页\共有49页\编于星期二\22点称为典型生成矩阵当前第41页\共有49页\编于星期二\22点生成矩阵G的每一行都是一个码组。例如，（参照前页矩阵G）。利用生成矩阵，码字再由得，H和G互为正交关系当前第42页\共有49页\编于星期二\22点译码,若发送码组为接收码组为二者之差为其中E称为错误图样。表示该位接收码元无错；表示该位接收码元有错。当前第43页\共有49页\编于星期二\22点

接收端译码时计算当接收码组无错时．S等于零有错但不超过检错能力时，S不等于零。在错码超过检错能力时，B变为另一许用码组，仍能成立S等于零。这样的错码是不可检测的。S称为校正子(伴随式)。S只与E有关，而与A无关，意味着S与E有的线性变换关系，能与E一一对应，可指示错码位置。当前第44页\共有49页\编于星期二\22点

线性码重要性质之一，是它具有封闭性。若：A1和A2是线性码中的两个许用码组，则：(A1+A2)仍为其中的一个码组。由封闭性，两个码组之间的距离必是另一码组的重量。故码的最小距离即是码的最小重量(除全“0”码组外)。线性码又称群码，这是由于线性码的各许用码组构成代数学中的群。当前第45页\共有49页\编于星期二\22点9.3.4线性分组码的译码

码字Ci接收字R

Ci的估值干扰

1.差错图案

线性分组码C的任一码字Ci=(ci1,ci

2,…,cin)经信道传输后，接收到字R

=(r

1,r2,…,rn)；令E=R-Ci=

(r

1-

ci1,r2-ci2,…,rn-cin);

这里称

E为差错图案。根据模2运算的性质，E=R+Ci

E=0则R是码C的码字；否则，R不是码C的码字。对于二元(n,k)码，差错图案E的分量中“1”的个数即为接收码字R差错的个数。差错图案出现t个差错的图案数量为Cnt。信道译码器当前第46页\共有49页\编于星期二\22点2.伴随式根据Ci

H

T=01×(n-k)及R=Ci+E，RH

T

=

(Ci+E)H

T=Ci

H

T+E

H

T=E

H

T

令S=RH

T

或S=E

H

T;这里S=(s1,s2,…,sn-k)这里称S为伴随式。伴随式S仅与接收字R或差错图案E有关，与码字Ci

无关。由于伴随式S是n-k维矢量，故不同S的个数只有2n-k个；而接收字R或差错图案E有2n个，因此，不同的接收字R或差错图案E有相同的伴随式S.

当前第47页\共有49页\编于星期二\22点例(5,2)线性分组码1°生成矩阵G2°

校验矩阵H3°编码码字:00000011011011111010dmin=34°差错图案E出现0

个差错的1个:00000

出现1

个差错的5个:0000100010001000100010000出现2

个差错的10个:0001100110011001100000101010101010001001

10010

10001当前第48页\共有49页\编于星期二\22点5°伴随式S=RHT=

EHT

00000→00000001→00100011→011

00010→010

00110→110

00100→10001100→001