Процессор быстрого преобразования Фурье Советский патент 1988 года по МПК G06F17/14 

ГС

ел

о со

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

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

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

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

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

Узелуправления (фиг.4) содержит одновибратор 8, триггеры 9-12, элемент ИЛИ 13 и одновибратор 14. I Блок 4 адресации (фиг.5) содержит ;Узел 15 управления, мультиплексор 16 ;счетчик 17, мультиплексор 18, ре- гистр 19, коммутатор 20, компаратор 21,. элементы ИЛИ 22 и 23, элементы И 24 и 25, сдвигатель 26, одновибратор 27, мультиплексор 28, элемент И 29, одновибратор 30, элемент ИЛИ 3 триггер 32, реверсивный счетчик 33, элемент И 34, элемент НЕ 35.

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

По включению питания все регистры и счетчики устанавливаются в О. Триггер 9 узла 15 устанавливается в 1, которая блокирует 10- 12 и устанавливает их в О. О на выходе узла 15 обеспечивает подключение выходов триггера 32 и счетчика 17 через мультиплексор 28 к адресной шине блока 4 адресации. 1 на выходе узла 15 обеспечивает прохождение тактовых импульсов через элементы И 24 и 25, что обусловливает

о

Q

..

5

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

При передаче последнего коэффици-. ента в блок 3 памяти блок 1 формирует сигнал конца преобразования, который поступает на вход блок 4 адресации и запускает одновибратор 14, устанавливающий триггер 9 в О. Одиночный импульс с выхода одновиб- ратора 14 поступает также на R-входы триггера 32 и счетчиков 17 и 33 и устанавливает их в О. О на входах элементов ИЛИ-22 и 23 разрешает управление прохождением тактовых импульсов через элементы И 24 и 25 от компаратора, а также управление мультиплексором 16 и триггером 32 от мультиплексора 18. Кроме того, по импульсу с выхода одновибратора 14 в регистр 19 записывается код, управляющий размерностью преобразования. Максимал.ьная размерность определяется разрядностью счетчика 17 плюс единица (поскольку триггер 32 формирует младший разряд адресного кода). .

При этом для размерности (п-1)-й разряд счетчика 17 подключается через элемент И 34 и к S-входу триггера 32 и управляющему входу мультиплексора 16, а сдвигатель 26 обеспечивает сдвиг исходного кода X на i разрядов в сторону младших раз г рядов. Пусть (). Рассмотрим процедуру перестановки двух операн- /(ов, которая выполняется за четьфе такта. По импульсу с выхода элемента ИЛИ 13 счетчики 17 и 33 и триггер 32 устанавливаются в О. На выходе 0 г X компаратора устанавливается 1, а на выходе of X компаратора О, тем самым следующий тактовый импульс поступает на тактовьй вход триггера 1 узла 15. При этом управляюпще сигналы для блока 3 не сформированы, а содержимое счетчика (триггер 32 - счетчик 17) увеличивается на единицу. При этом на выходах компаратора 21

состояние изменяется на противоположное, т.е. разрешается прохождение последующих тактовых импульсов на тактовый вход узла 15, на выходах которого формируются сигналы согласно временной диаграмме (фиг.З). Высоким уровнем сигнала на выходе узла к адресному входу блока 3 подключается модифицированный код oi 00...01 и из ячейки памяти с этим адресом считывается первый операнд и записывается в регистр 5 блока 2 перестановки.

Далее по второму такту низким уровнем сигнала на выходе узла и адресному входу через мультиплексор 28 подключается исходньй код .. и в регистр 5 записывается второй операнд, при этом первый операнд переписывается в регистр 6 блока 2 перестановки и поступает на информационный вход блока 3 памяти. По следующему такту формируется сигнал WR/RD записи и первый операнд записывается по адресу исходного кода X. Далее высоким уровнем на выходе узла 15 по второму адресу записывается второй операнд.

Затем перепадом из О в М на выходе узла 15 содержимое счетчика (триггер 32 - счетчик 17) увеличивается на единицу и процедура перестановки следующей пары операндов повторяется аналогично. При блокировке узла 15 (содержимое счетчика триггер 32 - счетчик 17 увеличивается на единицу) перестановка не осуществляется Указанная процедура формирования адресов перестановки осуществляется вплоть до адреса N/2-1. Далее при адресе, равном N/2, 1 старшего разряда модифицированного кода поступает через мультиплексор 18 на управляющий вход мультиплексора 16 и S-вход триггера 32. При этом на выходе триггера 32 устанавливается 1, а тактовые импульсы через мультиплексор 16 поступают на тактовый вход счетчика 17. Далее модифицированный код формируется с шагом два, т.е. в диапазоне адресов от N/2 до N-1 анали- зируется только N/4 нечетных адресов

Реверсивньи5 счетчик 33 включен параллельно счетчику 17, на управляющий вход счетчика 33 поступает сигнал с выхода мультиплексора 18. При О счетчик 33 работает в режиме суммирования, а при адресе N/2 и

10

15

25709

выше в режиме вычитания. Таким образом, при формировании счетчиком 17 (N-l)-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 содержатся данные, упорядоченные в естественном порядке.

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

25

30

35

45

40

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

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

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

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

5

0

5

0

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

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

0

5

0

7

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

425709

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

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

гера, S-вход которого соединен с пер- 15 одновибратора, тактовый вход первого

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

фие.2

и вход второго одновибра1 г ъ 1 г//jnJTjnjnJTJTTL

5 4

5

О i 2 5 4561

1