适合读者软考中级备考同学阅读时间4分钟内容CRC原理、模2除法步骤、生成多项式、例题1. 为什么需要CRC奇偶校验只能检测奇数个错误且无法定位错误位置。CRC循环冗余校验Cyclic Redundancy Check通过复杂的数学运算能够检测多位错误检错能力远强于奇偶校验广泛应用于网络通信如以太网、存储设备如硬盘等领域。软考中常考查CRC的编码过程核心是模2除法。2. 核心概念2.1 基本步骤发送方选定一个生成多项式G(x)发送方和接收方事先约定在原数据后面添加若干个00的个数 生成多项式位数 - 1用模2除法将添加0后的数据除以生成多项式得到的余数作为CRC校验码替换掉添加的0发送原始数据 CRC校验码2.2 接收方校验步骤用收到的完整数据数据CRC除以同一个生成多项式如果余数为0说明数据正确或未检测出错误如果余数不为0说明数据传输过程中发生了错误3. 模2除法关键技能模2除法与普通除法不同不借位、不进位按位做异或运算每一位独立计算1-100-001-010-11其实就是异或规则取被除数的前n位n生成多项式的位数如果最高位为1则商1并用被除数与生成多项式做异或减如果最高位为0则商0并直接落下一位重复直到所有位处理完毕最后的余数位数 生成多项式位数4. 生成多项式的表示生成多项式G(x)可以用二进制串表示例如G(x) x^4 x 1 → 二进制 10011从最高次到常数项系数为1的位对应1G(x) x^3 x^2 1 → 二进制 1101注意生成多项式的位数 最高次幂 1。例如x^4对应的二进制有5位。5. 完整示例软考典型题目原始数据为101101生成多项式为10011即x^4 x 1求CRC校验码。步骤1确定添加0的个数生成多项式10011共5位所以添加5-14个0数据变为101101 0000步骤2模2除法用1011010000除以100111011010000 ÷ 10011我们逐步计算取被除数前5位10110最高位1 → 商1与10011异或10110 ⊕ 10011 00101即101落下一位0 →10104位不够5位继续落位等一下我们按照长除法习惯上一步余数是101即0101再落下一变成01010更规范的写法10011 ) 1011010000 10011 ← 第一次商1减异或 ---- 011011 ← 余数011再落下一0等等实际上应该是 1011010000 10011 (对齐前5位) ---- 0110110000? 我一步步来还是列竖式更清楚10011 ) 1011010000 10011 ---- 0100110000 (余数 01001? 不)为了避免混乱我改用手工逐位推导被除数1 0 1 1 0 1 0 0 0 0除数 1 0 0 1 1第一次取前5位 1 0 1 1 0最高位1商1异或得 0 0 1 0 1即101余数101然后落下一第六位1 → 1011不对我们还有后面的0。实际上我们逐位移动初始取5位 1011010110 XOR 10011 00101即101现在余数101落下一原第6位1 → 10114位需要5位所以再落一位原第7位0 → 1011010110 XOR 10011 00101 → 余数101落下一原第8位0 → 10104位再落一位原第9位0 → 1010010100 XOR 10011 00111 → 余数111落下一原第10位0 → 11104位此时没有更多位了。余数1110共4位小于除数位数5。所以余数为 1110。因此CRC校验码 1110。最终发送数据原始数据 CRC 101101 11106. 接收方校验示例接收方收到1011011110用同一个生成多项式10011做模2除法若余数为0则正确。计算过程略与发送方类似最终余数应为0。7. 生成多项式的常见标准软考中可能直接给出生成多项式的二进制形式不必记忆标准但了解常用多项式有助于理解名称生成多项式二进制用途CRC-8100000111嵌入式CRC-1611000000000000101异步通信CRC-32100000100110000010001110110110111以太网、ZIP考试一般会直接给出多项式无需记忆。8. 常见考点与陷阱考点说明添加0的个数 生成多项式位数 - 1模2除法与普通除法的区别减法是异或不借位余数的位数小于生成多项式位数检错能力CRC能检测全部单比特错误、双比特错误、奇数个错误、突发长度≤r-1的错误r为校验位位数生成多项式选择国际标准不可随意选择9. 经典例题软考常见题目1原始数据为1101生成多项式为1011求CRC校验码。解生成多项式位数4添加3个0 →1101000模2除法1011 ) 1101000 1011 ---- 0110 (余数110落下一0得1100) 1011 ---- 0111 (余数111落下一0得1110) 1011 ---- 0101 (余数101)余数1013位小于4位。校验码 101发送数据1101 101答案101题目2接收方收到数据1101101生成多项式为1011数据是否正确解用1101101除以1011看余数是否为0。计算过程略最终余数若为0则正确。本题结果为余数0可自行验证。答案正确题目3判断题CRC校验码既能检错也能纠错。答案错误。CRC通常只能检错不能定位和纠正错误除非结合重传机制。10. 记忆口诀CRC有多项式除后余数做校验。模2除不借位异或运算要熟练。接收方再相除余数为0则安全。11. 给备考同学的一句话CRC的难点在模2除法。多动手算几遍熟悉对齐、异或、落位的流程。考试时如果计算量大可以先列出二进制竖式逐位处理。记住添加0的个数 多项式位数 - 1余数位数 多项式位数。本专栏日更2篇点击头像 → 专栏《软考中级高频考点》订阅需要“计算机系统知识”完整思维导图私信回复“软考计算机”免费获取#软考中级 #软件设计师 #CRC #循环冗余校验 #计算机系统知识
