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

 

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ

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

Союз Советских

Социалистических

Республик

<и788114 (61) Дополнительное к авт. свид-ву (51)М. Кл. (22) Заявлено 29.0179 {21) 2717845/18-24 с присоединением заявки ¹

G 06 Р 15/31

Государственный комитет

СССР по делам изобретений и открытий (23) Приоритет

Опубликовано 1512я0. Бюллетень ¹ 46

Дата опубликования описания 15.1280 (53) УДК 681.14 (088.8) (72) Авторы изобретения

В.В. Звягинцев и Б.И. Павлусь (71) Заявитель (54) ПРОЦЕССОР БЫСТРОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ тоя нного запоминающего устройства (ПЗУ), регистра адреса ОЗУ, регистра адреса ПЗУ, формирователя сигналов приращений регистров, счетчика отсчетов, счетчика итераций и устройства управления и сопряжения с

3ВМ (2) .

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

Цель изобретения - повышение быстродействия.

Поставленная цель достигается тем, что процессор быстрого преобразования

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

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

В известном процессоре11) дискретные отсчеты хранятся в оперативном запоминающем устройстве (ОЗУ), а сомножители матрицы преобразований — в постоянном запоминающем устройстве 15 (ПЗУ) .

Вычисление спектра происходит поэтапно.

При этом дискретные векторы отсчетов попарно выбираются из ОЗУ и 20 после умножения на соответствующие коэффициенты преобразования записываются в ОЗУ по тем же адресам.

Наиболее близким по технической сущности к предлагаемому является 25 специализированный процессор для быстрого решения задач гармонического анализа, состоящий из арифметического устройства, оперативного запоминающего устройства (ОЗУ), пос- 30

Ордена Ленина институт кибернетики АН Украинской ССР

788114

60 B 5-й итерации опускаются вычисления гармоник с 99 9-25, 10-26, ll-17, 12-28, 13-29, 14-30 и 15-31.

Исходные данные для вычислений гармоник 5-21, 6-22 и 7-.23 расположены — 65 в ячейках памяти 20, 21, 12-13 и чен ко входам соответственно регистра адреса памяти и регистра адреса постоянной памяти, выход которого соединен со входом блока постоянной памяти, выход которого подключен к первому входу арифметического устройства, ныход которого соединен с первым уходом устройства управления, первый выход которого подключен к .первому

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

На чертеже схематически изображено устройство °

Устройство состоит из арифметичес кого устройства 1, блока 2 памяти, блока 3 постоянной памяти, регистра

4 адреса памяти, регистра 5 адреса постоянной памяти, формирователя б сигналов приращений регистров, счетчика 7 отсчетов, счетчика 8 итераций, устройства 9 управления, узла 10 формирования дополнительного кода,,блока 11 сравнения и дополнительного регистра 12 адреса.

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

Через устройство 9 с 3BN поступают сигналы, включающие счетчик 7 отсчетов и счетчик 8 итераций. В зависимости от кодов на выходах этих счетчиков формирователь б подает сигналы на регистр 4, регистр 5 и дополнительный регистр 12, которые формируют адреса обращения к блокам 2 и

3 согласно графу БПФ. При этом приращение дополнительного регистра 12 отстает на один период от приращения

4,т.е. регистр 12 постоянно повторяет коды предыдущей итерации. Блок сра внения выделяет в каждой итерации номера гармоник, расположенных во 2 и

4 кнадрантах. Если код одного из этих адресов появится на регистре 4 или на регистрах 4 и 12 однонременно, то

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

1О первом выходе блока ll возникает сигнал, по которому устройство образования дополнительных кодов 10 формируют адреса памяти н дополнительном коде.

Рассмотрим работу процессора на

15 примере N=32 отсчетов. Согласно графу БПФ для N-8 порядок формирования адресов обращения к ОЭУ и ПЗУ показан по 4 итерации в таблице.

Иэ таблицы видно, что.коды каждой

