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

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСНРЕСПУБЛИК 605 51)5 С 06 Р 32 ОПИСАНИЕ ИЗОБРЕТЕН АеторСНОМ СвиДКткЛМтвм 41Поваренко танин15/332 ьство СССР 15/332, 1980 ЫЧИСЛЕНИЯ БЫ ФУРЬЕ сится к вычи слиГОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТНРЫТИПРИ ГКНТ СССР(54) УСТРОЙСТВО ДЛЯРОГО ПРЕОБРАЗОВАНИЯ(57) Изобретение отн тельной технике и предназначено длявыполнения алгоритма быстрого преобразования Фурье в устройствах цифровой обработки сигналов. Цель изобретения - упрощение устройства. Поставленная цель достигается тем, что всостав устройства входят входной блок3 памяти, блоки 4, 5 памяти, арифметический блок 6, блок 7 постояннойпамяти, регистры 8,9, накапливающиесумматоры 1 О, 11, блок 12 синхронизации, блок 13 памяти, блок 14 задержки и выходной арифметический блок 15.6 ил.Изобретение относится к вычислительной технике и предназначено длявычисления алгоритма быстрого преобразования Фурье (БПФ) в устройствах цифровой обработки сигналов.Цель изобретения - упрощение устройства,На фиг.1 представлена структурная схема устройства для вычислениябыстрого преобразования Фурье; нафиг.2 - структурная схема выходногоарифметического блока; на фиг.З -временная диаграмма управления входным блоком памяти; на фиг.4 - временная диаграмма записи в блок оперативной памяти; на фиг.5 - временнаядиаграмма считывания из блока оперативной памяти; на фиг.6 - временнаядиаграмма считывания из блока памятирезультата и управляющих сигналов вы"ходного арифметического блока.Устройство содержит (фиг.1) ин"формационный вход 1, информационныйвход 2 второго канала, входной блок3 памяти , блоки 4 и 5 оперативнойпамяти, арифметический блок 6, блок7 постоянной памяти, регистры 8 и 9,накапливающие сумматоры 10 и 11,блок12 .синхронизации, блок,13 памяти результата, блок 14 задержки, выходнойарифметической блок 15, информационный выход 16.Выходной арифметический блок 15(фнг.2) содержит мультиплексоры 17 "20, сумматор 21, вычитатель 22, сумматор 23, вычитатель 24, тактовыевходы 25 и 26.Устройство работает следующим образом,Устройство вычисляет БПФ двухвходных действительных массивов данных Х(п) и У(п) длиной 02" (г щ2, 3, 4,. ). Действительные массивы представляются в виде одного комплексного с элементами 2(п) = Х(п) ++ 17(п) (1 - - 1)Поступлениевходных данных осуществляется параллельно по двум каналам через входы1 и 2 соответственно. Для примеравыберем Б щ 8. В блоке 3 памяти производится предварительное накопление входных данных, поступающих вреальном масштабе времени по двумканалам. Отсчеты Х(п) первого каналазаписываются в первые два поДблока,а отсчеты второго канала 7(п) - вовторые подблоки. Отсчеты с четныминомерами О, 2, 4, 6 заносятся в первый и третий подблоки, а отсчеты снечетными номерами 1, 3, 5, 7 - вовторой и четвертый подблоки. Объемпамяти каждого подблока равен Ю/2действительных слов, Временная диаграмма записи информации приведенана фиг,З, Низкий уровень сигналоввыбора подблоков соответствует записи операндов.По окончании приема инбормацииво входной блок 3 памяти производится ее перезагрузка в один из свободных блоков 4 или 5 памяти. При этомдействительная часть Х(п) входногомассива 2(п) передается по шинамКеА и КеВ , а мнимая 7 - по шинам1 ш А и 1 ш В. Операнды с четными1 1номерами 0,2,4,6 будут передавать 20 ся через шину А(РКеА и 1 шА), а снечетными номерами 1, 3, 5, 7 черезшину В (КеВ и 1 шВ). Пусть информация заносится в блок 4 памяти. Приэтом блок 12 будет формировать ад 25 ресные и управляющие сигналы,соответствующие режиму записи, Объем памяти каждого подблока блоков 4 и 5памяти равен Б/4 комплексных слов,Перезапись информации производитсяза О/2 д 4 такта, Подблоки памяти.входного блока 3 памяти переводятсяв режим считывания и выдают инбормацию параллельно каждый на свой вь- хоц. В первом такте производитсязапись нулевого и первого комплексных операндов в первые два подблокасоответственно. Во втором такте запись второго и третьего комплексныхоперандов в первые два подблока со 40 ответственно. В третьем такте производится запись четвертого и пятогокомппексных операндов во вторые дваподблока соответственно, На четвертом такте аналогично записываются45 шестой и седьмой операнды. Временнаядиаграмма процесса записи информациив блок 4 памяти приведена на фиг.4.Нижние уровни сигналов выбора подбло-,ков соответствуют записи соответст 50вующих операндов. Последовательностьадресов повторяется два разе,После перезаписи информации начинается процедура вычисления БПФ пограбу с постоянной структурой и накопление нового массива в блоке 3.При этом на вход блока 6 информацияпоступает по шинам А и В, а записьрезультата в свободный блок 5 памятипроизводится через шины Аи В ,Вы 15256 5 О 5 20 25 30 35 40 45 50 55 5 160 числение базовых операций алгоритма БПФ производится по основанию 2 с прореживанием по частоте. Блок 4 памяти переводится в режим считывания информации, а блок 5 памяти - записи, Время выполнения одного этапа БПФ составляет (п/2 + п) тактов, где и у - количество тактов выполнения одной базовой операции. В первый такт считываются нулевой и четвертый операнд из первого и третьего подблоков соответственно по шинам А и В, Они поступают на входы арифметического блока б, который выполняет базовую операцию за п тактов. Во втором такте производится считывание первого и пятого комплексного операндов из второго и четвертого подблоков соответственно. В третьем такте - второго и шестого из первого и третьего подблоков, В четвертом - третьего и седьмого из второго и четвертого подблоков соответственно.Адреса и управляющие сигналы формируются блоком 12. Временная диаграмма приведена на фиг.5. По каждому адресу производится считывание пары операндов сперва из первого и третьего нодблоков, затем - из второго и четвертого подблоков, Через п тактов после начала выполнения этапа БПФ на выходах блока 6 будут последовательно появляться пары результатов, которые по шинам А и Б записываются в блок 5 памяти.Блок 12 формирует последовательность управляющих сигналов для блока 5 памяти, Запись информации в блок 5 осуществляется аналогично записи информации в блок 4 при загрузке из входного блока 3. Задержка. работы блоков 4 и 5 памяти составляет п тактов. Временная диаграмма записи информации в блок 5 аналогична диаграмме, приведенной на Фиг,4.После записи последней пары результатов из блока 6 в блок 5 памяти начинается новый этап вычисления БПФ. Режим работы блоков 4 и 5 меняется. Информация считывается из блока 5, а заносится в блок 4 по описанным выше алгоритмам. Количество этапов определяется 1 одИ = г. ВремяГ 1 вычисления БПФ составляет г( -- +2 + и ) тактов . Описанный алгоритм работы устройства продолжается до последнего этапа вычислений. На последнем этапе по сигналу с выхода блока 12 на шины А и В " будут поступать накопленные в блоке 3 отсчеты новой выборки, которые заносятся в свободный блок 4 или 5. Дру- . гой блок памяти будет выдавать информацию на блок 6 для выполнения последнего этапа. Таким образом,производится совмещение во времени загрузки информации и выдачи результа 1 й тов, которые по шинам А и В поступают в блок 13 памяти результата.Последний переводится в режим записи, а управление им осуществляется блоком 12, Временная диаграмма работы блока 13 памяти результата соответствует фиг,4. Адресные сигналы на входы поступают параллельно и одинаково согласно алгоритму работы предыдущих блоков 4 и 5 памяти в режиме записи. В первый подблок запишутся последовательно выходные отсчеты - нулевой и второй, во второй подблок - четвертый и шестой, в третий подблок - первый и третий, в четвертый - пятый и седьмой. По окончании записи результата в блок 13 памяти устройство начинает вычисление БПФ нового массива и разделение спектров исходных действительных массивов. Блок 13 памяти переключается в режим считывания. Временная диаграмма работы блоков 13 и 15 в режиме выдачи результатов приведена на фиг.б, Все управляющие сигналы формируются блоком 12. На одном из адресных входов блока 13 памяти прямая последовательность адресов, на другом адресном входе - инверсная последовательность адресов. Смена адресов производится через каждые два такта считывания. На первом такте считывается 2(0)(2(п) - результат БПФ комплексного массива из первого подблока и 2 (7) из четвертого под- . блока. Операнд 2 (0) с первого выхода 13 памяти результата поступает на первый вход выходного арифметического блока 15. На один управляюший вход поступает нижний управляющий уровень, а на другой управляющий вход поступает верхний управляющий уровень. При этом на выходах сумматоров 21 и 23 будут значения КеХ(0) и ВеУ(0) соответственно, На выходах вычитателей 22 и 24 будут значения 1,Х(0) = О и 1 Ь,У(0). С приходом синх 1605256роимпульса значение Е(7) запишетсяв блок 14 задержки.Во втором такте иэ второго подблока на второй выход блока 13 памятирезультата поступает значение Е (6),на первый выход этого же блока 15значение Е (1) из третьего подблока.Управляющие сигналы на входах 25 и26 выходного арифметического блока15 находятся в нижнем уровне, приэтом все мультиплексоры 17 - 20 передают информацию с первых входов.На первый вход выходного арифметического блока 15 поступает значениеЕ (1), а на второй - значение Е (7)с выхода блока 14 задержки, Послевыполнения соответствующих суммирований и вычитаний на выходе сумматора 21 будет значение КеХ(1), на выходе вычитателя 22 - 1 Х(1), на выходе сумматора 23 - РеУ(1) на выходе вычитателя 24 - 1 ш 7(1), Будемполагать, что все выходные результаты промасштабированы соответствующим 25образом, На третьем такте из первого подблока считывается Е (2), а изчетвертого подблока Е (5), На входывыходного арифметического блока 15поступают Е (2) и Е (6), записанные 30в блок 14 задержки на предыдущемтакте. С выходов сумматоров 21 и 23снимают значения КеХ(2) и КеУ(2),а с выходов вычитателей - 1 Х(2) и1 7(2), На четвертом такте из второго подблока считывается значениеЕ (4), из третьего подблока - Е (3).На входах выходного блока 15 значения Е (3) и Е (5). На выходах 16блока 15 значения КеХ(3), КеУ(3) 401 Х(3), 17(3). В пятом такте навторой вход блока 15 поступает значение Е (4) иэ блока 14 задержки.На входе 26 блока 15 остается нижнийуровень, а на входе 25 устанавливается верхнее значение управляющегосигнала. При этом мультиплексоры17 и 19 будут передавать информацию с второго входа, На выходах сумматоров "1 и 23 будут значения КеХ(4) 50и КеУ(4), а на выходах вычитателей22 и 24 - 1 Х(4) = О и 17(4) = О.После выдачи последних результатовблок 12 переводится в режим ожиданияприема новыхрезультатов в блок 13памяти результата,Формула изобретенияУстройство дпя вычисления быстрого преобразования Фурье, содержащее блок синхронизации, блок постояннойпамяти, первый и второй блоки памяти, арифметический блок, выходы первого и второго результатов которогоподключены соответственно. к первомуи второму информационным входам первого блока памяти и соответственнок первому и второму информационнымвходам второго блока памяти, первыйи второй выходы которого соединенысоответственно с первым и вторым выходами первого блока памяти и подключены к входам соответственно первого и второго операндов арифметического блока, тактовый вход которогоподключен к первому тактовому выходу блока синхронизации, первый и второй адресные выходы которых подключены к адресным входам соответственнопервого и второго блоков памяти,входы управления записью-считываниемкоторых подключены соответственно квторому и третьему тактовым выходамблока синхронизации, третий адресныйвыход которого подключен к адресномувходу блока постоянной памяти,тактовым входом и входом запуска устройства являются соответственно тактовыйвход и вход запуска блока синхронизации, четвертый тактовый выход которого является выходом окончания вычислений устройства, о т л и ч а ю -щ е е с я тем, что, с целью упрощения устройства, оно содержит входной блок памяти, первый и второй регистры, первый и второй накапливающие сумматоры, блок задержки, третийблок памяти и выходной арифметический блок, выход которого являетсяинформационным выходом устройства,первым и вторым информационным входами которого являются соответственно первый и второй информационныевходы входного блока памяти, первыйи второй выходы которого подключенысоответственно к первому и второмуинформационньгм входам первого блокапамяти, выходы первого и второго результатов подключены соответственнок первому и второму информационнымвходам третьего блока памяти, первыйи второй выходы которого подключенысоответственно к входу блока задержки и входу первого операнда выходного арифметического блока, вход второго операнда которого поключен квыходу блока задержки, первый и второйвыходы блока постоянной памяти под 1605256ключены к информационным входам соответственно первого и второго накапливающих сумматоров, выходы которых подключены к информационным входам соответственно первого и второго регистров, выходы которых подключены соответственно к первому и второму входам коэффициентов арифметического блока, адресный вход и вход управле" ния записью"считыванием третьего блока памяти подключены соответственно к четвертому адресному и пятому тактовым выходам блока синхронизации, пятый адресный выход, шестой и седьмой тактовые выходы которого подключены соответственно к адресному входу и входу управления записью-считыванием входного блока памяти и входу обнуления второго накапливающего сумматора, тактовый вход которого соединен с тактовым входом первого накапливающего сумматора и подключен к восьмому тактовому выходу блока синхронизации, девятый и десятый выходы которого подключены соответственно к первому и второму тактовым входам выходного арифметического блока, который содержит четыре мультиплексора, два сумматора и два вычи.тателя причем первые входы первых сумматора н вычитателя подключены к выходу первого мультиплексора, первый :информационный вход которого соединен с первым информационным входом;.второго мультиплексора и объединенный с соединенными между собой пер- .5выми информационными входами третьего и четвертого мультиплексоров образуют вход первого операнда выходного арифметического блока, выходомкоторого являются объединенные междусобой выходы первого и второго сумматоров и первого и второго вычитателей, вторые входы первых сумматора ивычитателя подключены к выходу второго мультиплексора, второй информационный вход которого соединен с вторым информационным входом первогомультиплексора и объединенный с соединенными между собой вторыми информационными входами третьего и четвертого мультиплексоров образует входвторого операнда выходного арифмети"ческого блока, первым тактовым входомкоторого являются соединенные междусобой управляющие входы первого и 25 третьего коммутаторов, выход третьего мультиплексора подключен к первым входам вторых сумматора и вычитателя, вторые входы которых подключены к выходу четвертого мультиплекЗо сора, управляющий вход которого соединен с управляющим входом второгомультиплексора и является вторым тактовым входом выходного арифметического блока,1605256 Фиг д Составитель А,БарановТехред И.цндык Корректор И.Максимишинец Редактор Н.Тупица Заказ 3455 Тираж 569 ПодписноеВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР 113035, Иосква, Ж, Раушская наб., д. 4/5 Производственно-издательский комбинат "Патент", г. Ужгород, ул. Гагарина, 101