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

 

Изобретение относится к области вычислительной техники и предназначено для выполнения алгоритма быстрого преобразования Фурье (БПФ), используемого при цифровой обработке сигналов. Цель изобретения - упрощение устройства. Поставленная цель достигается за счет того, что устройство состоит из двух групп блоков памяти 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

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

 

Похожие патенты:

Изобретение относится к области телемеханики и может быть использовано для организации удаленного доступа терминальных устройств к вычислительным комплексам

Изобретение относится к автоматике и вычислительной технике и может быть использовано для построения процессоров быстрого преобразования Фурье

Изобретение относится к вычислительной технике и может быть использовано в системах цифровой обработки сигналов в реальном масштабе времени

Изобретение относится к вычислительной технике и может быть нсно.тьзовано в ариф.метических устройствах сиециа

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

Изобретение относится к автоматике и вычислительной технике и может быть использовано в измерительной технике, радиотехнике и электросвязи для выполнения преобразования Фурье непрерывных дискретных, детерминированных и случайных сигналов в реальном масштабе времени

Изобретение относится к вычислительной технике, предназначено для оперативного определения коэффициентов ДПФ в реальном масштабе времени и может быть использовано в автоматике , радиотехнике и других областях науки и техники

Изобретение относится к области автоматики и вычислительной техники и может быть использовано в цифровых системах связи для построения устройств цифровой фильтрации, сжатия изображений и вьщеления контуров,основанных на алгоритме быстрого преобразования Хаара

Изобретение относится к автоматике и вычислительной технике и может быть использовано для спектрального анализа случайных процессов в системах передачи дискретных сообщений и для цифровой фильтрации в функциональных преобразователях

Изобретение относится к автоматике и вычислительной технике и может быть использовано в радиотехни L r ке и измерительной технике для определейия коэффициентов преобразования Фурье случайных сигналов в реальном масштабе времени

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

Изобретение относится к вычислительной технике и может быть использовано для вычисления скользящего спектра Фурье

Изобретение относится к способам обработки цифрового сигнала

Изобретение относится к области обработки информации и может быть использовано в анализаторах речевых сигналов

Изобретение относится к вычислительной технике и может быть использовано для преобразования сигналов

Изобретение относится к области вычислительной техники и может быть использовано при анализе случайных сигналов

Изобретение относится к области вычислительной техники и может быть использовано при анализе случайных сигналов
Наверх