第11章差错控制编码祥解.ppt

第7章 数字带通传输系统 通 信 原 理 例如： 发方码组A：0100110 收方码组B：0100010 错码 通过校正子纠错： 监督阵H：（7，4）汉明码： =（100） 即对应的a2位出错， 纠错即可。 或者，查表得到差错图样，同样可以纠错： =（100） … … 只能检错 011 0000011 111 1000000 110 0100000 101 0010000 011 0001000 100 0000100 010 0000010 错1位 并纠错 001 0000001 无错 000 0000000 错码情况 S E 纠错： 【例】 （5，2）线性分组码，已知： （1）监督矩阵H； （2）最小汉明距离d0； （3）若接收到码组为B=（10001），求校正子S； （4）已知B中只有一位错，试纠正。 求： 【解】 （1）监督矩阵H： （2）最小汉明距离d0： ——穷举法 C1=10101 C2=01011 必然包含全零码： C4=00000 由线性码可知： C3=C1+C2=11110 最小汉明距离d0=3 能检 个错； 能纠 个错； 2 1 d0 ? e + 1 d0 ? 2t + 1 （3）若接收到码组为B=（10001），求校正子S； =（100） （4）已知B中只有一位错，试纠正。 补充：汉明码 能够纠正1位错码且编码效率较高的一种线性分组码。 1. 线性码（n，k） 码长——n； 信息位——k； 监督位——r=n-k； 2. r个监督位： 即为r位校正子 r位校正子（监督位）的可能取值： 2r 其中，用“00…0”表示无错； 剩余的(2r-1)则可能指出(2r-1)种一位错码的位置。 一般来说，对于n位码组，如果希望用r个监督位构造出r个监督关系式来指示1位错码，则要求： 例：设分组码(n, k)中k = 4，且能纠正1位错码。 由 监督位数 r ? 3 若取 r = 3，则n = k + r = 7 分组码(7, 4) 3. 码元参数要求 7位码组： 3位校正子： （1）则S1、S2和S3的值与一位错码位置的对应关系： 无错码 000 a3 011 a6 111 a2 100 a5 110 a1 010 a4 101 a0 001 错码位置 S1 S2 S3 错码位置 S1 S2 S3 根据校正子查表确定1位错码位置。 由表中规定可见，仅当一位错码的位置在a2 、a4、a5或a6时，校正子中S1为1；否则S1为零。这就意味着a2 、a4、a5和a6四个码元构成偶数监督关系: 同理， a1、a3、a5和a6构成偶数监督关系： 以及a0、a3、a4 和a6构成偶数监督关系： 无错码 000 a3 011 a6 111 a2 100 a5 110 a1 010 a4 101 a0 001 错码位置 S1 S2 S3 错码位置 S1 S2 S3 （2）（7,4）汉明码的构造 在发送端编码时，信息位a6、a5、a4和a3的值决定于输入信号，因此它们是随机的。 监督位a2、a1和a0应根据信息位的取值按监督关系来确定，即监督位应使上3式中S1、S2和S3的值为0（表示编成的码组中应无错码）。 监督位a2、a1和a0应根据信息位的取值按监督关系来确定，即监督位应使上3式中S1、S2和S3的值为0（表示编成的码组中应无错码）： 上式经过移项运算，解出监督位： 给定信息位后，可以直接按下式算出监督位， 结果见下表： 111 1111 000 0111 100 1110 011 0110 010 1101 101 0101 001 1100 110 0100 001 1011 110 0011 010 1010 101 0010 100 1001 011 0001 111 1000 000 0000 监督位 a2 a1 a0 信息位 a6 a5 a4 a3 监督位 a2 a1 a0 信息位 a6 a5 a4 a3 接收端收到每个码组后，先计算出S1、S2和S3，再查表判断错码情况。 例如，若接收码组为0000011，按公式计算可得：S1 = 0，S2 = 1，S3 = 1。由于S1 S2 S3 等于011，故查表可知在a3位有1错码。 无错码 000 a3 011 a6 111 a2 100 a5 110 a1 010 a4 101 a0 001 错码位置 S1 S2 S3 错码位置 S1 S2 S3 （3）根据校正子进行1位纠错 按照上述方法构造的码称为汉明码。表中所列的(7, 4)汉明码的最小码距d0 = 3。