Устройство для умножения чисел по модулю

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

 

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

Известно устройство (аналог) (авт.св. СССР № 1571583, МКИ G06F 7/72, БИ № 22, 1990 г.), содержащее дешифраторы, группы элементов И, элементы ИЛИ, сумматор по модулю 2, элементы И, элементы НЕ, группы элементов ИЛИ, коммутатор, шифраторы. Недостаток устройства - невозможность выполнения модульной операции умножения.

Известно также устройство (аналог) (авт.св. СССР № 1689949, МКИ G06F 7/72, БИ № 41, 1991 г.), содержащее дешифраторы, элементы И и НЕ, элемент ИЛИ-НЕ, группы элементов ИЛИ, коммутатор, группы элементов И, шифратор. Недостаток устройства - невозможность выполнения модульной операции умножения.

Наиболее близким по технической сущности (прототипом к предлагаемому изобретению) является устройство (патент РФ № 2188448, МКИ G06F 7/72, БИ № 24, 2002 г.), содержащее дешифраторы, шифратор, управляемые фазовращатели, генератор гармонического сигнала, фазовращатели на фиксированное значение фазы и измеритель фазы гармонического сигнала.

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

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

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

Технический результат достигается тем, что в устройство, содержащее l дешифраторов (l=]log2[, где р - модуль устройства), l управляемых фазовращателей, генератор гармонического сигнала, измеритель фазы гармонического сигнала, (р-1) фазовращателей на фиксированные значения фазы и шифратор, причем выход генератора гармонического сигнала соединен с первым входом первого управляемого фазовращателя, выход i-го управляемого фазовращателя - с первым входом (i+1)-го управляемого фазовращателя, выход l-го управляемого фазовращателя - с первым входом измерителя фазы гармонического сигнала, второй вход которого соединен с выходом генератора гармонического сигнала, вход измерителя фазы гармонического сигнала соединен с выходом генератора гармонического сигнала через фазовращатель на фиксированное значение фазы, равное , при этом вход (p+2) измерителя фазы гармонического сигнала является тактовым входом устройства, выход измерителя фазы гармонического сигнала соединен со входом шифратора, выход которого является выходом устройства, а выходы дешифраторов подключены ко вторым входам соответствующих управляемых фазовращателей, введены (l-1) блоков умножения на константу по модулю и l блоков элементов И, причем вход первого сомножителя устройства соединен со входами блоков умножения на константу по модулю и вторым входом l-го блока элементов И, входы разрядов второго сомножителя соединены с первыми входами соответствующих блоков элементов И, выходы которых подключены к входам соответствующих дешифраторов, а выходы блоков умножения на константу по модулю соединены со вторыми входами соответствующих блоков элементов И.

