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

 

Изобретение относится к вычислительной технике и предназначено для вычисления коэффициентов прямого и обратного преобразований Фурье при различных длинах обрабатываемых массивов , в том числе вычисления сверток, счетчик, мультиплексор, пять элеменИзобретение может быть использовано для построения цифровых систем обработки в различных областях техники. Цель изобретения - расширение функциональных возможностей устройства за счет вычисления прямого и обратного преобразований Фурье при различных длинах обрабатываемых массивов. Поставленная цель достигается за счет того, что процессор имеет в своем составе арифметический блок, три блока памяти, блок постоянной памяти, пять мультиплексоров, три регистра адреса, блок формирования команд, сдвиговый регистр, блок формирования адресов, счетчик отсчетов, блок синхронизации, сдвигатель, счетчик и реверсивный . счетчик. Причем блок формирования команд содержит узел постоянной памяти. счетчик, мультиплексор, пять элементов И и три элемента ИЛИ. 1 з.п.ф-лы, 5 ил. а О) to со сд

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

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

РЕСПУБЛИК

„„ЯЦ„„1277135 А 1

yg g G Об F 15/332

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

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

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

ll0 ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ (21) 3903425/24-24 (22) 29. 05. 85 (46) 15 ° 12. 86. Бюл. Ф 46 (72) В.П.Карасев и В.А.Шаньгин (53) 681.32(088.8) (56) Патент США и 3680105, кл, G 06 F 15/332, 1974.

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

Р 1119027, кл. G 06 F 15/332. (54) ПРОЦЕССОР БЫСТРОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ (57) Изобретение относится к вычислительной технике и предназначено для вычисления коэффициентов прямого и обратного преобразований Фурье при. различных длинах обрабатываемых массивов, в том числе вычисления сверток.

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

Цель изобретения — расширение функциональных возможностей устройства за счет вычисления прямого и обратного преобразований Фурье при различных длинах обрабатываемых массивов. Поставленная цель достигается за счет того, что процессор имеет в своем составе арифметический блок, три блока памяти, блок постоянной памяти, пять мультиплексоров, три регистра адреса, блок формирования команд, сдвиговый регистр, блок формирования адресов, счетчик отсчетов, блок синхронизации. сдвигатель, счетчик и ревераивный счетчик. Причем блок формирования команд содержит узел постоянной памяти, счетчик, мультиплексор, пять элементов Й и три элемента ИЛИ. 1 з.п. ф-лы, 5 ил.

1277135

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

Цель изобретения — расширение функциональных возможностей устройства 10 за счет выполнения, помимо прямого, и обратного преобразований Фурье при различных длинах обрабатыг»емых массивов.

На фиг.1 представлена функциональ- 1> н»я схема процессора; на фиг.2 — функциональная схема блока формирования каманд," на фиг.З вЂ” схема блока формирования адресов, на фиг.4 — схема блока синхронизации; на фиг,5 — диаграм- 20 ма преобразования адресов.

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

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

5, регистры 6 и 7 адреса, блок 8 посToHHHoII памяти, мультиплексоры 9 и

10, регистр 11 адреса (постоянной памяти), блок l2 формирования команд, (итерационный) сдвиговьи регистр 13, блок 14 формирования адресов, счетчик

15 отсчетов, блок 16 синх!зонизации, блок 17 памяти, сдвигатель 18, мультиплексор 19, счетчик 20 и реверсивный счетчик 2 !. 35

Блок 12 формирования команд (фиг,2) вырабатывает необходимые упр»вляюшие сигналы для блоков процес- 40 сора, обеспечивая выполнения заданной программы работы. Формирователь команд содержит узел ?2 постоянной памяти, счетчик 23„ мультиплексор 24, элементы И 25-29, элементы ИПИ30-31.

Блок 14 формирования адресов (фиг.Ç) служит для выработки адресов опер»пдов и весовых коэффициентов, необходимых для выполнения алгоритма

БПФ. Структурная схема блока определяется основанием алгоритма БПФ, уровнем совмещения операций B процессоре, На фиг.З приведена схема блока для алгоритмов БПФ с основанием 2 с замещением. Формирователь адресов содержит мультиплексор 32, поразрядные двухоходовые элементы ИЛИ 33, счетчики адресов операндов 34 и адресов коэффициентов 35, Блок 16 синхронизации (фиг.4) содержит генератор 36 тактовых импульсов, распределитель 37 импульсов, элемент ИЛИ 38, элемент И 39 и ждущий мультивибратор 40.

