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

СОЮЗ СОВЕТСНИХСОЦИАЛИСТИЧЕСНИХРЕСПУБЛИН щ)С 06 Г 15/332 ОПИСАНИЕ ИЗОБРЕТЕНИЯК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ Фиг. ГОСУДАРСТВЕННЫЙ НОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОЧНРЫТИЯМПРИ ГКНТ СССР(46) 07.11.90, Бюл. У 41 (71) Таганрогский радиотехнический институт им, В,Д,Калмыкова (72) К,Г,Иваненко и Л.В,Лысенко (53) 681.32 (088.8)(56) Авторское свидетельство СССР Р 129865, кл, С 06 Г 15/332, 1986,Авторское свидетельство СССР 9 1320804, кл. С 06 Р 15/332, 1986. (54) УСТРОЙСТВО ДЛЯ ФОРЬИРОВАНИЯ АДРЕСОВ ПРОЦЕССОРА БЫСТРОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ.(57) Изобретение относится к вычис 80160525 А 1 глительной технике и может быть использовано в составе процессора БПФ, Цель изобретения заключается в расширении области применения за счет реализации формирования адресов в алгоритмах простых множителей, Винограда полиномиальных преобразований.Для этого устройство содержит суммирующие счетчики 1, 2, группу из Б суммирующих счетчиков 5, преобразователь 7 кодов, комбинационный сумматор 9 и регистр 10 адреса, дешифратор 3, группу мультиплексоров 4,группу блоков 6 умножения, мультиплексор 8 и группу регистров 11. 2 нл.Изобретение относится к вычислительной технике и может быть использовано в составе процессора быстрого преобразования Фурье (БПФ).Цель изобретения - расширение области применения устройства за счет реализации формирования адресов в алгоритмах простых множителей, Винограда.и полиномиальныхпреобразований.На фиг,1 представлена структурная схема устройства, выполняющего формирование адресов процессора БПФ,реализующего алгоритм Винограда; на фиг, 2 - временная диаграмма работы устройства.В состав вычислительного устройства, выполняющего формирование адресов процессора БПФ, реализующего алгоритм ВиногРада, входят первый суммируюший счетчик 1, второй суммирующий счетчик 2, дешифратор З,группа мультиплексоров 4, группа суммирующих счетчиков 5, группа блоков 6 умножения, преобразователь 7 кодов, мультиплексор 8, комбинационный сумматор 9, регистр 1 О адреса, группа регистров 11, вход 12 сопровождения данных устройства, выход 13 устройства, входы 14,1-14,Ь постоянного коэффициента устройстваУстройство предназначено для формирования адресов процессора, реализующего алгоритм Винограда преобразования Фурье (АВПФ). Алгоритм Винограда основан на представленииматрицы 11Г 11 - точечного диск"Ю:еретного преобразования Фурье (1 ШФ),где 11 Е - взаимно простые числа, ввиде прямого произведения матриц11 - точечных ДПФ61,1: 1,111,1,Я,111,и сведении вычисления 11 Е - точечныхДПФ к вычислению круговых сверток сиспользованием арифметики в кольцеполиномо.з. Короткие 11 Е - точечныепоследовательности вычисляются по алгоритму Рейдера, позволяющему существенно сократить число вычислитель/ных операций, Алгоритм Виноградаобъединяет короткие последовательности в гнездовую структуру.Адреса операндов для алгоритмаВинограда определяются на входе покитайской теореме об остатках (КТО): Ми: -- -"и Тшой М (1)- шее е"Э 7е=15 где М = Г 1 шЕ - размер преобразования;Е= шЕ - взаимно простые модули;и - вычет и по модулю шМ10 - -- -"Т= 1 шоршеПоследовательность адресов на выходе .определяется по формулеМ15 и: ф --- " ишой М (2)=с- шС=6Реализация АВПФ состоит из Ь этапов, на каждом из которых адреса операндов определяются по формуле (1), 20 Различается лишь порядок следованиячленов формулы (1). Так, на первомэтапе В изменяется от 1 до Ь, на втором - от 2 до Ь и далее до 1, натретьем от 3 до Ь и далее до 2 ит.д. Такую процедуру реализует кольцевая структура из Ь счетчиков повзаимно простым модулям. На 1-м этапе реализации АВПФ Е-й счетчик группы является первым по порядку рабо ты, (1+1)-й - вторым и т.д. На счетный вход первого по порядку работысчетчика группы поступают импульсысопровождения данных, на счетныевходы остальных счетчиков группысигналы с выходов переполнения предыдущих счетчиков группы. Данным процессом управляют первый 1 и второй 2счетчики и дешифратор 3. На каждом 1-м этапе на счетныйвход первого счетчика 1 поступают импульсы сопровождения данных и после прихода (11-1)-го импульса формируется сигнал его переполнения, который 45 поступает на счетный вход второгосчетчика 2, увеличивая его содержимое на единицу. Таким образом, счет, - чик 2 является счетчиком итерации или этапа, На Й-м этапе Е-й выход дешифратора 3 находитс в активном состоянии, т.е, на 1-м выходе - логический нуль, который поступает на управляющий вход 1-го мультиплексора 4 группы, разрешает прохождение на его выход информации с его первого входа, т.е, импульсов сопровождения данных. Остальные выходы дешифратора 3 - пассивны и находятся в логической единице, поэтому на выходы всех