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

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

Иллюстрации

Показать все

Реферат

 

Изобретение относится к вычисли- ,тельнрй технике и может бытьи использовано в быстродействующих процессорах быстрого преобразования Фурье для умножения комплексных чисел на поворачивающие множители, а также для получения последних. Цель изобретения - сокращение аппаратурньсх затрат. Поставленная цель достигается тем, что в устройство для умножения комплексных чисел в модулярном коде, содержащее входной регистр 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

СОЮЗ СОВЕТСМИХ

С{ХЗИАЛИСТИЧЕСНИ Х

РЕСГ1УБЛИК

„„SU„„ 1330ß! А1 11 4 G 06 F 7/12 ъ» rr .„1 1; . Г

i,!

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

По ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТЖ (21) 3990960/24-24 (2 ) 13.12.85 (46) 15.08.87. Бюл. Э 30 (7l) Научно-исследовательский институт прикладных физических проблем им.А.Н.Севченко (72) Л.Н.Василевич, А.А.Коляда, B,В.Ревинский и M.Þ.Ñåëÿíèíîâ (53) 681.3(088.8) (56) Авторское свидетельство СССР

Ф 1015382, кл. С 06 F 7/72, 1981.

Авторское свидетельство СССР

У 1280625, кл. С 06 F 7/72, 01.08.85 (54) УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ КОМП—

ЛЕКСНЫХ ЧИСЕЛ В МОДУЛЯРНОМ КОДЕ (57) Изобретение относится к вычисли, тельнрй технике и может быть использовано в быстродействующих процессорах быстрого преобразования Фурье для умножения комплексных чисел ма поворачивающие множители, а также для получения последних. Цель изобретения — сокращение аппаратурных затрат. Поставленная цель достигается тем, что в устройство для умножения комплексных чисел в модулярном коде, содержащее входной регистр 12, блок 8 формирования дополнительного кода по модулям системы счисления, блоки 7 и ll мультиплексоров, группу блоков 21 суммирования вычетов, вспомогательные регистры 5,10, 13 и 23, блок 29 деления на вспомогательный модуль, блок 22 модульных сумматоров, блок 17 вычисления интервального индекса и блоки 16 н 18 хранения констант, введены вспомогательные регистры 24, 27 и 30, блок 26 мультиплек.î- 4 ров, блок 15 схем сравнения, многовходовый сумматор 20, блок 28 модульЮ ных вычитателей, элементы ИЛИ 6,14 и элементы 19, 25 и 31 задержки с соответствующими связями. 2 ил.

S 330Ь31

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

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

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

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

Устройство для умножения комплексных чисел в модулярном коде (фиг.l) содержит первый 1 и второй 2 информационньге входь), вход 3 номера константы и группу тактовых входов 4 устройства,. первый вспомогательный регистр

5, первый элемент ИЛИ Ь, первый блок

7 мультиплексоров, блок 8 формирования дополнительного кода по модулям системы счисления, выход 9 устройства, второй вспомогательный регистр

I0, второй блок 11 мультиплексоров, входной регистр 12, третий вспомогательный регистр 13, второй элемент

ИПИ 14, блок 15 схем сравнения, первый блок 16 хранения констант, блок

17 вычисления интервального индекса числа, второй блок 18 хранения констант, первый элемент 19 задержки, 25

Ч, (Х;,1,1) (г,(Х;,1,1); К,(Х),1„1),...,R),(X;,1,,1)), (I) М; „, М„,/m., М

50,1),...,R), (Х,1 „1), (2) Ч (Х, lo 1) сК,(Х,1

Группа блоков 21 суммиронания вычетов содержит блоки суммирования вычетов по модулям m m„, i -й из ко-) торых (i=O,l,...,k) осуществляет слоа

А

m — Х, если Х > р. где г . (Х,,14,1 ) =1<з; k- Х ) W/m;li

I M; k. г Х ) /и) . ЪЦ

1 ) j 0-k;

W — константа с номером 21+1,, 1,E(0,1}, 1 6 (O,...,L-1}, число используемых комплексных констант (панорачивающих множителей);

Х, е (O,...,m; — 1)1, i I-k; щ,...,m — система попарно взаимно простых модулей, причем m ),, 2р+

+k-2, р — фиксированное натуральное число, щ, — вспомогательный модуль

m, р, g<=d (m»m 3) I i щ) з k 1, (i где R (Х, I„l) IX W/ml, j O,...,k;

Х, если Х с р м)гаг «k <>J«мм:, «р . О, г ру«г<у блоков 21 < уммггрог<;гг<гг«вз,«гс тс<)г, бл к

