Процессор быстрого преобразования фурье

 

Изобретение относится к специализированным устройствам цифровой обработки сигналов, использующих алгоритм быстрого преобразования Фурье, и может быть применено в различных -областях техники, использующих спектральный и корреляционный анализ. Цель изобретения.- повьшение быстродействия. Поставленная цель достигается за счет того, что в состав устройства входят блок 1 вычисления коэффициентов Фурье, блок перестановки 2, блок памяти 3, блок адресации 4. 6 ил.

СОЮЗ СОВЕТСНИХ

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

РЕСПУБЛИК (SI> 4 С 06 F ..15/332

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

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ

Н А BTOPGHOMY СВИДЕТЕЛЬСТВУ (21) 4214217/24-24(22) 25.03.87 (46) 23.09.88. Бюл, У 35 (71) Институт технической кибернетики

AH БССР (72) P.Õ. Садыхов, С.А. Золотой, А.В. Шаренков и Н,Н. Легонин (53) 681.32(088.8) (54) IIPOiJECCOP БЫСТРОГО ПРЕОБРАЗОВАНИЯ,ФУРЬЕ (57) Изобретение относится к специ„„SU„„1425709 A 1 ализированным устройствам цифровой обработки сигналов, использующих алгбритм быстрого преобразования

Фурье, и может быть применено в pasличных областях техники, использующих спектральный и корреляционный анализ. Цель изобретения. — повьппение быстродействия. Поставленная цель достигается за счет того, что в состав устройства входят блок 1 вычисления коэффициентов Фурье, блок перестановки 2, блок памяти 3, блок адресации 4. 6 ил.

1425709

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

Цель изобретения — повышение бы- fp стродействия процессора за счет сокращения числа операций на перестановку выходного массива, при сокра щении объема рабочей памяти в два раза. f5

На фиг. 1 представлена функцио нальная схема устройства," на фиг.2— функциональная схема блока перестановки; на фиг. 3 — временные диаграммы функционирования узла управ- 20 ления и формирования сигнала WR/RD; на фиг. 4 — функциональная схема узла управления на фиг. 5 — функциональная схема коммутатора; на фиг. 6 функциональная схема блока адресации. 25

Процессор (фиг,1) содержит блок, 1 вычисления коэффициентов Фурье, блок 2 перестановки, блок 3 памяти, блок 4 адресации.

Блок 2 перестановки (фиг.2) со- ° 30 ,держит регистры 5 и 6, мультиплек- сор 7.

Узел управления (фиг,4) содержит одновибратор 8, триггеры 9-12, элемент ИЛИ 13 и одновибратор 14.

Блок 4 адресации (фиг.5) содержит

35 узел 15 управления, мультиплексор 16, I счетчик 17, мультиплексор 18 регистр 19, коммутатор 20, компаратор

21,. элементы ИЛИ 22 и 23, элементы

И 24 и 25, сдвигатель 26, одновибратор 27, мультиплексор 28, элемент

И 29, одновибратор 30, элемент ИЛИ 31, триггер 32, реверсивный счетчик 33, элемент И 34, элемент НЕ 35.

Блок 4 адресации работает следующим образом.

По включению питания все регистры и счетчики устанавливаются в "0".

Триггер 9 узла 15 устанавливается в

"1", которая блокирует триггеры 1012 и устанавливает их в "0". "0" на выходе узла 15 обеспечивает подключение выходов триггера 32 и счетчика

17 через мультиплексор 28 к адреси и 55 иой шине блока 4 адресации. 1 на выходе узла 15 обеспечивает прохождение тактовых импульсов через элементы И 24 и 25, что обусловливает изменение адреса, (формируемого триггером 32 и счетчиком 17) по каждому такту и генерирование сигналов записи в блок 3 памяти (на выходе узла и входе блока 4 адресации присутствуют

"1"). "1" на управляющем входе мультиплексора 7 блока 2 перестановки обеспечивает соединение выхода про-. цессора быстрого преобразования Фурье с информационным входом блока 3 памяти. Тем самым обеспечен режим последовательной записи в блок 3 памяти коэффициентов Фурье.

При передаче последнего коэффици-. ента в блок 3 памяти блок 1 формирует сигнал конца преобразования, который поступает на вход блок 4 адресации и запускает одновибратор 14 устанавливающий триггер 9 в "0".

Одиночный импульс с выхода одновибратора 14 поступает также на R-входы триггера 32 и счетчиков 17 и 33 и устанавливает их в "0", "0" на входах элементов ИЛИ, 22 и 23 разрешает управление прохождением тактовых импульсов через элементы И 24 и 25 от компаратора, а также управление мультиплексором 16 и триггером 32 от мультиплексора 18. Кроме того, по импульсу с выхода одновибратора 14 в регистр !9 записывается код, управляющий размерностью преобразования.

Максимальная размерность определяется разрядностью счетчика 17 плюс единица (поскольку триггер 32 формирует младший разряд адресного кода).„, При этом для размерности N=2 (n-1)-й разряд счетчика 17 подключается через элемент И 34 и к S-входу триггера 32 и управляющему входу мультиплексора 16, а сдвигатель 26 обеспечивает сдвиг исходного кода Х на i разрядов в сторону младших раз рядов. Пусть N=2 (i=10). Рассмотрим процедуру перестановки двух операнцов, которая выполняется за четыре такта. По импульсу с выхода элемента

ИЛИ 13 счетчики 17 и 33 и триггер 32 устанавливаются в "0". На выходе

Ы Х компаратора устанавливается "1", а на выходе ы (Х компаратора "0", тем самым следующий тактовый импульс поступает на тактовый вход триггера

1 узла 15. При этом управляющие сигналы для блока 3 не сформированы, а содержимое счетчика (триггер 32— счетчик 17) увеличивается на единицу.

При этом на выходах компаратора 21

1425709 состояние изменяется на противоположное, т.е. разрешается прохождение последующих тактовых импульсов на тактовый вход узла 15, на выходах которого формируются сигналы согласно временной диаграмме (фиг.3).

Высоким уровнем сигнала на выходе узла к адресному входу блока 3 подключается модифицированный код оа

00...01 и иэ ячейки памяти с этим адресом считывается первый операнд и записывается в регистр 5 блока 2 перестановки.

Далее по второму такту низким уровнем сигнала на выходе узла и адресному входу через мультиплексор

28 подключается исходный код Х=10...0 и в регистр 5 записывается второй операнд, при этом первый операнд переписывается в регистр 6 блока 2 перестановки и поступает на информационный вход блока 3 памяти. По следующему такту формируется сигнал

WR/RD записи и первый операнд записывается по адресу исходного кода

Х. Далее высоким уровнем на выходе узла 15 по второму адресу записывается второй операнд, Затем перепадом из "0" в "1" на выходе узла 15 содержимое счетчика (триггер 32 — счетчик 17) увеличивается на единицу и процедура перестановки следующей пары операндов повторяется аналогично. При блокировке узла 15 (содержимое счетчика триггер

32 — счетчик 17 увеличивается на единицу) перестановка не осуществляется.

Указанная процедура формирования адресов перестановки осуществляется вплоть до адреса Б/2-1. Далее при адресе, равном N/2, "1" старшего разряда модифицированного кода поступает через мультиплексор 18 на управляющий вход мультиплексора 16 и S-вход триггера 32. При этом на выходе триггера 32 устанавливается "1", а тактовые импульсы через мультиплексор

16 поступают на тактовый вход счетчика 17. Далее модифицированный код формируется с шагом два, т,е, в диапазоне адресов от N/2 до N-1 анализируется только N/4 нечетных адресов.

Реверсивный счетчик 33 включен параллельно счетчику 17, на управляющий вход счетчика 33 поступает сигнал с выхода мультиплексора 18.

При "0" счетчик 33 работает в режиме суммирования, а при адресе N/2 и

Процессор быстрого преобразования

Фурье, содержащий блок вычисления коэффициентов Фурье, блок перестановки, блок памяти и блок адресации, 45 тактовый выход которого подключен к входу управления перестановкой блока перестановки, выход которого подключен к информационному входу блока памяти, выход которого является выходом процессора, информационным входом которого является информацион1 ный вход блока вычисления коэффициентов Фурье, тактовый вход которого является первым тактовым входом процессора, отличающийся .тем, что, с целью повышения быстродействия, информационный выход и выход окончания вычислениИ блока вы10

40 выше в режиме вычитания. Таким образом, при формировании счетчиком 17 (N- 1)-ro адреса счетчик 33 обнуляется и на его выходе переноса формируется сигнал окончания процедуры перестановок, который поступает на вход узла синхронизации и запускает одновибратор 8, который устанавливает триггер 9 в "1", а счетчики 17 и 33 и триггер 32 обнуляется. Тем самым блок 4 адресации вновь готов к работе. При подаче на вход блока 4 адресации низкого потенциала запрещено формирование сигнала записи и реализуется режим считывания иэ блока 3.

Процессор быстрого преобразования

Фурье работает следующим образом.

Исследуемый. процесс поступает на вход блока 1 вычисления коэффициентов Фурье, на выходе которого формируются спектральные коэффициенты в обратном двоичном порядке, поступающие последовательно через мультиплексор 7 блока 2 перестановки в блок 3. При этом блок 4 адресации формирует по тактам последовательные адреса и управляющие сигналы для бло-. ка 3. После формирования последнего коэффициента Ср из блока 1 в блок 4 адресации поступает сигнал конца преобразования и блок 4 адресации переводится в режим переупорядочения, при этом выход регистра 6 подключен через мультиплексор 7 к входу блока

3. В результате описанных процедур перестановки через 3/4N циклов в блоке 3 содержатся данные, упорядоченные в естественном порядке.

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

1425709 числения коэффициентов Фурье подключены соответственно к первому информационному входу блока перестановки и входу условий блока адреса5 ции, адресный выход, выход управления записью-считыванием и выход выборки которого подключены соответственно к адресному входу, входу упранления записью-считыванием и вхо- ð ду выборки блока памяти, вьмод которого подключен к второму информационному входу блока перестановки, 1 ! тактовый вход которого является вто рым тактовым входом процессора, тре тьим и четвертым тактовыми входами которого являются соответственно . первый и второй тактовые входы блока

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

1 .мультиплексор, первый информационный !, вход которого подключен к выходу 25

,первого регистра, информационный вход которого подключен к выходу второго ! ,регистра, вход записи которого соединен с входом записи первого регистра

,и является тактовым входом блока пе:рестановки, первым и вторым информа,ционными входами и входом управления перестановкой которого являются со ответственно второй информационный вход мультиплексора, информационный вход второго регистра и управляющий

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

f подключен к первому входу первого элемента ИЛИ, выход которого подключен к второму информационному нходу первого мультиплексора и тактовому нходу триггера, выход переноса реверсивного счетчика подключен к входу останова узла управления, третий выход которого подключен к управляющему входу второго мультиплексора, первый информационный вход которого соединен с первым входом компаратора и подключен к вьмоду сдвигателя, информационный вход которого подключен к выходу коммутатора, информационный выход счетчика и выход триггера через шину данных подключены к второму информационному входувторого мультиплексора,информационному входукоммутатора, второму входу компаратора и информационному входу третьего мультиплексора, выход которого подключен к второму входу Неравно" первого элемента И, вьмоды "Равно" компаратора подключены к первым входам соответственно второго и третьего элементов ИЛИ, выходы которых подключены к первым входам соответственно второго и третьего элементов И, выходы второго элемента И подключены к второму входу первого элемента ИЛИ, .выход третьего элементаИ подключен к первому входу четвертого элемента И и тактовому вхо" ду узла управления, четвертый выход кото- рого подключен к второму входу четвертого элемента И, выход которого подключен

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

14257 триггера, два одновибратора и элемент ИЛИ, причем прямой выход первого триггера подключен к тактовому входу второго триггера, инверсный

5 выход которого подключен к D-входу первого триггера, инверсный выход первого триггера подключен к D-входу первого триггера и тактовому входу третьего триггера, инверсный выход которого подключен к D-входу третьего триггера, R-вход которого соединен с R-входом первого триггера и подключен к выходу четвертого триггера, S-вход которого соединен с пер- 15 вым входом элемента ИЛИ и подключен к выходу первого одновибратора, а вы09

8 ход второго одновибратора подключен к R — входу четвертого триггера и второму входу элемента ИЛИ, выход которого является первым выходом узла управления, вторым, третьим, четвертым и пятым выходами которого являются соответственно прямой выход второго триггера, инверсный выход третьего триггера, инверсный выход второго триггера и выход четвертого триггера, входом останова, тактовым входом и входом запуска узла управления являются соответственно вход первого одновибратора, тактовый вход первого триггера и вход второго одновибратора.

1425709

0425 ЧХб7

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

Техред М,Дидык Корректор M. Васильева

Редактор М. Бланар

Заказ 4773/49

Тираж 704 Подписное

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

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

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