据说，循环冗余校验（CRC）可以检测少于r + 1位的突发错误，其中r是多项式的次数。此外，长度大于r + 1位的突发错误被检测到的概率为1 - 2-r。
有人能指引我找到相同的证明吗？
有人能指引我找到相同的证明吗？
CRC突发错误检测校验和结果的证明
3
- anuja
1
我投票关闭此问题，因为这是更适合[cs.se]的问题，该网站专门处理像这样的通用算法问题。 - Machavity
1个回答
6
不完全正确。一个r位的CRC将能够检测出长度为r+1的所有突发错误模式，除了一个模式——多项式本身。请参考这篇讲义进行证明。
只有在消息无法检测出错误时，CRC多项式才能够被错误多项式整除。如果错误多项式长达r个比特位，则一次项系数为1的r+1阶多项式不能够整除一个r阶多项式，因为它不包含x作为因子，而且它能够整除的仅有一个r+1阶多项式是它自身。所有CRC多项式都有一个一次项系数为1。
你的另一个声明是任何r位哈希函数的性质，即使得所有可能的r位哈希值上的消息等概率分布，而CRC也具备此性质。2^(-r)仅仅是应用错误后刚好导致相同CRC的概率，而其中有2^r种可能性。这就好比说，在一个六面骰子上投掷与刚刚所投掷的点数相同的概率为1/6。
只有在消息无法检测出错误时，CRC多项式才能够被错误多项式整除。如果错误多项式长达r个比特位，则一次项系数为1的r+1阶多项式不能够整除一个r阶多项式，因为它不包含x作为因子，而且它能够整除的仅有一个r+1阶多项式是它自身。所有CRC多项式都有一个一次项系数为1。
你的另一个声明是任何r位哈希函数的性质，即使得所有可能的r位哈希值上的消息等概率分布，而CRC也具备此性质。2^(-r)仅仅是应用错误后刚好导致相同CRC的概率，而其中有2^r种可能性。这就好比说，在一个六面骰子上投掷与刚刚所投掷的点数相同的概率为1/6。
- Mark Adler
6
关于爆发检测弱点...这是否意味着当我在任何位置使用XOR和完整的CRC多项式（例如ATM-8 CRC-8的0x107）合并我的数据时，我应该得到与合并操作之前相同的校验和？ - Silicomancer
1是的，完全正确。您可以在消息中的任何位置多次执行此操作。还有许多其他更长的位模式，称为“码字”，也具有该属性。该多项式是最短的码字，并且只有一个该长度的码字。 - Mark Adler
刚试了一下。使用ASCII数据“AAA”（0..2=0x41,0x41,0x41）计算CRC-8，得到的校验和为0x63（请参见https://crccalc.com/?crc=AAA&method=crc8&datatype=ascii）。将该数据与0x107异或后应该得到“F@A”（0..2=0x46,0x40,0x41），这会给我0x60（请参见https://crccalc.com/?crc=F@A&method=crc8&datatype=ascii）。我在C++代码中尝试了相同的操作，但结果仍然是错误的。我还是做错了什么吗？ - Silicomancer
1我使用了普通的CRC-8多项式=0x07，初始值=0，异或输出=0，反转输入=false，反转输出=false。 - Silicomancer
1是的，你做错了。对于非反射CRC（refin和refout为false），多项式的位按照消息中的位顺序进行异或运算。因此，
01000001 01000001 01000001可以与以第二个字节的最低有效位结尾的多项式进行异或运算，得到01000000 01000110 01000001，或者"@FA"。这给出了相同的CRC值。 - Mark Adler你说“r位的循环冗余校验码可以检测到长度为r+1的所有突发模式”。我猜“r位的循环冗余校验码可以检测到长度最多为r+1的所有突发模式”也是正确的吧？ - Silicomancer
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接