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

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

Иллюстрации

Показать все

Реферат

 

Изобретение относится к области вычислительной техники и предназначено для выполнения алгоритма быстрого преобразования Фурье (БПФ), используемого при цифровой обработке сигналов. Цель изобретения - упрощение устройства. Поставленная цель достигается за счет того, что устройство состоит из двух групп блоков памяти 1,2, арифметического блока 3, содержащего сумматор 4, вычитатель 6, умножитель 7 комплексных чисел и элементы задержки 7,8, блока синхронизации 9, состоящего из триггеров 10,11 и злемента задержки 12, коммутаторов 13 и 14, счетчиков адреса 15 и 16, дешифратора адреса 17, сдвигового регистра итераций 18, блока элементов И 19, блока постоянной памяти 20 и коммутатора 21. Устройство реализует алгоритмы БПФ с прореживанием по частоте и постоянной структурой от итерации к итерации. 1 з.п,. ф-лы, 3 ил. i 1сл DO САЭ СО

СО(ОЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (19) (11) (51) 4 G 06 F 15 332

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ (21) 4000663/24-24 (22) 30.12,85 (46) 15.09.87, Бюл. ¹ 34 (72) С.В.Редькин, С,Н.Васянин и С.Б.Плешаков (53) 681.32 (088.8) (56) Макаревич О.Б., Спиридонов Б ° Г.

Цифровые процессоры обработки сигналов на основе БИС. — Зарубежная электронная техника, 1983, № 1.

Авторское свидетельство СССР

У 723582, кл. G 06 F 15/332, 1977. (54) УСТРОЙСТВО ДЛЯ ВЫПОЛНЕНИЯ БЫСТРОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ (57) Изобретение относится к области вычислительной техники и предназначено для выполнения алгоритма быстрого преобразования Фурье (БПФ), используемого при цифровой обработке сигналов. Цель изобретения — упрощение устройства, Поставленная цель достигается за счет того, что устройство состоит из двух групп блоков памяти 1,2, арифметического блока 3, содержащего сумматор 4, вычитатель 6, умножитель 7 комплексных чисел и элементы задержки 7,8, блока синхронизации 9, состоящего из триггеров

l0,11 и элемента задержки 12, коммутаторов 13 и 14, счетчиков адреса

l5 и 16, дешифратора адреса 17, сдвигового регистра итераций 18, блока элементов И 19, блока постоянной памяти 20 и коммутатора 21. Устройство реализует алгоритмы БПФ с прореживанием по частоте и постоянной структурой от итерации к итерации. 1 з.п. ф-лы, 3 ил.

133

Изобретение относится к вычислительной технике и предназначено для выполнения алгоритма быстрого преобразования Фурье (БПФ), который используется при цифровой обработке сигналов.

Пель изобретения — упрощение устройства, На фиг,) представлена структурная схема устройства для выполнения Б)ПФ; на фиг,2 — граф алгоритма БПФ; на фиг. 3 — базовая операция БПФ.

Устройство содержит две группы блоков 1 и 2 памяти с произвольной выборкой, каждая из которых состоит из двух блоков 1.1 и 1,2 (2.1 и 2.2),,fptt(>t«(. 11«песк«п« б:«ск 3, co;tep Äftftft«t !. У) (мы 1 Ор 4 к Омп:1!.. к(«н>1х ч«1 се:1, вычит ате If 5 комп:«екс«п«х чисел, умпожитель

6 tottttztef(» «tbtx чисел и два элементы

7 и 8 задержки, блок 9 синхронизации, содержащий два триггера 10 и 11 и элемент 12 задержки, два коммутатора 13 и )4 данных, два счетчика адреса 15 и 16, дешифратор 17 адресы, сдвиговый регистр 18 итераций, блок

)лементов И 19, блок 20 постоянной памяти и коммутатор 21 сигналов эа писи.

Устройс t 1»o реализует алгоритмы

Ы!Ф с прореживанием по частоте и постоянной структурой о« итерации к итера««ии, граф которого изображен на фиг.2, где через .!. () = 0,1,..., 1

log N) обозначены последовательные массивы данных направленного графа, ! а через а„— элеttpffT«t массива

I1 (n = О, l..., V) . Такий а.«гори гм !

n():»f»ozIЯет не меllлт« ПО!)Ндик Выборы опер;шдов из памяти и записи в память резулы атов расчетов ««а всех этапах вычисления БПФ, ы также дает Возможность разде:«ить каждый блок памяти только на две секции при простейшей организации буфера ввода-вывода.

