我知道使用 CRC 的全部目的是进行错误检测，但我听说有人说除了错误检测之外，它还可以用来进行基本的纠错。我很好奇是不是这样，如果是这样，它有多强大？我的意思是，我们通常将 CRC 称为能够执行 x 位检测，但我很好奇它是否能够执行 x 位校正。如果是这样，这是如何工作的？谢谢。
问问题
13061 次
4 回答
14
可以使用 CRC 进行单比特纠错。假设有一个 CRC “寄存器”，并且具有一次向前和向后运行 CRC 算法的功能，忽略传入的数据
int crc_forward（int old_value，int data_bit）
{
如果（旧值和 0x8000）
返回 ((old_value ^ 0x8000) SHL 1) ^ 0x1021 ^ data_bit;
别的
返回（旧值 SHL 1）^ 数据位；
}
int crc_reverse(int old_value)
{
如果（旧值和 1）
返回（旧值 SHR 1）^ 0x8810；
别的
返回旧值 SHR 1；
}
假设一个数据包经过计算，以便将 crc 初始化为某个值并为每个位（MSB 优先）运行 crc_forward 应该产生零。如果获得的 CRC 值不是零，则可以反向运行算法（忽略数据位），直到计算出的 CRC 值为 1。这就是不正确位的位置。
请注意，这种方法可能足以用于 NAND 闪存之类的软件纠错。为了有效地将其用于硬件纠错，必须能够延迟读取操作直到可以处理 ECC，或者需要一个“综合症”值和位位置表。
于 2011-05-29T19:13:12.267 回答
8
您可以使用 CRC 进行多位纠错。查看维基百科，参考 koopmans 的工作，CRC 可以检测到其 hamming_distance-1 错误。汉明距离取决于有效载荷长度和使用的 CRC 多项式。因此，例如 0xBA0DC66B 的 Koopmans 多项式可以在最长 16360 位的消息中检测到 5 位错误。前两条消息中描述的算法可以根据需要扩展到任意多的位，但时间随着要修复的位数呈指数增长。
- 计算错误 CRC = CRC_gotten ^ CRC_expected。
- 查看所有可能的 1 位消息（即全 0、1 和全 0）（需要评估 message_length 情况。注意这是 BITS 而不是 BYTES），错误位是生成错误 CRC 的消息。
- 反转检测到的位以纠正错误。
如果您找不到与错误 CRC 匹配的 1 位，请查看所有 2 位、3 位直到您的 hamming_distance-1。请注意，这会变慢变快，message_length 平方为 2 位，三次方为 3 位，最高为 5 位的五次方。
于 2015-01-09T17:12:24.617 回答
5
我最近从事 CRC16 错误检测和单比特纠错。
这是基本思想：
- 假设您有一个位错误。
- 如果 data+crc 没有错误，则 CRC 为 0，否则为 0。
- 我们将发送的 CRC 定义为 CRC，将接收的 CRC 定义为 CRCr。
- 然后错误位由 给出
CRCox = CRCs ^ CRCr。 - 结果包括 CRC 错误和数据错误。
- 看看CRCox和误码有什么关系。
这清楚吗？我有一篇关于这个的论文。如果您想了解更多，请告诉我。
于 2011-12-21T09:30:45.967 回答
1
迟到的答案，但 CRC32 多项式
0x1f1922815 (= 0x787 * 0x557 * 0x465 * 0x3 * 0x3)
对于 1024 位（992 位数据，32 位 CRC）消息，可以检测多达 7 位错误并纠正多达 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 位错误。
链接到示例代码：
于 2020-06-04T18:10:27.690 回答