CRC - таблица поиска 16 бит с использованием различных полиномиальных обозначений

Question

Я использую 16-битный CRC и имею генератор таблицы поиска (LUT), который производит LUT для данного многочлена. Генератор код я использует обозначения Купмана (например, 0x8810 для МККТТ) и, следовательно, производит первую строку таблицы, как:

0x0000, 0x8810, 0x9830, 0x1020, 0xB870, 0x3060, 0x2040, 0xA850, 

Я нашел уже вычисленный CCITT-таблицу с реализацией в Интернете однако, по-видимому использует другие нотация с первой линией определяется как:

0x0000,0x1021,0x2042,0x3063,0x4084,0x50a5,0x60c6,0x70e7, 

Мой вопрос: есть ли короткие и длинные нотации (0x8810 против 0x11021) дают одинаковые результаты с различными таблицами (т.е. использования в в LUT отличается) или CRC различны, используя один и тот же полином в разных обозначениях?

пс: Насколько я знаю, 0x8810 и 0x11021 являются Неотраженная Купман/«нормальная» нотация и 0x8408 и 0x10811 отраженных из них (для CCITT)

имп: «Код использования» для вторая таблица определяется как:

uint16_t crc16_block(uint16_t crc, uint8_t *data, int len){ 
    int i; 

    for (i = 0; i < len; i++) 
     crc = (crc << 8)^crc16_tbl[(crc >> 8)^data[i]]; 

    return crc; 
} 

Answer 1

обозначения Купман представляет полином, но не многочлен. Вы не можете использовать его в качестве входа в генератор таблицы поиска, который вы использовали. Ваша первая таблица бесполезно, так как подразумеваемая многочлен не имеет низкий бит 1.

нотации Купман зависит от того, что все полиномы CRC конца в 1. Многочлен всегда имеет срок + 1. Когда они преобразуются в двоичные, они всегда начинаются с 1 (самая высокая мощность x) и всегда заканчиваются 1. Например. 10001000000100001 или 0x11021, для CCITT полинома, ^{х 16 х} + + х +1.

Досадная вещь об этом номере состоит в том, что для представления требуется 17 бит. Вы хотели бы иметь обозначение, которое использует только 16 бит, чтобы упростить указание полинома в компьютерной программе с 16-разрядными целыми числами (или аналогичным образом, для 32-битного CRC необходимо 32 бита вместо 33 бит).

Существует два решения. Отбросьте максимум 1 или опустите нижний уровень 1. Обычно вы увидите, что высокий 1 упал. То есть 0x1021, плюс вам тогда также необходимо указать длину CRC, 16 в этом случае. Таким образом, спецификация 16, 0x1021. (Есть и другие вещи, которые нужно указать, как хорошо, но сейчас мы ограничимся размером CRC и полиномом.)

Купман понял, что если вместо этого вы сбросили низкий 1, вы Wouldn» t даже нужно указать длину и по-прежнему указывать 16-битовый многочлен CRC в 16 бит. Вы понижаете низкий 1, сдвигая вниз. Таким образом, 0x11021 становится 0x8810. Высокий 1 все еще существует, поэтому он неявно определяет длину CRC.

Однако, чтобы сделать использование в виде CRC в обозначениях Купмана, вы должны переложить его на один и добавьте, чтобы получить полином для расчета и таблицы.