Устройство для умножения полиномов над конечными полями gf(2 @ )

Устройство для умножения полиномов над конечными полями gf(2 @ )

Иллюстрации

Показать все

Реферат

 

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (я)5 G 06 F 15/31

ГОСУДАРСТВЕННЫЙ КОМИТЕТ

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

16 17 (21) 4712289/24 (22) 29.06.89 (46) 15.06.91. Бюл. М 22 (71) Научно-исследовательский институт бытовой радиоэлектронной аппаратуры (72) И,И.Кавалив и З.Д.Коноплянко (53) 681.325(088.8) (56) Авторское свидетельство СССР

М 989559, кл, G 06 F 15/31, 1980.

Авторское свидетельство СССР

hh 997039, кл. G 06 F 15/31, 1983, (54) УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ, ПОЛИНОМОВ НАД КОНЕЧНЫМИ ПОЛЯМИ GF(2 )

14.

„, Я ÄÄ 1656550 А1 (57) Изобретение относится к.специализи.рованным цифровым вычислительным устройствам и может использоваться в декодирующих устройствах двоичных кодов, проверочные матрицы которых содержат элементы конечных полей GE(2 ). Цель изобретения — повышение быстродействия устройства. Устройство содержит блок 1 деления на примитивный элемент поля GE(2 ), где m — степень неприводимого полинома поля, блок 2 умножения на примитивный элемент поля GF(2 ), генератор 3 тактовых импульсов, дешифратор 4, группу элементов И 5, элементы ИЛИ вЂ” НЕ 6 и 7, элементы

ИЛИ 8 — 11, элемент И 12 и триггер 13. 1 ил, 1656550

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

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

Устройство для умножения полиномов над конечными полями GF(2m) содержит блок 1 деления на примитивный элемент поля GF(2 ), блок 2 умножения на примитивный элемент поля GF(2 ), генератор 3 тактовых импульсов, дешифратор 4, группу элементов И 51, 52, 5з,...,5m первый и второй элементы ИЛИ-НЕ 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 устройство готово к выполнению вычисления результата умножения.

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

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

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

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

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

8 сформированы нулевые потенциалы, а значит, и на его выходе также будет нулевой потенциал. Следовательно, на выходе 19 устройства отсутствует сигнал готовности результата вычисления. Для выполнения вычислений на вход 16 устройства подается импульс, равный логической единице, который, проходя через элемент ИЛИ 9, поступает на информационный вход триггера 13.

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

10

20

30

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

Импульсы на входах синхронизации блоков

1 и 2 выполняют циклические сдвиги влево и вправо, и одновременно в соответствии со связями — суммирование по модулю два содержимых блока 1 деления (сдвиг влево) и блока 2 умножения (сдвиг вправо). Указанные сдвиги и суммирование по модулю два осуществляют одновременное последовательное деление первого полинома-сомножителя и умножение второго полинома-сомножителя на примитивный элемент поля GF(2 ). Блоки 1 и 2 настроены на неприводимый многочлен, образующий поле GF(2 1, при этом примитивный элемент поля соответствует комбинации сигналов

0100...0. Деление первого полинома-сомножителя, а значит, и умножение второго полинома-сомножителя на примитивный элемент поля осуществляется до тех пор, пока на выходах блока 1 не сформируется комбинация сигналов, равная "100..0". Потенциал на выходе элемента ИЛИ 8, равный логической единице, определяет окончание функционирования устройства при выполнении операции умножения. Этот потенциал сбросит триггер 13 в нулевое состояние, а также сформирует на выходе 19 устройства сигнал готовности результата вычисления. Потенциал логического нуля на выходе триггера 13 не разрешит прохождение импульсов от генератора 3 на входы синхронизации блоков 1 и 2, а следовательно, содержимое этих блоков дальше изменяться не будет. Этим обеспечивается фиксация результата вычисления и задание окончания функционирования устройства при выполнении операции умножения. Для выполнения следующей операции умножения необходимо установить устройство в исходное состояние и выполнить два описанных шага работы устройства.

Формула изобретения

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

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

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

GF(2 ), выходы дешифратора подключены к входам первого элемента ИЛИ вЂ” HE, выходы которого подключен к второму входу первого элемента ИЛИ, выходы блока умножения на примитивный элемент в поле GF(2 ) подключены к входам второго элемента ИЛИНЕ, выход которого подключен к третьему входу первого элемента ИЛИ, первый вход синхронизации, второй вход синхронизации и вход запуска устройства подключены соответственно к вторым входам третьего, четвертого и второго элементов ИЛИ.