差错控制编码第二次课.pptx

《差错控制编码第二次课.pptx》由会员分享，可在线阅读，更多相关《差错控制编码第二次课.pptx（49页珍藏版）》请在第一文库网上搜索。

1、差错控制编码第二次课在在(n,k)码中码中,为能纠正一位错误要求为能纠正一位错误要求nr 1212rkr在在(n,k)码中码中,k=4。为能纠正一位错码。为能纠正一位错码,则则r至少应为多少？至少应为多少？举例说明如何构造监督关系式举例说明如何构造监督关系式:上例中上例中,若取若取r=3,则则n=k+r=7。(7,4)线性分组码线性分组码(a6 a5 a4 a3 a2 a1 a0)校正子与错码位置得对应关系如表规定校正子与错码位置得对应关系如表规定(也可也可以另外规定以另外规定)。S1S2S3错码位置错码位置S1S2S3错码位置错码位置001a0101a4010a1110a5100a2111a

2、6011a3000无错无错由表可见由表可见,当一错码位置在当一错码位置在a2,a4,a5或或a6时校正时校正子子S1为为1;否则否则S1为为0即构成如下关系即构成如下关系24561aaaaS13562aaaaS03463aaaaS01356aaaa00346aaaa02456aaaa由此解出由此解出3561aaaa3460aaaa4562aaaa给定信息位后给定信息位后,可直接按上式算出监督位可直接按上式算出监督位监督方监督方程程信息位监督位信息位监督位a6a5a4a3a2a1a0a6a5a4a3a2a1a00000000100011100010111001100001010110100100

3、0111101011001010011011000010101101110101001100111110100011100011111112、监督矩阵监督矩阵H和生成矩阵和生成矩阵G 010011010010101100010111012345601234560123456aaaaaaaaaaaaaaaaaaaaa01356aaaa00346aaaa02456aaaa改写为改写为0001011001110101011101000123456aaaaaaa(模模2)简记为简记为 或或TTHA00TAH101100111010101110100H称为监督矩阵称为监督矩阵IrPH0010101001

4、01111011110H矩阵得各个行就是线性无关得矩阵得各个行就是线性无关得行数行数=监督位数监督位数,列数列数=码字长度码字长度典型阵典型阵r 行行n列列3561aaaa3460aaaa4562aaaa345620111aaaaa345611011aaaaa345601101aaaaa3456012101111011110aaaaaaaQaaaaaaaaaaa34563456012011101110111转置得转置得K行行r列列0111011101110001001001001000QIGkQ=PT,在在Q矩阵得左边在加上一个矩阵得左边在加上一个kk得单得单位矩阵位矩阵,就形成了一个新矩阵就

5、形成了一个新矩阵G:典型形式典型形式生成矩阵生成矩阵K行行n列列称为生成矩阵称为生成矩阵生成矩阵生成矩阵G得每一行都就是一个码得每一行都就是一个码组组 Gaaaaaaaaaaaaaaa3456345601234560111011101110001001001001000G为典型生成矩阵为典型生成矩阵,则得到得码为系统码则得到得码为系统码否则得到得码为非系统码否则得到得码为非系统码例【例【1】已知线性已知线性(6,3)码得生成矩阵为码得生成矩阵为 100101010011001110G 求求(1)信息码组为信息码组为101对应得编码码组对应得编码码组 (2)所有许用码组、各码组得码重、最所有许用

6、码组、各码组得码重、最小码距和该码得差错控制能力小码距和该码得差错控制能力。000001010011100101110111B0 0 00 0 0 0 0 00 0 10 0 1 1 1 00 1 00 1 0 0 1 11 0 0 1 0 10 1 10 1 1 1 0 10 1 0 0 1 11 0 01 0 0 1 0 10 0 1 1 1 01 0 11 0 1 0 1 11 1 01 1 0 1 1 01 1 11 1 1 0 0 0C例例2已知已知(7,4)码得生成矩阵为码得生成矩阵为:0111011101110001001001001000G列出所有许用码组并求监督矩阵列出所有许

7、用码组并求监督矩阵例例3课后习题课后习题9-61、写出监督方程、写出监督方程2、由监督方程求出所有许用码组、由监督方程求出所有许用码组3、求生成矩阵、求生成矩阵4、最小码距？只用于检错、最小码距？只用于检错,能检出几位能检出几位错码？只用于纠错？同时用于检错和错码？只用于纠错？同时用于检错和纠错？纠错？若发送码组为若发送码组为021,aaaAnn021,bbbBnn021,eeeABEnniiiiibabae,1,0表示该位接收码元无错表示该位接收码元无错;表示该位接收码元有错。表示该位接收码元有错。3、译码、译码接收码组为接收码组为二者之差为二者之差为E称为错误图样称为错误图样 接收端译码时

8、计算接收端译码时计算SEHEHAHHEABHTTTTT)(错误图样与校正子之间有确定得关系错误图样与校正子之间有确定得关系无错时无错时,S等于零等于零有错有错,S不等于零。不等于零。校正子校正子(伴随式伴随式)纠错纠错-只纠一位错误时只纠一位错误时.21niHHHHH.0121eeeeEnnniinnnTHeHeHeHeHES02211.例例4 设 验证验证3个接收码组就是否发生差错？个接收码组就是否发生差错？若在某码组中有错码若在某码组中有错码,错码得校正子就是什么？然错码得校正子就是什么？然后再指出发生错码得码字中后再指出发生错码得码字中,哪位有错？哪位有错？100101010110001

9、011H1011101B1101012B1100003B且有且有3个接收码组个接收码组解解:1)若无错若无错,则错误图样为则错误图样为0,S为为000011THBSB1无错10122THBSB2错11033THBSB3错2)S2=H 第1列 E=1 0 0 0 0 0 第1位错同理 S3=H 第3列 E=0 0 1 0 0 0 第3位错TEHS 例例5、已知一、已知一(7,4),监督码元和信息码元之间得监督码元和信息码元之间得关系为关系为:345235613462aaaaaaaaaaaa求求(1)信息码字信息码字I=0 0 1 1时得编码码组时得编码码组 (2)如果接收得码字如果接收得码字B=

