Арифметическое устройство процессора быстрого преобразования фурье

 

Союз Советских

Социалистических

Республик

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (б} ) Дополнительное к авт. свид-ву— (22)Заявлено 05.06.81 (2!) 3320901/18-2É с присоединением заявки М— (23) Приоритет

Опубликовано 23.02.83, Бюллетень М 7 (5! )М. Ê .

G 06 F 15/332

Гевударствеевв кввпет

СССР ю девам взеврвтевк» я вткрытик (53) удК 681.3 (088.8) Дата опубликования описания 23. 02

1 (72) Авторы изобретения

6. С. Каневский, С. Э. Котов, Н.

F. А. Некрасов и О.А.Фе

Киевский ордена Ленина политехниче им. 50-летия Великой Октябрьской соци революции (71) Заявитель (5т!) АРИФМЕТИЧЕСКОЕ УСТРОЙСТВО ПРОЦЕССОРА

БЬ!СТРОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ!

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

Известно арифметическое устройство (,АУ ), используемое для выполнения. алгоритма БПФ. Устройство содержит регистры реальной и мнимой частей комплексных весовых коэффициентов, два регистра чисел, два сумматора поразрядных сумм и два сумматора чи". сел 113.

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

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

2 маторов первого уровня, восемь накапливающих сумматоров, каждый из которых состоит из сумматора и регистра сдвига (? g.

Недостатком известного устройства

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

Кроме того, в нем нельзя в течение первой итерации выполнить умножение исходного массива на весовую функцию, например, вида 1/2 (1-cos 2 2 л и /й), где п=0,1,2,...N-1. Невозможность сов35 мещения во времени выполнения первой ,итерации и умножения исходных данных на весовую функцию обусловлено тем, что в известном устройстве выполняется только три комплексных умножения, которых достаточно для выполнения базовой операции преобразования Фурье, но недостаточно для умножения на весовую функцию.

99906

Целью изобретения является увеличение быстродействия устройства.

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

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

roynn подключены к входам первого

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

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

S 999061 С элементов И четвертой группы подклю- ходного отсчета на коэффициент меточены к входам второго сумматора пер- дом накопления. вого уровня четвертой .группы, вы- Объединение выходов регистров 8.1ходы сумматоров первого уровня всех 8.8 и регистров 11.1-11.16 накаплигрупп подключены к входам соответст- 3 вающих блоков 9.1-9.4 можно осущест-. вующих регистров первого уровня, вы- вить, используя, например, регистры ходы которых подключены к информаци- с тремя состояниями на выходе, ймеюонным входам соответствующих накап- щие управляющие входы выдачи информа" ливающих сумматоров, выходы накапли- ции, или используя мультиплексоры. вающих сумматоров подключены к инфор-<в В качестве сумматоров 10.1-10.4 мационным входам соответствующих ре" накапливающих блоков 9.1-9.4 можно гистров, второго уровня, выходы всех использовать известные микросхемы регистров второго уровня подключены арифметикологических устройств, вык первым информационным входам перво- полняющих операции сложения и вычи го и второго накапливающих блоков, >> тания, а для сумматора 10.1 еще и первые информационные входы третьего операцию пропуска второго оПеранда, и четвертого накапливающих блоков т.е. сложение его с нулем. подключены к выходу. второго накапли- Структура, образуемая регистра" вающего блока, вторые информационные ми. 1.1, 1.2 множителя регистрами входы первого, второго, третьего.и 2в 2.1, 2.2 множимого,, блоками элеменчетвертого накапливающих блоков под- тов И 3.1-3.4, сумматорами первого к0ючены к выходу первого накапли- уровня 4.1, 4.2, регистрами первого вающего блока, выходы третьего и чет- уровня 5.1, 5.2, накапливающими сумвертого накапгивающих блоков подключе- маторами, состоящими из сумматоров

- ны к информационным входам первого и 6.1, 6.2 и регистров 7.1, 7.2 и ре- второго выходных регистров, выход вто- гистрами 8.1, 8.2, четырежды повторого выходного регистра подключен к ряясь, составляет первую часть схемы информационному входу третьего выход- и представляет собой комплексный умного регистра, выходы первого и треть- ножитель, выполняющий вычисления по его выходных регистров являются вы- ЗФ формуле ходами устройства, выходы блока мик- p(i)=(Rqx(i) jlmx(i)) х рви а) 1Ии("- ) ропрограммного управления подключе- =Кех(()Rew - 1п)х(1) Im w +j(Rex(I)t ны к управляющим входам регистров Imw" +Imx(i)Rew I )х сдвига множителей, регистров множимо- Регистры 2.1, 2.2 множимого приго, регистров первого и. второго уров-ц нимают исходный отсчет, 2.1 - дейстней, накапливающих сумматоров, накап- вительную часть. Rex(i), 2.2 - мни- . ливающих блоков и выходных регистров. мую часть Imx(i). Регистры 1.1, 1.2

