Устройство для выполнения быстрого преобразования Фурье Советский патент 1983 года по МПК G06F17/14 

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

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

Изобретение; относится к вычислительной технике, в частности к устройствам циФЕОвой обработки сигналов методами быстрого преобразова1а1 Фурье, и может быть использовано в цифровых фильтрах генераторах слу-чайных процессов, анализаторах спек ра и других устройствах. Придифровой обработке сигналов в реальн&м масштабе времени особое значение приобретает быстродействие вычислительного устройства. Известны устройства, в которых повышение быстродействия достигаетс увеличением количества блоков умножения и сумма торрв, так что /уня каждой из четырех операций умножения при выполнении базовой операции быс рого преобразования Фурье в этих устройствах содержится свой блок ум ножения. Устройства ссдаержат четыре формирователя поразрядных произведе ний, два набора сумматоров, четыре 4)егистЕ а . Наиболее близким к изобретению rio технической сущности и достигаемо му результату является устройство для выполнения быстрого преобразования Фурье, содержащее быстродействукадий блок умножения, cy Ф1втop-вычитатель, регистр комплексной весовой функции и блок умножения L3J. Неясютаток этого устройства низкое быстродействие, вызванное тем, что быстродействуквдий блок умн жения, наиболее дорогоетояций и объ емный блок устройства, простаивает половину времени вычислений. Целью изобретения является повышение быстродействия устройства за счет совмецения во времени операций выполн.я:емых его различными блоксши. Поставленная цель достигается тем, что в устройство для выполнени быстрого преобразоваяия Фурье, содержацее умножения, первый сум матор-вычитатель, блок управления и регистр ксзмплексной весовой функции, информационный вход которого соединен с первым входсм устройства а выхою - с первым, входом блока умножения, введены второй С1Ч«маторвычитатель и четыре блока памяти, причем информационные входы первого и второго блоков памяти соединены с вторьм вхоцсмл устройства, выход первого блока памяти -. с зторын входсял блока умножения, выход которого связан с информационными входами третьего и.четвертого блоков памяти, выходы которых соединены соответственно с nepBfcw и BToiftjM информационными входами первого сумматора-вычитатег1я, выход которого подключен к первому информационному вхсщу второго сугл 1атора-вычитателя, со-, единенного своим выходом с выходом устройства, первый выхол блока управления соединен с первыми входа ми сшресов записи всех блоков памяти, с первь 4 входом адреса чтения второго блока пгшяти, с управляж щим входом первого сумматора-вычитателя и с управляющим вхсдом регистра ксянплексной весовой , второй выход блока управления связан с первьми входами адресов чтения третьего и четвертого блоков памяти, третий выход блока управления соединен с первым входом адреса чтения первого блока пгшяти, четвертый выход - с управляшщт вхсщом второго сумиатора-вычитателя/ пятый вьвссю с вторьми BxcisaMH адресов записи первого, второго и третьего блоков памяти, шестой выход - с входами адресов чтения второго, третьего и четвертого блоков памяти, седьмой выход - с вторьми входами адреса чтения первого блока памяти и адреса эапяси четвертого блсжд пaмяtи, восьмой выход - с управляюуцимн входгши записи it.четвертого блоков памяти,девятый выход - с управляющюви входгйЗи записи 1ВТСФРГО и третьего блоков памяти, а вход первоначальной установки блока управления н его вход тактов1 с импульсов являются соответственно третьим и четвертьм входами устройства. HI этом блок .управления содержит трехразрядный двоичный счетчик, |одноразря|дный регистр, семь элементов задержки, элемент эквивгшентности и два двухвходовых элементаИ, причем вход установки счетчика в ну левсзе сехзтояние и вход установки регистра в единичное состояние связаны, с вхсщом первоначальной устано ки блока, счетный вход счетчика, управлянций вхся регистра и первые входы элементов И подключены к вхсп тактовых импульсов блока, прямые и инверсные выходы первого, второго и третьего разрядов счетчика и прямскй выход р егистра через соответствующи элементы задержки подсоединены соот ветственно к первому, второму, трет ему, етвертому, пятому, шестому и седьмому выходам блока, прямой выхо первого разряда и инверсный выход второго разряда счетчика связаны со входами элемента эквивалентности, а прямой выкод третьего разряда - с информационнБ 4 входом регистра, выход элемента экв ивалентности псдклк чен к входу инвертора и к второму входу первого элемента И, выход инвертора - к входу второго второго злемевта И, а выходы первого и второго элементов И подсоединены соот ветственно к восьмому и девятому вы хсщам блока. На фиг. 1 представлена функциональная схема устройства; на фиг.2 то же, блока управления; на фиг.З вариант схемы блока памяти. Устройство содержит блок 1 умножения, регистр 2 комплексной весово функции, информационный вход которо го сое циненС; первым входом 3 устройства, первый 4 и второй 5 блоки памяти, информационные входы которы соединены с вторым входом 6 устрой CTBaV третий блок 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 памяти. В качестве блока умножения в устройстве может быть использован быстродей твукюий матричный умножитель, обеспечивающий выполнение операции умножения за один машинный цикл, т.е. за времени между передним фронтом одного из тактовых импульсов и передним фронтом последующего тактового импульса. Сумматорил-вычитатели производят сложнение или вычитание чисел, поступающих на их информационные входы, в зависимости от сигнала, поступающего на управляющий вход. При единичном управляющем сигнале выполняется сложение, а при нулевом - вычитание, причем число, поступающее по первому информационному входу . вычитается из числа, поступающего по второму информационному входу. Регистр комплексной весовой функции служит для хранения значений этой функции. Занесение в регистр производится по переднему фронту импульса, подаваемого на его управляющий вход. Блсжи памяти на четыре машинных слова предназначены для хранения исходных данных и промежуточных результатов . Они обеспечивают одновременное и независимое выполнение операщ1й записи и чтения информгшии, для чего имеют по два раздельных одноразрядных входа адреса записи и адреса чтения исправляющий вход записи. Запись производится по переднему фронту импульса, подаваемого на управляющий вход | записи. Адрес записи устанавливается предва- . рительно до поступления импульса записи н может изменяться только после выполнения записи. , управления по второму варианту выполнения (фиг 2) содержит трехразрядиый. двоичный счетчик 46, одноразрядный регистр.47, первый 48, BTOpoi 49, третий 50, четвертый 51, пятый 52, шестой 53 и седьмой 54 элементы задержки, элемент 55 эквивалентности, инвертор 56 и первый и второй двухвходовые элементы И 57 и 58. Устройство для выполнения быстро го преобразования Фурье работает следующим образом.., Вначале -на вход..12 ycTpqiftcTBa по дается импульс первоначальнЬй установки. По этому импульсу устанавливается в нулевое состояние C4eT4Hjj 46блока 11 управления и в единичное состояние регистр 47 этого блока. После окончания импульса первоначальной установки на вход 13 устройства подаются тактовые импульсы. По этим импульсам извеняются состоя ния счетчика 46 блока И управления и на выходах блока с помощью элемен та 55 эквивалентности, инвертора 56, элементов И 57 и 58 и регистра 47вырабатываются управляющие сигналы, определяющие режимы работы сумматоров-вычитателей 9 и 10, адреса чтения и записи блоков 4,5,6,7 и 8 памяти и моменты занесения инфо мации в регистр 2 и блоки памяти. Элементы48 - 54 задержки необходимы для .того, чтобы адреса и информация на входах блоков Пс1мяти изменялись только после записи информации В первом цикле работы устройства т.е. после поступ.ления первого тактового импульса на вход 13 устройства, по переднему фронту сигнала, поступающего с выхода 14 блока 11 управления на управляющий вход 21 регистра 2, в этот регистр с первого входа 3 устройства заносится действительная часть комплексной весовой функции Rew . В первый блок 4 памяти по переднему фронту сигнала, поступакщего на его управляющий вход 41 с выхода 40блока 11 управления, записывается действительная часть первого операнда ReA. Адрес ячейки памяти, по которому производится запись, поступает на входы 15 .и 30 блока 4 памяти с выходов 14 и 29 блока 11 управления, ЧиcлaReWc выхода регистра 2 и ReA с выхода бпока 4 памяти поступают на входы блока 1 умножения, где производится их перемножение. К концу первого цикла на выходе бло ка 1 умножения формируется произведение ReA ReW . В нача.ле второго цикла в первый блок 4 памяти со входа 6 устройства по адресу, определяемому сигналами с выходов 14 и 29 блока 11 уттравления, записывается мнимая часть пер вого операнда От А, В это же время в четвертый блок 8 памяти по адресу, поступающему на его входы 18 и 39 и определяемс 1у сигналами с выходов 14 и 37 /5.пока 11 управления, с выхода блока 1 умножения записывается первое произведение RcA- Рехч . С выхода первого блока 4 памяти, в соответствии с.адресом чтения, пост пающим на его вХодь 26 w 38 с выходов 25 и 37 блока 11 управления, на второй вход блока 1 умножения поступает число ЗтА. В конце второго цикла на выходе блока 1 умножения фор мируется произведение rnA-ReW. В начале третьего цикла по управяющему сигналу, поступающему с выхода 43 блока 11 управления на вход 45 третьего блока 7 памяти, в этот блок записывается произведение JmA« x-Revy, В регистр 2 комплексной весовой функции в это время заносится мнимая часть комплексной весовой функции 3rnvc . Во второй блок 5 памяти со входа 6 устройства записывается действительная часть второго операнда ReB. На входы блока 1 умножения поступают числа Jm А и Jm.a на его выходе формируется их произведение JmA- JmW . . В четвертом цикле произведение JmA-JmNW записывается в третий блок 7 памяти, во второй блок 5 памяти со входа 6 устройства записывается мнимая часть второго операнда Jmft. На выходе блока 1 умножения формируется произведение ReA-JmW. С выходов третьего и четвертого блоков 7 и 8 памяти на информационные входы первого сумматора-вычитателя 9 поступают произведения ReA-Pe W и 3inA-amV /, а на его вькоде в соответствии с управляющим сигналом, поступающим на его вход 20 с выхода 14 блока 11 управления, формируется .разность ReA-Rew-OmA-Л. . Эта разность поступает на первый информационный вход второго сумматора-вычитателя 10.. На его второй информационный вход с выхода второго блока 5.памяти поступает число РеВ . Под воздействием единичного управляющего сигнала, поступающего на вход 28 второго сумматора-вычитателя 10, на его выходе, а следовательно, и на выходе устройства формируется первый результат первой базовой Операции ,(eA Re8+ReA. ReW-DmA-3tflW. В пятом цииле в первый блок 4 памяти со входа 6 заносится действительная часть первого операнда второй базовой операцииReW, На выходе блока 1 умножения формируется произведение РеА-ЗгпЧУ, на выходе первого сумматора-вычитателя 9 - сумма (JeA-JmW-t-OmA-PeW на выходе второго сумматора-выиитателя 10 и на выходе устройства второй результат первой базовой операции ЛтЛ 3|тВ- - Re А Лтл -i-J m A-R е W. В шестом и седьмом циклах работы в устройство прсяолжают заноситься исходные данные и формируются произведения для второй .базовой операции, а на выходах сумиаторо -вычитателей и на выходе устройства формиоуются третий и четвертый результаты первой базовой операции -ReBtReB-fJeA- Re + 3mA-3mW в шестом цикле, Jtn BotnB-fte A-Jm -0m A-Raw в седьмом цикле. Начиная с восьмого цикла, на выходе устройства формируются результаты второй базовой операции, а затем через каждые четыре цикла на вы ход устройства поступают результаты новой базовой операции. Вариант блока памяти (флг. 3), используемый в данном устройстве, содержит четыре регистра 59 - 62, группы вентилей 63 - 66, группу четырехвходовык элементов ИЛИ 67, дву входовой д@1Шфратор 68 адреса чтени двухвхоповой деишфратор 69 адреса iianHCH и группу вентилей 70. Информ ционные вхопы регистров 59 - 62 сое динены с информационным входом 7i блока памяти, а выход группы элемен тов ИЛИ 67 является выходом блока. Шсоды д«нифратора 68 адреса чтения .соединены с 72 адреса чтени блока памяти, входы дешифратора 69 ад1реса записи соединены с входами 7, адреса записи блока, а второй вход группы вентилей 70 .- с управляющим входе 74 записи блока памяти.. ... .: . . ,. Блок памяти работает следующим образс«. Для записи информация подается на информационный вход 71 блока памяти. На входы подается адрес 9аписи На выходе дешифратора, соот ветствующем поданному адресу, вырабатывается единичный сигнал, который поступает на первый вход соответствующего вентиля группы вентилей 70. На управляющий вход 74 записи блока подается сигнал записи. По этому сигналу на одном из выходов группы вентилей 70 появляется единичный сигнал. Этот сигнал подается на вход занесения соответствующего регистра 59, 60, 61 или 62. По переднему фронту сигнала происходит занесение информации со входа 71 в этот регистр., Для чтения информации адрес ячейки подается на входы 72 адреса чтения, дешифрируется на дешифраторе 68, сигнал с выхода дешифратора, соответствующего адресу чтения, открывает соответствующую группу вентилей 63,64,65 или 66. Информация с выхода соответствующего регистра 59, 60, 61 или 62 черюз открытую группу , вентилей 63, 64, 65 или 66 и группу элементов ИЛИ 67 поступает на выход блока. Ввеяение в устройство для выполнения быстрого преобразования Фурье второго сумматора-вычитателя и блоков памяти позволило более полно совместить во времени операции, выпблняемые разными блоками устройства, 5гстранить простои в работе блоков и; за счет этого повысить быстродействие устройства.

-