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

Реферат

 

Изобретение относится к вычислительной технике и может быть использовано в цифровых вычислительных устройствах, а также в устройствах для формирования элементов конечных полей. Цель изобретения - повышение быстродействия формирования остатка - достигается введением блока 3 формирования частичных остатков, накапливающего сумматора 4 по модулю, генератора 5, триггера 8 и элемента задержки 12. Сущность изобретения заключается в том, что вычисляется частичный остаток от 2i (на первом такте i = 0), а затем анализируется коэффициент ai при представлении числа Aк в позиционной системе счисления и при ai= 1 производится накапливающее суммирование по модулю соответствующего частичного остатка, одновременно вычисляется частичный остаток от 2i+1 и т.д. до тех пор, пока не будут проанализированы все разряды регистра, в котором записано число Aк . 2 з.п.ф-лы, 3 ил.

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

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

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

Известно, что позиционные системы счисления строятся следующим образом. Выбирается некоторое число m - основание системы счисления, и каждое число А представляется в виде комбинации его степеней с коэффициентами аi, i=i = . Для случая двоичной системы счисления (m=2) всякое число А можно представить в виде следующего выражения: А=аk2k+...+а121+aо, где ai, i=i = - принимают значения "0" или "1".

Для вычисления остатка от числа А по модулю достаточно просуммировать частичные остатки по модулю Р от числа 2i для max i, для которых коэффициент аi=1. Способ вычисления частичного остатка состоит в следующем. Частичный остаток от 2о для любого модулю Р2 всегда равен единице. Частичный остаток от 21 в два раза превышает (с учетом операции приведения по модулю) частичный остаток от 2 и т.д., т.е. частичный остаток от 2i в два раза превышает частичный остаток от 2i-1. Таким образом, вычисления частичного остатка от 2i заключается в умножении на два частичного остатка от 2i-1 и приведения результата по модулю Р. Операция приведения по модулю Р для чисел, не превышающих величину 2Р-1, реализуется следующим образом. Если число не превышает величину Р, то оно остается без изменения, если же число лежит в интервале от Р до 2Р-1, то из него вычитается модуль Р, а результат является остатком.

Операция умножения на два (как видно из представленного выражения), может быть реализована сдвигом всех разрядов умножаемого числа на один влево, либо подачей разрядов множимого на выход результата в такой последовательности: 2i разряд множимого на 2i+1 разряд произведения, i=i = .

Таким образом, вычисления остатка от числа А по модулю Р может быть выполнено в следующий последовательности: 1. Вычисляется частичный остаток от 2i (на первом такте i=0).

