Циклические коды (CRC)
Циклические коды – это целое семейство помехоустойчивых кодов, включающее в себя в качестве одной из разновидностей коды Хэмминга, но: целом обеспечивающее большую гибкость с точки зрения возможности реализации кодов с необходимой способностью обнаружения и исправ ления ошибок, определяемой параметром d0, по сравнению с кодами Хэм минга (для которых dQ=3 или d0=4). Широкое использование циклических кодов на практике обусловлено также простотой реализации соответствующих кодеров и декодеров.
Основные свойства и само название циклических кодов связаны с те!\ что все разрешенные комбинации бит в передаваемом сообщении (кодовые слова) могут быть получены путем операции циклического сдвиг некоторого исходного кодового слова:
Циклические коды задаются с помощью так называемых порождающих полиномов (многочленов) g(x) или их корней. Кроме того, вводятся понятия полинома исходного сообщения.
Для этих полиномов, представляющих собой, по существу, альтернативную запись чисел в двоичной системе счисления, определяются опер ции сложения, умножения и деления, необходимые для организации кодирования и декодирования сообщения. Все эти операции выполняются по модулю 2.
Рассмотрим последовательность кодирования на примере циклического кода (7.4.3), имеющего g(x) = х3 + х + 1:
- информационная часть сообщения записывается в виде полинома:
В рассматриваемом примере k = 4 и для сообщения 0111 получаем:
- и(х) умножается хг, что соответствует циклическому сдвигу исходного сообщения на г разрядов влево:
- полученный многочлен делится на g(x):
Где с(х) – полином – частное с максимальной степенью (k-1); R(x) – полином – остаток с максимальной степенью (г-1); (+) – обозначение поразрядной операции суммирования по модулю 2 (исключающее ИЛИ).
Кодированное сообщение представляется в виде:
…то есть на месте младших, освобожденных после домножения на хг, разрядов, записываются проверочные разряды.
Для рассматриваемого примера:
Таким образом, в данном случае А(х) = (х3 + х4 + х3) (+) х = х5 + х4 + х3 + х. Передаваемое кодированное сообщение в обычной двоичной форме имеет вид:
