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

 

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

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

Известно устройство для формирования остатка по произвольному модулю от числа [1] .

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

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

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

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

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

Сущность изобретения заключается в том, что предварительно для всех индексов r_i ((i= 0, )) первообразного элемента Θ поля GF(P) находятся элементы a ∈ GF(P), которые определяют адрес блока памяти, в информационные ячейки которого записываются значения r_i. В рабочем режиме элементы a ∈ GF(P) подаются на адресные входы блока памяти, в режиме чтения которого с его информационных выходов снимаются коды индексов r_i.

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

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

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

В исходном состоянии регистр 5 обнулен, в блоке 13 памяти информация отсутствует, на вторые входы сумматора 12 подан код числа "два".

Модуль, по которому определяется порядок поля GF(P), задается параллельным двоичным кодом, подаваемым на вход 18 модуля устройства. Код первообразного элемента Θ, по которому предлагается формировать индексы, подается на вход 19. Импульс начала вычисления поступает на вход 17 "Начало вычислений". Этот импульс обнуляет счетчик 11, через коммутатор 3 поступает на вход вычитателя, через коммутатор 2 поступает на вход схемы 7 сравнения, а, пройдя через третий вход элемента ИЛИ 14, разрешает сравнение кода единицы с кодом модуля. При этом схема 7 сравнения на выход "меньше" выдает импульс, который поступает на вход элемента 16 задержки и на вход записи блока 13 памяти. На адресные входы блока 13 памяти с выходов коммутатора 2 поступает код единицы, а на информационных входах информация отсутствует, так как счетчик 11 обнулен. Поэтому по первому адресу блока 13 памяти записывается код нуля. После записи кода нуля на выходе элемента 16 задержки появляется импульс, который поступает на первый вход элемента И 15, записывает единицу в счетчик 11 и поступает на второй вход элемента ИЛИ 14. На выход элемента И 15 импульс не проходит, так как с выхода схемы 8 сравнения на второй его вход поступает нулевой потенциал.

Так как одновременно с процессом записи информации в блок 13 памяти в блоке 1 умножения происходит перемножение кода первообразного элемента, поступающего на вход 19 устройства, с кодом, поступающим с выходов коммутатора 2, то импульс, поступающий с выхода элемента ИЛИ 14 в схему 7 сравнения, разрешает сравнение кода произведения с кодом модуля.

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

Если произведение по своему значению больше модуля, схема 7 сравнения выдает импульс на выход "больше". Этот импульс поступает на вход формирователя 9 импульсов и на вход разрешения вычитания вычитателя 4. На вход вычитаемого вычитателя 4 поступает значение модуля с входа 18 устройства, а на вход уменьшаемого - значение произведения через коммутатор 3. Значение разности с выхода вычитателя 4 под воздействием импульса, сформированного формирователем 9 импульсов, по фронту входного импульса записывается в регистр 5. По срезу импульса, сформированного формирователем 9, формирователь 10 импульсов выдает сигнал, который открывает блок 6 элементов И, поступает через элемент ИЛИ 14 на вход разрешения схемы 7 сравнения и, воздействуя на управляющие входы коммутаторов 2 и 3, подключает выходы блока 6 элементов И к входам уменьшаемого вычитателя 4 и к входам схемы 7 сравнения. Код разности, записанный в регистр 5, через блок 6 элементов И и коммутатор 2 поступает на входы схемы 7 сравнения, на вторые входы которой поступает с входа 18 код модуля. Под действием импульса с выхода элемента ИЛИ 14 схема 7 сравнения сравнивает коды чисел, поступающих на его входы.

В результате сравнения могут возникнуть две ситуации, при которых схема 7 сравнения выдает импульс в зависимости от результатов сравнения на один из своих двух выходов. Процесс вычисления остатка по модулю от произведения продолжается до тех пор, пока полученное в результате вычитания значение окажется меньше величины модуля. В результате с выхода регистра 5 через блок 6 элементов И и коммутатор 2 код остатка поступает на адресные входы блока 13 памяти, в ячейки памяти которого записывается информация о состоянии счетчика 11.

Работа устройства в таком режиме продолжается до момента поступления на вход счетчика 11 Р - 2 импульсов. Как только счетчик 11 сосчитает Р - 2 импульса, на выходе сумматора 12 появляется код модуля, поэтому на выходе схемы 8 сравнения появляется сигнал, поступающий на второй вход элемента И 15. Поэтому очередной импульс, поступающий с выхода элемента 16 задержки на первый вход элемента И 15, поступает на выход 22 устройства, сигнализируя об окончании процесса записи информации в блок 13 памяти.

В рабочем режиме на вход 20 устройства подаются коды элементов поля, которые определяют адрес памяти блока 13, а на вход 21 подаются импульсы считывания. При этом с выходов 23 устройства снимаются коды индексов элементов мультипликативных групп полей Галуа. Например, для поля GF(P) при Θ = 3 по первому адресу записывается код нуля, по третьему адресу - код единицы, по второму адресу - код двойки, по шестому адресу - код тройки, по четвертому адресу - код четверки и по пятому адресу - код пятерки. Поэтому в процессе формирования индексов на адресные входы блока 13 памяти подаются коды элементов поля, а с выходов в режиме чтения снимаются коды индексов.

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

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

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

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

РИСУНКИ

Рисунок 1, Рисунок 2