Курс лекций дисциплины вариативной части математического и естественнонаучного цикла (855805), страница 16

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 16)

с ростомдлины преобразования N количество умножений и сложений растетквадратично (при прямой реализации ДПФ). В 1965 году была опубликованастатья Дж. В. Кули (Cooley) и Дж. Тьюки (Tukey), в которой описывалсяэффективный алгоритм вычисления ДПФ (уменьшает число умножений с N 2до N log 2 N , но требует, чтобы N было степенью двойки). Кроме этогоалгоритма известны работы Винограда, гнездовой алгоритм, алгоритмБлюстейна и т.п. Каждый из методов использует свойства ДПФ и накладываетограничения на выбор длины преобразования. Например, эффективныеалгоритмы БПФ требуют длин выборки равной простому числу или егостепени.Известныйгнездовойалгоритмпредполагает,чтодлинапреобразования представляется произведением простых чисел.Широкое распространение алгоритма по основанию два (Кули-Тьюки)объясняется простотой реализации в вычислительных системах.

РассмотримДПФ длины N=2k (k – целое число).N −1X (k ) = ∑ x(n )e−j2 knNn =0Последовательность отсчетов можно разбить на две части – с четнымииндексами и нечетными:X (k ) ==0.5 N −1∑ x(2n ) e−j2 k2nNn =00.5 N −1∑ x(2n ) en =0−j2 kn0.5 N+0.5 N −1∑ x(2n + 1) e−j2 k( 2 n +1)Nn =0+e−j2 k 0.5 N −1N∑ x(2n + 1) e−j=2 kn0.5 Nn =0Обе суммы (по четным и нечетным индексам исходной последовательности)представляют собой ДПФ длины 0.5N.

Однако, число отсчетов в частотнойобласти также равно 0.5N: X (k ) = X чет (k ) + e−j2 kNX нечет (k ) , k=0, …, 0.5N-1.Для получения отсчетов из диапазона 0.5N ÷ N необходимо воспользоватьсяпериодичностью дискретного спектра:131X чет (k + 0.5 N ) = X чет (k ) , X нечет (k + 0.5 N ) = X нечет (k )X (k ) = X чет (k − 0.5 N ) + e−j2 kN−j2( k − 0 .5 N )N= X чет (k − 0.5 N ) − eX нечет (k − 0.5 N ) =X нечет (k − 0.5 N )Далее, рассматривая полученные две последовательности (отсчеты счетными и нечетными индексами) как независимые, разбиваем их по аналогии,получая ДПФ вдвое короткой последовательности, и так далее до тех пор, покане останется набор последовательностей ДПФ длины 2 – рис.

4.10.x(0)x1(0)x3(0)=x(0)x(1)x1(1)x3(1)=x(4)x(2)x1(2)x4(0)=x(2)x(3)x1(3)x4(1)=x(6)x(4)x2(0)x5(0)=x(1)x(5)x2(1)x5(1)=x(5)x(6)x2(2)x6(0)=x(3)x(7)x2(3)x6(1)=x(7)N=80.5N=40.25N=2№ двоичноепредставление01234567двоичноинвертированноепредставление№00010001011000110101111104261537000001010011100101110111Рис. 4.10 – Процесс разбиения последовательности в алгоритме Кули-ТьюкиИтеративный процесс разбиения последовательности отсчетов на четные инечетные индексы приводит к перестановке данных. При этом связь индексовисходной и конечной последовательностей осуществляется так называемойдвоичной инверсией (пример – таблица на рис. 4.10). В процессе разбиениякаждаясуммаотсчетовснечетнымиповорачивающий множитель типа W = ekN−jиндексами2kNумножаетсяна(каждая пунктирная стрелка нарисунке):X (k ) =X (k1 ) =N −1∑ x(n ) e−j2 knNn =00.5 N −1∑ x(2n ) en =0, k = 0 ÷ N −1−j2 k1n0 .5 N+e−j2 k1 0.5 N −1N∑ x(2n + 1) en =0−j2 k1n0 .5 N= A1 (k1 ) + WNk1 B1 (k1 )NNX  k1 +  = A1 (k1 ) − WNk1 B1 (k1 ), k1 = 0 ÷ − 122132A1 (k 2 ) =0.25 N −1∑ x(4n )e−j2 k 2n0.25 Nn =0+e−j2 k 2 0.25 N −10 .5 N∑ x(4n + 1)e−j2 k 2n0.25 Nn =0== А 2 (k 2 ) + W0k.52 N B 2 (k 2 )NNA1  k 2 +  = A 2 (k 2 ) − W0k.52 N B 2 (k 2 ), k 2 = 0 ÷ − 144B1 (k 2 ) =0.25 N −1∑ x(4n + 2)e−j2 k 2n0.25 Nn =0+e−j2 k 2 0.25 N −10 .5 N∑ x(4n + 3)en =0−j2 k 2n0.25 N== А3 (k 2 ) + W0k.52 N B 3 (k 2 )NNB1  k 2 +  = A3 (k 2 ) − W0k.52 N B 3 (k 2 ), k 2 = 0 ÷ − 144Далее каждая из последовательностей A2, B2, A3, B3 снова делятся на две.Процесс следует прекратить, когда в каждой последовательности останетсявсего два отсчета.

