Основы теории передачи информации


Неалгебраические методы декодирования циклических кодов


Все методы декодирования линейных блочных кодов можно разбить на две группы: алгебраические и неалгебраические.

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

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

Одним из неалгебраических методов является декодирование с использованием алгоритма Меггитта, пригодного для исправления как одиночных, так и l-кратных ошибок (на практике l £ 3).

При декодировании в соответствии с алгоритмом Меггитта также вычисляется синдром принятой последовательности S(x), однако используется он иначе, нежели в рассмотренных ранее синдромных декодерах.

Идея, лежащая в основе декодера Меггитта, очень проста и основывается на следующих свойствах циклических кодов:

-  существует взаимно-однозначное соответствие между множеством всех исправляемых ошибок и множеством синдромов;

-  если S(x) — синдромный многочлен, соответствующий многочлену ошибок    е(x),   то   x×S(x) mod g(x)  —  синдромный   многочлен, соответствующий  x× e(x) mod (xn + 1).

Равенство а(x) = b(x) mod p(x) читается как а(x), сравнимо с b(x) по модулю р(x)” и означает, что а(x) и b(x) имеют одинаковые остатки от деления на полином p(x).

Таким образом, второе условие означает, что если комбинация ошибок циклически сдвинута на одну позицию вправо, то для получения нового синдрома нужно сдвинуть содержимое регистра сдвига с обратными связями, содержащего S(x),  также на одну позицию вправо.

Следовательно, основным элементом декодера Меггитта является сдвиговый регистр. Структурная схема декодера Меггитта для циклических кодов произвольной длины приведена  на рис. 1.15.

Рис. 1.15

Декодер работает следующим образом. Перед началом работы содержимое всех разрядов регистров равно нулю. Принимаемая последовательность r в течение первых n




Начало  Назад  Вперед



Книжный магазин