Сущность изобретения состоит в следующем: пусть А - первый операнд, В - второй и необходимо провести операцию модульного умножения |А·В|p, где р - модуль. Представим число В в виде B=Sl-1·2l-1+Sl-2·2l-2+...+S0·20(l=]log2p[). Тогда (Si=0 либо 1, т.е. соответствует значению соответствующего разряда в двоичном представлении числа В). Произведение вида |А·2i|p можно получить при помощи блока умножения на константу по модулю (авт.св. СССР № 1617439, МКИ G06F 7/72, 1990 г.). Следовательно, для получения результата операции |А·В|p необходимо произвести последовательное сложение чисел вида |А·2i|p для тех разрядов двоичного представления числа В, Si которых равны 1. Немодульная операция - нахождение остатка по модулю от числа возможна, если операнд А равен единице, тогда на выходе устройства имеем результат операции |В|p при 2>р. Дополнительной возможностью заявляемого устройства является то, что при соответствующей коммутации его можно использовать для сложения ]log2p[ чисел по модулю.

На фиг.1 представлена структурная схема предлагаемого устройства, где: 1 - генератор гармонического сигнала, 21÷2l (l=]log2p[) - управляемые фазовращатели, 3 - измеритель фазы гармонического сигнала, 4 - группа фазовращателей на фиксированное значение фазы , 5 - шифратор, 6 - выход устройства, 7 - вход первого сомножителя, 81÷8(l-1) - блоки умножения на константу по модулю, 91÷9l - блоки элементов И, 101÷10(l-1) - входы разрядов второго сомножителя, 111÷11l - дешифраторы. Выход генератора гармонического сигнала 1 соединен с первым входом первого управляемого фазовращателя 21, выход управляемого фазовращателя 2i - с первым входом управляемого фазовращателя 2(i+1) (; где l=]log2p[, а р - модуль устройства), выход управляемого фазовращателя 2l - с первым входом измерителя фазы гармонического сигнала 3, второй вход которого соединен с выходом генератора 1 гармонического сигнала, вход измерителя фазы гармонического сигнала 3 соединен с выходом генератора 1 гармонического сигнала через фазовращатель 4(q-2) на фиксированное значение фазы, равное , при этом вход (р+2) измерителя фазы гармонического сигнала 3 является тактовым входом устройства, выход измерителя фазы гармонического сигнала 3 соединен со входом шифратора 5, выход которого является выходом 6 устройства, вход первого сомножителя 7 устройства соединен со входами блоков умножения 8i, на константу по модулю и вторым входом l-го блока 9l, элементов И, входы разрядов 10j второго сомножителя соединены с первыми входами блоков 9m элементов И соответственно, выходы которых подключены к входам соответствующих дешифраторов 11m, выходы блоков умножения на константу по модулю 8i соединены со вторыми входами соответствующих блоков 9i элементов И, вторые входы управляемых фазовращателей 2m, соединены с выходами соответствующих дешифраторов 11m.

На фиг.2 представлена структурная схема измерителя фазы гармонического сигнала 3, где Bx1÷Вх(p+2) - входы измерителя фазы, 121÷12p - аналоговые перемножители, 131÷13p - интеграторы, 14 - решающее устройство.

На фиг.3 представлена структурная схема управляемого фазовращателя 2t, где Вх1 и Вх2 - входы управляемого фазовращателя, 151÷15p - коммутаторы гармонического сигнала, 16k - линии задержки на (ω - несущая частота гармонического сигнала).

Рассмотрим работу устройства. Первый сомножитель А поступает на входы блоков 8i умножения на константу по модулю, а также на второй вход блока 9l элементов И. На выходах блоков 8i умножения на константу по модулю получаем произведения вида , а на втором входе блока 9l элементов И имеем . Данные числа будут представлены в двоичном коде. На входы разрядов 10j второго сомножителя поступает второй операнд В. С выходов блоков 9l элементов И на входы дешифраторов 11m поступают числа в двоичном коде вида для тех разрядов операнда В, которые не равны нулю. В противном случае на вход соответствующего дешифратора 11 поступит двоичный позиционный код числа ноль.

После их преобразования в дешифраторах 11m, в унитарные коды числа поступают на Вх2 соответствующих управляемых фазовращателей 21÷2l. В соответствии со значениями унитарных кодов чисел в управляемых фазовращателях 21÷2l путем подключения коммутаторами 151÷15p соответствующих линий задержки 161÷16p-1 устанавливаются набеги фазы, равные . После прохождения гармонического сигнала с выхода генератора 1 гармонического сигнала через l фазовращателей 2i суммарный набег фазы этого сигнала будет равен .

Пример. Пусть p=5, А=4, В=3.

Двоичный код числа В равен 0112. Первый сомножитель поступает на вход блока 82 умножения на константу по модулю, на выходе которого получим число , на выходе блока 81 умножения на константу по модулю будет число , а на втором входе блока 93 элементов И - . На входах разрядов 102, 101 и 100 при B=3 будут соответствующие значения S2=0, S1=1 и S0=1. Следовательно после преобразования двоичных позиционных кодов , и в дешифраторах 111÷113 устройства в унитарные коды в управляемых фазовращателях 21÷23 коммутаторами 151÷155 подключаются соответствующие линии задержки 161÷163 на время, равное , и .

После прохождения гармонического сигнала через управляемые фазовращатели 21÷23 фаза этого сигнала на выходе управляемого фазовращателя 23 будет равна , а исходя из периодичности гармонической функции . Таким образом, суммарная фаза гармонического сигнала прямо пропорциональна числу 2. Напряжение на выходе интегратора 13 в канале измерителя фазы будет максимальным для второго номера канала. Следовательно, на выход 6 устройства после шифратора 5 поступит число 2 в двоичном коде.

Устройство для умножения чисел по модулю, содержащее l дешифраторов (l=[log2p], где р - модуль устройства), l управляемых фазовращателей, генератор гармонического сигнала, измеритель фазы гармонического сигнала, (р-1) фазовращателей на фиксированные значения фазы и шифратор, причем выход генератора гармонического сигнала соединен с первым входом первого управляемого фазовращателя, выход i-го управляемого фазовращателя - с первым входом (i+1)-го управляемого фазовращателя (i=1, l-1), выход l-го управляемого фазовращателя - со входом 1 измерителя фазы гармонического сигнала, вход 2 которого соединен с выходом генератора гармонического сигнала, вход измерителя фазы гармонического сигнала соединен с выходом генератора гармонического сигнала через фазовращатель на фиксированное значение фазы, равное , при этом вход (р+2) измерителя фазы гармонического сигнала является тактовым входом устройства, выход измерителя фазы гармонического сигнала соединен со входом шифратора, выход которого является выходом устройства, а выходы дешифраторов подключены ко вторым входам соответствующих управляемых фазовращателей, отличающееся тем, что в него введены (l-1) блоков умножения на константу по модулю и l блоков элементов И, причем вход первого сомножителя устройства соединен со входами блоков умножения на константу по модулю и вторым входом l-го блока элементов И, входы разрядов второго сомножителя соединены с первыми входами соответствующих блоков элементов И, выходы которых подключены к входам соответствующих дешифраторов, а выходы блоков умножения на константу по модулю соединены со вторыми входами соответствующих блоков элементов И.



 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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