4.3. Методы мажоритарного декодирования

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

быть просто реализованы. Типичными представителями таких кодов являются коды, допускающие мажоритарное декодирование (см. разд. 4.5.2). В некоторой области значений параметров эти коды имеют корректирующую способность, незначительно уступающую корректирующей способности БЧХ-кодов, но зато их можно проще реализовать [3, 4, 22—24].

Определим -ичную мажоритарную функцию от переменных принимающих значения в следующим образом:

1) Если некоторые переменных принимают одно и то же значение а, то значение мажоритарной функции также равно а.

2) Во всех остальных случаях мажоритарная функция принимает нулевое значение.

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

Вначале поясним метод порогового декодирования на простом примере.

Пример 4.9. Рассмотрим -код максимальной длины. Матрица в данном случае имеет следующий вид:

Пусть вектор ошибок, компоненты синдрома. Тогда

Положив получаем

Заметим, что каждая из компонент вектора ошибок, за исключением входит только в одну из сумм Предположим, что произошла только одна ошибка. Тогда, если то одна из сумм будет равна 1, а остальные две будут равны 0. Если то Следовательно, при отсутствии ошибок, а также при одиночных ошибках

Так как рассматриваемый код является циклическим, то аналогичные соотношения имеют место и для остальных

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

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

1) для любого существует такое что

2) для любого все символы за исключением, быть может, одного, равны 0. Такие линейные -суммы называются ортогональными относительно

Линейные -суммы и из примера 4.9 ортогональны относительно

Вес вектора будем, как обычно, обозначать через

Лемма 4.4. Если линейные -суммы ортогональны относительно линейной -суммы и то

Доказательство. Пусть Если

то, согласно условию 2 ортогональности, среди самое большее линейных -сумм отличны от нуля. В этом случае справедливость соотношения (4.20) непосредственно следует из определения Если хотя бы для одного то количество компонент не превышает Но тогда из определения ортогональности получаем, что не меньше чем линейных -сумм среди равны Таким образом, в этом случае равенство (4.20) также выполняется.

Если в лемме то формула (4.20) принимает следующий вид:

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

Указанную выше идею порогового декодирования в один шаг можно развить дальше следующим образом. Выше предполагалось, что являются проверочными суммами. Здесь же будем считать, что это просто линейные -суммы, для каждой из которых, однако, существуют проверочных сумм ортогональных относительно Тогда, если то, вычисляя по принятому вектору у значения всех проверочных сумм с помощью леммы 4.4 можно найти значения всех линейных -сумм далее, вновь обращаясь к лемме 4.4, найти В этом случае говорят, что ошибки веса до можно исправить с помощью порогового декодирования в 2 шага. Совершенно аналогично можно описать декодирование в шагов. В последнем случае говорят, что ошибки веса до включительно можно исправить с помощью порогового декодирования в шагов.

Этот метод первоначально был предложен Ридом [25] для декодирования кодов Рида—Маллера (см. разд. 4.5). Имеет место следующая теорема [4, 24].

Теорема 4.2. Пусть код С допускает исправление ошибок веса до с помощью порогового декодирования в один шаг. Тогда, если код двойственный к коду С, имеет минимальное расстояние то

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

Из этой теоремы видно, что возможности порогового декодирования в один шаг очень ограничены. Например, как следует из примера 4.2, в случае двоичного -кода Голея так что . Таким образом, -код Голея, который, вообще говоря, позволяет исправлять ошибки веса 3 и менее, при пороговом декодировании в один шаг позволяет исправлять только одиночные ошибки. Это же можно сказать и о кодах Рида — Соломона (см. пример 4.4). Если минимальное расстояние кода равно и он позволяет исправлять ошибки веса до с помощью порогового декодирования в шагов, то говорят, что код допускает полную ортогонализацию в шагов. Для произвольного имеет место следующая теорема.

Теорема 4.3. Пусть код С допускает исправление ошибок веса и менее с помощью порогового декодирования в шагов. Если минимальное расстояние кода, двойственного к коду С, то

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

может быть отличной от нуля. Следовательно,

Так как , то

С другой стороны, по предположению . Из формул (4.24) и (4.26) имеем

Отсюда и из соотношений (4.22), (4.23), (4.25) в свою очередь следует, что

а поэтому

Если сравнить верхние границы для то можно заметить, что оценка для приблизительно в 2 раза меньше оценки для

Пример 4.10. Рассмотрим -код Хэмминга. Проверочная матрица этого кода была построена в примере 3.5:

Обозначим через проверочные суммы, коэффициентами которых являются элементы соответственно 1, 2 и 3-й строк матрицы Так как

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

Это означает, что проверочные суммы ортогональны относительно во Поскольку суммы во ортогональны в свою очередь относительно во и этот код является циклическим, то, таким образом, мы показали, что рассматриваемый код допускает исправление одиночных ошибок с помощью порогового декодирования в 2 шага и, следовательно, является полностью ортогонализуемым в 2 шага. Этот код представляет собой один из укороченных циклических кодов Рида — Маллера, а описанный здесь метод его декодирования является частным случаем известного общего метода декодирования таких кодов (см. пример 4.12).

Задача 4.9 [26]. Как следует изменить формулировку леммы 4.4, если свойство 2 в определении ортогональности заменить следующим:

2) для любого среди символов отличными от нуля являются самое большее X символов..

Краткое решение. Величину [1/2] следует заменить на Доказательство леммы 4.4 в этом случае проводится аналогично.

Методы декодирования, основанные на лемме 4.4, измененной указанным в задаче 4.9 способом, называются методами порогового декодирования с помощью неортогональных проверок. Область применения этих методов достаточно широка, но они обладают тем недостатком, что при их использовании значительно возрастает число входов мажоритарных элементов [4]. Обобщению методов мажоритарного декодирования и их модификации посвящен ряд работ [4, 27—31]. Наиболее типичные классы кодов, допускающих мажоритарное декодирование, будут рассмотрены в разд. 4.5.2 и 7.7.2.