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

О П И С А Н И Е (11) 480079ИЗОБРЕТЕНИЯК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ Союз Советских Социалистических Республик(088.8) ко лелем изобретен и открытий(72) Авторы изобретения Власов и Г, В, Беляев,аски(71) Заявител СТРОЙСТВО ДЛЯ РЕАЛИЗАЦИИ АЛГОРИТМАБЫСТРОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ(54) 2 Изобретение относится к области цифровой вычислительной техники и может быть использовано в составе автоматизированного комплекса обработки данных экспериментальных исследований.Известны цифровые вычислительные устройства, используемые для обработки данных экспериментальных исследований, реализуюцего алгоритм быстрого преобразования Фурье (БПФ).Известны два направления реализации БПФ:реализация БПФ в цифровых вычислительных системах на основе ЦВМ широкого назначения;реализация БПФ в системах обработки данных на основе специализированных цифровых вычислительных машин (СЦВМ).Использование ЦВМ широкого назначения в отдельных случаях не обеспечивает высокой производительности в связи с наличием специфических особенностей алгоритма БПФ, Так, например, в ходе вычисления коэффициентов Фурье необходимо выполнять сложную перегруппировку адресов ЗУ. Необходимая перегруппировка проводится по простейшей программе, тем не менее ее весьма трудно запрограммировать для ЦВМ широкого назначения, на выполнение этой программы тратится почти половина машинного времени,необходимого для реализации всего алгоритма.Реализация БПФ на основе СЦВМ обеспечивает сокращение времени вычисления ко 5 эффициентов, но для решения других задачэти устройства применять невозможно.Известны также устройства для обработкиинформации, в которых производительностьповышается за счет увеличения числа ариф 10 метнческих блоков (например, до четырех) иприняты меры по повышению быстродействия при выполнении суммирования чисел исокращению времени обмена информациеймежду арифметическим блоком и блоками15 памяти,Целью изобретения является повышениебыстродействия устройства.Эта цель достигается путем схемного выпол.нения процедуры адресации ячеек блока па 20 мяти,Для этого в устройство введен делительчастоты, вход которого соединен со вторымвыходом преобразователя напряжения в код,первый и второй выходы подключены соответ 25 ственно к управляющему входу арифметического блока и к счетному входу счетчика адреса. Варианты схемы устройства показаны нафиг. 1 и 2, где обозначены: регистр 1 (регистр 30 множителя) АУ, обеспечивающий сдвиг кода480079 Таблица 1 Код порядково номераотсчета Код адреса для функции АНомер адреса Код адреса для функции ВНомер адреса ЯМо пп 0000 1000 0100 1100 0010 1010 0110 1110 0000 0001 00100011 0100 0101 0110 0111 0 8 4 12 2 10 б 14 0001 1001 0101 1101 0011 1011 0111 1111 1 9 5 13 3 11 7 15 35 40 45 влево (вправо); регистр и суммирующие схемы 2 (регистр суммы); регистр 3 первого слагаемого (множимого), блок памяти 4; дешифратор адреса 5; счетчик адреса 6; делитель частоты 7; преобразователь напряжения в код 8, арифметический блок 9, входы 10 - 12 устройства и схемы И 13 - 15 (узлы управления, синхронизации и регистрации данных на чертежах не показаны).Выход триггера младшего разряда регистра 2 соединен с входом триггера старшего разряда регистра 1, выход триггера старшего разряда регистра 2 - с входом триггера младшего разряда регистра 1.Выходы триггеров регистра 1 соединены с 15 входами триггеров регистра 2, выходы которого связаны с входами триггеров регистра 3 и счетчика адреса 6. Выходы триггеров регистра 3 подключены к входу блока памяти 4, выход которого связан с входами триггеров 20 регистра 3. Выходы счетчика адреса 6 управляют работой дешифратора адреса 5, вход которого подключен к входу блока памяти 4.Преобразователь 8 соединен с входом регистра 3 и с входом делителя частоты 7. Первый 25 и второй выходы делителя подключены соответственно к счетным входам триггеров регистра 2 и счетчика адреса 3.Рассмотрим работу устройства при реализации алгоритма БПФ. С целью исключения 30 затрат времени на перестановку коэффициенС помощью преобразователя 8 значение отсчета функции А преобразуется в двоичный код и пересылается в регистр 3. Предварительно на делитель частоты 7 поступает импульс, который готовит логические схемы делителя для прохождения следующего импульса на второй выход. Так как ко времени поступления кода из преобразователя 8 регистр 3 и счетчик адреса 6 находятся в нулевом состоянии, то код регистра 3, соответствующий нулевому отсчету функции А, заносится в блок памяти 4 по нулевому адресу.Затем проводятся отсчет и преобразование значения функции В. До выдачи кода в регистр 3 на делитель частоты 7 и на счетный тов Фурье после их вычисления в устройств проводится соответствующая перестановка отсчетов преобразуемой функции при записи этих отсчетов в блок памяти. Если порядковый номер 1-го отсчета функции представлен в виде двоичного кода.0= й йа Д где 1= 1, 2,п - номер двоичного разряда арифметического устройства;и - разрядность арифметического устройства, то для исключения последующей перегруппировки коэффициентов необходимо занести в блок памяти значение отсчета функции по адресу Указанное преобразование проводится за счет схемных соединений отдельных узлов, что исключает программирование указанной операции и повышает быстродействие вычисления коэффициентов Фурье.В исходном положении все регистры установлены в нулевое состояние. Работа системы рассматривается при одновременной обработке двух процессов А и В (входы 11, 12 устройства). При этом отсчеты функций следуют попарно,Нумерация отсчетов функций А и В и адреса ячеек, в которые заносятся значения этих отсчетов, приведены в таблице 1. ьход младшего разряда счетчика 6 поступает импульс, который заносит в счетчик код единицы. Код регистра 3, поступивший из преобразователя 8, заносится в блок памяти 4 по первому адресу.Согласно алгоритму БПФ второй отсчет функции А заносится в адрес, определяемый инвертированным относительно среднего разряда регистра 2 значением порядкового номера отсчета, Перед началом отсчета и преобразования кода через делитель частоты 7 на счетный вход триггера младшего разряда регистра 2 поступает импульс, который заносит в регистр код единицы. После чего значение кода регистра 2 пересылается в регистр 1.5Во время этой пересылки код Я;=К й,КРпреобразуется в код вида Я =д д - ь " К т. е. проводится инвертирование кода относительно среднего разряда регистра.Следующим тактом код Яг =д. Ь -" д пересылается в регистр 2 с последующей пересылкой его в счетчик адреса 6.Поступивший из преобразователя 8 код заносится в блок 4 по адресу 1000 (см. табл. 1).Следующий преобразованный код заносится в блок 4 по адресу 1001, так как импульс, соответствующий четвертому преобразованию, через делитель частоты 7 поступает на счетный вход триггера младшего разряда счетчика адреса 6, С целью восстановления истинного значения номера отсчета код 1000, хранящийся в регистре 2 за период времени преобразования и засылки в блок 4 очередного кода, пересылается из регистра 2 в регистр 1 и преобразуется из кода Я =К. а в" й в код Я;=д Дь д, т. е, в регистре 2 хранится код 0001.Дальнейшие отсчеты преобразования кодов и расстановка их в блоке памяти 4 приводятся аналогично.Для примера был рассмотрен вариант устройства, содержащего четыре разряда.Число разрядов регистров может быть любым,Для оперативного изменения числа отчетов функции в ходе обработки данных в устройстве первый выход делителя частоты может быть подключен к входам схем И, вторые входы которых подключены к органам управления пульта оператора, а выходы - к счетным входам триггеров дух разрядов регистра 480079 2 сумматора, при этом д;=юг+1 - д (см.фиг.2),д= 1,2,3,Оператор при фиксированной разрядностивыбирает необходимое число отсчетов иссле дуемой функции. Различным числам отсчетов2=512, 1024, 2048 и т. д. соответствует отдельная шина, подключаемая ко входу 10. По выбранной шине поступает управляющий сигнал, который через соответствующую схему 10 И пропускает импульс, поступающий с делителя частоты на счетный вход триггера соответствующего разряда. В дальнейшем устройство работает аналогично рассмотренному выше.15Предмет изобретенияУстройство для реализации алгоритма быстрого преобразования Фурье, содержащее блок памяти, счетчик адреса, дешифратор ад реса, арифметический блок, первый выход которого через счетчик адреса и дешифратор адреса подключен ко входу блока памяти, информационный вход которого соединен со вторым выходом арифметического блока, первый 25 информационный вход которого подключен квыходу блока памяти, преобразователь напря.кения в код, входы которого подключены к соответствующим входам устройства, первый выход соединен со вторым информационным 30 входом арифметического блока, о т л и ч а ющ е е с я тем, что, с целью повышения быстродействия, в него введен делитель частоты, вход которого соединен со вторым выходом преобразователя напряжения в код, первый и 35 второй выходы подключены соответственно куправляющему входу арифметического блока и к счетному входу счетчика адреса.480079 Составитель А. Жерено Редакт Утехи ехред М. Семенов Корректор Т. Фисенк Заказ 122713ЦНИИП Изд.934 Государственного по делам из 113035, Москва, Ж