是否可以使用 CRC 进行基本的纠错？
我知道使用 CRC 的全部目的是进行错误检测，但我听到有人说它除了错误检测之外还可以用于进行基本的错误纠正。我很好奇是否是这样，如果是的话，它的威力有多大？我的意思是，我们通常将 CRC 称为能够执行 x 位检测，但我很好奇它是否能够执行 x 位校正。如果是这样，这是如何运作的？谢谢。
I know the whole intention of using CRC is to do error detection, but I heard someone state that it can be used to do basic error correction in addition to error detection. I was curious if this was the case, and if so, how powerful is it? I mean, we usually refer to CRC as capable of performing x-bit detection, but I'm curious if it is capable of performing x-bit correction. If so, how does this work? Thanks.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
可以使用 CRC 进行单比特错误纠正。假设有一个 CRC“寄存器”，并且具有一次向前和向后一位运行 CRC 算法的功能，忽略传入数据
int crc_forward(int old_value, int data_bit) { if (old_value & 0x8000) return ((old_value ^ 0x8000) SHL 1) ^ 0x1021 ^ data_bit; else return (old_value SHL 1) ^ data_bit; } int crc_reverse(int old_value) { if (old_value & 1) return (old_value SHR 1) ^ 0x8810; else return old_value SHR 1; }假设有一个经过计算的数据包，以便将 crc 初始化为某个值并为每一位运行 crc_forward （MSB 首先）应该产生零。如果得到的 CRC 值不为零，则可以反向运行该算法（忽略数据位），直到计算出的 CRC 值为 1。这就是错误位的位置。
请注意，这种方法可能足以纠正 NAND 闪存等软件错误。为了有效地将其用于硬件纠错，必须能够延迟读取操作直到可以处理 ECC，否则将需要一张“综合症”值和位位置表。
It is possible to do single-bit error correction with a CRC. Assume one has a CRC "register" and has functions to run the CRC algorithm forward and backward a bit at a time, ignoring incoming data
int crc_forward(int old_value, int data_bit) { if (old_value & 0x8000) return ((old_value ^ 0x8000) SHL 1) ^ 0x1021 ^ data_bit; else return (old_value SHL 1) ^ data_bit; } int crc_reverse(int old_value) { if (old_value & 1) return (old_value SHR 1) ^ 0x8810; else return old_value SHR 1; }Suppose one has a packet which is computed so that initializing the crc to some value and running crc_forward for each bit (MSB first) should yield zero. If one gets a CRC value other than zero, one can run the algorithm in reverse (ignoring data bits) until the computed CRC value is 1. That's the location of the incorrect bit.
Note that this approach may be adequate for software error correction in things like NAND flash. To usefully employ it for hardware error correction, one would have to either be able to delay read operations until the ECC could be processed, or else one would need a table of 'syndrome' values and bit positions.
您可以使用 CRC 进行多位纠错。查看维基百科，参考 koopman 的工作，CRC 可以检测到其 hamming_distance-1 错误。汉明距离取决于有效负载长度和使用的 CRC 多项式。例如，Koopmans 多项式 0xBA0DC66B 可以检测长度高达 16360 位的消息中最多 5 位的错误。前两条消息中描述的算法可以扩展到所需的位数，但时间随着要修复的位数呈指数增长。
如果找不到与错误 CRC 匹配的 1 位，请查看所有 2 位、3 位，直到 hamming_distance-1。请注意，这会变得很慢很快，message_length 为 2 位的平方，为 3 位的立方，直到 5 位的五次方。
You CAN do multi-bit error correction with CRCs. Looking at wikipedia, with references to koopmans work, a CRC can detect up its hamming_distance-1 errors. The hamming distance depends on the payload length, and the CRC polynomial in use. So for example Koopmans polynomial of 0xBA0DC66B can detect up to 5 bits of error in messages up to 16360 bits long. The algorithm described in the previous two messages can be extended up to as many bits as needed, but the time goes up exponentially with the number of bits to fix.
If you can't find 1 bit matching the error CRC, look through all 2-bit, 3-bit up to your hamming_distance-1. Note that this gets slow fast, message_length squared for 2 bits, cubed for 3 bits up to fifth power for five bits.
我最近致力于 CRC16 错误检测和单位错误纠正。
基本思想如下：
CRCox = CRCs ^ CRCr给出。这清楚吗？我有一篇关于这个的论文。如果您想了解更多信息，请告诉我。
I recently worked on CRC16 error detection and single bit error correction.
Here's the basic idea:
CRCox = CRCs ^ CRCr.Is this clear? I have a paper about this. If you want to know more, just let me know.
迟到的答案，但 CRC32 多项式
可以检测最多 7 位错误，并针对 1024 位（992 位数据，32 位 CRC）消息纠正最多 3 位错误。有comb(1024,1)+comb(1024,2)+comb(1024,3)=178957824个可纠正的位错误模式。如果有足够的内存容纳 1431662592 字节表 (178957824*8 = ~1.4 GB)，则可以生成所有可能的 1、2 和 3 位错误 CRC 并将其存储在该表中，其中每个条目为： 32 位 CRC ，一个 2 位错误计数，以及三个用于位错误位置的 10 位字段。
然后对表进行排序，并且在检查 CRC 时，如果它是坏的，则对表进行二分搜索（最多 28 个循环）可以确定它是否是 1、2 或 3 位错误情况，并使用存储的索引进行纠正在表中。
然而，存在5个或更多比特错误的误纠正的可能性。如果某些 5 错误位模式产生与 3 错误位模式相同的 CRC，则错误的 3 位将被更改，从而导致看似具有有效 CRC 的 8 位错误。
链接到示例代码：
https://github.com/jeffareid/misc/blob /master/crccor3.c
Late answer, but CRC32 polynomial
can detect up to 7 bit errors and correct up to 3 bit errors for a 1024 bit (992 bit data, 32 bit CRC) message. There are comb(1024,1) + comb(1024,2) + comb(1024,3) = 178957824 correctable bit error patterns. If there is enough memory for a 1431662592 byte table (178957824*8 = ~1.4 GB), then all possible 1, 2, and 3 bit error CRC's could be generated and stored in that table, where each entry would be: 32 bit CRC, a 2 bit error count, and three 10 bit fields for bit error locations.
The table would then be sorted, and when checking a CRC, if it is bad, a binary search of the table (max 28 loops) could determine if it was a 1, 2, or 3 bit error case and corrected using the indexes stored in the table.
However, there is a possibility of mis-correction with 5 or more bit errors. If some 5 error bit pattern produces the same CRC as a 3 error bit pattern, the wrong 3 bits will be changed, resulting in an 8 bit error that appears to have a valid CRC.
Link to example code:
https://github.com/jeffareid/misc/blob/master/crccor3.c