Устройство для формирования остатка по произвольному модулю от числа

 

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

н у к д

1 м в

P н в и р н с и с

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

Цель изобретения — повышение быстройствия, Схема устройства приведена на чертеже.

Устройство содержит блок 1 умножея, блоки 2, 3 сравнения, вычитатель 4, гистры 5, 6, 7, 8, счетчики 9; 10, элементы

И 11, 12, 13, 14, 15, 16; формирователи, 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 сравнения, выход "He равно" которого соединен со вторым входом элемента ИЛИ 11 ° выход элемента ИЛИ 12, соединен со входом разрешения сравнения блока 2 сравнения, выход "Равно" которого является выходом 28 "Конец вычислений" устройства и соединен со входом разрешения выдачи результата счетчика 9 и входом установки в нулевое состояние блока 1 умножения, выход "Конец умножения" котороroсоединен с первым входом элемента ИЛИ

13 и со счетным входом счетчика 9, выходы разрядов которого являются выходами 29

1837401 индекса устройства, информационные входы первой группы блока 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.

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

Если О первообразный элемент поля

GF(P), то для любого элемента а BGF(P) существует единственное целое число r 6 GF(P) такое, что а = О", которое и называется индексом элемента а по основанию О .

Первоначально выбирается первообразный элемент9, по которому предполага"0 ется формировать индексы. Затем задается элемент поля .а, от которого необходимо сформировать индекс. Элемент умножается на единицу, затем результат произведения умножается на элемент О, далее снова ре"5 зультат произведения умножается на О и т..д.

Каждый раз результат произведения приводится по заданному модулю P и затем сравнивается с элементом поля а. Одновременно подсчитывается количество умножений, Как

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

В исходном состоянии все регистры и счетчики обнулены. Импульс "Начало вы30 числений" поступает на вход 24 и обнуляет счетчик 9 и осуществляет запись единицы в регистр множимого блока умножения 1.

Модуль, по которому осуществляется

35 формирование остатков, задается параллельным двоичным кодом, подаваемым на вход 25. Импульс "Начало вычислений", пройдя через элемент 19 задержки, через элемент ИЛИ 11 запускает блок умножения, В регистр множителя блока 1 умножения по входу 26 записывается первообразный элемент. поля. После перемножения импульс конца умножения подсчитывается счетчиком 9, записывает в регистр 6 — код модуля, в регистр 7 — младшие разряды кода числа, а в регистр 8 — старшие разряды кода числа, получаемого в результате работы блока 1 умножения. Причем количество N-старших разрядов численно равно количеству разря5О дов, необходимому для представления в параллельном двоичном коде модуля, а количество младших разрядов равно М вЂ” N, где М вЂ” общее количество разрядов на выходе блока 1 умножения. Так как на управ55 ляющий вход мультиплексора 20 воздействует нулевой потенциал, то его выходы, подключенные к информационным входам регистра 8,. скоммутированны с его первыми входами. Этот же импульс "Начало

1837401

25

40

55

ычислений", проходя через элемент 13

ЛИ, поступает на вход формирователя 18 мпульсов. По срезу входного импульса (т.е. осле того как произведена запись кодов исел и модуля в регистры 6, 7, 8) формироатель 18 импульсов, сформирует импульс, оторый разрешит сравнение блоком 3 равнения старших разрядов кода числа, вписанных в регистре 8, и кода модуля, аписанного в регистре 6, В результате равнения могут возникнуть следующие сиуации. а) Код числа, записанного в регистре 8, кажется меньше кода модуля. В этом слуае блок 3 сравнения выдаст на свой выход

Меньше" импульс, который, проходя элеент 15 ИЛИ, поступит на первый вход элеента И 21, и тэк на второй (инверсный) вход лемента И 21 воздействует нулевой потениал с выхода счетчика 10, этот импульс ройдет через элемент И 21 и поступит нэ ходы сдвига регистров 7.и 0. При этом код исла в этих регистрах сдвинется на один азряд в сторону старших разрядов (реистр 8 имеет разрядность N + 1), причем в амый младший разряд регистра 8 перепиется информация с самого старшего разяда регистра 7, Этот же импульс поступит а счетный вход счетчика 10, который сосчиает его, и на второй вход элемента ИЛИ 13. выхода элемента ИЛИ 13 импульс постуит на вход формирователя 18 импульсов, оторый по срезу входного импульса сфорирует следующий импульс для разрешеия работы блока 3 сравнения. В результате равнения могут возникнуть указанные сиуации. б) Код числа. записанного в регистре 8, кажется равен коду модуля. В этом случае лок 3 сравнения выдаст на свой выход

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