2. Анализируется ai - коэффициент (в формуле числа А, если он равен единице, то производится накапливающее суммирование соответствующего частичного остатка, одновременно вычисляется частичный остаток от 2i+1 (на умножение 2i на 2 время не затрачивается), если же этот коэффициент равен нулю, то данный частичный остаток не суммируется, а вычисляется частичный остаток от 2i+1, и т.д. пока не будут проанализированы все разряды регистра, в котором записано число А. По окончании работы на выходе накапливающего сумматора будет сформирован остаток по модулю Р от числа А.

На фиг. 1 представлена функциональная схема устройства для формирования остатка по произвольному модулю от числа, на фиг. 2 - функциональная схема накапливающего сумматора по модулю, а на фиг. 3 - функциональная схема блока формирования частичных остатков.

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

Накапливающий сумматор 4 по модулю содержит (см. фиг. 2) сумматор 18, блок формирования частичных остатков 19 и регистр 20.

В состав блока 3 формирования частичных остатков (см. фиг. 3) входят сумматоры 21, 22, элемент И 23, элемент НЕ 24 и ключ 25.

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

В исходном состоянии триггер 8 (см. фиг. 1, 2, 3), счетчик 6, регистры 1, 2 и 20 обнулены. Перед началом работы на вход 13 устройства подается число Ак, от которого необходимо сформировать остаток, а на входы модуля 14 код модуля Рi, по которому формируется остаток.

Начало работы устройства определяется моментом подачи на его вход 15 единичного потенциала. Этот потенциал устанавливает триггер 8 в единичное состояние, записывает единицу в младший разряд регистра 2, устанавливает счетчик 6 в единичное состояние, записывает код числа Аk в регистр 1, поступает на обнуляющий вход регистра 20 накапливающего сумматора 4 и поступает на вход элемента 11 ИЛИ. После установки счетчика 6 в единичное состояние, на адресные входы мультиплексора 7 поступит код единицы. Мультиплексор 7 скоммутирует свой первый вход, подключенный к 2о разряду регистра 1 в результате чего на выходе мультиплексора 7 окажется логический потенциал, записанный в 2о разряде регистра 1, который поступит на вход элемента 10 И. К этому же времени с выхода элемента 11 ИЛИ, через элемент задержки 12, на другой вход элемента 10 И поступит единичный потенциал. Одновременно, на информационный вход накапливающего сумматора 4 поступит частичный остаток от 2о=1 с выхода регистра 2. Если коэффициент ао числа Аk равен единице, то на выходе элемента 10 И появится импульс, который поступит на вход записи накапливающего сумматора 4 и осуществит запоминание частичного остатка от 2о. Если же коэффициент ао=0, то такой импульс на вход записи накапливающего сумматора 4 не поступит и запоминания частичного остатка от 2о не произойдет.

Как только в регистр 2 будет записана единица, параллельно с вышеописанной работой устройства, осуществляется формирование частичного остатка в блоке 3. Причем, выходы регистра 2 соединены со входами блока 3 со сдвигом на один разряд влево, т.е. число на его входах всегда в 2 раза больше числа, записанного в регистре 2. Поэтому блок 3 формирует частичный остаток по модулю Pi от числа 21.

Далее работа устройства осуществляется следующим образом. Через открытый элемент 9 И на вход записи регистра 2 с выхода генератора 5 поступают тактовые импульсы. Эти же импульсы поступают на счетный вход счетчика 6 и на вход элемента 11 ИЛИ. Период тактовых импульсов превышает сумму времени распространения сигнала через элементы 11 ИЛИ, 10 И задержки 12 и время записи в регистр 20 накапливающего сумматора 4. По каждому тактовому импульсу осуществляется запись очередного частичного остатка в регистр 2, увеличение содержимого счетчика 6 на единицу, накапливающее суммирование частичного остатка по модулю Рi, записанного в регистре 2, в случае равенства соответствующего коэффициента аi, в представлении числа Аk, единице. После того, как будет сформирован самый старший частичный остаток и в зависимости от значения самого старшего коэффициента ai произойдет или не произойдет его накапливающее суммирование в накапливающем сумматоре 4, счетчик 6 выдаст на свой выход переполнения импульс (объем счетчика 6 равен количеству разрядов регистра 1, а количество разрядов регистра 1 равно количеству разрядов регистра 2), который обнулит триггер 8 и поступит на выход 17 окончания работы устройства, свидетельствуя о том, что формирование остатка от числа Аk по модулю Рi закончено. При этом на вход 13 устройства может быть подано другое число, от которого необходимо сформировать остаток, а на входе 14 может быть сменен модуль.

Накапливающий сумматор 4 по модулю (см. фиг. 2) работает следующим образом. Сумматор 18 суммирует коды чисел, поступающие на его входы. Причем одно число поступает извне, а второе с выходов регистра 20. Блок 19 формирования частичных остатков осуществляет формирование остатка по модулю Рi от числа, поступающего с выходов сумматора 18. Результат с выхода блока 19 записывается в регистр 20 под воздействием импульса на его вход записи. Таким образом, в регистре 20 всегда записано число, не превышающее величину модуля Рi и равное сумме всех чисел, поступивших на вход блока 4 и стробируемых импульсом записи.

Блоки формирования 19 и 3 частичных остатков (см. фиг. 3) работают следующим образом. Сумматор 21 совместно с элементом НЕ 24 выполняют функцию вычитания модуля из числа, от которого необходимо сформировать частичный остаток. Если разность меньше нуля, то сумматор 22 добавляет к этой разности код модуля (т.е. входное число было меньше модуля), если же разность больше нуля, то ключ 25 оказывается закрытым и эта разность поступает без изменения через сумматор 22 блока. Таким образом, на выходе блока формирования частичных остатков будет сформирован остаток от числа, воздействующего на его входы по модулю Рi.

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

1. УСТРОЙСТВО ДЛЯ ФОРМИРОВАНИЯ ОСТАТКА ПО ПРОИЗВОЛЬНОМУ МОДУЛЮ ОТ ЧИСЛА, содержащее два элемента И, мультиплексор, два регистра, счетчик и элемент ИЛИ, причем информационный вход первого регистра соединен с входом числа устройства, выход первого элемента И - со счетным входом счетчика и первым входом элемента ИЛИ, второй вход которого соединен с входом установки счетчика, входом записи первого регистра и входом начала вычисления устройства, отличающееся тем, что, с целью повышения быстродействия, в него введены накапливающий сумматор по модулю, блок формирования частичных остатков, триггер, элемент задержки и генератор тактовых импульсов, выход которого соединен с первым входом первого элемента И,второй вход которого соединен с выходом триггера, вход установки которого соединен с информационным входом младшего разряда второго регистра, входом сброса накапливающего сумматора по модулю и входом начала вычисления устройства, вход модуля которого соединен с первым входом блока формирования частичных остатков и первым информационным входом накапливающего сумматора по модулю, второй информационный вход которого соединен с выходом второго регистра и вторым входом блока формирования частичных остатков, выходы которого соединены с соответствующими информационными разрядными входами, кроме входа младшего разряда, второго регистра, вход записи которого соединен с выходом первого элемента И, выход элемента ИЛИ соединен с входом элемента задержки, выход которого соединен с первым входом второго элемента И, второй вход которого соединен с выходом мультиплексора, информационный вход которого соединен с выходом первого регистра, а адресный вход - с информационными выходами счетчика, выход переполнения которого соединен с входом сброса триггера и выходом окончания вычисления устройства, выход второго элемента И соединен с входом записи накапливающего сумматора по модулю, выход которого соединен с выходом результата устройства.

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

3. Устройство по пп. 1 и 2, отличающееся тем, что блок формирования частичных остатков содержит элемент И, два сумматора, ключ и элемент НЕ, вход которого соединен с информационным входом ключа и первым информационным входом блока, выход которого соединен с выходом первого сумматора, вход первого слагаемого которого соединен с выходом ключа, управляющий вход которого соединен с выходом элемента И, первый вход которого соединен с выходом переноса второго сумматора, выход суммы которого соединен с входом второго слагаемого первого сумматора, второй вход элемента И соединен с входом старшего разряда второго информационного входа блока, вход логической единицы которого соединен с входом переноса второго сумматора, вход второго слагаемого которого соединен с вторым информационным входом блока, кроме входа старшего разряда.

РИСУНКИ

Рисунок 1, Рисунок 2, Рисунок 3