假设我有一个任意的字节块。使用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）编码的介质进行交换的：介质层在相同级别的每五个连续数据位之后注入一个stuff位，其中stuff位的极性与前面的位相反；例如，
00000000的值作为000001000发送。位填充非常不受欢迎，因为它增加了开销。为了利用crc算法对尾部数据（用于填充）的不变性，同时避免位填充，我打算在更新crc余数之前用0x55对每个数据字节进行异或（尽管它可能是任何其他避免填充的位模式），然后用0x5555对最后余数进行异或。
作为参考，这里是标准的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输入和输出XORS：
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
我的问题是：我是否通过引入这种修改来损害算法的错误检测特性？我还有什么不好的地方要注意吗？
最佳答案
在标准的错误模型（比特以固定的概率独立翻转）下，没有缺点。很难预料实际的困难。
关于algorithm - 循环冗余校验算法，该算法与具有特定非零值的尾随字节数无关，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/51020246/