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

 

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

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

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

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

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

Недостаток прототипа - низкое быстродействие, так как для сложения N чисел в нем требуется время 2τ_лэ]log₂p[, ограниченное временем переключения логических элементов τ_лэ, где где ]•[ - символ округления в большую сторону до ближайшего целого.

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

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

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

Сущность изобретения основывается на использовании при реализации операции модульного сложения N чисел свойства периодичности гармонической функции. При N<f•τ_лэ•(2•]log₂p[-1)-3 (f - частота гармонического сигнала; τ_лэ- время переключения логического элемента) происходит повышение быстродействия выполнения модульной операции.

Известно, что cos(x) = cos(x+2πk) = cos((x)mod2π), (1) где k=1,2,3,...

Если гармонический сигнал с амплитудой U и частотой ω u(t) = Ucos(ωt) (2) проходит через N последовательно соединенных фазовращателей, то на выходе последнего (N-го) фазовращателя гармонический сигнал будет описываться выражением где Δϕ_i- сдвиг фазы в i-м фазовращателе, Положим, что в i-м фазовращателе сдвиг фазы Δϕ_i прямо пропорционален значению i-го слагаемого A_i

где р - величина модуля.

Тогда (3) с учетом (4) можно представить в виде

Так как

а в свою очередь

то на основании (3) - (6) получим

где [•] - символ округления в меньшую сторону до ближайшего целого.

Таким образом, после прохождения гармонического сигнала через N фазовращателей, сдвиги фазы в которых прямо пропорциональны значению слагаемых А_i фаза гармонического сигнала (7) на выходе N-го фазовращателя будет прямо пропорциональна значению модуля суммы N чисел

Для определения α (8) необходимо измерить величину фазы гармонического сигнала. (7). Измеритель фазы гармонического сигнала можно построить на основе оптимального измерителя параметра сигнала известной формы [1, с. 488, рис. 12.1.].

Необходимые для реализации устройства сложения N чисел по модулю р N последовательно соединенных фазовращателей должны быть управляемыми и могут быть реализованы на основе различных схемных решений. Например, в СВЧ диапазоне [2, с. 102] такой фазовращатель наиболее просто реализовать на основе линий задержки (ЛЗ) на время

где ω- несущая частота гармонического сигнала.

Действительно, если на входе ЛЗ на время Δt_s (9) действует гармонический сигнал
u_в(t) = Ucos(ωt),
то на выходе ЛЗ с учетом (9) будет сигнал

то есть фаза сигнала (10) будет соответствовать (4) при s = А_i. Следовательно, подключая линию задержки в соответствии с унитарным кодом слагаемого можно получить значения фазового сдвига в i-ом управляемом фазовращателе прямо пропорциональное величине этого слагаемого.

Как отмечалось выше, сложение N чисел в прототипе происходит за ]log₂p[ тактов. Следовательно, время выполнения модульной операции в прототипе составляет
T_ПР = ]log₂p[•τ_Σ, (11)
где τ_Σ - суммарное время переключения цифровых логических схем в табличном вычислителе.

Основу узла, выполняющего операцию сложения по модулю р в табличном вычислителе прототипа, составляет матричный дешифратор [3, с. 16-17], построенный на двухвходовых элементах И, расположенных в местах пересечений р горизонтальных и р вертикальных входных шин. Выходы элементов И подключены ко входу соответствующих элементов ИЛИ, число которых равно р. Таким образом, сигнал от входа к выходу в табличном вычислителе проходит через 2 логических элемента - И и ИЛИ. Поэтому
τ_Σ = τ_И+τ_ИЛИ≈2τ_ЛЭ, (12)
где τ_лэ- время переключения логического элемента (И, ИЛИ).

Как показано в [4, с. 173], время τ_лэ≈10^-10 с является практическим пределом для логических элементов на транзисторах, которое достигается только при жидкостном охлаждении до криогенных температур.

Поэтому минимальное время выполнения модульной операции в прототипе на основании (11) и (12) составляет
T_ПР≈2•10^-10•]log₂p[, c. (13)
Время выполнения модульной операции в предлагаемом устройстве (Т_ПУ) на основании вышеизложенного равно сумме времени задержки гармонического сигнала в N управляемых фазовращателях (N•τ_Ф) и времени измерения значения фазы τ_ИЗМ в измерителе фазы гармонического сигнала. Если измеритель фазы гармонического сигнала построен на основе оптимального измерителя параметра сигнала известной формы [1, с. 488, рис. 12.1], то, как следует из его структурной схемы, τ_ИЗМ равно сумме времени интегрирования Т_И в интеграторах измерителя фазы и времени принятия решения в решающем устройстве τ_РУ. Тогда
T_ПУ = Nτ_Ф+T_И+τ_РУ. (14)
Максимальное время задержки в управляемом фазовращателе на ЛЗ, с учетом (9), будет равно

где
f - несущая частота гармонического сигнала, Гц.

Измерение значения фазы гармонического сигнала (7) в измерителе фазы гармонического сигнала происходит путем сравнения фазы этого сигнала с фазами р опорных сигналов, соответственно равными
ϕ_ОП0 = 0;



Алгоритм такого сравнения [1] заключается в перемножении гармонического сигнала (7), снимаемого с выхода N-го управляемого фазовращателя, с опорными сигналами, интегрировании результата перемножения и принятии решения о значении фазы сигнала (7) путем определения в решающем устройстве канала, на выходе интегратора которого результат будет максимальным. Результат перемножения гармонического сигнала с j-ым опорным сигналом можно записать в виде (при выводе формулы u_пj(t) полагалось, что амплитуда опорного сигнала равна U)

где фаза j-го опорного сигнала.

После интегрирования U_пj(t) в интеграторе, получим

Так как ω≫1, то из (16) видно, что уже при Т_И≥(2... 3)Т

причем u_Иj будет максимальным для
С учетом изложенного, для расчета времени выполнения модульной операции возьмем значение Т_И = 3Т.

И, наконец, время принятия решения τ_РУ соизмеримо с временем переключения цифровых логических элементов τ_РУ = τ_ЛЭ, которое в расчетах возьмем равным τ_РУ = τ_ЛЭ≈10^-10c.
Таким образом, с учетом (14) - (17):
T_ПУ = NT+3T+τ_ЛЭ
или для
τ_ЛЭ≈10^-10 (18)
T_ПУ≈N•T+3T+10^-10c.
Уже сейчас на практике реализованы вплоть до 100...150 ГГц типовые радиотехнические элементы (в том числе и в интегральном исполнении) [2] из которых состоят управляемые фазовращатели и измеритель фазы гармонического сигнала.

Следовательно, при f = 100 ГГц = 10¹¹ Гц
T_ПУ ≈ {(N+3)(10^-11+10^-10}, с. (19)
Например, при N=10 и p=5 из (13) и (19) получим
T_ПР ≈ 6•10^-10;
Т_ПУ ≈ 2,3•10^-10.

Из (13) и (18) следует, что в рамках сформулированных допущений о составе сравниваемых устройств предлагаемое устройство предпочтительнее использовать, если
N<f•τ_ЛЭ(2]log₂p[-1)-3,
а при f = 100 ГГц = 10¹¹ Гц и τ_ЛЭ≈10^-10c
N<10•(2•]log₂p[-1)-3.
Для p= 5 в соответствии с (20) предлагаемое устройство предпочтительнее прототипа, если N<47.

1 - 1_N - информационные входы устройства, 2₁ - 2_N - дешифраторы, 3 - генератор гармонического сигнала, 4₁ - 4_N - управляемые фазовращатели, фазовращатели па фиксированные значения фазы, равные 6 - измеритель фазы гармонического сигнала, 7 - шифратор, 8 - выход устройства.

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

На фиг. 2 представлена структурная схема измерителя фазы гармонического сигнала 6, где Вх_K входы измерителя фазы, 9₁ - 9_p - аналоговые перемножители, 10₁ - 10_p - интеграторы, 11 - решающее устройство.

На фиг. 3 представлена структурная схема управляемого фазовращателя 4_r, где Bx₁ и Вх₂ - входы управляемого фaзoвpaщaтeля 12₁ - 12_p - коммутаторы гармонического сигнала, 13_m, линии задержки на время ω - несущая частота гармонического сигнала).

Рассмотрим работу устройства. На N информационных входов 1₁ - 1_N устройства поступают двоичные позиционные коды N чисел А_i, После их преобразования в дешифраторах 2₁ - 2_N в унитарные коды, они поступают на Вх₂, соответствующих управляемых фазовращателей 4₁ - 4_N. В соответствии со значениями унитарных кодов чисел A_i, поступающих на Вх₂ управляемых фазовращателей 4₁ - 4_N, в них путем подключения коммутаторами 12₁ - 12_p соответствующих линий задержки 13₁ - 13_(p-1) устанавливаются набеги фазы, равные После прохождения гармонического сигнала с выхода генератора гармонического сигнала 3 через N управляемых фазовращателей 4₁ - 4_N в соответствии с выражением (7) на выходе фазовращателя 4_N суммарный набег фаз этого сигнала будет равен
В измерителе фазы 6 происходит сравнение фазы сигнала с выхода фазовращателя 4_N, поступающего на Bx₁ измерителя фазы 6, с фазой опорных сигналов поступающих с выхода генератора 3 непосредственно на Вх₂ (ϕ_on0 = 0) измерителя фазы 6 и через фазовращатели 5_q на Bx_(q+2) измерителя фазы 6. При этом. максимальное напряжение будет на выходе того канала, фаза опорного сигнала которого совпадает с фазой гармонического сигнала на выходе фазовращателя 4_N. В момент прихода тактирующего сигнала на Вх_(p+2) измерителя фазы 6 на его выходе появляется унитарный код, соответствующий номеру канала с максимальным напряжением, что соответствует коду α результата сложения N чисел по модулю р: После преобразования этого кода в шифраторе 7 в двоичный позиционный код, результат сложения N чисел по модулю p поступает на выход 8 устройства.

Пример. Пусть р = 5, N = 4 (A₁ = 1; А₂ = 4; A₃ = 2; A₄ = 1). После преобразования двоичных позиционных кодов А_i, в дешифраторах 2₁-2₄ устройства в унитарные коды, в i-ых (i=) управляемых фазовращателях 4₁ - 4₄ коммутаторами 12_q подключаются соответствующие линии задержки 13_q на время, равное где

После прохождения гармонического сигнала с выхода генератора 3 через управляемые фазовращатели 4₁-4₄, на выходе фазовращателя 4₄ фаза этого сигнала в соответствии с (5) будет равна Так как гармоническая функция периодическая, то в соответствии с (1) значение фазы эквивалентно Таким образом, фаза гармонического сигнала на выходе управляемого фазовращателя 4₄ прямо пропорциональна модулю суммы Напряжения на выходах интеграторов 10₁ - 10_s в каналах измерителя фазы 6 в соответствии с (17) будут равны

Из приведенных формул видно, что максимальное напряжение будет на выходе канала j= 3, соответствующего фазе После прихода тактирующего сигнала u_TC на Вх_(p+2) (Вх₇) измерителя фазы 6 на его выходе образуется унитарный код числа α = 3, который преобразуется в шифраторе 7 в позиционный двоичный код и поступает на выход 8 устройства.

Формула изобретения

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

РИСУНКИ

Рисунок 1, Рисунок 2, Рисунок 3