22 м<>дульных гуммат< р«в, четверпгй нгггг<м«г:)тел),ный рс k и тр 23, ггятьп) нспс м< г атp!1!,íb<é рег)гс тр 24 „второй элемент 25 эадержк)г, третий блок 26 мультиплексоров, шестой вспомогатепьный регистр 27, блок 28 модульных нычитателей, блок 29 деления на нспомога тел b)lb))1 модуль, с едьмой нспамс— гательный регистр 30, третий элемент

31 задержки.

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

"5" да "8", чта соответствует T=3.

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

Временная диаграмма рабать< устройства при обработке мнимой части искомого числа )голу<гается из приведенной днаграммъг путем сдвига паследней на дна такта.

Первый блок 16 хранения констант реализован íà k-1 элементах памяти, в ячейку i ãî из котс)рых с адресам

)) +1

Х +1 2" +1 2 записыггается набор

<г констант:

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

П m,.

): 1

Первые, вторые и третьи адресные входы элементов памяти в совокупности o6разуют соответственна первый, второй и тре<ий адресные входы блока 16 хранения констант, а выходы, соответстнуюшие перььгм и j-м компонентам выходных наборов вычетов, образуют соответственно первый и з-й выходы блока 16 хранения констант (j 2,...,k+2). В ячейку блока 18 с адресом Х + 1 2 + 1 2 " записьгп< вается набор констант:

13Ю< 11

10 х

+ - -- m

М„, Ь

ГДЕ Х< 1 jM., Х,./Ш,;

I(X) — интервальный индекс числа, 15

Блок 15 схем сравнения содержит

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

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

i-ro из которых записывается вычет

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

i -1