Рассмотрим работу процессора на примере обработки массива N = 8 при вычислении свертки,. Как известно, для вычисления свертки необходимо выполнить следующие операции: вычисление спектра входной ре»лизации, перемножение спектров входного и эталонного сигналов, обратное преобразование

Фурье от результат» перемножения.

В исходном состоянии иа второй вход процессора поступает код, соответствующий длине массива !! = 8, на третий вход — код, соответствующий начальному адресу программы работы процессора (в данном случае вычисленио программы свертки), н блоке 17 памяти хранятся спектры эталонных сигналов. По команде "Пуск", поступающей на вход процессора, блок синхронизации вырабатывает сигнал "Уст. 0", который поступает на все блоки процессора и блокирует выработку cIIIIxpoсигналов распредепителя 37 на время, определяемое длитепьностью импульса ждущего мультивибратора 40. По заднему фронту этого сигнала в счетчик 23 заносится начальный адрес провраммы работы процессора, а в младший разряд итерационного сдвигового регистра за-. носится "1".

На выходе ПЗУ формируются сигналы, обеспечивающие выполнение операций и ввода массива отсчетов. При этом через мультиплексор 1 первый вход процессора подключается к входу блока 2 памяти, Выход счетчика 20 через первый вход мультиплексора 19 подключается на вход сцвигателя 18, причем

