Умножитель на два по модулю

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

 

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

Известен умножитель на два по модулю, содержащий два сумматора, элементы ИЛИ-НЕ и элементы ИЛИ с соответствующими связями (см. Пухальский Т.И., Новосельцева Т.Я. Проектирование дискретных устройств на интегральных микросхемах. Справочник. М.: Радио и связь, 1990, с.205, рис.3.131).

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

Наиболее близким по технической сущности к заявляемому изобретению является умножитель на два по модулю, содержащий сумматор и мультиплексор (см. патент РФ №2015537, кл. G06F 7/49, 30.06.1994).

Недостатком данного устройства являются его ограниченные функциональные возможности, а именно ограниченный диапазон значений входных чисел х (0<х≤р-1, где р - значение модуля, по которому производится вычисление).

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

Известно, что любое число х, представленное в двоичной форме, можно умножить на два путем сдвига всех разрядов числа на один в сторону старшего с записью значения "0" в младший разряд. При проведении вычислений по модулю р значение а=2х сравнивается со значением модуля. Если полученное значение а≥р, то из а вычитается значение модуля р, а полученное в результате значение а1=а-р вновь сравнивается со значением р. Если и в этом случае значение а1≥р, то из а1 вновь вычитается значение р, а полученное в результате значение а21-р сравнивается со значением р. Данные операции проводятся до тех пор, пока значение an, полученное на n-м шаге вычислений, не станет меньше значения модуля р. В этом случае значение an является результатом умножения числа х на два по модулю р. Если уже на первом шаге входное значение а<р, значение а остается без изменений и является результатом умножения числа х на два по модулю.

Предлагаемый умножитель на два по модулю осуществляет данный метод путем параллельного выполнения n операций (где n - размер умножителя, определяемый количеством входящих в его состав сумматоров), в ходе i-й операции значение а=2х сравнивается со значением i×p путем вычисления разности а-i×p, где i=1, ..., n. Как только при выполнении i-й операции значение полученной разности станет отрицательным, результатом умножения числа х на два по модулю будет являться значение разности, полученное в результате (i-1)-й операции. Диапазон значений входных чисел х для данного умножителя определяется размером умножителя и находится в пределах 0<x≤(n/2)p-1.

На чертеже представлена схема умножителя на два по модулю.

Умножитель на два по модулю содержит n сумматоров 1, n инверторов 2, (n-1) умножителей 3 и мультиплексор 4. Вход 5 служит для подачи двоичного кода числа х, вход 6 служит для подачи двоичного кода модуля р. Выходы переноса сумматоров 1 подключены к управляющим входам мультиплексора 4, информационные выходы сумматоров 1 подключены к информационным входам мультиплексора 4. Выход 7 является выходом устройства.

Умножитель на два по модулю работает следующим образом.

На вход 5 подается код числа из диапазона 0<х≤(n/2)р-1, где х - умножаемое число, р - модуль, n - размер умножителя, определяемый количеством сумматоров 1. Данный код поступает на первые входы сумматоров 1 и на первый информационный вход мультиплексора 4. Со входа 6 код модуля р подается на входы умножителей 3 и на вход первого инвертора 2, причем значение модуля в k-м умножителе умножается на значение i=(k+1), где k=1, ..., n-1. С выхода k-го умножителя 3 код значения i×p поступает на вход (k+1)-го инвертора 2. В j-м инверторе 2 поступающий на его вход код переводится в инверсный код, который подается на второй вход j-го сумматора 1, где j=1, ..., n. Таким образом, на второй вход каждого сумматора 1 поступает инверсный код значения i×p, где i - номер сумматора. На третий вход каждого сумматора 1 поступает код числа "1", служащий для перевода инверсного кода модуля в дополнительный код.

В общем виде сумматор 1 осуществляет операцию, описываемую выражением: , где с - результат суммирования, х - число, умножаемое на два по модулю, i - номер сумматора, р - модуль. Старший разряд сформированного значения с поступает на выход переноса сумматора 1, остальные разряды представляют разность 2х-i×p и поступают на информационный выход сумматора 1.

До тех пор, пока значение 2х превышает значение i×p, на выходе переноса i-го сумматора 1 будет формироваться "1", которая будет поступать на i-й управляющий вход мультиплексора 4. При превышении значением i×p значения 2х на выходе переноса i-го сумматора 1 сформируется "0". При поступлении на i-й управляющий вход мультиплексора 4 символа "0" с выхода переноса i-го сумматора 1 мультиплексор 4 проключит на выход 7 информационный вход, на который подается значение с информационного выхода (i-1)-го сумматора 1. Данное значение будет представлять результат умножения числа х на два по модулю р.

Рассмотрим работу умножителя на примере.

Пусть x=710=001112, 2х=1410=011102, p=410=001002, Как показано выше, i-й сумматор 1 формирует значение , поэтому для второго сумматора i×p=2×p=810=010002, для третьего сумматора i×p=3×p=1210=011002, для четвертого сумматора i×p=4×p=1610=100002, Тогда первый сумматор 1 сформирует значение c1=011102+110112+1=1010102, второй c2=011102+101112+1=1001102, третий - c3=011102+100112+1=1000102, четвертый - c4=011102+011112+1=0111102.

Как видно из примера, на выходах переноса первых трех сумматоров 1 сформировано значение "1", на выходе же четвертого сумматора 1 сформировано значение "0", поэтому на выход 7 мультиплексора поступит значение с информационного выхода третьего сумматора 1, равное 000102=210. Так как (7×2)(mod 4)=2, то правильность работы устройства очевидна.

Пусть теперь х=310=00112, 2x=610=01102, p=710=01112, В этом случае первый сумматор 1 сформирует значение c1=01102+10002+1=011112. Так как уже первый сумматор на выходе переноса формирует символ "0", на выход 7 мультиплексора поступит значение со входа 5 умножителя, то есть 2х=01102=610=(3×2)(mod 7).

Умножитель на два по модулю, состоящий из сумматора и мультиплексора, отличающийся тем, что в него дополнительно введены (n-1) сумматоров, (n-1) умножителей и n инверторов, причем вход записи двоичного кода числа, сдвинутого на один разряд в сторону старшего, подключен к первому информационному входу мультиплексора и первым входам всех сумматоров, выход переноса i-го сумматора подключен к i-му управляющему входу мультиплексора, информационный выход i-го сумматора подключен к (i+1)-му информационному входу мультиплексора, где i=1, ..., n, вход записи двоичного кода модуля подключен к входу первого инвертора и к входу каждого умножителя, j-й умножитель производит умножение значения на своем входе на величину (j+1), где j=1, ..., n-1, выход j-го умножителя подключен к входу (j+1)-го инвертора, выход i-го инвертора подключен ко второму входу i-го сумматора, к третьему входу каждого сумматора подключен вход записи логической единицы, выход мультиплексора является выходом умножителя.



 

Похожие патенты:

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

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

Изобретение относится к вычислительной техники и, в частности, к модулярным нейрокомпьютерным средствам и предназначено для выполнения операций округления и масштабирования над числами, представленными в системе остаточных классах (СОК).

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

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

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

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

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

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

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

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

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

Изобретение относится к способу инициализации чип-карты. .

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

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

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

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

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

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

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

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