Изобретение относится к вычислитель- й технике и может быть.использовано в устройствах для формирования сигнально- кодовых конструкций в конечных полях.
Цель изобретения - повышение быстро- д йствия.
Схема устройства приведена на чертеже. Устройство содержит блок 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 элемента поля, в.ход 28 Конец вычислений, выходы 29 декса. Вход Начало вычислений 24уст- рёйства соединен со входом установки в нулевое состоян счетчика 9, входом записи единичного значения блока умножения 1 через элемент 19 задержки - с первым вводом элемента ИЛИ 11, выход которого соединен со входом разрешения умножения блока 1 умножения, выходы разрядов регистра 5 соединены с соответствующими .информационными входами первой группы блока 2 сравнения и входами соответствующих разрядов множителя блока 1 умножения, входы разрядов множимого которого являются входами 26 записи первообразного элемента поля, входы 27 разрядов элемента поля, входы 27 разрядов элемента поля устройства соединены, с соответствующими информационными входами второй группы блока 2 сравнения, выход Не равно которого соединен со вторым входом элемента ИЛИ 11. выход элемента ИЛИ 12, соединен со входом разрешения сравнения блока 2 сравнения, выход Равно которого является выходом 28 Конец вычислений4 устройства и соединен со входом разрешения выдачи результата счетчика 9 и входом установки в нулевое состояние блока 1 умножения, выход Конец умножения которого соединен с первым входом элемента ИЛИ 13 и со счетным входом счетчика 9, выходы разрядов которого являются выходами 29
00 СА) Ч
$ь
О
индекса устройства, информационные входы первой группы блока 3 сравнения соединены со входами вычитаемого вычитателя 4, а информационные входы второй группы соединены с информационными входами регистра 5, выходы старших и младших разрядов произведения блока 1 умножения соединены соответственно с первыми информационными входами мультиплексора
20и информационными входами регистра 7, а выход Конец умножения соединен со счетным входом счетчика 9, с обнуляющим входом счетчика 10, с первыми входами элементов ИЛИ 14 и 15 и со входами разрешения записи регистров 6 и 7, информационные входы регистра 6 являются входами 25 разрядов модуля устройства, а выходы подключены к информационным входам первой группы блока 3 сравнения и входом вычитаемого вычитателя 4, выходы которого соединены со вторыми информационными входами мультиплексора 20, выходы которого подключены к информационным входам регистра 8, выходы которого соединены с информационными входами регистра 5, входами уменьшаемого вычитателя 4 и информационными входами второй группы блока 3 сравнения, выход Меньше которого подключен к первым входам элементов ИЛИ 15 и 16, выходы которых соединены соответственно с разрешающим входом элемента И
21и первым входом элемента И 22, выход Равно блока 3 сравнения подключен ко входу четвертого регистра 8, второму входу элемента ИЛИ 15 и первому входу элемента И 23, выход окончание работы вычитателя соединен с управляющим входом мультиплексора 20, вторым входом элемента ИЛИ 14 и входом формирователя 17 импульсов, выход которого подключен к третьему входу элемента ИЛИ 15 и второму входу элемента ИЛИ 16, выходы элемента ИЛИ 14 и регистра 7 соединены соответственно со входом разрешения записи и информационным входом регистра 8, выход элемента И 21 подключен ко входам сдвига регистров 7 и 8, входу элемента ИЛИ 13 и счетному входу счетчика 10, выход которого соединен с запрещающим входом элемента И 21 и вторыми входами элементов И 21 и 22, выходы которых подключены соответственно к первому и второму входам элемента ИЛИ 12, а также соответственно ко входу разрешения записи и обнуляющему входу регистра 5, выход элемента ИЛИ 13 соединен со входом формирователя 18 импульсов, выход которого подключен к разрешающему входу блока 3 сравнения, выход Больше которого соединен с разрешающим входом вычитателя 4.
Устройство работает следующим образом.
Если 0 первообразный элемент поля GF(P), то для любого элемента a 6GF(P) cyществует единственное целое число (6 GF(P) такое, что а 0Г, которое и называется индексом элемента а по основанию Э .
Первоначально выбирается первообразный элемент© , по которому предполагается формировать индексы. Затем задается элемент поля а, от которого необходимо сформировать индекс. Элемент умножается на единицу, затем результат произведения умножается на элемент 0 . далее снова результат произведения умножается на 0 и т.д. Каждый раз результат произведения приводится по заданному модулю Р и затем сравнивается с элементом поля а. Одновременно
подсчитывается количество умножений. Как только в результате очередного умножения
окажется, что вышеуказанное произведение, приведенное по модулю Р численно равно значению элемента поля а, то это означает, что количество выполненных умножений численно равно индексу элемента а по основанию 0 в поле GF(P), т.е. индекс элемента а сформирован.
В исходном состоянии все регистры и
счетчики обнулены. Импульс Начало вычислений поступает на вход 24 и обнуляет
счетчик 9 и осуществляет запись единицы в
регистр множимого блока умножения 1.
Модуль, по которому осуществляется
формирование остатков, задается параллельным двоичным кодом, подаваемым на вход 25. Импульс Начало вычислений, пройдя через элемент 19 задержки, через элемент ИЛИ 11 запускает блок умножения.
В регистр множителя блока 1 умножения по входу 26 записывается первообразный элемент поля. После перемножения импульс конца умножения подсчитывается счетчиком 9, записывает в регистр 6 - код модуля,
в регистр 7 - младшие разряды кода числа, а в регистр 8 - старшие разряды кода числа, получаемого в результате работы блока 1 умножения. Причем количество М-старших t разрядов численно равно количеству разрядов, необходимому для представления в параллельном двоичном коде модуля, а количество младших разрядов равно М - N, где М - общее количество разрядов на выходе блока 1 умножения. Так как на управляющий вход мультиплексора 20 воздействует нулевой потенциал, то его выходы, подключенные к информационным входам регистра 8,. скоммутированны с его первыми входами. Этот же импульс Начало
шчислений, проходя через элемент 13 4ЛИ, поступает на вход формирователя 18 шпульсов. По срезу входного импульса (т.е. после того как произведена запись кодов шсел и модуля в регистры 6. 7, 8) формирователь 18 импульсов, сформирует импульс, который разрешит сравнение блоком 3 :равнения старших разрядов кода числа, записанных в регистре 8, и кода модуля, записанного в регистре 6, В результате сравнения могут возникнуть следующие си- уации.
а) Код числа, записанного в регистре 8, скажется меньше кода модуля. В этом слу- iae блок 3 сравнения выдаст на свой выход Меньше импульс, который, проходя эле- иент 15 ИЛИ, поступит на первый входэле- иента И 21, и так на второй (инверсный) вход элемента И 21 воздействует нулевой потен- диал с выхода счетчика 10, этот импульс пройдет через элемент И 21 и поступит на }ходы сдвига регистров 7.и 8. При этом код мела в этих регистрах сдвинется на один эазряд в сторону старших разрядов (ре- истр 8 имеет разрядность N + 1), причем в :амый младший разряд регистра 8 перепи- иется информация с самого старшего раз- зяда регистра 7. Этот же импульс поступит ia счетный вход счетчика 10, который сосчи- -ает его, и на второй вход элемента ИЛИ 13. выхода элемента ИЛИ 13 импульс посту- 1ит на вход формирователя 18 импульсов, соторый по срезу входного импульса сформирует следующий импульс для разреше- 1ия работы блока 3 сравнения. В результате
сравнения могут возникнуть указанные си уации.
б)Код числа, записанного в регистре 8, окажется равен коду модуля. В этом случае
)лок 3 сравнения выдаст на свой выход Равно импульс, который обнуляет регистр $и, проходя через элементы 15 ИЛИ и И 21, перепишет информацию с самого старшего азряда регистра 7 в самый младший раз- яд регистра 8. Этот импульс также сосчи- ается счетчиком 10 и через элемент ИЛИ 13 юступит на вход формирователя 18 импульсов, который сформирует импульс для разрешения работы блока 3 сравнения.
в)Код числа, записанного в регистре 8, Скажется больше кода модуля. В этом случае блок 3 сравнения выдаст на свой выход Больше импульс, который поступит на |1ход Начало вычитания вычитателя 4. При ITOM вычитатель 4 вычитает из кода числа, написанного в регистре 8, код модуля и выдаст на свои информационные выходы код разности. Одновременно на выходе Конец оычитания вычитателя 4 появится импульс, который установит мультиплексор 20 в состояние коммутации его выходов со своими вторыми входами. Этот же импульс воздействует через элемент ИЛи 14 на вход разрешения записи регистра 8. В результате в 5 регистр 8 записывается код разности с выходов вычитателя 4. Импульс Конец вычитания воздействует также на вход формирователя 17 импульсов. По срезу входного импульса (т.е. после того, как про- 10 изойдет запись в регистр 14) формирователь 17 импульсов сформирует импульс, который проходя через элементы ИЛИ 15 и И 21, осуществит сдвиг информации в реги- страх.,7 и 8 в сторону старших разрядов и 15 перепишет информацию с самого старшего разряда регистра 7 в самый младший разряд регистра 8, а также сосчитается счетчиком 10 и поступит через элемент ИЛИ 13 на вход формирователя 18 импульсов. По срезу
0 входного импульса формирователь 18 сформирует импульс, который разрушит работу блока 3 сравнения.
Как только счетчик 10 заполнится (его объем равен М - N), элемент И 21 закроется
5 и импульсы с выхода блока 3 будут поступать по другой цепи. Если при выполнении последней операции сравнения блок 3 выдаст импульс на свой выход Меньше, то этот импульс, проходя через элемент ИЛИ
0 16 и открытый элемент И 22, поступит на вход разрешения записи регистра 5 и на первый вход элемента ИЛИ 12. При этом в регистр 5 запишется остаток от произведения по заданному модулю, полученного на
5 выходах разрядов произведению блока 1 умножения, Если же блок 3 выдаст импульс на свой выход Равно, то этот импульс обнулит регистр 8, через открытый элемент И 23 поступит на второй вход элемента ИЛИ
0 12 и обнулит регистр 5. А если же блок 3 выдаст импульс на свой выход Больше, то этот импульс разрешит вычитание кода модуля из кода числа записанного в регистре 8, разность будет записана в регистр 8, раз5 ность будет записана в регистр 8, и далее под воздействием импульса, сформированного формирователем 17 и, прошедшего че- рез элемент ИЛИ 16 и открытый элемент И 22, эта разность будет записана в регистр 5.
0 Импульсе выхода элемента ИЛИ разрешит сравнение остатка от произведения по модулю, записанного в регистре 5 и элемента поля, подаваемого на входы 27 устройства. Если остаток от произведения не
5 равен элементу поля, то с выхода Не равно блока 2 сравнения импульс поступает на второй вход элемента ИЛИ 11 и с его выхода на вход разрешения умножения блока 1 умножения. Блок 1 умножения осуществляет умножение чисел, записанных в его регистpax множимого и множителя и выдает произведение на свои выходы разрядов произведения. Далее осуществляется приведение произведения по модулюгсрав нение блоком 2 остатка от произведения с элементом поля и в зависимости от результатов сравнения работа устройства повторяется - если остаток не равен элементу поля или, если остаток равен элементу поля, блок 3 выдает импульс на свой выход Равно. Этот импульс обнуляет регистр множимого блока 1 умножения, разрешает выдачу результата счетчиком 9, в котором записано количество умножений, произведенное блоком 1, (т.е. индекс числа а по модулю Р при заданном 0 ), и поступает на выход 28 Конец вычислений устройства, свидетельствуя о том, что работа устройства закончена и на выходах 29 устройства выставлен двоичный код в параллельном виде индекса элемента а.
Задавая следующий элемент поля на входах 27 и, подавая импульс на вход 24, получим индекс этого элемента поля на вы- . ходах 29 устройства и т.д. При этом формирование индексов элементов поля может происходить при выборе различных первообразных элементов, а также в различных полях GF(P).
Технико-экономическая эффективность предлагаемого устройства заключается в повышении быстродействия формирования остатка по произвольному модулю от числа.
Оценим выигрыш в быстродействии, получаемый при использовании предлагаемого устройства. Так, например, при разрядности (в случае двоичного представления параллельным кодом) модуля N, разрядность на выходах блока умножения будет равна 2N, тогда устройство прототип затратит на один цикл вычислений (22N/2N) х Ti + Т2 2N -Ti + Т2 единиц времени, где Ti - сумма времен, необходимых для срабатывания блока 3 сравнения, вычитателя 4 и регистра 5, а Та - сумма времен, необходимых для срабатывания блока 1 умножения и блока 2 сравнения. Предлагаемое же устройство затратит N -Ti + Т2 единиц времени, Считывая Ti и Т2 примерно одинаковыми в обоих случаях выигрыш в быстродействии (за один цикл работы устройства) запишем как:
iN
В
Ti+T2
, раз.
N -Ti +T2 Итак, предлагаемое устройство в K-(2N-Ti + T2)/(N-Ti + Т2) раз быстро сформирует индекс числа от заданного элемента а поля GF(P). где индекс элемента а поля
GF(P) при заданном первообразном элементе Э .
Формула изобретения Устройство для формирования остатка
по произвольному модулю от числа, содержащее блок умножения, первый и второй блоки сравнения, вычитатель. первый и второй регистры, первый счетчик, первый, второй и третий элементы ИЛИ, первый и
0 второй формирователи импульсов и элемент задержки, причем вход начала вычислений устройства соединен с входом установки в нулевое состояние первого счетчика, входом записи единичного значе5 ния блока умножения и через элемент задержки - с первым входом первого элемента ИЛИ, выход которого соединен с входом разрешения умножения блока умножения, разрядные выходы первого регистра
0 соединены соответственно с информационными входами первой группы первого блока сравнения и входами множителя блока умножения, входы множимого которого являются входами записи первоообразного
5 элемента поля устройства, входы разрядов элемента поля устройства соединены соответственно с информационными входами второй группы первого блока сравнения, выход Не равно которого соединен с вто0 рым входом первого элемента ИЛИ, выход второго элемента ИЛИ соединен с входом разрешения сравнения первого блока сравнения, выход Равно которого является выходом окончания вычислений устройства и
5 соединен с входом разрешения выдачи результата первого счетчика и входом установки в нулевое состояние блока умножения, выход Конец умножения которого соединен с первым входом третьего элемента
0 ИЛИ и со счетным входом первого счетчика, разрядные выходы которого являются выходами индекса устройства, информационные входы первой группы второго блока сравнения соединены соответственно с входами
5 вычитаемого вычитателя, а информационные входы второй группы второго блока сравнения соединены соответственно с информационными входами первого регистра, вход разрешения записи и вход обнуления
0 которого соединены соответственно с первым и вторым входами второго элемента ИЛИ, отличающееся тем, что, с целью повышения быстродействия, в устройство введены мультиплексор, второй счетчик,
5 третий и четвертый регистры, первый, второй и третий элементы И и четвертый, пятый и шестой элементы ИЛИ, причем выходы старших разрядов произведения блока умножения соединены соответственно с информационными входами первой группы
Мультиплексора, выходы младших разрядов произведения блока умножения соединены с оответственно с информационными входами третьего регистра, а выход Конец умно- хения блока умножения соединен с входом с бнуления второго счетчика, первым входом veTBeproro элемента ИЛИ и с входами разре- иения записи второго и третьего регистров, v нформационные входы второго регистра яв- л яются входами разрядов модуля устройства, s разрядные выходы второго регистра соеди- нены соответственно с информационными входами первой группы второго блока сравнения и с выходами вычитаемого вычитателя, выходы которого соединены соответственно с информационными входами второй группы г/ультиплексора, выходы которого соединены соответственно с информационными входами четвертого регистра, разрядные выходы которого соединены соответственно с инфор- ь/ационными входами первого регистра, входами уменьшаемого вычитателя и информационными входами второй группы второго блока сравнения, выход Меньше к эторого соединен с первыми входами пя- того и шестого элементов ИЛИ, выходы ко- тэрых соединены соответственно с п эрвыми входами первого и второго элементов И, выход равно второго блока
сравнения соединен с входом обнуления четвертого регистра, вторым входо м пятого элемента ИЛИ и первым входом третьего элемента И, выход окончания работы вычи- тгтеля соединен с управляющим входом мультиплексора, вторым входом четвертого элемента ИЛИ и входом первого формирователя импульсов, выход которого соединен с третьим входом пятого и вторым входом шестого элементов ИЛИ, выход третьего элемента ИЛИ соединен с входом разрешения записи четвертого регистра, информационный вход которого соединен с выходом третьего регистра, выход первого элемента И соединен с входами сдвига третьего и четвертого регистров, вторым входом четвертого элемента ИЛИ и счетным входом второго счетчика, выход которого соединен с вторым (инверсным) входом первого элемента И и вторыми входами второго и третьего элементов И, выходы которых соединены соответственно с первым и вторым входами второго элемента ИЛИ, выход четвертого элемента ИЛИ соединен с входом второго формирователя импульсов, выход которого соединен с входом разрешения второго блока сравнения, выход Больше которого соединен с входом разрешения вычитатеяя.
«
Ј6 1 1 1
Изобретение относится к вычислитель- й технике и может быть использовано в устройствах для формирования сигнально- кодовых конструкций в конечных полях. Цель изобретения - повышение быстродействия устройства. Устройство для формирования остатка по произвольному модулю от числа содержит блок умножения, два блока сравнения, вычитатель, четыре регистра, два счетчика, шесть элементов ИЛИ, два формирователя импульсов, элемент задержки, мультиплексор, три элемента И, вход начала вычислений, вход разрядов модуля, вход записи первообразного элемента поля, вход элемента поля, выход конца вычислений и выход индекса, соединенные между собой функционально. 1 ил.
