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

 

Изобретение относится к вычислительной технике и предназначено для использования в цифровых вычислительных устройствах, а также в устройствах для формирования сигнально-кодовых конструкций в конечных полях. Цель изобретения - повышение быстродействия - достигается введением блока 7 постоянной памяти, блока 8 элементов И, блока 10 сумматоров по произвольному модулю, блока 9 инверторов, второго 11 и третьего 12 элементов задержки. Сущность изобретения заключается в том, что при формировании индексов процедура приведения по заданному модулю реализуется путем параллельного сложения сравнений. 1 ил.

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

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

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

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

Сущность изобретения заключается в том, что первоначально выбирается первообразный элемент Θ , по которому предполагается формировать индексы. Затем задается элемент поля а, от которого необходимо сформировать индекс. Элемент поля Θ умножается на единицу, затем результат умножения - произведение - умножается на элемент Θ , далее результат произведения умножается на Θ и т. д. Каждый результат приводится по заданному модулю Р и затем сравнивается с элементом поля а, а также подсчитывается количество умножений.

Процедура приведения по заданному модулю реализуется за счет возможности почленного складывания сравнений, т. е. так как (a_k2^k + a_k-12^k-1 + . . . + a₁2 + a_o)modP = a_k2^k(modP) + a_k-12^k-1(modP) + . . . + a₁2(modP) + a_o(modP), (1) где k - разрядность полученного произведения, причем для двоичной системы счисления a_i = 0v1, то, суммируя заранее вычисленные остатки по модулю Р от чисел 2_i, i = , для которых коэффициент ai = 1, получают остаток по модулю Р от кода произведения. Для модулей P_j, с которыми предлагается работа устройства, в блоке постоянной памяти запоминаются заранее вычисленные остатки от чисел 2ⁱ, i = , где k - разрядность кодов произведений, от которых необходимо формировать остатки.

Как только приведенный по модулю указанный выше результат умножения станет численно равным значению элементов поля а, то это означает, что количество выполненных умножений численно равно индексу элемента а по основанию Θ в поле GF(P), т. е. индекс элемента а сформирован.

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

Устройство содержит первый элемент 1 задержки, элемент ИЛИ 2, схему 3 сравнения, регистр 4, блок 5 умножения, счетчик 6, блок 7 памяти, блок 8 элементов И, блок элементов 9 НЕ, сумматор 10 по произвольному модулю, второй 11 и третий 12 элементы задержки.

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

В исходном состоянии регистр 4 обнулен. В блок 7 памяти предварительно записаны заранее вычисленные остатки от чисел 2ⁱ, i = где k - максимальная разрядность произведения, по модулям P_j, с которыми предлагается работа устройства. На вход 15 "Начало вычисления" поступает импульс, который обнуляет счетчик 6 и осуществляет запись единицы в регистр множимого блока 5 умножения.

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

Задавая следующий элемент и подавая импульс на вход 15, получают индекс этого элемента поля на выходах счетчика 6 и т. д. При этом формирование индексов элементов поля может происходить при различных первообразных элементах, а также в различных полях GF(P).

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

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

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

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

РИСУНКИ

Рисунок 1