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

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

Иллюстрации

Показать все

Реферат

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

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

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

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

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

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

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

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

Сущность изобретения состоит в следующем: пусть А - первый операнд, В - второй и необходимо провести операцию модульного умножения , где р - модуль. Представим число В в виде В=S_b-n·2^b-n+...+S_b-1·2^b-1+S₀·2⁰. Тогда (S_i=0 либо 1, т.е. равно значению соответствующего разряда в двоичном представлении числа В).

Произведение вида можно получить при помощи блока умножения на константу по модулю (авт. св. СССР №1617439, МКИ G06F 7/72, БИ №48, 1990 г.). Следовательно, для получения результата операции необходимо произвести последовательное сложение чисел вида для тех разрядов двоичного представления числа В, S_i которых равны 1.

Сокращение количества используемого оборудования может быть достигнуто за счет использования свойства симметрии таблицы Кэли относительно вертикали и горизонтали, проходящих между величинами (p-1)/2 и (p+1)/2. Если воспользоваться понятием индекса операнда: то для операции модульного умножения в силу вертикальной и горизонтальной симметрии таблицы Кэли справедливы следующие соотношения: где α'=р-α; β'=р-β.

Например. Пусть p=5, А=4, 5=3. Так как (p+1)/2≤A≤(p-1) и (р+1)/2≤В≤(р-1), то γ_α=γ_β=1, следовательно, воспользуемся соотношением , где α', β' - разряды операндов А и В, представленных в унитарном коде. Для сокращения оборудования в соответствии с таблицей 2 необходимо объединить разряды операнда А и разряды операнда В, так чтобы α'=р-А и β'=р-В.

Пусть р=5, А=2, В=2. Так как 0<A≤(p-1)/2 и 0<В≤(р-1)/2, то γ_α=γ_β=0, следовательно, воспользуемся соотношением , где α, β-разряды операндов А и В, представленных в унитарном коде.

Таблица Кэли для умножения по модулю 5

Таблица 1
α	β
0	1	2	3	4
0	0	0	0	0	0
1	0	1	2	3	4
2	0	2	4	1	3
3	0	3	1	4	2
4	0	4	3	2	1

Таблица Кэли для умножения по модулю 5 с учетом симметрии относительно вертикали и горизонтали

Таблица 2
α	β
0	1	2
0	0	0	0
1	0	1	2
2	0	2	4

На фиг.1 представлена структурная схема предлагаемого устройства, где: 1 - генератор гармонического сигнала, 2₁÷2_l - управляемые фазовращатели, 3 - измеритель фазы гармонического сигнала, 4 - группа фазовращателей на фиксированное значение фазы , 5 - первый шифратор, - входы первого сомножителя, 7 - первый дешифратор, 8 - первый элемент ИЛИ, 9₁÷9_(p-1)/2 - элементы ИЛИ первой группы, 10 - второй элемент ИЛИ, 11 - второй шифратор, 12₁÷12_(l-1) - блоки умножения на константу по модулю, 13₁÷13_l - блоки элементов И, - входы разрядов второго сомножителя, 15 - второй дешифратор, 16₁÷16_(p-1)/2 - элементы ИЛИ второй группы, 17 - третий элемент ИЛИ, 18 - третий шифратор, 19₁÷19_l - дешифраторы первой группы, 20 - сумматор по модулю два, 21 - первый блок элементов ИЛИ, 22 - второй блок элементов ИЛИ, 23 - преобразователь кода числа х в р-х, 24 - третий блок элементов ИЛИ, 25 - выход устройства.

