Устройство для умножения комплексных чисел в модулярном коде Советский патент 1987 года по МПК G06F7/72 

1 i

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

Цель изобретения - сокращение аппаратурных затрат.

На фиг.1 приведена структурная схе ма устройства для умножения комплексных чисел в модулярном коде; на фиг.2 временная диаграмма работы устройства

Устройство для умножения комплексных чисел в модулярном коде (фиг.1) содефжит первый 1 и второй 2 информационные входы, вход 3 номера константы и группу тактовых входов А устройства,, первый вспомогательный регистр 5, первый элемент ИЛИ 6, первый блок 7 мультиплексоров, блок 8 формирования дополнительного кода по модулям системы счисления, выход 9 устройства, второй вспомогательный регистр 10, второй блок 11 мультиплексоров, входной регистр 12, третий вспомогательный регистр 13, второй элемент ИЛИ 14, блок 15 схем сравнения, первый блок 16 хранения констант, блок 17 вычисления интервального индекса числа, второй блок 18 хранения констант, первый элемент 19 задержки.

V,(X,.,1,1) г,(Х.,1о,1); Re(X,,U,l),...,R(X,,lp,l), (I)

где г.(Х.,1д,1 ) |м-.,- X,-W/nii|;

(х,.ц.1) « 0-k;

W - константа с номером 21-t-lj,

l,elo,l,. 1 е(оL-i,

L - число используемых комплексных 45 констант (поворачивающих множителей);

га ( - система попарно взаимX;eiO,...,mj-l,

1,.- но простых модулей, причем т , 2р+

, р - фиксированное натуральное число, т, - вспомогательный модуль т,7, р, gcd(m4,m)-l , k-1, (i V (Х,1, ,l)(X,le,l),...,Rt(X,l,l),

где RJ (X,,l,l)X;W/m,, ,...,k;

X, если X р

,АД

m V - X, если X , р.

МИ(Л nHX.llJlllBl.lM CVMM llli) t O, Г РУШ У

блоков 2 1 умми) пычетоя, блок 22 м()луЛ1,Н1,1х гумматорор, MOTRt p-n.irt prnoMiU-aTCJii.ni.irt регистр 2), пятьп (1глтр-П,иый pofncTp 24, второй .элемент 25 задержки, третий блок 26 мультиплексоров, шестой вспомогательный регистр 27, блок 28 модульных 1Q вычитателей, блок 29 деления на вспомогательный модуль, седьмой вспомо- гательны} регистр 30, третий элемент 31 задержки.

15

Временная диаграмма работы устройства (фиг.2) приведена для случая, когда число оснований изменяется от

до

8

что соответствует .

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

Временная диаграмма работь устрой- ства при обработке мшгмой части искомого числа Tioj-гучается из приведенной диаграммы путем сдпиг а последней на два такта.

Первый блок 16 хранения констант реа;тизован на k-1 элементах памяти, в ячейку i-ro из которых с адресом X 2 2 записывается констант:

1 ,...,k-l) ; k - число модулей выбранной модулярной сис1ем1,1 счисления.

W-(

М

1 , tc - (

M., /m; , M

V-

n

j

m.

Первые, вторые и третьи адресные входы элементов памяти в совокупности образуют соответственно первый, второй и третий адресные входы бло ка 16 хранения констант, а выходы, соответствующие первым и -м компонентам выходных наборов вычетов, образуют соответственно первый и j-й выходы блока 16 хранения констант (J-2,. . . ,) . В ячейку блока 18 с адресом X + 1,-2 1 записывается набор констант:

(2)

Группа блоков 21 суммирования вычетов содержит блоки суммирования вычетов по модулям т, i -и из ко-| торых (,1,...,k) осуществляет еложение за Т logjk-l( тактов наборов И- k-1 вычетов по модулю т,.

Блок 17 вычисления интервального индекса числа по входному модулярному коду (х,,...,Х|) некоторого числа X модулярной системы счисления определяет машинный интервальный индекс:

I(X)-/I(X)/m,« - i. -f

m+..

m.

-IM:;

где X,, V., M.,,, -Xj/m,;

I(X) - интервальный индекс числа.

Блок 15 схем сравнения содержит k-l схем сравнения, каждая из которых формирует на выходе единичный сип- нал, если значение на первом входе больше или равно значению на втором входе.

Блок 29 деления на вспомогательный модуль реализован на k элементах памяти, в ячейку с адресом v +2 ° 1 i-ro из которых записывается вычет

Первые входы всех элементов памяти объединены и в совокупности с вторыми входами образуют вход блока 29 де- леиия иа вспомогательный модуль.

k-

„v, C/iJc.l-W l

де Q , , - I----- J ;

KA W - А W)- 21 (р; )+QVVQ ; - Я, ;

fi1 и

k-t

KA W -ь A W )- L (Q f, qV )

Д f, -l--- -- -

. «vM- -i7--l

; «I(A )W , .I(A )W

)W; (-A ).W ;

