algorithm - 一种循环冗余校验算法，它对具有特定非零值的尾随字节数不变

Question

假设我有一个任意字节 block 。该 block 以使用 CRC-16-CCITT 算法在整个 block 上计算的 CRC 余数终止，其中余数按大端字节顺序排列。在 block 和余数之后，有任意数量的零字节，它们一直持续到字节流结束。

这种安排利用了此 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) 编码的介质交换的:介质层在同一级别的每五个连续数据位之后注入(inject)一个填充位，其中极性填充位与前面的位相反；例如00000000 的值作为 000001000 传输。位填充是非常不受欢迎的，因为它会增加开销。

为了利用 CRC 算法对尾随数据(用于填充)的不变性并避免位填充，我打算用 0x55 异或每个数据字节(尽管它可以是任何其他位模式避免填充)在更新 CRC 余数之前，然后将最后的余数与 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

我的问题如下:我是否通过引入此修改来损害算法的错误检测属性？还有其他我应该注意的缺点吗？

Answer 1

在错误的标准模型(位以固定概率独立翻转)下，没有缺点。实际困难很难预料。