6. Метод последовательного исключения независимых переменных и мажоритарное декодирование со связанными проверками

Из материала § 5 следует, что если в системе (VII.4.1) можно указать d непересекающихся подсистем, каждая из которых разрешима относительно , то независимая переменная , будет определена правильно по крайней мере тогда, когда принятая комбинация содержит искаженных символов, пели такие условия выполняются для всех независимых переменных, то комбинации кода отличаются не менее чем в d позициях. Однако обратное утверждение неверно. Так, например, в случае семизначного бинарного кода с система уравнений (VII.4.1) имеет вид:

(VII.6.1)

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

(VII.6.2)

Решения имеют вид:

(VII.6.3)

Каждое уравнение (VI1.6.1) входит не более чем в две подсистемы (VII.6.2). Поэтому, если в принятой комбинации окажется один искаженный символ, то только две из пяти подсистем будут решены неправильно, и истинное значение может быть найдено по большинству «голосов». Легко проверить, что и для остальных независимых переменных могут быть составлены уравнения вида (VII.6.3).

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

Обозначим через значение первого информационного символа, найденное из (VII.6.3) в результате «голосования». Подставляя в систему уравнений (VII.6.1), получим систему из 6 уравнений, содержащую три (в общем случае ) независимые переменные:

(VII.6.4)

где

(VII.6.5)

Система (VII.6.4) существенно проще системы (VII.6.2), поэтому и задача отыскания значений решается значительно легче:

(VII.6.6)

откуда следует:

(VII.6.7)

Обозначим через значение второго информационного символа, найденное из (VII.6.7) в результате «голосования». Заметим, что оно будет истинным, если было истинным и среди символов, стоящих в правой части (VII.6.4), имеется не более одного трансформированного. Подставляя в (VII.6.4), получим систему пяти уравнений, содержащую две независимых переменных. Из нее определяется и т. д. Методом последовательного исключения независимых переменных [55] могут декодироваться все линейные коды, при этом в небинарных кодах оказывается необходимым использование более сложных логических операций, чем процедура голосования [55]. Отметим, что весьма просто синтезируются базисные матрицы достаточно эффективных кодов, априори рассчитанных на такой метод опознания информационных символов. Метод последовательного исключения независимых переменных позволяет осуществить мажоритарное декодирование с простым сдвигом символов комбинации кодов, как допускающих мажоритарное циклическое декодирование с независимыми проверками, так и целого ряда кодов, не наделенных этим свойством.

На рис. VII.4 показано устройство, предназначенное для декодирования комбинаций кода (VII.5.36) методом последовательного исключения независимых перемеых.

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

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

В табл. VII.4 шаг за шагом показан процесс выделения независимых переменных в предположении, что принятая комбинация не содержит искаженных символов.

После четырех тактов работы схемы состояния ячеек РП определяются последней строкой табл.VII.4. Любопытно отметить, что если выполнить операции, «обратные» описанным выше, то образуется последовательность символов, соответствующая системе линейных форм, записанных в первой строке таблицы VII.4. Поэтому формирование комбинаций рассматриваемого кода может быть выполнено с помощью устройства, показанного на рис. (VII.5. Его работа протекает следующим образом.

Таблица VII.4

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

Рис. VII.5. Кодирующее устройство для кода (9, 4, 3) и (8, 4, 3).

такта работы схемы в ее ячейках памяти окажется записана комбинация кода (VII.5.36).

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

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

только что описанного типа. При этом следует иметь в виду, что отличные от нуля начальные состояния некоторых ячеек регистра памяти кодера являются следствием характерных особенностей кода (VII.5.36). Действительно, если предположить, что первоначальные состояния ячеек РП были нулевыми, то после четырех тактов работы схемы рис. VII.5. образуется код (система линейных форм)

(VII.6.8)

Опознание информационных символов (VII.6.8) выполняется по схеме рис. VI1.6, регистр которой содержит не девять, а восемь ячеек памяти (последняя форма в (VII.6.8) не влияет на процесс декодирования информационных символов).

Рис. VII.7. Кодирующее устройство для кода (7, 3, 4).

Таким образом, при нулевых начальных условиях образуется код с значности, меньшей, чем (VII.5.36) с простой схемсгй кодирования и декодирования. Обратим внимание на то, что к коду (VII.6.8) не применим метод мажоритарного циклического декодирования.

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

Можно убедиться, что комбинации кода (VII.5.35) также опознаются способом, аналогичным рассмотренному выше, а их формирование может проводиться с помощью схемы рис. (VII.7) при нулевых начальных состояниях ячеек регистра памяти.

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

(VII.6.9)

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