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

 

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

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (sl)s G 06 F 15/332

ГОСУДАРСТВЕННЫЙ КОМИТЕТ

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4773174/24 (22) 23.10.89 (46) 07.12.91. Бюл. М 45 (72) А.С.Дыкун, Ю.М.Захарко и А.А.Мельник (53) 681.3(088.8) (56) Авторское свидетельство СССР

NÜ 1277135, кл. G 06 F 15/332, 1986.

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

М 1265794, кл. G 06 F 15/332, 1986. (54) УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ БЫСТРОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ (57) Изобретение относится к вычислительной технике и может быть исиользовано для

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

Цель изобретения — расширение области применения за счет обеспечения возможности изменения размерности преобразования.

На фиг.1 приведена функциональная схема устройства; на фиг.2 приведена временная диаграмма приема и продвижения информации в процессе обработки по устройству.

Устройство содержит и вычислительных блоков 1> — 1>, где и = logzN, N — максимальная размерность преобразования, блок 2 синхронизации, тактовый вход 3, вход 4 сброса, регистры 5-7, умножители 8 памяти

9 коэффициентов, элемент HE 10, 0-триггер

„„ 0„„ 1697086 А 1 построения цифровых фильтров и анализаторов спектра, работающих в реальном масштабе времени. Цель изобретения— расширение области применения за счет обеспечения возможности изменения размерности преобразования.

Устройство для этого содержит п вычислительных блоков(п = logzN, N — максимальная размерность преобразования), блок синхронизации и счетчик, при этом каждый вычислительный блок содержит умножитель, два арифметических узла, два узла задержки, два мультиплексора, коммутатор. память коэффициентов и память коэффициентов кодов операций. 2 ил.

11, арифметические узлы 12, 13 памяти 14 кодов операций, первый элемент И 15, второй элемент И 16, элементы 17, 18 задержки, мультиплексоры 19, 20, коммутаторы 21, счетчик 22, второй информационный выход

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

Количество регистров в стеке равно количеству тактов задержки, т,е. определяется номером блока.

Устройство работает следующим образом. При поступлении на вход 4 устройства импульса начала обработки триггер 11 и счетчик 22 адреса устанавливаются в нулевое состояние. Следующим тактовым импульсом, поступающим на вход 3 устройства, триггер 11 устанавливается в l697086

55 единичное состояние. Одновременно с тактовым импульсом на входы регистров 5 и 6 поступает первое информационное слово.

По заднему фронту тактового импульса на выходе элемента И 15 формируется импульс, по которому на регистр 5 принимается первое информационное слово, а на счетчике 22 устанавливается первый адрес, По второму тактовому импульсу триггер 11 переключается в нулевое состояние. По заднему фронту тактового импульса на выходе элемента И 16 формируется импульс, записывающий в регистр 6 второе информационное слово. В следующем такте информационное слово с регистра 5 переписывается в регистр 7, с регистра 6 записывается в (комплексный) умножитель 8, а в регистр 5 принимается следующее информационное слово. Одновременно на умножитель 8 с памяти коэффициентов 9 принимается значение соответствующего тригонометрического коэффициента.

Адресное пространство памяти 9 коэффициентов и памяти 14 кодов операций состоит из младшей и средней частей.

Младшая часть управляется с выхода счетчика (адреса) 22. старшая часть указывает величину размера обрабатываемого массива и задается с входа 2 устройства, Максимальный размер обрабатываемого массива определяется выражением N =- 2", где n— количество блоков или этапов выполнения быстрого предбразования Фурье (БПФ).

Тогда количество разрядов старшей части равно целой большей части от logzN. Количество разрядов младшей части адресного пространства определяется выражением

1092 2 за счет распараллеливания входN ной информации на два канала.

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

В следующем такте с регистра 7 и умножителя 8 информационные слова принимаются на арифметические узлы 12 и 13, С выхода арифметического узла 12 значение

A+W В поступает на элемент 17 задержки, а с выхода устройства 13 значение А-W В.

k поступает на коммутатор 21, Мультиплексоры 19 и 20 принимают информацию или с элементов 17 и 18 задержки сортветственно или с арифметического узла

12 и коммутатора 21 соответственно, Управ20

40 ление мультиплексорами осуществляется с памяти 14, Коммутатор 21 выполняет стандартную для потолочного процессора БПФ операцию "прямо-накрест".

Сущность настройки устройства на обработку массива разных размерностей состоит в следующем. В зависимости от кода операции, поступающего на соответствующий вход устройства и указывающего на размерность преобразования памяти 9 и памяти 14 в зависимости от кода адреса, поступающего со счетчика 22, формируется соответствующее размерности значение тригонометрических коэффициентов и управляющих сигналов. При этом, если размерность преобразования меньше, в обработке задействованы не все блоки, Блоки, не задействованные в обработке, но через которые проходит информация, работают следующим образом. На (комплексный) умножитель 8 с выхода памяти 9 коэффициентов поступает значение коэффициента, равное "1", т.е. умножитель выполняет умножение на "1". На арифметические устройства с первого и второго выходов памяти 14 поступает код операции, указывающий на пропуск информации: для арифметического узла

12 — пропуск на выход информации, поступающей на второй вход, для арифметического узла 13 — пропуск на выход информации, поступающей на первый вход, На мультиплексор 19 с памяти 14 поступает управляющий сигнал, по которому он пропускает на выход информацию с арифметического узла 12, минуя элемент 17 задержки, Коммутатор 21 по сигналу от памяти 14 осуществляет передачу информации прямо.

Мультиплексор 20 передает информацию с первого выхода коммутатора 21, минуя элемент 18 задержки.

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

Устройство для вычисления быстрого преобразования Фурье, содержащее и вычислительных блоков (и = logzN, N — максимальнаяя размерность преобразования). блок синхронизации, счетчик и-первый регистр, причем первый информационный вход k-го вычислительного блока (k = 2,n) соединен с первым информационным выхо-. дом (k- 1)-го вычислительного блока, второй информационный выход которого соединен с вторым информационным входом kro вычислительного блока, первый и второй информационные выходы и-го вычислительного блока являются соответственно первым и вторым информационными выходами устройства, первый выход блока

1697086

ЗО

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

1697086

1697086 аюа Л.

Впрах

ЬаТ

П 7ЯФа4Г

Auod 7 /1 хааа мою 10

ЯЬдаа" луч 1J

Аааа зим 1б

Heave

Рг5 й/1 аа

Ргб

Пряж наРг7 фЮГФ

Ю Egg

Прием ь АУ/Г

Прядем нп бб17

Составитель l0,Ланцов

Редактор Б.Федотов Техред М,Моргентал Корректор Т.Палий

Заказ 4307 Тираж Подписное

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

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

Производственно-издательский комбинат "Патент", г. ужгород, ул. Гагарина, 101