t все разряды двоичноинвертиров»ны. На управляющий вход сдигателя 18 с выхода формирователя команд поступает код, обеспечивающий сдвиг кода адреса в младшие разряды, при этом в старших .разрядах — нули, /(и»грамма, поясняющая эти операции,.приведена на фиг.5, Из диаграммы видно, что при N = 8 на выходе сдвигателя остаются только три разряда счетчика, при N = 16 — четыре разряда и т.д., при этом они двоичноинвертированы„ В общем случае сдвигатель должен обеспечивать сдвиг кода на число разрядов N lop N где

И вЂ” количество разрядов счетчика ад1277

3 реса, Код с выхода сдвига"åëÿ 18 через открытый вход мультиплексора 9 поступает на адресный регистр 6 и далее — на блок 2 памяти. Мультиплексор

24 контролирует старшие разряды счет5 чика 15, при этом при N =- 8 на выход мультиплексора выводится 4-й разряд (при N = 16 — пятый и т.д.).

После окончания импульса "Уст. 0 распределитель импульсов 37 начинает 10 вырабатывать синхросигналы.

За время выполнения базовой операции вырабатывается 22 синхросигнала.

При операции ввода массива за время выполнения базовой операции обеспечивается запись одного отсчета, и ввод всего массива завершается за две итерации. Подсчет числа базовых операций осуществляется счетчиком 15.

На выходе блока 16 формируется сумма 20 двух синхросигналов СИ 11 и СИ 21, которая поступает на счетный вход счетчика 15. Первый разряд четвертого выхода при операции ввода находится в состоянии "1" и разрешает прохожде- 25 ние синхросигналов через элемент И 27 на счетный вход счетчика 20 адресов ввода. После ввода четырех отсчетов (И/2) четвертый разряд счетчика 15 устанавливается в состояние "1". Че- 30 рез мультиплексор 24 и элемент И 25 (на второй вхоц элемента И 25 поступает высокий уровень с восьмого выхода ПЗУ) на счетный вход счетчика 23 поступает сигнал "+i Состояние счетчика увеличивается на единицу.

Кроме того, сигнал с выхода мультиплексора 24 через элемент ИЛИ 30 поступает на вход установки в нуль счетчика 15. Начинает выполняться 10 вторая итерация операции ввода. Состояние выходов ПЗУ сохраняется. После ввода остальных четырех отсчетов в счетчик 23 добавляется единица, На выходах ПЗУ формируются сигналы, обе- 5 спечивающие выполнение операции прямого преобразования Фурье. При этом на первом выходе блока 12 формирования команд устанавливается сигнал

"0", и выход блока 5 через второй вход мультиплексора 1 подключается на вход блока 2 памяти. На четвертом выходе блока формирования команд устанавливается код 001, при котором мультиплексор 9 подключает на вход регистра 6 адреса выход формирователя

14 адресов. На девятом выходе ПЗУ устанавливается код 01, настраивающий блок на выполнение операции БПФ. В

135 процессоре реализован алгоритм БП@ с основанием ? с двоичной инверсией отсчетов на входе с замещением. На одиннадцатом выходе ПЗУ устанавлива-, ется уровень "1", при этом выход мультиплексора 24 через элемент И

26 подключается к тактовому входу регистра 13 сдвига.

Формирователь адресов работает следующим образом (фиг.3). На второй вход блока поступает код с итерационного регистра 13 сдвига. На первый вход поступает младший разряд счетчика 15 отсчетов, который управляет переключением мультиплексора 32. При нулевом значении разряда на выход блока пропускается код счетчика 34, на котором формируются первые адреса базовой операции. При единичном значении разряда на выход пропускается выход схем ИЛИ 33, на которых образуются вторые адреса операндов базовой операции. На входы счетчиков 34 и 35 поступает синхроимпульс, который через схемы входной логики изменяет состояние разрядов счетчиков °

Управление порядком счета осуществляется сдвиговым регистром 13 и состоит в том, что выход разряда итерационного регистра, который находится в состоянии "1", блокирует соответствующий разряд счетчика, запрещая прохождение единиц переноса в этот разряд с предыдущего и разрешая прохождение этих единиц переноса непосредственно в следующий за блокируемым разряд. Адрес второго операнда пары формируется на выходах поразрядньгх элементов ИЛИ 33, на одни входы которых поступает код счетчика 34, а на другие входы — код с итерационного сдвигового регистра 13 с "1" в соответствующем разряде.

Код адреса весового коэффициента формируется на счетчике 35, причем за счет входной логики счетные импульсы поступают на тот разряд счетчика, на который приходит "1" со сдвигового регистра 13. При появлении "1" в четвертом разряде счетчика 15 добавляется "1" в счетчик 23 и проходит сигнал регистра 13 сдвига. Начинается выпол- нение второй итерации. После выполнения третьей итерации на выходах ПЗУ устанавливаются коды, при которых выполняется операция перемножения комплексных массивов. При выполнении этой операции спектр сигнала находит— 1277135 ся в блоке 2 памяти, эталонные спектры — в блоке 17 памяти и поступают ка второй и первый входы арифметического блока 5 соответственно, Результаты перемножения записываются в блок

3 памяти. Адреса считывания спектра сигнала образуются на счетчике 20 и через второй вход мультиплексора 9

{определяется кодом на четвертом выходе блока 12 формирования команд) и регистр б поступают на адресный вход блока 2 памяти. Адреса считывания эталонного сигнала формируются на счетчике 20.

Адреса записи результатов для блока 3 памяти образуются следующим образом. Известно, что для выполнения операции обратного преобразования Фурье достаточно перед ее выполнением произвести .переупаковку массива следующим образом:

Исходный массив: 0,1,2,3...N-2,N-1

Переупаковочныймассив: О, N-1, N-2...4, 3, 2, 1

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

С целью экономии времени такая переадресация массива производится при выполнении операции перемножения комплексных массивов при формировании, адресов записи в блок 3 памяти. При . выполнении этой операции сигнал с выхода счетчика 2 1 через открытый второй вход мультиплексора 19 проходит через сдвигатель и далее через первый вход фльтиплексора 10 и регистр 7 поступает на адресный вход блока 3 памяти. Счетчик 21 работает при этом на вычитание. На вычитающий. вход счетччка 21 поступает сикхросигналы с выхода элемента И 28, ка первый вход которого поступает разрешающий сигнал с третьего выхода ПЗУ. При передаче кода счетчика на сдвигатель выполняется двоичная инверсия разрядов, так же, как и при выполнении операции ввода, осуществляется сдвиг кода на соответствующее количество разрядов. За время базовой операции выполняется перемножение одной пары отсчетов, и вся операция длится две итерации. После выполнения операции перемножения комплексных мсассивов на счетчике 23 устанавливается код„ по которому иэ ПЗУ считываются коды команды, обеспечивающие выполнение операции обратного преобразования Фурье.

При этом выход блока 12 формирования ,адресов через вход мультиплексора 10

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

После выполнения операции обратного преобразования Фурье на выходе

ПЗУ формируются коды команд, обеспечивающие выпблнение операций вывода.

При этой операции адреса считывания для блока 3 памяти формируются на счетчике 21, который в этом случае работает на сложение. Адреса поступают на вход блока 3 памяти через вход мультиплексора 10 и регистр 7.

Операция вывода длится две итерации.

Далее по программе выполняется опера25 ция перемножения комплексных массивов, причем на седьмом выходе блока

12 формирования адресов появляется код 001, и при выполнении операции перемножения из блока 17 памяти считывается второй эталонный спектр.

Операции обратного преобразования

Фурье и вывода выполняются так же, как и в первом цикле. При соответствующем увеличении объема блока 17 памяти и удлинении программы можно производить обработку с различным числом копий. Ввод эталонных сигналов в блок 17 памяти при необходимости можно выполнять одновременно с обра40 боткой сигнала, например с выполнением операций вычисления преобразования Фурье. При появлении на счет гике 23 кода 0011 на вьг оде формирователя ко-, манд устанавливается сигнал "0", ко-

45 торый поступает на в оды элементов И

39, ИЛИ 38 и блокирует работу распределителя 37 импульсов, Процессор пе реходит в режим ожидания до появления следующего запускающего импульса

"Пуск", Работа процессора при этом повторяется аналогично описанной выше.

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

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

7 1277 выходам соответственно первого и второго регистров адреса, вход задания коэффициентов арифметического блока подключен к информационному выходу блока постоянной памяти, адресный вход которого подключен к выходу третьего регистра адреса, информационный вход которого подключен к первому,выходу блока формирования адресов, первый вход которого подключен к выходу первого разряда счетчика отсчетов, счетный вход которого подключен к первому выходу блока синхронизации, вход запуска которого является выходом запуска процессора, информационный выход арифметического блока соединен с информационным входом второго блока памяти и первым информационным входом первого мультиплексора, выход которого подключен к.информационному входу первого блока памяти, информа-„ ционный выход которого подключен к первому информационному входу второго мультиплексора, выход которого подключен к информационному входу ариф- 25 метического блока, информационный выход второго блока памяти подключен к второму информационному входу второго мультиплексора и является информационным выходом процессора, информационным входом которого является второй информационный вход первого мультиплексора, второй выход формирования адресов подключен к первым информационным входам третьего и четвертого мультиплексоров, выходы которых подключены к информационным входам соответственно первого и второго регистров адреса, информационный выход сдвигового регистра подключен к второму входу блока формирования адресов, о т л и а ю шийся тем, что, с целью расширения функциональных возможностей за счет выполнения, помимо прямого, и обратного преобра- 4> зования Фурье при различных длинах обрабатываемых массивов., в .него введены сдвигатель, счетчик, реверсивный счетчик, пятый мультиплексор, третий блок памяти и блок формирования команд, первый, второй, третий, четвертый и пятый выходы блока формирования

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

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

j 2i 713

И, первый и второй информационные входы мультиплексора являются соответ— ственно вторым и третьим входами блока, выход .мультиплексора подключен к первому входу первого элемента И, вто — 5 рой вход которого подключен к выходу восьмого разряда узла постоянной IIàмяти, информационный выход счетчика подключен к адресному входу узла постоянной памяти, выходы разрядов с 10 первого по десятый которого являются соответственно первым, вторым, третьим, четвертым, шестым, пятым, тринадцатым, десятым, четырнадцатым и пятнадцатым выходами блока, выход IS второго элемента ИЛИ является один" надцатым выходом блока, выход одиннадцатого разряда узла постоянной памяти подключен к первому входу второго элемента И, выход которого являет- 20 ся шестнадцатым выходом блока, выход,пве13адцатого р11з рядH уз 11<1 Г3остоя иной

ПАМЯТИ ПОДKПЮ !t Ч K ВТОPОМУ ВХОДУ ПЕР во!о эле3!ента ИЛИ, вь1хол которого является двенадцатым выходом блока, BTTход четвертого разряда узла постоянной памяти подключен к первому входу третьего элемента И, выход которого является седьмым выходом блока, выход третьего разряда узла постоянной памяти подключен к первому входу четвертого элемента И, выход которого является девятым выходом блока, выход седьмого разряда узла постоянной памяти подключен к первому выходу пятого элемента И, выход которого является восьмым выходом блока, вторые входы третьего, четвертого и пятого элементов И и третий вход пер— ваго элемента И объединены и являются тактовым входом блока.

1277135

)277)35

Гиь. ); ытиР ь а ю

СИ11 СФРЮ „Уела 0

Р 0 dg o(g Яу л.. 7g g p (dt о Э «» р-у g(ру 6МОд 7g < (о(о

1 г з о — — — и-р »

»

«

Ф 1 — — — Фд o(g Gfg Цо/х, gP о((у Ъ ау Nä dр

Я а )

Д г ф

Составитель A.Áàðàíîâ

Техред М.Ходанич Корректор A.Обручар

Редактор И.Рыбченко

Заказ б669/44 Тираж 671 Подписное

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

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

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