На чертеже представлена функцио- множителя принимают весовой коэффинальная схема арифметического устрой- .циент, 1. 1- действительную часть ства процессора быстрого преобразо- щ R« 1. 2.- мнимую часть lm w" .йя е с вания Фурье.. первый вход сумматора 4.1 приходят частичные произведения Rex(i) Веи1

Устройство содержит регистры 1. 1". на второй -. частичные произведения 1.8 сдвига множителя, регистры 2.1- Imx(i) Imw . Ha выходе сумматора

1t

2.8 множимого, блоки элементов И. 3.1- - 4.1 получается разность этих час3.16, сумматоры 4,1-4.8 первого уров- тичных произведений. ня, регистры 5. 1-5.8 первого уровня, На первый вход сумматора 4.2 присумматоры 6. 1-6.8 и регистры сдвига ходят .частичные произведения 1mx(I)

7. 1-7.8 входящие в состав накапли-. — -Rew i, на второй - частичные произ- вающих сумматоров, регистры 8.1-8.8 ведения йех(т) lmw, на выходе сумвторого уровня, накапливающие блоки матора 4.2 получается сумма этих

9.1-9.4, состоящие из сумматоров частичных произведений. .10, 1-10,4 и блоков регистров 11.1- Затем выполняется накопление сумм

, 1 1 16 выходные регистры 1 2 . 1 -1 2- 3 р частичных произведений на накапливаю блок 13 микропрограммного управле- щих сумматорах 6.1, 7.1 и 6.2, 7,2 ния. и на регистры 8.1, 8.2 принимаются

Регистры 1.1-1.8 сдвига множителя действительная Вер(1) и мнимая обеспечивают последовательный анализ Imp(I) части комплексного произверазрядов множителя при умножении вы" 4eHHHR Rep(I) " в 8. 1, Imp(I) в 8.2.

7 9990

Вторая часть устройства, состоящая из четырех накапливающих блоков .9.1-9.4 и трех выходных регистров

12 ° 1-12.3 представляет собой схему суммирования, которая формирует окон- 5 чательные результаты преобразования в соответствии с выражением

x(i) =pep(i)+ Rep(i+2))+PRep(i+I)+

+ Rep(i+3)p j+(Imp(i)+Imp(i+2)) +

+(Jtmp(I+1)+ tmp(I+3))) Ю х(i+1) = (Rep(i)-Rep(i+2)) -I Imp(i+1)-tmp(i+3))+j ((Rep(i+I)-Rep(i+3)j +

+ (!а!1(!)-Imp(i+2)) х(i+2)=(Rep(i)+ Rep(i+2)j

"3Rep(i+I) + Rep(!+3))+j p(imp(i) +

+lmp(+2)1-(Imp(i+1)+ Imp(i+3))3

x(i+3) =t Rep(i ) -Rep(i+2))+)Imp(I+1)- Imp(i+1)3 -j f(Rep(i+1) -Rep(i+3})-(tnp(i)-Imp(i+2})J где p(i),p(i+1), p(i+2),p(i+3) - ком- 2в плексные произведения исходных отсчетов на весовые коэффициенты;.

Re(...) - действительная часть числа;

Im(...) - мнимая часть числа;

x(i),x(i+1),x(i+2},x(i+3) -результаты преобразования °

Блок 13 микропрограммного управления может состоять из генератора синхронизирующих импульсов, счетчика Ý0 тактов и блока памяти микрокоманд (,ПЗУ }, адресные входы которого соединены с выходами соответствующих разрядов счетчика тактов, а выходы являются выходами блока микропрограм-3g много управления.

Поскольку все составные части арифметического устройства, кроме сумматора 10 1, должны работать не более чем в двух режимах (сложение вычи» gg тание, прием - запрет приема, выдача - запрет выдачи }, для каждого управляющего сигнала достаточно одного разряда. Для сумматора 10.1 требуется два управляющих разряда, так как он должен работать в трех. режимах: сложение, вычитание второго операнда, пропуск второго операнда (сложение его с нулем }.

Рассмотрим работу АУ при выполнении базовой операции, Для примера рассмотрим случай, когда весовые коэффициенты четырехразрядные, т,е. для умножения требуется четыре такта.

Поскольку комплексные исходные отсчеты х(i) принимаются в умножители последовательно со сдвигом на .такт,.то результаты комплексных умно61 8 жений р(i)=x(!)w ) принимаются=e выходные регистры умножителей тоже со сдвигом на такт, причем в каждом такте принимаются параллельно действительная Rep(i) и мнимая Imp(i) части комплексных произведений. Организация схемы суммирования предполагает последовательный. поток действительных и мнимых частей комплексных произведений, поэтому за один такт схема суммирования должна успеть принять два числа: Pep(i) и lmp(i) с тем, чтобы в следующем такте принять действительную Rep(i+1) и мнимую Imn(i+1) части следующего комплексного произведения, Таким образом, длительность, такта работы схемы суммирования в два раза меньые, чем временной интервал между приемом комплексных отсчетов в выходные регистры соседних умножителей

