Устройство для умножения полиномов над конечными полями GF(2 @ ) Советский патент 1991 года по МПК G06F15/31 

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

Целью изобретения является повышение быстродействия устройства.

На чертеже представлена схема устройства для умножения полиномов над конечными полями GF(2m).

Устройство для умножения полиномов над конечными полями GF(2m) содержит блок 1 деления на примитивный элемент поля GF(2m), блок 2 умножения на примитивный элемент поля GF(2m), генератор 3 тактовых импульсов, дешифратор 4, группу

элементов И 5i, 62.5з5т, первый и второй

элементы ИЛИ-НЕ 6 и 7, с первого по четвертый элементы ИЛИ 8-11, элемент И 12, триггер 13, входы 14 первого сомножителя, входы 15 второго сомножителя, вход 16 запуска, первый и второй входы синхронизации 17 и 18, выход 19 признака готовности и выход 20 результата устройства.

Устройство работает следующим образом.

В исходном состоянии триггер 13 обнулен. На информационные входы блоков 1 и 2 и на входы 16-18 устройства поданы нулевые потенциалы. При этом на выходе триггера 13, на втором входе элемента И 12 и, следовательно, на его выходе сформированы нулевые потенциалы. Импульсы с выхода генератора 3 не поступают на входы синхронизации блоков 1 и 2, Этим обеспечивается возможность неодновременного поступления на входы первого и второго сомножителей устройства коэффициентов полиномов-сомножителей по синхроимпульсам, подаваемым на входы 17 и 18 соответственно.

На первом шаге работы устройства на информационные входы блоков 1 и 2 поступают коэффициенты первого и второго полинома-сомножителя по синхроимпульсам, подаваемым на входы 17 и 18, которые через элементы ИЛИ 10 и 11 поступают на входы синхронизации блоков 1 и 2 соответственно. Коэффициенты полиномов-сомножителей при старших степенях фиктивной переменной в полиномах-сомножителях записываются как в блок 1, так и в блок 2. После записи коэффициентов полиномов- сомножителей в блоки 1 и 2 устройство готово к выполнению вычисления результата умножения.

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

В первом случае хотя бы один из полиномов-сомножителей равен нулю. При этом на выходе одного из элементов ИЛИ- НЕ 6 или 7 появится единичный потенциал,

который, поступая на вход элемента ИЛИ 8, устанавливает на его выходе единичный потенциал, Данный потенциал не разрешает установку триггера 13 в 1 и прохождение импульсов от генератора 3 через элемент И

0 12 и элементы ИЛИ 10, 11 на входы синхронизации блоков 1, 2, а также формирует на выходе 19 устройства сигнал готовности результата вычисления. Этот результат равен нулю, если первый или второй полином-со5 множитель равен нулю. В данном случае результат вычисления формируется сразу же при записи в один из блоков 1 или 2 коэффициентов полинома-сомножителя, равного нулю.

0Во втором случае первый полином-сомножитель равен единице, второй полином- сомножитель не равен нулю. При этом на входах дешифратора 4 появляется комбинация сигналов 100...О, а значит, на его вы5 ходе формируется потенциал логической единицы, который, поступая на вход элемента ИЛИ 8, устанавливает на его выходе единичный потенциал. Данный потенциал не разрешает прохождение импульсов от

0 генератора 3 на входы синхронизации блоков 1 и 2, а также формирует на выходе 19 устройства сигнал готовности результата вычисления. Этот результат равен значению второго полинома-сомножителя.

5 В третьем случае первый полином-сомножитель не равен ни нулю, ни единице, второй полином-сомножитель не равен нулю. При этом на всех входах элемента ИЛИ 8 сформированы нулевые потенциалы, а

0 значит, и на его выходе также будет нулевой потенциал. Следовательно, на выходе 19 устройства отсутствует сигнал готовности результата вычисления. Для выполнения вычислений на вход 16 устройства подается

5 импульс, равный логической единице, который, проходя через элемент ИЛИ 9, поступает на информационный вход триггера 13. После этого с поступлением нового импульса от генератора 3 на вход синхронизации

