Устройство для быстрого преобразования фурье последовательности с нулевыми элементами — SU 896631 (original) (raw)

Союз СоветскихСоциалистическихреспублик ОП ИСАНИЕИЗОБРЕТЕН ИЯК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ(22) Заявлено 21.04.80 (21) 2913447/18-24с присоединением заявки Рй(51)М; Кл. 6 06 Р 15/332 Гееудвретеееие кеинтет С С С.Р ае девам изебретенкй я еткрьпяй(72) Авторы изобретения Л, Г, Коваленко, Г. А. Кухарев, О. С, РомановВ Д Т 4) УСТРОЙСТВО ДЛЯ БЪСТРО ПОСЛЕДОВАТЕЛЬНОСТИ ОБРАЗОВАНЕВЫМИ ЭЛЕМЕНТАМ т 1 зобретение относится к вычислительной технике и может быть использовано для выполнения быстрого преобразования Фурье.Известны устройства для выполнения быст рого преобразования Фурье, содержащие арифметический блок, входной блок памяти, блок памяти, блок памяти тригономе;рических коэффициентов и блок управления 1 и 121.Однако в этих устройствах не используются воэможности для уменьшения времени вычислений при преобразовании последовательностей, содержащих часть нулевых элементов. Кроме того, в этих устройствах ненулевая часть элементов должна быть расположена в начальной части исходной последовательности.Наиболее близким к предлагаемому является устройство для быстрого преобразования Фурье последовательности с нулевыми элементами, содержащее арифметический блок, входной блок памяти, блок памяти, блок умноже. ния, блок памяти тригонометрических коэффициентов и блок инверсной перестановки 13),Недостатком известного устройства является то, что в нем использованы не все возможности для уменьшения времени вычисленийбыстрого преобразования Фурье последователь.ности с нулевыми элементамн, так как под.ключение блока инверсной перестановки квыходу блока памяти в схеме распределитель 5ного блока обуславливают длительное времяид переадресацию и пересылку полной последовательности, содержащей часть нулевых эле.ментов.1 ОЦель изобретения - повышение быстродействия устройства.Поставленная цель достигается тем, что вустройство, содержащее блок умножения, арифметический блок, блок синхронизации, блок 15памяти результатов, блок памяти коэффициен.тов, входной блок памяти, информационныйвход которого является входом устройства,выход блока памяти результатов соединен спервым информационным входом арифметического блока, первый информационный входблока памяти результатов соединен с выхо.дом арифметического блока, второй информационный вход которого подключен к первому выходу блока памяти коэффициентов,8966314перестановок. Далее распределительный блок3 осуществляет продолжение ненулевой частипоследовательности, получаемой на выходеблока инверсной перестановки, на всю последовательность в блок 4 памяти результатов.Каждый переупорядоченный элемент из блока 1 записывается в помощью распределительного блока 3 в массив ячеек блока 4 памяти результатов. Адреса ячеек памяти оп.1 о ределяются содержимым счетчика 10, разрядность которого соответствует длине входнойпоследовательности Й, на счетный вход которого поступают тактовые сигналы записи, Спомощью дешифратора 11 на выход распределительного блока 3 передаются ненулевыеотсчеты и производится дополнение входнойпоследовательности нулевыми отсчетами. Вотличие от известного устройства, в которомраспределение ненулевых отсчетов в блок 4 опамяти результатов производится по сложнойадресации ячеек, начиная с первого элементас периодом, равным минимальной степенидвух не превосходящих число ненулевых элементов, запись в массив ячеек производитсяпоследовательно сначала первого элемента, 25затем - второго и тд. до последнего ненулевого элемента. Это позволяет сократить вре.мя на переадресацию ячеек памяти и упростить конструкцию распределительного блока 3.Арифметический блок 5 выполняет стандартзоные арифметические операции сложения и умножения над элементами исходной последовательности, . хранящимися в блоке 4 памятирезультатов и значениями тригонометрических коэффициентов, взятых из блока 8 памя. З 5 ти тригонометрических коэффициентов. Послезавершения вычислений полученные коэффи.циенты Фурье поступают в блок 9 умножения, на второй вход которого подаются зна.чения тригонометрических коэффициентов из 4 о блока 8, значения которых определяются числом начальных нулевых элементов входнойпоследовательности данных.Предлагаемое устройство позволяет повысить быстродействие за счет сокрашения вре.45 мени на формирование адресов и обмен данных при перестановках в занесении в блок памяти, а также упростить конструкцию распределительного блока. второй выход которого соединен с первыминформационным входом блока умножения,выход которого является выходом устройства, выход блока синхронизации соединенсо входами синхронизации входйого блокапамяти, блока умножения, арифметическогоблока, блока памяти результатов и блокапамяти коэффициентов, дополнительно введенраспределительный блок, информационныйвход и вход синхронизации которого соедиЙен соответственно с выходом входного блока памяти и с выходом блока синхронизации, информационный выход и адресный выход распределительного блока соединены соот.ветственно со вторым информационным входом и с адресным входом блока памяти ре.зультатов, выход которого соединен со вторым информационным входом блока умножения.Кроме того, распределительный блок содержит счетчик, дешифратор, матрицу элементовИ, группу элементов ИЛИ, причем вход син.хронизации блока соединен со входом счетчика, выход которого соединен с адреснымвыходом блока и со входом дешифратора,выходы которого соединены с первыми входами элементов И соответствующих столбцовматрицы элементов И, разряды информационного входа блока соединены со вторыми входами элементов И соответствующих строкматрицы элементов И, выходы элементов Икаждой строки матрицы элементов И соединены с соответствующими входами соответствующего элемента ИЛИ группы, выходы элементоИЛИ группы соединены с соответствующимиразрядами информационного выхода блока.На фиг. 1 представлена блок-схема устройства; на фиг. 2 - распределительный блок,функциональная схема,Устройство. содержит входной блок 1 памяти, блок 2 синхронизации, распределительныйблок 3, блок 4 памяти результатов, арифметический блок 5, содержащий сумматор 6 иумножитель 7, блок 8 памяти коэффициентов. и блок 9 умножения.Распределительный блок 3 содержит счетчик10, дешифратор 11, матрицу 12 элементов И,группу 13 элементов ИЛИ.Устройство работает следующим образом.М ненулевых элементов последовательности,от которой вычисляется преобразование Фурье, 50поступают во входной блок 1 памяти и за.тем переупорядочиваются в отличие от известного устройства, в котором переупорядочиванию подвергается целиком весь массив из Йотсчетов. Следовательно, при М Ч в устройстве затрачивается гораздо меньше временина формирование адресов инверсных перестановок и обмен данных при выполнении этих Формула изобретения 1. Устройство для быстрого преобразования Фурье последовательности с нулевыми элементами, содержащее блок умножения, ариф метический блок, блок синхронизации, блок памяти результатов, блок памяти коэффициентов, входной блок памяти, информационный5вход которого является входом устройства, выход блока памяти результатов соединен с первым информационным входом арифмети. ческого блока, первый информационный вход блока памяти результатов соединен с выходом арифметического блока, второй ин. формационный вход которого подключен к первому выходу блока памяти козффициен. тов, второй выход которого соединен с первьм информационным входом блока умножения, выход которого является выходом устройства, выход блока синхронизации соединен со входами синхронизации входного блока памяти, блока умножения, арифметического блока, блока памяти результатов, блока памяти коэффициентов, о т л и ч аю щ е е с я тем, что, с целью повышения быстродействия устройства, в него введен распределительный блок, информационнын вход и вход синхронизации которого соединены соответственно с выходом входно;о блока памяти и с выходом блока синхронизации, информационный выход и адресный выход распределительного блока соединены соответ ственно со вторым информационным входом и с адресным входом блока памяти результатов, выход которого соединен со вторым информационным входом блока умножения. 896632. Устройство по п. 1, о т л и ч а ющ е е с я тем, что распределительный блоксодержит счетчик, дешифратор, матрицу эле.ментов И, группу элементов ИЛИ, причем ф вход синхронизации блока соединен со входом счетчика, выход которого соединен садресным выходом блока и со входом дсшифратора, выходы которого соединены с первыми входами элементов И соответствующих 1 Ь столбцов матрицы элементов И, разряды ин.формационного входа блока соединены совторыми входами элементов И соответствующихстрок матрицы элементов И, выходы элементов И каждой строки матрицы элементов И 1% соединены с соответствующими входами соот.ветствующего элемента ИЛИ группы, выходыэлементов ИЛИ группы соединены с соответ.ствующими разрядами информационного вы.хода блока,36Источники информациипринятые во внимание при экспертизе фф 1.Патент США йф 3920978,кл,235.156, 1975.2.Патент США Мф 4138730,кл.364-726, 1979.3, Авторское свидетельство СССР У 509872,кл. 6 06 Е 15/34, 1976 (прототип).896631 Фю Е. ск 07/38 Тираж 731 ВНИИПИ Государственного комитета ССС по делам изобретений и открытий 113035, Москва, Ж, Раушская наб., д."Патент", г, Ужгород, ул, Проектная Составитель В. АедоницкийТехред АСавка Корректор Г РешетнВ

Смотреть

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