Выход генератора гармонического сигнала 1 соединен с первым входом первого управляемого фазовращателя 2₁; выход управляемого фазовращателя 2_i - с первым входом управляемого фазовращателя 2_(i+1), выход управляемого фазовращателя 2_l - с первым входом измерителя фазы гармонического сигнала 3, вход q измерителя фазы гармонического сигнала 3 соединен с выходом генератора 1 гармонического сигнала через фазовращатель 4_(q-1) на фиксированное значение фазы, равное , при этом вход (p+1) измерителя фазы гармонического сигнала 3 является тактовым входом устройства, выход измерителя фазы гармонического сигнала 3 соединен со входом первого шифратора 5, входы разрядов 6_j первого сомножителя устройства соединены с соответствующими входами первого дешифратора 7, выход нулевого разряда которого соединен со вторым входом первого элемента 8 ИЛИ, а i-е и (p-i)-е выходы первого дешифратора подключаются ко входам соответствующих элементов 9_i ИЛИ первой группы, при этом (p-i)-e выходы первого дешифратора также соединены со входами второго элемента 10 ИЛИ, выходы элементов 9_i ИЛИ первой группы подключены к соответствующим входам второго шифратора 11, выходы которого подключаются ко входам блоков умножения 12_i на константу по модулю и вторым входом l-го блока 13, элементов И, входы разрядов 14_j второго сомножителя соединены с соответствующими входами второго дешифратора 15, выход нулевого разряда которого соединен с первым входом первого элемента 8 ИЛИ, а i-е и (p-i)-е выходы второго дешифратора подключаются ко входам соответствующих элементов 16_i ИЛИ второй группы, при этом (p-i)-е выходы второго дешифратора также соединены со входами третьего элемента 17 ИЛИ, выходы элементов 16_i ИЛИ второй группы соединены с соответствующими входами третьего шифратора 18, выходы которого подключаются к первым входам блоков 13_m элементов И соответственно, выходы которых подключены к входам соответствующих дешифраторов 19_m, выходы блоков умножения на константу по модулю 12_i соединены со вторыми входами соответствующих блоков 13_m элементов И, вторые входы управляемых фазовращателей 2_m соединены с выходами соответствующих дешифраторов 19_m, выход первого элемента 8 ИЛИ соединен со входом нулевого разряда первого шифратора 5, выход которого подключен ко вторым входам блоков 21, 22 элементов ИЛИ, выходы элементов 10, 17 ИЛИ соединены со входами сумматора по модулю два 20, инверсионный выход которого подключен к первому входу первого блока 21 элементов ИЛИ, а прямой выход сумматора по модулю два подключен к первому входу второго блока 22 элементов ИЛИ, выход которого соединен со вторым входом третьего блока 24 элементов ИЛИ, выход которого является выходом устройства 25, выход первого блока элементов ИЛИ соединен через преобразователь кода 23 числа х в р-х с первым входом третьего блока элементов ИЛИ.

На фиг.2 представлена структурная схема измерителя фазы гармонического сигнала 3, где Bx₁÷Вх_p+1 - входы измерителя фазы, 26₁÷26_p-1 - аналоговые перемножители, 27₁÷27_p-1 - интеграторы, 28 - решающее устройство.

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

Рассмотрим работу устройства. На входы разрядов 6_j первого сомножителя поступает первый операнд А. После преобразования в первом дешифраторе 7 в унитарный код нулевой разряд числа подключается ко второму входу первого элемента 8 ИЛИ, a i-е и (p-i)-е разряды числа для объединения поступают на входы соответствующих элементов 9_i ИЛИ первой группы, (p-i)-е разряды числа также поступают на входы второго элемента 10 ИЛИ для проведения коррекции результата. После преобразования в шифраторе 11 в двоичный код числа поступают на входы блоков 12_i умножения на константу по модулю, а также на второй вход блока 13_l элементов И. На выходах блоков 12_i умножения на константу по модулю получаем произведения вида , а на втором входе блока 13_l элементов И имеем . Данные числа будут представлены в двоичном коде. На входы разрядов 14_j второго сомножителя поступает второй операнд В. После преобразования во втором дешифраторе 15 в унитарный код нулевой разряд числа подключается к первому входу первого элемента 8 ИЛИ, а i-е и (p-i)-е разряды числа для объединения поступают на входы соответствующих элементов 16_i ИЛИ второй группы, (p-i)-е разряды числа также поступают на входы третьего элемента 17 ИЛИ для проведения коррекции результата. После преобразования в шифраторе 18 в двоичный код числа поступают на первые входы блоков 13_l элементов И. С выходов блоков 13_l элементов И на входы дешифраторов 19_m поступают числа в двоичном коде вида для тех разрядов операнда В, которые не равны нулю. В противном случае на вход соответствующего дешифратора 19_m поступит двоичный позиционный код числа ноль. После их преобразования в дешифраторах 19_m в унитарные коды числа поступают на входы соответствующих управляемых фазовращателей 2₁÷2_l. В соответствии со значениями унитарных кодов чисел в управляемых фазовращателях 2₁÷2_l путем подключения коммутаторами 29₁÷29_р соответствующих линий задержки 30₁÷30_p-1 устанавливаются набеги фазы, равные . После прохождения гармонического сигнала с выхода генератора 1 гармонического сигнала через l фазовращателей 2 суммарный набег фазы этого сигнала будет равен .

