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

 

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ

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

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

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

Республик

<о744598 (6) ) Дополнительное к авт. свид-ву (51)М. Кл.2 (22) Заявлено 05.12.77 (21) 2550924/18-24 с присоединением заявки ¹

G 06 F 15/34

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

СССР но делам изобретений и открытий (23) Приоритет

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

Дата опубликования описания 300680 (53) УДК 681. 3 (088 .8) (72) Авторы изобретения

Л.И. Сулин, Н.Н. Немшилов, К.П. Бочаров и В.N. Сергеев (71) Заявитель

{ 54) УСТРОЙСТВО ДЛЯ БЫСТРОГО ПРЕОБРАЗОВАНИЯ

ФУРЬЕ

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

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

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

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

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

Недостатком устройства является то, что после каждого цикла вычислений

15 ре зульт ат н ак аплив ае тс я в этой же строке. Это обусловлено тем, что номера строк ассоциативной памяти,в которые записываются результаты очередной итерации, каждай раэ различны.

20 Поэтому пересылки операндов осуществляются с помощью коммутирующей матрицы, соединяющей шину связи с шиной разрешения записи соответствующих строк накопителя.

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

30 о- > оК N

744598

45

65

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

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

Поставленная цель достигается тем, что в устройство, содержащее первый .и второй регистры, регистр маски, памяти коэффициентов, матрицу ассоциативной памяти, состоящую из Ч/2. . строк (где N — - количество точек в .исходной последовательности отсчетов), каждая из которых состоит иэ десяти ячеек, соединенных своими установочными входами через регистр маски с выходами первого регистра„ а выходами - со входами второго регистра,, входы пятой и шестой ячеек соединены с соответствующим номеру строки выходом памяти коэффициентов, первый и второй коммутаторы, дополнительно введены третий и четвертый коммутаторы, при этом вход первого коммутатора соединен с выходами первой, третьей, пятой, шестой, седьмой и десятой ячеек каждой строки, а выход — со входами седьмой, девятой ячеек каждой строки и с первым выходом разрешения записи строки матрицы ассоциативной памяти, вход второго коммутатора соединен. с выходами второй, четвертой, пятой, шестой, восьмой и девятой ячеек каждой строки, а выход — со входами восьмой и десятой ячеек и вторым выходом разрешения записи строки матрицы ассоциативной памяти, вход третьего коммутатора соединен с выходами восьмой и девятой ячеек каждой строки,«а выход — с третьим выходом разрешения записи строки матрицы ассоциативной памяти, вход четвертого коммутатора соединен с выходами седьмой и десятой ячеек каждой строки, а выход - с чет чертым выходом разрешения записи строки ассоциативной памяти, входы первой, второй, третьей, чет.вертой ячеек каждой строки соединены с соответствующими входами строки матрицы ассоциативной памяти.

Математические действия, выполняемые по каждому двухточечному преобразованию.

Обозначим: л/к=а + g а соэХЖк 8; 2Жк где пары входных выборок, причем р=1+

Значения выходных выборок -, и

В ть вычисляются дледукщим образом

z<= 2;+g (a„+jb„ )=x,.+)у; (y. +jy )(а +jb ).

?щ=,+2„(а„-)ЬЬ„ =х,+р.+(к+ у )(а - Ь )

Объединяя мнимые и действитель ные части, получаем

-b у ф)(у.+а J +ь х =х + }у р 1<р 1 ИР 1с P Я4 6 р Z -v..ie„y, +Ь у +j(v;+ ур-Ь х =х )ум

Значения г и гщ пересылаются на входы для выполненйя над ними очередных итераций.

На чертеже представлена схема

15 устройства.

Устройство содержит матрицу ассоциатив ной ncLMHTH состоящую из одйнаковых строк 1, коммутаторы 2 (Ис„-Hc„) память 3 коэффициентов, щ регистр 4 маски, первый регистр 5, второй регистр б, Устройство работает следующим образом, Каждая строка 1 (ячейка памяти АПП) разделена на 10 ячеек: в первой ячейке хранится значение х1, во второй у>, в третьей хр, в четвертой — у в пятой - а„, в шестой-в, седьмая, восьмая, девятая и десятая ячейки резервируются для промежуточных реЗо зультатов вычислений.

В каждой итерации информация всех строк обновляется. Значения 2 и 2р

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

35коэффициенты ак и b

В каждой итерации вычисления выполяются в следующем порядке.

1-й этап. Одновременные умножения: (а„) ° (х р) 7 ячейк а (а„) (у„) 8 ячейка

2-й этап. Одновременные сложения: (р„ )+(х;)-ъ 9 ячейка (p2 )+ (у, ) - 10 ячейка

3-й этап. Одновременные умножения (b„) ° (х ) -+ 7 ячейка (bÄ) - (у„) - 8 ячейка

После выполнения первых трех этапов получаются промежуточные результаты, которые размещены в ячейках

50 7 - 10 тех же строк, где хранятся ! исходные величины. Соответствующие пересылки промежуточных результатов вычислений осуществляются с помощью первого и второго коммутаторов.

После завершения размещения промежуточных результатов. вычислений в ячейках 7 - 10, выполняются еще два этапа:

О 4-й этап. Одновременные сложения

7 ячейка + 10 ячейка у (UC )

8 ячейка + 9 ячейка х (UC )

5-й этап. Одновременные вйчитания:

9 ячейка-8 ячейка«х (ПС )

10 ячейка-7 ячейка-у (БС, ) 744598

Результаты операций, произведенных в процессе выполнения 4-го и 5-го этапов, размещаются в зонах у, х,„, хе и у соответствующих строк ассоцйативной памяти. Такое размещение результатов вычислений обеспечивается путем подключения раз решающих запис.ь входбв этих ячеек, соответственно к выходам первого, второго, третьего и четвертого коммутаторов (UC — UC<) .

Одновременно с выполнением 5-го этапа любой из итераций в зоне a„ и Ь„ всех строк 1 вводятся новые значения коэффициентов ч", хранимые в постоянной памяти 3. После окончания 5-го этапа устройство готово к выполнению очередной итерацииа

Коэффициенты Фурье образуются в зонах х и у всех строк после завершения всех &g>N итераций, аналогичных описанной.

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

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

25 тым выходом разрешения записи строки ассоциативной памяти, входы первой, второй, третьей, четвертой ячеек

1 каждой строки соединены с соответствующими входами строки матрицы ассо30 циативной памяти °

Источники информации, принятые ва внимание при экспертизе

1.Tonkin A.> Savage J. An App91cation of Correlation to Pader SysЗ temsL The Radio and Ы.Е. gag .

W 12, W 7, 1972.

2. Прангишвили И.В. Однородные микроэлектроннйе"ассоциативные процес-"" соре, М., Советское радио, 1973 (прототип).

744598

Составитель Н. Шелобанова

Редактор A. Долинич Tezp Л. Теслюк KoppeKTop Г. Назарова.

Заказ 3795/14 Тираж 751,, Подписное

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

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

«»»««» «»

»»» ««»««««««» ««

Филиал ППП Патент ., r. Ужгород, ул. Проектная, 4