©安徽科技学院
2015-4-30
第6 页
海明纠错码
2．确定校验码位置
上一步我们确定了对应信息中要插入的校验码位数， 但这还不够，因为这些校验码不是直接附加在信息码 的前面、后面或中间的，而是分开插入到不同的位置 。但不用担心，校验码的位置很容易确定的，那就是 校验码必须是在2n次方位置，如第1、2、4、8、16 、32，……位（对应20、21、22、23、24、25，……， 是从最左边的位数起的），这样一来就知道了信息码 的分布位置，也就是非2n次方位置，如第3、5、6、7 、9、10、11、12、13，……位（是从最左边的位数 起的）。
©安徽科技学院
2015-4-30
第9 页
海明纠错码
3. 确定校验码
p2（第2个校验位，也是整个码字的第2位）的校验规则是： 从当前位数起，连续校验2位，然后跳过2位，再连续校验2 位，再跳过2位，……。这样就可得出p2校验码位可以校验的 码字位包括：第2位（也就是p2本身）、第3位，第6位、第7 位，第10位、第11位，第14位、第15位，……。 p3（第3个校验位，也是整个码字的第4位）的校验规则是： 从当前位数起，连续校验4位，然后跳过4位，再连续校验4 位，再跳过4位，……。这样就可得出p4校验码位可以校验的 码字位包括：第4位（也就是p4本身）、第5位、第6位、第7 位，第12位、第13位、第14位、第15位，第20位、第21位、 第22位、第23位，……。
©安徽科技学院
2015-4-30
第7 页
海明纠错码
2．确定校验码位置
举一个例子，假设现有一个8位信息码，即b1、b2 、b3、b4、b5、b6、b7、b8，由1得知，它需要插入 4位校验码，即p1、p2、p3、p4，也就是整个经过编 码后的数据码（称之为“码字”）共有12位。根据以 上介绍的校验码位置分布规则可以得出，这12位编码 后的数据就是p1、p2、b1、p3、b2、b3、b4、p4 、b5、b6、b7、b8。
©安徽科技学院
2015-4-30
第11页
海明纠错码
4. 校验码计算示例
10011101 1 ？1？001？1101 再求第2个“？”（也就是p2，第2位）的值，根据以上规 则可以很快得出本示例中p2校验码校验的位数是2、3、6 、7、10、11，也是一共6位。这6位中除了第2位（也就是 p2位）不能确定外，其余5位的值都是已知的，分别为：1 、0、1、1、0。现假设采用的是偶校验，从已知的5位码 值可知，也已有3个“1”，所以此时p2位校验码的值必须为 “1”，得出p2=1。1 1 1？001？1101 假设采用的是偶校验
G4G3G2G1=1000 说明第八位出现了错误
©安徽科技学院
2015-4-30
第15页
©安徽科技学院
2015-4-30
第13页
海明纠错码
4. 校验码计算示例
10011101 1 1 1 0 001？1101 最后求第4个“？”（也就是p4，第8位）的值，根据以上 规则可以很快得出本示例中p4校验码校验的位数是8、9、10 、11、12（本来是可以连续校验8位的，但本示例的码字后面 的长度没有这么多位，所以只校验到第12位止），也是一共5 位。这5位中除了第8位（也就是p4位）不能确定外，其余4位 的值都是已知的，分别为：1、1、0、1。现假设采用的是偶 校验，从已知的4位码值可知，已有3个“1”，所以此时p2位 校验码的值必须为“1”，得出p4=1。 1 1 1 0 001 1 1101 假设采用的是偶校验
现假设原来的8位信息码为10011101，因现在还没有求出 各位校验码值，现在这些校验码位都用“？”表示，最终 的码字为：？？1 ？001 ？1101。
©安徽科技学院
2015-4-30
第8 页
海明纠错码
3. 确定校验码
第i位校验码从当前位开始，每次连续校验i（这里是数 值i，不是第i位，下同）位后再跳过i位，然后再连续 校验i位，再跳过i位，以此类推。最后根据所采用的是 奇校验，还是偶校验即可得出第i位校验码的值。
奇偶校验码
奇偶校验码
串行数据在传输过程中，由于干扰可能引起信息的出错， 例如，传输字符‘E’，其各位为： 0100，0101=45H D7 D0由于干扰，可能使位变为1这种情况，我们称为出现 了“误码”。
奇偶校验码分为奇校验和偶校验两种。偶 校验就是让信息位和冗余位中‘1’的个数为 偶数；奇校验就是让‘1’的个数为奇数。 假设：要发送的信息位为 奇偶校验位为
©安徽科技学院
2015-4-30
第2 页
奇偶校验码
1、如果进行偶校验，则有 2、如果进行奇校验，则有
©安徽科技学院
20码
海明码（Hamming Code）是一个可以有 多个校验位，具有检测并纠正一位错误代 码的纠错码。 要采用海明码纠错，需要按以下步骤来进 行：计算校验位数→确定校验码位置→确 定校验码→实现校验和纠错。
具体计算方法如下： p1（第1个校验位，也是整个码字的第1位）的校验规则 是：从当前位数起，校验1位，然后跳过1位，再校验1位， 再跳过1位，……。这样就可得出p1校验码位可以校验的码字 位包括：第1位（也就是p1本身）、第3位、第5位、第7位、 第9位、第11位、第13位、第15位，……。然后根据所采用 的是奇校验，还是偶校验，最终可以确定该校验位的值。
©安徽科技学院
2015-4-30
第10页
海明纠错码
4. 校验码计算示例
10011101 ？？1？001？1101 假设采用的是偶校验 先求第1个“？”（也就是p1，第1位）的值，因为整个码字 长度为12（包括信息码长和校验码长），所以可以得出本示 例中p1校验码校验的位数是1、3、5、7、9、11共6位。这6 位中除了第1位（也就是p1位）不能确定外，其余5位的值都 是已知的，分别为：1、0、1、1、0。现假设采用的是偶校 验（也就是要求整个被校验的位中的“1”的个数为偶数）， 从已知的5位码值可知，已有3个“1”，所以此时p1位校验码 的值必须为“1”，得出p1=1。 1 ？1？001？1101
如K=5，则要求2r-r≥5+1=6，根据计算可以得知r的最小 值为4，也就是要校验5位信息码，则要插入4位校验码。
©安徽科技学院
2015-4-30
第5 页
海明纠错码
1. 计算校验位数
信息码位数与校验码位数之间的关系
信息码位数 1 2~4 5~11 12~2 27~5 58~1 121~ 6 7 20 247 校验码位数 2 3 4 5 6 7 8
©安徽科技学院
2015-4-30
第14页
海明纠错码
111000101101
1 1 1 2 1 3 0 4 0 5 0 6 1 7 0 8 1 9 1 10 0 11 1 12
G1=1 G2=1 G3=0 G4=0
1 1 0 1
0 0 0 1
1 1 1 0
1 0 ->0 1 0 ->0 1 ->0 1 ->1
©安徽科技学院
2015-4-30
第4 页
海明纠错码
1. 计算校验位数
要使用海明码纠错，首先就要确定发送的数据所需 要要的校验码（也就是“海明码”）位数（也称“校 验码长度”）。它是这样的规定的：假设用N表示添 加了校验码位后整个信息的二进制位数，用K代表其 中有效信息位数，r表示添加的校验码位，它们之间 的关系应满足：N=K＋r≤2r－1。
©安徽科技学院
2015-4-30
第12页
海明纠错码
4. 校验码计算示例
10011101 假设采用的是偶校验
1 1 1？001？1101
再求第3个“？”（也就是p3，第4位）的值，根据以上 规则可以很快得出本示例中p3校验码校验的位数是4、5 、6、7、12，一共5位。这5位中除了第4位（也就是p3 位）不能确定外，其余4位的值都是已知的，分别为：0 、0、1、1。现假设采用的是偶校验，从已知的4位码值 可知，也已有2个“1”，所以此时p2位校验码的值必须为 “0”，得出p3=0。1 1 1 0 001？1101