17

我知道使用 CRC 的全部目的是进行错误检测,但我听说有人说除了错误检测之外,它还可以用来进行基本的纠错。我很好奇是不是这样,如果是这样,它有多强大?我的意思是,我们通常将 CRC 称为能够执行 x 位检测,但我很好奇它是否能够执行 x 位校正。如果是这样,这是如何工作的?谢谢。

4

4 回答 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 位错误。前两条消息中描述的算法可以根据需要扩展到任意多的位,但时间随着要修复的位数呈指数增长。

  1. 计算错误 CRC = CRC_gotten ^ CRC_expected。
  2. 查看所有可能的 1 位消息(即全 0、1 和全 0)(需要评估 message_length 情况。注意这是 BITS 而不是 BYTES),错误位是生成错误 CRC 的消息。
  3. 反转检测到的位以纠正错误。

如果您找不到与错误 CRC 匹配的 1 位,请查看所有 2 位、3 位直到您的 hamming_distance-1。请注意,这会变慢变快,message_length 平方为 2 位,三次方为 3 位,最高为 5 位的五次方。

于 2015-01-09T17:12:24.617 回答
5

我最近从事 CRC16 错误检测和单比特纠错。

这是基本思想:

  1. 假设您有一个位错误。
  2. 如果 data+crc 没有错误,则 CRC 为 0,否则为 0。
  3. 我们将发送的 CRC 定义为 CRC,将接收的 CRC 定义为 CRCr。
  4. 然后错误位由 给出CRCox = CRCs ^ CRCr
  5. 结果包括 CRC 错误和数据错误。
  6. 看看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 位错误。

链接到示例代码:

https://github.com/jeffareid/misc/blob/master/crccor3.c

于 2020-06-04T18:10:27.690 回答