Следовательно, / (<J - 1) < п - 1, и мажоритарный декодер может исправлять JI2 ошибок, □

Итак, при мажоритарном декодировании нельзя декодировать на радиусе упаковки кода, если не выполняется неравенство

< (п - \)1 (й - 1) + 1.

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

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

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

Определение 13.1.7. Множество проверочных соотношений называется согласующимся в множестве координат i, i, U, если существует множество коэффициентов Л1, А, А,., такое, что сумма Aid + AzQ + • • • + ArCi входит в каждое проверочное равенство данного множества и каждая компонента q при 1ф il, i, г,. входит не более чем в одно проверочное равенство множества.

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

Теорема 13.1.8. Пусть d - минимальное расстояние кода, дуального коду над GF (q). Тогда Ь-шагсеый мажоритарный декодер для может исправлять не более nid - 1/2 ошибок.

Доказательство. Чтобы исправлять / ошибок, прежде всего необходимо составить J = 2t проверочных равенств, согласующихся в некотором множестве В, содержащем b координат. Каждое такое равенство соответствует линейной комбинации строк матрицы Н, и эти линейные комбинации представляют собой кодовые слова дуального кода Пусть число ненулевых компонент в /-М проверочном равенстве, не считая компонент, коорди-

г=1 \ i=i

Теперь необходимо вывести второе условие. Разность двух кодовых слов дуального кода также представляет собой кодовое слово, у которого в b позициях стоят нули. Отсюда следует, что при /ф V

Существует J {J - 1) таких равенств, и каждое щ входит в 2 (J - 1) из них. Складывая все такие равенства, имеем

2{Jl)aiJ{J-l)d.

Наконец, исключим 5]/=iGb используя это равенство и полученное ранее. Это дает

2J (n~d) J (J - 1) d.

Так как мажоритарный декодер может исправлять J/2 ошибок, отсюда следует утверждение теоремы. □

Из этой теоремы, в частности, следует, что (23,12)-код Голея не может быть декодирован мажоритарным методом.

13.2. СХЕМЫ МАЖОРИТАРНОГО ДЕКОДИРОВАНИЯ

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

наты которых принадлежат В, равно Oi, 1=1, J- Эти равенства соответствуют кодовым словам дуального кода, и поэтому

Ь + щ-й.

Суммируя эти J соотношений, получаем

Л+ Ц G, Jd. 1=1

Так как каждая компонента, координата которой не принадлежит множеству В, может быть ненулевой не более чем в одном проверочном равенстве, то

йг < п - 6.

Исключая Ь, получаем

13.2. СХЕМЫ МАЖОРИТАРНОГО ДЕКОДИРОВАНИЯ 453

В качестве первого примера рассмотрим (7,3)-код, дуальный (7,4)-коду Хэмминга. Этот код, известный под названием симплексного, имеет минимальное расстояние 4 и может исправлять одну ошибку. Так как 1 <: (7-1) (3 -1)-V2 = 3/2, теорема 13.1.6 не исключает возможности мажоритарного декодирования. Один из способов нахождения проверочной матрицы для этого кода основан на том, что в циклическом коде а" и являются корнями порождающего многочлена, лежащими в GF (8). Следовательно,

а» ао «о ао а» а» а»

Над GF (2) эта матрица принимает вид

1111111

10 1110 0 1110 0 10 0 0 10 111

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

1111111

0 0 10 111 .0100011 .•

.0 0 01101 • •

". 1001011

1 1 о о 1.0 1 1 0 1 0 0 0 1 0 1110 0 1

Выбрав третью, четвертую и седьмую строки, получим равенства

Со + + Сб = О,

Со + Са + Сз = О, •

Со + С4 + Сб = О,

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