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

(19) 11 51)4 С 06 Р 15 332 ОПИСАНИЕ ИЗОБРЕТЕНИЯК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ), 3И з.с).1) Г. 1)урои от итерациилы, 3 ил,СУДАРСТВЕННЫЙ КОМИТЕТ СССРО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИИ(56) Макаревич О.Б., Спиридонов Б,Г. Цифровые процессоры обработки сигналов на основе БИС. - Зарубежная электронная техника, 1983, 9 1.Авторское свидетельство СССР У 723582, кл. С 06 Г 15/332, 1977. (54) УСТРОЙСТВО ДЛЯ ВЫПОЛНЕНИЯ БЫСТРОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ(57) Изобретение относится к области вычислительной техники и предназначено для выполнения алгоритма быстрого преобразования Фурье (БПФ), используемого при цифровой обработке сигналов, Цель изобретения - упрощение устройства, Поставленная цельдостигается за счет того, что устройство состоит из двух групп блоковпамяти 1,2, арифметического блока 3,содержащего сумматор 4, вычитатель 6,умножитель 7 комплексных чисел иэлементы задержки 7,8, блока синхронизации 9, состоящего из триггеров10,11 и элемента задержки 12, коммутаторов 13 и 14, счетчиков адреса15 и 16, дешифратора адреса 17, сдвигового регистра итераций 18, блокаэлементов И 19, блока постоянной памяти 20 и коммутатора 21. Устройствореализует алгоритмы БПФ с прореживанием по частоте и постоянной структ к итерации, 1 з.п11 ЗЗИзобретение относится к вычислительной технике и предназначено для выполнения алгоритма быстрого преобразования Фурье (БПФ), который используется при цифровой обработкесигналов.Цель изобретения - упрощение устройства,На фиг, представлена структурнаясхема устройства для выполнения БПФ;на фиг,2 - граф алгоритма БПФ; цафиг, 3 - базовая операция БПФ.Устройство содержит две группы блоков 1 и 2 памяти с произвольной вьборкой, каждая из которых состоит издвух блоков 1,1 и 1,2 (2.1 и 2,2),ырифмепсеск 11 б:лк 3, содерж;шпйсумматор 4 клмн:ексных спсел, вычитатель 5 компексцых чисел, улцожите:ь6 комп.ексных чисел и два элементы7 и 8 задержки, блок 9 синхронизации, содержащий два триггера 1 О и 11и элемент 12 задержки, два коммутатора 13 и 14 данных, два счетчика адреса 15 и 16, дешифратор 17 адресы,сдвиговый регистр 18 итераций, блокэлементов И 19, блок 20 постояннойпамяти и коммутатор 21 сичалов эанцси.Устройство редгшзует алгоритмыБПФ с прореживанием по частоте и постоянной структурой от итерации к итераии, граф которого изображен ндфиг,2 где через .1 (э. = 0,11 о, 11) обозначены последовательныеМс 1 ССИВЬ ДДНЦЫХ 1 с 1 ГРс 1 ЭЛЕННО 1 О Рс 1 фсЭа через д - элементы массиваМ (и = О, 1, Ч) . Тсэклй д:гори гмпл:эволяет не менять порядок выборыопер;шдов из пдмяти и записи в памятьрезугыдтов расчетов а всех этапахвычисления БПФ, д также дает возможность разде:ить каждый блок памятитолько на две секции при простейшейорганизации буфера ввода-вывода.При этом векторы массива М,Аг ага 1 Агаг, 11гу, е гсс+112 1 э гпь г+с э 1 гхранятся соответс.твенцо г, четных инечетных ячейках секций А и В блокапамяти,Общая формула получения элеметоьмассива .1 из элементов массиваимеет вид Фа = а + а ,эгг,Г 2г ()гс1чей=012 0,0.1 ор 11;2Ы=13 = .1-1,Согласно формуле (1) при вычислении значений пары соседнихс ,+а и а массива ,1г э г, с элементов прлиэводится выбор нары элементов15аиз первой и второйс "12 а и половин ыы 1 сэнд 11 и поворотного множителяГтэ 2 Зиз тдбгицы комплексных ко .эдр 4 ицентов, Нд структурной схемеэтл соответствует выбору пары одноименных элементов из блоков 1,1(2,1) и 1.2(2.2) одной группы и передаче их а первьй и второй информационные 25 входы блока 3 с помо 1 ью коммутаторад;шньх. Пэисем выбор четных либо нечетных элементов определяется значением +1-го разряды счетчика 15 адреса, соединенного с переключающим 30 вхлдом коммутаторов 13 и 14 данных.Запись результытсэц производитсяв соседние ячейки блоков 2.1(1.1)очи 2.2(1.2) другой рупь в зависимости т значения стдршего разрядасчетчика 16 адресы, соедэценного с1 ходом коммутаторы 21 импульсов записи. Выбор нужного поворотного мноо ,юг-жителя 11, 1 1 из блока 20 постояццли памяти производитсяпл адресу, коорый формируется в соответствии с формулой (1) с помощьюб:окд элементов И 19, счетчика 15 адреса и регистра 18 итераций, состояние которого ца первой итерации 45 11 .111 , на второй - 11110на третьей - "11100", ца Р-йв 00000 в.Перед цачдллм выполнения БПФ вблоке 1 (опердтивной памяти) имеетсяэлементов исходной выборки. Счетчики 15 и 16 адреса сброшены. Счетчик 16 заблокирован низким уровнемсигнала с выхода элемента 12 задержки. Счетчик 15 разблокирован высокимуровнем сигнала с выхода триггера 11,Низким уровнем сигнала с выходатриггера 1 О открыт коммутатор 13 иэдкрьп коммутатор 14. Ленифратор 7адреса установлен в положение, в ко з 133 тором выходы счетчиков 15 и 16 адреса подключены соответственно к адресным входам секций первого и второго блоков памяти.Вычисление БПФ начинается с подачи тактовых импульсов (ТИ) на тактовый вход устройства. Под их воздействием начинает работать счетчик 15, нызыная считывание одноименных разряо о одон операндов а аи, и 11 из блоков оперативной 1 и постоянной 20 памяти на входы арифметического блока 3 и далее - нд входы сумматора 4, нычитателя 5 и элемента 8 задержки 8.о о Соответствующие разряды суммы а + а,о ю 2поступают нд вход элемента 7 задержки, а одноименные разряды разностио оа, - аи, - на вход умножителя 6, надругои вход которого приходят соотнетствуюшие разряды поворотного мноожителя И , задержанные на нужное число тактов элементом 8 задержки,Через К тактов импульсов ТИ на первом и нтором выходах арифметического блока 3, являющихся выходами элемента 7 задержки и умножителя 6, появляются одноименные разряды реэультата ао и а, . На выходе элемента 12 задержки появляется высокий уровень сигнала с выхода триггера 11, которым разрешается счетный режим счетчика 16 адреса и открывается коммутатор 21 сигналов записи. Запись указанных разрядов результата произнодится в блок 2 памяти по адресу, который определяется состоянием выхода счетчика 16.После выдачи в арифметический б.сок 3 последних разрядов операндов о ой,2 - 1аи, , аи, и Ысигнал переполи, фнеция с счетчика 15 адреса поступает на входи регистра 18 итераций и триггера 11. В регистре 18 итераций происходит сдвиг кодовой комбинации наодну позицию в сторону старших разрядон. Триггер 11 сбрасывается и блокирует счетчик 15, запрещая дальнейшее считывание операндов из блока 1 оперативной и блока 20 постоянной памяти,Запись оставшихся в арифметичес 1 ком блоке 3 разрядон операндов аи и д продолжается в течение еще Ки.такон, после чего триггервзводится сигналом переполнения счетчи 7904 кд 16 и рдзблокирс 1 с ч гчик 15, При этом счетчик 16 бло цруется сцгцдлом с выхода элемента 12 задержки. Триггер 10, ца счетный вход кот роо поступил сигнал переполнения счетчцкд 16, переключается, эакрывдс т коммутатор 13, открывая при этом коммутатор 14, подключает с помощю дешифрдторд 17 выходы счетчиков 15 и 16 к длресным входам блокон групп 2 и 1 и посредством коммутатора 21 задает посв 10 ледним режимы чтения и записи соответственно.Этим завершается первая итерациявычисления БПФ. Остальные итерднии 15 выполняются аналогично Формула изобретения 20 25 30 35 40 45 50 55 1, Устройство для выполнения быстрого преобразования Фурье, содержащее четыре блока памяти, днд коммутатора, арифметический блок, блок постоянной памяти, блок элементов И, первый счетчик адреса и сдвигоный регистр итераций, выход которого подключен к первому входу блока элементов И, выход которого подключен к первому ддресному входу, блок постоянной памяти, выход которого подключен к входу задания коэффициентов арифметического блока, выход переноса первого счетчика адреса подключен к тактовому входу сдвигового регистра итераций, а информационный выход первого счетчика адреса подключен к второму входа блокд элементов И, о т л и ч а ю щ е е с я тем, что, с целью упрощения устройства, оно содержит два триггера, элемент задержки, второй счетчик адреса, дешифратор адреса и третий коммутатор, выходы с перного по четнертый которого подключены к входам разрешения записи-считыванця блоков памяти соответственно, с первого по четвертый информационные выходь 1 первого и второго счетчиков адреса подключены соответственно к первому и второму входам дешифратора ддресд, первый ныход которого подключен к адресным входам первого и второго блоков памяти, выходы реальной и мнимой частей операнда которых подключены соответственно к первому, второму, третьему и четвертому информдционным входам первого коммутатора, первый и второй выходы которого соединень 1 соответственно с первым и цто 133790 чрым выходами второго коммутатора иподключены к входам соответственно первого и второго операндов арифметического блока, первый и второй выходы результатов которого подключены к входам соответственно правой и леной частей операнда информационныхнходон первого, второго, третьего и четвертого блоков памяти, второй выход дешифратора адреса подключен к адресным входам третьего и четвертого блоков памяти, выходы реальной и мнимой частей операнда которых подключены соответственно к первому, второму, третьему и четвертому информационным нходам второго коммутатора, первый управляющий вход которого соединен с первым управляющим входомсрного коммутатора и подключен к выходу 1,+-го (Е-разрядность операнда)разряда первОго счетчика адреса, счетный вход которого соединен с информационным нходом третьего коммутатора,счетным входом второго счетчика адреса и является тактовым входом устройстна, выходы разрядов с первого поЕ-й первого адресного счетчика подключены к входам соответствующих разрядов нторого адресного входа блока постоянной памяти, выход переноса первого счетчика адреса подключен кустановочному входу первого триггерд, выход которого подключен к входу рдзрешения счета первого счетчика адреса и входу элемента задержки, выход которого подключен к первому управляющему входу третьего коммутаторд и входу разрешения счета второ оадресного счетчика, выход старшегордэряда которого подключен к второму управляющему входу третьего коммутдторд, третий упранляющий входкоторого соединен с вторыми упранляю.шими входами первого и второго коммутаторов, третьим входом дешифраторди подключен к ныходу второго триггера, тактовый вход которого соединенс тактовым входом первого триггераи подключен к выходу переноса второго счетчика адреса.152. Устройство по п,1, о т л ич а ю щ е е с я тем, что арифметический блок содержит дна элемента задержки, умножитель комплексных чисел, нычитатель комплексных чисел и сумматор комплексных чисел, выход которого подключен к входу первого элемента задержки, выход которого является выходом первого результата блока, вы ходом второгО результата которого ян -ляется выход умножителя комплексных чисел, первый и второй входы которого подключены соответстненно к выходу второго элемента задержки и выходу вычитателя комплексных чисел, первый и второй входы которого соединены соответственно с первым и вторым входами сумматора комплексных чисели янляются входами соответственно 35первого и второго операндов блока,нходом задания коэффициентов которого янляется вход второго элемента эадержки.Составитель А.БарановТехред М. Ходанич Корректор Л,Бескид Редактор И.Касарда Заказ 4133/48 Тираж 672ВНИИПИ Государственного комитета СССРпо делам изобретений и открытий13035, Москва, Ж, Раушская наб д.4/5 Подписное Производственно-полиграфическое предприятие, г.ужгород, ул.Проектная, 4