0 триггера 13 последний установится в единицу. Потенциал логической единицы с выхода триггера 13 разрешает прохождение импульсов от генератора 3 через элемент И 12 и через элементы ИЛИ 10, 11 на входы син5 хронизации блоков 1 и 2. Кроме того, этот потенциал через элемент ИЛИ 9 будет поддерживать состояние логической единицы на информационном входе триггера 13, вследствие чего триггер 13 не перейдет в нулевое состояние по следующим импульсам, поступающим на его вход синхронизации. Это обеспечивает точное задание начала функционирования устройства при выполнении каждой операции умножения; а также повышает надежность за счет функционирования синхронизации работы устройства в составе декодирующих устройств. Импульсы на входах синхронизации блоков 1 и 2 выполняют циклические сдвиги влево и вправо, и одновременно в соответствии со связями - суммирование по модулю два содержимых блока 1 деления (сдвиг влево) и блока 2 умножения (сдвиг вправо). Указанные сдвиги и суммирование по модулю два осуществляют одновременное последовательное деление первого полинома-сомножителя и умножение второго полинома-сомножителя на примитивный элемент поля GF(2m). Блоки 1 и 2 настроены на неприводимый многочлен, образующий полеСР(2тХ при этом примитивный элемент поля соответствует комбинации сигналов 0100...0. Деление первого полинома-сомножителя, а значит, и умножение второго полинома-сомножителя на примитивный элемент поля осуществляется до тех пор, пока на выходах блока 1 не сформируется комбинация сигналов, равная 100..О. Потенциал на выходе элемента ИЛИ 8, равный логической единице, определяет окончание функционирования устройства при выполнении операции умножения. Этот потенциал сбросит триггер 13 в нулевое состояние, а также сформирует на выходе 19 устройства сигнал готовности результата вычисления. Потенциал логического нуля на выходе триггера 13 не разрешит прохождение импульсов от генератора 3 на входы синхронизации блоков 1 и 2, а следовательно, содержимое этих блоков дальше изменяться не будет. Этим обеспечивается фиксация результата вычисления и задание окончания функционирования устройства при выполнении операции умножения. Для выполнения следующей операции умножения необходимо установить устройство в исходное состояние и выполнить два описанных шага работы устройства.

Формула изобретения Устройство для умножения полиномов над конечными полями GF(2m), содержащее

блок деления на примитивный элемент по-- ля GF(2m), где m - степень неприводимого многочлена поля, блок умножения на примитивный элемент поля GF(2m), генератор 5 тактовых импульсов, дешифратор и группу из m элементов И, причем информационные входы первого и второго сомножителей устройства подключены соответственно к информационным входам блока деления на

0 примитивный элемент поля GF(2m) и блока умножения на примитивный элемент поля GF(2m), выходы блока деления на примитивный элемент поля GF(2m) подключены к входам дешифратора, выход которого подключен

5 к первым входам элементов И группы, выходы которых подключены соответственно к выходам результата устройства, выходы блока умножения на примитивный элемент поля GF(2m) подключены соответст0 венно к вторым входам элементов И группы, отлича ющееся тем, что, с целью повышения быстродействия, оно содержит первый и второй элементы ИЛИ-НЕ, с первого по четвертый элементы ИЛИ, триггер и

5 элемент И, причем выход дешифратора подключен к первому входу первого элемента ИЛИ, выход которого подключен к выходу признака готовности результата устройства и к входу установки в О триггера, выход

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

0 умножения на примитивный элемент в поле GF(2m), выходы дешифратора подключены к входам первого элемента ИЛИ-НЕ, выходы которого подключен к второму входу первого элемента ИЛИ, выходы блока умножения

5 на примитивный элемент в поле GF(2m) подключены к входам второго элемента ИЛИ- НЕ, выход которого подключен к третьему входу первого элемента ИЛИ, первый вход синхронизации, второй вход синхрониза0 ции и вход запуска устройства подключены соответственно к вторым входам третьего, четвертого и второго элементов ИЛИ.