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

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

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

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

Устройство содержит сдвигающий регистр 1, первую группу из (т-1) элементов И 2, вторую группу из (т-1) элементов И 3, третью группу из m элементов И 4, первую группу из (т-1) сумматоров 5 по модулю два, вторую группу из m сумматоров 6 по модулю два, группу элементов ИЛИ 7, первую группу триггеров 8, вторую группу триггеров 9, блок 10 определения старшего ненулевого разряда, ключи 11, первый 12 и второй 13 элементы ИЛИ-НЕ, входы элемента ИЛИ 14, элемент НЕ 15, элемент И 16, такговый вход 17 устройства, входы 18 коэффициентов множителя устройства, входы 19 неприводимого многочлена устройства, входы 20 ко- эффициентов множимого устройства, выходы 21 результата устройства и выход 22 признака готовности результата устройства. Сдвигающий регистр 1 содержит триггеры 23 и элементы ИЛИ 24,

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

В исходном состоянии на входы элементов ИЛИ-НЕ 12 и 13 поступают нулевые сигналы, тогда на выходе элемента ИЛИ 14 - логическая единица, а на первый вход элемента И 16 поступает логический нуль. В этом случае непрерывно поступающий синхросигнал с входа 17 не проходит на выход элемента И 16 и на входы синхронизации сдвигающего регистра 1 и триггеров 8 и 9 не поступает. На выходе 22 при этом устанавливается логическая единица, сигнализирующая о готовности устройства к работе или выдаче результата вычислений.

После того, как в сдвигающий регистр 1 и в триггеры 8 записаны отличные от нуля зн.ачения множимого и множителя, на выходах элементов ИЛИ-НЕ 12 и 13 появляются нулевые сигналы и на первый вход элемента

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

В случае, если один из сомножителей равен нулю, на первом входе элемента И 16 всегда исходное нулевое состояние, и сигнал с выхода 22 сигнализирует о готовности

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

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

Устройство для умножения полиномов над конечными полями GF(2m), содержащее сдвигающий регистр, первую и вторую группы из m триггеров, с первого по m-й ключи, / первую и вторую группы из (т-1) элементов И

каждая, третью группу из m элементов И, первую группу из (т-1) сумматоров по модулю два, сторую группу из m сумматоров по модулю два, группу из m элементов ИЛ И и блок определения старшего ненулевого разряда,

причем входы с первого по m-й коэффициентов множителя устройства подключены соответственно к информационным входам с первого по m-й сдвигающего регистра, входы с первого по (т-1)-й неприводимого

многочлена устройства подключены соответственно к входам с первого по (т-1)-й блока определения старшего ненулевого разряда и соответственно к первым входам элементов И с первого по (гл-1)-й первой

группы, выходы которых подключены соответственно к первым входам сумматоров по модулю два с первого по (т-1)-й первой группы, m-й вход неприводимого многочлена устройства подключен к m-му входу блока

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

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

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