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

СОЮЗ СОВЕТСКИХсеиалаиисиикЩСПУБЛИК 62713 А 09) И 1) 3(51) С 06 Г 15/33 с. ОПИСАНИЕ ИЗОБРЕТЕНИЯ ) ТВ ТОРСНОМУ СВИДЕТЕЛ яти, умма- вхоОСУДАРСТВЕННЫЙ КОМИТЕТ СССРО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИИ(56) 1. Натент С(А У 3800130,кл. 235-156, опублик 1973.2. Рвторское свидетельство СССРВ 399859, кл.б 06 Г 7/38, 1971.3. Рвторское свидетельство СССР9 598085, кл. 0 06 Г 15/34, 1976(прототип),(54)(57) 1. УСТРОЙСТВО ДЛЯ ВЬПОЛНЕНИЯ БЫСТРОГО НРЕОБРР.ЭОВРНИЯ ФУРЬЕ, содержащее блок умножения, первый ,сумматор-вычитатель,блок управления и регистр ксеиплексной весовой функции,информационный вход которого соединен с первым входом устройства,а выход - с первьи входом блока умножения, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия, в него введены второй сумматор-вычитатель и четыре блока памяти, причем инфррмационные входы первого и второго блоков памяти соединены с вторым входом устройства, высод первого блока памяти - с вторыми входом блока умножения, выход которого связан с информационньаки входами третьего н четвертого блоков памяти, выходы которых соединены соответственно с первьи и вторым информационньии вхсдами первого сумматора-вычитателя, выход которого подклэ)чен к первому информационному входу второго сумматора-вычитателя, соединенного своимвыходом с выходом устройства, пер .вый выход .блока управления соединенс первыми входами адресов записивсех блоков памяти, с перника входом. адреса чтения второго блока пам с управляющим входом первого с тора-вычитателя и с управлякщим дом регистра комплексной весовой функции, второй выход блока управления связан с первьми входами адресов чтения третьего и четвертого блоков памяти, третий выход блока управления соединен с первью входом адреса чтения первого блока памяти четвертый выход - с управлякщим входом второго сумматора-вычитателя, пятый выход - с вторыми входами адресов записи первого, второго и третьего блоков памяти, шестой выход - с вторьаии входами адресов чтения второго, третьего и четвертого блоков памяти, седьмой выход - с вторыми входамиадреса чтения первого блока памяти и адреса записи четвертого блока памяти, восьмой выход - с управляющими входами записи первого и четвертого блоков памяти, девятый выход - с уп)йвляющими входами записи второго и третьего блоков памяти, а вход первоначальной установки. блока управления и его вход тактовых им: пульсов являются соответственно третьим и четвертым входами устройства.2. Устройство го и. 1, о т л ич а ю щ е е с я тем, что блок управления содержит трехразрядный двоичный счетчик, одноразрядный регистр, семь зпементов задержки элементэквивалентности и два двухвходовых элемента И, причем вход установки счетчика в нулевое состояние и вход установки регистра в единичное состояние связаны с входом первоначальной установки блока, счетный вход счетчика, управляющий вход регистра и первые входы элементов И подключены к входу тактовых импульсов блока, прямые и инверсные выходы первого, второго и третьего разрядов счетчика и прямой выход регистра через соответствукщие элементы задержки подсоединены соответственно к первому, второму, третьему, четвертому,1062713 пятому, шестому и седьмому выходамблока, прямой выход первого разрядаи инверсный выход второго разрядасчетчика связаны со входами элементаэквивалентности, а прямой выходтретьего разряда - с информационнымвходом регистра, выход элемента жви 1Изобретение, относится к вычислительной технике, в частности к устройствам цифровой обработки сигналов методами быстрого преобразования Фурье, и может быть использовано в цифровых фильтрах,. генераторах случайных процессов, анализаторах спектра й других устройствах.Нри,цифровой обработке сигналов в реальйЬм масштабе времени особое значение приобретает быстродействие вычислительного устройства.Известны устройства, в которых повышение быстродействия достигаетсяувеличением количества блоков умножения и сумматоров, так что для каждой из четырех операций умножениипри выполнении базовой операции быстрого преобразования Фурье в этих устройствах содержится свой блок умножения, устройства содержап четыре 2 О формирователя поразрядных произведений,.два набора сумматоров, четыре регистра 11 и 1,2 3.Наиболее близким к изобретению по технической сущности и достигаемо му результату является устройство для выполнения быстрого преобразования Фурье, содержащее бистродействукций блок умножения, сумматор-вычитатель, регистр комплексной весовой ЗО функции и блок умножения 3 3.Йедостаток этого устройства -низкое быстродействие, вызванноетем, что быстродействукюций блок умножения, наиболее дорогостоящий и объемный блок устройства, простаиваетполовину времени вычислений.Целью изобретения является повЫшение быстродействия устройства эасчет совмещения во времени операций, д)выполняемых его различными блоками.Поставленная цель достигаетсятем, что в устройство для выполнениябьегтрого.преобразования Фурье, содержащее блок умножения, первый сумматорвычитатель, блок управленияи регистр комплексной весовой Функции, информационный вход которогосоединен с первым входом устройства, а выход -с первым входом блока умножения, введены второй сумматорвалентности подключен к вкоду инвертора и к второму входу первого элемента И, выход инвертора - к второму входу второго элемента И, а выходы первого и второго элементов И подсоединены соответственно к восьмомуи девятому выходам блока. 2вычитатель и четыре блока памяти, причем информационные входи первого и второго блоков памяти соединены с вторым входом устройства, выход первого блока памяти -. с вторым входом блока умножения, выход которого связан с информационными входами третьего и.четвертого блоков памяти, выходы которых соединены соответственно с первьм н вторьщ информационныки входами первого сумматора-вычитателя, выход которого подключен к первому информационному входу второго сумматора-вычитателя, соединенного своим выходом с выхо" дом устройства, первый выход блока управления соединен с первыми входа" ми адресов записи всех блоков памя-ти, с первым входом адреса чтения второго блока памяти, с управляющим входом первого сумматора-вычитателя н с управляющим входом регистра комплексной весовой функции, второй выход блока управления связан с первыми входами адресов чтения третьего и четвертого блоков памяти, третий выход блока управления соединен с первым входсе адреса чтения первого блока памяти, четвертый выход - с управлвецим входом второго суьщатора-вычитателя, пятый выксдс вторыми входами адресов записи первого, второго и третьего блоков памяти, шестой выход - с вторыми входами адресов чтения второго, третьего и четвертого блоков памяти, седьмой выход - с вторыми входами адреса чтения первого блока памяти и адреса записи четвертого блока памяти, восьмой выход - с управляющими входами записи первого и четвертого блоков памяти, девятый выход - с управляющими входами записи . второго и третьего блоков памяти, а вход первоначальной установки блока управления и его вход тактовых им-пульсов являются соответственно третьим и четвертьв входами устройства.При этом блок,управления содержит трехразрядный двоичный счетчик, одноразрядный регистр, семь элементов задержки, элемент эквивалентности и два двухвходовых элемента И, причем вход установки счетчика в нулевое состояние и вход установки регистра в единичное состояние связаны,с входом первоначальной установки блока, счетный вход счетчика, 5 управлякщий вход регистра и первые входы элементов И подключены к входу тактовых импульсов блока, прямые и инверсные выхсды первого, второго и третьего разрядов счетчика и прямой щ выход регистра через соответствукщие элементы задержки подсоединены соот.- ветственно к первому, второму, треть ему, четвертому, пятому, шестому и седьмому выходам блока, прямой выход 15 первого разряда и инверсный выход второго разряда счетчика связаны со входами элемента эквивалентности, а прямой выход третьего разряда - с информационныц входом регистра, выход элемента эквивалентности подклю- ф чен к входу инвертора и к второму входу первого элемента И, выход инвертора - к входу второго второго элемента И., а выходы первого и вто рого элементов И подсоединены соответственно к восьмому и девятому вы.ходам блокаНа Фиг. 1 представлена функциональная схема устройства 1 на Фиг,2 - то же, блока управления; на Фиг.3 - ЗО вариант схемы блока памяти.Устройство содержит блок 1 умножения,.регистр 2 комплексной весовой Функции, информационный вход которого соецинен с первык входом 3 уст ройства, первый 4 и второй 5 блоки памяти, информационные входы которых соединены с вторым входом 6 устройства трртий блок 7 памяти, четвертый блок 8 памяти, первый и второй сумматоры-вычитатели 9 н 10, блок 11 управления, вход первоначальной установки которого соединен с третьим входом 12 устройства, а входтактовых импульсов - с четвертью входсм 13 устройства. Иервый выход 14 блока 11 управления связан с первьми входами 15 - 18 адресов записи блоков 4,5,7 и 8 памяти, с первьм входом 19 адреса чтения второго блока 5 памяти, с управлякщим входом20 первого сумматора-вычитателя 9 и с управлякщнм входом 21 регистра2 комплексной весовой функции, второй выход 22 блока 11 управления подключен к первым входам 23 и 24 адреса чтения третьего и четвертого блоков 7 и 8 памяти; третий выход 25 - к первому входу 26 адреса чтения первого блока 4 памяти. Четвертый выход 27 блока 11 управления со- еО единен с управлякщим входом 28 второго сумматора-вычитателя 10, пятый выход 29 - с вторьзки входами 30-32 адреса записи первого, второго и третьего блоков 4,5 и 7 памяти, шес той выход 33 - с вторыми входами 34 - 36 адреса чтение второго третьего и четвертого блоков 5, 7 и 8 памяти. Седьмой выход 37 блока 11 управления связан с вторым входом 38 адреса чтения первого блока 4 памяти и с вторым входом 39 адреса записи четвертого блока 8 памяти, восьмой выход 40 - с управляющими входами 41 и 42 записи первого и четвертого блоков 4 и 8 памяти, а девятый выход 43 - с управлякщнми входами 44 н 45 записи второго и третьего блоков 5 и 7 памяти.В качестве блока умножения в устройстве может быть использован быстродействунхаий матричный умножитель, обеспечивакщий выполнение операции умножения за один машинный цикл, т.е. за отрезок времени между передним Фронтом одного из тактовых импульсов и передним фронтом последующего тактового импульса.Сумматоры-вычитатели производят сложнение или вычитание чисел, поступакщих на их информационные входы, в зависимости от сигнала, поступающего на управлякщий вход. Ври единичном управлякщем сигнале выполняется сложение, а при нулевом - вычитание, причем число, поступакицее по первому информационному входу . вычитается из числа, поступакицего по второму информационному входу,Регистр комплексной весовой функции служит для хранения значенийэтой Функции. Занесение в регистрпроизводится по переднему фронтуимпульса, подаваемого на его управлякиций вхсд.Блоки памяти на четыре машинныхслова предназначены для храненияисходных данных и прсиежуточных результатов. Они обеспечивают одйовременное и независимое выполнениеопераций записи и чтения инФормации,для чего имеют по два раздельныходноразрядных входа адреса записин адреса чтения и управлякщий входзаписи. Запись производится по пе-.реднему фронту импульса, подаваемого на управлякщий входзаписи. адрес записиустанавливается предва-,рительйо до поступления импульсазаписи в может изменяться толькопосле выполнения записи,Блок , управления по второму варианту выполнения (Фиг 2) содеркит трехраэрядный двоичный счетчик 46, одноразрядный регистр 47, первый 48, второ 9 49, третий 50, четвертый 51, пятый 52, шестой 53 и седьмой 54 элементы задержки, элемент 55 эквивалентности, инвертор 56 и первый и второй двухвходовые элементы И 57 й 58.Устройство для выполнения быстрого преобразования Фурье работаетследукщим образом.Вначале на вход.,12 устройства по-дается импульс первоначальной установки. Но этому импульсу устанавливается в нулевое состояние счетчик46 блока 11 управления и в единичное состояние регистр 47 этого блока. Восле окончания импульса первоначальной установки на вход 13 уст"ройства подаются тактовые импульсы.Но этим импульсам извеняются состояния счетчика 46 блока 11 управления,и на выходах блока с помощью элемента 55 эквивалентности, инвертора56, элементов И 57 и 58 и регистра47 вырабатываются управлякщие сигналы, определякщие режимы работысумматоров-вычитателей 9.и 10, адреса чтения и записи блоков 4,5,6,7и 8 памяти и моменты занесения инфор мации в регистр 2 и блоки памяти.Элементы 48 - 54 задержки необходимыдля ,того, чтобы адреса и информация на входах блоков памяти изменялись только после записи информации.В первом цикле работы устройства,т.е. после поступления первого тактового импульса на вход 13 устройства, по переднему фронту сигнала,поступакщего с выхода 14 блока 11 3 Оуправления на управлякщий вход 21регистра 2, в этот регистр с первого входа 3 устройства заноситсядействительная чзсть комплекснойвесовой функции Реи . В первый блок 354 памяти по переднему фронту сигнала, поступакщего на его управлякзцийвход 41 с выхода 40 блока 11 управления, записывается действительнаячасть первого операнда РеА . Адрес 40ячейки памяти, по которому производится запись, поступает на вхОды15,и 30 блока 4. памяти с выходов14 и 29 блока:11 управления,Числа Ре%с выхода регистра 2 и 45РеА с выхода блока 4 памяти поступают на входы блока 1 умножения,где производится их перемножение.К концу первого цикла на выходе блока 1 умножения формируется произведение РеА РеЧЧ,В начале второго цикла в первыйблок 4 памяти со входа б устрбйствапо адресу, определяемому сигналамис выходов 14 и 29 блока 11 управления, записывается мнимая часть первого операнда ЭтЯ. В это же время вчетвертый блок 8 памяти по адресу,поступакщему на его входы 18 и 39и определяемому сигналами с выходов14 и 37 рлока 11 управления, с выхода блока 1 умножения записываетсяпервое произведение МеА. Кем , Свыхода первого блока 4 памяти, всоответствии с.адресом чтения, поступакщим на его входы, 26 и 38 с выхо дов 25 и 37 блока 11 управления, навторой вход блока 1 умножения поступает число ЭпА. В конце второго цикла на выходе блока 1 умножения формируется произведение Эп 1 А РеМ,В начале третьего цикла по управякщему сигналу, поступакщему с выода 43 блока 11 управления на вход45 третьего блока 7 памяти, в этотблок записывается произведение ЭпАкеа, В регис тр 2 к омплекс ной в ес овойфункции в это время заносится мнимая часть комплексной весовой функции эпщ . Во второй блок 5 памятисо входа б устройства записываетсядействительная часть второго операнда кеВ, На входы блока 1 умноженияпоступают числа Эгл А и Эпа,а на еговыходе Формируется их произведениеЭтА ЭючЧ.В четвертом цикле произведениеЭтА Эти записывается в третийблок 7 памяти, во второй блок 5 памяти со входа б устройства записывается мнимая часть второго операнда ЭпЬ,На выходе блока 1 умножения формируется произведение РеА. Эт%. С выходовтретьего и четвертого блоков 7 и 8памяти на информационные входы первого сумматора-вычитателя 9 поступаютпроизведения ЙеА Ре% и ЗвА эьФ,а на его выходе в соответствии с управлякщим сигналом, поступакщим наего вход 20 с выхода 14 блока 11 управления, Формируется .разностьРеА Рею-ЭеА Э.еа. Эта разность поступает на первый информационный вход второго сумматора-вычитателя 10. На его второй информационный вход с выхода второго блока 5,памяти поступает число РеЬ Нод воздействием единичного управляющего сигнала, поступакщего на вход 28 второго сумматора-вычитателя 10, на его выходе, а следовательно, и на выходе устройства формируется первый результат первой базовой ЬперацииРеА:йеб+йеА Ре%-ЭеА ЗеФ.В пятом цикле в первый блок 4 памяти со входа 6 заносится действительная часть первого операнда второй базовой операцииРеФ.На выходе блока 1 умножения формируется произведение РеА Эпчч, на выходе первого сумматора-вычитателя 9 - сумма ЙеЯ.Этф/фЭвЛ РеФ на выходе второго сумматора-вычитателя 10 и на выходе устройства - второй результат первой базовой операции ЗвА:Зпй+йеА эгл%4.Эв А РеЖВ щестом и седьмом циклах работы в устройство продолжают заноситься исходные данные и Формируются произведения для второй, базовой операции, а на выходах сумматоров-вычитателей и на выходе устройства Форьирутся третий и четвертый результаты первой базовой операции ВеВ=РеВ-РеА. йеФ+3 нА Эта в шестом цикле, Эв В"ЭвВ-Фе А 1 ю -ЗрА йечч в седьмом цикле.Начиная с восьмого цикла, на выходе устройства формируются результаты второй базовой операции, а за-. тем через каждые четыре цикла на выход устройства поступают результаты новой базовой операции.Вариант блока памяти (фиг. 3), используемый в данном устройстве, содержит четыре регистра 59 - 62, группы вентилей 63 - 66, группу четырехвходовых элементов ИЛИ 67, двухвходовой дешифратор 68 адреса чтения, двухвходовой дешифратор 69 адреса записи и группу вентилей 70. ИнФормационные входы регистров 59 - 62 соединены с информационныя входом 71 блока памяти, а выход группы элемеи- ф тов ИЛИ 67 является выходом блока. .Входы дешифратора 68 адреса чтения 20 .соединены с входами 72 адреса чтения блока памяти, входы дешифратора 69 адреса записи соединены с вхсщами 73 адреса записи блока, а второй вход группы вентилей 70 - с управ лякщим входом 74 записи блока памяти.Блок памяти работает следукщим об ра зом еДля записи информация подается 30 на инфораационный вхсд 71 блока памяти, На входы 73 подается адрес записи., На выходе дешифратора, соответствукщем поданному адресу, вырабатывается единичный сигнал, который поступает на первый вход соответствукщего вентиля группы вентилей 70. На управлякщий вход 74записи блока подается сигнал записи,Ро этому сигналу на одном из выкодов группы вентилей 70 появляетсяединичный сигнал. Этот сигнал подается на вход занесения соответствукщего регистра 59, 60, 61 или62. Ро переднему фронту сигнала происходит занесение информации совхода 71 в этот регистр.,для чтения информации адрес ячейки подается на входы 72 адреса чтения, дешифрируется на дешифраторе68, сигнал с выхода дешифратора, соответствующего адресу чтения, открывает соответствукщую группу вентилей 63,64,65 или 66. Информация свыхода соответствующего регистра 59,60, 61 или 62 через открытую группувентилей 63, 64, 65 или 66 и группуэлементов ИЛИ 67 поступает на выхсдблока. Введение в устройство для выполнения быстрого преобразования фурье .второго сумматора-вычитателя и блоков памяти позволило более полно совместить во времени операции, выполняемые разньии блоками устройства, устранить простои в работе блоков и. за счет этого повысить быстродействие устройства.1062713 авител УехРед Савееюю щи Тираж 70 ударс твен но ивобретени ква, Ж, ент, г. ужгород, ул. Проектна ПП ф нлиал е 8 актор Н.Лаэаренко каэ 10220/51 ВНИИПИ Гос по делам 113035, Рос" КорректорИ.Шарсти Подпис ноесмитета СССРоткрытийушская наб., 4/5