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

 

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

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

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

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

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

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

ПРИ ГКНТ СССР

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

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4720582/24 (22) 18.08.89 (46) 07.09.91. Бюл. I4 33 (71) Научно-исследовательский институт бытовой радиоэлектронной аппаратуры (72) И.И.Ковалив и 3.Д. Коноплянко (53) 681.325(088.8) (56) Авторское свидетельство СССР

М 997039, кл. G 06 F 15/31, 1982, Авторское свидетельство СССР

М 1061134. кл, G 06 F 7/49, 1982.. Ж 1675901 А1 (54) УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ ПОЛИНОМОВ НАД КОНЕЧНЫМИ ПОЛЯМИ

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

Цель достигается тем, что устройство содер1675901

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

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

На чертеже представлена схема предлагаемого устройс1 ва.

Устройство содержит сдвигающий регистр 1, первую группу из(гг-1) элементов И

2, вторую группу из (rn-1) элементов И 3, третью группу из m элементов И 4, первую группу из (m-1) сумматоров ". по модулю два, вторую группу из m сумматоров б по модулю два, группу элементов ИЛИ 7, первую fрупny триггеров 8, вторую rpynny триггеров 9, блок 10 определения старшего ненулевого разряда, ключи 11, первый 2 и второй 13 элементы ИЛИ-НЕ, входы элемента ИЛИ 14, элемент НЕ 15, элемент И 16, такговый вход

17 устройства, входы 18 коэффициентов множителя устройс. ва, входы 19 неприводимого многочлена устройства, входы 20 коэффициентов множимого устройства, выходы 21 результата устройства и выход 22 признака готовности результата устройства. Сдвигающий регистр 1 содержит триггеры 23 и элементы ИЛИ 24, Устройство работает сгедующим образом.

В исходном состоянии на входы элементов ИЛИ-НЕ 12 и 13 поступ=- ют нулевые сигналы, тогда на aofxopf. элем.nòa ИЛИ 14— логическая единица, а на первый вход элемента И 16 поступает логический нуль, В этом случае непрерывно поступающий синхросигнал с входа 17 не проходит на выход элемента И 16 и на входы синхронизации сдвигающего регистра 1 и триггеров 8 и 9 не поступает. На выходе 22 при этом устанавливается логическая единица, сигнализирующая о готовности устройства к работе или выдаче результата вычисленлй, После того, как в сдвигающий регистр 1 и в триггеры 8 записаны отли гные от нуля значения множимого и мно:кителя, на выходах элементов ИЛИ-НЕ 12 и 13 появляются нулевые сигналы и на первь:й вход элемента тов ИЛИ 7, первую группу триггеров 8, вторую группу триггеров 9, блок 10 определения старшего ненулевого разряда, m ключей

11. первый и второй элементы ИЛИ-НЕ 12 и

13, элемент ИЛИ 14, элемент НЕ 15, элемент

И1б.1 ил, И 16 поступает логическая единица, При этом с входа 17 поступают тактовые сигналы и происходят сдвиги в регистре 1. На m-м шаге сдвига формируется конечный результат вычислений результата, на входы элементов ИЛИ-НЕ 12 и 13 поступают нулевые сигналы, останавливающие поступление синхросигналов, и на выходе 22 формируется сигнал готовности результата вычислений, f3 случае, если один из сомножителей оавен нулю; на первом входе элемента И 16 всегда исходное нулевое состояние, и сигнал с выхода 22 сигнализирует о готовности результата вычислений, обеспечивая тем самым m-кратное повышение быстродействия устройства при выполнении данной операции.

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

Устройство для умножения полиномов над коне:ными полями GF(2"), содержащее сдвигающий регистр, первую и вторую группы из m триггеров, с первого по m-й ключи, / первую и вторую группы из (гп-1) элементов И каждая, третью группу из rn элементов И, первую группу из (rn-1) суммагоров по модулю два, вторую группу из m сумматоров по модулю два, группу из rn элементов ИЛИ и блок определения старшего ненулевого разряда, причем входы с первого по m-й коэффициентов множителя устройства подключены соответствен; о к информационным входам с первого no m-й сдвигающего регистра, входы с первого по (гп-1)-й неприводимого многочлена устройства подключены соответственно к входам с первого по (m-1)-й блока определения старшего ненулевого разряда и соответственно к первым входам элементов И с первого по (m-1)-й первой группы, выходы которых подключены соответственно к первым входам сумматоров по модулю два с первого по (m-1)-й первой группы, fï-й вход неприводимого многочлена устройства подключен к m-му входу блока определения старшего ненулевого разряда, выходы с первого no (m-1)-й блока определения старшего ненулевого разряда подключены состветственно к управляющим входам ключей с первого no (m-1)-й и к пер50 вы . входам элементов И с первого по (m-1)1675901

Составитель В, Смирнов

Техред M.Moðråíòàë Корректор И.Муска

Редактор И. Горная

Заказ 3004 Тираж Подписное

8НИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

113035, Москва, Ж-35, Раушская наб., 4/5

Производственно-издательский комбинат "Патент", г. Ужгород, ул.Гагарина, 101 и второй группы, m-й выход блока определения старшего ненулевого разряда подключен к управляющему входу m-го ключа, первый информационный вход которого подключен к входу нулевого потенциала устройства, выход а-ro ключа (где а = 2, ..., m) подключен к первому информационному входу (а-1)-ro ключа и к второму входу (а-1)го элемента И первой группы, выходы элементов И с первого no (m-1)-й второй группы подключены соответственно к вторым входам сумматоров по модулю два с первого по (m-1)-й первой группы, выход m-го ключа и выходы сумматоров по модулю два с первого по (m-1)-й подключены соответственно к первым входам с первого по m-й элементов ИЛИ группы, выходы которых подключены соответственно к информационным входам триггеров с первого по е-й первой группы, выход Ь-го триггера первой группы (где Ь =

1, ..., m-1) подключен к второму информационному входу b-ro ключа, ко второму входу

Ь-ro элемента И второй группы и к первому входу Ь-ro элемента И третьей группы, выход m-го триггера первой группы подключен к второму информационному входу m-го ключа и первому входу m-ro элемента И третьей группы, входы с первого по m-й множимого устройства подключены соответственно к вторым входам элементов ИЛИ с первого по m-й группы, первый выход сдвигающего регистра подключен к вторым входам всех элементов И третьей группы, выходы которых подключены соответствен5 но к первым входам сумматоров по модулю два второй группы, выходы которых подключены к информационным входам триггеров второй группы, выходы которых подключены соответственно к вторым входам сумма10 торов по модулю два второй группы и соответственно к выходам результата устройства, о т л и ч а ю щ е е с я тем, что, с целью увеличения быстродействия, оно содержит элемент ИЛИ, первый и второй эле15 менты ИЛИ-НЕ, элемент НЕ и элемент И, причем тактовый вход устройства подключен к первому входу элемента И, выход которого подключен к входам синхронизации триггеров первой и второй групп и сдвига20 ющего регистра, выходы с первого по m-й подключены соответственно к входам первого элемента ИЛИ-НЕ, выход которого подключен к первому входу элемента ИЛИ, выход которого подключен к выходу призна25 ка готовности результата устройства и входу элемента НЕ, выход которого подключен к второму входу элемента И, выходы триггеров первой группы подключены к входам второго элемента ИЛИ-НЕ, выход которого

30 подключен к второму входу элемента ИЛИ.