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

 

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

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

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

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

Известно, что позиционные системы счисления строятся следующим образом. Выбирается некоторое число m - основание системы счисления, и каждое число А представляется в виде комбинации его степеней с коэффициентами а_i, i=i = . Для случая двоичной системы счисления (m=2) всякое число А можно представить в виде следующего выражения: А=а_k2^k+...+а₁2¹+a_о, где a_i, i=i = - принимают значения "0" или "1".

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

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

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

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

На фиг. 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 формирует частичный остаток по модулю P_i от числа 2¹.

Далее работа устройства осуществляется следующим образом. Через открытый элемент 9 И на вход записи регистра 2 с выхода генератора 5 поступают тактовые импульсы. Эти же импульсы поступают на счетный вход счетчика 6 и на вход элемента 11 ИЛИ. Период тактовых импульсов превышает сумму времени распространения сигнала через элементы 11 ИЛИ, 10 И задержки 12 и время записи в регистр 20 накапливающего сумматора 4. По каждому тактовому импульсу осуществляется запись очередного частичного остатка в регистр 2, увеличение содержимого счетчика 6 на единицу, накапливающее суммирование частичного остатка по модулю Р_i, записанного в регистре 2, в случае равенства соответствующего коэффициента а_i, в представлении числа А_k, единице. После того, как будет сформирован самый старший частичный остаток и в зависимости от значения самого старшего коэффициента a_i произойдет или не произойдет его накапливающее суммирование в накапливающем сумматоре 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