Устройство для выполнения быстрого преобразования фурье

 

1. УСТРОЙСТВО ДЛЯ ВЫПОЛНЕНИЯ БЫСТРОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ, содержащее блок умножения, первый .сумматор-вычитатель,блок управления и регистр комплексной весовой функ- i ции,информационный вход которого соединен с первым входом устройс тва,а выход - с первьм входом блока умножения , о т л и ч а ю щ е е с я тем, что, с целью повьлпения быстродействия , в него введены второй сумматорвьиита т ель и четыре блока памяти, причем инфррлационные входы первого и второго блоков памяти соединены с BTOpfcw входом устройства, выход первого блока памяти - с вторьвл входом блока умножения, выхрд которого связан с информационньми входами третьего и четвертого блоков памяти, выходы которых соединены соответственно с первым и вторым информационньми вх,оцами первого сумматора-вычитатёля, выход которого подключен к первому информационному входу второго сумма .тора-вычитателя, соединенного своим выходсм с выходом устройства, пер, вый выход блсяса управления соединен с первьми входами адресов записи всех блоков пгшяти, с первьм входом адреса чтения второго блока памяти, с управляющим входом первого сумматора-вычитателя и с управляющим входом регистра комплексной весовой функции, второй выход блока управле НИН связан с первьми входами адресов чтения третьего и четвертого блоков памяти, третий выход блока управления соединен с первьм входом адреса чтения первого блока памяти, четвертый выход - с управляющим входом второго сумматора-вычитателя, пятый выход - с вторыми -входами адресов записи первого, второго и третьего блоков памяти, шестой выход - с вторыми входами адресов чтения второго, третьего и четвертого блоков памяти седьмой выход - с вторыми входами адреса чтения первого блока памяти и адреса записи четвертого блока S памяти, восьмой выход - с управляющими входами записи первого и четвертого блоков памяти, девятый выход - с упЕ авлякмцими входами записи второго и третьего блоков памяти, а вход первоначальной установки, блока управления и его вход тактовых им пульсов являются соответственно третьим и четвертьм входами устройства. 2. Устройство по п. l, о т л иа чающеес я тем, что блок управINP ления содержит трехразрядный двоичный счетчик, одноразрядный регистр, семь элементов задержки, эломейт эквивалентноети и два двухвходовых М элемента И, причем вход установки счетчика в нулевое состояние и вход установки регистра в единичное сое- .. тояние связаны с входом первоначальной установки блока,счетный вход счетчика, упр авляющий вход регистра и первые входы элементов И подключены к входу тактовых ийпульсов блока, прямые и инверсные выходы первого, второго и третьего разр.ядов счетчика и прямой выход регистра через соответствующие элементы згщержки подсоединены соответственно к первому , второму, третьему, четвертому.

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

РЕСПУБЛИК

62713 А (19) (11) 3(51) С 06 Г 15/332

ОПИСАНИЕ ИЗОБРЕТЕНИЯ );."

Н ABTOPCHOMV СВИДЕТЕЛЬСТВУ

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 2890025/18-24 (22) 03.03.80 (46) 23.12.83. Бюл. В 47 (72) А;И ° Никонов и A E.Ëåóñåíêo (71) Минский радиотехнический институт (53) 681.325.5(038,8)

{56) 1. Натент США У 3800130,. кл. 235-156, опублик-. 1973.

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

В 399859, кл.G 06 F 7/38, 1971.

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

9-598085, кл. G 06 F 15/34, 1976 (прототип). (54) (57) 1. УСТРОЙСТВО ДЛЯ BHPOJIHEНИЯ БЫСТРОГО НРЕОБРР.ЭОВРНИЯ ФУРЬЕ, содержащее блок умножения, первый ,сумматор-вычитатель,блок управления и регистр ксмплексной весовой функции,информационный вход которого соединен с первым входом устройства,а выход - с первьм входом блока умножения, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия, в него введены второй сумматор-вычитатель и четыре блока памяти, причем инфррмационные входы первого и второго блоков памяти соединены с вторьм входом устройства, вы<од первого блока памяти - с вторыми входом блока умножения, выход которого связан с информационными входами третьего и четвертого блоков памяти, выходы которых соединены соответственно с первьм и вторым информационными вхсдами первого сумматора-вычитателя, выход которого подклЮчен к первому информационному входу второго сумматора-вычитателя, соединенного своим выходом с Выходом устройства, пер вый выход .блока управления соединен с первьми входами адресов записи всех блоков памяти, с перника входом адреса чтения второго блока памяти, с управляющим входом первого сумматора-вычитателя и с управлякщим входом регистра комплексной весовой функции, второй выход блока управления связан с первьми входами адресов чтения третьего и четвертого блоков памяти, третий выход блока управления соединен с первьм входом адреса чтения первого блока памяти, четвертый выход — с управлякщим входом второго сумматора-вычитателя, пятый выход — с вторыми -входами адресов записи первого, второго и третьего блоков памяти, шестой выход — с вторыми входами адресов чтения второго, третьего и четвертого блоков памяти, седьмой выход — с вторыми входами адреса чтения первого блока памяти и адреса записи четвертого блока памяти, восьмой выход — с управляющими входами записи первого и четвертого блоков памяти, девятый выход — с упфавляющими входами записи второго и третьего блоков памяти, а вход первоначальной установки. блока управления и его вход тактовых им пульсов являются соответственно третьим и четвертым входами устройства.