Поэтому на произвольном шаге разбиения получаетсяунифицированнаяоперация,связывающаяотсчетытекущегошагаспредыдущим, которая известна как бабочка Фурье. Алгоритм с разбиениемотсчетов во временной области получил название быстрого преобразованияФурье (БПФ) с прореживанием по времени.X (k i ) = X чет + WNkii X нечетXчетXнечетWNki(X k i + 0.5 Ni)= Xчет− WNkii X нечетРис. 4.11 – Бабочка Фурье при прореживании по времениПример.Даны отсчеты синусоидального сигнала (8 отсчетов на период)x(0)x(1)x(2)x(3)x(4)x(5)x(6)x(7)00.5 210.5 20− 0.5 2−1− 0.5 2Спектр сигналаX(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)0-j0.500000j0.51337X (k ) = ∑ x(n )e−j2 kn8n =03X (k1 ) = ∑ x(2n )e−j, k =0÷72 k1n4+en =0−j2 k1 38∑ x(2n + 1)e−j2 k1n4n =0= A1 (k1 ) + W8k1 B1 (k1 )X (k1 + 4 ) = A1 (k1 ) − W B1 (k1 ), k1 = 0 ÷ 3k181A1 (k 2 ) = ∑ x(4n )e−j2 k 2n2n =0+e−j2 k 2 14∑ x(4n + 1)e− jk 2+e− j k22A1 (k 2 + 2 ) = A 2 (k 2 ) − W4k2 B 2 (k 2 ), k 2 = 0 ÷ 1B1 (k 2 ) = ∑ x(4n + 2 )e−j2 k 2n2n =0+e−j= x 2 + x6 e[x1∑ x(4n + 3)e+e− j k22A2(0)A2(1)x(4)e− j k 2A3(0)x(2)A3(1)x(6)e− j k 2[xx(5)B2(1)e− j k 2B3(0)x(3)B3(1)x(7)e− j k 23−j2 k 2n2=]+ x7 e − jk2 = А3 (k 2 ) + W4k2 B 3 (k 2 )A1(0)− j k2e 2− j k2e 2B2(0)x(1)]n =0− jk 2=+ x5 e − jk2 = А 2 (k 2 ) + W4k2 B 2 (k 2 )2 k 2 14B1 (k 2 + 2 ) = A3 (k 2 ) − W0k.52 N B 3 (k 2 ), k 2 = 0 ÷ 1x(0)2 k 2n2n =0= x0 + x 4 e1−jA1(2)A1(1)A1(3)X(0)− j k2e 4X(1)− j k2e 4B1(0)− j k2e 2− j k2e 2B1(2)B1(1)B1(3)X(4)X(5)X(2)− j k2e 4X(6)X(3)− j k2e 4X(7)Рис.

4.12 – Структурная схема алгоритма Кули-Тьюки (N=8, прореживание по времени)Аналогичным образом можно построить алгоритм с прореживанием почастоте.134X (k ) =0.5 N −1∑ x(n ) e2 knNn =0С учетом, что eX (2k ) =−j−j2 k0.5 NN+0.5 N −1∑ x(n + 0.5 N ) e−j2 k( n + 0 .5 N )Nn =0= (− 1) можно получить:k0.5 N −1∑ [x(n ) + x(n + 0.5 N )]e−j2 kn0 .5 Nn =0X (2k + 1) = e−j2 k 0.5 N −1N∑ [x(n ) − x(n + 0.5 N )]e−j2 kn0 .5 Nn =0x(m)x(m+0.5N)xчетWkxнечетРис.

