ГЛАВА 13. КОДЫ И АЛГОРИТМЫ ДЛЯ ДЕКОДИРОВАНИЯ МАЖОРИТАРНЫМ МЕТОДОМ

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

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

13.1. ДЕКОДИРОВАНИЕ МАЖОРИТАРНЫМ МЕТОДОМ

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

Напомним, что любой линейный -код над имеет проверочную матрицу а кодовые слова удовлетворяют

равенсхву Если ограничиться рассмотрением строки матрицы то получаегся проверочное равенство

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

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

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

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

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

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

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

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

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

Доказательство следует непосредственно.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Существует таких равенств, и каждое а, входит в из них. Складывая все такие равенства, имеем

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

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

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