一种循环冗余校验算法，它与具有特定非零值的尾随字节数不变量。
一种循环冗余校验算法，它与具有特定非零值的尾随字节数不变量。
提问于 2018-06-25 09:30:35
假设我有一个任意的字节块。使用CRC-16-CCITT算法在整个块上计算CRC余数来终止该块，其中余数按大端字节顺序排列。在块和剩余部分之后，有一个任意数目的零字节，它们一直持续到字节流的末尾。
这种安排利用了通常认为不受欢迎的CRC算法的一个特性:它不区分具有不同数目的尾随零的消息，前提是消息以其余数终止(在我的情况下)。这允许接收方断言数据的正确性，而不管流中的尾字节数如何。
下面是一个示例：
>>> hex(crc(b'123456789')) # Computing the remainder
'0x29b1'
>>> hex(crc(b'123456789\x29\xb1')) # Appending the remainder in the big-endian order
'0x0' # If the remainder is correct, the residual value is always zero
>>> hex(crc(b'123456789\x29\xb1\x00\x00')) # ...and it is invariant to the number of trailing zeros
'0x0'
>>> hex(crc(b'123456789\x29\xb1\x00\x00\x00'))
'0x0'这是我想要的行为。然而，在我的应用程序中，数据是通过一种使用不返回到零(NRZ)编码的介质交换的:介质层在同一级别的每五个连续数据位之后注入一个填充位，其中填充位的极性与前面的比特相反；例如，00000000的值被传输为000001000。比特填充是非常不可取的，因为它增加了开销。
为了利用CRC算法对尾随数据(用于填充)的不变性，同时又避免比特填充，我打算在更新CRC余数之前用0x55 (虽然可以是避免填充的任何其他位模式)对每个数据字节进行xor，然后用0x5555对最后的余数进行xor。
作为参考，这里是标准的CRC-16-CCITT算法，天真的实现：
def crc16(b):
crc = 0xFFFF
for byte in b:
crc ^= byte << 8
for bit in range(8):
if crc & 0x8000:
crc = ((crc << 1) ^ 0x1021) & 0xFFFF
else:
crc = (crc << 1) & 0xFFFF
return crc下面是我对0x55输入和输出的修改：
def crc16_mod(b):
crc = 0xFFFF
for byte in b:
crc ^= (byte ^ 0x55) << 8
for bit in range(8):
if crc & 0x8000:
crc = ((crc << 1) ^ 0x1021) & 0xFFFF
else:
crc = (crc << 1) & 0xFFFF
return crc ^ 0x5555一个简单的检查确认，修改后的算法的行为与预期的一致：
>>> print(hex(crc16_mod(b'123456789'))) # New remainder
0x954f
>>> print(hex(crc16_mod(b'123456789\x95\x4f'))) # Appending the remainder; residual is 0x5555
0x5555
>>> print(hex(crc16_mod(b'123456789\x95\x4f\x55\x55\x55'))) # Invariant to the number of trailing 0x55
0x5555
>>> print(hex(crc16_mod(b'123456789\x95\x4f\x55\x55\x55\x55'))) # Invariant to the number of trailing 0x55
0x5555我的问题如下:我是否通过引入这种修改而损害了该算法的错误检测特性？还有什么别的坏处我应该意识到吗？
Stack Overflow用户
回答已采纳
发布于 2018-06-25 13:55:22
在标准的误差模型下(比特以固定的概率独立翻转)，没有缺点。很难预料实际的困难。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/51020246
复制相关文章
相似问题
腾讯云开发者
