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

 

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

Социалистических респубпнн

ОП ИСАНИЕ

И ЗОВРЕТЕ Н ИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ ()896631 (61) Дополнительное к авт. саид-ву (22) Заивлено 21.04.80 (21) 2913447/18.24 с присоединением заявки РЙ (23) Приоритет (53)M; Кл.

G 06 F 15/332

Гееудярстееееий кеинтет

СССР ае девам изебретенкй я етерьпяй

Опубликовано 07.01.82. Бюллетень Ж 1

Дата опубликования описания 07.01.82 (53 ) УДК 681;3 (088.8) (72) Авторы изобретения

Л, Г. Коваленко, Г. А. Кухарев, О. С. Романов

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

ПОСЛЕДОВАТЕЛЬНОСТИ С НУЛЕВЫМИ ЭЛЕМЕНТАМИ т1зобретение относится к вычислительной технике и может быть использовано для выполнения быстрого преобразования Фурье.

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

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

Кроме того, в этих устройствах ненулевая часть элементов должна быть расположена в начальной части исходной последовательности.

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

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

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

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

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

4 перестановок. Далее распределительный блок

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

Каждый переупорядоченный элемент из блока 1 записывается в помощью распределительного блока 3 в массив ячеек блока 4 памяти результатов. Адреса ячеек памяти определяются содержимым счетчика 10, разрядность которого соответствует длине входной последовательности Й, на счетный вход которого поступают тактовые сигналы записи. С помощью дещифратора 11 на выход распределительного блока 3 передаются ненулевые отсчеты и производится дополнение входной последовательности нулевыми отсчетами. 8 отличие от известного устройства, в котором распределение ненулевых отсчетов в блок 4 о памяти результатов производится по сложной адресации ячеек, начиная с первого элемента с периодом, равным минимальной степени двух не превосходящих число ненулевых элементов, запись в массив ячеек производится последовательно сначала первого элемента, 25 затем — второго и тд. до последнего ненулевого элемента. Это позволяет сократить время на переадресацию ячеек памяти и упростить конструкцию распределительного блока 3.

Арифметический блок 5 выполняет стандартзо ные арифметические операции сложения и умножения- над элементами исходной последовательности,. хранящимися в блоке 4 памяти результатов и значениями тригонометрических коэффициентов, взятых из блока 8 памяти тригонометрических коэффициентов. После завершения вычислений полученные коэффициенты Фурье поступают в блок 9 умножения, на второй вход которого подаются значения тригонометрических коэффициентов иэ

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

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

Кроме того, распределительный блок содержит счетчик, дешифратор, матрицу элементов

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

ИЛИ группы соединены с соответствующими разрядами информационного выхода блока.

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

Устройство. содержит входной блок 1 памяти, блок 2 синхронизации, распределительный блок 3, блок 4 памяти результатов, арифмети ческий блок 5, содержащий сумматор 6 и умножитель 7, блок 8 памяти коэффициентов . и блок 9 умножения.

Распределительный блок 3 содержит счетчик

10, дешифратор 11, матрицу 12 элементов И, группу 13 элементов ИЛИ.

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

М ненулевых элементов последовательности, от которой вычисляется преобразование Фурье, 5О поступают во входной блок 1 памяти и затем переупорядочиваются в отличие от извест ного устройства, в котором переупорядочиванию подвергается целиком весь массив из N отсчетов. Следовательно, при М (4 M в устрой- 55 стве затрачивается гораздо меньше времени на формирование адресов инверсных перестановок и обмен данных при выполнении этих

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

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

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

896631

2. Устройство по п. 1, от лича ющ е е с я тем, что распределительный блок содержит счетчик, дешифратор, матрицу элементов И, группу элементов ИЛИ, причем

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

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

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

26

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

1.Патент США й4 3920978кл.235-156, 1975.

2.Патент США М 4138730,кл.364-726, 1979.

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

896631

Составитель В. Аедоницкий

Техред АСавка Корректор Г. Решетник

Редактор Е. Дичинская

Подписное

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

Заказ 11707/38 Тираж 731

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

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