5. Метод независимых решений и мажоритарное декодирование с независимыми проверками

Как известно, всякая система уравнений сначала может быть разрешена относительно затем относительно и т. д. В силу избыточности системы (VII.4.1) каждая из ее независимых переменных может быть найдена не единственным образом. Так, в случае (VII.4.2) определяется в результате решения следующих подсистем:

(VII.5.1)

Из (VII.5.1) следует:

(VII.5.2)

Аналогично определяется из решения подсистем:

(VII.5.3)

Отсюда получим:

(VII.5.4)

Наконец независимая переменная является решением четырех различных подсистем:

(VII.5.5)

причем

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

Пусть в системе (VII.4.1) каждая независимая переменная может быть найдена в результате решения d непересекающихся подсистем вида (VII.5.1) из которых содержат точно два уравнения. При этих условиях значение определяется d соотношениями типа (VII.5.2):

(VII.5.6)

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

Пусть канал является симметричным. Тогда вероятности того, что и совпадут с истинным значением равны и а вероятность того, что это не будет иметь место , . Учитывая это, а также статистическую независимость величин (VII.5.6), легко записать отношение правдоподобия:

(VII.5.7)

(VII.5.8)

где , — число величин , совпадающих с единицей, и

(VII.5.9)

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

(VII.5.10)

где

(VII.5.11)

Если неравенство (VII.5.10) не выполняется, то принимается решение .

При (сравнительно малые ) указанный алгоритм вырождается в процедуру принятия решения «по большинству голосов»: , если

(VII.5.12)

, если

(VII.5.13)

Наконец, если

(VII.5.14)

(последнее возможно лишь при четных d).

Правила принятия решения (VII.5.12)-(VII.5.14) часто называют мажоритарным декодированием с независимыми проверками. Впервые такой алгоритм был использован в [147], а затем в различных вариантах обсуждался в [25, 29, 42, 55, 82, 106, 114].

Вероятность неправильного опознания символа

(VII.5.15)

где

Вероятность неправильного опознания комбинации

(VII.5.16)

Для достаточно больших d и сравнительно плохих состояний канала распределения величин можно полагать нормальными с дисперсиями

(VII.5.17)

Средние этих распределений при и определяются величинами

(VII.5.18)

(VII.5.19)

Вероятность неправильного опознания символа теперь записывается так:

(VII.5.20)

где

(VII.5.21)

Наконец, разлагая в ряд, получим

(VII.5.22)

Это соотношение позволяет оценить значение обеспечивающее при фиксированном . Кроме того, из (VII.5.22) следует, что при мажоритарном декодировании с независимыми проверками и фиксированной скорости передачи вероятность по мере роста значности кода если d растет быстрее, чем . Аналогичное положение имеет место и при приеме с двумя градациями верности. В этом случае оптимальный (по критерию максимума отношения правдоподобия) процесс опознания сводится к следующему. Прежде всего вычисляется величина

(VII.5.23)

где , если -надежный символ, и

в противном случае; , причем значение зависит от числа ненадежных символов, входящих в правую часть -го равенства (VII.5.6);при этом величины

(VII.5.24)

(VII.5.25)

(VII.5.26)

Следует считать , если

(VII.5.27)

и полагать в противном случае. (Правая часть (VII.5.27) обращается в нуль, если в (VII.5.23) допустить, что , а не ). Вероятность неправильного опознания символа и комбинации здесь оценивается по формулам (VII.5.20) и (VII.5.22), если в них положить

(VII.5.28)

где

(VII.5.29)

(VII.5.30)

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

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

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

(VII.5.31)

Значность таких кодов при достаточно больших равна

(VII.5.32)

а скорость передачи равна

(VII.5.33)

Так, например, для получим код

(VII.5.34)

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

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

Изменим порядок следования уравнений в системе (VII.4.2):

(VII.5.35)

Схема для определения независимой переменной показана на рис. VII.2. Она состоит из регистра памяти , трех сумматоров по модулю два и мажоритарного селектора МС (устройства, в котором решение о том, является ли нулем или единицей, принимается по большинству голосов).

Легко видеть, что при сдвиге влево на один шаг символов, записанных в РП, на все четыре входа МС поступит независимая переменная [на первом входе на втором на третьем наконец, на четвертом .

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

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

Например, Грушко И. И. построила нециклический код, но допускающий

Рис. VII.2. Блок-схема декодера, предназначенная для мажоритарного циклического декодирования кода (7, 3, 4).

циклическое мажоритарное декодирование с независимыми проверками (рис. VII.3):

(VII.5.36)

Этот код не является циклическим, так как его комбинация 100011100 при циклическом сдвиге на 7 тактов

Рис. VII.3. Блок-схема декодера, предназначенная для мажоритарного циклического декодирования информационных символов нециклического кода (9, 4, 3).

вправо приводит к комбинации 001000111, которая не принадлежит коду. В этом легко убедиться, если подставить в (VII.5.36) и .