10、1000101,确定收确定收到得码组就是否有错到得码组就是否有错,并纠正。并纠正。4、汉明码、汉明码(1)码长满足码长满足12 rn(2)最小码距最小码距d0=3(3)编码效率编码效率nrrnkRrr11212 9、4 线性分组码线性分组码 我们把建立在代数学基础上得编码我们把建立在代数学基础上得编码称为代数码。在代数码中称为代数码。在代数码中,常见得就是线常见得就是线性码。线性码中信息位和监督位就是由性码。线性码中信息位和监督位就是由一些线性代数方程联系着得一些线性代数方程联系着得,或者说或者说,线性线性码就是按一组线性方程构成得。码就是按一组线性方程构成得。本节将以汉明本节将以汉明(Ham

11、ming)码为例引码为例引入线性分组码得一般原理。入线性分组码得一般原理。回顾奇偶监督码在接收端解码时回顾奇偶监督码在接收端解码时,实际上实际上就就是在计算就就是在计算若若S0,认为无错认为无错;若若S1,认为有错。认为有错。上式称为监督关系式上式称为监督关系式,S称为校正子。称为校正子。S只只有两种取值有两种取值,只能代表有、无错两种信只能代表有、无错两种信息息,不能指出错码位置。不能指出错码位置。如果监督位增加一位如果监督位增加一位,则增加一个监督关则增加一个监督关系式。两个校正子得可能值有系式。两个校正子得可能值有4种组种组合合:00,01,10,11,故能表示故能表示4种不同种不同状态

12、。状态。0021aaann021aaaSnn 若用其一种表示无错若用其一种表示无错,则其余则其余3种就可能种就可能用来指示一位错码得用来指示一位错码得3种不同位置。同理种不同位置。同理r个监督关系式能指示一位错码得个监督关系式能指示一位错码得(2r-1)个个可能位置。可能位置。一般地一般地,若码长为若码长为n,信息位数为信息位数为k,则监督位则监督位数数r=n-k。如果希望用。如果希望用r个监督位构造出个监督位构造出r个监督关系式来指示一位错码得个监督关系式来指示一位错码得n种可能种可能位置位置,则要求则要求 2r-1 n,或者或者 2r r+k+1举例说明如何构造监督关系式举例说明如何构造监

13、督关系式:设设(n,k)分组码中分组码中k=4。为了纠正一位错。为了纠正一位错码码,要求监督位数要求监督位数r 3。若取。若取r=3,则则n=k+r=7。校正子与错码位置得对应关。校正子与错码位置得对应关系如表系如表94规定规定(也可以另外规定也可以另外规定)。S1S2S3错码位置错码位置S1S2S3错码位置错码位置001a0101a4010a1110a5100a2111a6011a3000无错无错由表可见由表可见,当一错码在当一错码在a2,a4,a5或或a6时校时校正子正子S1为为1;否则否则S1为为0、a2,a4,a5和和a6构成偶数监督关系。构成偶数监督关系。即构成如下关系即构成如下关系

14、:同理同理24561aaaaS13562aaaaS03463aaaaS在发送端编码时在发送端编码时,信息位信息位a6a5a4a3得值决定于输得值决定于输入信号入信号,因此她们就是随机得。监督值因此她们就是随机得。监督值a2a1ao应应根据信息位得取值按监督关系来确定、即监督根据信息位得取值按监督关系来确定、即监督位应使上三式中得值为零位应使上三式中得值为零(表示编成得码组中表示编成得码组中应无错码应无错码),由此得到方程组由此得到方程组01356aaaa00346aaaa02456aaaa由此解出由此解出1653aaaa3460aaaa4562aaaa给定信息位后给定信息位后,可直接按上式算出

15、监督位可直接按上式算出监督位,其结其结果如表果如表95所列。所列。信息位信息位监督位监督位信息位信息位监督位监督位a6a5a4a3a2a1a0a6a5a4a3a2a1a00000000100011100010111001100001010110100100011110101100101001101100001010110111010100110011111010001110001111111 接收端收到每个码组后接收端收到每个码组后,先按监督方程计先按监督方程计算出算出S1、S2、S3,再按表再按表94判断错码判断错码情况。例情况。例:接收接收0000011,可得可得:S1S2S3=011。由

16、表。由表94可知在可知在a3位有错位有错码。码。(7,4)汉明码汉明码:l最小码距最小码距d0=3l纠一个错码或检测两个错码。纠一个错码或检测两个错码。l编码效率编码效率k/n=(2r-1-r)(2r-1)=I-rn。当当n很大时很大时,则编码效率接近则编码效率接近1。线性分组码得线性分组码得般原理。线性分组码就般原理。线性分组码就是指信息位和监督位满足一组线性方程是指信息位和监督位满足一组线性方程得编码。得编码。改写为改写为01356aaaa00346aaaa02456aaaa654321011101000aaaaaaa654321011010100aaaaaaa654321010110010aaaaaaa0001011001110101011101000123456aaaaaaa(模模2)简记为简记为 或或TTHAO0TAH101100111010101110100H称为监督矩阵称为监督矩阵1110 1001101 0101011 001rHP IH矩阵得各个行就是线性无关得矩阵得各个行就是线性无关得行数行数=监督位数监督位数,列数列数=码字长度码字长度典型阵典型阵3561aaaa