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

)5 Н 03 М 7/1 1 ь КОМИТЕТИ ОТКРЫТИЯМ ИЗОБ ЕТЕЛЬСТВУ ЕНИЯ ИСАН К АВТОРСКОМ(56) Авторское свидетельство СССР Ф 1001079, кл, Н 03 М 7/18, 1981.Авторское свидетельство СССР В 1417192, кл. Н 03 М 7/18, 1987, (54) УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ ОСТАТКА ПО МОДУЛЮ ОТ ДВОИЧНОГО ЧИС- ЛА г(57) Изобретение относится к области вычислительной техники и может быть использовано для сопряжения вычислительных устройств, функционирующих в системе остаточных классов. Цель изобретения- повышение быстродействия, Устройство для вычисления остатка по модулю от двоичного числа содержит входной регистр 1, блок 2 свертки по модулю, блоки 3,4 умножения на константу по модулю, сумматоры 5,6 по модулю, коммутатор 7, выходной регистр 8, счетчик 9, выход 10, тактовый вйд 11, и управляющий вход 12, соединенные между собой функционально. 1 ил,(3) Изобретение относится к вычислительной технике и может быть использовано для сопряжения вычислительных устройств, функционирующих в системе остаточных классов,Известно устройство для вычисления остатк по модулю от двоичного числа, содержащее первый и второй регистры, входной регистр, первый и второй коммутаторы, блок умножения на константу по модулю и сумматор по модулю,Недостатком известного устройства является низкое быстродействие. Наиболее близким к предлагаемому является устройство для вычисления остатка по модулю от двоичного числа, содержащее входной регистр,. первый и второй блоки свертки по модулю, первый и второй регистры, первый и второй коммутаторы, блок умножения на константу по модулю и сумматор по модулю, первый и второй блоки свертки по модулю, причем выходы разрядов с (3 т)-го по (в-е)-й входного регистра подключены к входу первого блока свертки по модулю (а п, где и - разрядность модуля;= )К/в, К - разрядность двоичного числа), выход которого соединен с вторым информационным входом первого коммутатора, выходы разрядов с (1 щ-т)-го по (ев)-й входного регистра подключены к входу второго блока свертки по модулю, выход которого подключен к входу второго слагаемого сумматора по модулю, выход первого коммутатора соединен с входом блока умножения на константу по модулю, выход которого Соединен с входом первого слагаемогосумматора по модулю, выход которого является выходом устройства и соединен с информационным входами первого и второго регистра, выходы которых соединены соответственно с первым и вторым информационными входами второго коммутатора. Выход последнего соединен с первым информационным входом первого коммутатбра. Вход разрешения сдвига входного регистра, управляющие входы первого и второго коммутаторов и входы разрешения приема первого и второго регистров соединены соответственно с тактовыми входами группы устройства.Недостатком известного устройства является низкое быстродействие.Цель изобретения - повышение быстродействия,Поставленная цель достигается тем, что е известное устройство, содержащее входной регистр, коммутатор, блок умножения на константу по модулю, блок свертки по модулю, сумматор по модулю, входной регистр, причем выход разрядов с 0-го по (щ)-й входного регистра подключен к входу блока свертки по модулю, выход которого подключен,к первому входу коммутатора, выход которого подключен к первому входу сумматора по модулю, выход которого подключен к входу выходного регистра. выход которого является выходом устройства и подключен к второму входу коммутатора, вход разрешения сдвига входного регистра, вход записи выходного регистра и управляющий вход коммутатора соединены соответстеенно с тактовым и управляющим входами устройства, введены второй блок умножения, причем выходы разрядов с п 1-го по(2 гп)-й входного регистра подключены к первому входу первого блока умножения на константу по модулю (п 1 п, где п - разрядность модуля), выходы разрядов с 2 п 1-го по(Зп 1-1)-й входного регистра подключены к первому входу второго блока умножения на константу по модулю, вторые входы обоих блоков умножения на константу по модулю соединены с выходом счетчика, а их выходы подключены к входам второго сумматора по модулю, выход которого подключен к второму входу первого сумматора по модулю, вход счетчика соединен с тактовым входом устройства,Отличительными признаками являются второй блок умножения нэ константу по модулю, второй сумматор по модулю, счетчик, а также образовавшиеся связи между введенными и имеющимися блоками,Предлагаемое устройство е своей работе использует следующее.Двоичное К-разрядное число Х может быть представлено в виде Преобразуем (1) к виду, удобному длянахождения остатка Х от числа Х по модулюР Х=ЗХ += .,Яэ2 рр В Р. (2) Пусть выбранный модуль Р имеет разрядность и, Разобьем двоичное представление числа Х на группы по гл двоичных разрядов, причем 1 т 1 и. С учетом разбиения преобразуем (2) к виду 1 в+ +Х=1;Г Ар 2р р р, 1=О= (6,4) 7 + (7,2) 7 + (3) 7=6,На чертеже представлена функциональная схема предлагаемого устройства.Устройство для вычисления остатка помодулю от двоичного числа содержит входной регистр 1, блок 2 свертки по модулю,блоки 3 и 4 умножения на константу по модулю, сумматоры 5 и 6 по модулю, коммутатор 7, выходной регистр 8, счетчик 9, выход10 устройства, тактовый вход 11 устройстваи управляющий вход 12 устройства. Регистр1 имеет управляющий вход, при подаче сигнала на который содержимое регистра 1сдвигается на 2 а разрядов влево, начиная са-го разряда, Шины записи в регистр 1 начертеже не показаны.Блок 2 свертки по модулю преобразуетгп-разрядное входное число Ао в п-разряд+ный остаток по модулю Р Во =Аозр, можетбыть реализован аналогично как в прототипе или с помощью ППЗУ емость которого2 слов Хп разрядов,Блоки 3 и 4 умножения осуществляютоперации умножения входного и-разрядного кода соответственно на константуф ( = 1,3,5, - нечетное) и на константу Дф = 2,4,6 . - четное) по модулю Р, Ониреализуются с помощью таблиц, записан ных в ППЗУ, емкость которых равна 2слов Х и разрядов я = ) ода - и О, ори этоми разрядов адреса задается кодом умножаемого числа Вь а Я - старших разрядовадреса определяется кодом номера константы. 55Сумматоры 5 и 6 по модулю реализуются табличным способом, например, с по-.мощью ППЗУ емкостью 2 " слов Хпразрядов каждый,Разрядность регистра 8 и коммутатора 7 равна и. Запись в регистр 8 осуществляется подачей тактового импульса на его вход записи. При подаче нулевого потенциала на управляющий вход 12 устройства коммутатор 7 подключает выход блока 2 свертки к входу сумматора 6 по модулю, а в случае подачи единичного потенциала к входу сумматора 6 по модулю подключается выход регистра 8,Счетчик 9 имеет 5-разрядов и осуществляет тактовые импульсы, номер которых является номером константы, на которую происходит умножение в блоках 3 и 4 умножения;Выход с 0-го по (в)-й разряда входного регистра 1 подключен к входу блока 2 свертки по модулю; выход которого подключен к первому входу коммутатора 7, выход которого подключен к первому входу сумматора 6 по модулю, выход которого подключен к входу выходного регистра 9, выход которого является выходом 10 устройства и подключен к второму входу коммутатора 7, управляющий вход которого соединен с управляющим входом 12 устройства, выходы в младших разрядов с а-го по (2 а)-й и с (2 в)-го по(3 а)-й входного регистра 1 соответственно подключены к первыщ входам блоков 3 и 4 умножения на константу по модулю, к вторым входам которых подключен выход счетчика 9, а их выходы подключены к входам сумматора 5 по модулю, выход которого подключен к второму входу сумматора 6 по модулю, тактовый вход 11 устройства подключен к входу счетчика 9, входу разрешения сдвига регистра 1 и входу записи регистра 8:Предлагаемое устройство работает следующим образом,В исходном состоянии в регистре 1 находится код числа А, т.е. преобразуемого числа Х, На управляющем входе 12 присутствует нулевой потенциал, Коммутатор 7 подключает выход блока 2 свертки по модулю к входу сумматора 6 по модулю. Счетчик 9 и регистр 8 обнулены,Код числа Ао, .определяемого т-младшим разрядами преобразуемого числа Х, .преобразуется блоком 2 свертки по модулю в код остатка В по модулю Р, Одновременно коды чисел А и Ао с выхода регистра 1 поступают на входы блоков 3 и 4 соответственно, Нулевой код в счетчике 9 задает номер константы, на которую происходит умножение по модулю Р, Для блока 3 величина константы равная = 2р, а для блока 4 Р 2 = 2 р, Таким образом, через время переходных процессов на выходе блоков 3+ 1 А 1 Р 11 Р+ ВО 1 Р,и 4 умножения по модулю появляются коды величины 1 А Р 1 р и 1 А 2 Р 2 Р соответ. ственно. Коды этих величин суммируются в сумматоре 5 по модулю, а код суммы в сумматоре 6 складывается с кодом величины Ва. Через время, равное времени переходных процессов в блоке умножения, сумматорах 5 и 6 на тактовый вход 11 устройства подается тактовый импульс (ТИ), который запишет код величиныА 2 ф 21 Р + 1 А 1 рР + Во +р в регистр 8,Одновременно в момент поступления ТИ содержимое регистра 1 сдвинется на 2 гп разрядов влево, состояние счетчика 9 увеличится на единицу, в данном случае в счетчике будет код единицы. На управляющий вход 12 будет подан единичный потенциал, который скоммутирует выход регистра 8 на вход сумматора 6 по модулю. При этом содержимое регистра 1 Аз , и А 4 в блоках 3 и 4 умножится на константу/Ъ ИР 4 СООтВЕтСтВЕННО, ГдЕРЗ = 12 Згп р, а 34 аа 121 р, Коды величин 1 А 2 Д 1+р и 1 А 4 А Р, суммируются в сумматорах 5 и 6 по модулю с кодом величины, записанной в регистре 8, на выходе сумматора 6 имеем результат 1 А 4 ф 41 Р+ Азиз Р+ 1 А 2 Р 21 Р+ который на втором такте запишется врегистр 8,Далее процесс работы повторяется,На последнем т такте (т = ) --- О оконК - и)чательный результат преобразования 1 Х 1+рснимается с выхода регистра 8 на выход 10устройства.Покажем преимущество предлагаемогоустройства по сравнению с базовым объектом.Быстродействие базового объекта определяется следующим выражением: ТбТсв + Тком + Тум + Тсум ++ Тзап.рг + (1-2)Тбт,(5)К где Тсв - время переходных процессов вблоке свертки по модулю;Тком - в коммутаторе;Тум - в блоке умножения;Тсум - в сумматоре по модулю;Тзвп,тг - время записи в регистр.Тбт - пеРиоД слеДованиЯ ТИ, котоРыйравенТбт 2 Тком + Тум + Тсум + Тзап.рг (6) 15 20 30 35 40 45 50 55 В то время как в предлагаемом устройстве быстродействие равно Тп = Тум + 2 Тсум + Тзап, рг + (1-1)Тпт (7)где Тп = Тум + 2 Тсум + Тсд.рг+ Тзап,рг Тсд.рг - время сдвига данных в регистре Для оценки положительного эффекта введен показатель Кт = ТбТп, показывающий, во сколько раз произошло увеличение быстродействия,Сравнивая выражения (5) и (7), видим,( - 1 ТЧтс Кт= - , УЧИтЫВаЯ, ЧтО Тбт Тпт,бта Тпт- 1то Кт=Например, для случая К = 40 разрядов,и) = 8 разрядов,= 5, а 1 = 2, Тогда5 - 1Кт = -- = 2 (раза),2Повышение быстродействия в предлагаемом устройстве достигается введением блока умножения на константу помодулю, сумматора по модулю и счетчика, а также эа счет образовавшихся связей между имеющимися и введеннымиблоками,Формула изобретения Устройство для вычисления остатка по модулю от двоичного числа, содержащее входной регистр, коммутатор, первый блок умножения на константу по модулю, блок свертки по модулю, первый сумматор по модулю, выходной регистр, причем выход разрядов с нулевого по (пт)-й вход- його регистра подключен к входу блока свертки по модулю, выход которого подключен к первому входу коммутатора, выход которого подключен к первому входу первого сумматора по модулю, выход которого подключен к входу выходного регистра, выход которого является выходом устройства и подключен к второму входу коммутатора, вход разрешения сдвига входного регистра и вход записи выходного регистра соединены с тактовым входом устройства, управляющий вход коммутатора соединен с управляющим входом устройства, отл ич а ю щ ее с я тем, что, с целью повышения быстродействия, в него введены второй блок умножения на константу по модулю, второй сумматор по модулю и счетчик, причем выходы разрядов с гп-го по (2 пт)-й. входного регистра подключены к первому входу первого блока1751857 10 Составитель А. ОленевТехред М.Моргентал Редактор С. Лисина Корректор М Шароши Заказ 2697. Тираж Подписное ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР 113035, Москва, Ж, Раушская наб 4/5 Производственно-издательский комбинат "Патент", г, Ужгород, ул.Гагарина, 101 умножения на константу по модулю (еп, где и - разрядность модуля), выходы разрядов с 2 в-го по (Зе)-й входного регистра подключены к первому входу второго блока умножения на константу по модулю, вторые входы обоих блоков умножения на константу по модулю соединены с выходом счетчика, а их выходы подключены к входам второго сумматора по модулю, выход которого подключен к второму входу первого сумма тора по модулю, вход счетчика соединен стактовым входом устройства,