Для проведения коррекции результата сигналы с элементов 10 и 17 ИЛИ поступают на входы сумматора по модулю два 20. Если для сигналов на входах сумматора γ_A=γ_В, то с прямого выхода сумматора результат поступает на выход устройства 25. Если γ_A≠γ_B, то с инверсного выхода сумматора результат поступает на преобразователь кода 23 числа х в р-х, на выходе которого получаем при γ_α=0; γ_β=1 или при γ_α=1; γ_β=0.

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

На входах разрядов 6₂, 6₁ и 6₀ при A=4 будут соответствующие значения S₂=1, S₁=0 и S₀=0, которые поступают на дешифратор 7, на выходе которого разряды i₁ и i₄ поступают на первый элемент 9₁ ИЛИ первой группы, а разряды i₂ и i₃ поступают на второй элемент 9₂ ИЛИ первой группы и на входе шифратора 11 получаем два разряда, равные соответственно i₁=1 и i₂=0. Следовательно, на втором входе блока 13₁ элементов И получим число . На входах разрядов 14₂, 14₁ и 14₀ при B=3 будут соответствующие значения S₂=0, S₁=1 и S₀=1, которые поступают на дешифратор 15, на выходе которого разряды i₁ и i₄ поступают на первый элемент 16₁ ИЛИ второй группы, а разряды i₂ и i₃ поступают на второй элемент 16₂ ИЛИ второй группы и на входе шифратора 18 получаем два разряда, равные соответственно i₁=0 и i₂=1. Следовательно, после преобразования двоичного позиционного кода в дешифраторе 19 устройства в унитарный код в управляемом фазовращателе 2 коммутаторами 29₁÷29₅ подключаются соответствующие линии задержки 30₁÷30₄ на время, равное .

После прохождения гармонического сигнала через управляемый фазовращатель 2 фаза этого сигнала будет равна . Таким образом, суммарная фаза гармонического сигнала прямо пропорциональна числу 2. Напряжение на выходе интегратора 27 в канале измерителя фазы будет максимальным для второго номера канала. Так как для сигналов, поступающих на сумматор по модулю два 20 γ_A=γ_B=1, то коррекция результата отсутствует и на выход 25 устройства поступит число 2 в двоичном коде.

Пусть p=5, А=2, B=2.

На входах разрядов 6₂, 6₁ и 6₀ при А=2 будут соответствующие значения S₂=0, S₁=1 и S₀=0, которые поступают на дешифратор 7, на выходе которого разряды i₁ и i₄ поступают на первый элемент 9₁ ИЛИ первой группы, а разряды i₂ и i₃ поступают на второй элемент 9₂ ИЛИ первой группы и на входе шифратора 11 получаем два разряда, равные соответственно i₁=0 и i₂=1. Следовательно, на втором входе блока 13₁ элементов И получим число . На входах разрядов 14₂, 14₁ и 14₀ при В=2 будут соответствующие значения S₂=0, S₁=1 и S₀=0, которые поступают на дешифратор 15, на выходе которого разряды i₁ и i₄ поступают на первый элемент 16₁ ИЛИ второй группы, а разряды i₂ и i₃ поступают на второй элемент 16₂ ИЛИ второй группы и на входе шифратора 18 получаем два разряда, равные соответственно i₁=0 и i₂=1. Следовательно, после преобразования двоичного позиционного кода в дешифраторе 19 устройства в унитарный код в управляемом фазовращателе 2 коммутаторами 29₁÷29₅ подключаются соответствующие линии задержки 30₁÷30₄ на время, равное .

После прохождения гармонического сигнала через управляемый фазовращатель 2 фаза этого сигнала будет равна . Таким образом, суммарная фаза гармонического сигнала прямо пропорциональна числу 4. Напряжение на выходе интегратора 27 в канале измерителя фазы будет максимальным для четвертого номера канала. Так как для сигналов, поступающих на сумматор по модулю два 20 γ_A=γ_B=0, то коррекция результата отсутствует и на выход 25 устройства поступит число 4 в двоичном коде.

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