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

 

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

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

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

Данное устройство имеет узкие функциональные возможности.

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

Недостатком данного устройства является его низкое быстродействие.

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

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

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

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

Устройство для формирования элементов мультипликативных групп полей Галуа GF(P) работает следующим образом.

В исходном состоянии регистры 6 и 7 обнулены. В блок 8 памяти предварительно записаны заранее вычисленные остатки от чисел 2ⁱ, i = , где k - максимальная разрядность произведения, по модулям p_j, с которыми предлагается работа устройства. Перед началом работы на вход 15 поступает импульс, который обнуляет регистры множимого и множителя блока 1, на входы 19 подается код модуля, который поступает на информационные входы блока 8 памяти и вторые входы вычитателя 11 и схем 12, 13 сравнения, в регистр множителя блока 1 подается с входа 18 двоичный код числа первообразного элемента Θ_i , в регистр множимого блока 1 по входу 16 записывается "единичный" элемент. При подаче импульса на вход 17 устройство начинает выполнять операцию умножения. Блок 1 умножения умножает единицу на Θ_i и выдает результат умножения на свои выходы, который через третьи входы мультиплексора 2 поступает на информационные входы регистров 6 и 7. Сигнал окончания умножения с выхода блока 1 умножения через первый вход элемента ИЛИ 5 поступает на вход разрешения считывания блока 8 памяти, на вход разрешения записи регистра 6 и на вход элемента 14 задержки. При этом в регистр 6 через мультиплексор 2 происходит запись кода произведения, а на выходах блока 8 памяти появляются остатки от чисел 2ⁱ, i = , по модулю p блок 8 памяти имеет k групп выходов, каждая из которых состоит из l разрядов, необходимых для представления остатков чисел 2ⁱ по модулю p_i.

Блок 9 ключей представляет собой группу k l-входовых ключей. В зависимости от того, на какой из управляющих входов ключей поступает логическая "1", тот из ключей блока 9 оказывается открытым и коммутирует на свои выходы входные сигналы. В результате на соответствующие входы сумматора 10 поступают остатки от чисел 2ⁱ, i = , для тех i, для которых коэффициент a_i = 1 в представлении записанного в регистр 6 кода произведения в позиционной системе счисления. Сумматор 10 осуществляет суммирование чисел, поступающих на его входы, и эта сумма в двоичном параллельном коде оказывается на его выходах. При этом на первые входы схемы 12 сравнения воздействует код модуля pj, а на вторые входы - код вычисленной суммы с выхода сумматора 10. К этому моменту времени на выходе элемента 14 задержки появляется импульс, который, поступая на управляющий вход схемы 12 сравнения, разрешает сравнение кодов чисел, воздействующих на ее входы. Если в результате сравнения оказывается, что код числа, воздействующий на первые входы схемы сравнения, меньше кода модуля, то на выходе "меньше" схемы 12 сравнения появляется импульс, который поступает на первый управляющий вход мультиплексора 2 и через элемент ИЛИ 3 на вход разрешения записи регистра 7. В результате мультиплексор 2 коммутирует на выходы свои первые входы и в регистр 7 при этом записывается с выходов сумматора 10 код остатка, а на выходе 21 разрешения считывания устройства появляется импульс, свидетельствующий о том, что разрешено считывание очередного элемента поля с выходов 20, а также (на чертеже не показано) на вход 17 запуска (после считывания) блока 1 умножения, где по этому импульсу в регистр множимого записывается код числа с выходов регистра 7 и блок 1 начинает умножать первообразный элемент на это число.

Если импульс появляется на выходе "больше" схемы 12 сравнения, то это свидетельствует о том, что формирование остатка не закончено. Импульс с выхода "больше" схемы 12 сравнения поступает на управляющий вход схемы 13 сравнения, разрешая сравнение кодов чисел, воздействующих на ее входы. При этом на ее вторые входы воздействует код модуля p_j, а на первые входы воздействует код числа с выхода вычитателя 11, численно равный разности кода произведения с выхода сумматора 10 и кода модуля. Если в результате работы схемы 13 сравнения импульс появляется на выходе "меньше", то это свидетельствует о том, что формирование остатка закончено. Этот импульс через элемент ИЛИ 4 поступает на второй управляющий вход мультиплексора 2 и через элемент ИЛИ 3 на вход разрешения записи регистра 7. В результате выходы мультиплексора 2 оказываются скоммутированными с его вторыми входами и в регистр 7 записывается код числа с выходов вычитателя 11. При этом на выходе 21 появляется сигнал, свидетельствующий о том, что разрешено считывание очередного элемента поля с выходов 20.

Если импульс появляется на выходе "больше" схемы 13 сравнения, то это свидетельствует о том, что формирование остатка еще не закончено. Этот импульс поступает через элемент ИЛИ 4 на второй управляющий вход мультиплексора 2, коммутируя его выходы с его вторыми входами, а также на второй вход элемента ИЛИ 5. При этом работа устройства повторяется, но в регистр 6 записан код числа с выходов вычитателя 11, воздействующий на информационные входы регистра 6 через мультиплексор 2. Процесс формирования остатка по модулю от числа продолжается до тех пор, пока на выходах сумматора 10 или вычитателя 11 не появится число, меньшее модуля. В этом случае устройство выдает код элемента поля на выходы 20, а на выход 21 импульс разрешения считывания этого элемента. (56) Авторское свидетельство СССР N 1633495, кл. H 03 M 7/18, 1989.

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

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

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

РИСУНКИ

Рисунок 1