1 в) Код числа, записанного в регистре 8, кажется больше кода модуля. 8 этом случае блок 3 сравнения выдаст на свой выход

Больше" импульс. который поступит на ход "Начало вычитания" вычитателя 4. При том вычитатель 4 вычитает из кода числа, вписанного в регистре 8, код модуля и выаст на свои информационные выходы код азности. Одновременно на выходе "Конец

ычитания" вычитателя 4 появится импульс, который установит мультиплексор 20 в состояние коммутации его выходов со своими вторыми входами. Этот же импульс воздействует через элемент ИЛи 14 на вход разрешения записи регистра 8. В результате в регистр 8 записывается код разности с выходов вычитателя 4. Импульс "Конец вычитания" воздействует также на вход формирователя 17 импульсов. Ilo срезу входного импульса (т.е. после того, кэк про10 изойдет запись в регистр 14) формирователь 17 импульсов сформирует импульс, который проходя через элементы ИЛИ 15 и

И 21, осуществит.сдвиг информации в регистрах.,7 и 8 в сторону старших разрядов и

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

Как только счетчик 10 заполнится (его обьем равен М вЂ” N). элемент И 21 закроется и импульсы с выхода блока 3 будут поступать по другой цепи. Если при выполнении последней операции сравнения блок 3 выдаст импульс на свой выход "Меньше", то этот импульс, проходя через элемент ИЛИ

16 и открытый элемент И 22, поступит на вход разрешения записи регистра 5 и на первый вход элемента ИЛИ 12. При этом в регистр 5 запишется остаток от произведения по заданному модулю, полученного на выходах разрядов, произведению блока 1 умножения, Если же блок 3 выдаст импульС на свой выход "Равно", то этот импульс обнулит регистр 8, через открытый элемент И

23 поступит на второй вход элемента ИЛИ

12 и обнулит регистр 5, А если же блок 3 выдаст импульс на свой выход "Больше", то этот импульс разрешит вычитание кода модуля из кода числа записанного в регистре

8, разность будет записана в регистр 8, разность будет записана в регистр 8, и далее под воздействием импульса, сформированного формирователем 17 и, прошедшего через элемент ИЛИ 16 и открытый элемент И

22, эта разность будет записана в регистр 5.

Импульс с выхода элемента ИЛИ 12 разрешит сравнение остатка о1 произведения, Ilo модулю, записанного в регистре 5 и элемента поля, подаваемого на входы 27 устройства. Если остаток от произведения не равен элементу поля, то с выхода "Не равно" блока 2 сравнения импульс поступает на второй вход элемента ИЛИ 11 и с его выхода на вход разрешения умножения блока 1 умножения. Блок 1 умножения осуществляет умножение чисел. записанных в его регист1837401.

15

25

35

55 мирует индекс числа от заданного элемента са но а лоля GF(P), где индекс элемента а лола фо рах множимого и множителя и выдает произведение на свои выходы разрядов произведения. Далее осуществляется приведение произведения по модулю,сравнение блоком 2 остатка от произведения с элементом поля и в зависимости от результатов сравнения работа устройства повторяется — если остаток не равен элементу ноля или, если остаток равен элементу поля, блок 3 выдает импульс на свой выход иРавно". Этот импульс обнуляет регистр мнажимого блока 1 умножения, разрешает выдачу результата счетчиком 9, в котором записано количество умножений, произведенное блоком 1, (т.е. индекс числа à по модулю Р при заданном О ), и поступает на выход 28 "Конец вычислений" устройства, свидетельствуя о том, что работа устройства закончена и на выходах 29 устройства выставлен двоичный код в параллельном виде индекса элемента а.

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

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