2. Устройство r.o п. 1, о т л ич а ю щ е е с я тем, что блок управления содержит трехразрядный двоичный счетчик, одноразрядный регистр, семь зпементов задержки, элемент . эквивалентности и два двухвходовых элемента И, причем вход установки счетчика в нулевое состояние и вход установки регистра в единичное сос-.. тояние связаны с входом первоначальной установки блока, счетный вход счетчика, управляющий вход регистра и первые входы элементов И подключены к входу тактовых импульсов блока, прямые и инверсные выходы первого, второго и третьего разрядов счетчика и прямой выход регистра через соответствукщие элементы задержки подсоединены соответственно к первому, второму, третьему, четвертому, 1062713 пятому,.шестому и седьмому выходам блока, прямой выход первого разряда и инверсный выход второго разряда счетчика связаны со входами элемента эквивалентности, а прямой выход третьего разряда — с информационньм входом регистра, выход элемента Бсви1

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

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

Известны устройства, в которых повышение быстродействия достигается увеличением количества блоков умножения и сумматорОв, так что для каждой из четырех операций умножении при выполнении базовой операции быстрого преобразования Фурье в этих устройствах содержится свой блок умножения. Устройства содержап четыре формирователя поразрядных произведений,.два набора сумматоров, четыре регистра (11и(2 j.

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

Йедостаток этого устройства—

° низкое быстродействие, вызванное тем, что быстродействукиций блок умно» жения, наиболее дорогостоящий и объ- 35 емный блок устройства, простаивает половину времени вычислений.

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

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

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

При этом блок .управления ссдержит трехразрядный двоичный счетчик, сдноразрядный Регистр, семь элементов задержки, элемент зквиваяентнос10627l 3 ти и два двухвходовых элемента И, причем вход установки счетчика в нулевое состояние и вход установки регистра в единичное состояние связаны., с входом первоначальной установки блока, счетный вход счетчика, 5 управлякщий вход регистра и первые входы элементов И подключены к входу тактовых импульсов блока, прямые и инверсные выхсды первого, второго и третьего разрядов счетчика и прямой 1п выход регистра через соответствукщие элементы задержки подсоединены соот.ветственно к первому, второму, треть» ему, четвертому, пятому, шес*ому и седьмому выходам блока, прямой выход 15 первого разряда и инверсный выход второго разряда счетчика связаны со вхсдами элемента эквквалентностк, а прямой выход третьего разряда — с кнформационныц входом регистра, выход элемента эквивалентности псдклю- ® чен к входу инвертора и к второму входу первого элемента И, выход инвертора - к входу второго второго элемента И., а выхсды первого и вто рого элементов И подсоединены соответственно к восьмому и девятому вы.ходам блока.

На фиг. 1 представлена функциональная схема устройства; на фиг.2— то же, блока управления; на фиг.3 — ЗО вариант схемы блока памяти.

Устройство ссдержит блок 1 умножения,:.регистр 2 комплексной весовой функции, информационный вход которого соецинен с первык вхсдом 3 уст- 35 ройства, первый 4 и второй 5 блоки памяти, информационные входы которых соединены с вторым входом 6 устройства трртий блок 7 памяти, четвертый блок 8 памяти. первый и второй 4р сумматоры-вычитатели 9 н 10, блок

11 управления, вход первоначальной установки которого соединен с третьим входом . 12 устройства, а вхсд тактовых импульсов - с четвертью 4 входсм 13 устройства. Иервый выхсд

14 блока 11 управления связан с первьми входами 15 - 18 адресов записи блоков 4,5,7 и 8 памяти, с первым входом 19 адреса чтения второго блока 5 памяти, с управлякщим входом

20 первого сумматора-вычитателя 9 и с управлякщнм входом 21 регистра

2 комплексной весовой функции, второй выход 22 блока ll управления подключен к первым входам 23 и 24 адреса чтения третьего и четвертого блоков 7 и 8 памяти; третий выхсд

25 — к первому входу 26 адреса чтения первого блока 4 памяти. Четвертый выход 27 блока 11 управления со- 60 единен с управлякщим входом 28 второго сумматора-вычитателя 10, пятый выхсд 29 - с вторьв1и входами 30-32 адреса записи первого, второго к третьего блоков 4,5 и 7 памяти, шес- 65 той выход 33 - с вторьв1и входами

34 - 36 адреса чтение второго третьего и четвертого блоков 5, 7 и 8 памяти. Седьмой выход 37 блока

11 управления связан с вторым sxoдом 38 адреса чтения первого блока

4 памяти и с вторым вхсдом 39 адреса записи четвертого блока 8 памяти, восьмой выход 40 - с управляющими входами 41 и 42 записи первого и четвертого блоков 4 и 8 памяти, а девятый выход 43 - с управлякщнми входами 44 н 45 записи второго и третьего блоков 5 и 7 памяти.

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

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

Регистр комплексной весовой функции служит для хранения значений этой функции. Занесение в регистр производится по переднему фронту импульса, подаваемого íà его управлякщий вход.

Блоки памяти на четыре машинных слова предназначены для хранения исходных данных и промежуточных результатов. Они обеспечивают одйовременное и независимое выполнение операций записи и чтения информации, для чего имеют по два раздельных сдноразрядных входа адреса записи н адреса чтения и управлякщий вхсд записи. Запись производится по пе-. реднему фронту импульса, подаваемого на управлякщий вхсд зaпиcк. И>т рес записи 1 устанавливается предва- . рительно до поступления импульса записи к может изменяться только после выполнения записи.

Блок, управления по второму варианту выполнения (фиг 2} содержит трехраэрядный двоичный счетчик 46, одноразрядный регистр 47, первый

48, второф 49, третий 50, четвертый

51, пятый 52, шестой 53 и седьмой

54 элементы задержки, элемент 55 эквивалентности, инвертор 56 и первый к второй двухвходовые элементы

И57й58.

1062713

Устройство для выполнения быстрого преобразования Фурье работает

° следукщим образом.

Вначале -на вход.,12 устройства по- дается импульс первоначальной установки. Ро этому импульсу Устанавли- 5 вается в нулевое состояние счетчик

46 блока 11 управления и в единичное состояние регистр 47 этого блока. Poñëå окончания импульса первоначальной установки на вход 13 устройства подаются тактовые импульсы.

Ро этим импульсам извеняются состояния счетчика 46 блока ll управления, и на выходах блока с помощью элемента 55 эквивалентности, инвертора

56, элементов И 57 и 58 и регистра

47 вырабатываются управлякщие сигналы, определякщие режимы работы сумматоров-вычитателей 9.и 10, адреса чтения и записи блоков 4,5,6,7 и 8 памяти и моменты занесения инфор-2 мации в регистр 2 и блоки памяти.

Элементы 48 — 54 задержки необходимы для .того, чтобы адреса и информация на входах блоков памяти изменялись только после записи ииформации.

В первом цикле работы устройства, т.е. после поступления первого тактового импульса на вход 13 устройства, по переднему фронту сигнала, поступакщего с выхода 14 блока 11 управления на управлякщий вход 21 регистра 2, в этот регистр с первого входа 3 устройства заносится действительная чзсть комплексной весовой функции Rew . В первый блок 35

4 памяти по переднему фронту сигнала, поступакщего на его управлякщий вход 41 с выхода 40 блока 11 управления, записывается действительная часть первого операнда РеА. Адрес 4g ячейки памяти, по которому производится запись, поступает на вхОды

15,и 30 б.лока 4. памяти с выходов

14 и 29 блока:11 управления.

Числа Ре1 с выхода регистра 2 и 45

ReA с выхода блока 4 памяти поступают на входы блока 1 умножения, где производится их перемножение.

К концу первого цикла на выходе блока l умножения формируется произведение ReA Re%I.

В начале второго цикла в первый блок 4 памяти со входа б устрОйства по адресу, определяемому сигналами с выходов 14 и 29 блока 11 управления, записывается мнимая часть пер вого операнда 3mA. В это же время в четвертый блок 8 памяти по адресу, поступакщему на его входы 18 и 39 и определяемому сигналами с выходов

14 и 37 блока ll управления, с выхода блока 1 умножения записывается первое произведение ReA. ЯечЧ . С выхода первого блока 4 памяти, в соответствии с,адресом чтения, поступакщим на его входы, 26 и 38 с выхо- б5 дов 25 и 37 блока 11 управления, на второй вход блока 1 умножения поступает число DmA. В конце второго цикла на выходе блока 1 умножения фор мируется произведение 3пiА РеМ.

В начале третьего цикла по управякщему сигналу, поступакщему с выода 43 блока 11 управления на вход

45 третьего блока 7 памяти, в этот блок. записывается произведение 3 еА « кебич, В регис тр 2 к омплекс ной в ес овой функции в это время заносится мнимая часть комплексной весовой функции 3mw . Во второй блок 5 памяти со входа б устройства записывается действительная часть второго операнда ЙеВ. На входы блока l умножения поступают числа 3m А и 3пму,а на его выходе формируется их произведение

3mA 3m 9 °

В четвертом цикле произведение

3m A 3т и записывается в третий блок 7 памяти, во второй блок. 5 памяти со входа б устройства записывается мнимая часть второго операнда 3m8.

На выходе блока 1 умножения формируется произведение ReA- 3m%. С выхсдов третьего и четвертого блоков 7 и 8 памяти на информационные входы первого сумматора-вычитателя 9 поступают произведения QGA. Ре% и ЗЛА -3rnw, а на его выходе в соответствии с управлякщим сигналом, поступакщим на его вход 20 с выхода 14 блока 11 управления, формируется .разность

ReA. Re%-3л А 3уъ%.

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

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

28 второго сумматора-вычитателя 10, на его выходе, а следовательно, и на выходе устройства формируется первый ре зуль тат перв ой ба вовой Ьперации

ReA = йеб+йеА peW-Зт А -Зйн.

В пятом цикле в первый блок 4 памяти со входа 6 заносится действительная часть первого операнда второй базовой операциикечЧ.На выходе блока 1 умножения формируется произведение

РеА- Зп Чч, на выхсде первого сумматора-вычитателя 9 - сумма OeA Jmw+J A-Re% на выходе второго сумматора-вычитателя 10 и на выходе устройства— второй результат первой базовой операции 3eA =Зпй+РеА.3гл%4-3в Акен

В щестом и седьмом циклах работы в устройство продолжают заноситься исходные данные и формируются произведения для второй, базовой операции, а на выходах сумматоров-вычитателей и на выхсде устройства Форьиру тся третий и четвертый результаты первой базовой операции ВеВ =ReB-РеА- йе19 7 1062713 8

+QmA.3m% в шестом цикле, 3tn В "ЭвВ-яе А1ю -Зр А-ReW в седьмом цикле.

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

Вариант блока памяти (фиг. 3), используемый в данном устройстве, содержит четыре регистра 59 - 62, группы вентилей 63 - 66, группу четырехвходовых элементов ИЛИ 67, двухвходовой дешифратор 68 адреса чтения, двухвходовой дешифратор 69 адреса записи и группу вентилей 70. Информа-15 ционные входы регистров 59 - 62 соединены с информационныя входом 71 блока памяти, а выход группы элемеи- > тов ИЛИ 67 является выходом блока. .Входы дешифратора 68 адреса чтения 20 .соединены с входами 72 адреса чтения блока памяти, входы дешифратора 69 адреса записи соединены с вхсщами

73 адреса записи блока, а второй вход группы вентилей 70 - с ynpas- 25 лякщим входом 74 записи блока памяти.

- Блок памяти работает следующим образом.

Для записи информация подается 30 на инфо мационный вхсд 71 блока памяти, На входы 73 подается адрес записи На выхсде дешифратора, соответствукщем поданному адресу, вырабатывается единичный сигнал, который поступает на первый вход соответствукщего вентиля группы вентилей 70. На управлякщий вход 74 записи блока подается сигнал записи.

Ро этому сигналу на одном из выкодов группы вентилей 70 появляется единичный сигнал. Этот сигнал подается на вход занесения соответствукщего регистра 59, 60, 61 или

62. Pо переднему фронту сигнала происходит занесение информации со входа 71 в этот регистр., для чтения информации адрес ячейки подается на входы 72 адреса чтения, дешифрируется на дешифраторе

68, сигнал с выхода дешифратора, соответствукщего адресу чтения, открывает соответствукщую группу вентилей 63,64,65 или 66. Информация с выхода соответствукщего регистра 59, 60, 61 или 62 через открытую группу вентилей 63, 64, 65 или 66 и группу элементов ИЛИ 67 поступает на выхсд блока.

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

1062713

Составитель Е.Целовальников

Коррек тор М . Шарсти

Ревактор Н.Лаэаренко Text@ С.Мигунова

Закаэ 10220/51. Тираж 706 Псдпис ное

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

113035, Москва, Ж-35, Раушская наб., 4/5 .Филиал ППП Патент, г. ужгород, ул. Проектная, 4