Устройство для формирования элементов мультипликативных групп полей галуа gf (p)

 

Изобретение относится к вычислительной технике и может быть использовано в устройствах формирования кодовых рекуррентных последовательностей, построение которых основывается на теории конечных полей. Цель изобретения - повышение быстродействия устройства. Устройство для формирования элементов мультипликативных групп полей Галуа GF (P) содержит два блока 1 и 2 элементов ИЛИ, вычитатель 3, два регистра 4 и 10, два блока 5 - 13 элементов И, схему 6 сравнения, три формирователя 7, 8 и 11 импульсов, элемент ИЛИ 9 и блок 12 умножения, соединенные между собой функционально. 1 ил.

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

Известно устройство для формирования остатка по произвольному модулю от числа, содержащее два регистра, вычитатель, схему сравнения, два блока элементов И, два блока элементов ИЛИ, два формирователя импульсов и два элемента ИЛИ с соответствующими функциональными связями [1] . Однако данное устройство не позволяет формировать элементы мультипликативных групп полей Галуа GF(P).

Наиболее близким по функциональной сущности к изобретению является устройство для формирования элементов мультипликативных групп полей Галуа GF(P), содержащее блок умножения, регистр, блок элементов И, формирователь импульсов, элемент ИЛИ и элемент задержки с соответствующими функциональными связями [2] . Однако данное устройство обладает низким быстродействием формирования элементов мультипликативных групп полей Галуа GF(P).

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

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

Функциональная схема устройства для формирования элементов мультипликативных групп полей Галуа GF(P) представлена на чертеже.

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

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

Перед началом работы на вход 14 поступает импульс, который обнуляет регистры множимого и множителя блока 12, на входы 17 подается код модуля Р, который поступает на вторые входы схемы 6 сравнения и на вторые входы вычитателя 3, в регистр множителя блока 12 подается с входов 16 двоичный код числа первообразного элемента Θ_i, в регистр множимого блока 12 по входу 18 записывается "единичный" элемент. При подаче импульса на вход 15 устройство начинает выполнять операцию умножения. Блок 12 умножения умножает единицу на Θ_i, и выдает результат умножения на свои выходы. По импульсу окончания умножения с блока умножения результат умножения, пройдя через второй блок 13 элементов И, поступает на первые входы первого и второго блоков 1 и 2 элементов ИЛИ и проходит на их выходы. Результат умножения с выходов первого блока 1 элементов ИЛИ поступает на первые входы вычитателя 3, а с выходов второго блока 2 элементов ИЛИ - на входы регистра 10 и на первые входы схемы 6 сравнения.

Импульс окончания умножения с блока 12 умножения также поступает на второй вход элемента ИЛИ 9 и далее через элемент 21 задержки на вход разрешения сравнения схемы 6 сравнения. Время задержки элемента 21 задержки выбирается несколько больше времени распространения сигнала через блок 13 элементов И и блок 2 элементов ИЛИ для исключения ложных срабатываний схемы 6 сравнения. Схема 6 сравнения производит сравнение поступивших на ее вход кодов чисел, а именно результата умножения и кода модуля Р.

Возможны два случая.

В первом случае результат умножения меньше модуля Р, т. е. является элементом поля. В этом случае на выходе "меньше" схемы 6 сравнения образуется импульс, который поступает на вход разрешения записи регистра 10 и дает команду на запись в него результата умножения с выхода блока 2 элементов ИЛИ. Этот импульс также поступает на формирователь 11 импульсов, который формирует импульс по его срезу. Импульс с выхода схемы 6 сравнения поступает на выход 20 разрешения считывания очередного элемента поля, а также на вход 15 запуска блока 12 умножения, где по этому импульсу в регистр множимого записывается код числа с выходов регистра 10 и блок 12 умножения начинает умножать первообразный элемент на это число.

