Устройство для формирования первообразных элементов конечных полей

 

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

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

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

Недостаток устройства - низкое быстродействие.

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

Сущность изобретения состоит в реализации следующей идеи формирования первообразных элементов конечных полей. Пусть элемент а ∈GF(P). Тогда элемент а является примитивным, если он удовлетворяет условиям: aⁱ ≠ 1(modP), i = , (1) a^Р-1 = 1(modP). (2) Устройство для формирования первообразных элементов конечных полей на основе заданного модуля Р формирует первообразные элементы следующим образом. Перебирая в лексико-графическом порядке все элементы мультипликативных групп, устройство возводит каждый из них в степени 2,3...Р-1, приводя результат вычислений каждый раз по модулю Р. При этом каждое значение aⁱ, i = , проверяется на равенство единице. Если i ≠ P-1, а аⁱ = 1(modP), то элемент а не является первообразным и осуществляется переход к следующему элементу поля. Если проверяемый элемент окажется первообразным (т.е. удовлетворяет условиям (1) и (2), то этот элемент записывается в блок памяти и осуществляется переход к проверке следующего элемента. По окончании проверки всех элементов устройство прекращает работу (единица и Р-1 не проверяются, так как они заведомо не являются первообразными элементами для любых GF(P)), а в блоке памяти окажутся записанными все первообразные элементы заданного поля GF(P). Из соображений упрощения поиска первообразных элементов их перебор начинается с элемента Р-2.

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

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

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

Порядок поля Р, для которого необходимо сформировать первообразные элементы, задается параллельным двоичным кодом, подаваемым на первые входы вычитателя 1, схемы 2 сравнения и сумматора 9. Так как на вторых входах сумматора 9 зашит инверсный код двойки, то на его выходах появится код Р-2, который поступает на информационные входы счетчиков 10 и 11. Сигнал начала вычисления обнуляет формирователь 13 адреса, разрешает запись кода Р-2 во второй счетчик 11 и через первый вход элемента ИЛИ 7 поступает на его выход. Сигнал с выхода элемента ИЛИ 7 разрешает запись кода Р-2 в первый счетчик 10, через элемент 16 запрета поступает на первый управляющий вход второго мультиплексора 15, коммутируя его первые информационные входы на выходы, а через третий элемент ИЛИ 24 поступает на вход записи второго регистра 4, на информационные входы которого с выхода второго счетчика 11 через второй мультиплексор 15 поступает код Р-2. Одновременно сигнал с выхода элемента ИЛИ 24 поступает на вход элемента 22 задержки, время задержки которого равно времени работы умножителя 12, на первые входы которого поступает код Р-2 с выхода второго счетчика 11, а на вторые входы поступает также код Р-2 с выхода второго регистра 4. Умножитель 12 осуществляет умножение чисел, двоичные коды которых поступают на его входы.

Как только в умножителя 12 будет сформирован результат, на выходе элемента 22 задержки появится сигнал, который поступит на первый управляющий вход первого мультиплексора 14, коммутируя с выходами его первые информационные входы, вычтет из содержимого первого счетчика 10 единицу, а также через второй вход второго элемента ИЛИ 8 поступит на управляющий вход схемы 2 сравнения, разрешая сравнение кодов, поступающих на ее информационные входы. На первые входы схемы 2 поступает код модуля Р, а на вторые - код произведения с выхода мультиплексора 14. Если код произведения больше кода модуля, то сигнал появится на выходе "Больше" схемы 2 сравнения, поступая далее на управляющий вход вычитателя 1 и на вход первого формирователя 5 импульсов. Вычитатель формирует разность кода произведения (уменьшаемое), подаваемого на его вторые входы с выходов мультиплексора 14, и кода модуля (вычитаемое). По окончании пpоцесса вычитания фоpмирователь 5 выдаст импульс, который запишет результат вычитания в регистр 3 и поступит на вход формирователя 6 импульсов.

Формирователь 6 импульсов выдаст по окончании записи в регистр 3 сигнал, который, поступая на второй управляющий вход мультиплексора 14, обеспечит коммутацию его вторых информационных входов на выходы, а поступая через второй элемент ИЛИ 8 на управляющий вход схемы 2 сравнения, обеспечит сравнение кода, поступающего с второго выхода мультиплексора 14, с кодом модуля. Если первый больше кода модуля, то сигнал появится на выходе "Больше" схемы 2 сравнения, поступая далее на управляющий вход вычитателя 1 и обеспечивая вычитание кода модуля и т.д. до тех пор, пока код разности не станет меньше кода модуля. В этом случае сигнал появится на выходе "Меньше" схемы 2 сравнения. При этом возможны два варианта: остаток равен, либо не равен единице. Если остаток не равен единице, то на выходе второго дешифратора 21 единицы сигнал будет отсутствовать, поэтому с выхода элемента 17 запрета сигнал поступит на второй вход мультиплексора 15, чем обеспечит подключение вторых информационных входов мультиплексора 15 к его выходам, а через элемент ИЛИ 24 - на вход записи регистра 4, обеспечивая запись в него кода остатка, поступающего на его информационные входы с регистра 3 через мультиплексоры 14 и 15. После перемножения умножителем 12 кода остатка, записанного во втором регистре 4, на код, записанный в счетчике 11, на входе первого элемента 22 задержки появится сигнал, обеспечивающий вычитание следующей единицы из содержимого счетчика 10 и повторение цикла формирования остатка от полученного значения произведения.

Если же значение остатка равно единице, то на выходе дешифратора 21 единицы появится сигнал, который, поступая на второй вход элемента 17 запрета, исключит прохождение сигнала с выхода "Меньше" схемы 2 сравнения на выход элемента 17 запрета и, проходя через элемент запрета 18 и элемент ИЛИ 25 на вычитающий вход счетчика 11, обеспечит вычитание из его содержимого единицы, тем самым подготавливая к проверке следующий элемент поля, т. е. Р-3. Кроме того, этот же сигнал начнет действовать аналогично сигналу начала вычисления, т.е., проходя через элемент ИЛИ 7 на вход записи первого счетчика 10, обеспечит восстановление кода Р-2, поступающего на его информационные входы с выхода сумматора 9, а также, поступая через элемент 16 запрета на первый вход мультиплексора 15 и вход третьего элемента ИЛИ 24, обеспечит дальнейший поиск первообразного элемента поля GF(P), причем теперь в счетчике 11 будет записан код Р-3, а содержимое счетчика 10 будет изменяться от Р-2 до нуля. Работа всех элементов и узлов устройства будет проходить так, как описано выше.

Если проверяемый элемент окажется первообразным, то сигнал на выходе дешифратора 21 единицы появится только при обнулении счетчика 10 (и не раньше), т. е. после выполнения Р-2 циклов умножения проверяемого элемента - при первом умножении на самого себя, а при последующих умножениях - на результат предыдущего умножения.

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

Как только счетчик 10 будет обнулен, на выходе дешифратора 19 нуля появится сигнал, который, поступая на второй вход элемента 18 запрета, исключит прохождение сигнала с его первого входа на выход, а также поступит на первый вход элемента И 26. При этом сигнал с выхода дешифратора 21 единицы через элемент И 26 поступит на упpавляющий вход формирователя 13 адреса и на вход второго элемента 23 задержки.

Формирователь 13 адреса в простейшем виде может быть выполнен в виде обычного счетчика. При этом он подсчитывает импульсы, поступающие на его управляющий вход. После подсчета импульса (формирования адреса, равного в данном случае по своему абсолютному значению единице) элемент 23 задержки выдаст импульс, который запишет в блок 27 памяти по первому адресу значение первого сформированного первообразного элемента, двоичный код которого воздействует на его информационные входы с выходов счетчика 11.

Кроме того, сигнал с выхода элемента 23 задержки поступит через элемент ИЛИ 25 на вычитающий вход счетчика 11 и на второй вход элемента ИЛИ 7, обеспечивая новый цикл поиска следующего первообразного элемента поля. Работа всех элементов и узлов устройства осуществляется аналогично описанному выше.

Как только во второй счетчик 11 будет записана единица, поиск первообразных элементов поля GF(P) будет прекращен, а на выходе дешифратора 20 единицы появится сигнал, который, поступая на второй вход элемента 16 запрета, запретит прохождение сигналов с первого его входа на выход, тем самым останавливая работу устройства, а также будет являться сигналом окончания работы устройства.

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

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

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

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

РИСУНКИ

Рисунок 1