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

 

ОПИСАНИЕ

;.ИЗОБРЕТЕНИЯ

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

«ii866561

СОюЭ СОВ4тСких

Сфцнапистнчеавик

Р4спублмк (б3) Дополнительное к авт. свид-ву (22) ЗаявЛено 131279 (21) 2855490/18-24 с присоединением заявки ¹

М (з

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

С.ССР но делан нзо4ретеннЯ и открытн В

G Об F 15/332 (23) Приоритет

Опубликовано 230%81. Бюллетень No 35

Дата опубликования описания 23, 09. 81 (53) УДК 681. 3 (088.8) f

Н.Н.Немшилов и М.А.Титов

1;,. с

Военная ордена Ленина Краснознаменная академия связи им. С.М.Буденного (72) Авторы изобретения (73) Заявитель, (54 ) УСТРОЙСТВО ДЛЯ БЫСТРОГО

ПРЕОБРА, фЭВАНИЯ ФУРЬЕ

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

Известно устройство для выполне ния БПФ, содержащее коммутатор, счетчик циклов, счетчик шагов, арифметико — логическое устройство, блок памяти (Ц .

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

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

Недостатком. известного устройства является низкое быстродействие, Поскольку в нем используется сугубо последовательный принцип обработки операндов °

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

Поставленная цель достигается тем, что устройство для быстрого преобразования Фурье содержащее арифметический блок, блок памяти коэффициентов и N — разрядный регистр отсчетов, содержит R регистров сдвига по f разрядов (R м tt = N) и дополнительно (R/2)-1 арифметических блоков, причем выход i - ro разряда j — го регистра сдвига (i = 1 - т,, 1 = 1 — R) подклю.чен ко входу i + (j — 1) 3 - го разряда регистра отсчетов, выходы (2m—

Ц - ro и 2m - ro (m = 1 - R/2) разрядов регистра отсчетов, являющиеся выходами устройства, а также m — - ый выход блока памяти коэффициентов подключены ко входам m — го арифметического блока, первый и второй выходы которого подключены ко входу  — го разряда (2m - 1 ) - ro и 2m - го регистров сдвига соответственно.

На фиг.1 представлена функциональная. схема предлагаемого. Устройстват на фиг.2 - график реализуемого алгоритма БПФ для случая N - =32, R = --4, М = 8 °

Устройство содержит арифметические блоки 1 и 2, регистр отсчетов, обра30 . эованный группами разрядов 3 - 6., 866561 соответствующими регистрам сдвига

3 - 6 и дополнительной группой разрядов 7, блок памяти коэффициентов 8.

Предполагается, что числа N, R, Х являются целой степенью основания алгоритма БПФ.

В качестве арифметического модуля

;может быть использовано .любое устройство, способное выполнять операции

А +wB над комплексными числами. Для одновременной передачи кодов во все

R/2 арифметические блоки можно Йспользовать выходы первых R разрядов регистра отсчетов, либо в соответствии с фиг.1, 1-ый разряд (6. ) и R l дополнительных разрядов 7 регистра отсчетов. Соединение выходов арифметических блоков со входами регистров сдвига 3 — 6 < соответствует графу алгоритма БПФ (фиг.2).

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

Исходные данные в виде N отсчетов исследуемого сигнала записываются в

N разрядов 3 — 6 регистра отсчетов.

Цепи записи на фиг.1 не показаны, хотя для этой цели могут быть исполь- щ5 зованы входы а, b, с, d регистров сдвига 3 — 6 .

Для реализации алгоритма БПФ осуществляются 1а " N итераций (график на фиг.2 соответствует одной итерации). Данные на .входы арифметических блоков поступают группами (по R чисел в группе). Такие группы (фиг.2) образованы отсчетами с номерами 1, 2, 3, 4; с номерами 5, 6, 7, 8 и т.д.

После ввода всего массива исходных данных первая группа данных с выходов первых R разрядов (из группы 6 ) реМ гистра отсчетов (если не используются дополнительные разряды 7) поступает на входы арифметических блоков 1 и 2. 4О

Из памяти коэффициентов 8 в блоки 1 и

2 подаются соответствующие номеру

Группы данных и номеру итерации значения весовых коэффициентов, получаемые путем необходимого циклического сдвига всего массива коэффициентов.

За время выполнения преобразований над отсчетами первой группы, содержимое регистра отсчетов сдвигается вправо íà R разрядов так,.чтобы вторая группа отсчетов заняла место первой.

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

:в регистры сдвига 3 - 6 по входам а, Ь, с, d, после чего содержимбе регистров сдвига сдвигается на один разряд вправо. Одновременно в арифметические блоки 1 и 2 передается вторая группа данных и описанный процесс повторяется N/R раз, в результате чего очередная итерация алгоритма БПФ выполнена. Данные иэ регистров сдвига передаются параллельным кодом в регистр отсчетов, и устройство переходит к выполнению очередной итерации.

По окончании последней итерации результат преобразования по группам выдается на.выход устройства, одно-, временно входные данные могут поступать на входы а, b с, d.

Уменьшение времени преобразований в предлагаемом устройстве достигается благодаря испольЭованию групповой обработки данных.

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

Устройство для быстрого преобразования Фурье, содержащее арифметический блок, блок памяти коэффициентов и N — - разрядный регистр отсчетов, о тл и ч а ю щ е е с я тем, что, с целью повышения быстродействия, оно содержит R регистров сдвига по р разрядов (R > E = N) и дополнительно (R/2) — 1 арифметических блоков, причем выход

i - го разряда j — го регистра сдвига (i = 1 — E, j = 1 — R) подключен ко входу i +(j - 1) g, — го разряда регистра отсчетов, выход»; (2m — 1) — го и 2m — ro (m = 1 — R/2) разрядов регистра отсчетов, являющиеся выходами устройства, а также m - ый выход блока памяти коэффициентов подключены ко входам m — го арифметического блока, первый и второй выходы которого подключены ко входу  — го разряда (2m - 1)-го и 2m — ro регистров сдвига соответственно.

Источники информации, принятые во внимание при экспертизе 1. Авторское свидетельство СССР

Р 590750., кл. G Об F 15/34, 1975.

2. Авторское свидетельство СССР ю 615488, кл. G 06 F 15/34, 1976 (прототип).