差错控制编码第二次课3课件.ppt

1、11.5 线性分组码线性分组码 1 基本概念基本概念 分组码分组码 将信息码分组，每组由信码附加若干监督将信息码分组，每组由信码附加若干监督码组成。分组码一般用符号（码组成。分组码一般用符号（n,k）表示，）表示，k为每组信为每组信码位数；码位数；n为每组编码总位数，又称为码长；为每组编码总位数，又称为码长；r=n-k为为每组中监督码元数。每组中监督码元数。代数码代数码 建立在代数学基础上的编码称为代数码。建立在代数学基础上的编码称为代数码。线性码线性码 码组的信息码和监督码间码组的信息码和监督码间约束关系约束关系按一按一组组线性代数方程组线性代数方程组构成。线性码是一种代数码。构成。线性码是

2、一种代数码。由此可见，将分组码和线性码的概念结合一起，即由此可见，将分组码和线性码的概念结合一起，即为线性分组码。为线性分组码。0021aaann回顾奇偶监督码回顾奇偶监督码在接收端解码时，实际上就是在计算在接收端解码时，实际上就是在计算021aaaSnn若若S0，认为无错，认为无错若若S1，认为有错，认为有错S只有两种取值，只能代表有、无错两种信息，只有两种取值，只能代表有、无错两种信息，不能指出错码位置。不能指出错码位置。监督关系式监督关系式校正子校正子在（在（n,k）码中，为能纠正一位错误要求）码中，为能纠正一位错误要求nr 1212rkr在（在（n,k）码中，）码中，k=4。为能纠正一

3、位错码，。为能纠正一位错码，则则r至少应为多少？至少应为多少？举例说明如何构造监督关系式：举例说明如何构造监督关系式：上例中，若取上例中，若取r=3，则，则n=k+r=7。(7,4)线性分组码（线性分组码（a6 a5 a4 a3 a2 a1 a0)校正子与错码位置的对应关系如表规定校正子与错码位置的对应关系如表规定(也可也可以另外规定以另外规定)。S1S2S3错码位置错码位置S1S2S3错码位置错码位置001a0101a4010a1110a5100a2111a6011a3000无错无错由表可见，当一错码位置在由表可见，当一错码位置在a2,a4，a5或或a6时校时校正子正子S1为为1；否则；否则

4、S1为为0即构成如下关系即构成如下关系24561aaaaS13562aaaaS03463aaaaS01356aaaa00346aaaa02456aaaa由此解出由此解出3561aaaa3460aaaa4562aaaa给定信息位后，可直接按上式算出监督位给定信息位后，可直接按上式算出监督位监督方监督方程程信息位监督位信息位监督位a6a5a4a3a2a1a0a6a5a4a3a2a1a0000000010001110001011100110000101011010010001111010110010100110110000101011011101010011001111101000111000111

5、11112、监督矩阵监督矩阵H和生成矩阵和生成矩阵G 010011010010101100010111012345601234560123456aaaaaaaaaaaaaaaaaaaaa01356aaaa00346aaaa02456aaaa改写为改写为0001011001110101011101000123456aaaaaaa(模模2)简记为简记为 或或TTHA00TAH101100111010101110100H称为称为监督矩阵监督矩阵IrPH001010100101111011110H矩阵的各个行是线性无关的矩阵的各个行是线性无关的行数行数=监督位数，列数监督位数，列数=码字长度码字长度典

6、型阵典型阵r 行行n列列3561aaaa3460aaaa4562aaaa345620111aaaaa345611011aaaaa345601101aaaaa3456012101111011110aaaaaaaQaaaaaaaaaaa34563456012011101110111转置得转置得K行行r列列0111011101110001001001001000QIGkQ=PT，在，在Q矩阵的左边在加上一个矩阵的左边在加上一个kk的的单位矩阵，就形成了一个新矩阵单位矩阵，就形成了一个新矩阵G：典型形式典型形式生成矩阵生成矩阵K行行n列列称为生成矩阵称为生成矩阵生成矩阵生成矩阵G的每一行都是一个码组的

7、每一行都是一个码组 Gaaaaaaaaaaaaaaa3456345601234560111011101110001001001001000G为典型生成矩阵，则得到的码为系统码为典型生成矩阵，则得到的码为系统码否则得到的码为非系统码否则得到的码为非系统码例【例【1】已知线性（已知线性（6，3）码的生成矩）码的生成矩阵为阵为 100101010011001110G 求（求（1）信息码组为信息码组为101对应的编码码组对应的编码码组 （2）所有许用码组、各码组的码重、）所有许用码组、各码组的码重、最小码距和该码的差错控制能力最小码距和该码的差错控制能力。00000101001110010111011

8、1B0 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列出所有许用码组并求监督矩阵列出所有许用码组并求监督矩阵例例3课后习题课后习题9-61、写出监督方程、写出监督方程2、由监督方程求出所有许用码组、由监督方

9、程求出所有许用码组3、求生成矩阵、求生成矩阵4、最小码距？只用于检错，能检出几、最小码距？只用于检错，能检出几位错码？只用于纠错？同时用于检错位错码？只用于纠错？同时用于检错和纠错？和纠错？若发送码组为若发送码组为021,aaaAnn021,bbbBnn021,eeeABEnniiiiibabae,1,0表示该位接收码元无错；表示该位接收码元无错；表示该位接收码元有错。表示该位接收码元有错。3、译码、译码接收码组为接收码组为二者之差为二者之差为E称为错误图样称为错误图样 接收端译码时计算接收端译码时计算SEHEHAHHEABHTTTTT)(错误图样与校正子之间有确定的关系错误图样与校正子之间有

10、确定的关系无错时，无错时，S等于零等于零有错，有错，S不等于零。不等于零。校正子校正子(伴随式伴随式)纠错纠错-只纠一位错误时只纠一位错误时.21niHHHHH.0121eeeeEnnniinnnTHeHeHeHeHES02211.例例4 设 验证验证3个接收码组是否发生差错？个接收码组是否发生差错？若在某码组中有错码，错码的校正子是什么？然若在某码组中有错码，错码的校正子是什么？然后再指出发生错码的码字中，哪位有错？后再指出发生错码的码字中，哪位有错？100101010110001011H1011101B1101012B1100003B且有且有3个接收码组个接收码组解：解：1）若无错，则错误

11、图样为）若无错，则错误图样为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=1000101，确，确定收到的码组是否有错，并纠正。定收到的码组是否有错，并纠正。4、汉明码、汉

12、明码（1）码长满足）码长满足12 rn（2）最小码距）最小码距d0=3（3）编码效率）编码效率nrrnkRrr11212 9.4 线性分组码线性分组码 我们把我们把建立在代数学基础上的编码建立在代数学基础上的编码称为代数码。称为代数码。在代数码中，常见的是线在代数码中，常见的是线性码。性码。线性码中信息位和监督位是由一线性码中信息位和监督位是由一些线性代数方程联系着的，或者说，线些线性代数方程联系着的，或者说，线性码是按一组线性方程构成的。性码是按一组线性方程构成的。本节将以汉明本节将以汉明(Hamming)码为例引码为例引入线性分组码的一般原理。入线性分组码的一般原理。回顾奇偶监督码在接收端

13、解码时，实际上回顾奇偶监督码在接收端解码时，实际上就是在计算就是在计算若若S0，认为无错；若，认为无错；若S1，认为有错。，认为有错。上式称为监督关系式，上式称为监督关系式，S称为校正子。称为校正子。S只只有两种取值，有两种取值，只能代表有、无错两种信只能代表有、无错两种信息，不能指出错码位置息，不能指出错码位置。如果监督位增加一位，则增加一个监督关如果监督位增加一位，则增加一个监督关系式。系式。两个校正子的可能值有两个校正子的可能值有4种组种组合：合：00，01，10，11，故能表示，故能表示4种不同种不同状态。状态。0021aaann021aaaSnn 若用其一种表示无错，则其余若用其一种

14、表示无错，则其余3种就可能种就可能用来指示一位错码的用来指示一位错码的3种不同位置。同理种不同位置。同理r个监督关系式能指示一位错码的个监督关系式能指示一位错码的(2r-1)个个可能位置可能位置。一般地，若码长为一般地，若码长为n，信息位数为，信息位数为k，则监，则监督位数督位数r=n-k。如果希望用。如果希望用r个监督位构个监督位构造出造出r个监督关系式来指示一位错码的个监督关系式来指示一位错码的n种可能位置，则要求种可能位置，则要求 2r-1 n，或者，或者 2r r+k+1举例说明如何构造监督关系式：举例说明如何构造监督关系式：设设(n，k)分组码中分组码中k=4。为了纠正一位错。为了纠

15、正一位错码，要求监督位数码，要求监督位数r 3。若取。若取r=3，则，则n=k+r=7。校正子与错码位置的对应关。校正子与错码位置的对应关系如表系如表94规定规定(也可以另外规定也可以另外规定)。S1S2S3错码位置错码位置S1S2S3错码位置错码位置001a0101a4010a1110a5100a2111a6011a3000无错无错由表可见，由表可见，当一错码在当一错码在a2,a4，a5或或a6时校正子时校正子S1为为1；否则；否则S1为为0.a2,a4，a5和和a6构成偶数监督关系。构成偶数监督关系。即构成如下关系即构成如下关系:同理同理24561aaaaS13562aaaaS03463a

16、aaaS在发送端编码时，信息位在发送端编码时，信息位a6a5a4a3的值决定于的值决定于输入信号，因此它们是随机的。监督值输入信号，因此它们是随机的。监督值a2a1ao应根据信息位的取值按监督关系来确定即监应根据信息位的取值按监督关系来确定即监督位应使上三式中的值为零督位应使上三式中的值为零(表示编成的码组表示编成的码组中应无错码中应无错码)，由此得到方程组，由此得到方程组01356aaaa00346aaaa02456aaaa由此解出由此解出1653aaaa3460aaaa4562aaaa给定信息位后，可直接按上式算出监督位，其给定信息位后，可直接按上式算出监督位，其结果如表结果如表95所列。

17、所列。信息位信息位监督位监督位信息位信息位监督位监督位a6a5a4a3a2a1a0a6a5a4a3a2a1a00000000100011100010111001100001010110100100011110101100101001101100001010110111010100110011111010001110001111111 接收端收到每个码组后，先按监督方程接收端收到每个码组后，先按监督方程计算出计算出S1、S2、S3，再按表，再按表94判断判断错码情况。例：接收错码情况。例：接收0000011，可得：，可得：S1S2S3=011。由表。由表94可知在可知在a3位有错位有错码。码。(

18、7，4)汉明码：汉明码：l最小码距最小码距d0=3l纠一个错码或检测两个错码。纠一个错码或检测两个错码。l编码效率编码效率k/n=(2r-1-r)(2r-1)=I-rn。当当n很大时，则编码效率接近很大时，则编码效率接近1。线性分组码的线性分组码的般原理。线性分组码是般原理。线性分组码是指信息位和监督位满足一组线性方程的指信息位和监督位满足一组线性方程的编码。编码。改写为改写为01356aaaa00346aaaa02456aaaa654321011101000aaaaaaa654321011010100aaaaaaa654321010110010aaaaaaa00010110011101010

19、11101000123456aaaaaaa(模模2)简记为简记为 或或TTHAO0TAH101100111010101110100H称为监督矩阵称为监督矩阵1110 1001101 0101011 001rHP IH矩阵的各个行是线性无关的矩阵的各个行是线性无关的行数行数=监督位数，列数监督位数，列数=码字长度码字长度典型阵典型阵3561aaaa3460aaaa4562aaaa345620111aaaaa345611011aaaaa345601101aaaaa3456012101111011110aaaaaaa 21065436543111110101011a a aa a a aa a a

20、aQ转置得转置得TQP其中：其中：矩阵P Gaaaaaaaaaaaaaaa3456345601234560111011101110001001001001000QIGknk0111011101110001001001001000称为典型称为典型生成矩阵生成矩阵GaaaaA3456生成矩阵生成矩阵G的每一行都是一个码组。的每一行都是一个码组。例如，（参照前页矩阵例如，（参照前页矩阵G）。）。利用生成矩阵，码字利用生成矩阵，码字TTHA0再由再由 得，得，0TTTMHGMGHMG0THGH和和G互为正互为正交关系交关系译码译码,若发送码组为若发送码组为接收码组为接收码组为二者之差为二者之差为其中其

21、中E称为错误图样。称为错误图样。021,aaaAnn021,bbbBnn021,eeeABEnniiiiibabae,1,0表示该位接收码元无错；表示该位接收码元无错；表示该位接收码元有错。表示该位接收码元有错。接收端译码时计算接收端译码时计算当接收码组无错时当接收码组无错时S等于零等于零有错但不超过检错能力时，有错但不超过检错能力时，S不等于零。不等于零。在错码超过检错能力时，在错码超过检错能力时，B变为另一许用码变为另一许用码组，仍能成立组，仍能成立S等于零。这样的错码是不可等于零。这样的错码是不可检测的。检测的。S称为校正子称为校正子(伴随式伴随式)。S只与只与E有关，而与有关，而与A无

22、关，意味着无关，意味着S与与E有的线性变换关系，能有的线性变换关系，能与与E一一对应，可指示错码位置。一一对应，可指示错码位置。SEHEHAHHEABHTTTTT)(线性码重要性质之一，是它具有封闭性。线性码重要性质之一，是它具有封闭性。若：若：A1和和A2是线性码中的两个许用码组，是线性码中的两个许用码组，则：则：(A1+A2)仍为其中的一个码组。仍为其中的一个码组。由封闭性，两个码组之间的距离必是另由封闭性，两个码组之间的距离必是另一码组的重量。故码的最小距离即是码一码组的重量。故码的最小距离即是码的最小重量的最小重量(除全除全“0”码组外码组外)。线性码又称群码，这是由于线性码的各线性码

23、又称群码，这是由于线性码的各许用码组构成代数学中的群。许用码组构成代数学中的群。9.3.4 9.3.4 线性分组码的译码线性分组码的译码 码字码字Ci 接收接收字字R Ci的估值的估值 干扰干扰 1.1.差错图案差错图案 线性分组码线性分组码 C 的任一码字的任一码字Ci=(ci 1,ci 2,cin)经信道经信道传输后，接收到字传输后，接收到字 R=(r 1,r 2,rn)；令；令 E=R-Ci=(r 1-ci1,r2-ci2,rn-cin);这里称这里称 E 为差错图案为差错图案。根据模根据模2运算的性质，运算的性质，E=R+Ci E=0 则则R是码是码C 的码字；否则，的码字；否则，R不

24、是码不是码C 的码字。的码字。对于二元对于二元(n,k)码码，差错图案差错图案E 的分量中的分量中“1”的个数即的个数即为接收码字为接收码字R 差错的个数差错的个数。差错图案出现差错图案出现 t 个差错的图案数量为个差错的图案数量为Cnt。信道信道译码器译码器2.2.伴随式伴随式 根据根据 Ci H T=0 1(n-k)及及 R=Ci+E，R H T=(Ci+E)H T=Ci H T+E H T=E H T 令令 S=R H T 或或 S=E H T ;这里这里 S=(s1,s2,sn-k)这里称这里称 S 为伴随式为伴随式。伴随式伴随式 S 仅与接收字仅与接收字R 或差错图案或差错图案E 有

25、关，与码字有关，与码字Ci 无关。无关。由于伴随式由于伴随式S是是n-k 维矢量，故不同维矢量，故不同S的个数只有的个数只有2n-k 个；而接收字个；而接收字R 或差错图案或差错图案 E 有有 2 n 个，因此，不同的接收个，因此，不同的接收字字R 或差错图案或差错图案E 有相同的伴随式有相同的伴随式 S.例例 (5,2)线性分组码线性分组码 1生成矩阵生成矩阵G 2 校验矩阵校验矩阵H3编码码字编码码字:00000 01101 10111 11010 dmin=34差错图案差错图案E出现出现 0 个差错的个差错的 1个个:00000 出现出现 1 个差错的个差错的 5个个:00001 000

26、10 00100 01000 10000出现出现 2 个差错的个差错的10个个:00011 00110 01100 11000 00101 01010 10100 01001 10010 10001 1011011101G 100110100100111H5伴随式伴随式S=R HT=E HT 00000000 00001001 00011011 00010010 00110110 00100100 01100001 01000101 11000010 10000111 00101101 01010111 10100011 01001100 10010101 10001110 100010001

27、101111THE SE SE S3.3.线性分组码的译码原理线性分组码的译码原理 生成矩阵生成矩阵G 或校验矩阵或校验矩阵H确定后，就可以解决编码问确定后，就可以解决编码问题。码字经过信道传输后，接收端获得的只有题。码字经过信道传输后，接收端获得的只有R，而，而 Ci 未未知的，因此知的，因此E也是未知的也是未知的.如何根据如何根据H和和R进行译码，进行译码，1如果接收字无差错，则如果接收字无差错，则 R=Ci，则，则S=R H T=0；2如果接收字有差错，当差错如果接收字有差错，当差错dmin时，则时，则S=RH T0；3当码字当码字Ci 错为另一个码字时错为另一个码字时,则则 S=RH

28、T=0。结论：结论：如果如果S0，则接收字有差错；如果，则接收字有差错；如果 S=0，不能肯定接，不能肯定接收字无差错。收字无差错。在有扰信道情况下，找到一个绝对无错的译码方案是在有扰信道情况下，找到一个绝对无错的译码方案是不可能的，不可能的，只能选择一种译码错误概率最小的译码方案。只能选择一种译码错误概率最小的译码方案。无论无论S0 或或 S=0，均按最小距离原理译码。，均按最小距离原理译码。4.4.伴随式译码伴随式译码 1根据根据H计算出与各种差错图案计算出与各种差错图案E 对应的伴随式对应的伴随式S；2接收到码字接收到码字R，计算，计算 S=RH T；3根据根据 S,查找与对应的差错图案

29、或陪集头查找与对应的差错图案或陪集头E；4计算计算 C=R+E,则则 C 被认为是发送的码字。被认为是发送的码字。前例前例 根据根据H计算差错图案对应的伴随式计算差错图案对应的伴随式S 若接收字若接收字 R=(10101)，则，则 S=RHT=(010)查表得查表得 S=(010)E=(00010)译码译码 C=R+E=(10101)+(00010)=(10111)(n,k)线性分组码，当线性分组码，当 n,k 较大时译码表，译码器较大时译码表，译码器变得很复杂。变得很复杂。S000001010100101111011110E0000000001000100010001000100000001

30、1001109.3.6 9.3.6 完备码完备码 二元二元(n,k)线性分组码能纠正线性分组码能纠正 2n-k个差错图案，包括无个差错图案，包括无错的差错图案错的差错图案.二元二元(n,k)码的接收字码的接收字R 有有 2n 个个,码字码字Ci 的个数为的个数为2k 个，伴随式个，伴随式S 最多有最多有 2n-k 个，差错图案个，差错图案 E 有有 2n 个个,但只能但只能纠检错纠检错 2n-k 个。个。差错为差错为0图案图案Cn0，差错为，差错为1图案图案Cn1,差错为差错为t图案图案Cnt。若二元若二元(n,k)线性分组码纠错能力为线性分组码纠错能力为 t,则对差错数小于则对差错数小于等于

31、等于 t 的差错图案的差错图案均应有一个伴随式均应有一个伴随式与之对应与之对应。因此，。因此，若若 则称二元则称二元(n,k)线性分组码为线性分组码为完备码完备码 tiintnnnnknCCCCC02102 tiinknC021.Hamming码码 若二元若二元(n,k)线性分组码纠错能力为线性分组码纠错能力为1，试求是否有完，试求是否有完备码备码。因为因为 Cn01，Cn1n，所以，所以 2n k=1+n 令令 n=2nk-1 ,k=2nk-1-(n-k)再令再令 m=n-k 则则 n=2m1,k=2m 1 m,m=3,4,5,这种形式二元这种形式二元(n,k)线性分组码称为线性分组码称为H

32、amming码码,它是它是一类完备码一类完备码,其其 最小距离最小距离 dmin=3,纠错能力纠错能力 t=1；编码效率编码效率 R=(2m 1 m)/(2m1)。当当 m=3,4,5,6,7,8,时时,有有 (7,4),(15,11),(31,26),(63,57),(127,120),例例 (7,4)线性分组码线性分组码 1生成矩阵生成矩阵G 2 校验矩阵校验矩阵H3码字码字:0000000 0001011 0010110 0011101 11111114差错图案差错图案E 与伴随与伴随式式S 1101000011010011100101010001G 100010001110011111101THE0000000 0000001 0000010 0000100S000001010100E0001000 0010000 0100000 1000000S011110111101