13.7. КОДИРОВАНИЕ И ДЕКОДИРОВАНИЕ (II)

Алгоритм Рида неприменим при систематическом кодировании РМ-кода как расширенного циклического кода (такое кодирование описано в § 7.8). К счастью, в этом случае работает другая

схема мажоритарного декодирования, и ее описание приведет нас к более общему классу кодов — конечно-геометрическим кодам

Если некоторый -код над GF(q) с проверочной матрицей то слова этого кода должны удовлетворять системе проверочных уравнений, задаваемых строками матрицы

Ясно, что каждая линейная комбинация строк проверочной матрицы также задает проверочное соотношение, таким образом, всего имеется проверок Идея мажоритарного декодирования состоит в выборе наилучшего подмножества проверок

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

Пример Рассмотрим [7, 3, 4] симплексный код с проверочной матрицей

На рис 13 7 приведены 7 из 16 возможных проверок для этого кода

Рис. 13.7 Проверки для -кода

Строкам 1, 5 и 7 на рис 13 7 соответствуют проверочны уравнения

которые ортогональны относительно координаты 0. На рис. 2.12 это, очевидно, соответствует линиям, проходящим через точку 0. Аналогично линии, проходящие через точку 1, задают три проверочных уравнения, ортогональных на координате 1, и т. д.

Предположим, теперь что вектор ошибок равен так что получен вектор Если имеется проверок, ортогональных относительно координаты 0, то обозначим через результаты применения этих проверок к вектору у. Для рассмотренного выше примера имеем:

Теорема 15. Если число ошибок не превосходит то правильное значение равно величине, принимаемой большинством проверок в случае альтернативы принимается решение

Доказательство. Предположим, что произошло не более чем ошибок, (i). Если то не более чем — проверок могут быть искажены. Следовательно, по меньшей мере величин будут равны 0.

(ii). Если то заведомо меньше чем проверок будут искажены остальными ошибками. Следовательно, большинство из величин будут равны

Следствие 16. Если для каждой координаты имеется проверок, ортогональных относительно нее, то код может исправлять — ошибок.

Замечания. (i). Если код циклический, то, найдя проверок, ортогональных относительно одной координаты, системы ортогональных проверок для остальных координат можно получить путем циклического сдвига первой системы проверок.

(ii). Из хода доказательства теоремы 15 видно, что некоторые векторы ошибок, вес которых больше чем могут привести к неправильному декодированию. Однако одно из замечательных свойств мажоритарных декодеров состоит в том, что (без удорожания устройства) они позволяют правильно декодировать многие векторы ошибок, вес которых больше чем

(iii). В случае альтернативы решение принимается в пользу если 0 является одной из альтернатив; в противном случае

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

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

Теорема 17. Число ошибок, которые можно исправить мажоритарным декодированием в один шаг, для произвольного кода над GF(q) не превосходит где минимальное расстояние дуального кода.

Доказательство. Проверки, ортогональные относительно первой координаты, имеют вид

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

Примеры. (1). Для -кода Голея следовательно, мажоритарное декодирование в один шаг позволяет исправить самоебольшое ошибку.

(2). Большинство кодов РС также не могут быть декодированы мажоритарным образом в один шаг, так как для них

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

Декодирование в L шагов. Некоторые коды, например РМ коды, могут быть декодированы за счет многократного использования мажоритарной процедуры.

Определение. Множество проверок называется ортогональным относительно координат если сумма входит в каждую проверку этого множества, а все остальные входят не более чем в одну проверку этого множе» ства.

Пример. Декодирование [7, 4, 3]-кода в два шага. Рассмотрим семь ненулевых проверок.

Среди них имеются две проверки, ортогональные относительно координат 0 и 1, а именно:

и две, ортогональные относительно координат 0 и 2

и т. д. Предположим, что произошла одна ошибка. Тогда мажоритарное правило дает правильное значение (из первой пары уравнений) и правильное значение (из второй пары). Далее уравнения

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

Рис. 13.8. Двухшаговый мажоритарный декодер для -кода

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

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

Лемма 18. Если каждый уровень мажоритарного декодера содержит проверок, то могут быть исправлены — ошибок.

Доказательство. Аналогично доказательству теоремы 15. Даже -шаговое декодирование может оказаться недостаточным для того, чтобы исправлять все ошибки вплоть до половины минимального расстояния.

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

где d - минимальное расстояние дуального кода.

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