При этом векторы массива М, А .. = -1 А,.„= ...Л

L. l>n+t(12J > 2>))>-! t 2m+»>)ffz) хранятся соответс.твенно г, четных и нечетных ячейках секций А и В блока памяти, Общая формула получения элеме««тоь массиl»а Л иэ элем IITOB массива имеет вид

It» !

+ а )>)2

N

1«е m = 0 1

1 = О>О> ° . ° > 1ОК2мэ

1 ««

2!

Ы = 1

J = -Г-7, Согласно формуле (1) при вычислеэлементов нии значений пары соседних

I ! >! >+! а и а массива .l

2m 2 tn ° »б! проиэвоа и дится выбор нары элементов

15 ! а „из первой и второй

)>» )>!2

ПОЛОВИН

1!

l mt2 J

W из таб)п«цы комплексных ко20 .)дрфициентов, 11;I структурной схеме это соответствует t»It()opy пары одноименных элементов из блоков 1 . 1 (2 ° 1) и 1.2(2.2) одной группы и передаче их ««а первь»й и Второй информационные

25 Входы блока 3 с помощью коммутатора д;шных. Гlричем выбор четных либо нечетных элементов определяется значением +1-ro разряды счетчика 15 адреса, соединенного с переключающим

Входом коммутаторов 13 и 14 данных.

3attIIcf pesya« f;f f.i»» производится в соседние ячейки блоков 2. 1 (1, 1) или 2. 2 (1. 2) другой t рупии в зависимости «т значения старшего разряда счетчика 16 адреса, соедине««ного с

)!кидом коммутатора 21 импульсов записи. Быбир пужногo поворотного мно0,юz-! жителя W, W,..., W из блок.«20 Ifocòo)t«ftfoè памяти производится

tt() ffäðoсу, ко горый формируется в соОтветствии с формулой (1) с помощью б:«ока элементов И 19, счетчика )5 адреса и регистра 18 итераций, состояние которого на первой итерации

4(, "Il...lll, на Второй — 1)...1)0, на третьей — "11...100", на Р-й

"00...000".

Перед началом Выполнения БПФ в блоке I (оперативной памяти) имеется

«) элементов исходной выборки. Счетчики 15 и 16 адреса сброшены. Счетчик 16 заблокирован низким уровнем сигнала с выхода элемента 1? задержки. Счетчик 15 разблокирован высоким у))оннем сигнала с выхода триггера 11 ) 5

Низким уровнем сигналы с выхода триггера 10 открыт коммутатор 13 и

»акрьп коммутатор 14. дешифратор ) 7 адреса установлен В положение, в ко7904 2 ,Г<" 1 2 (1)

2n>+ з 133 тором выходы счетчиков 15 и 16 адреса подключены соответственно к адресным входам секций первого и второго б:to

Вычисление БПФ начинается с подачи тактовых импу It соВ (ТИ) на тактовый вход устройства. Под их воздействием начинает работать счетчик 15, вызывая считывание одноименных разряо о о дов операндов а, а„ и W из блоков оперативной 1 и постоянной 20 памяти на входы арифметического блока 3 и далее — на входы сумматора 4, вычитателя 5 и элемента 8 задержки 8. о о

Соответствующие разряды суммы а + а„, о ю

7904

15 ка 16 и разблокирует з c«t гчик 15. При этом счетчик 16 бло ируется сигналом с выхода элемента 1 2 задержки. Триггер 10, на счетный вход кот рс i o IIAc тупил сигнал переполнения счетчика

16, переключается, 3BKptlB tt. т коммутатор 13, открывая при этом коммутатор

14, подключает с помощ .ю дешифратора

17 выходы счетчиков 15 и 16 к адресным входам блоков групп 2 и 1 и посредством коммутатора 21 задает пос— ледним режимы чтения и записи соответственно.

Этим завершается первая итерация вычисления БПФ. Остальные итерации поступают на вход элемента 7 задержки, а одноименные разряды разности о о а, — at, — на вход умножителя 6, на другои вход которого приходят соответствуюпие разряды поворотного мноо жителя W, задержанные на нужное число тактов элементом 8 задержки.

