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

Процессор быстрого преобразовани Фурье относится к вычислительной те нике и может быть использован при решении задач гармонического анали за, где необходимо выполнять прямое или обратное преобразование Фурье функций,заданных дискретными отсчетами, а также при цифровой обработк сигналов в реальном масштабе времен В известном процессоре дискрет отсчеты хранятся в оперативном запо 1линаюцем устройстве (ОЗУ) , а сомно хители матрицу преобразований - в постоянном запоминающем устройстве (ПЗУ) . Вычисление спектра происходит поэтапно. При этом дискретные векторы отсчетов попарно выбираются из ОЗУ и после умножения на соответствующие коэффиш1енты преобразования записываются в ОЗУ по тем же адресам. Наиболее близким по технической сущности к предлагаемому является специализированный процессор для быстрого решения задач гармоничес кого анализа, состоящий из арифметического устройства, оперативного запоминающего устройства (ОЗУ), пос тоянного запоминающего устройства (ПЗУ), регистра адреса ОЗУ, регистра адреса ПЗУ, формирователя сигналов приргцдений регистров, счетчика отсчетов, счетчика итераций и устройства управления и сопряжения с ЭВМ 2 .. 1. . Повьяаенное число арифметических операций при вычислении спектра, который действительного сигнала симметричен относительно ординат и все его отсчеты комплексно сопряжены, вследствие чего для дальнейшего использования результатов преобразования Фурье достаточно половины отсчета спектра. Вычисление всего спектра приводит к уменьшению быстродействия процессора. Цель изобретения - повышение быстродействия. Поставленная цель достигается тем, что процессор быстрого преобразования Фурье, содержащий арифметическое устройство, блок памяти, блок постоянной памяти, регистр алреса памяти, регистр ёщреса постоянной пгцлятн, счетчик отсчетов, счетчик итераций, устройство управления, формирователь сигналов приращений регистров, первый и ВТОРОЙ выход которого подключен ко входам соответственно регистра адреса памяти и регистра адреса постоянной памяти, выход которого содинен со входом блока постоянной памяти, выход которого подключен к первому входу арифметического устройства, выход которого соединен с первым рходом устройства управления, первый выход которого подключен к .первому -входу блока памяти, выход которого соединен со вторым входом арифметического устройства и вторым входом устройства управления, второй выход которого подключен ко входу счетчика отсчетов, первый выход которого соединен с первым входом формирователя сигналов приращений регшстров, второй вход которого подключен к выходу счетчика итераций, вход которог подключен ко второму выходу счетчика отсчетов, выход регистра адреса памяти соединен со вторым входом блока памяти, а третий вход устройства управления является тактовым входом процессора, в него введены узел формирования дополнительного кода, блок сравнения и дополнительный регистр адреса, группа выходов которого соединена со входами первой группы блока сравнения, первый выход которого подключен к третьему входу формирователя сигналов приращений регистров, третий выход которого подключен ко вкоду дополнительного регистра адреса, группа выходов регистра адреса памяти подключена ко входам второй группы блока сравнения, второй выход которогосоединен со входом устройства формирования дополнительного кода, выход которого соединен с третьим входом блока памяти.

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

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

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

Через устройство 9 с ЭВМ поступают сигналы, включающие счетчик 7 отсчетов и счетчик 8 итераций. В зависимости от кодов на выходах этих счетчиков формирователь б подает сигналы на регистр 4, регистр 5 и дополнительный регистр 12, которые формируют адреса обращения, к блокам 2 и 3 согласно графу БПФ. При э.том приращение дополнительного регистра 12 отстает на один период от приращени 4,т.е. регистр 12 постоянно повторяет коды предыдущей итерации.Блок срвнепия вьще/1яет в каждой итерации номера гармоник, расположенных, во 2 и 4 квадрантах. Если код одного из этих адресов появится на регистре 4 или на регистрах 4 и 12 однойременно, то е на втором выходе блока 11 образуется сигнал запрета арифметических операций и происходит выборка следующих отсчетов. При появлении указан- ных кодов только на регистре 12, на первом вы}:оде блока 11 возникает сигнал, по которому устройство образования дополнительных кодов 10 формируют адреса памяти в дополнительном коде.

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

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

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

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

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

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

5 гармоники с W 3-7 во 2-м и 4-м квадрантах имеют симметрично располо-. жеаные гармоники соответственно с № 5-1. В связи с этим, гармоники 3-7 можно не вычислять, а для образова- .

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

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

В 4-й итерации опускаются вычисления гармоник с №№ 5-13, 6-14, 7-15. Однако для вычисления гармоник с №№ 3-11 необходимаГармоника 3 из

03-й итерации, оценки которой размещены b ячейках ОЗУ 24, 26, 25 и 27. Так как гармоники 3-7 не- вычислялись в 3-й итерации, то исходными данными для вычисления гармоник 3-11 является гармоника 5, оценки которой расположены в ячейках памяти 20, 22, 21 и 23. Коды адресов этих ячеек памяти являются дополнительными кодами номеров вычисляемых гармоник.

0 В 5-й итерации опускаются вычисления гармоник с W 9-25, 10-26, 11-17, 12-28, 13-29, 14-30 и 15-31. Исходные данные для вычислений гармоник 5-21, 6-22,и 7-.23 расположены

5 в ячейках памяти 20, 21, 12-13 и

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

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

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

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

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

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

1,Авторское свидетельство СССР 467356, кл. G 06 F 15/34 1978.

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