我知道使用循环冗余校验的主要目的是进行错误检测，但我听说有人声称它除了错误检测还可用于基本纠错。我很好奇这是否属实，如果属实，那么它的强大程度如何？ 我的意思是，我们通常认为CRC能够执行x位检测，但我想知道它是否能够执行x位纠正。如果可以，那么如何实现？ 谢谢。
4个回答
15
使用CRC可以进行单比特错误的纠正。假设有一个CRC“寄存器”，并且有函数以一位为单位向前和向后运行CRC算法，忽略传入的数据。
假设有一个数据包，初始化crc值并对每个比特（从MSB开始）运行crc_forward应该得到零。如果得到的CRC值不是零，则可以反向运行算法（忽略数据位），直到计算出的CRC值是1。这就是错误比特的位置。
请注意，这种方法可能足够用于诸如NAND闪存之类的软件纠错。要将其用于硬件纠错，必须能够延迟读取操作直到ECC可以处理，否则需要一个“综合征”值和位位置表。
假设有一个数据包，初始化crc值并对每个比特（从MSB开始）运行crc_forward应该得到零。如果得到的CRC值不是零，则可以反向运行算法（忽略数据位），直到计算出的CRC值是1。这就是错误比特的位置。
请注意，这种方法可能足够用于诸如NAND闪存之类的软件纠错。要将其用于硬件纠错，必须能够延迟读取操作直到ECC可以处理，否则需要一个“综合征”值和位位置表。
- supercat
1
还可以实现单次突发纠错。一些16位CRC多项式允许对长达184位的消息中的7位单次突发进行纠正。 - rcgldr
9
你可以使用CRC进行多位错误纠正。根据维基百科，参考库普曼的研究，CRC可以检测其汉明距离-1个错误。汉明距离取决于负载长度和使用的CRC多项式。例如，Koopmans多项式0xBA0DC66B可以检测长达16360位的消息中高达5位错误。前两条消息中描述的算法可以扩展到需要修复的位数，但随着要修复的位数增加，时间呈指数增长。
- 计算错误CRC = CRC_gotten ^ CRC_expected。
- 查找所有可能的1位消息（即所有0、1和所有0）（有message_length种情况需要评估，注意这是位而不是字节），错误位是生成错误CRC的消息。
- 反转检测到的位以纠正错误。
如果找不到匹配错误CRC的1位，请查看所有2位、3位直至汉明距离-1的位。请注意，这会很快变慢，对于2位来说，消息长度的平方，对于3位来说，消息长度的立方，对于五位来说，是第五次幂。
- ilgitano
5
所述算法的措辞似乎对于单比特错误是n平方，对于双比特错误是n立方等等，因为独立计算每个消息的CRC需要时间N。建议提供一些有助于在没有额外N因素的情况下完成此操作的方法。 - supercat
不，N代表单个位。我可以在logN时间内计算出N位中设置了单个位的CRC。更好的是，如果给定N位消息中位置X处单个位的CRC，则可以轻松地告诉您带有第N+1位的消息的CRC。这只是CRC内部循环的一个步骤。 - ilgitano
只需在循环中使用您的crc_forward函数：从1开始，进行crc_forward操作，这是crc错误吗？不是，再次进行crc_forward并检查。 - ilgitano
2这有点误导人...仅仅因为你可以_检测_5个单比特错误，并不意味着你也能_纠正_它们。在实践中，对于你所给出的消息，通常只能纠正2个单比特错误——这仅仅是根据鸽笼原理（在长度为16360的消息中，平均有超过1000种可能性产生3位错误）。当然，单个突发错误是完全不同的故事——在这种情况下，除了生成多项式以外，所有33位突发错误都可以被检测到，并且纠正长度应该大于10b，适用于<=16360b的消息。 - Arne Vogel
1@Arne，koopsmans的工作包括一张表格，告诉您数据长度，在给定位数的情况下，CRC错误停止是唯一的。只要您的消息比那个短，错误代码就会是唯一的。当然，这取决于所使用的多项式。 - ilgitano
5
我最近进行了CRC16错误检测和单比特错误纠正方面的工作。
基本思路如下：
1. 假设有一个单比特错误。
2. 如果数据+crc没有错误，则CRC为0，否则不为0。
3. 我们将发送的CRC定义为CRCs，接收到的CRC定义为CRCr。
4. 然后误差位由公式CRCox=CRCs^CRCr计算得出。
5. 结果包括CRC错误和数据错误。
6. 查看CRCox与比特错误之间的关系。
清楚吗？我有一篇论文讲解这个问题。如果您想了解更多信息，请告诉我。
基本思路如下：
1. 假设有一个单比特错误。
2. 如果数据+crc没有错误，则CRC为0，否则不为0。
3. 我们将发送的CRC定义为CRCs，接收到的CRC定义为CRCr。
4. 然后误差位由公式CRCox=CRCs^CRCr计算得出。
5. 结果包括CRC错误和数据错误。
6. 查看CRCox与比特错误之间的关系。
清楚吗？我有一篇论文讲解这个问题。如果您想了解更多信息，请告诉我。
- 4t8dds
3
我认为这可能是@Wandy所指的论文：http://espace.library.uq.edu.au/eserv.php?pid=UQ:9523&dsID=n01393289.pdf - Jason Sundram
1对于第二点，CRC 不会为 0。它是接收到的 CRC 与接收数据计算出的 CRC 进行异或运算的结果！ - Étienne
@Étienne 当然他的意思是接收到的数据CRC码加上CRC校验码为零。 - Steve Cox
1
晚了一点回答，但是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位字段的比特错误位置。
0x1f1922815 (= 0x787 * 0x557 * 0x465 * 0x3 * 0x3)
可以检测到最多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个比特错误。
示例代码链接：
- rcgldr
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接