第四章抗干扰二元编码原理及方法3_构造纠错码的基本方法.ppt

4.3 构造纠错码的基本方法 二、纠正一位错误的汉明码 是一种（n，k）分组码 k 个信息码元 + r 个监督码元 = n 个码元（一个汉明码码字） r个监督码元应能监督k个信息码元和r个自身码元中哪个错，以及无错情况，共k+r+1=n+1种状态 1、监督矩阵 例： （7，4）汉明码的监督矩阵[H]为： 编码后的码字可由下列矩阵乘法验证 2、校验矩阵 3、生成矩阵 例： （7，4）汉明码的生成矩阵[H]为： 4、错误概率和编码效率 三、循环码 1、循环码的码字和多项式 2、生成多项式 几种（7，k）循环码 3、生成矩阵和监督矩阵 例：（7，4）循环码的生成多项式 g(x) = x3+x+1 求生成矩阵[G]和监督矩阵[H]，并利用生成矩阵[G]求出（7，4）循环码的所有码字 生成多项式为g(x) = x3+x+1的（7,4）循环码码字表 4、直接利用生成多项式进行循环码编码 例：利用（7，4）循环码的生成多项式 g(x) = x3+x+1，求循环码的所有码字 5、循环码的校验子 （7，4）循环码的生成多项式为 g(x) = x3+x2+1 3）将该循环码字0001011错成0001111，则 4）将该循环码字0001011错成0000011，则 1 1 0 1 0 0 1 0 s0 0 1 1 1 0 1 0 0 s1 1 1 1 0 1 0 0 0 s2 C6* C5* C4* C3* C2* C1* C0* 无差错 校验子 生成多项式为g(x) = x3+x+1的（7,4）循环码校验表 1 1 0 1 0 0 1 0 s0 0 1 1 1 0 1 0 0 s1 1 1 1 0 1 0 0 0 s2 C6* C5* C4* C3* C2* C1* C0* 无差错 校验子 根据校验表译码 例：生成多项式为g(x) = x3+x+1的（7，4）循环码 若接收到循环码字1110011 故纠错得1010011 若该码字是系统码，则译码为1010 得生成矩阵： n = 7，k = 4，r = n – k = 3 1101 由生成多项式 g(x) = x3+x2+1 得监督矩阵： 11101 由检验多项式 h(x) = x4+x3+x2+1 * * 一、简单重复码 1、逐位重复 例三重重复码： 000，111，000，000，111，111，000，111，… 优点：逐位重复的设备很简单 2、分组重复 0100，0100，0100，1101，1101，1101，… 优点：可抗成群连续差错 简单重复码的重复次数应为奇数 简单重复码的优点：检、纠错能力较好 简单重复码的缺点：编码效率低， n重重复码的编码效率： （7，4）汉明码 x1 x2 x3 x4 x5 x6 x7 × × × × ×：信息码元 ：监督码元 监督矩阵的每一行均表示一个监督码元与4个信息码元之间的关系 已知信息码元，根据监督矩阵，由上式求出监督码元，并将监督码元加在信息码元后面，构成汉明码字，即完成编码。汉明码字是一种系统码。 解：由监督矩阵得监督码元与信息码元的关系： 根据上式，对信源序列编码得汉明码字：0110011，1001100，0010110，0101010，0110011，… 对信源序列为0110，1001，0010，0101，0110,… 进行编码 对上例编码得到的汉明码字：0110011，1001100，0010110，0101010，0110011,…进行验证，均为[0] 1 0 0 1 0 1 1 0 s3 0 1 0 1 1 0 1 0 s2 0 0 1 1 1 1 0 0 s1 x7* x6* x5* x4* x3* x2* x1* 无差错 校验子 校验表 1 0 0 1 0 1 1 0 s3 0 1 0 1 1 0 1 0 s2 0 0 1 1 1 1 0 0 s1 x7* x6* x5* x4* x3* x2* x1* 无差错 校验子 例：若接收机收到的汉明码字为：0110111，1011100，0010110，…，求译码输出 解：根据校验子 0110111 1011100 ? [S]=[100] x5*错 ? 0110011 ? 0110 ? [S]=[110] x3*错 ? 1001100 ? 1001 0010110 ? [S]=[000] 无错 ? 0010110 ? 0010 得译码输出：0110，1001，0010，… 汉明码的编