Устройство для вычисления остатка по модулю от двоичного числа

 

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

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (19) (! Ф) (я)з Н 03 M 7/18

ГОСУДАРСТВЕН-Нэ!Й КОМИТЕТ

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР

) 13 4

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4848934/24 (22) 09.07.90 (46) 30.07.92. Бюл. ЬЬ 28 (72) Н.И,Червяков, А.А.Оленев и К,M.Сагреев (56) Авторское свидетельство СССР

Ф 1001079, кл, Н 03 М 7/18, 1981.

Авторское свидетельство СССР

РЬ 1417192, кл. Н 03 М 7/18, 1987. (54) УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ ОСТАТКА ПО МОДУЛЮ ОТ ДВОИЧНОГО ЧИСЛА

2 (57} Изобретение относится к области вычислительной техники и может быть использовано для сопряжения вычислительных устройств, функционирующих в системе ос„таточных классов. Цель изобретения- повышение быстродействия. Устройство для вычисления остатка по модулю от двоичного числа содержит входной регистр 1, блок 2 свертки по модулю, блоки 3,4 умножения на константу по модулю, сумматоры 5,6 по модулю, коммутатор 7, выходной регистр 8, счетчик 9, выход 10, тактовый вЖд 11, и управляющий вход 12, соединенные между собой функционально. 1 ил, 1751857

20

К вЂ” 1

Х =, ), а 2

1=0

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

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

