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

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

Иллюстрации

Показать все

Реферат

 

00 480079

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ

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

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

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

Республик (61) Дополнительное к авт. свид-ву (22) Заявлено 12.07.73 (21) 1949804/18-24 с присоединением заявки № (23) Приоритет

Опубликовано 05.08.75. Бюллетень № 29

Дата опубликования описания 11.03.76 (51) М. Кл. G 061 15/34

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

Совета. Министров СССР ко делам изобретении и открытий (53) УДК 681.326.3 (088.8) (72) Авторы изобретения

Г. В. Беляев, Б. М. Власов и Л. М. Баскин (71) Заявитель (54) УСТРОЙСТВО ДЛЯ РЕАЛИЗАЦИИ АЛГОРИТМА

БЫСТРОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ

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

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

Фурье (БПФ).

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

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

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

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

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

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

15 па м яти.

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

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

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

Варианты схемы устройства показаны на фиг. 1 и 2, где обозначены: регистр 1 (регистр

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

480079

Таблица 1

Код порядково номера отсчета

Код адреса для функции А

Номер адреса

Код адреса для функции В

Номер адреса №№ пп

1110

0001

0011

0101

0111

8

12

10 б

0001

1001

0101

1101

0011

1011

0111

1111

9

13

11

15

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

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

Выходы триггеров регистра 1 соединены с входами триггеров регистра 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 и на счетный тов Фурье после их вычисления в устройств проводится соответствующая перестановка отсчетов преобразуемой функции при записи этих отсчетов в блок памяти. Если порядковый номер i-го отсчета функции представлен в виде двоичного кода.

Qt È Й2 Ил где i 1, 2, ... п — номер двоичного разряда арифметического устройства; и — разрядность арифметического устройства, то для исключения последующей перегруппировки коэффициентов необходимо занести в блок памяти значение отсчета функции по адресу

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

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

Нумерация отсчетов функций А и В и адреса ячеек, в которые заносятся значения этих отсчетов, приведены в таблице 1. ьход младшего разряда счетчика 6 поступает импульс, который заносит в счетчик код единицы. Код регистра 3, поступивший из преобразователя 8, заносится в блок памяти 4 ..ю первому адресу.

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

Во время этой пересылки код Q;=gl, g,, ... g„

I преобразуется в код вида Qi =g, g — ь " ь т. е. проводится инвертирование кода относительно среднего разряда регистра.

Г

Следующим тактом код Q< =g, g ь ... g пересылается в регистр 2 с последующей пересылкой его в счетчик адреса 6.

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

Следующий преобразованный код заносится в блок 4 по адресу 1001, так как импульс, соответствующий четвертому преобразованию, через делитель частоты 7 поступает на счетный вход триггера младшего разряда счетчика адреса 6. С целью восстановления истинного значения номера отсчета код 1000, хранящийся в регистре 2 за период времени преобразования и засылки в блок 4 очередного кода, пересылается из регистра 2 в регистр 1 и преобразуется из кода Qi =g„, g„ >,... gl в код Q;=g), g>,... g, т. е. в регистре 2 хранится код 0001.

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

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

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

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

480079

2 сумматора, при этом g; =n+1 — q (см. фиг. 2), q= 1, 2, 3, ...

Оператор при фиксированной разрядности выбирает необходимое число отсчетов иссле5 дуемой функции. Различным числам отсчетов

2 =512, 1024, 2048 и т. д. соответствует отдельная шина, подключаемая ко входу 10. По выбранной шине поступает управляющий сигнал, который через соответствующую схему

10 «И» пропускает импульс, поступающий с делителя частоты на счетный вход триггера соответствующего разряда. В дальнейшем устройство работает аналогично рассмотренному выше.

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

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

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

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

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

480079

Составитель А. Жеренов

Редактор Л. Утехина Техред М. Семенов Корректор Т. Фисенко

Заказ 122713 Изд. № 934 Тираж 679 Подписное

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

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

Типография, пр. Сапунова, 2