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

 

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

„„SU, 1476488 А1

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

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

РЕСПУБЛИК (51)4 G 06 F 15/332

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

М А BTOPCKOMY СВИДЕТЕЛЬСТВ

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

ПО ИЗОБРЕТЕНИЯМ И OTHPbfTHRM

ПРИ ГКНТ СССР (2 1-) 4141640/24-24 (22) 31.10.86 (46) 30.04.89. Бюл. К 16 (71) Институт технической кибернетики АН БССР (72) .С.Н.Демиденко, В.Н.Дащук, Э.Б.Куновский и П.И.Чеголин (53) 681.32(088.8) (56) Авторское свидетельство СССР

У 1242985, кл. G 06 F 15/332, 1985.

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

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

Поставленная цель достигается за счет того, что в состав устройства входят синхронизатор 1, счетчик адреса 2, блок постоянной памяти 3, счетчик адреса 4, входной регистр 5, регистр 6, входной регистр 7, блок памяти 8, сумматор-вычитатель 9, умножитель 10, мультиплексоры 1 1, 12, сумматоры 13, 14, мультиплексор 15, информационные вход 16 и выход 17.

14764

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

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

На фиг.1 показана структурная схе- 15 ма устройства; на фиг. 2 — алгоритм

1быстрого преобразования Фурье (БПФ), реализованный в устройстве.

Устройство содержит синхронизатор

1, счетчик 2 адреса, блок 3 постоян- 2р ной памяти, счетчик 4 адреса, входной регистр 5, регистр 6, входной регистр 7, блок 8 памяти, сумматорвычитатель 9, умножитель 10, первый

11 и второй 12 мультиплексоры, пер- 25 вый 13 и второй 14 сумматоры, третий мультиплексор 15, информационные вход 16 и выход 17.

Граф алгоритма БПФ приведен для Зр исходного массива длиной в 16 значений. На фиг.2 используются следующие обозначения: входная последовательность 18, выходная последовательность

19, коэффициентов Фурье, операции 20* 35 применяемые в алгоритме.

Устройство работает следующим образом.

Выполнение БПФ включает три эта. па: ввод исходной информации, вычис- 40 ление клэффициентов Фурье и вывод результатов преобразования.

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

15 с входа 16.

Этап вычисления коэффициентов Фурье включает несколько шагов. На первом

5Р .шаге в соответствии с алгоритмом выполняются операции сложения и вычитания отсчетов. Синхронизатор 1 передает в счетчик 4 сигнал, по которому в последнем формируется и передается на блок 8 памяти код адреса первого перанда, представляющего собой неоторый х-й входной отсчет (i=0,1,...

88 2

N/2-1). Считанный из блока 8 памяти операнд фиксируется во входном регистре 5. С выхода последнего цифровой код поступает на вход сумматора- вычитателя 9 и через мультиплексор

11 на вход сумматора )4. На счетчике

4 адреса по сигналу синхронизатора 1 формируется код адреса второго операнда, являющегося (i+N/2)-м входным отсчетом. С выхода блока 8 памяти значение операнда поступает на вход" ной регистр 7 и фиксируется в нем.

Отсюда цифровой код подается на второй вход сумматора-вычитателя 9 и через второй 12 мультиплексор на другой вход сумматора 14. Синхронизатор 1 одновременно с передачей в счетчик 4 сигнала для формирования адреса первого операнда подает управляющие сигналы в сумматор-вычитатель 9, переводя его в режим суммирования операндов, и на входы мультиплексоров

11 и 12 для коммутации выходов входных регистров 5 и 7 на входы сумматора 14. Сумматор-вычитатель 9 осуществляет сложение операндов, поступающих на его входы, а сумматор 14— вычитание второго операнда из первого. С выходов сумматора-вычитателя 9 и сумматора 14 результаты поступают соответственно на четвертый и второй входы мультиплексора 15. По сигналам с синхронизатора 1 эти данные последовательно передаются в блок 8 памяти и фиксируются по адресам операндов, считанных из него в начале выполнения шага. Аналогично происходит обработка остальных пар отсчетов на первом шаге алгоритма.

Выполнение второго шага включает только операции сложения-вычитания и происходит в целом подобно первому шагу. Однако в данном случае используются другие коды адресов, задаваемые по командам синхронизатора 1 из счетчика 4 в блок 8 памяти (в данном случае из блока 8 памяти в соответствии с алгоритмом так же, как и на предыдущем шаге, выбираются такие пары операндов, над которыми надо . производить операции сложения и вычитания). Кроме того, на данном шаге присутствуют операнды, над которыми не требуется выполнять какие-либо .преобразования (с номерами N/2 и 11/4).

Эти отсчеты не считываются из блока

8 и не подвергаются обработке.

1476488

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

Помимо процедур, выполняемых на первом и втором шагах, вводятся две дополнительные вычислительные процедуры. !

О !

Первая из процедур может быть описана парой операций вида .а+сЬ и a-cb, где операнды а и Ъ - отсчеты, полу ченные в предшествующий такт выпол 15 нения алгоритма: с — весовой коэффи,циент.

