我知道使用 CRC 的全部目的是进行错误检测,但我听说有人说除了错误检测之外,它还可以用来进行基本的纠错。我很好奇是不是这样,如果是这样,它有多强大?我的意思是,我们通常将 CRC 称为能够执行 x 位检测,但我很好奇它是否能够执行 x 位校正。如果是这样,这是如何工作的?谢谢。
4 回答
可以使用 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,或者需要一个“综合症”值和位位置表。
您可以使用 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 位的五次方。
我最近从事 CRC16 错误检测和单比特纠错。
这是基本思想:
- 假设您有一个位错误。
- 如果 data+crc 没有错误,则 CRC 为 0,否则为 0。
- 我们将发送的 CRC 定义为 CRC,将接收的 CRC 定义为 CRCr。
- 然后错误位由 给出
CRCox = CRCs ^ CRCr
。 - 结果包括 CRC 错误和数据错误。
- 看看CRCox和误码有什么关系。
这清楚吗?我有一篇关于这个的论文。如果您想了解更多,请告诉我。
迟到的答案,但 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 位错误。
链接到示例代码: