Алгоритм проверки циклическим избыточным кодом, который инвариантен к числу завершающих байтов с конкретным ненулевым значением - PullRequest
Новая
       54

Алгоритм проверки циклическим избыточным кодом, который инвариантен к числу завершающих байтов с конкретным ненулевым значением

0 голосов
/ 25 июня 2018

Предположим, у меня есть произвольный блок байтов.Блок заканчивается остатком CRC, вычисленным по всему блоку с использованием алгоритма CRC-16-CCITT, где остаток расположен в порядке байтов с прямым порядком байтов.После блока и остатка существует произвольное число нулевых байтов, которые продолжаются до конца потока байтов.

Эта схема использует преимущество определенного свойства этого алгоритма 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 для конечных данных (которые используются для заполнения) и, тем не менее, избежать битовой вставки, я намерен xor каждыйбайт данных с 0x55 (хотя это может быть любой другой битовый шаблон, который позволяет избежать вставки) перед обновлением остатка CRC, а затем xor конечного остатка с 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

Мой вопрос заключается в следующем: компрометирую ли я свойства алгоритма обнаружения ошибок введением этой модификации?Есть ли другие недостатки, о которых я должен знать?

1 Ответ

0 голосов
/ 25 июня 2018

При стандартной модели ошибок (биты переключаются независимо с фиксированной вероятностью), недостатка нет.Трудно предвидеть практические трудности.

...