一种循环冗余校验算法，其对于特定非零值的尾随字节数是不变的。

Question

假设我有一段任意的字节块。该块以使用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异或(虽然它可以是任何避免填充的其他位模式)，然后将最终余数与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对输入和输出进行异或操作：

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

我的问题如下：通过引入这种修改，我是否会损害算法的错误检测属性？我应该注意哪些其他缺点？

- Pavel Kirienko

Answer 1

在标准错误模型下（比特以固定概率翻转），没有任何不利影响。很难预见实际困难。

- David Eisenstat