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

(19) (11) 1) 4 С) 06 Р 15332 ГОСУДАРСПО ДЕЛ ВЕННЫИ КОМИТЕТ СССРИЗОБРЕТЕНИЙ И ОТКРЫТИЙ ФСГ,6 М;мю е ОПИСАНИЕ ИЗО ЕН М)1 ГК)((56) Макаревич О. Ь., Спирисоноцифровые процессоры обработки сна основе БИС. Заруб.жндя алектехника,1 (25, 1983.Авторское свилетельство СССР723582, кл. С) 06 Г 15/332, 1977.(54) УСТРОГ 1 СТВО ДЛЯ ВЫ ПОЛБЫСТРОГО ПРЕОБРАЗОВАНИЯ(57) Изобретение относится к вычисной технике и предназначено для вния быстрого нреобрдзования Фурь рое используется ири цифр)нс Обработке сигналОВ. 1)егсь изобре 1 ени 5 унрс)иение 5 Строиствс. 11 Остдв,)оннс)5 цсь Достиг)етс 5 зд счст того, что чстроиство ичсст лвс руины блоков регистров 1, 2, ссрифметический блок 3, содержащий сулсмс)тс)р 4, вычитатель 5 и умножитель 6 косчнлексных чисел и два элечента здлержки 7, 8, блок инхронизации 9, сс)держащий длсчент здлержки О и триггеры 11, 12, кс)мчутаторы 3, 14, счетякк разряд)ВО, ссет Ик с);срс сд(1, с;ни гс). вый регистр итердций 17, блок 18 зс)елсит)В И, блок постоянной памяти 19, коммутатор 20. Усгройство реализует ссгсгоритч быстрого нре 06 рс)зов)ни 5 Фчрье с ирОрежиВссниеч ио частоте и иостояннс)й структурой от итерации к итердции. 1 3. и. ф-льс, 4 ил. Б.гнало Т 1)оннд НБНИЯ ФУРЬЕ сительсполн- котоиг А ВТОРСКОМУ СВИДЕТЕЛЬСТВУ,гт .где В=в Ф; 1= х - 1Согласно формуле (1) при вычислении значений пары соседних элементов а и а" массива М,производится выбор пиры элементов а, и а,.г м/г из первой и второй половиц массива М, и поворотного множителя Ф"диз известной таблицы комплексных коэффициентов.а структурной схеме это соответствует выбору пары одноименных элементов из блоИзобретение относится к вычислительной технике ц предназначено для выполнения быстрого преобразования Фурье (БПФ), которое используется при цифровой обработке сигналов.Цель изобретения - упрощение устройства.На фиг. 1 представлена структурная схема устройства для выполнения БПФ; на фиг. 2 - граф алгоритма БПФ; на фиг. 3 - базовая операция БПФ; на фиг. 4арифметический блок устройства.Устройство содержит две группы блоков 1 и 2 (сдвиговых) регистров, каждая из которых состоит из четырех блоков 1.1, 1.2, 1.3, 1,4 (2.1, 2.2, 2.3, 2.4), арифметический блок 3, содержагций сумматор 4 комплексных чисел, вычитатель 5 комплексных чисел, у множитель 6 комплексных чисел ц два элемента 7 и 8 задержки, блок 9 синхронизации, состоящий из элемента О задержки и двух триггеров 11 и 12, два коммутатора 13 и 14, счетчик 15 разрядов, счетчик 16 адреса, сдвиговый регистр 17 итераций, блок 18 элементов И, блок 19 постоянной памяти и коммутатор 20 тактовых импульсов.Уст ройство реализует алгоритм БПФ с прореживанием по частоте и постоянной структурой от итерации к итерации, граф которого изображен ца фиг. 2, где через М, (=О, 1, , 1 одгЛ) обозначены последовательные массивы данных направленного графи, а через аэлементы массива М, (п=О, 1, , Х - 1).акой алгоритм позволяет не менять порядок выбора операндов из памяти и записи и память результатов расчетов ца всех этапах вычисления БПФ. При этом векторы массива М А -аг /В,=/ аг,+/;С= аг, + Л//2/;0ц +А/2где и=О, 1, , А/2 - 1,хранятся соответственно в секциях А, В,С и О блока памяти.Общая формула получения элементамассива М,+1 из элементов массива М,имеет вид 5 10 15 20 25 30 35 40 45 50 55 ков 1.1 (2.1) и 1.3 (2.3) или 1.2 (1.2) и 1.4 (2.4) одной группы и передаче их на первый и второй входы арифметического блока 3 с помощью коммутатора данных, причем выбор четных либо нечетных элементов определяется значением младшего разряда счет. чика 16 адреса, подключенного к управляющему входу коммутаторов 13 и 14 и к управляющему входу коммутатора 20. Запись результатов производится в блоки 2.1 (1.) и 2.2 (1.2) или 2.3 (1.3) и 2.4 (1.4) другой группы в зависимости от значения старшего разряда счетчика 6 адреса, подключенного к управляющему входу коммутатора 20 через элемент 10 задержки. Выбор нужного поворотного множителя Ю", Ф, ,из блока 19 постоянной памяти производится по адресу, который формируется в соответствии с формулой (1) с помощью блока 18 элементов, счетчика 6 адреса и регистра7 итераций, состояние которого на первой итерации устанавливается 11111, на второй - 11110, на третьей - 11 110, на Р-й - 00000.В исходном состоянии в группе блоков регистров имеется Лl элементов исходной выборки, счетчик 16 адреса и счетчик 15 разрядов сброшены, низким уровнем сигнала с выхода триггера 11 открыт коммутатор 18 и закрыт коммутатор 14.Работа устройства начинается с подачи тактовых импульсов (ТИ) на счетный вход счетчика 15 разрядов и через коммутатор 20 на управляющие входы блоков 1. и 1.3 первой и 2.1 и 2.3 второй групп блоков регистров куда записывается информация с выходов арифметического блока 3. ТИ вызывают также считывание одноименных разрядов операндов ао, а,г и йг соответственно изо о облоков 1.1 и 1.3 групп блоков 1 регистров через коммутатор 13 и из блока 19 памяти ца первый, второй и третий входы арифметического блока 3 и далее на входы суммато.ра 4, вычитателя 5 и элемента 7 задержки.Разряды суммы ао+а 2 С/г с выхода сумматора 4 поступают на вход элемента 7 задержки, а соответствующие разряды разности до-а 6 с выхода вычитателя 5 -- на первый вход умножителя 6, на второй вход которого поступают одноименные разряды поворотного множителя Ф, задержанные на нужное число тактов элементов 8 задержки.Одноименные разряды результата ао и а появляются на первом и втором выходах арифметического блока 3, являющихся выходами элемента 7 задержки и умножителя 6 через К ТИ.Сигналом переноса счетчика 15 разрядов, завершающим выдачу первой пары операндов, изменяется уровень сигнала с выхода счетчика 16 адреса, по которому коммутатор 20 переключает ТИ с входов блоков 1.1 и 1.3 на входы блоков 1.2 и 2.9 группы блоков 1 регистров, а выходы последних подключаются через коммутатор 13 к первомуи второму входам арифметического блок 3, обеспечивая ввод в него разрядов операндов о оа( и ах 4 1 одновременно с одноименными разрядами коэффициента из блока 19 постоянной памяти.По сигналу с выхода старшего разряда счетчика 16 адреса, задержанному на К тактов элементом 10 задержки, коммутатор 20 производит переключение ТИ с входов здполненых блоков 2.1 и 2.2 нд входы блоков 2.3 и 3.4 группы блоков 2 регистров. После выдачи в арифметический блок 3 последних разрядов операндов ав г 1, а" и Исигнал на выхоле Р - 1-го разряда счетчика6 адреса переходит в исхо;пгое состояние, сдвигает кодовук комбинацию в регистре 7 итераций на одну позицию В сторону старших разрядов и взводит триггер 12, сигна,ч на выходе которого удерживает счетчик 15 разрядов в сброшенном состоянии до конца итерации, запрепгая дальнейшее считывание операнлов из блока 19 пОстОяннОЙ памяти. Запись Оставп 1 ихся В ариметицеском блоке 3 разрядов результата ани а., в блоки 2.3 и 2.4 группы бло 1ков 2 регистров продолжается в течение е(цс К тактов, после чего сигнал на выходе элемента 1 О задержки переходит в исхолное состояние, сбрасывает триггер 12, снимзя тем самым блокировку со счетчика 15, и переключает триггер 11, Вь(ходной сигнал которого переключает коммутатор 20 для выдачи ТИ на входы блоков 1.1 и 1.3 второй и 1.1 и 1.2 первой групп блоков регистров, закрывает коммутатор 13 и открывает коммутатор 4, подготавливая устройство к следуюгцей итерации, выполнение которой полностью аналогично рассмотренной. формула изобретения. Устройство для выполнения быстрого преобразования Фурье, содержащее первую и вторую группы блоков регистров, по четыре блока регистров в каждой, первый и второй коммутаторы, арифметический блок, блок постоянной памяти, блок элементов И, слвиговый регистр итераций и счетчик адреса, информационный выход которого подклк)чен к первому входу блока элементов И, выход которого подключен к первому адресному входу блока постоянной памяти, выход которого подключен к входу задания коэффициентов арифметического блока, а выход сдвигового регистра итераций подключен к второму входу б,чока элементов И, от,гичающееся тем, что, с целью упрощения устройства, оно содержит третий коммутатор, первый и второй триггеры, счетчик разрядов и элемент задержки, выход которого под. ключен к тактовым входам первого и второго триггеров и первому управляю(нему входу третьего коммутатора, выходы с первого 5 1 О 15 20 25 30 35 40 45 50 55 по четвертый которого полклкцены к тактовым вхочдм соответствующих блоков регистров первой группы, выходы которых полклк)- чены к соответствукнцим информацисшным входам первоп коммутатора, первый и второй выходы которого соединены соответственно с первым и вторым выходами второго коммутатора и подключены к входам соотВетственно первого и второго операнлов дрифметического блока, первый выход результата которого подключен к информационнь(м входам первых и третьих блоков регистров первой и второй групп, информационные Входы вторых и четвертых блоков регистров которых подключены к второму выхолу результата арифметического блока, выход первого триггера подключен к первым управляющим входам первого и второго коммутаторов, второму управляюцгему вхо. лу третьего коммутг(тора, выходы с пятого по восьмой котор(го полклк)цены к тактовым входам соответствую(цих блоков регистров второй группы, Выходы которы подключены к соответствующим информационным вхолдм второп коммутдтора, выход младшего разряда счетчика адреса подключен к Вторым управлякнцим входам первого и Второго коммутдторОВ и третьему упраВляю 1 цему Входу третьего коммутатора, информационныи вход которого соединен со счетным входом счетчика разрялов и является тактовым входом устройства, Выход старшего разряда счетчика адреса подключен к тактовому входу слвигового регистра итераций, вхолу элемента задержки и установочному входу второго триггера, выход которого подключен к входу разрешения счета счетчика рдзрялов выход переноса и информационный выход которого подключены соответственно к счет. ному входу счетчика адреса и второму адресному входу блока постоянной памяти.2. Устройство по и. 1, от,гичающееея тем, что арифметический блок содержит первый и второй элементы задержки, умножитель комплексных чисел, вычитатель комплексных чисел и сумматор комплексных чисел, Вь(хол которого подключен к входу первого элемента задержки, выхол которого является Выходом первого результата блока, Выходом второго результата которого является выхол умножителя комплексны чисел, перВый ВХОЛ КОТОРОГО ПОДКЛК)ЧЕН К ВЬХОЛУ ВЫ. читателя комплексны чисел, перин(й вход которого соединен с первым входом сумматора комплексных чисел и является Входом первого операнда блока, входом второго операнда которого являются с(елиненные между собой вгорые входы сумматора комплексных чисел и выцитдтеля комплексных чисел, второй вход умножителя комплексных чисел полклк)чен к выходу второго элемента задержки, вход которого является Вхо,гх( задания коэффициентов блока.13126 м,т е Ц т д Н Н Варан Редактор г 1. Рогулич Тех Заказ 1845/49 Тир 311 ИИП И 1 осударствениого кочит18035, Москва, Ж ронзводственно-полиграфическиСоставитель Аед И. Верееж 673ета О.(,Р ио д35 за инске иредириягие ректор А. Тяскоиисноестенай и открытий45д, ул. роектиая, 4 Плам изобя наб.,г Ужгор