УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ ЧИСЕЛ ПО МОДУЛЮ Российский патент 2007 года по МПК G06F7/523 G06F7/72 

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

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

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

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

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

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

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

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

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

На фиг.1 представлена структурная схема предлагаемого устройства, где: 1 - генератор гармонического сигнала, 2₁÷2_l (l=]log₂p[) - управляемые фазовращатели, 3 - измеритель фазы гармонического сигнала, 4 - группа фазовращателей на фиксированное значение фазы , 5 - шифратор, 6 - выход устройства, 7 - вход первого сомножителя, 8₁÷8_(l-1) - блоки умножения на константу по модулю, 9₁÷9_l - блоки элементов И, 10₁÷10_(l-1) - входы разрядов второго сомножителя, 11₁÷11_l - дешифраторы. Выход генератора гармонического сигнала 1 соединен с первым входом первого управляемого фазовращателя 2₁, выход управляемого фазовращателя 2_i - с первым входом управляемого фазовращателя 2_(i+1) (; где l=]log₂p[, а р - модуль устройства), выход управляемого фазовращателя 2_l - с первым входом измерителя фазы гармонического сигнала 3, второй вход которого соединен с выходом генератора 1 гармонического сигнала, вход измерителя фазы гармонического сигнала 3 соединен с выходом генератора 1 гармонического сигнала через фазовращатель 4_(q-2) на фиксированное значение фазы, равное , при этом вход (р+2) измерителя фазы гармонического сигнала 3 является тактовым входом устройства, выход измерителя фазы гармонического сигнала 3 соединен со входом шифратора 5, выход которого является выходом 6 устройства, вход первого сомножителя 7 устройства соединен со входами блоков умножения 8_i, на константу по модулю и вторым входом l-го блока 9_l, элементов И, входы разрядов 10_j второго сомножителя соединены с первыми входами блоков 9_m элементов И соответственно, выходы которых подключены к входам соответствующих дешифраторов 11_m, выходы блоков умножения на константу по модулю 8_i соединены со вторыми входами соответствующих блоков 9_i элементов И, вторые входы управляемых фазовращателей 2_m, соединены с выходами соответствующих дешифраторов 11_m.

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

На фиг.3 представлена структурная схема управляемого фазовращателя 2_t, где Вх₁ и Вх₂ - входы управляемого фазовращателя, 15₁÷15_p - коммутаторы гармонического сигнала, 16_k - линии задержки на (ω - несущая частота гармонического сигнала).

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

После их преобразования в дешифраторах 11_m, в унитарные коды числа поступают на Вх₂ соответствующих управляемых фазовращателей 2₁÷2_l. В соответствии со значениями унитарных кодов чисел в управляемых фазовращателях 2₁÷2_l путем подключения коммутаторами 15₁÷15_p соответствующих линий задержки 16₁÷16_p-1 устанавливаются набеги фазы, равные . После прохождения гармонического сигнала с выхода генератора 1 гармонического сигнала через l фазовращателей 2_i суммарный набег фазы этого сигнала будет равен .

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

Двоичный код числа В равен 011₂. Первый сомножитель поступает на вход блока 8₂ умножения на константу по модулю, на выходе которого получим число , на выходе блока 8₁ умножения на константу по модулю будет число , а на втором входе блока 9₃ элементов И - . На входах разрядов 10₂, 10₁ и 10₀ при B=3 будут соответствующие значения S₂=0, S₁=1 и S₀=1. Следовательно после преобразования двоичных позиционных кодов , и в дешифраторах 11₁÷11₃ устройства в унитарные коды в управляемых фазовращателях 2₁÷2₃ коммутаторами 15₁÷15₅ подключаются соответствующие линии задержки 16₁÷16₃ на время, равное , и .

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

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

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