ГЛАВА 13

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

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

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

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

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

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

ству сН = 0. Если ограничиться рассмотрением /-й строки матрицы Н, то получается проверочное равенство

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

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

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

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

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

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

Si = т] "j: Hcpt = Hi) Hi;ei.

i=0 i=--0

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

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

всех Sj равны Ch, если равно нулю, и более J/2 всех Sj равны й, если fife отлично от нуля. Поэтому находится мажоритарным решением по Sj. □

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

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

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

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

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

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

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

Теорема 13.1.6. Пусть й-минимальное расстояние кода, дуального коду над GF (q). Тогда мажоритарный декодер для может исправить не более (п - 1) (<J - 1)"V2 ошибок.

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