适合读者软考中级备考同学阅读时间4分钟内容海明码原理、编码步骤、检错与纠错、例题1. 为什么需要海明码奇偶校验只能检测奇数个错误但不能定位错误位置CRC能检测多位错误但也不能纠错。海明码Hamming Code是一种既能检错又能纠错的线性分组码它通过在数据位之间插入多个校验位使得接收方不仅能知道发生了错误还能确定是哪一位错了并自动纠正通常是单比特错误。软考中常考查海明码的编码过程、校验位的位置、以及如何利用校验结果定位错误位。2. 核心原理2.1 基本思想将数据位分成若干组每组分配一个校验位每个校验位负责保护若干数据位这些数据位的下标在某个二进制位上为1出错时多个校验组会同时报警这些报警的组号二进制拼起来就是出错位的下标2.2 校验位的位置对于m位数据需要k位校验位满足[2^k \ge m k 1]校验位只放在2的幂次位置上1, 2, 4, 8, 16…数据位放在其余位置从1开始编号。示例若数据位m4则k需满足 2^k ≥ 4k1 → 2^k ≥ k5k3时2^38≥8成立。总码长nmk7位。位置分布位置12^0校验位P1位置22^1校验位P2位置3数据位D1位置42^2校验位P3位置5数据位D2位置6数据位D3位置7数据位D43. 编码步骤以4位数据1010为例设数据位 D1 D2 D3 D4 1 0 1 0按位置3,5,6,7存放。需要k3个校验位P1、P2、P3。步骤1确定每个校验位负责的组规则校验位P_i负责所有满足“位置号在第i位二进制为1”的位包括它自己但计算时通常只算数据位最终用偶校验确定P_i的值。具体P1位置1二进制001负责位置1、3、5、7二进制最低位为1的位P2位置2二进制010负责位置2、3、6、7二进制第二位为1的位P3位置4二进制100负责位置4、5、6、7二进制第三位为1的位步骤2计算每个校验位的值采用偶校验P1负责的组除去P1自己位置3(D11)、5(D20)、7(D40) → 1001奇数为了整体偶校验P1必须为1使得总数为偶数。所以P11。P2负责的组位置3(D11)、6(D31)、7(D40) → 1102偶数所以P20保持偶数。P3负责的组位置5(D20)、6(D31)、7(D40) → 0101奇数所以P31。得到校验位P11P20P31。步骤3组成完整海明码按位置填充位置1(P1)1位置2(P2)0位置3(D1)1位置4(P3)1位置5(D2)0位置6(D3)1位置7(D4)0→1011010从左到右位置1~74. 检错与纠错过程接收方收到7位码字后重新计算每个校验组的奇偶性用偶校验。每个校验组产生一个校验结果0表示偶校验正确1表示错误。4.1 生成“校验子”syndrome设G1、G2、G3分别为P1组、P2组、P3组的校验结果0正确1错误。将它们按G3 G2 G1顺序构成二进制数这个数就是出错位的位置若为0表示无错。4.2 示例假设传输过程中位置5原D20翻转为1接收到的码字变为位置11203141516170。重新计算P1组位1,3,5,71110 3奇数偶校验应为偶数 → G11P2组位2,3,6,70110 2偶数 → G20P3组位4,5,6,71110 3奇数 → G31校验子 (G3 G2 G1) 101二进制 5十进制表示第5位出错。将该位取反即可纠正1变0恢复原数据。5. 海明码的检错能力能力说明单比特错误✅ 不仅能检测还能自动纠正双比特错误能检测但不能定位和纠正通常视为不可纠正错误三比特及以上不一定能检测取决于分布在实际应用中海明码常用于内存ECC内存等需要单比特纠错的场景。6. 常见考点与陷阱考点说明校验位个数公式2^k ≥ mk1必须记住校验位位置只能放在2的幂次位置1,2,4,8,…分组规则校验位P_i负责所有位置号第i位为1的位包括自己校验方式通常用偶校验考试如无特别说明默认偶校验纠错原理校验子二进制数直接给出出错位序号扩展海明码加入全校验位可实现双比特检错单比特纠错SEC-DED7. 经典例题题目1对于8位数据求海明码所需的最少校验位数。解利用公式 2^k ≥ 8 k 1 k9k4时2^416 ≥ 13成立k3时2^38 12不成立。答案4位题目2已知海明码码字为1100101位置1~7采用偶校验请问是否出错若出错指出正确码字。解位置1(P1)1位置2(P2)1位置3(D1)0位置4(P3)0位置5(D2)0位置6(D3)1位置7(D4)1分组P1组1,3,5,710012偶→ G10P2组2,3,6,710113奇→ G21P3组4,5,6,700112偶→ G30校验子 (G3 G2 G1) 010二进制 2表示第2位出错。将位置2取反1→0正确码字为1000101。答案第2位错正确码字1000101题目3概念题以下关于海明码的说法正确的是 。A. 海明码可以检测所有双比特错误B. 海明码可以纠正所有双比特错误C. 海明码的校验位必须放在数据位的后面D. 海明码的校验子为0表示无错答案D校验子为0表示偶校验各组都正确无错A基本海明码不能保证检测所有双错B只能纠正单错C校验位放在2的幂次位不一定在最后8. 记忆口诀海明分组靠2的幂校验位数公式记。每组偶校验算出值接收分组得二进制。若不为零指向错取反纠正就完事。9. 给备考同学的一句话海明码的难点在于分组规则和校验子的计算。考试时如果遇到海明码先明确校验位的位置1,2,4,8…然后分组计算每组中1的个数偶校验要求偶数最后接收方的校验子二进制数直接告诉你错误的位置。多画位置表多练几道题就能熟练掌握。本专栏日更2篇点击头像 → 专栏《软考中级高频考点》订阅需要“计算机系统知识”完整思维导图私信回复“软考计算机”免费获取#软考中级 #软件设计师 #海明码 #汉明码 #校验码 #计算机系统知识