I(A W — А" W"),7 ((} " +Q . )+Q +Q — Я,; (6) (ii

+ " . )+ ", +Q (", I(A W +А" W) (Я <

1 < a1 W)

1

Ы 1 И"

J Lh. -- — ° ш, «1 где Q <,.

< 1

Р,i

На первом и втором тактовых входах

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

Модулярный код (<,,...,d ) мнимой

Ц ,45 части А числа А, поступающий с второго информационного входа 2 устройства на первый информационный вход первого блока 7 мультиплексоров, на управляющий вход которого подается

50 сигнал 6, =О, записывается во входной регистр 12; а в регистр 13 через вход

3 устройства передается номер комплексной константы W.

На первом такте модулярный код (d,,...,< „ ) 4исла А с входа 1 устройства через второй блок 11 мультиплексоров (C -O) поступает на вход блока 17 вычисления интервального индекса числа и первый адресный вход

1 1 1 Г; >,. W × (7) жение за Т = ) log k-I(тактов наборов и k-I вычетов по модулю m>.

Блок 17 вычисления интервального индекса числа по входному модулярному коду (х,,...,x„) некоторого числа

Х модулярной системы счисления определяет машинный интервальный индекс:

<,-1

I(X)-/I(X)/ „- —,Г -"- - +

I /- I /шо -1; 12 /-

mo (. 1

fl

II

«I » 1;1 .W

Я

1 ° е, m <.

Q q -Т(А " ) 1 ; Q",-I (-А" ) М";

Я, — количество переполнений при сложении чисел А W и А W

Q< — количество переполнений при сложении чисел А W" и А" W""..

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

Элемен1ы I9 и 3! задержки вып<лняloT задержку сигнал» с<стнетстве1<но на Т и (Т+Э) такта.

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

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

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

W .W константу W=----- + j------ имеющую

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

Действительная и мнимая части проН изведения В=В + jB могут быть вычислены по следующим приближенным формулам.

В J (А W + А" W ), (5) где .1(Х) (I(X) /<и,) — ядерный интервальный индекс числа Х; (х 1 — ближайшее к х целое число.

При этом

1330(3 >

Г

5 первого блока 16 xp;»((ии((к(и -.тлит, на второй и третий лдресиые входы которого с выходов (оответстненио ИЗ(И 6 элемента и регистра 13 поступлют величины 1 и 1, О. 5

На первом выходе первого блока

)6 хранения констант формируется набор вычетов г (.,1 1), который по1 ступает во вспомогательный регистр

24, на j-ì выходе первого блока 16 10 хранения констант формируется набор вычетов R . >(Ы., 1,,1) (см.формулу (1), который поступает на вход группы блоков 21 суммиронания вычетов, которые в ходе очередных Т тактов 15 суммируют по модулям системы наборы входных вычетов, а блок 17 вычисления интервального индекса числа начинает вычисление по модулю m инчер-. ( вального индекса 1(Л ). 20

На втором такте работы устроиства модулярный код (с,..., 3 ) числа

1(А с выхода входного регистра 1? «ерез второй блок 11 мультиплексоров (ь 1) поступает на нхад блока 17 ны- 25 ( числения интервального индекса числа и первый адресный вход первоro блока

16 хранения констант, на второй и третий адресные входы которого поступают неличины 1 и 1 =1 Содержимое З0 о вспомогательного регистра 24 записывается во вспомогательный регистр 27, а во вспомогательный регистр 24 поступает набор вычетов г;(Ы, 1 „,1), который формируется на перв(1м выходе 35 первого блока 16 хранения констант.

На j-ì ныходе первого блока 16 хранения констант формируется набор вычетов R (3.. 1,1), поступаю(ций на входы блоков 21 суммирования выче- 40 тов, а блок 17 вычисления интервального индекса числа начинает вычисления по модулю m < интернального индекса I(A ).

На третьем такте работь! содержи- 45 мые вспомогательных регистров 24 и

27 поступают соответственно на первый и второй входы блока 15 схем сравнения, ия выходе которого формируются резу(ьтаты срлвнения, которые 50 поступают нл четвертом такте иа вход сумматора 20, который находит величину Я,, за»исыианлпуюся в первый регистр нторо1 о элемента 25 задержки.

На (Т-1)-и т",кте на вход приема 55 кода регистра 23 поступает сигнал

4,=1, гслелст- ие чего содержимое 1 регистра 13 (аи(((ынается в регистр 23.

11(If(т(((. ((и Г-го тlN;TJ рлб >ты устf)<>(I (.(н,(I(1 и(lë(1äÃ. блока 7 Вычисленияия иизсрнлл(.ного индекса числа фор( мируется вычет 1. (A ) .

Ил (Т+1) -м тлкте величина 1(А ) с вых(да блока 17 вычисления интервального индекса числя поступает на первый лдресный вход второго блока 18 хранения констант, нл третий и второй адреснь(е входы которого подаются cooтнРтственно величины 1((0 с выхода элемента 19 задержки и величина 1 с выхода регистра 23. На выходе второго блока 18 хранеиия констант формируется набор остатков по модулям величины Я("(формула (7), которая записывается но вспомогательный регистр 5.

Ня выходе группы блоков 2! суммирования вычетов формируется набор ныче((- (<((, то В ПО МОдуЛ яМ В РЛИЧИ НЫ 2 Q

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

I(A ).

Нз (Т+2)-м такте величины с выходов трупп блоков 21 суммирования и вспомогательного регистра 5 поступают соотнетствеиио иа первый и второй нхо (ы блока модульных сумматоров 22, иа выходе которого формируется вели1 ((l ((! чи и а . (= Q + Q з а пи сынае,; е ющляся во вспомогательный регистр 30.

Одновременно с этим величина с выхода блока 17 вычисления интервального индекса числа поступает на первый адрссный вход второго блока 18 хранения констант, на третий и второй адресные входы которого подаются соответственно величины 1„ с выхода злемен. тл 19 задержки и 1 с выхода регистра

l3. !ia выходе второго блока 18 хранения констант формируется набор остатков по модулям величины I(А " ) W которая записывается во вспомогательный регистр 5. На выходе группы блоков 21 суммирования вычетов формируется набор остатков по модулям eel(! и э(,(-(- W личины 1(------- — --, на выходе а 1

mi в roporn элемента 25 задержки появляет. ся величина Я, .

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

13 торов 22, нл E>< lx<>fie которого <1ор<<111>у—

1 1 С<1 . И ется величина Х =, -- ---- <. л л

+ I(A ) W ), которая злииеынлетея «О нгпомогательньп1 регистр 30. ПредыдуЩЕЕ СОДЕРЖИМОЕ НСИОМОГЛТЕЛЬИОГO Ре1 гис тра ><0 (Х ) !!осту!гает нл пе р«111! вход блока 28 модульных нычитателей, на второй вход которого через третий блок 26 мультиплексоров (Д,=-О) с «В!хода второго элемента 25 задержки поступает величина Я, Блок модульньгх вычитлтелей 28 находит величину Y

Х, — Я, которая з»иисынается но вспомогательный рег истр 10.

На (T+4)-м такте работы устройстнл

I величинл X > с ньгхоцл вспомогательного регистра 30 подлется иа первый «ХОД блока 28 модульных «!<читателей, нл второй вход которого через блок 26 мультиплексоров (6,=1) с выхода Вспомогательного регистра 10 поступает

I величина Y . Блок модульных нычитателей находит величину Х вЂ” г

-Т(А W — А W ) (см.формулу (6), которая записывается но вспомогательный регистр 10.

На (T+5) и такте содержимое вспомогательного регистр 10 поступает на вход блока 29 деления на вспомогательный модуль, определяющий модулярный код (7E,..., 71„ ) действительной части искомого йро> знедения, который снимается с выхода 9 устройства.

В ходе тактов с третьего пс (Т+7)-й включительно указанные действия Выполняются для модулярных кодов (Ы,,..., Ы „ ) и (l-d",/m,,..., (- d /гп„), последний из которых на третьем такте работы устройства формируется в блоке 8 формирования дополнительного кода по входному моду1< лярному коду числа А и записывается во входной регистр 12. Иодулярнь<й код (1ь 1,..., 11" ) на (Т+7)-м такте снимается с выхода 9 устройства и на этом операция умно ения комплексных чисел А и W завершается.

106 »

15

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

Устройство для умножения комплексных чисел н модулярном коде, содержащее входной регистр, блок формирования дополнительного кода по модулям

1 системы счисления, два блока мультиплексоров, группу блоков суммирова30

ИИ, ««I <Åò<>1<, ЧРТЫРС «<-11 ),1 11< ре ги< тp«бл<>к 71<.1) «11111; 11,1 1«;. <, 1 те)11 иьл» м<>пуль, блок и<»;yJ1l 111х у);)<»-торов, блок гчячиелеIIEIR )иг р>1»..;1,«ог<

И<ГД<л К СЛ Чl!СЛЛ ll ««Л i>Jl<> K;1 X !>:) 11< 1111 1 коистлнт, причем и< р)>1 е 1111<1 );» л «и< и— ные ВхОДи пег)н<>г О 11 i>T<>p<>I <> бло)<о«

МУ)IЬТПИЛРK C OP<>EI < ОРДИИ< 1114 < <>о! I>< T< T

«е«11<) г «тор)г и и«рным 1<111<>Е м lи><о«в

1и <ми «ходами устройс)«л, «их< д и< р<>Ого блока мультиилекеоро«се < дине« с входом входного регистр», 1,гх<)д котОрого соединен с «ходом блока формиро«лиил дополнительного кодл по модулям системы счисления, «ь<хОП нторогО блока мультиплексоров соец<<нен с первым адресным «ходом иег>г)ог<> блока

ХР;IНРНИЯ КО«С ТЛНТ, НЬ1ХОДЫ K<> I ОРОГО, кроме милдшего, соединен!1 с «ходами соответствующих блоков сум)<г!ровлния вычетов группы, выходы которых соединеиь1 с входом первого слагаемого блока модульных суммлторов, вход второго слагаемого которого соединен с ньг

:.одом перног о вспомогательного регистра, вход которого соединен с «ыходом второго блока хранения констант, первый лдреснь)й нход которого соединен с выходом блока вычисления инТЕРНЛЛЬНОГО ИНДЕКСЛ ЧИС.<ГЛ, «ХОД КОторогп соединен с vt txo7toII второго блока мультиплексоров, выход «торого вспомогательного регистра соединен с

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

1330631

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

5 входного регистра соединен с вторым элементов ИЛИ, выход многовходового информационным входом второго блока сумматора соединен с входом второго мультиплексоров, младший выход перво- элемента задержки, вггход которого соего блока хранения констант соединен с динен с первым информационным входом входом пятого вспомогательного ре- 10 третьего блока мультиплексоров, втогистра, выход которого соединен с пер рой информационный вход которого соевым входом блока схем сравнения и че" дннен с выходом второго вспомогательpcs щестой вспомогательный регистр — ного регистра, выход второго элеменс вторым входом блока схем сравнения, тя ИЛИ соединен через третий элемент выход которого соединен с вторым вхо- 15 задержки с управляющим входом третьедом многовходового сумматора, первый го блока мультиплексоров, выход котактовый вход группы устройства соеди торого соединен с входом вычитаемого нен с первыми входами первого и вто- блока модульных вычнтателей, выход рого элементов HJIH, выход первого эле- которого соединен с входом второго мента ИЛИ соединен с третьим адресным ро вспомогательного регистра, выход бловходом первого блока хранения конс- кя модульных сумматоров соединен с таит и через первый элемент задержки — входом седьмого вспомогательного рес третьим адресным входом второго бло- гистра, выход которого соединен с ка хранения констант, выход второго входом уменьщаемого блока модульных элемента ИЛИ соединен с управляющим ?5 вычитателей. конера

/ТЮлу7иМФ

&юк 18 блок 15 блок 20 блок 1о блок 22 блок 28

Елок 29 блок 25

Елок 5

&ив Л

& ок 13

Фиг. Z

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

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

ВНИИПИ Государственного комитета СССР по делам иэобретений и открытий

ll3035, Москва, Ж-35, Раушская наб., д.4/5

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

1- с: ооращеюие блол 17 г-с. Ирщение блок 21

1-с. оорпщсяиу

Юлон 21

2-с оорощенис

1 2 J 4 9 б 7 д

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

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