6.5. Циклические коды

Циклические коды - частный случай полиномиальных. Для любого двоичного блока преобразование дает циклический сдвиг вправо этого блока. В циклическом коде сдвиг в любом из его слов дает слово того же кода. Код можно построить с заданным значением кодового расстояния.

Теорема о порождающем полиноме циклического кода. Для любого двоичного циклического -кода существует порождающий полином степени с двоичными коэффициентами, делящий без остатка двучлен . Любое кодовое слово можно представить полиномом из (6.11) степени , где - любой полином с двоичными коэффициентами степени не выше .

Цикличность упрощает кодирование и декодирование с обнаружением ошибок. Вместо задания элементов матрицы в порождающей матрице , достаточно задать коэффициентов полинома . Алгоритм (6.11) смешивает информационные и проверочные символы в каждом кодовом слове. Это затрудняет декодирование. Найдем систематический циклический код. Умножим информационный полином на . Результат разделим на . Получим , где - частное от деления, а - остаток. Так как результаты суммирования и вычитания по совпадают, . Здесь - искомый полином кодового слова, так как он делится на . В полиноме первые членов низшего порядка равны . Коэффициенты остальных равны коэффициентам полинома . Степень полинома меньше . Значит, в полиноме коэффициенты при в степени совпадают с информационными символами. Остальные коэффициенты, определяемые полиномом , - с проверочными символами. Кодирование состоит в умножении на , отыскании остатка от деления на и сложении по остатка с . Эти операции реализуемы в линейных регистрах с ячейками памяти и обратными связями, соответствующими полиному .

Циклический код можно задать также проверочным полиномом

(6.12)

причем для полинома любого кодового слова кода верно соотношение: .

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

Задание кода в (6.11) равносильно его заданию в (6.4). Все уравнения проверки следуют из одного циклическим сдвигом индексов его символов.

Пример 6.5.1. Для циклического кода с порождающим полиномом проверочный полином (см. (6.12)). Из соотношения следуют уравнения проверки. Умножая и приравнивая коэффициенты при , и в произведении, выразим проверочные символы: , , . На рис. 6.3 показана схема кодера циклического кода .

Рис. 6.3. Схема кодера циклического кода с проверочным полиномом ; - ячейки сдвигающего регистра, - сумматор по

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

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

Для кода, обнаруживающего все одиночные ошибки, полином ошибок , . Самый простой полином , не делящий полином , - . Согласно (6.11), делится на . Остаток от деления на зависит лишь от вектора ошибки. Ошибки можно исправить, используя таблицу соответствия между и в памяти декодера. Цикличность упрощает декодирование. Пусть циклический код с кодовым расстоянием исправляет все ошибки кратности ( - целая часть от ). Один из алгоритмов исправления ошибок основан на свойствах синдрома такого кода:

а) если искажены лишь проверочные символы, вес вектора синдрома , а сам синдром совпадает с вектором ошибок;

б) если искажен хоть информационный символ, вес синдрома ;

в) если - остаток от деления на , остаток от деления на - полином ; то есть, синдром некоторого циклического сдвига полинома является соответствующим циклическим сдвигом синдрома исходного полинома;

Пример 6.5.2. На рис. 6.4 показана схема декодера для кода с порождающим полиномом и кодовым расстоянием .

Код исправляет все однократные ошибки. Принятое кодовое слово поступает в буферный регистр сдвига (для запоминания и циклического сдвига) и на устройство деления на полином (для расчета синдрома). Сначала ключ - в положении . После и тактов буферный регистр будет загружен, а в регистре устройства деления найден синдром. Если вес синдрома , декодер делает циклические сдвиги слова в буферном регистре (без нового слова на входе) и находит их синдромы в устройстве деления. Если вес синдрома станет , ключ переходит в положение . Обратные связи в регистре деления разрываются. Далее, за тактов, ошибки исправляют, подав содержимое регистра деления на вход сумматора буферного регистра. Символы информации занимают старшие разряды исправленного слова, как и в исходном состоянии.

T7

Рис. 6.4. Структурная схема декодера циклического кода

Коды Хэмминга (см. п. 6.2) – циклические, а - порождающий полином кода Хэмминга . Из циклических широко применяют коды Боуза-Чоудхури-Хоквингема (БЧХ). Их порождающие полиномы заданы своими определенными корнями. Можно показать, что для любых целых и есть двоичный код БЧХ длины с кодовым расстоянием и числом проверочных символов . БЧХ коды умеренной длины дают выигрыш в помехоустойчивости при относительно низкой скорости передачи: .

Цикличность упрощает расчет синдрома, но не исключает запоминания векторов в таблице декодера. Сложность декодирования экспоненциально зависит от . Есть методы с полиномиальной сложностью декодирования. Например, - алгебраические методы декодирования для БЧХ и подобных им кодов и мажоритарные методы декодирования. В ом случае ошибочные разряды принятых кодовых слов находят, решая некоторые системы линейных уравнений вместо перебора всех видов ошибок. Во ом случае берут линейные коды с разделенными проверками. Каждый из символов блока входит лишь в одну из проверок для любого символа блока. В коде , дуальном коду Хэмминга, ый символ блока удовлетворяет проверкам: . Делая проверки, решают: или , в зависимости от того, будет больше в их результатах или . Мажоритарное декодирование возможно не всегда.