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

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

 

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

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

Известно устройство (аналог) (патент РФ №2157560, МКИ G 06 F 7/72, 7/49; Б.И. №28, 2000 г.), содержащее шифраторы, блоки элементов И, мультиплексоры, табличные вычислители, регистры, преобразователи кода, блоки умножения на константу по модулю, квадраторы по модулю, блоки деления на четыре по модулю. Недостаток устройства - большое количество используемого оборудования.

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

Недостаток прототипа - большое количество используемого оборудования вследствие того, что оно прямо пропорционально модулю устройства р.

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

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

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

Сущность изобретения состоит в замене операции на операции

(p=р₁·р₂ - модуль операции, p₁ - первый подмодуль, р₂ - второй подмодуль) с последующим преобразованием промежуточных сумм в результат операции по модулю р.

Исходя из минимизации количества используемого оборудования, целесообразно выбирать p₁≈p₂, т.е. . Рассмотрим реализацию основных узлов устройства при p₁=5, р₂=7, т.е. р=р₁·р₂=35. Преобразователи 8₁÷8_N двоичного кода числа реализуют операцию A_i mod 5, а преобразователи 9₁÷9_N - A_i mod 7. Они могут быть выполнены, например, на программируемых логических матрицах. Табличный вычислитель 13 для p₁=5 и р₂=7 реализует следующую таблицу.

Таблица
p1	p2
0	1	2	3	4	5	6
0	0	15	30	10	25	5	20
1	21	1	16	31	11	26	6
2	7	22	2	17	32	12	27
3	28	8	23	3	18	33	13
4	14	29	9	24	4	19	34

Для р=35 в прототипе необходимо иметь (р-1)=34 фазовращателя на фиксированные значения фазы, тогда как в предлагаемом устройстве (p₁-1)+(р₂-1)=4+6=10. Хотя реализация устройства требует двойного количества управляемых фазовращателей и измерителей фазы гармонического сигнала, однако, в прототипе они имеют р=35 - входов, а в заявляемом устройстве всего лишь 5 и 7, т.е. суммарное количество элементов для реализации этих узлов существенно снизится.

Ввиду того, что операции сложения по первому p₁ и второму р₂ подмодулям для N чисел производятся одновременно, быстродействие устройства отличается от прототипа только на два такта, необходимых для получения в табличном вычислителе 13 результата операции по модулю р.

На фиг.1 представлена структурная схема предлагаемого устройства, где: 1 - генератор гармонического сигнала, 2₁÷2_N - первая группа управляемых фазовращателей, 3 - первый измеритель фазы гармонического сигнала, 4 - первая группа фазовращателей на фиксированное значение фазы, 5 - шифратор, 6 - выход устройства, 7₁÷7_N - входы устройства, 8₁÷8_N - преобразователи двоичного кода в унитарный код по первому подмодулю, 9₁÷9_N - преобразователи двоичного кода в унитарный код по второму подмодулю, 10₁÷10_N - вторая группа управляемых фазовращателей, 11 - второй измеритель фазы гармонического сигнала, 12 - вторая группа фазовращателей на фиксированное значение фазы, 13 - табличный вычислитель.

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

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

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

Рассмотрим работу устройства. На N входов 7₁÷7_N устройства поступают двоичные коды N чисел . Затем с выходов преобразователей 8₁÷8_N двоичного кода числа в унитарный код по первому по первому подмодулю числа (A_i)mod p₁ в унитарном коде поступают на Вх₂ соответствующих управляемых фазовращателей 2₁÷2_N первой группы. В соответствии со значениями унитарных кодов чисел (A_i)mod p₁ в управляемых фазовращателях 2₁÷2_N первой группы путем подключения коммутаторами соответствующих линий задержки устанавливаются набеги фазы, равные . После прохождения гармонического сигнала с выхода генератора 1 гармонического сигнала через N управляемых фазовращателей 2₁÷2_N первой группы на выходе фазовращателя 2_N суммарный набег фазы этого сигнала будет равен .

