[Править] Циклические коды

На практике активно применяются полиномиальные коды или циклические избыточные коды (Cyclic Redundancy Code — CRC).

CRC коды построены на рассмотрении битовой строки как строки коэффициентов полинома. k-битовая строка соответствует полиному степени k − 1. Самый левый бит строки — коэффициент при старшей степени. Например, строка 110001 представляет полином x⁵ + x⁴ + x⁰. Коэффициенты полинома принадлежат полю вычетов по модулю 2.

Основная идея заключена в том, чтобы пересылать только такие сообщения, полиномы которых делятся на некоторый фиксированный полином G(x). Если мы получаем сообщение, чей полином не делится на G(x), значит при передаче сигнал был искажен. Мы не заметим ошибок, если они один допустимый полином (то есть полином делящийся на G(x)) преобразовали в другой допустимый полином. Полином G(x) тем лучше, чем больше среднее расстояние Хемминга на парах допустимых полиномов.

Есть два очевидных способа кодирования сообщения в полином, который делится на G(x) — это либо умножить полином исходного сообщения на G(x), либо добавить к нашему сообщению некоторое количество бит так, чтобы результирующий полином делился на G(x). В CRC используется второй способ.

Отправитель и получатель заранее договариваются о конкретном полиноме-генераторе G(x). Пусть степень G(x) равна l. Тогда длина блока «конторольной суммы» также равна l.

Мы добавляем контрольные l бит в конец передаваемого блоку так, чтобы получился полином кратный генератору G(x). Когда получатель получает блок с контрольной суммой, он проверяет его делимость на G. Если есть остаток , то были ошибки при передаче.

Алгоритм кодирования CRC:

Дано слово W длины m. Ему соответствует полином W(x).

1. Добавить к исходному слову W справа r нулей. Получится слово длины n = m + r и полином :

2. Разделить полином на G(x) и вычислить остаток от деления R(x) :x^rW(x) = G(x)Q(x) + R(x);

3. Вычесть остаток (вычитание в то же самое, что и сложение) из полинома  :T(x) = x^rW(x) − R(x) = x^rW(x) + R(x) = G(x)Q(x). Слово, которое соответствует полиному T(x), и есть результат.

Рис. (fig:crc) иллюстрирует этот алгоритм для блока 1101011011 и G(x) = x⁴ + x + 1.

\begin{figure}[h!] \psfrag{Remainder}{Остаток} \centering\parbox{0.66\textwidth}{ \begin{tabular}{lcl} Слово&:&1101011011 \\G(x)&:&10011\\ Результат&:&11010110111110 \end{tabular}} \centering\includegraphics[clip=true, width=0.75\textwidth]{pictures/crc2.eps} \caption{CRC — полиномиальное кодирование} (fig:crc) \end{figure}

Этот метод позволяет отлавливать одиночные ошибки и групповые ошибки длины не более степени полинома.

Существует три международных стандарта на вид G(x):

• CRC − 12 = x¹² + x¹¹ + x³ + x² + x + 1

• CRC − 16 = x¹⁶ + x¹⁵ + x² + 1

• CRC − CCITT = x¹⁶ + x¹² + x⁵ + 1

CRC − 12 используется для передачи символов из 6 разрядов. Два остальных — для 8 разрядных. CRC − 16 и CRC − CCITT ловят одиночные, двойные ошибки, групповые ошибки длины не более 16 и нечётное число изолированных ошибок с вероятностью 0.99997.