Параллельно-последовательный умножитель по произвольному модулю

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

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

Известно устройство (аналог) для умножения чисел по модулю, содержащее два входных регистра, два дешифратора, три группы элементов ИЛИ, четыре группы элементов И, табличный вычислитель значений вида ''(mod/2)+/2, пять элементов ИЛИ, два элемента И и шифратор (см. А.с.1187161 СССР, МПК G06F 7/49, 23.10.1985).

Недостатком данного устройства является низкое быстродействие.

Известно устройство (аналог) для умножения два по модулю, содержащий сумматор и мультиплексор (см. Пат.2015537 Российская Федерация, МПК G06F 7/49. Умножитель на два по модулю [Текст] / Петренко В.И., Чипига А.Ф.; 30.06.1994).

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

Наиболее близким по технической сущности (прототипом к предлагаемой полезной модели) является умножитель по модулю, содержащий умножитель, n сумматоров, n инверторов, (n-1) умножителей на константу и мультиплексор (см. Пат.2299461 Российская Федерация, МПК G06F 7/523, G06F 7/72. Умножитель по модулю [Текст] / Петренко В.И., Кузьминов Ю.В.; патентообладатели Петренко В.И., Кузьминов Ю.В. - №2005130895/09; заявл. 05.10.05; опубл. 20.05.07, Бюл. №14).

Недостатком данного устройства является большие аппаратурные затраты.

Цель полезной модели - сокращение аппаратурных затрат.

Поставленная цель достигается тем, что в устройство содержащие

