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

ОП ИСАНИЕИЗОБРЕТЕН ИЯ К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ Союз СоветскихСоциалистицескихРеспублик(51 1341 9/18 ениед 1 заявки с присо осударственнын комнт Совета Мнннстров ССС оо делам нзооретеннй н открытий6.Бюллетень13 8.76 45 а опубликования описан 2) Автор изобретения Ра бинович Ордена Октябрьск й проектно) Заявительизыскательский и етических сии электр ои Революции Всесоюзный государственнынаучно-исследовательский институт энергических сетей "Энергосетьпроект" 4) УСТРОЙСТВО ДЛЯ БЫСТРОГО ПРЕОБРАЗОВАНИЯ ФУР ПОСЛЕДОВАТЕЛЬНОСТИ С НУЛЕВЫМИ ЭЛЕМЕНТАМИ ласти вычисьыход подключен ко входу блока памяти,выход которого через последовательно соединенные блок инверсной перестановки и я быстрого преарифметичем памяти,одной блок ржащие с блоко вовки в устроиств функций,н ко вхоче Это позволяетзатраты при нахообразования Фурьетельностп, содерждоцентов. меньшить вычислительные жденпи дискретного пре- (ДПФ) от последовашей часть нулевых элепклю к 10х применяойс У енин от асть нулсваны н последовательноевых элементов, все возможнони вычислений. метод вычисодержащей т с На фиг. 1 фиг. 2 ший пр сх выб представлена схема унаправленный графцедуру вычислений дланных значений. отором испольдля уденьшеоме того, в тть элементов тронст ва; на алнзую деленньУст ния вре ких ус должна т, рея опре йствах нулев :ть располож ая а ройств бло о жит Входно ледовател начальнои части исходнои пад я пати 1, распред мяти, арифд 1 ет тригонометрич,бл н ся повышение етения явля устройства я цель дос о введены Целью изобр быстродействия Поставленна что в устройствверснои переста вход 8 и выходУстройство р тигается тем ок умножения ход Которогоо блока памят елительныи блок, в с выходом входног и рас соеди Изобретение относитлительной техники,Известны устройстваобразования Фурье, содеский блок, соединенныйблок инверсной перестапамяти, соединенный сблок памяти тригонометпервый выход которогоду арифметического блоОднако в известных блок умножения соединен с выходом устройства, второй выход блока памяти тригонометрических функций подключен ко входублока умножения. елительныи блок 2 окический блок 4, блок 5 памятескнх функций, блок 6 инновки блок 7 умножения,9 устройства.аботает следующим обре 509872-1 2(И) -1 Ий Оз ы Ш М Ограничимся далее случаем, когдаВ=2 Р,Р=0,1,2,Обычный метод вычисления ДПф от последовательности из Я элементов, называемый прореживанием исходного ряда по времени, сводится к факторизации матрицы преобразования й и представлению ее с точностью до порядка расположения строк в виде Й = Г . ГГ , ( 3 ) рр" о Ненулевые элементы последовательности, от которой вычисляется ДПФ, поступают во входной блок памяти 1 и затем в распределительный блок 2, который осуществляет в блоке памяти 3 периодическое продолжение ненулевой части последовательности на всю последовательность, начиная с первого эле мента с периодом, равным минимальной степени двух, равной числу нулевых элементов или превосходящей его. 10Арифметический блок 4 выполняет стандартные арифметические операции сложения и умножения над элементами исходной последовательности, хранящимися в блоке 3 памяти и значениями тригонометрических 15 функций, взятых из блока .5 памяти тригонометрических функций. После завершения вычислений, полученные коэффициенты ДПФ упо 11 почиваются в блоке 6 инверсной перестановки и поступают в блок умножения 7, 20 на второй вход которого поданы значения тригонометрических функций, аргумент которых зависит от сдвига ненулевой части ис ходной последовательности относительно первого элемента этой последовательности, 25Для последовательности М равномерно расположенных элементов Ми, 11 = =- О, 1, 2 М -1. ДПФ определяется выражением+12, 2 1(РОпределим 1 -й шаг вычислительной процедуры в виде А= Г , А1 1 1 1 фгдеА= Г М; (7) ( = 1, 2 Р.Тогда результат Р -1-го шага вычислительной процедуры можно записать в форме вектора Ар-1д:х, х, оо,х,х, ,о,ЯЧ 2 ЧТаким образом, вектор А можнорв Яюобразовать из вектора М периодическимпродолжением ненулевых элементов М и с где вместо нулевых элементов, как и ввыражении ( 4 ), оставлены пропуски,Показатели степени, взятые в кружки,означают, что для получения показателя степени необходимо выполнить двойную инверсию над цифрой, записанной в кружке ипредставленной в двоичной форме ( например,при М = 8 и К=Э= ( 011) имеет К= 11 0)=6),факторизация матрицы преобразованияприводит к перестановке получаемых коэффициентов фурье согласно двоичной инверсии номеров этих коэффициентов.Рассмотрим теперь класс исходных последовательностей М и , содержащих частьнулевых элементов, т. е. таких, какМвместо выполнения2первых р-произведений (7),Оставшаяся часть произведений (7)для-( р; может быть найденас помощью классического метода быстрогопреобразования Фурье, Как правило, операции пересылки быстры и потерей временина их выполнение можно пренебречь.Следовательно, выигрыш вычислительныхзатрат , который обеспечивает изоб-ретение, оказывается равнымР(На фиг. 2 показан направленный графметода быстрого преобразования фурье,реализующий описанную выше процедуру вычислений для Я = 8 и М =2. На этой фигуре сплошные линии со стрелками на концахозначают умножение на о " , линии безстрелок - сложение и пунктирные линии -операцию пересылки.Наибольший интерес представляет случай, когда М ненулевых элементов расположены не в начале исходной последовательности и требуется вычислить еео 5 периодом ДПФ. Эта задача легко сводится к уже рассмотренной с помощью дискретного анало га теоремы сдвига.Пусть в последовательности из М элементов первые К элементов - нулевые, следу-З ющие М - ненулевые и оставшиеся-К-М также нулевые. Сдвинем эту последовательность на К элементов, так что ненуле -вые элементы расположатся, начиная с первого элемента всей последовательности. Затем по описанной выше методике вычислений находится ДПФ сдвинутой последовательности. Для получения ДПФ исходнойпоследовательности достаточно полученныйряд умножить на ЕХР (2 Тп 1 / М ),п=0,1 Н,Формула изобретенияУстройство для быстрого преобразования Фурье последовательности с нулевыми элементами, содержащее арифметический блок соединеннн й с блоком памяти, блок инверсной перестановки, входной блок пямяти, соединенный со входом устройства, блок памяти тригонометрических функций, первый выход которого подключен ко входу арифметического блока, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия, в него введены блок умножения и распределительный блок, вход которого соединен с вьходом входного блока памяти, выход подключен ко входу блока памяти, выход которого через последовательно соединенные блок инверсной перестановки и блок умножения соединен с выходом устройства, второй выход блока памяти тригонометрических функций подключен ко входу блока умножения,