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

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

Цель изобретения - расширение функ

циональных возможностей устройства

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

В исходном состоянии на второй вход процессора поступает код, соответствующий длине массива N 8, на третий вход - код, соответствующий начальному адресу пpoгpaм iы работы

и обратного преобразований Фурье при различных длинах обрабатываемых массивов.

На.фиг,1 представлена функциональ- 5 ная схема процессора-, на фиг.2 - функциональная схема блока формирования каманд; на фиг.З - схема блока формирования адресов, на фиг.4 - схема блока синхронизации,- на фиг.З - диаграм-20 процессора (в данном случае вычисле- .ма преобразования адресов.нию программы свертки), в блоке 17

Процессор быстрого преобразования Фурье (БПФ) содержит мультиплексор 1,

блоки 2 и 3 (оперативной) памяти, щщей на вход процессора, блок синхро- мультиплексор 4, арифметический блок низации вырабатывает сигнал Уст. О, 5, регистры 6 и 7 адреса, блок 8 постоянной памяти, мультиплексоры .9 и 10, регистр 11 адреса (постоянной памяти), блок 12 формирования команд, (итерационный) сдвиговыу регистр 13, блок 14 формирования адресов, счетчик 15 отсчетов, блок 16 сиш :ронизации.

памяти хранятся спектры эталонных По команде Пуск

сигналов,

поступа30

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

блок 17 памяти, сдвигатель 18, мультиплексор 19, счетчик 20 и реверсивный счетчик 21,

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

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

O

Блок 16 синхронизации (фиг.4) содержит генератор 36 тактовых импульсов, распределитель 37 импульсов, элемент 1-ШИ 38, элемент И 39 и ждущий мультивибратор 40.

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

В исходном состоянии на второй вход процессора поступает код, соответствующий длине массива N 8, на третий вход - код, соответствующий начальному адресу пpoгpaм iы работы

5 0 процессора (в данном случае вычисле- нию программы свертки), в блоке 17

щщей на вход процессора, блок синхро- низации вырабатывает сигнал Уст. О,

памяти хранятся спектры эталонных По команде Пуск

сигналов,

поступащщей на вход процессора, блок синхро- низации вырабатывает сигнал Уст. О,

0

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

На выходе ПЗУ формируются сигналы, обеспечивающие выполнение операций и ввода массива отсчетов. При этом через мультиплексор 1 первый вход процессора подключается к входу блока 2 памяти. Выход, счетчика 20 через первый, вход мультиплексора 19 подключается на вход сдвигателя 18, причем все разряды.двоичноинвертированы. На управляюЕщй вход сдигателя 18 с выхода формирователя команд поступает код, обеспечивающий сдвиг кода адреса в младшие разряды, при этом в старших .разрядах - нули. Диаграмма, поясняющая эти операции,, приведена на фиг.5. Из диаграммы видно, что при N 8 на выходе сдвигателя остаются только три разряда счетчика, при N 16 - четыре разряда и т.д., при этом они двоичноинвертированы,, В общем случае сдвигатель должен обеспечивать сдвиг кода на число разрядов М log N, где М - количество разрядов счетчика ад5

0

5

3-1

реса. Код с выхода сдвигателя 18 че- .рез открытый вход мультиплексора 9 поступает на адресный регистр 6 и далее - на блок 2 памяти. Мультиплексо 24 контролирует старшие разряды счетчика 15, при этом при N 8 на выход мультиплексора выводится 4-р1 разряд (при N 16 - пятый и т.д.).

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

За время выполнения базовой операции вырабатывается 22 синхросигнала. При операции ввода массива за время выполнения базовой операции обеспе- чивается запись одного отсчета, и ввод всего массива завершается за дв итерации. Подсчет числа базовых операций осуществляется счетчиком 15. На выходе блока 16 формируется сумма двух синхросигналов СИ 11 и СИ 21, которая поступает на счетный вход счетчика 15. Первый разряд четвертого выхода при операции ввода находится в состоянии 1 и разрешает прохождение синхросигналов через элемент И 27 на счетный вход счетчика 20 адресов ввода. После ввода четырех отсчетов (N/2) четвертый разряд счетчика 15 устанавливается в состояние 1. Че- рез мультиплексор 24 и элемент И 25 (на второй вход элемента И 25 поступает высокий уровень с восьмого выхода ПЗУ) на счетный вход счетчик-а 23 поступает сигнал +1. Состояние счетчика увеличивается на единицу. Кроме того, сигнал с выхода мультиплексора 24 через элемент ИЛИ 30 поступает на вход установки в нуль счетчика 15 . Начинает выполняться вторая итерация операции ввода. Состояние выходов ПЗУ сохраняется. После ввода остальных четьфех отсчетов в счетчик 23 добавляется единица. На выходах ПЗУ формируются сигналы, об.еспечивающие выполнение операции прямого преобразования Фурье. При этом на первом выходе блока 12 формирования команд устанавливается сигнал О, и выход блока 5 через второй вход .мультиплексора 1 подключается на вход блока 2 памяти. На четвертом выходе блока формирования команд устанавливается код 001, при котором мультиплексор 9 подключает на вход регистра 6 адреса выход формирователя 14 адресов. На девятом выходе ПЗУ устанавливается код 01, настраивающий блок на выполнение операции БПФ. В

