General CRC Generator

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

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

Алгоритм делит на , и устанавливает контрольную сумму равной двоичному вектору, соответствующему остатку. То есть, если , где – полином степени меньше , то контрольной суммой будет двоичный вектор, соответствующий . При необходимости алгоритм добавляет нули к контрольной сумме, чтобы она имела длину .

Функция генерации CRC, которая реализует фазу передачи алгоритма CRC, делает следующее:

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

Алгоритм CRC использует двоичные векторы для представления двоичных полиномов в порядке убывания их силы. Например, вектор [1 1 0 1] представляет полином .

Биты поступают в регистр сдвига с линейной обратной связью (linear feedback shift register, LFSR) в порядке от младшего бита к старшему. Последовательность входных битов сообщения представляет собой коэффициенты полинома сообщения в порядке убывания мощности. Вектор сообщений дополняется нулями, чтобы вымыть LFSR, где – степень порождающего полинома. Если на выходе левого каскада регистра d(1) стоит 1, то выполняется операция XOR битов cдвигового регистра с коэффициентами порождающего полинома. Когда дополненная последовательность сообщений полностью проходит через LFSR, в регистре остается контрольная сумма [d(1) d(2) …​ d(r)]. Это реализация двоичного длинного деления, в котором последовательность сообщений является делителем (числителем), а полином – делимым (знаменателем). Контрольная сумма CRC – это остаток от операции деления.

На блок-схеме показан алгоритм прямого CRC.

Здесь Ввод блока сообщений – это , а Вывод кодового слова – это

Начальный этап прямого CRC-кодирования происходит, когда три переключателя находятся в положении . Алгоритм подает на кодер биты сообщения . Эти биты являются первыми битами выходного кодового слова. Одновременно алгоритм посылает битов в регистр сдвига с линейной обратной связью (LFSR). Когда система полностью передает все бит сообщения в LFSR, переключатели переходят в положение . Здесь LFSR содержит математический остаток от деления полинома. Эти биты смещаются из LFSR и являются оставшимися битами (контрольной суммой) на выходе кодового слова.