i, - количество переполнений при сложении чисел А W и А flj - количество переполнений при сложении чисел А W и А W. Рассмотрим как работает устройство пя умножения комплексных чисел в моулярном коде.

На первом и втор 4 группы, выходе эл элемента 31 задержк равляющие сигналы 6

Модулярный код ( .45 части А числа А, п рого информационног (7) ства на первый инфо первого блока 7 мул управляющий вход ко 50 сигиал и, 0, запис регистр 12; а в рег 3 устройства переда лексной константы W

На первом такте 55 (o l. ., oi ) ройства через второ плексоров () по блока 17 вычисления декса числа и пернм

.

-

15

Элементы 19 и 31 зал{ ряч н выполняют задержку сигнлла соогретственно ня Т и (Т+3) такта.

Второй элемент 25 задержки представляет собой цепочку из Т-I последовательно соединенных регистрор,пход первого и выход последнего из которых являются соответственно входом 10 и выходом второго элемента 25 задержки.

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

Пусть требуется перемножить комплекс.1 . . (I ное число А А jA на комплексную

„ w .W

константу 1--, имеющую

pMk-1 , PMl,.,

яомер 1, А ,A ,W ,W - целые числа из диапазона D модулярной системы счисления. I

Действительная и мнимая части произведения JB могут быть вычислены по следующим приближен}гъгм формулам:

в г J (А W - А W ) ;

в J CA W -t- А W), (3)

где J(X)l(X)/mj -ядерный интервальный индекс числаX;

х - ближайшеек х целое число. При этом

20

25

30

(6)

На первом и втором тактовых входах 4 группы, выходе элемента ИЛИ 1А и элемента 31 задержки формируются управляющие сигналы 6р -6,, .

Модулярный код (о,,. . . ,(У 1) мнимой .45 части А числа А, поступающий с второго информационного входа 2 устрой- ства на первый информационный вход первого блока 7 мультиплексоров, на управляющий вход которого подается 50 сигиал и, 0, записывается во входной регистр 12; а в регистр 13 через вход 3 устройства передается номер комплексной константы W.

На первом такте модулярный код 55 (o l. ., oi ) А с входа 1 устройства через второй блок II мультиплексоров () поступает на вход блока 17 вычисления интервального индекса числа и пернмй адресный вход

513

первого блока 16 хршкмшя кппстянт, на второй и третий пдрссиые иходм которого с выходом соответственно Ш1И 6 элемента и регистра 13 поступлют величины 1 и 1,

0.

На первом выходе первого блока 16 хранения констант формируется набор вычетов г (« .,1 д 1), который по- ступа ет во вспомоглтельньй регистр 2А, на J-M выходе первого блока 16 хранения констант формируется набор вычетов R. (с., IO.D (см, формулу (1), который поступает на вход группы блоков 21 суммирования вычетов, которые в ходе очередных Т тактов суммируют по модулям системы наборы входных вычетов, а блок 17 вычисления интервального индекса числа начинает вычисление по модулю т, интервального индекса 1(Л ).

На втором такте работы устройства модулярный код (о,. , . , д( ) числа А с выхода входного регистра 12 через второй блок 11 мультиплексором («л.) поступает на вход блока 17 вычисления интервального индекса числа и первый адресный вход первого блока 16 хранения констант, на второй и третий адресные входы которого поступают величины 1 и 1(, 1- Содержимое вспомогател ного рег нстра 2Д записывается во вспомогательный регистр 27 а во вспомогательный регистр 24 поступает набор Еычетов Г; (dJ , 1,1), который формируется на первом выходе первого блока 16 хранения констант.

На J-M выходе первого блока 16 хранения констант формируется набор вычетов Rj .j (, Ij,), поступающий на входы блоков 21 суммирования вычетов, а блок 17 вычисления интервального индекса числа начинает вычисления по модулю m , интервального индекса 1(Л).

На третьем такте работы содержимые вспомогательных регистров 24 и 27 поступают соотпетственно на первый и второй входы блока I5 схем сравнения, на выходе которого формируются pesyJibraTbi сравнения, которые поступают нп четвертом такте на вход сумматора 20, который находит рели- чину Q, эаписынаютуюся в первый регистр второго элемента 25 задержки.

На (Т-1)-м тлкте на вход приема кода регистра 23 поступает сигнал i;, l, ьследгтпие чего содержимое 1 регистра 13 чаг.ис-ыидетгя в регистр 23

,3i6

j b ист« 1Г Иии () такта работы уст- P n ic i-iin на ibtxonc: блока 17 вычисления iiM t е)вал1.иого индекса числа фор- ми1)уетгя пычет 1.(А ).

На ()-м такте величина I(A ) с выхода блока 17 вычисления интервального индекса числа поступает на первый адресный вход второго блока 18 хранения констант, на третий и второй

адресные вхо;1ы которого подаются соотпетственно величины с выхода элемента 19 задержки и величина 1 с выхода регистра 23. На выходе второго блока 18 хранения констант формируется набор остатков по модулям величины Qy(формула (7), которая записьг- вается во вспомогательный регистр 5. }1а п(,1ходе группы блоков 2 суммирования вычетов формируется набор выче

k-i

(1

2„ И, Ч.

u i

а на в,гходе блока 17 вычисления ин- терпального индекса числа - вычет

л (I

I (Л ) .

ч

Нд (Т- -2)-м такте величины с выходов 1-руттп блоков 21 суммирования и ти-помогательног) регистра 5 поступают соотнетственно на первый и второй

входы блока модульных сумматоров 22, на выходе которот О с юрмируется велиk-i Т

ющаяся во вспомогательный регистр 30. Одновременно с этим величина с выхода блока I7 вычисления интервального индекса числа поступает на первый адресный вход второго блока 18 хранения констант, на третий и второй адресk-(

Z- Q. . записываf, i f

ные аходо которого подаются соответственно величины 1„ с выхода элемента 19 задержки и 1 с выхода регистра 13. Па выходе второго блока 18 хранения констант формируется набор остат- ков по модулям величины I (А ) -W , которая записывается во вспомогатель- Hbrii регистр 5. На выходе группы блоков 21 суммирования вычетов формируется набор остатков по модулям вет i ..

t 1- второго элемента 25 задержки пояаляется величина Л,,

На ()-м такте величины с выхо- дов группы блоков 21 суммирования вычетов и вспомогательного регистра 5 подаются соответственно на первый и второй входы блока модульных суммаличины

на выходе

торов 22, на Н1. которого форм1Н1у ется величина X

-I 1, j

I(A ) W), которая зшшсыпаетгя РО вгпомогательньт регистр 30. Предыдущее содержимое вспомогптельного регистра 30 (X ) поступает на перв(,ш вход блока 28 модульных вычитателей, на второй вход которого через третий блок 26 мультиплексоров (й,0) с пы- хода второго элемента 25 задержки поступает величина S7 , Блок модульных вычитателей 28 находит величину Y X , которая записывается во вспомогательный регистр Ш.

На ()-м такте работы устройств величина Xj с выхода вспомогательног регистра 30 подается на nepBbrfi лход

блока 28 модулып.гх вычитателей, на второй вход KOTOpoi o через блок 26 мультиплексоров () с выхода вспомогательного регистра 10 поступает величина Y . Блок модульных вычитателей находит величину X - Y -KA W - ) (см.формулу (6), которая записывается во вспомогательный регистр 10.

На (Т-«-5)-м такте содержимое вспомогательного регистра О поступает на вход блока 29 деления на вспомогательный модуль, определяющий мо- дулярньш код (pj,.,., f,) действительной части искомого прс тведения, который снимается с выхода 9 устройства.

В ходе тактов с третьего пс (Т- -7)включительно указанные действия выполняются для модулярных кодов

(; ,...,;) и (,.....

(-с(/га). последний из которых на третьем такте работы устройства формируется в блоке 8 формирования до- попинтельного кода по входному модулярному коду числа А и записывается во входной регистр 12. Модулярный код ( ..... /ijl) на ()-м такте снимается с выхода 9 устройства и на этом операция умножения комплексных чисел А и W завершается.

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

Устройство для умножения комплексных чисел в модулярном коде, содержащее входной регистр, блок формирования дополнительного кода по модулям системы счисления, два блока мультиплексоров, группу блоков суммироваННЧ nhineiOH, ЧР ГЫ( ИЧИЧ i l ,1 l Г .ш.и: : ч

рсм истрл , бдик делгиик и.ч ш ;N-N.M - TOJibHi m модуль, блок Mo;i.y.iibin.ix ,чторов, блок Г ЫЧИСЛГНИЯ 7П -| р 1. 1ЫЮГ(1

индекса числа и дна блок.ч хрлигиич констант, причем перр . о .,l иичм- ные входы первого и пторог о Плокоя мультиплексоров сординеиы чи тнетст0 иепнп с вторьт- и первым щк ормлциоп- входами устрО1)ствл, П1.1ХЧЛ псрпо- го блока мультиппркгорон сосдинои с входом входного регистра, т.рсод которого соединен с входом блока форми5 ропапия дополнительнот О кода по модулям системы счисления, гыход второ- 1-0 блока мультиплексоров соети(нен с первым адресным входом перпого блока хранения констант, выходы которого,

0 кроме младшего, соединены с входами соответствуюп1их блоков сумг-пфования вычетов группы, выходы которых соединены с входом первого слагаемого блока модульных сумматоров, вход второ5 го слагаемого которого соединен с вы- .одом первого вспомогательного регистра, вход которого соединен с выходом второго блока хранения констант. первы 1 адресный вход которс го соеди0 иен с выходом блохя вычисления интервального индекса числа, вход которого соединен с рыходом второго блока мультиплексоров, выход второго вспомогательного регистра соединен с

5 входом блока деления на вспомогательный модуль, выход которого является выходом устройства, вход номера кон- станть устройства соединен с входом третьего вспомогательного регистра,

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

5 вспомогательные регистры, третий блок мультиплексоров, блок схем сравнения, многовходовой сумматор, блок модульных вычитателей, два элемоша 11ПИ и . три элемента задержки, пт мчем выход

913

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

3110

входом второго блока мультиплексоров, второй и третий тактовые входы г руччпы устройства соединены соответственно с вторыми входами первого и второго элементов ИЛИ, выход многовходового сумматора соединен с входом второго элемента задержки, выход которого соединен с перрьгм информационным входом

третьего блока мультиплексоров, второй информационный вход которого соединен с выходом второго вспомогательного регистра, выход второго элемента ИЛИ соединен через третий элемент

задержки с управляющим входом третьего блока мультиплексоров, выход которого соединен с входом вычитаемого блока модульных вычитателей, БЫХОД которого соединен с входом второго

вспомогательного регистра, выход блока модульных сумматоров соединен с входом седьмого вспомогательного ре- гистра, выход которого соединен с входом уменьшаемого блока модульных

вычитателей.

7 2J«5678

п

п

п

Редактор М.Дьшын

Фиг.2

Составитель А.Клюев

Техред в. Кадар Корректор И.Муска

Заказ 3583/50 Тираж 672Подписное

ВНИИПИ Государственного комитета СССР

по делам изобретений и открытий 113035, Москва, Ж-35, Раушская наб., д.4/5

Производственно-полиграфическое предприятие,г.Ужгород,ул.Проектная,4

п

Изобретение относится к вычисли- ,тельнрй технике и может бытьи использовано в быстродействующих процессорах быстрого преобразования Фурье для умножения комплексных чисел на поворачивающие множители, а также для получения последних. Цель изобретения - сокращение аппаратурньсх затрат. Поставленная цель достигается тем, что в устройство для умножения комплексных чисел в модулярном коде, содержащее входной регистр 12, блок 8 формирования дополнительного кода по модулям систем счисления, блоки 7 и II мультиплексоров, группу блоков 21 суммирования вычетов, вспомогательные регистры 5,10, 13 и 23, блок 29 деления на вспомогательный модуль, блок 22 модульных сумматоров, блок 17 вычисления интервального ин- декся и блоки 16 и 18 хранения констант, вг:)едемы вспомогательрше регист- Q ры 2А, 27 и 30, блок 26 мультиллексо- ров, блок 15 схем сравнения, много- входовый с Мматор 20, блок 28 модульных вычитателей, злементы ИЛИ 6,14 и элементы 19, 25 и 31 задержки с соответствующими связями. 2 ил. (Л с: /- Lfl со 00 о О) 00