Циклические коды
Циклические коды
Циклический код имеет образующую матрицу G, все строки которой получены циклическим сдвигом одной строки – слова, соответствующего образующему многочлену. Дан пример образующей матрицы с многочленом g(x)=x3+x1+x0 .
Циклический сдвиг n - разрядного слова на один разряд означает умножение многочлена А(х), соответствующего этому слову, на «х» с операцией «приведения» по модулю хn+1, если 1 выходит при сдвиге за разрядную сетку:
A(x)x - xn +1 = A(x)x +xn+1
(операции суммирования и вычитания по модулю 2 дают одинаковый результат). Т.к. любое разрешенное слово является суммой строк порождающей матрицы, его можно представить в виде
|
|
Следовательно, если многочлен (xn+1) делится на g(x), то и любое разрешенное слово делится на образующий многочлен.
Формирование и проверка слова циклического кода
1. Информационное к - разрядное слово U(x) умножаем на xn-k, т.е. приписываем к слову (n-k) нулей со стороны младшего разряда.
Рекомендуемые материалы
2. Слово U(x)xn-k делим на порождающий многочлен g(x), в результате получаем многочлен Q(x) и остаток r(x).Следовательно, U(x) xn-k = g(x)Q(x) + r(x), или
U(x) xn-k + r(x) =g(x)Q(x). (1)
3. Формируем слово циклического кода V(x), приписывая остаток r(x) к слову U(x) со стороны младших разрядов. Из (1) следует, что многочлен кода V(x) делится на g(x) без остатка.
4. Для обнаружения ошибки в принятом слове его делят на порождающий многочлен.
Ненулевой остаток при делении слова V(x) на многочлен g(x) – признак ошибки. Нулевой остаток не гарантирует отсутствия ошибки, т.к. любой помехоустойчивый код выявляет только ошибки определенного типа.
Большинство применяемых на практике блоковых кодов – циклические. Разные классы циклических кодов разработаны для обнаружения и исправления ошибок определенного типа. Корректирующая способность кода зависит от образующего многочлена.
Коды Хемминга исправляют одиночную ошибку.
Коды Боуза-Чоудхури-Хоквингема (БЧХ) исправляют множественные ошибки. Их параметры n, k, s (s - кратность исправляемой ошибки) выбираются в широком диапазоне. Например, (255, 187, 9), (127, 8, 31), (63, 39, 4).
Коды Голея исправляют ошибки кратности выше 1.
Коды Рида-Соломона (не двоичные) способны исправлять несколько пакетов ошибок.
Коды Бартона, Файра предназначены для исправления одиночного пакета ошибок определенной длины.
Кодирование и декодирование циклических кодов
Рекомендуем посмотреть лекцию "10 Подсудность гражданских дел".
Формирование и обработка циклических кодов сводится к делению многочленов, выполняемому с использованием сдвиговых регистров с обратными связями. При делении делитель – порождающий многочлен вычитается сначала из делимого, затем из остатков. Процесс деления, при формировании слова циклического кода (7, 3) с порождающим многочленом g(x)=x3+x2+1 = 1101 поясняет рисунок.
К исходному слову U(x) = x3+1 = 1001 приписывается три нуля со стороны младших разрядов. Полученное слово x6+x3 = 1001000 делится на порождающий многочлен. Делимое за 3 такта вводится в сдвиговый регистр, после чего начинается процесс деления: на каждый такт, когда появляется 1 на выходе регистра, к содержимому регистра прибавляется делитель (то же самое, что и вычитается) и результат, полученный в регистре, сдвигается. Если на выходе регистра появляется 0, выполняется только сдвиг слова в регистре.
Деление столбиком показывает, что старшие разряды делимого и делителя не влияют на остаток, т.к. содержат 1 и сумма этих разрядов всегда равна 0. Поэтому сумматор для сложения старших разрядов не требуется, старший разряд х3 делителя - порождающего многочлена g(x) в вычислениях не участвует, а триггер для хранения разряда х6 делимого не предусматривается. Остатки, получаемые в процессе деления, выделены на рисунке жирным шрифтом.
Сдвиговые регистры с обратной связью используются как при формировании, так и при проверке циклического кода на отсутствие ошибок. Задача исправления ошибки, в случае ее обнаружения, сводится к определению вектора ошибки по синдрому (остатку от деления). В кодах Хемминга с исправлением одиночной ошибки эта задача решается просто. С увеличением кратности исправляемой ошибки декодирование сильно усложняется.