Оценим выигрыш в быстродействии, получаемый при использовании предлагаемого устройства. Так, например; при разрядности (в случае двоичного представления параллельным кодом) модуля N, разрядность на выходах блока умножения будет равна 2N, тогда устройство прототип затратит на один цикл вычисленйй (22 /2 ) х Т1+ Тг = 2 Т1+ Тг единиц времени, где Т1 — сумма времен, необходимых для срабатывания блока 3 сравнения, вычитателя 4 и регистра 5, à T2 — сумма времен, необходимых для срабатывания блока 1. умножения и блока 2 сравнения.

Предлагаемое же устройство затратит N T>

+ Тг единиц времени, Считывая Т1 и Т2 примерно одинаковыми в обоих случаях выигрыш в быстродействии (зэ один цикл работы устройства) запишем как:

2 Ti+Т

8-, раэ.

Й Т1+Т2

Итак, предлагаемое устройство в

К (2 . T> + Тг)/(й T> + Тг) раз быстро сфорGF(P) при заданном первообразном элементе О.

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

Устройство для формирования остатка по произвольному модулю от числа, содержащее блок умножения, первый и второй блоки сравнения, вычитатель, первый и второй регистры, первый счетчик, первый, второй и третий элементы ИЛИ, первый и второй формирователи импульсов и элемент задержки, причем вход начала вычислений устройства соединен с входом установки в нулевое состояние первого счетчика, входом записи единичного значения блока умножения и через элемент задержки — с первым входом первого элемента ИЛИ, выход которого соединен с входом разрешения умножения блока умножения, разрядные выходы первого регистра соединены соответственно с информационными входами первой группы первого блока сравнения и входами множителя блока умножения, входы множимого которого являются входами записи первоообразного элемента поля устройства, входы разрядов элемента поля устройства соединены соответственно с информационными входами второй группы первого блока сравнения, выход лНе равно" которого соединен с вторым входом первого элемента ИЛИ, выход второго элемента ИЛИ соединен с входом разрешения сравнения первого блока сравнения, выход "Равно" которого является выходом окончания вычислений устройства и соединен с входом разрешения выдачи результата первого счетчика и входом установки в нулевое состояние блока умножения, выход "Конец умножения" которого соединен с первым входом третьего элемента

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

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

1837401

10 ультиплексора, выходы младших разрядов роизведения блока умножения соединены оответственно с информационными входаи третьего регистра, а выход "Конец умноения" блока умножения соединен с входом бнуления второго счетчика, первым входом етвертого элемента ИЛИ и с входами разреения записи второго и третьего регистров, нформационные входы второго регистра явяются входами разрядов модуля устройства, . разрядные выходы второго регистра соедиены соответственно с информационными ходами первой группы второго блока сравения и с выходами вычитаемаго вычитателя, ыходы которого соединены соответственно информационными входами второй группы ультиплексора, выходы которого соединены с ответственно с информационными входами ч твертого регистра. разрядные-выходы кот рого соединены соответственно с инфорационными входами первого регистра, в одами уменьшаемого вычитателя и инормационными входами второй группы в орого блока сравнения, выход "Меньше" крторого соединен с первыми входами пят го и шестого элементов ИЛИ, выходы которых соединены соответственно с первыми входами первого и второго элементов И, выход "равно". второго блока сравнения соединен с входом обнуления четвертого регистра, вторым входом пятого элемента ИЛИ и первым входом третьего элемента И, выход окончания работы вычи5 т,"теля соединен с управляющим входом мультиплексора. вторым входом четвертого элемента ИЛИ и входом первого формирователя импульсов, выход которого соединен с третьим входом пятого и вторым входом

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

15 И соединен с входами сдвига третьего и четвертого регистров, вторым входом четвертого элемента ИЛИ и счетным входом второго счетчика, выход которого соединен с вторым (инверсным) входом первого эле20 мента И и вторыми входами второго и третьего элементов И, выходы которых соединены соответственно с первым и вторым входами второго элемента ИЛИ, выход четвертого элемента ИЛИ соединен с вхо25 дом второго формирователя импульсов, выход -которого соединен с входом разрешения второго блока сравнения, выход "Больше" которого соединен с входом разрешения вычитателя.

1837401

Составитель И.Горбенко

Техред М.Моргентал Корректор О.Густи

Редактор

Гкзоизводственно-издательский комбинат "Патент", г, Ужгород, ул.Гагарина, 101

Заказ 2871 Тираж Подписное

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

113035 Москва Ж-35 Ра шскаа наб. 4/5