是否可以使用CRC进行基本错误纠正？

Question

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

Answer 1

可以使用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初始化为某个值并且每个位(MSB优先)运行crc_forward应该产生零.如果得到的CRC值不是零,则可以反向运行算法(忽略数据位),直到计算出的CRC值为1.这就是错误位的位置.

请注意,这种方法可能足以用于NAND闪存等软件纠错.为了有效地将其用于硬件纠错,人们必须能够延迟读取操作直到可以处理ECC,否则就需要一个"校正"值和位位置表.

Answer 2

您可以使用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位为3位,5位为5位.

Answer 3

我最近致力于 CRC16 错误检测和单比特纠错。

这是基本思想：

1. 假设您有一个位错误。
2. 如果 data+crc 不包含错误，则 CRC 将为 0，否则为 0。
3. 我们将发送的 CRC 定义为 CRC，将接收的 CRC 定义为 CRCr。
4. 然后错误位由 给出CRCox = CRCs ^ CRCr。
5. 结果包括 CRC 错误和数据错误。
6. 看看CRCox和误码有什么关系。

这清楚吗？我有一篇关于这个的论文。如果您想了解更多，请告诉我。