Поэтому работу схемы суммирования мы будем рассматривать по половинам такта. Будем считать, что прием во все регистры осуществляется по началу такта 1,для схемы суммирования - по началу такта и началу второй половины такта }.

В нулевом такте весовой коэффициент ио принимается в регистры 1. 1 множителя (Rew< ) и 1.2 (Imw ),а исходный отсчет х(о) - в регистры

2.1 множимого (Rex(о)) и 2.2(lmx(о) первого умножителя и выполняется первый такт умножения.

В первом такте весовой коэффициент

@" принимается в регистры 1.3 множителя (Rew ) и 1.4 (tm«" ), а исходный отсчет х(1) — в регистры 2.3 множимого (Rex (1)) и 2.4 (lmx(l)), выполняется первый такт умножения во втором и второй такт в первом умножителях.

Во втором такте принимается весовой коэффициент w2 э регистры 1.5 (Rew2i ) и .1.6 (!вж !, исходный отсчет х(2) - s регистры 2.5 (Rex(2) и 2.6 (Imx(2) и выполняется первый такт умножения в третьем умножителе, второй и третий соответственно во втором и первом умножителях.

В третьем такте весовой коэффициент иЧ записывается в регистры .б (реиР! и 1.8 (tmw i ), исходный отсчет х(3) записывается в регистры 2.7 (Rex(3}) и 2.8 (Мх(3}) и выполняются первый, второй, третий и четвертый такты умножения соответственно в .четвертом, третьем, втором и первом умножителях.

9 999061 10

В четвертом такте в перзом умножи- мая часть 1шр10) нулевооо комплекснотеле вычисленные суммы последних дей- го произведения записывается в рествительных частичных произведений гистр 11.2 и из регистра 8. 3 вы-. нулевого комплексного произведения дается действительная часть первого (R(0)), т.е. результаты последнего s комплексного произведения Rep(1) и четвертого такта умножения, прини- сумматор 10.1 продолжает выполнять маются в регистры первого уровня Р.1 опеРацию пропуска второго операнда, и .2, следующие весовой коэффициент во второй половине шестого такта в и исходный отсчет х(4) принимаются регистр 11.3 принимается действитвпь1в регистры 1.1 (Rew ), .1.2(lmw4R) >а ная часть Кер(1). первого комплексного . 2.1(Рех(4)), 2.2(lmx(4)) и выполняет-. произведения, из регистра 8.4 выдася первый такт умножения в первом ется Imp(1) и сумматор 10.1 выполняумножителе и четвертый, третий и вто- ет операцию пропуска второго операнрой такты соответственно во втором, да. третьем и четвертом умножителях. !З В седьмом такте второе комплекс-!

В пятом такте нулевое комплексное ное произведение р (2 ) принимается произведение р(0 ) принимается в выход в выходные регистры 8.5 (Rep(2)) и ные регистры первого умножителя 8.1 8.6(lmp(2)) третьего умножителя, pe(Rep(0) и 8.2(lmp(0), в первом умно- зультаты последнего, четвертого, жителе выполняется второй такт умно- 20 такта умножения принимаются в регистжения, результаты четвертого такта ры первого уровня 5 7 и 5 ° 8 четвертоумножения записываются в регистры 5.3 го умножителя весовой коэффициент и 5.4 первого уровня второго умножи- и"1 принимается в регистры 1.7(Rewõ ) теля, весовой коэффициент ы - 1 прини- и 1.8(lmw . ), исходный отсчет х 7мается в регистры 1.3 (Rew+ ) 1.4 И в регистры 2.7 (Rex(7)) и 2.8(lmx(7)) (Imw 1 ), исходный отсчет x(5) - в ре- четвертого умножителя, выполняются де} гистры 2.3.(Rex(5)) и 3.4(lmx(5)) вто- первый, второй, третий и четвертый рого умножителя и выполняются первый, такты умножения соответственно в четчетвертый и третий такты умножения во вертом, третьем, втором и первом ум" втором, третвем и четвертом умножи- зв ножителях. Кроме того, в первой полотелях соответственно. Кроме того, в вине седьмого такта в регистр 11.4 первой половине пятого такта выдает- принимается мнимая часть Imp(l) перся содержимое регистра 8.1, т.е. вого комплексного произведения, из

Rep(0), сумматор 10. l выполняет сло- регистра 8.5 выдается действительжение второго операнда с нулем. Во ная часть Rep(2) второго комплексновторой половине пятого такта Rep(0) го произведения, из регистра 11.1 выпринимается в регистр 11.1 из регист- дается Rep(0), сумматор 10.! выполра 8.2 выдается мнимая часть 1шр(0) няет операцию сложения, а сумматор нулевого комплексного произведения и 10.2 выполняет операцию вычитания сумматор 10.1 продолжает выполнять 4а второго операнда из первого, т.е. на операцию пропуска второго операнда выходе сумматора 10.1 получаем Rep(0) (сложение с нулем) ° +Rep(2), на выходе сумматора 10.2В шестом такте первое комплексное Rep(0}-Rep(2). произведение р(1 ) принимается в вы- Во второй половине седьмого такходные регистры 8.3 (Rep(1)) и 8а4 та в регистры 11.1 и 11. 5 принимает". (Imp(1)) второго умножителя, резуль- . ся соответственно Рер(0) + Rep(2) и таты последнего, четвертого такта ум- Rep(0) - Rep(2), из регистра 8.6 выножения принимаются в регистры 5.5 и дается мнимая часть Imp(2} второго

5....6 третьего умножителя, в четвертом комплексного произведения, из регистпервом и втором умножителях выполняют- ра 11.2 выдается Imp(0), сумматор ся соответственно четвертый, третий и 10 ° 1 выполняет операцию сложения, на второй такту умножения, весовой коэф- его выходе получаем Imp(0) +Imp(2), фициент w 1 принимается в регистры

e,e) сумматор 10.2 выполняет операцию вы" .1.5 (Rew ) и 1.6 (1пы 6 ), исход- читания второго операнда и íà eto ный отсчетх(6)- врегистры 2.5(Rex(6)) 1: выходе получаем 1шр(0)- 11 1р(2).

33 2 6 (!ах(6))третьего умножителя и вы- В восьмом такте третье комплексное полняется первый такт умножения- в произведение р (3) принимается в вы третьем умножителе. Кроме того, в ходные регистры 8.7 (йер(3)и 8,8 " первой половине шестого такта мни- (1шр(3)) четвертого умножителя, ре999061

11

» эультаты четвертого такта умножения принимаются в регистры 5.1 и 5.2 первого умножителя, весовой коэффициент, w принимается в регистры 1.1(РеФ и 1.2(1 пив ),, а исходный отсчет х(6) - в регистры 2.1 (Rex(8)) и

2 ° 2 (Imx(8)) первого умножителя, выполняются первый, второй, третий и четвертый такты умножения соответственно в первом, четвертом, третьем 10 и втором умножителях. Кроме того, в первой половине восьмого такта в регистр 11.2 принимается результат операции на сумматоре 10.1 Imp(0) +

4. !е(2), а в регистр 11.6 - 1й результат lmp(0) — Imp(2), из регистра 8.7 выдается действительная часть

Rep(3) третьего комплексного произведения, из, регистра 11.3 выдается

Rep(1), сумматор 10.1 выполняет one- 20 рацию вычитания второго операнда иэ первого, а сумматор 10.2 - операцию сложения, т.е. на выходе 10.1 получаем Rep(1) - Rep(3), а на выходе

10.2 получим Rep(1) +Rep(3), во вто- И рой половине восьмого такта Рер(1)Рер(3) принимается в регистр 11.3, а Rep(l) +Rep(3) - в регистр 11.7, из регистра 8.8 выдается мнимая часть

Imp(3) третьего комплексного произ- зф ведения, из регистра 11.4 выдается

Imp(l), сумматор 10.1 выполняет операцию вычитания второго операнда из первого (1щр(1) -. Imp(3)» а сумматор 10.2 -. операцию сложения (Imp(I)a3

+Imp(3)).

Далее работа умножителей аналогичная, поэтому рассмотрим только работу схемы суммирования.

8 первой половине девятого такта в регистры 11.4 и 11.8 принимаются, результаты операций на сумматорах

10.1 и 10.2, lmp(1) - Imp(3) -в 11.4., Imp(1) +Imp(3) - в 11.8, из регистра

8. 1 выдается действительная часть

Rep(4) четвертого комплексного произведения - первого произведения следующей базовой операции, сумматор 10.1 выполняет операцию пропуска второго операнда, из регистра 11.1 выдается

Rep(0) +Rep(2), из регистра 11.7 выМ дается Rep(l) +Rep(3), сумматор 10.3 выполняет операцию вычитания второго операнда иэ первого, а сумматор 10.4операцию сложения, в результате на выходе 10.3 получаем Rex(2)=(Rep(0)+

Рер(2)3 -(Рер(1)+ Rep(3)g, а на вы: ходе 10.4 получаем Rex(0) =(Rep(0) +

+Рею(2))о :fRep(1)a Rep(3)) .

12

Во второй половине девятого такта в регистры 11.9 и 11,13 принимаются соответственно Rex(2) и Rex(0) в регистр 11. I записывается Рер(4), из регистра 8.2 выделяется мнимая часть !вп(4) четвертого комплексного произведения, сумматор 10.1 выполняет операцию пропуска второго операнда, на регистры Il.5-11,8 накапливающего блока 9.2 подается сигнал запрета приема. Из регистра 11,2 выдается Imp(0) +Imp(2), из регистра

11.8 выдается imp(1) +Imp(3), сумматор 10.3 выполняет операцию вычитания второго операнда, а сумматор

10.4-- операцию сложения, т.е. на выходе 10.3 получаем t«(2)

=fImx(0)a Imp(2)) -(imp(1) aImp(3)), а на выходе 10.4 получаем Imx(0)

= pimp(0)a Imp(2)j +tImp(I)a Imp(3)3 .

В первой половине десятого такта в регистры 11.10 и 11.14 принимаются соответственно Imx(2) и imx(0), в регистр 11 2 принимается Imp(4) из регистра 8.3 выдается действительная часть Rep(5) пятого комплексного произведения, сумматор 10.1 выполняет операцию пропуска второго операнда,. на регистрах 11.5 - 11.8 сохраняет- ся сигнал запрета записи из регистра 11.3 выдается Rep(1)

-фер(3), а из регистра 11.6 выдается Imp(0)-lmp(2), сумматор 10 ° 3 выполняет операцию сложения и в результате на его выходе получаем

lmx(1)=(!гпр(0)-Imp(2)+ Rep(1)-Rep(3)jq сумматор 10.4 выполняет операцию вычитания второго операнда из первого и на его выходе получаем Imx(3).-=

=(1ар(0) - 1п1р(2)) -(Рер(1) - Рер(3)) иэ регистра 11.13 выдается Rex(0).

Во второй половине десятого такта в регистры 11.11 и 11.15 принимаются соответственно Imx(l) и Imx(3), в регистр 11.3 принимается Rep(5), в регистр 12.2 принимается Rex(0), из регистра 3.4 выдается мнимая часть Imp(5) пятого комплексного произведения, сумматор 10.1 выполняет операцию пропуска второго операнда, из регистра 11.4 выдается

linp(1) - Imp(3), из регистра 11,5 выдается Рер(0) - Rep(2), на регистрах 11 ° 5-11.8 сохраняется сигнал запрета записи, сумматор 10.3 выполняет операцию сложения, на его выходе получаем Rex(3) =t.imp(1) - Imp(3)) + ,+ Rep(0) - Rep(2)), сумматор 10.4 выполняет операцию вычитания второ13 . 9990 го операнда,иэ первого и на его вы- ходе получаем Рех(1) =(Imp(1)

Imp(3))+pep(0) = Rep(2)g, иэ регистра 11.4 выдается Imx(0) .

В первой половине одиннадцатого э такта в регистры 11. 12 и 11.!6 -принимаются соответственно Rex(3) и

Рех(1), в,регистр 11.4 принимается

1вр(5), в регистр 12.1 принимается

Imp(5), в регистр 12.1 принимается >6

lmx(0), а в регистр 12.3 - Rex(0), из регистра 8,5 выдается действительная часть Rep(5) шестого комплексного произведе.<ия, иэ регистра 11.1 выдается действительная часть Rep(4), сумматор 10.1 выполняет операцию сложения, сумматор 10.2 выполняет операцию .вычитания второго операнда, с регистров l!.5-11.8 снимается сигнал запрета записи из регистра 11.6 26 выдается Rex(1).

Во второй половине одиннадцатого. такта в регистры 11.1 и !1.5 прини. маются соответственно Rep(4)+ Rep(6) и Rep(4)-Reo(6). в регистр 12.2 при- И нимается Rex(1), на регистры 11.9-!

1.16 подается сигнал запрета записи, из регистра 12.2 выдается !ар(4),из регистра 8.6 выдается Imp(6), сумма тор 10.1 выполняет операцию. сложения 30 и на его выходе получаем Imp(4) +

+Imp(6), сумматор 10.2 выполняет операцию вычитания второго операнда из первого и на его выходе получаем

Imp(4) — lmp(6), из регистра 11.11 выдается Imx(1).

В первой половине двенадцатого такта в регистры 11..2 и 11.6 при- нимаются соответственно lmp(4) + .+Imp(6) и lmp(4) -, Imp(6) в регистр

12.1 принимается Imx(1),, а в ре"гистр 2,3 - Rex(1), иэ регистра 8.7 выдается Rep(7), из регистра 1!.-3 выдается Rep(5), сумматор 10.1 вы. полняет операцию вычитания второго операнда, на его выходе получаем

Rep(5) - Rep(7), сумматор 10.2 выполняет операцию сложения и на его выходе получаем Rep(5)+ Rep(7), иэ регистра ll.9 выдается Рех(2), на регистрах 1I.9-11.16 сохраняется сигнал запрета записи.

Во второй половине двендацатого такта в регистры 11.3 и 11.7 принимаются соответственно Rep(5) - Rep(7) и Rep(5)+ Rep(7), в регистр 12.2 npuSf нимается Rex(2), из регистра 8.6 выдается Imp(7) сумматор 10.1 выполняет операцию вычитания второго one61 14 ранда и на выходе получаем 1ор(5)Imp(7) сумматор 10.2 выполняет операцию сложения и на его. выходе noslyчаем Imp(5) + Imp(7), из регистра

11.I0 выдается lmx(2), В первой половине тринадцатого такта в регистры 11.4 и !1.8 принимаются соответственно Imp(5) - Imp(7) и Imp(5)+ Imp(7), в регистр 12. l принимается lmx(2), в регистр 12.3 принимается Rex(2), из регистра 8.1 вы" дается действительная часть Rep(8) восьмого комплексного произведения, сумматор 10.1 выполняет операцию пропуска второго операнда, из регистра

11.12 выдается Rex(3), из регистра .

11.1 выдается Rep(4)+:Råp(6), из ре-, гистра 11.7 выдается Rep(5)+ Rep(7) сумматор 10,3 выполняет операцию вычитания второго операнда, на его выходе получаем Rex(6) =(Rep(4)+ Rep(6))-(Rep (5)+ Rep(7)1, сумматор !0.4 выполняет операцию сложения и íà его выходе получаем Rex(4) = )Rep(4)+

+Rep(6)j +t Rep(5)+ Rep(7)) °

Во второй половине тринадцатого. такта в регистр 11.1 принимается

Rep(8), в регистры 11.9"и 11.13 принимаются соответственно Rex(6) и

Rex(4), на регистры 11.5-11.8 по" дается сигнал запрета записи, в регистр 12.2 принимается Rex(3), из регистра 8.2 выдается мнимая часть

Imp(8) восьмого комплексного произведения, сумматор 10.1 продолжает выполнять операцию пропуска. второго операнда, из регистра Il.2 выдается Imp(4) + Imp(6), из регистра 11.8 выдается Imp(5)+ Imp(7), сумматор

10.3 выполняет операцию вычитания второго операнда, на его выходе получаем 1ях(6) = (!шр(4)+ !тр(6Ц

- {, Imp(5) + !вр(7Ц, из регистра 1! ° 5 выдается Imx(3).

В первой половине четырнадцатого . такта Rex(3) принимается в регистр

12.3, а в регистр 12. I запишется

Imx(3), Таким образом, получают на первом и втором выходах (выходах

Д и Е ) устройства четвертый преоб" разованный отсчет, т.е. последний из первой базовой операции. Далее работа всего устройства аналогична.

Время выполнения преобразования

Фурье над массивом М комплексных отсчетов в предлагаемом устройстве составляет 1

Т = 4 ht ° Н ° 1оо2М, где Дй - длительность такта.

999061 16

В известном устройстве

= (Т л+ Тмми1 где Т „, Т мн - время выполнения операций сложения и умножения.

Таким образом, производительность предлагаемого устройства повышается

Т„+т в Qраз, гдеЯ= мн

4nt

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

Арифметическое устройство процессора быстрого преобразования Фурье; содержащее три группы по два регистра сдвига множителя, четыре группы по два регистра множимого, три группы по четыре блока элементов И, три группы по два сумматора первого уровня, четыре группы по два накапливающих сумматора, каждый из которых состойт из сумматора и регистра сдвига, причем первый вход сумматора является информационным входом соответствующего накапливающего сумматора, вы- И ход сумматора является выходом накапливающего сумматора и подключен к параллельному входу регистра сдвига в соответствующем накапливающем суммато.. ре, параллельный выход регистра сдви- lO га подключен к второму входу соответствующего сумматора, а вход управления сдвигом регистра сдвига является управляющим входом соответст-. вующего накапливающего сумматора, па- З$ раллельные входы первого и второго регистров сдвига множителей, первой, второй и третьей групп подключены соответственно к входу действительной и мнимой частей весового коэффициен- 4 та устройства, входы первого и второго регистров множимого каждой группы подключены соответственно к входу действительной и мнимой частей отсчета входного сигнала устройства, вы-4$ ход первого регистра множимого первой, второй и третьей групп подключен к информационному входу первого и второго блоков элементов И соответствующей группы, выход второго регистра множимого первой, второй и третьей групп подключен к информационному входу третьего и четвертого блоков эле ы ментов И соответствующей группы, последовательный выход первого регистра

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

999 гистра сдвига множителя четвертой группы подключен к управляющим входам второго и четвертого блоков элементов И четвертой группы, выходы первого и четвертого блоков элемен- % тов. И четвертой группы подключены к входам первого сумматора первого уровня четвертой группы, выходы второго и третьего блоков элементов И четвертой группы подключены к входам второго сумматора первого уровня четвертой группы, выходы сумматоров первого уровня всех групп подключены к входам соответствующих регистров пер- . вого уровня, выходы которых подключе-tS ны к информационйым входам соответствующих накапливающих сумматоров, выходы накапливающих сумматоров подключены к информационным входам соответствующих регистров второго уровня з выходы всех регистров второго уровня подключены к первым информационным входам первого и второго накапливающих блоков, первые информационные входы третьего и четвертого накапли- вающих блоков подключены к выходу второго накапливающего блока, вторые информационные входы первого, второго, третьего и четвертого накапливаю061 18 щих блоков подключены к выходу перcoro накапливающего блока, выходы третьего и четвертого накапливающих блоков подключены к информационным входам первого и второго выходных регистров, выход второго выходного регистра подключен к информационному входу третьего выходного регистра, выходы первого .и третьего выходных регистров являются выходами устройства, выходы блока микропрограммного управления подключены к управляющим входам регистров сдвига множителей, регистров множимого,регистров первого и второго уровней, накапливаю" щих сумматоров, накапливающих бгоков и выходных регистров.

Источники информации, принятые во внимание при экспертизе

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

N 467356, кл.G 06 F 15/332, 1975.

2. Gottlieb Рaul, Lorenzo Leonard J. d.e. Parallel data Stems

and serial arithmetic for Fourier

transform Process. -"IEEE Transac"

tions on Acoust. Speech and Signal

Process", 1974, Н 2, р.11.1-!17 (прототип).