Наиболее близким к предлагаемому является устройство для вычисления остатка по модулю от двоичного числа, содержащее входной регистр,. первый и второй блоки свертки по модулю, первый и второй регистры, первый и второй коммутаторы, блок умножения на константу по модулю и сумматор по модулю, первый и второй блоки свертки по модулю, причем выходы разрядов с (Im-1)-го по (Im-m)-й входного регистра подключены к входу первого блока свертки по модулю (в п, где и — разрядность модуля; I = jK/m(, К вЂ” разрядность двоичного числа), выход которого соединен с вторым информационным входом первого коммутатора, выходы разрядов с ((m-m-1)-ro no (Im-2m)-й входного регистра подключены к входу второго блока свертки по модулю, выход которого подключен к входу второго слагаемого сумматора по модулю, выход первого коммутатора соединен с входом блока умножения на константу по модулю, выход которого Соединен с входом первого слагаемого сумматора по модулю, выход которого является выходом устройства и соединен с информационным входами первого и второго регистра, выходы которых соединены соответственно с первым и вторым информационными входами второго коммутатора. Выход последнего соединен с первым информационным входом первого коммутатбра. Вход разрешения сдвига входного регистра, управляющие входы первого и второго коммутаторов и входы разрешения приема первого и второго регистров соединены соответственно с тактовыми входами группы устройства.

Недостатком известного устройства является низкое быстродействие.

Цель изобретения — повышение быстродействия, Поставленная цель достигается тем, что в известное устройство, содержащее входной регистр, коммутатор, блок умножения на константу по модулю, блок свертки по модулю, сумматор по модулю, входной регистр, причем выход разрядов с 0-ro по (m1)-й входного регистра подключен к входу блока свертки по модулю, выход которого подключен,к первому входу коммутатора, выход которого подключен к первому входу сумматора по модулю, выход которого подключен к входу выходного регистра. выход которого является выходом устройства и подключен к второму входу коммутатора, вход разрешения сдвига входного регистра, вход записи выходного регистра и управляющий вход коммутатора соединены соответственно с тактовым и управляющим входами устройства, введены второй блок умножения, причем выходы разрядов с m-го по (2гп-1)-й входного регистра подключены к первому входу первого блока умножения на константу по модулю (т п, где п — разрядность модуля), выходы разрядов с 2m-го по (3m-1)-й входного регистра подключены к первому входу второго блока умножения на константу по модулю, вторые входы обоих блоков умножения на константу по модулю соединены с выходом счетчика, а их выходы подключены к входам второго сумматора по модулю, выход которого подключен к второму входу первого сумматора по модулю, вход счетчика соединен с тактовым входом устройства, Отличительными признаками являются второй блок умножения на константу по модулю, второй сумматор по модулю, счетчик, а также образовавшиеся связи между введенными и имеющимися блоками.

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

Двоичное К-разрядное число X может быть представлено в виде

Преобразуем (1) к виду, удобному для нахождения остатка Х от числа Х по модулюР

Х =2Х2 +=2 ., Я а; 2 2 2 р 2 р р. (2) Пусть выбранный модуль P имеет разрядность и, Разобьем двоичное представление числа Х на группы no m двоичных разрядов, причем m n. С учетом разбиения преобразуем (2) к виду г — 1 y +

Х=!,"Г„! IAilp 22 pl Ipl Ip, i -o

1751857 к где Ai = ai 2, =, 1= 0,И.

J =о

Обозначим B;== IA I и,В =!2 I приведем (3) к виду

6 — 1 + Ф

Х= Х< =I «г В Р IPIp. (4) =о

При этом Pi является константами, вычисленными заранее.

Пример. Пусть К=12 и Х=1651=

01101110011, Возьмем и =3; Р = 7, m = 4, тогда А0= 3;

А1 = 7; Аг = 6, следовательно число Х = 1651 можно представить в виде Х = 6,256+ 7,16+

+ 3,1 = 1651, Вычислим Po = 1; Pt = (16) 7 = 2; . Pz = (256) т = 4, откуда Х = (1651) т

= (6,4) т + (7,2) 7 + {3) 7= 6.

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

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

10 устройства, тактовый вход 11 устройства и управляющий вход 12 устройства. Регистр

1 имеет управляющий вход, при подаче сигнала на который содержимое регистра 1 сдвигается на 2m разрядов влево, начиная с m-го разряда, Шины записи в регистр 1 на чертеже не показаны.

Блок 2 свертки по модулю преобразует

m-разрядное входное число А0 в п-разряд+ ный остаток по модулю Р Bo = I AoIp, может быть реализован аналогично как в прототипе или с помощью ППЗУ емкость которого

2 слов Хп разрядов, Блоки 3 и 4 умножения осуществляют операции умножения входного и-разрядного кода соответственно на константу

Pj (i = 1,3,5, ...- нечетное) и на константу Д» ф = 2,4,6 ... — четное) по модулю Р, Они реализуются с помощью таблиц, записан ных в ППЗУ, емкость которых равна 2""

СЛОВ Х П рдЗР ЯДОВ ($ = )092 — 0. f1pM ЭТОМ и разрядов адреса задается кодом умножаемого числа В, à S — старших разрядов адреса определяется кодом номера константы. 55

Сумматоры 5 и 6 по модулю реализуются табличным способом, например, с помощью ППЗУ емкостью 2 " слов Хп разрядов каждый.

Разрядность регистра 8 и коммутатора

7 равна и. Запись в регистр 8 осуществляется подачей тактового импульса на его вход записи. При подаче нулевого потенциала на управляющий вход 12 устройства коммутатор 7 подключает выход блока 2 свертки к входу сумматора 6 по модулю, а в случае подачи единичного потенциала к входу сумматора 6 по модулю подключается выход регистра 8, Счетчик 9 имеет $-разрядов и осуществляет тактовые импульсы, номер которых является номером константы, на которую происходит умножение в блоках 3 и 4 умножения;

Выход с 0-го по (m-1)-й разряда входного регистра 1 подключен к входу блока 2 свертки по модулю; выход которого подключен к первому входу коммутатора 7, выход которого подключен к первому входу сумматора 6 по модулю, выход которого подключен к входу выходного регистра 9, выход которого является выходом 10 устройства и подключен к второму входу коммутатора 7, управляющий вход которого соединен C управляющим входом 12 устройства, выходы

m младших разрядов с m-го по (2m-1)-й и с (2m)-ro по {Зе-1)-й входного регистра 1 соответственно подключены к первым входам блоков 3 и 4 умножения на константу по модулю, к BTopblM входам которых подключен выход счетчика 9, а их выходы подключены к входам сумматора 5 по модулю, выход которого подключен к второму входу сумматора 6 по модулю, тактовый вход 11 устройства подключен к входу счетчика 9, входу разрешения сдвига регистра 1 и входу записи регистра 8:

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

В исходном состоянии в регистре 1 находится код числа А, т.е. преобразуемого числа Х. На управляющем входе 12 присутствует нулевой потенциал. Коммутатор 7 подключает выход блока 2 свертки по модулю к входу сумматора 6 по модулю. Счетчик

9 и регистр 8 обнулены, Код числа А0, определяемого m-младшим разрядами преобразуемого числа Х, .преобразуется блоком 2 свертки по модулю в код остатка В по модулю Р, Одновременно коды чисел А и А0 с выхода регистра 1 поступают на входы блоков 3 и 4 соответственно, Нулевой код в счетчике 9 задает номер константы, на которую происходит умножение по модулю P. Для блока 3 величина константы равнаP, = !2 I p, а для блока 4

j4 = 12 ml ð, Таким образом, через время переходных процессов на выходе блоков 3

1751857

2,ат=) — — — {.

+ IA1P1I P+ ВО 1 P и 4 умножения по модулю появляются коды величины IА1 f1 I р и 1А2 р21 р соответ. ственно. Коды этих величин суммируются в сумматоре 5 по модулю, а код суммы в сумматоре 6 складывается с кодом величины

Ва. Через время, равное времени переходных процессов в блоке умножения, сумматорах 5 и 6 на тактовый вход 11 устройства подается тактовый импульс (ТИ), который запишет код величины I A2p2l Р + I A1j911 P

+ 1В I +р в регистр 8, Одновременно в момент поступления

ТИ содержимое регистра 1 сдвинется на 2m разрядов влево, состояние счетчика 9 увеличится на единицу, в данном случае в счетчике будет код единицы. На управляющий вход 12 будет подан единичный потенциал, который скоммутирует выход регистра 8 на вход сумматора 6 по модулю. При этом содержимое регистра 1 Аз, и А4 в блоках 3 и 4 умножится на константурз иф4 соответственно, где {Вз = 12 1 ð, а

Р4- 12 1 р. Коды величин IAz Д1+р и

lA4p4l Р, суммируются в сумматорах 5 и 6 по модулю с кодом величины, записанной в регистре 8, на выходе сумматора 6 имеем результат

IA4 j94I Р + 1Азфз1 Р + lA2P21 Р + который на втором такте запишется в регистр 8.

Далее процесс работы повторяется, На последнем t такте {t = { — — — {{ оконК вЂ” m чательный результат преобразования I Х1+р снимается с выхода регистра 8 на выход 10 устройства.

Покажем преимущество предлагаемого устройства по сравнению с базовым объектом.

Быстродействие базового объекта определяется следующим выражением:

Te - Тса + Тком + Тум + Тсум +

+ Тзап.рг + (1-2)Тбт, — (5)

К где Уса — время переходных процессов в блоке свертки по модулю;

Тком — в коммутаторе;

Тум — в блоке умножения;

Гсум — в сумматоре по модулю;

Тзап.тг — время записи в регистр.

Ter — период следования ТИ, который равен

Тбт 2Тком + Тум + Тсум + Тзап.рг (6) 15

В то время как в предлагаемом устройстве быстродействие равно

Тп = Тум + 2Тсум + Тзап.рг + (1-1)Тпт (7) где Тп = Тум + 2Тсум + Тсд.рг + Тзап.рг

Тсд.pr — время сдвига данных в регистре

Для оценки положительного эффекта введен показатель Kr = Te/Tr{, показывающий, во сколько раэ произошло увеличение быстродействия, Сравнивая выражения (5) и (7), видим, «(1 — 1 Т что Kr=, учитывая, что Ter =Тпт, бт

t Тпт ! — 1 то Кт=

Например, для случая К = 40 разрядов, m =8 разрядов, = 5, а 1 = 2, Тогда

5 — 1

Кт = — — = 2 (раза).

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

Устройство для вычисления остатка по модулю от двоичного числа, содержащее входной регистр, коммутатор, первый блок умножения на константу по модулю, блок свертки по модулю, первый сумматор по модулю, выходной регистр, причем выход разрядов с нулевого по (m-1)-й входйого регистра подключен к входу блока свертки по модулю, выход которого подключен к первому входу коммутатора, выход которого подключен к первому входу первого сумматора по модулю, выход которого подключен к входу выходного регистра, выход которого является выходом устройства и подключен к второму входу коммутатора. вход разрешения сдвига входного регистра и вход записи выходного регистра соединены с тактовым входом устройства, управляющий вход коммутатора соединен с управляющим входом устройства, отл и ч а ю щ ее с я тем, что, с целью повышения быстродействия, в него введены второй блок умножения на константу по модулю, второй сумматор по модулю и счетчик, причем выходы разрядов с

m-го по (2m-1)-й. входного регистра подключены к первому входу первого блока

1751857

Составитель А. Оленев

Техред М.Моргентал

Редактор С. Лисина

Корректор М, Шароши

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

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

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

Производственно-издательский комбинат "Патент", г, Ужгород, ул.Гагарина, 101 умножения на константу по модулю (m en, где и — разрядность модуля), выходы разрядов с 2m-го по (3m-1)-й входного регистра подключены к первому входу второго блока умножения на константу по модулю, вторые входы обоих блоков умножения на констанг ту по модулю соединены с выходом счетчика, а их выходы подключены к входам второго сумматора по модулю, выход которого подключен к второму входу первого сумма5 тора по модулю, вход счетчика соединен с тактовым входом устройства.