Данная процедура является основной для последнего и-го шага алгоритма (выполняется над N-4 операнда20 ми). Кроме того, она присутствует в

Imarax с номерами 3,4,...,n-l и выМ полняется в каждом из них над 2 опе рандами, где k — номер шага.

Устройства при выполнении этой процедуры функционирует следующим образом.

По сигналам с синхронизатора 1 счетчик 4 последовательно формирует коды адресов, по которым из блока 8 памяти считывается очередная пара

30 операндов и записывается во входные регистры 5 и 7 (отсчитываемые операнды а,Ь выбираются такими, .над которыми должна быть выполнена пара операций а+сЬ и а-сЪ. Для представленного на фиг.2 алгоритма при N=16 на третьем шаге это отсчеты с номерами 8 и )О, )2 и )4; на четвертом (последнем) шаге — 4 и 5; 6 и 7 и т.д.). Одновременно по сигналам из синхронизатора 1 счетчик 2 адреса формирует и передает на блок 3 постоянной памяти код адреса, по которому из него считываются и фиксируются в регистре значения соответствующего

45 весового коэффициента. С выхода регистра 6 код коэффициента передается на вход первого множителя 10 на второй вход которого передается содержимое входного регистра 7 ° Результат умножения подается на второй вход сумматора 13 и через мультиплексор

12 на первый вход сумматора 14. На другие входы сумматоров 13 и 14 через мультиплексор 11 подается код операнда с выхода первого входного регистра 5. В сумматоре 13 происходит сложение, а в сумматоре 14 вычитани операндов. Результаты из сумматоров

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

Вторая вычислительная процедура описывается парой выражений вида (а-Ъ)+2сЬ и (а-Ь)-2сЬ. Отличие ее выполнения от первой процедуры заключается в том, что мультиплексор

11 подключает на входы сумматоров 13 и 14 не входной регистр 5 а сумматор-вычитатель 9, который переводится в режим вычитания синхронизатором

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

14 передаются в блок 8 памяти и фиксируются в нем. Аналогично производится обработка и остальных пар операндов. На этом заканчивается обработка устройством третьего шага алгоритма.

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

На последнем шаге алгоритма над отсчетами с номерами 0,1 выполняется пара операций вида a+b, а-Ь, которая характерна для первого шага.

Над отсчетами с номерами 2 и 3 операций не производится. Над остальными парами операндов производятся опе" рации, аналогичные первой вычисли" ,тельной процедуре алгоритма с номерами 3,4,. ° .,n-1.

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

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

àî,a à N/2 b,,bq,...,b N/2 °

5 147

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

Устройство для быстрого действительного преобразования Фурье, содержащее синхронизатор, первый.. и второй выходы которого подключены к счетным входам соответственно первого и второго счетчиков адреса, информационные выходы которых подключены к адресным входам соответственно блока постоянной памяти и блока памяти, третий и четвертый выходы синхронизатора подключены соответственно к входу чтения блока постоянной памяти и входу управления за-.. писью-считыванием блока памяти, выход которого подключен к информационным входам первого и второго входных регистров и является информационным выходом устройства, выход блока постоянной памяти подключен к информационному входу регистра, тактовый вход которого подключен к пятому выходу синхронизатора, шестой и седьмой выходы которого подключены к тактовым входам соответственно первого и второго входных регистров, умножитель, два сумматора, первый, второй и третий мультиплексоры, выходы которых подключены соответственно к первому входу первого сумматора, пер,вому входу второго сумматора и информационному входу блока памяти, выходы первого и второго сумматоров подключены соответственно к первому, второму информационным входам треть6488,. 6 его мультиплексора, третий информационный вход которого является информационным входом устройства, выход второго входного регистра под5 ключен к первому информационному входу второго мультиплексора и первому входу умножителя, выход которого подключен к второму информационному вхо1О ду второго мультиплексора, управляющие входы первого, второго и третьего мультиплексоров подключены соответственно к восьмому, девятому и десятому выходам синхронизатора, а вы15 ход регистра подключен к второму входу умножителя, о т л и ч а ю щ е ес я тем, что, с целью увеличения быстродействия, в него введен сумматор-вычитатель, первый информационный вход которого соединен с первым информационным входом первого мультиплексора и подключен к выходу первого входного регистра, выход второго входного регистра подключен к второ25 му информационному входу сумматора-вычитателя, выход которого подключен к четвертому информационному входу третьего мультиплексора и второму информационному входу первого мультиЗО плексора, выход которого подключен к второму входу второго сумматора, второй вход первого сумматора подключен к выходу умножителя, а управля- ющий вход сумматора-вычитателя под35 ключе одиннадцатому вь оду синхро» низатора.

1476488 хО

Xf х х„, х ху х 7 хв х>

Х1

Н юг

lÂ

Х/4 х6

b, ь

IL /Vcugg

1Я

0- bc

Ь

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

Редактор Л.Пчолинская Техред М. Ходанич корректор М.Максимишинец

Заказ 2158/50 Тираж 669 Подписное

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

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

Производственно-издательский комбинат "Патент", г. Ужгород, ул. Гагарина,103