ГЛАВА 7. ЛИНЕЙНЫЕ ПЕРЕКЛЮЧАТЕЛЬНЫЕ СХЕМЫ

Основу оборудования, используемого при кодировании и при исправлении или обнаружении ошибок с помощью линейных кодов, составляют линейные переключательные схемы с конечным числом состояний. В разд. 7.2, 7.3 и 7.4 дается описание некоторых схем, используемых при реализации линейных кодов. Дальнейшие свойства этих схем даются в разд. 7.5. В разд. 7.6 вводится общая теория линейных переключательных схем с конечным числом состояний, причем показывается, что любая линейная переключательная схема эквивалентна некоторой схеме типа схемы, описываемой в разд. 7.2.

7.1. Определения

Предполагается, что в линейных переключательных схемах информация представлена с помощью элементов поля GF(q). Используются три вида устройств. Первое из них — сумматор, имеющий два входа и один выход, равный сумме входов. Второе — это запоминающее устройство, имеющее один вход и один выход. Оно может быть устройством с задержкой и иметь выход, всегда совпадающий со значением, которое вход принял в предшествующий момент времени. Его можно рассматривать также как разряд регистра сдвига. В регистре сдвига имеется сигнал сдвига, не показанный на схемах и приходящий со схемы синхронизации. В момент прихода этого сигнала выход каждого разряда принимает значение, которое было на входе непосредственно перед сигналом сдвига. Третий вид устройств — это устройство умножения на постоянную величину, имеющее один вход и один выход, равный просто входу, умноженному на постоянную величину. Этой постоянной может быть любой элемент поля. Правило взаимодействия этих устройств состоит в том, что любое число входов может быть соединено с любым выходом, но никакие два выхода не могут быть соединены вместе. Изображения этих устройств, принятые в схемах, показаны на рис. 7.1.

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

вычислительных машинах. В случае двоичного кода сумматор тождествен логической схеме "исключающего или", а запоминающее устройство совпадает либо с устройством задержки, либо с разрядом обычного двоичного регистра сдвига. Умножение на постоянную величину для постоянной, равной 1, равносильно наличию связи в схеме, а для постоянной, равной 0, — отсутствию связи.

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

Рис. 7.1. Блоки, являющиеся составными элементами линейных переключательных схем. а — сумматор; б - запоминающее устройство, хранящее а, т. е. таное, что его выход равен а; в — устройство умножения на постоянную величину а.

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

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