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

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

Иллюстрации

Показать все

Реферат

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

Известно устройство (аналог) (авт.св. СССР № 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 в двоичном коде.

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