1354

процессоре реализован алгоритм БПФ с основанием 2 с двоичной инверсией отсчетов на входе с замещением. На одиннадцатом выходе ПЗУ устанавливается уровень 1, при этом выход мультиплексора 24 через элемент И 26 подключается к тактовому входу ре гистря 13 сдвига.

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

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

Код адреса весового коэффициента формируется на счетчике 35,, причем за счет входной логики счетные импульсы поступают на тот разряд счетчика, на который приходит 1 со сдвигового регистра 13. При появлении 1 в четвертом разряде счетчика 15 добавляется 1 в счетчик 23 и проходит сигнал регистра 13 сдвига. Начинается вьшол- нение второй итерации. После выполнения третьей итерации на выходах ПЗУ устанавливаются коды, при которых выполняется операи:ия перемножения комплексных массивов. При выполнении этой операции спектр сигнала находится в блоке 2 памяти, эталонные спектры - в блоке 17 памяти и поступают на второй и первый входы арифметического блока 5 соответственно. Результаты перемножения записываются в блок 3 памяти. Адреса считывания спектра сигнала образуются на счетчике 20 и через второй вход мультиплексора 9 (определяется кодом на четвертом выходе блока 12 формирования команд) и регистр 6 поступают на адресный вход блока 2 памяти. Адреса считывания эталонного сигнала формируются на счетчике 20.

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

Исходный массив: О,1,2,3,..N-2,N-1 Переупаковочный массив: 0,,N-1 ,N-2., .4,3,2,1 Кроме того, учитывая, что в процессоре используется граф -с двоичной инверсией отсчетов на входе, необходимо произвести двоичную инверсию отсчетов ,

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

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

которому из ПЗУ считываются КОДД; КО

0

5 Q

с

5

0

0

5

манды, обеспечивающие выполнение операции обратного преобразования Фурье. При этом выход блока 12 формирования .адресов через вход мультиплексора 10 и регистр 7 подключается к адресному входу блока 3 памяти. Выход последнего через вход мультиплексора подключается к второму входу арифметического блока 5. В остальном операция выполняется аналогично операции прямого преобразования Фурье. Результаты вы- . числений находятся Е блоке 3 памяти. После выполнения операции обратного преобразования Фурье на выходе ПЗУ формирутатся коды команд, обеспечивающие выполнение операций вывода. При этой операции адреса считывания для блока 3 памяти формируются- на счетчике 21, который в этом случае работает на сложение. Адреса поступают на вход блока 3 памяти через вход мультиплексора 10 и регистр 7. Операция вывода длится две итерации. Далее по программе выполняется операция перемножения комплексных массивов, причем на седьмом выходе блока 12 формирования адресов появляется код 001, и при выполнении операции перемножения из блока 17 памяти считывается второй эталонный спектр. .Операции обратного преобразоззания Фурье и вывода выполняются так же, как и в первом цикле. При соответствующем увеличении объема блока 17 памяти и удлинении программы можно производить обработку с различным числом копий. Ввод эталонных сигналов в блок 17 памяти при необходимости можно выполнять одновременно с обра- бот кой сигнала, например с выполнением операций вычисления преобразования Фурье. При появлении на счет чике 23 кода 0011 на выходе формирователя ко-, манд устанавш вается сигнал О, ко- торый поступает на входы элементов И 39, ИЛИ 38 и блокирует работу распределителя 37 И1 1пульсоз, Процессор пе- реходит в режт-гм ожидания до появления следующего запускающего импульса Пуск. Работа процессора при этом повторяется аналогично описанной вьше.

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

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

7 1

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

блок памяти и блок формирования ко-

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

1358

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

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

9127

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

i .KJ

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

Вх.1

Cuf/ rflffct/ffffiy/ M t t

f

Г

iS

(ffUff.i

Cff

0X.2

ffirfx. 2

36

ffjf.1

„/7ус

1

J9

0

о Ы

С(г

c,

/-f. ЛУ

of, (д| ---. pj

(oaf 73

p/r ;r.|

or.

of cf.

Вых.го

Af S

5

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

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

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

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

ВНИРШИ Государственного комитета СССР по делам изобретений и открытий 113035, Москва Ж-35, Раушская наб., д. 4/5

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

Ctjf f ffcu &-frer/

СИ 11 С И 22 ,i/c/7.o

/tv/tv

J7

7V 7

4-0

Фиг A

o(.

of.

n-f

0(,

Q /7./

o-j

C3f5

/Vi

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