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

 

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

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

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

Недостатком устройства являются его узкие функциональные возможности.

Наиболее близким к предложенному по технической сущности и достигаемому результату является устройство для формирования остатка по произвольному модулю от числа, содержащее блок умножения, счетчик, элемент задержки, три элемента ИЛИ, вычитатель, две схемы сравнения и два регистра с соответствующими функциональными связями [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.

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

В исходном состоянии все регистры обнулены. В блок 12 памяти предварительно записаны заранее вычисленные остатки от чисел 2ⁱ, где i = ; K - максимальная разрядность произведения по модулям P_j, с которыми предполагается работа устройства. На вход начала вычислений поступает импульс, который обнуляет счетчик 2 и осуществляет запись значения "единицы" в регистр множимого блока 1 умножения.

Модуль, по которому осуществляется формирование остатков, задается параллельным двоичным кодом, подаваемым на вход модуля устройства. Импульс начала вычисления, пройдя через элемент 4 задержки, поступает на второй вход элемента ИЛИ 7 и запускает блок 1 умножения. В регистр множителя блока 1 умножения записывается первообразный элемент Θ . После перемножения импульс конца умножения подсчитывается счетчиком 2 и, пройдя через элемент ИЛИ 8, поступает на вход разрешения считывания блока 12 памяти, на вход разрешения записи регистра 20 и на вход элемента 5 задержки. При этом в регистр 20 через мультиплексор 3 происходит запись кода произведения, поступающего с выхода блока 1 умножения, а на выходах блока 12 памяти появляются остатки от чисел 2ⁱ, i = , по модулю P Блок 12 памяти имеет К групп выходов, каждая из которых состоит из l разрядов, необходимых для представления остатков чисел 2ⁱ по модулю P_j. Блок 13 ключей представляет собой группу K l-входовых ключей. В зависимости от того, на какой из управляющих входов блока ключей поступает логическая "1", тот из ключей блока 13 оказывается открытым и коммутирует на свои выходы входные сигналы. В результате на соответствующие входы сумматора 14 поступают остатки от чисел 2ⁱ, i = , для тех i, для которых коэффициент a _i= 1 в представлении кода произведения, записанного в регистре 20. Сумматор 14 осуществляет суммирование чисел, поступающих на его входы, и эта сумма в двоичном параллельном коде оказывается на его выходах. При этом на первые входы схемы 17 сравнения воздействует код модуля P_j, а на вторые входы - код вычисленной суммы с выходов сумматора 14. К этому моменту времени на выходе элемента 5 задержки появляется импульс, который, поступая на управляющий вход схемы 17 сравнения, разрешает сравнение кодов чисел, воздействующих на ее входы. Если в результате сравнения оказывается, что код числа, воздействующий на второй вход схемы 17 сравнения, меньше кода модуля, то на выходе "меньше" схемы 17 сравнения появляется импульс, который поступает на второй управляющий вход мультиплексора 3 и через элемент ИЛИ 11 на вход разрешения записи регистра 19. В результате мультиплексор 3 коммутирует на выходы свои третьим входы и в регистр 19 при этом записывается с выходов сумматора 14 код остатка. В результате с выхода регистра 19 остаток от произведения по модулю поступает на первый вход схемы 16 сравнения, а импульс конца формирования остатка с выхода элемента ИЛИ 6 поступает на управляющий вход схемы 16 сравнения, разрешая сравнение остатка от произведения по модулю и элемента поля, подаваемого на вход устройства. Если остаток от произведения не равен элементу поля, то с выхода "не равно" схемы 16 сравнения импульс поступает на первый вход элемента ИЛИ 7 и с его выхода на запускающий вход блока умножения. Процесс формирования повторяется сначала, а количество перемножения подсчитывается счетчиком 2. С выхода счетчика 2, являющегося выходом устройства, в параллельном двоичном коде снимается индекс элементов мультипликативных групп. Если остаток от произведения по модулю численно равен элементу поля, то с выхода "равно" схемы 16 сравнения поступает импульс, который обнуляет регистр множимого блока 1 умножения, останавливает работу счетчика 2 и поступает на выход конца вычисления, свидетельствуя о том, что вычисление закончено, а на выходах счетчика 2 формируется индекс от заданного элемента поля по первообразному элементу.

Если в процессе сравнения кода произведения и кода модуля импульс появляется на выходе "равно" схемы 17 сравнения, то это свидетельствует о том, что остаток кода произведения равен модулю P_j, что означает тождественное равенство нулю кода произведения. При этом импульс с выхода "равно" схемы 17 сравнения, пройдя через элемент ИЛИ 10, обнуляет регистр 19 и через элемент ИЛИ 6 поступает на управляющий вход схемы 16 сравнения.

Появление импульса на выходе "больше" схемы 17 сравнения свидетельствует о том, что формирование остатка не закончено. Импульс с выхода "больше" схемы 17 сравнения поступает на управляющий вход схемы 18 сравнения, разрешая сравнение кодов чисел, воздействующих на его входы. При этом на его первые входы воздействует код модуля P_j, а на вторые входы воздействует код числа с выхода вычитателя 15, численно равного разности кода числа с выхода сумматора 14 и кода модуля. Если в результате работы схемы 18 сравнения импульс появляется на его выходе "равно", то это свидетельствует о том, что код произведения тождественно равен нулю по модулю P_j. Этот импульс, пройдя через элемент ИЛИ 10, поступает на обнуляющий вход регистра 19 и на второй вход элемента ИЛИ 6.

Если импульс появляется на выходе "меньше" схемы 18 сравнения, то это также свидетельствует о том, что формирование остатка закончено. Этот импульс через элемент ИЛИ 9 поступает на первый управляющий вход мультиплексора 3 и через элемент ИЛИ 11 на вход разрешения записи регистра 19. В результате выходы мультиплексора 3 оказываются скоммутированными с его вторыми входами и в регистр 19 записывается код числа с выходов вычитателя 15. При этом на управляющем входе схемы 16 сравнения появляется импульс конца формирования остатка.

Если импульс появляется на выходе "больше" схемы 18 сравнения, то это свидетельствует о том, что формирование остатка еще не закончено. Этот импульс поступает через элемент ИЛИ 9 на первый управляющий вход мультиплексора 3, коммутируя его выходы с его вторыми входами, а также на второй вход элемента ИЛИ 8. При этом в регистре 20 записан код числа с выходов вычитателя 13, воздействующий на информационные входы регистра 20 через мультиплексор 3. Процесс формирования остатка продолжается до тех пор, пока на выходах сумматора 14 или вычитателя 15 не появится число, меньшее или равное модулю.

Задавая следующий элемент и подавая импульс на вход начала вычисления, получают индекс этого элемента поля на выходах счетчика 2 устройства и т. д. При том формирование индексов поля может происходить при различных первообразных элементах, а также в различных полях GF(P). (56) Авторское свидетельство СССР N 1633495, кл. H 03 M 7/18, 1989.

Авторское свидетельство СССР N 1686702, кл. H 03 M 7/18, 1989.

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

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

РИСУНКИ

Рисунок 1