4.13 – Бабочка Фурье при прореживании по частотеСравнение эффективности вычислений ДПФ по методу Кули-Тьюки попорядку числа операций умножения относительно прямого вычисления поформуле представлено на рис. 4.14.Число операцийN2N log 2 NNРис. 4.14 – Эффективность БПФ по сравнению с прямым ДПФ135ДПФ действительного сигнала, невзирая на алгоритмы БПФ, все равносодержит избыточность, т.к. спектр сигнала симметричен (это означает, чтофактически расчет одной и той же величины выполняется дважды). В связи сэтим появились модификации быстрых алгоритмов под задачи, которыетребуют расчета ДПФ двух разных сигналов.

Известны два подхода: методдвойного преобразования и метод ДПФ сигнала удвоенной длины.4.2.1 Двойное преобразованиеЕсли два независимых действительных входных сигнала x1 (n ) и x2 (n ) соспектрами X 1 (k ) и X 2 (k ) соответственно представить одним комплекснымсигналом:x(n ) = x1 (n ) + jx2 (n ) , то выполнение одного БПФ позволяетрассчитать спектры обоих сигналов одновременно.N −1X (k ) = ∑ ( x1 (n ) + jx2 (n ))en =0−j2 knNN −1= ∑ x1n e−j2 knNn =0N −1+ j ∑ x2 n e−j2 knNn =0=N −1N −1  2k   2k  2k   2k  = ∑ x1n  cosn  − j sin n   + j ∑ x2 n  cosn  − j sin n =NNNNn =0n=0N −1N −1 2k  2k   2k  2k  = ∑  x1n cosn  + x2 n sin n   + j ∑  x2 n cosn  − x1n sin n =n =0 n =0  N  N  N  N = X re (k ) + jX im (k )Поскольку сигнал на входе был комплексным, то его спектр, очевидно,не обладает симметрией.

Однако в силу линейности свойств ДПФ онпредставляет собой линейную комбинацию спектров сигналов x1 и x2.N −1 2k  2k  X ( N − k ) = ∑  x1n cosn  − x2 n sin n +n =0  N  N N −1 2k  2k  + j ∑  x2 n cosn  + x1n sin n   = X re ( N − k ) + jX im ( N − k )NNn =0 Поэтому возможно по данным действительным X re (k ) , X re ( N − k ) и мнимымX im (k ) , X im ( N − k ) частям спектра комплексного сигнала x(n ) = x1 (n ) + jx2 (n )определить спектры сигналов x1 (n ) и x2 (n ) :X 1 (k ) = 0.5[ X re (k ) + X re ( N − k )] + j 0.5[ X im ( N − k ) − X im (k )]X 2 (k ) = 0.5[ X im ( N − k ) + X im (k )] + j 0.5[ X re (k ) − X re ( N − k )]136Эффективность вычислений теоретически увеличивается в два раза завычетом операций для вычисления спектров исходных сигналов из спектракомплексного сигнала.

В таблице 4.2 представлено аналитическое сравнениеметода двойного преобразования с расчетом двух независимых БПФ длякаждого сигнала в отдельности.Таблица 4.2 – Эффективность метода двойного преобразованияВид алгоритмаОперацииСложенияУмножения6 N log 2 N4 N log 2 N3 N log 2 N + 2 N2 N log 2 N + NДва БПФ«Двойное» БПФТогда можно вычислить коэффициент эффективности в зависимости отдлины преобразования (считая, что операции умножения и сложения имеютодинаковую трудоемкость вычисления):  =5 log 2 N − 3100% .

На рис. 4.1510 log 2 Nпостроена полученная зависимость.η, %4846444240383634 010N110210310410510Рис. 4.15 – Эффективность метода двойного преобразования посравнению с расчетом двух независимых БПФ1374.2.2 БПФ действительного сигнала удвоенной длиныДопустим, дана выборка действительного сигнала x(n ) четной длины:2N отсчетов, спектр которого обозначим X (k ) .

Характеристики

Список файлов лекций