Во втором случае результат умножения больше модуля Р. В результате сравнения по схеме 6 сравнения результата умножения и кода модуля Р появляется импульс на выходе "больше", который поступает на вход разрешения вычитания вычитателя 3 и на вход формирователя 7 импульсов. На первых входах вычитателя 3 оказывается код результатов умножения, а на вторых - код модуля Р. Результат вычитания поступает на выходы вычитателя 3 и по импульсу, сформированному формирователем 7 импульсов, записывается в регистр 4. Этот импульс поступает на вход формирователя 8 импульсов, который по его срезу формирует импульс, поступающий на второй вход блока 5 элементов И и на вход элемента ИЛИ 9. Результат вычитания поступает через блок 5 элементов И на первые входы блоков 1, 2 элементов ИЛИ и далее на их выходы. С выходов блока 1 элементов ИЛИ эти коды поступают на входы вычитателя 3, а с выходов блока 2 элементов ИЛИ - на входы схемы 6 сравнения и на информационные входы регистра 10. Импульс с формирователя 8 импульсов, пройдя через элемент ИЛИ 9 и элемент 21 задержки, поступает на вход разрешения сравнения схемы 6 сравнения. В результате сравнения возможны два варианта, описанные выше.

Работа устройства таким образом происходит до тех пор, пока результат вычитания не станет меньше модуля Р. В этом случае устройство выдает код элемента поля на выходы 19, а на выход 20 импульс разрешения считывания этого элемента. (56) 1. Авторское свидетельство СССР N 1396281, кл. Н 03 М 7/18, 1986.

2. Авторское свидетельство СССР N 1236497, кл. G 06 F 15/20, 1984.

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

УСТРОЙСТВО ДЛЯ ФОРМИРОВАНИЯ ЭЛЕМЕНТОВ МУЛЬТИПЛИКАТИВНЫХ ГРУПП ПОЛЕЙ ГАЛУА GF (P), содержащее блок умножения, первый регистр, элемент ИЛИ, первый блок элементов И, первый формирователь импульсов и элемент задержки, причем входы записи первообразного элемента устройства соединены с входами регистра множителя блока умножения, вход установки в "0" которого соединен с установочным входом устройства, вход записи значения единицы которого соединен с младшим разрядом регистра множимого блока умножения, отличающееся тем, что, с целью повышения быстродействия, в него введены схема сравнения, вычитатель, второй регистр, второй блок элементов И, первый и второй блоки элементов ИЛИ и второй и третий формирователи импульсов, причем входы записи модуля устройства соединены соответственно с входами первой группы схемы сравнения и с входами первой группы вычитателя, входы второй группы которого соединены соответственно с выходами первого блока элементов ИЛИ, входы первой группы которого соединены соответственно с входами первой группы второго блока элементов ИЛИ и с выходами второго блока элементов И, входы первой группы которого соединены с выходами результата блока умножения, выход окончания умножения которого соединен с входами второй группы второго блока элементов И и с первым входом элемента ИЛИ, выход которого соединен с входом элемента задержки, выход которого соединен с управляющим входом схемы сравнения, выход "Меньше" которой соединен с входом разрешения записи второго регистра и входом третьего формирователя импульсов, выход которого соединен с входом запуска устройства, входом разрешения работы блока умножения и является выходом разрешения считывания устройства, выход вычитателя соединен с информационным входом первого регистра, разрядные выходы которого соединены соответственно с входами первой группы первого блока элементов И, выходы которого соединены соответственно с входами второй группы первого блока элементов ИЛИ и входами второй группы второго блока элементов ИЛИ, выходы которого соединены соответственно с входами второй группы схемы сравнения и информационными входами второго регистра, разрядные выходы которого соединены соответственно с входами регистра множимого блока умножения и являются выходами элементов мультипликативных групп устройства, выход "Больше" схемы сравнения соединен с управляющим входом вычитателя и входом второго формирователя импульсов, выход которого соединен с входом разрешения записи первого регистра и с входом третьего формирователя импульсов, выход которого соединен с входами второй группы первого блока элементов И и вторым входом элемента ИЛИ.

РИСУНКИ

Рисунок 1