Ввиду того, что двоичные числа А_i поступают одновременно на входы преобразователей 9₁÷9_N двоичного кода числа в унитарный код по второму подмодулю, с их выходов числа (A_i)mod p₂ в унитарном коде поступают на Вх₂ соответствующих управляемых фазовращателей 10₁÷10_N второй группы. Следовательно, после прохождения гармонического сигнала с выхода генератора 1 гармонического сигнала через N управляемых фазовращателей 10₁÷10_N второй группы на выходе фазовращателя 10_N суммарный набег фазы сигнала будет равен .

В первом измерителе 3 фазы происходит сравнение фазы сигнала с выхода фазовращателя 2_N, поступающего на Bx₁ первого измерителя 3 фазы, с фазой опорных сигналов , поступающих с выхода генератора 1 непосредственно на Вх₂(ϕ_{ОП 0}=0) измерителя фазы 3 и через фазовращатели первой группы на измерителя фазы 3. При этом максимальное напряжение будет на выходе того канала, фаза опорного сигнала которого совпадает с фазой гармонического сигнала на выходе фазовращателя 2_N. В момент прихода тактирующего сигнала U_TC на измерителя фазы 3 на его выходе появляется унитарный код, соответствующий номеру канала с максимальным напряжением, что соответствует коду результата сложения .

Аналогичные процессы одновременно происходят во втором измерителе 13 фазы и фазовращателях 12 второй группы с точностью до величины подмодуля, равного р₂. Следовательно, в момент прихода тактирующего сигнала U_TC на выходе второго измерителя 11 фазы появляется унитарный код, соответствующий результату сложения N чисел , который поступает на второй вход табличного вычислителя 13, на первый вход которого поступает унитарный код числа . Табличный вычислитель 13 преобразует промежуточные суммы в результат операции в унитарном коде, который поступает на вход шифратора 5. С его выхода результат сложения N чисел в двоичном коде поступает на выход 6 устройства.

Пример: Пусть p₁=5, р₂=7 (p=p₁·р₂=5·7=35), N=4 (A₁=17, А₂=26, А₃=31, А₄=29). После преобразования двоичных позиционных кодов в преобразователях 8₁÷8₄ по первому подмодулю p₁=5 в i-х управляемых фазовращателях 2₁÷2₄ коммутаторами 17₁÷17₅ подключаются соответствующие линии задержки 18₁÷18₄ на время, равное и получаем: ; ; ; , ввиду того, что A₁ mod 5=17 mod 5=2; А₂ mod 5=26 mod 5=1; А₃ mod 5=31 mod 5=1; А₄ mod 5=29 mod 5=4.

После прохождения гармонического сигнала с выхода генератора 1 через управляемые фазовращатели 2₁÷2₄ первой группы фаза этого сигнала на выходе управляемого фазовращателя 2₄ будет равна , а исходя из периодичности гармонической функции . Таким образом, фаза гармонического сигнала на выходе управляемого фазовращателя 2₄ первой группы прямо пропорциональна величине . Напряжение на выходе интегратора 15 в каналах измерителя фазы 3 будет максимальным для данного номера канала, т.е. для третьего. Следовательно, на первый вход табличного вычислителя 13 поступит число 3 в унитарном коде. Учитывая, что A₁ mod 7=17 mod 7=3; А₂ mod 7=26 mod 7=5; А₃ mod 7=31 mod 7=3; А₄ mod 7=29 mod 7=1, то после прохождения гармонического сигнала через управляемые фазовращатели 10₁÷10_N второй группы на выходе фазовращателя 10₄ фаза сигнала будет равна: а исходя из периодичности гармонической функции . Следовательно, на второй вход табличного вычислителя 13 с выхода второго 11 измерителя фазы поступит число 5 в унитарном коде. Согласно таблицы (для p₁=5, р₂=7) на выходе табличного вычислителя 13 будет число 33₁₀, которое с выхода шифратора 5 поступит в двоичном коде на выход 6 устройства.

Проверка: (17+26+31+29)mod 35=103 mod 35=33 mod 35.

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