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

(56) Авторское свидетельство СССРМ 1105895, кл. б 06 Г 11/08, 1983,Авторское свидетельство СССРМ 1575186, кл, 6 06 Г 11/10, 22,09.88.Авторское свидетельство СССР1 Ф 1396281, кл, Н 03 М. 7/18, 1986.(54) УСТРОЙСТВО ДЛЯ ФОРМИРОВАНИЯ ОСТАТКА ПО ПРОИЗВОЛЬНОМУ МОДУЛЮ ОТ ЧИСЛА(57) Изобретение относится к вычислительной технике. Его использование в системах обработки цифровой информации (например, для формирования элементов конечных полей) позволяет повысить быстродействие, Устройство содержит формирователи 2, 3 импульсов, элементы ИЛИ 5, 4, элемент 9 сравнения, вычитатель 10 и регистры 11, 12. Благодаря введению счетчика 1, элементов ИЛИ 6-8, регистров 13, 14, элементов И 15 - 17 и мультиплексора 18 в устройстве реализуется более быстрый ал- горитм вычислений. 1 ил. ХО ОСУДАРСТВЕН 1 ЫЙ КОМИТЕТО ИЗОБРЕТЕНИЯМ И ОТКРЫТИРИ ГКНТ СССР 658388 А 1Изобретение относится к вычислительной технике и может использоваться в системах обработки цифровой информации, вчастности для формирования элементов конечных полей.Цель изобретения - повышение быстродействия.На чертеже представлена функциональная схема устройства,Устройство содержит счетчик 1, первыйи второй формирователи 2 и 3 импульсов,первый - пятый элементы ИЛИ 4 - 8, элемент 9 сравнения, вычитатель 10, первый -четвертый регистры 11 - 14, первый - третий элементы И 15 - 17 и мультиплексор 18.На чертеже обозначены информационныевходы 19, входы 20 задания модуля, вход 21"Начало вычисления", выход 22 "Конец вычисления", выходы 23 результата,Принцип работы устройства для формирования остатка по произвольному модулюот числа заключается в реализации следующего алгоритма приведения чисел по модулю,Из старших разрядов некоторого числа,поступающего на входы устройства, производится вычитание кода выбранногомодуля, если величина числа, образованного этими разрядами, больше величинывыбранного модуля; если же оно окажетсяменьше, то производится сдвиг на один разряд в сторону старших разрядов и циклповторяется, После вычитания разность записывается на место уменьшаемого в регистр старших разрядов, производитсясдвиг полученного кода на один разряд всторону старших разрядов и вся операцияповторяется до тех пор, пока младшиеразряды кода числа не будут сдвинуты врегистр старших разрядов, содержимоекоторого после записи в него разности последней операции вычитания и будет соответствовать коду результата вычислений,т,е. величине остатка числа по выбранномумодулю.Устройство для формирования остаткапо произвольному модулю от числа работает следующим образом.В исходном состоянии все регистры11 - 14 обнулены, Модуль, по которому осуществляется формирование остатков чисел,задается параллельным двоичным кодом,подаваемым на входы 20 устройства. Навходы 19 устройства поступает число в параллельном двоичном коде, причем старшие М разрядов поступают на первые входымультиплексора 18, а младшие М - М разрядов поступают на информационные входырегистра 13,(М - количество разрядов, необходимое для представления в параллель 10 15 20 25 30 35 40 45 50 55 ном двоичном коде числа, от которого необходимо сформировать остаток, а М - количество разрядов, необходимое для представления в параллельном двоичном коде модуля). После подачи кодов числа и модуля на входы 19 и 20 устройства, на вход 21 "Начало вычисления" подают импульс, который обнуляет счетчик 1, записывает в регистр 12 код модуля, в регистр 13 - младшие разряды кода числа, а в регистр 14 - старшие разряды кода числа, Так как на управляющий вход мультиплексора 18 воздействует нулевой потенциал, то его выходы, подключенные к информационным входам регистра 14, скоммутированы с его первыми входами, Этот же импульс "Начало вычисления", проходя через элемент ИЛИ 6, поступает на вход формирователя 3 импульсов. По срезу входного импульса (т.е, после того, как произведена запись кодов чисел и модуля в регистры 12 - 14) формирователь 3 импульсов, сформирует импульс, который разрешит сравнение элементов 9 старших М разрядов кода числа, записанных в регистре 14, и кода модуля, записанного в регистр 12, В результате сравнения могут возникнуть три ситуации.а) Код числа, записанного в регистре 14, окажется меньше кода модуля, В этом случае элемент 9 сравнения выдаст на свой выход "Меньше" импульс, который, проходя через элемент ИЛИ 7, поступает на первый вход элемента И 15, и так как на второй (инверсный) вход элемента И 15 воздействует нулевой потенциал с выхода счетчика 1, этот импульс пройдет через элемент И 15 и поступит на входы сдвига регистров 13 и 14. При этом код числа в этих регистрах сдвинется на один разряд в сторону старших разряов (регистр 14 имеет разрядность М + 1), причем в самый младший разряд регистра 14 перепишется информация с самого старшего разряда регистра 13. Этот же импульс поступит на счетный вход счетчика 1, который сосчитает его, и на второй вход элемента ИЛИ 6, С выхода элемента ИЛИ 6 импульс поступает на вход формирователя 3 импульсов, который по срезу входного импульса сформирует следующий импульс для разрешения работы элемента 9 сравнения и работа устройства повторится,б) Код числа, записанного в регистре 14, окажется равен коду модуля, В этом случае элемент 9 сравнения выдаст на свой выход "Равно" импульс, который обнуляет регистр 14 и, проходя через элементы ИЛИ 7 и И 15, перепишет информацию с самого старшего разряда регистра 13 в самый младший разряд регистра 14, Этот импульс также сосчитается счетчиком 1 и через элемент ИЛИ 65 10 15 20 25 30 35 40 45 50 55 поступает на вход формирователя 3 импульсов, который сформирует импульс для разрешения работы элемента 9 сравнения,в) Код числа, записанного в регистре 14, окажется больше кода модуля, В этом случае элемент 9 сравнения выдает на свой выход "Больше" импульс. который поступает на вход "Начало вычитания" вычитателя 10. При этом вычитатель 10 вычитает из кода числа, записанного в регистре 14, код модуля и выдает на свои информационные выходы код разности, Одновременно на выходе "Конец вычитания" вычитателя 10 появляется импульс, который устанавливает мультиплексор 18 в состояние коммутации его выходов со своими вторыми входами. Этот же импульс воздействует через элемент ИЛИ 4 на вход разрешения записи регистра 14. В результате в регистр 14 записывается код разности с выходов вычитателя 10. Импульс "Конец вычитания" воздействует также на вход формирователя 2 импульсов, По срезу входного импульса (т.е, после того, как произойдет запись в регистр 14) формирователь 2 импульсов сформирует импульс, который, проходя через элементы ИЛИ 7 и И 15, осуществляет сдвиг информации в регистрах 14 и 13 в сторону старших разрядов и переписывает информацию с самого старшего разряда регистра 13 в самый младший разряд регистра 14, а также сосчитается счетчиком 1 и поступает через элемент ИЛИ 6 на вход формирователя 3 импульсов, По срезу входного импульса формирователь 3 импульсов сформирует импульс, который разрешает работу элемента 9 сравнения. Как только счетчик 1 заполнится (его объем равен М-М), элемент И 15 закроется и импульсы с выхода элемента 9 сравнения будут поступать по другой цепи. Если при выполнении последней операции сравнения элемент 9 выдаст импульс на свой выход "Меньше", то этот импульс, проходя через элемент ИЛИ 8 и открытый элемент И 17, поступает на вход разрешения записи регистра 11 и на первый вход элемента ИЛИ 5. При этом в регистр 11 записывается результат вычислений (т,е. остаток по выбранному модулю от заданного числа), а на выходе элемента ИЛИ 5 появляется импульс "Конец вычисления", свидетельствующий о том, что формирование остатка закончено, его код записан в выходном регистре 11 и устройство готово к следующему циклу вычислений. Если же элемент 9 сравнения выдаст импульс на свой выход "Равно", то этот импульс обнуляет регистр 14, через открытый элемент И 16 поступает на второй вход элемента ИЛИ 5 и обнуляет выходной регистр 11. На выходе 22 появляется импульс "Конец вычисления", При этом остаток от заданного числа по выбранному модулю будет тождественно равен нулю. А если же элемент 9 сравнения выдаст импульс на свой выход "Больше", то этот импульс разрешает вычитание кода модуля из кода числа, записанного в регистре 14, разность будет записана в регистр 14, и далее под воздействием импульса, сформированного формирователем 2 импульсов и прошедшего через элемент ИЛИ 8, и открытый элемент И 17 эта разность будет записана в выходной регистр 11, На выходе 22 появляется импульс "Конец вычисления", свидетельствующий о том, что на выходах 23 сформирован остаток от заданного числа по выбранному модулю, и устройство готово к следующему циклу вычислений, при котором может быть выбран любой другой модуль и задано любое другое число.Технико-экономическая эффективность рассматриваемого устройства заключается в повышении быстродействия формирования остатка по произвольному модулю от числа. Так, например, при разрядности числа М и разрядности модуля й известное устройство затратит (2 /2 )л единиц врем имени, где т - сумма времени, необходимая для срабатывания элемента сравнения, вычитателя и для записи данных в регистр, Рассматриваемое устройство осуществляет формирование остатка от числа по выбранному модулю за (М - И). т единиц времени, Считая величину 1 примерно одинаковой в обоих случаях, оценим выигрыш В в быстродействии предлагаемого устройства, по сравнению с известным.2 т 2м - м м - иВ. -Формула изобретения Устройство для формирования остатка по произвольному модулю от числа, содержащее элемент сравнения, выход "Больше" которого соединен с разрешающим входом вычитателя, первый и второй формирователи импульсов, первый элемент ИЛИ, первый вход которого является входом "Начало вычисления" устройства, второй элемент ИЛИ, первый и второй входы которого объединены с входами соответственно обнуления и разрешения записи первого регистра, выходы которого являются выходами результата устройства, второй регистр, выход второго элемента ИЛИ является выходом "Конец вычисления" устройства, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродейст1658388 Составитель О, РевинскийРедак гор В,Бугренкова Техред М.Моргентал Корректор М.йарошиЗаказ 1722 Тираж 471 ПодписноеВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР113035, Москва, Ж, Раушская наб., 4/5 Производственно-издательский комбинат "Патент", г, Ужгород, ул.Гагарина, 101 вия, в устройство введены третий и четвертый регистры, счетчик, третий - пятый элементы ИЛИ, первый - третий элементы И и мультиплексор, первые информационные входы которого и информационные входы третьего регистра являются соответственно старшими и младшими разрядами информационных входов устройства, входы разрешения записи второго и третьего регистров объединены с входом обнуления счетчика и первым входом третьего элемента ИЛИ и подключены к входу "Начало вычисления" устройства, информационные входы второго регистра являются входами задания модуля устройства, выходы второго регистра подключены к первым входам элемента сравнения и входам вычитаемого вычитателя, выходы которого соединены с вторыми информационными входами мультиплексора, выходы которого подключены к установочным входам четвертого регистра, выходы которого соединены с информационными входами первого регистра, входами уменьшаемого вычитателя и вторыми информационными входами элемента сравнения, выход "Меньше" которого подключен к первым входам четвертого и пятого элементов ИЛИ, выходы которых соединены соответственно с разрешающими входами первого элемента И и первым входом третьего элемента И, выход "Равно" элемента сравнения подключен к входу четвертого 5 регистра, второму входу четвертого элемента ИЛИ и первому входу второго элемента И, выход окончания работы вычитателя соединен с управляющим входом мультиплексора, вторым входом первого элемента ИЛИ 10 и входом первого формирователя импульсов, выход которого подключен к третьему входу четвертого и второму входу пятого элементов ИЛИ, выходы первого элемента ИЛИ и третьего регистра соединены соот ветственно с входом разрешения записи иинформационным входом четвертого регистра, выход первого элемента И подключен к входам сдвига третьего и четвертого регистров, второму входу третьего элемента 20 ИЛИ и счетному входу счетчика, выход которогосоединен с запрещающим входом первого элемента И и вторыми входами второго и третьего элементов И, выходы которых подключены сомветственно к первому и второму входам второго 25 элемента ИЛИ, выход третьего элемента ИЛИсоединен с входом второго формирователя импульсов, выход которого подключен к разрешающему входу элемента сравнения.