General CRC Syndrome Detector

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

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

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

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

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

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

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

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

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