позиционный умножитель, (k-1) сумматоров, (k-1) инверторов, (k-2) умножителей на константу и мультиплексор, вход подачи логической единицы, шины подачи двоичных кодов значений первого и второго множителя, шину подачи двоичного кода значения модуля, шину вывода результата вычислений, причем шины подачи двоичных кодов значений первого и второго множителя подключены к входам позиционного умножителя, выход которого подключен ко вторым входам второго, третьего,..., k-го сумматоров, информационные выходы которых подключены ко второму, третьему, (, k-му информационным входам мультиплексора соответственно, выход которого является шиной вывода результата вычислений, шина подачи двоичного кода значения модуля подключена к первым входам третьего, четвертого, (, k-го умножителей на константу, выходы которых подключены ко входам третьего, четвертого, (, k-го инверторов соответственно, выходы второго, третьего, (, k-го инверторов подключены к третьим входам второго, третьего, (, k-го сумматоров соответственно, первые входы которых соединены с входом подачи логической единицы, введены устройство управления, два сумматора, два инвертора, три умножителя на константу, элемент И-НЕ, шифратор, вход синхронизации и вход подачи импульса «Пуск», при этом выход позиционного умножителя подключен ко вторым входам первого и (k+1)-го сумматоров, первые входы которых соединены с входом подачи логической единицы, информационный выход первого сумматора подключен к первому входу мультиплексора, шина подачи двоичного кода значения модуля подключена к первым входам первого, второго и (k+1)-го умножителей на константу, выходы первого и второго умножителей на константу подключены ко входам первого и второго инверторов соответственно, выход первого инвертора подключен к третьему входу первого сумматора, выходы переноса первого, второго, (, (k+1)-го сумматоров подключены ко входам элемента И-НЕ и к первому, второму, (, (k+1)-му входам шифратора соответственно, выход которого подключен к адресному входу

мультиплексора, выход элемента И-НЕ подключен к третьему входу устройства управления, первый вход которого соединен со входом синхронизации, второй - со входом подачи сигнала «Пуск», выход - подключен ко вторым входам всех умножителей на константу, устройство управления содержит счетчик, два элемента И, триггер, дифференцирующую цепь, три входа и один выход, при этом выходом устройства управления является выход счетчика синхровход которого соединен с выходом первого элемента И, первый вход которого соединен с первым входом устройства управления, второй с выходом триггера, вход установки единицы которого соединен с выходом второго элемента И, вход установки нуля с выходом дифференцирующей цепи, вход которой, как и второй вход второго элемента И, соединен с третьим входом устройства управления, первый вход второго элемента И соединен со вторым входом устройства управления.

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

Предлагаемое устройство функционирует по следующему алгоритму.

Представим результат позиционного умножения множителей n₁ и n ₂ (n₁,n₂=0,1, (,m-1) в виде n=m×i+r, где r - искомый остаток по модулю m,0r<m.

Если результат умножения n<m, то n - есть искомый результат.

Если результат умножения nm, то из n последовательно вычитается значение модуля m и разность сравнивается с m. Вычитание выполняется до тех пор, пока не выполнится условие r_j<m, где j - количество вычитаний значения модуля m из n, тогда r _j=r - есть искомый результат произведения n ₁·n₂=r(mod m).

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

которая и становится основной операцией двоичного сумматора, функционирующего по модулю 2^d, где d - разрядность сумматора.

Правило преобразования в дополнительный код:

где - представление числа А в дополнительном коде, q - основание системы счисления, abs(А) - абсолютная величина А.

Например, пусть на входы параллельно-последовательный умножителя по произвольному модулю поданы двоичные значения чисел n₁ =3₁₀=00011₂, n ₂=7₁₀=00111₂ модуля m=4₁₀=001002, мультиплексор имеет k=4 информационных входов.

В момент времени соответствующий началу преобразования на второй вход устройства управления поступит импульс «Пуск». На выходе позиционного умножителя 1 образуется значение n=n₁·n₂ =21₁₀=10101₂.

Результаты промежуточных вычислений предложенного устройства на первом такте вычислений представлены в таблице 1.

Таблица 1
№№ п/п	Выходы умножителей на константу	Выходы инверторов	Результат суммирования
				Выходы переноса сумматоров
1				1
2	=410=001002			1
3	=810=010002			1
4				1
5			-	1

Так как на выходе переноса всех сумматоров 3.1, 3.2, (, 3.5 сформировались сигналы логической единицы, то на умножителях на константу 5.1, 5.2, (, 5.5 формируется следующий набор чисел. Результаты промежуточных вычислений на втором такте представлены в таблице 2.

Таблица 2
№п/п	Выходы умножителей на константу	Выходы инверторов	Результат суммирования
				Выходы переноса сумматоров
1				1
2				1
3				0
4				0
5			-	0

Так как на выходе переноса сумматора 3.3 сформирован сигнал логического нуля, а на выходе переноса сумматора 3.2 сформирован сигнал логической единицы, то на выход устройства будет подано значение остатка сформированного на выходе сумматоре 3.2 - и действительно 1=21 (mod 4), r=n-m·j.

Предлагаемое устройство содержит позиционный умножитель 1, устройство управления 2, (k+1) сумматоров 3, (k+1) инверторов 4, (k+1) умножителей на константу 5, элемент И-НЕ 6, шифратор 7, мультиплексор 8, вход 9 подачи логической единицы, шины 10 и 11 подачи двоичного кода значений первого и второго множителей, шину 12 подачи двоичного кода значения модуля, вход 13 синхронизации, вход 14 подачи импульса «Пуск» и шину 15 вывода результата вычислений.

Шины 10 и 11 подачи двоичных кодов значений первого и второго множителей подключены к входам позиционного умножителя 1, выход которого подключен ко вторыми входами сумматоров 3.i, i=1,2,..., (k+1), информационные выходы которых подключены к первому, второму,..., k-му информационным входам мультиплексора 8 соответственно, выход которого является шиной 15 вывода результата вычислений. Шина 12 подачи двоичного кода значения модуля подключена к первым входам умножителей 5.i, i=1,2,..., (k+1) на константу, вторые входы которых соединены с выходом устройства управления, выходы подключены к входам инверторов 4.i, i=1,2, (, (k+1) соответственно, выходы которых подключены к третьим входам сумматоров 3.i, i=1,2,..., (k+1) соответственно, первые входы которых соединен с входом 9 подачи логической единицы. Выходы переносов сумматоров 3.i, i=1,2,..., (k+1) подключены к входам элемента И-НЕ 6 и к первому, второму,..., (k+1)-му входам шифратора 7 соответственно, выход которого подключен к адресному входу мультиплексора 8. Выход элемента И-НЕ 6 подключен к третьему входу устройства управления 2, первый вход которого соединен со входом 13 синхронизации, второй - со входом 14 подачи импульса «Пуск».

Устройство управления содержит элемент И 16, счетчик 17, элемент И 18, триггер 19, дифференцирующую цепь 20, входы 21, 22, 23 и выход 24.

Выходом 24 устройства управления является выход счетчика 17 синхровход которого соединен с выходом элемента И 18, первый вход которого соединен с входом 21 устройства управления, второй с выходом триггера 19, вход установки единицы которого соединен с выходом элемента И 16, вход установки нуля с выходом дифференцирующей цепи 20, вход которой, как и второй вход элемента И 16, соединен с входом 23 устройства управления, первый вход элемента И 16 соединен с входом 22 устройства управления.

Умножитель на константу 5 предназначен для формирования на 1-м такте числа:

Шифратор 7 предназначен для перекодировки кода _k, (=1,2,..., k), образующегося на выходах переноса сумматоров 3.i, i=1,2,..., (k+1) в порядковый номер подключаемого информационного выхода сумматора к соответствующему информационному входу мультиплексора 8 согласно таблицы 3.

Таблица 3

Дифференцирующую цепь 20 вырабатывает короткий единичный импульс при подачи на ее вход единичного потенциала с выхода элемента И-НЕ6.

В исходном состоянии счетчик 17 и триггер 19 обнулены, на вход 9 подано значение логической единицы. На входы 10 и 11 поданы коды значений множителей n ₁ и n₂, на вход 12 подан двоичный код значения модуля m умножения, на вход 13 и соответственно на вход 21 устройства управления подается последовательность синхроимпульсов, мультиплексор имеет k информационных входов.

На выходе позиционного умножителя 1 сформирован код обычного произведения n=n₁·n ₂, который поступает на вторые входы всех сумматоров. На выходе умножителей 5.i,i=1,2, (, (k+1) на константу на t-м такте образуются числа , i=1,2,..., (k+1) соответственно согласно формулы (1).

Сформированные числа через инверторы подаются на третьи входы сумматоров 3.i, i=1,2,..., (k+1) соответственно. При этом на выходе инверторов 4.i, i=1,2, (, (k+1) сформированы коды ,i=1,2, (, (k+1) соответственно. На информационных выходах сумматоров 3.i, i=1,2, (, (k+1) образуются суммы:

Если в сумматорах образуются суммы, для которых справедливо , то на выходах формирования переноса будут сформированы сигналы логической единицы, а в остальных сумматорах - нули. Сформированные значения на выходах переноса сумматоров поступают на входы элемента И-НЕ 6 и шифратора 7.

Результат выполнения логической операции с выхода элемента И-НЕ поступает на третий вход устройства управления 2. При этом сигнал логического нуля указывает на отсутствие искомого результата вычислений в текущем такте. В соответствии с формулой (1) вычисления будут продолжены до формирования сигнала логической единицы на выходе элемента И-НЕ 6.

Появление сигнала логического нуля на выходе переноса сумматора 3.i, i=1,2, (, (k+1) означает, что на выходе сумматора 3.i-1, i=1,2, (, (k+1) сформировано искомое значение остатка r от произведения чисел n₁ и n ₂ по модулю m.

С выхода шифратора 7 в соответствии с таблицей 3 на адресный вход мультиплексора 8 поступит код ((=1,2, (, k), обуславливающий подачу результата вычислений с выхода соответствующего сумматора на выход устройства.

Процесс умножения при этом считается законченным.

В момент времени соответствующий началу преобразования на входе 14 устройства и соответственно входе 25 устройства управления 2 поступит импульс «Пуск». При этом если результат произведения n=n ₁·n₂<m·i,i=1,2, (, (k+1) то на выходе элемента И-НЕ 6 и соответственно на втором входе элемента И 16 сформирован сигнал логического нуля, триггер 19 остается в нулевом состоянии.

Если n=n₁ ·n₂m·i,i=1,2, (, (k+1) то на выходе элемента И-НЕ 6 будет сформирован сигнал логического нуля, который поступит на первый вход элемента И 16 и обеспечит прохождение сигнала «Пуск» на вход установки единицы триггера 19 и установит его в единичное состояние. Тем самым, обеспечив прохождение синхроимпульса с входа 21 устройства управления на синхровход счетчика 17 обеспечив единичное увеличение его содержимого. С выхода счетчика 17 на выход устройства управления поступит код соответствующий номеру текущего такта вычислений, обеспечив формирование умножителями 5.i, i=1,2, (, (k+1) на константу следующего набора чисел соответственно, согласно формулы (1).

По сравнению с известными, предлагаемое устройство реализует параллельно-последовательный принцип функционирования. То есть требует для своей реализации в m_max (где m_max - максимальное значение модуля, l - количество циклов функционирования) меньше объема оборудования, за счет увеличения длительности функционирования в m_max/l раз.

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

1. Последовательно-параллельный умножитель по произвольному модулю, состоящий из позиционного умножителя, (k-1) сумматоров, (k-1) инверторов, (k-2) умножителей на константу и мультиплексора, входа подачи логической единицы, шин подачи двоичных кодов значений первого и второго множителей, шины подачи двоичного кода значения модуля, шины вывода результата вычислений, причем шины подачи двоичных кодов значений первого и второго множителей подключены к входам позиционного умножителя, выход которого подключен ко вторым входам второго, третьего, ..., k-го сумматоров, информационные выходы которых подключены ко второму, третьему, ..., k-му информационным входам мультиплексора соответственно, выход которого является шиной вывода результата вычислений, шина подачи двоичного кода модуля подключена к первым входам третьего, четвертого, ...,k-го умножителей на константу, выходы которых подключены ко входам третьего, четвертого, ..., 1 k-го инверторов соответственно, выходы второго, третьего, ..., k-го инверторов подключены ко третьим входам второго, третьего, ..., k-го сумматоров соответственно, первые входы которых соединены с входом подачи логической единицы, отличающийся тем, что, с целью сокращения аппаратурных затрат, введены устройство управления, два сумматора, два инвертора, три умножителя на константу, элемент И-НЕ, шифратор, вход синхронизации и вход подачи импульса «Пуск», при этом выход позиционного умножителя подключен ко вторым входам первого и (k+1)-го сумматоров, первые входы которых соединены с входом подачи логической единицы, информационный выход первого сумматора подключен к первому входу мультиплексора, шина подачи двоичного кода значения модуля подключена к первым входам первого, второго и (k+1)-го умножителей на константу, выходы первого и второго умножителей на константу подключены ко входам первого и второго инверторов соответственно, выход первого инвертора подключен к третьему входу первого сумматора, выходы переносов первого, второго, ..., (k+1)-го сумматоров подключены ко входам элемента И-НЕ и к первому, второму, ..., (k+1)-му входам шифратора соответственно, выход которого подключен к адресному входу мультиплексора, выход элемента И-НЕ подключен к третьему входу устройства управления, первый вход которого соединен со входом синхронизации, второй вход - со входом подачи сигнала «Пуск», выход подключен ко вторым входам всех умножителей на константу.

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