2О пари адресов ОЗУ, необходимых для выполнения элементарной операции преобразования Фурье, различаются только в одном разряде, адреса (условно обозначенном F) . Причем положение этого разряда меняется в кажжой итерации. Коды старших разрядон адреса ОЗУ до разряда%, прочитанные н обратном порядке, показывают номер гармоники.

Начиная с 3 итерации, вычисляются

30 гармоники, расположенные но 2-м и

4-м квадрантах, значения которых в силу симметрии спектра действительного сигнала можно соответственно найти в 3-м и 1-м квадрант, х. Так

35 гармоники с У 3-7 но 2-м и 4-м квадрантах имеют симметрично располо-. женные гармоники соответственно с

9 5-1. В связи с этим, гармоники 3-7 можно не вычислять, а для образования гармоник более высокого порядка в последующих итерациях исходными можно брать гармоники с Р 5-1, адреса которых являются дополнительными кодами номеров гармоник 3-7. Поэтому в 3-й итерации вычисления гармоник

3-7 опускаются.

В 4-й итерации опускаются вычисления гармоник с МР 5-13, 6-14, 7-15.

Однако для вычисления гармоник с

ЮР 3-11 необходима гармоника 3 из

50 3-й итерации, оценки которой размещены в ячейках ОЗУ 24, 26, 25 и 27.

Так как гармоники 3-7 не- вычислялись в 3-й итерации, то исходными данными для вычисления гармоник 3-11 ян55 ляется гармоника 5, оценки которой расположены в ячейках памяти 20, 22, 21 и 23. Коды адресов этих ячеек памяти являются дополнительными кодами номеров вычисляемых гармоник.

788114

Адрес ОЗУ

Адрес ПЭУ

Гармоника, Р

0000-00010

00001-00011

00-100-00110

00101-00111

0-2

0-16 00000-10000

00000-01000

00000-01000

0-8

0-8

0-16 00000-10000

1-3

8-24 01000-11000

4-12 00 100-0100

4-12 00100-01100

2-10 00010-01010

2-10 00010-01010

4-6

8-24 01000-11000

5-7

4-20 00100-10100

8-10 01000-01010

9-11 01001-01011

4-20 00100.-10100

6-14 00110-01110 12-28 01100-11100 12-14 01100-01110

6-14 00110-01110 12-28 01100-11100

13-15 011-01-01111

00001-01001

00001-01001

1-9

2-18 00010-10010 16 — 18 10000-10010

2-18 00010-10010 17-19 10001-10011

1-9

5-13 00101-01101 10-26 01010-11010 20-22 10100-10110

5-13 00101-01101 10-26 01010-11010 21-23 10101-10111

6-22 001100-10110 24-26 11000-11010

6-22 00110-10110 25-27 11001-11011

3-11 00011-01011

3-11 00011-01011

7-15 00111-01111 14-30 01110-11110 28-30 11100-11110

7-15 00111-01111 14-30 01110-11110 29-31 11101-11111

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

28-29. Адреса этих ячеек формируются в дополнительном коде, образованном от номеров гармоник.

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

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

50 ко второму выходу счетчика отсчетов, выход регистра адреса памяти соединен со вторым входом блока памятй, а третий вход устройства управления является тактовым входом процессора, отличающийся тем, что, с целью повышения быстродействия, в него введены узел формирования дополнительного кода, блок сравнения и дополнительный регистр адреса, группа выходов которого соеди О иена со входами первой группы блока сравнения, первый выход которого подключен к третьему входу формирователя Сигналов приращений регистров, третий выход которого подклю6S чен ко входу дополнительного регист 7

788114

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

Корректор В . Бутяга

Редактор A. долиниЧ Техред M.Рейвес

Заказ 8354/57 Тираж 751

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

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

4/5

Филиал ППП Патент г. Ужгород, ул. Проектная, 4

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

Источники информации, принятые во внимание при экспертизе

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

М 467356, кл. 6 06 F 15/34 с 1978.

2. Электроника, 1968, 9 13, т,. 41 (прототип).