Через К тактов импульсов ТИ на первом и втором выходах арифметического блока 3, являющихся выходами элемента 7 задержки и умножителя 6, появляются одноименные разряды ре1 t эультата а и а, . На выходе элемента 12 задержки появляется высокий уровень сигнала с выхода триггера 11, которым разрешается счетный режим счетчика 16 адреса и открывается коммутатор 21 сигналов записи. Запись указанных разрядов результата производится в блок 2 памяти по адресу, который определяется состоянием выхода счетчика 16.

После выдачи в арифметический блок 3 последних разрядов операндов о о

N,i i! а„,, а„, и W сигнал переполИ(ненни с счетчика 15 адреса поступает на входи регистра 18 итераций и триггера 11. В регистре 18 итераций происходит сдвиг кодовой комбинации на одну позицию в сторону старших разрядов. Триггер ll сбрасывается и блокирует счетчик 15, запрещая дальнейшее считывание операндов из блока 1 оперативной и блока 20 постоянной памяти, Запись оставшихся в арифметичес1 ком блоке 3 разрядов операндов а

1 и а„ продолжается в течение еще К н- так ов, после чего триггер 1 взводитс я сигналом переполнения счетчи20

55 выполняются аналогично

Ф о р м у л а и з о б р е т е н и я

1, Устройство для выполнения быстрого преобразования Фурье, содержащее четыре блока памяти, два коммутатора, арифметический блок, блок постоянной памяти, блок элементов И, первый счетчик адреса и сдвигоный регистр итераций, выход которого подключен к первому входу блока элементов И, выход которого подключен к первому адресному входу, блок постоянной памяти, выход которого подключен к входу задания коэффициентов арифметического блока, выход переноса первого счетчика адреса подключен к тактовому входу сдвигового регистра итераций, а информационный выход первого счетчика адреса подключен к второму входч блока элементов И, о т л и ч а ю щ е е с я тем, что, с целью упрощения устройства, оно содержит два триггера, элемент задержки, второй счетчик адреса, дешифратор адреса и третий коммутатор, выходы с первого по четвертый которого подключены к входам разрешения записи-считывания блоков памяти соответственно, с первого по четвертый информационные выходы первого и второго счетчиков адреса подключены соответственно к первому и второму входам дешифратора адреса, первый выход которого подключен к адресным входам первого и второго блоков памяти, выходы реальной и мнимой частей операнда которых подключены соответственно к первому, второму, третьему и четвертому информационным входам первого коммутатора, первый и второй выходы которого гоев динены соответственно с первым и вто1337904 рым выходами второго коммутатора и подключены к входам соответственно верного и второго операндов арифметическ го блока, первый и нторой выходы результатов которого подключены к входам соответственно правой и пеной частей операнда информационных входон первого, второго, третьего и четвертого блоков памяти, второй выход дешифратора адреса подключен к адресным входам третьего и четвертого блоков памяти, выходы реальной и мнимой частей операнда которых подключены соответственно к первому, второму, третьему и четвертому информационным нходам второго коммутатора, II! .рвый управляющий вход которого соединен с первым управляющим входом пс рвого коммутатора и подключен к выходу 1.+! -ro (L-разрядность операнда)

p;>зряда первОго счетчика адреса, счетный вход которого соединен с информационным нходом третьего коммутатора, счетным входом второго счетчика адреса и является тактовым входом устройстна, выходы разрядов с первого по

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

2. Устройство по п.j, о т л и ч а ю щ е е с я тем, что арифметический блок содержит два элемента задержки, умножитель комплексных чисел, вычитатель комплексных чисел и сумматор комплексных чисел, выход которого подключен к входу первого элемента задержки, выход которого является выходом первого результата блока, выходом второго результата которого ян— ляется выход умножителя комплексных чисел, первый и второй входы которогo подключены соотнетстненно к выходу второго элемента задержки и выходу вычитателя комплексных чисел, первый и второй входы которого соединены соответственно с первым и вторым входами сумматора комплексных чисел и янляются входами соответственно

35 первого и второго операндов блока, нходом задания коэффициентов которого является вход второго элемента эадержки.

l337904 с . 1

+cт

Фиг л

Составитель А.Баранов

Техред М. Ходанич

Корректор Л.Бескид

Редактор И.Касарда

Заказ 4133/48 Тираж 672

BHHHIIH Государственного комитета СССР по делам изобретений и открытий

ll3035, 11осква, Ж-35, Раушская наб,, д.4/5

Подписное

Производственно-полиграфическое предприятие, г.ужгород, ул.Проектная, 4