轻松掌握CRC错误检测算法详解
需积分: 32 116 浏览量
更新于2024-07-17
收藏 195KB PDF 举报
本文档是一份详尽的CRC算法指南，名为《CRC算法：轻松理解和检测错误的全面解析》。作者Ross N. Williams深入浅出地介绍了CRC（Cyclic Redundancy Check）算法，这是一种广泛应用于数据传输和存储系统中的校验方法，用于检测和纠正突发错误。
1. **引言：错误检测** - 文章首先探讨了在数字通信中错误检测的重要性，强调了CRC算法如何作为可靠的数据完整性检查工具。
2. **复杂性需求** - CRC算法设计的关键在于平衡计算效率和检测能力，文章解释了为何选择适当的复杂度对于确保有效性和性能至关重要。
3. **基本理念** - CRC算法的核心思想是利用余数生成器多项式来生成一个附加的校验位，当接收端与发送端的校验结果不匹配时，意味着数据传输过程中可能存在错误。
4. **多项式算术** - CRC算法涉及在二进制域中进行多项式运算，包括模2除法和乘法，这对于理解算法的工作原理至关重要。
5. **无进位二进制算术** - 为了简化计算过程，讨论了没有进位的二进制运算，这有助于直观地理解校验位的生成过程。
6. **实例演示** - 文献提供了一个完整的CRC算法工作示例，一步步展示如何应用理论到实际操作中。
7. **选择多项式** - CRC算法的多样性体现在不同标准中使用的多项式选择上，如CRC-16、CRC-32等，文章探讨了如何根据具体应用场景选择合适的多项式。
8. **直觉实现** - 文献概述了两种基本的CRC实现方式，一种是直接使用多项式操作，另一种是基于表格的方法。
9. **表格驱动实现** - 通过表格来存储中间步骤的结果，提高了查找和计算速度，但可能涉及到不同的表驱动策略。
10. **变形的表格驱动实现** - 提到了“反射”和“反转”策略，这些技巧可以优化表格结构，进一步提升算法效率。
11. **初始和终止值** - 初始化和终止值在CRC算法中扮演着关键角色，它们决定了生成的校验位和校验的有效性。
12. **绝对算法定义** - 文章确保了算法定义的精确性，避免因理解歧义导致的错误。
13. **参数化模型** - CRC算法可以根据特定参数进行调整，形成一系列适应不同场景的变种。
14. **标准参数集目录** - 列出了常见的标准参数集，帮助读者了解行业标准是如何应用CRC算法的。
15. **模型算法实现** - 文档提供了一个通用的CRC算法模型，供开发者参考实现。
16. **自定义表格驱动实现** - 鼓励读者根据实际需求调整和定制自己的表格驱动实现方法。
17. **生成查找表** - 解释了如何通过编程生成用于快速计算的查找表，以提高算法效率。
18. **版本更新与资源获取** - 最后，作者提供了文档的最新版本日期以及如何通过网络（FTP地址）或传统邮寄方式获取完整文本。
《CRC算法：轻松理解和检测错误的全面解析》是一份全面且实用的指南，涵盖了CRC算法的基本原理、多种实现方式、参数选择和应用实例，为从事IT行业的人员理解和应用CRC算法提供了详尽的指导。
----....,.,,,
0110...,.,,,
0000...,.,,,
----...,.,,,
1100..,.,,,
1001..,.,,,
====..,.,,,
0110.,.,,,
0000.,.,,,
----.,.,,,
1100,.,,,
1001,.,,,
====,.,,,
0111.,,,
0000.,,,
----.,,,
1110,,,
1001,,,
====,,,
1011,,
1001,,
====,,
0101,
0000,
----
1011
1001
====
0010 = 02 = 2 = REMAINDER
In decimal this is "1559 divided by 9 is 173 with a remainder of 2".
Although the effect of each bit of the input message on the quotient
is not all that significant, the 4-bit remainder gets kicked about
quite a lot during the calculation, and if more bytes were added to
the message (dividend) it's value could change radically again very
quickly. This is why division works where addition doesn't.
In case you're wondering, using this 4-bit checksum the transmitted
message would look like this (in hexadecimal): 06172 (where the 0617
is the message and the 2 is the checksum). The receiver would divide
0617 by 9 and see whether the remainder was 2.
4. Polynomical Arithmetic
While the division scheme described in the previous section is very
very similar to the checksumming schemes called CRC schemes, the CRC
schemes are in fact a bit weirder, and we need to delve into some
strange number systems to understand them.
The word you will hear all the time when dealing with CRC algorithms
is the word "polynomial". A given CRC algorithm will be said to be
Pa
g
e 5 of 30A PAINLESS GUIDE TO CRC ERROR DETECTION ALGORITHMS
11/19/2004htt
p
://www.
g
eocities.com/SiliconValle
y
/Pines/8659/crc.htm
using a particular polynomial, and CRC algorithms in general are said
to be operating using polynomial arithmetic. What does this mean?
Instead of the divisor, dividend (message), quotient, and remainder
(as described in the previous section) being viewed as positive
integers, they are viewed as polynomials with binary coefficients.
This is done by treating each number as a bit-string whose bits are
the coefficients of a polynomial. For example, the ordinary number 23
(decimal) is 17 (hex) and 10111 binary and so it corresponds to the
polynomial:
1*x^4 + 0*x^3 + 1*x^2 + 1*x^1 + 1*x^0
or, more simply:
x^4 + x^2 + x^1 + x^0
Using this technique, the message, and the divisor can be represented
as polynomials and we can do all our arithmetic just as before, except
that now it's all cluttered up with Xs. For example, suppose we wanted
to multiply 1101 by 1011. We can do this simply by multiplying the
polynomials:
(x^3 + x^2 + x^0)(x^3 + x^1 + x^0)
= (x^6 + x^4 + x^3
+ x^5 + x^3 + x^2
+ x^3 + x^1 + x^0) = x^6 + x^5 + x^4 + 3*x^3 + x^2 + x^1 + x^0
At this point, to get the right answer, we have to pretend that x is 2
and propagate binary carries from the 3*x^3 yielding
x^7 + x^3 + x^2 + x^1 + x^0
It's just like ordinary arithmetic except that the base is abstracted
and brought into all the calculations explicitly instead of being
there implicitly. So what's the point?
The point is that IF we pretend that we DON'T know what x is, we CAN'T
perform the carries. We don't know that 3*x^3 is the same as x^4 + x^3
because we don't know that x is 2. In this true polynomial arithmetic
the relationship between all the coefficients is unknown and so the
coefficients of each power effectively become strongly typed;
coefficients of x^2 are effectively of a different type to
coefficients of x^3.
With the coefficients of each power nicely isolated, mathematicians
came up with all sorts of different kinds of polynomial arithmetics
simply by changing the rules about how coefficients work. Of these
schemes, one in particular is relevant here, and that is a polynomial
arithmetic where the coefficients are calculated MOD 2 and there is no
carry; all coefficients must be either 0 or 1 and no carries are
calculated. This is called "polynomial arithmetic mod 2". Thus,
returning to the earlier example:
(x^3 + x^2 + x^0)(x^3 + x^1 + x^0)
= (x^6 + x^4 + x^3
+ x^5 + x^3 + x^2
+ x^3 + x^1 + x^0)
= x^6 + x^5 + x^4 + 3*x^3 + x^2 + x^1 + x^0
Pa
g
e 6 of 30A PAINLESS GUIDE TO CRC ERROR DETECTION ALGORITHMS
11/19/2004htt
p
://www.
g
eocities.com/SiliconValle
y
/Pines/8659/crc.htm
剩余14页未读，继续阅读
2014-10-14 上传
2019-03-27 上传
2023-06-13 上传
2023-06-13 上传
2023-06-13 上传
2023-06-13 上传
2023-07-28 上传
2023-05-27 上传
知所无一
- 粉丝: 3
- 资源: 1
我的内容管理
展开
最新资源
- WPF渲染层字符绘制原理探究及源代码解析
- 海康精简版监控软件：iVMS4200Lite版发布
- 自动化脚本在lspci-TV的应用介绍
- Chrome 81版本稳定版及匹配的chromedriver下载
- 深入解析Python推荐引擎与自然语言处理
- MATLAB数学建模算法程序包及案例数据
- Springboot人力资源管理系统：设计与功能
- STM32F4系列微控制器开发全面参考指南
- Python实现人脸识别的机器学习流程
- 基于STM32F103C8T6的HLW8032电量采集与解析方案
- Node.js高效MySQL驱动程序：mysqljs/mysql特性和配置
- 基于Python和大数据技术的电影推荐系统设计与实现
- 为ripro主题添加Live2D看板娘的后端资源教程
- 2022版PowerToys Everything插件升级，稳定运行无报错
- Map简易斗地主游戏实现方法介绍
- SJTU ICS Lab6 实验报告解析
