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

1

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

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

Известны два направления реализации БПФ:

реализация БПФ в цифровых вычислительных системах на основе ЦВМ широкого назначения;

реализация БПФ в системах обработки данных на основе специализированных цифровых вычислительных машин (СЦВМ).

Использование ЦВМ широкого назначения в отдельных случаях не обеспечивает высокой производительности в связи с наличием специфических особенностей алгоритма БПФ. Так, например, в ходе вычисления коэффициентов Фурье необходимо выполнять сложную перегруппировку адресов ЗУ. Необходимая перегруппировка проводится по простейшей программе, тем не менее ее весьма трудно запрограммировать для ЦВМ широкого назначения, на выполнение этой программы тратится почти половина машинного времени.

необходимого для реализации всего алгоритма.

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

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

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

Эта цель достигается путем схемного выполнения процедуры адресации ячеек блока памяти.

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

Варианты схемы устройства показаны на

фиг. 1 и 2, где обозначены: регистр 1 (регистр

множителя) АУ, обеспечивающий сдвиг кода

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

Выход триггера младшего разряда регистра 2 соединен с входом триггера старшего разряда регистра 1, выход триггера старшего разряда регистра 2 - с входом триггера м.чадшего разряда регистра 1.

Выходы триггеров регистра 1 соединены с входами триггеров регистра 2, выходы которого связаны с входами триггеров регистра 3 и счетчика адреса 6. Выходы триггеров регистра 3 подключены к входу блока памяти 4, выход которого связан с входами триггеров регистра 3. Выходы счетчика адреса б управляют работой дешифратора адреса 5, вход которого подключен к входу блока намяти 4.

Преобразователь 8 соединен с входом регистра 3 и с входом делителя частоты 7. Первый и второй выходы делителя подключены соответственно к счетным входам триггеров регистра 2 и счетчика адреса 3.

Рассмотрим работу устройства при реализации алгоритма БПФ. С целью исключения затрат времени на перестановку коэффициентов Фурье после их вычисления в устройство проводится соответствуюш.ая перестановка отсчетов преобразуемой функции при записи этих отсчетов в блок памяти. Если порядковый номер j-ro отсчета функции представлен в виде двоичного кода.

Qi g, §2, , gn,

где , 2, ... п - номер двоичного разряда арифметического устройства;

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

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

В исходном положении все регистры установлены в нулевое состояние. Работа системы рассматривается при одновременной обработке двух процессов А и В (входы 11, 12 устройства). При этом отсчеты функций следуют нопарно.

Пумерация отсчетов функций Л и S и адреса ячеек, в которые заносятся значения этих отсчетов, приведены в таблице 1.

Таблица 1

С помощью преобразователя 8 значение отсчета функции А преобразуется в двоичный код и пересылается в регистр 3. Предварительно на делитель частоты 7 поступает импульс, который готовит логические схемы делителя для прохождения следующего импульса на второй выход. Так как ко времени поступления кода из преобразователя 8 регистр 3 и счетчик адреса 6 находятся в нулевом состоянии, то код регистра 3, соответствующий нулевому отсчету функции А, заносится в блок памяти 4 по нулевому адресу.

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

ьход младшего разряда счетчика б поступает импульс, который заносит в счетчик код едиНИНЫ. Код регистра 3, поступивший из преобразователя 8, заносится в блок памяти 4 по первому адресу.

Согласно алгоритму БПФ второй отсчет функции А заносится в адрес, определяемый инвертированным относительно среднего разряда регистра 2 значением порядкового номера отсчета. Перед началом отсчета и преобразования кода через делитель частоты 7 на счетный вход триггера младшего разряда регистра 2 поступает импульс, который заносит в регистр код единицы. После чего значение кода регистра 2 пересылается в регистр 1.

Во время этой пересылки код §2, - gn преобразуется в код вида QI gn, gn-i, ... gi, т. e. проводится инвертирование кода относительно среднего разряда регистра.

Следующим тактом код Qi gn, gn-i,.-g пересылается в регистр 2 с последующей пересылкой его в счетчик адреса 6.

Поступивщий из преобразователя 8 код заносится в блок 4 по адресу 1000 (см. табл. 1).

Следующий преобразованный код заносится в блок 4 по адресу 1001, так как импульс, соответствующий четвертому преобразованию, через делитель частоты 7 поступает на счетный вход триггера младшего разряда счетчика адреса 6. С целью восстановления истинного значения номера отсчета код 1000, хранящийся в регистре 2 за период времени преобразования и засылки в блок 4 очередного кода, пересылается из регистра 2 в регистр 1

и преобразуется из кода Ql gn, gn-i, ...gi в код Qi g,g2,...gn, т. e. в регистре 2 хранится код 0001.

Дальнейшие отсчеты преобразования кодов и расстановка их в блоке памяти 4 приводятся аналогично.

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

Число разрядов регистров может быть любым.

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

2 сумматора, при этом gi (см. фиг. 2), 1,2,3,...

Оператор при фиксированной разрядности выбирает необходимое число отсчетов исследуемой функции. Различным числам отсчетов 29 512, 1024, 2048 и т. д. соответствует отдельная щина, подключаемая ко входу 10. По выбранной щине поступает управляющий сигнал, который через соответствующую схему «И пропускает импульс, поступающий с делителя частоты на счетный вход триггера соответствующего разряда. В дальнейшем устройство работает аналогично рассмотренному выше.

.

Предмет изобретения

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

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

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

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