Устройство для формирования остатка по произвольному модулю от числа Советский патент 1991 года по МПК H03M7/18 G06F11/08 

&

Изобретение относится к вычислительной технике. Его использование в системах обработки цифровой информации (например, для формирования элементов конечных полей) позволяет повысить быстродействие. Устройство содержит формирователи 2, 3 импульсов, элементы ИЛИ 5, 4, элемент 9 сравнения, вычитатель 10 и регистры 11, 12. Благодаря введению счетчика 1, элементов ИЛИ 6-8. регистров 13, 14, элементов И 15-17 и мультиплексора 18 в устройстве реализуется более быстрый ал- горитм вычислений.1 ил t9

го

ск

СП 00 00 00 00

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

Цель изобретения - повышение быстродействия.

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

Устройство содержит счетчик 1, первый и второй формирователи 2 и 3 импульсов, первый - пятый элементы ИЛИ 4-8, элемент 9 сравнения, вычитатель 10, первый - четвертый регистры 11-14, первый - третий элементы И 15 - 17 и мультиплексор 18. На чертеже обозначены информационные входы 19, входы 20 задания модуля, вход 21 Начало вычисления, выход 22 Конец вычисления, выходы 23 результата.

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

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

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

В исходном состоянии все регистры 11-14 обнулены. Модуль, по которому осуществляется формирование остатков чисел, задается параллельным двоичным кодом, подаваемым на входы 20 устройства. На входы 19 устройства поступает число в параллельном двоичном коде, причем старшие N разрядов поступают на первые входы мультиплексора 18, а младшие М - N разрядов поступают на информационные входы регистра 13, (М - количество разрядов, не- ,обходимое для представления в параллельном двоичном коде числа, от которого необходимо сформировать остаток, а N - количество разрядов, необходимое для представления в параллельном двоичном

коде модуля). После подачи кодов числа и модуля на входы 19 и 20 устройства, на вход 21 Начало вычисления подают импульс, который обнуляет счетчик 1, записывает в регистр 12 код модуля, в регистр 13 - млад0 шие разряды кода числа, а в регистр 14 - старшие разряды кода числа. Так как на управляющий вход мультиплексора 18 воздействует нулевой потенциал, то его выходы, подключенные к информационным

5 входам регистра 14, скоммутированы с его первыми входами. Этот же импульс Начало вычисления, проходя через элемент ИЛИ 6, поступает на вход формирователя 3 импульсов. По срезу входного импульса (т.е. после

0 того, как произведена запись кодов чисел и модуля в регистры 12 - 14) формирователь 3 импульсов, сформирует импульс, который разрешит сравнение элементов 9 старших N разрядов кода числа, записанных в регистре

5 14, и кода модуля, записанного в регистр 12. В результате сравнения могут возникнуть три ситуации.

а)Код числа, записанного в регистре 14, окажется меньше кода модуля. В этом слу0 чае элемент 9 сравнения выдаст на свой выход Меньше импульс, который, проходя через элемент ИЛИ 7, поступает на первый вход элемента И 15, и так как на второй (инверсный) вход элемента И 15 воздейству5 ет нулевой-потенциал с выхода счетчика 1, этот импульс пройдет через элемент И 15 и поступит на входы сдвига регистров 13 и 14. При этом код числа в этих регистрах сдвинется на один разряд в сторону старших

0 разряов (регистр 14 имеет разрядность N + 1), причем в самый младший разряд регистра 14 перепишется информация с самого старшего разряда регистра 13. Этот же импульс поступит на счетный вход счетчика

5 1, который сосчитает его, и на второй вход элемента ИЛИ 6. С выхода элемента ИЛИ 6 импульс поступает на вход формирователя 3 импульсов, который по срезу входного импульса сформирует следующий импульс для

0 разрешения работы элемента 9 сравнения и работа устройства повторится.

б)Код числа, записанного в регистре 14, окажется равен коду модуля. В этом случае элемент 9 сравнения выдаст на свой выход

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

поступает на вход формирователя 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 заполнится (его объем равен M-N). элемент И 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 сформирован остаток от заданного числа по выбранному модулю, и устройство готово к следующему циклу вычислений, при котором может быть выбран любой другой модуль и задано любое другое число.

Технико-экономическая эффективность рассматриваемого устройства заключается в повышении быстродействия формирования остатка по произвольному модулю от числа. Так, например, при разрядности числа М и разрядности модуля N известное устройство затратит (2M/2N).t единиц времени, где t - сумма времени, необходимая

для срабатывания элемента сравнения, вычитателя и для записи данных в регистр. Рассматриваемое устройство осуществляет- формирование остатка от числа по выбранному модулю за (М - N). t единиц времени.

Считая величину t примерно одинаковой в обоих случаях, оценим выигрыш В в быстродействии предлагаемого устройства, по сравнению с известным.

В

2м N

,М -N

(М-N) t M-N

5

0

5

Формула изобретения Устройство для формирования остатка по произвольному модулю от числа, содержащее элемент сравнения, выход Больше которого соединен с разрешающим входом вычитателя, первый и второй формирователи импульсов, первый элемент ИЛИ, первый вход которого является входом Начало вычисления устройства, второй элемент ИЛИ, первый и второй входы которого объединены с входами соответственно обнуления и разрешения записи первого регистра, выходы которого являются выходами результата устройства, второй регистр, выход второго элемента ИЛИ является выходом Конец вычисления устройства, отличающееся тем. что, с целью повышения быстродействиз, в устройство введены третий и четвертый регистры, счетчик, третий - пятый элементы ИЛИ, первый - третий элементы И и мультиплексор, первые информационные входы которого и информационные входы третьего регистра являются соответственно старшими и младшими разрядами информационных входов устройства, входы разрешения записи второго и третьего регистров объединены с входом обнуления счетчика и первым входом третьего элемента ИЛИ и подключены к входу Начало вычисления устройства, информационные входы второго регистра являются входами задания модуля устройства, выходы второго регистра подключены к первым ЁХОДЭМ элемента сравнения и входам вычитаемого вычитате- ля, выходы которого соединены с вторыми информационными входами мультиплексора, выходы которого подключены к установочным входам четвертого регистра, выходы которого соединены с информационными входами первого регистра, входами уменьшаемого вычитателя и вторыми информационными входами элемента сравнения, выход Меньше которого подключен к первым входам четвертого и пятого элементов ИЛИ, выходы которых соединены соответственно с разрешающими входами первого элемента И и первым входом третьего элемента И, выход Равно элемента сравнения подключен к входу четвертого

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

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

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

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