Пусть Тогда и из (13.14) следует, что

Исключая получаем, что а исключая приходим к неравенству

Пример. Для -кода Голея -шаговое мажоритарное декодирование не позволяет исправлять больше чем две ошибки.

Контрастом к этому является следующее утверждение. Теорема 20. Для РМ кода порядка мажоритарное декодирование в шагов позволяет исправлять ошибок.

Доказательство. Дуальным к является код и согласно теореме 8 слова минимального веса в являются векторами инцидентности -мерных плоскостей в

Пусть V — некоторая -мерная плоскость. Найдем множество проверок, ортогональных относительно координат для Действительно, пусть -мерная плоскость, содержащая Ясно, что каждая из точек, не принадлежащих V, определяет некоторую плоскость и что каждая плоскость полностью задается такими точками. Следовательно, всего имеется различных плоскостей Любые две такие плоскости пересекаются только по Это дает нам оценку для суммы причем оценка будет правильной, если произойдет не более чем ошибок.

Такое решение может быть принято для каждой -мерной плоскости

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

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

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

Иллюстрацией к этому является пример [7, 4, 3]-кода, для которого на рис. 13.8 приведена схема, реализующая декодирование в два шага. На самом деле этот код является кодом

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

Заметим, что

Таким образом, если мы согласимся подождать один такт, то может быть получено без введения дополнительного мажоритарного элемента. Соответствующая схема декодера показана на рис. 13.9.

Рис. 13.9. Декодер для [7, 4, 3]-кода, основанный на методе последовательной редукции кода

В общем случае этот метод (если он применим) позволяет уменьшить число мажоритарных элементов, сумматоров и т. п. с экспоненциальной функции от числа шагов до линейной функции ценой увеличения линейной задержки (рис. 13.10).

Рис. 13.10. Схема декодера, основанного на последовательной редукции кода (а), и схема А-шагового декодера (б)

Название «последовательная редукция кода» этот метод получил потому, что на каждом последовательном шаге декодирования вводятся дополнительные проверки, так что кодовое слово по существу рассматривается как слово меньшего кода. В рассмотренном примере после первого шага декодирования мы знаем все суммы которые на самом деле являются проверками [7, 1, 7]-кода с повторением.

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

Ссылки на работы о различных модификациях и обобщениях основного алгоритма мажоритарного декодирования даны в замечаниях к главе.

Пороговое декодирование. Вернемся ненадолго опять к вопросу о декодировании произвольного двоичного линейного кода. Предположим, что передано слово х, а получено слово у. Декодер решает, что наиболее правдоподобным вектором ошибок является лидер смежного класса, содержащего вектор у, и декодирует у как . В теореме 5 гл. 1 мы видели, что является функцией синдрома Более точно представляет собой двоичную векторную функцию от компонент вектора Для небольших кодов вектор может быть синтезирован посредством простой комбинаторно-логической схемы, использующей элементы И, ИЛИ и др. и не использующей элементы задержки. В случае циклических кодов эта схема может быть упрощена еще больше, и тогда она называется декодером Меггитта. Устройство, приведенное на рис. 13.8, является простым примером декодера Меггитта (см. также упражнение (36) гл. 7).

Однако синтез вектора для больших кодов (например, для кодов БЧХ, см. рис. 9.5) требует значительно более сложных элементов.

Рис. 13 11. Вычисление вектора ошибок

Например, в данной главе для декодирования РМ-кодов мы использовали мажоритарные элементы. Более общий подход состоит в использовании взвешенных мажоритарных элементов, или пороговых элементов, представляющих собой функции от с действительными весами и определяемых равенством

где все суммы вычисляются как действительные числа.

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

Теорема 21. (Рудольф.) Любой двоичный линейный код допускает пороговое декодирование в один шаг.

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

где - коэффициент Адамара для функции задаваемый равенством (14.8). Тогда

Если — некоторая пороговая функция от входов с весами то из определения функции сразу вытекает, что

где если если Следовательно,

если выбрать Так как это может быть проделано для каждого то теорема доказана.

К сожалению, уравнение (13.16) определяет как пороговую функцию от всех проверок, так что рассмотренный алгоритм практически непригоден. Однако в отдельных случаях удается найти различные одношаговые пороговые алгоритмы вычисления использующие значительно меньшее число проверок (см. замечания к главе).

Задача (нерешенная). (13.2). Найти более эффективную одношаговую пороговую процедуру реализации заданной булевой функции.