|
Главная Теоретические основы радиотехнологии 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 [ 34 ] 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 х(] = х(0) - х(1) +... + x(N - 2) - x(N -1) = (-lfx(k). J k=Q Согласно (6.25), спектр является сопряженно-симметричным относительно N/1. Это наглядно иллюстрирует тот факт, что спектр содержит ровно такое же количество информации, что и сам сигнал. В самом деле, исходная последовательность представляется набором из N вещественных чисел. Спектр же представляется набором из N/2 (вторая половина взаимно однозначно связана с первой) комплексных чисел, каждое из которых с информационной точки зрения эквивалентно двум вещественным. Если же исходная последовательность {х{к)) не является вещественной, симметрия спектра отсутствует и N комплексным отсчетам во временной области соответствует N комплексных отсчетов в спектральной области. 4. ДПФ произведения последовательностей. Возьмем две последовательности отсчетов {xi{k)} и {xjk)} одинаковой длины N и вычислим результат их поэлементного умножения: У{к) = Хх{к) Х2(к). Если применить к этой формуле прямое ДПФ, получится следующее выражение: y( ) = -lrfl!xi(i)X2(n-i). (6.27) -Л' ,-=0 Замечание 2 При выполнении вычислений по формуле (6.27) могут понадобиться значения 2(0 с номерами /, выходящими за рамки диапазона 0...N- 1. В этом случае следует воспользоваться свойством периодичности спектра: X2(i) = X2(i± N). При и = О из (6.27) получается дискретный аналог теоремы Рэлея (см. § 1.7 и формулу (1.56)): ПО) = ici(к)Х2 (к) = А-, (02 (-/) = 1 т*2 И). (6.28) При выводе формулы (6.28) были использованы соотношения (6.25) и (6.26). Если, кроме того, последовательности {х\(к)} и {Х2(к)} совпадают, т. е. xi(k) = Х2(к) = х{к) для всех k = G...N- 1, из (6.28) получается дискретный аналог равенства Парсеваля (см. § 1.7 и фор-мулу (1.57)): N-[ I N-l . 2 Z () = Т7 I И') к=0 /=0 5. ДПФ круговой свертки последовательностей. Так как мы рассматриваем периодические последовательности, то и суммирование при вычислении свертки таких последовательностей следует производить по одному периоду. Такую операцию называют круговой сверткой: У(к) = l!xi (i)x2 (к - i) = х, (i)x2 ((к - i) mod N) (6.29) j=0 J=0 (в этой формуле выражение (к - i) mod N означает взятие (к - /) по модулю N, т. е. вычисление остатка от деления (к - i) на N). Подставив выражение (6.29) в (6.23), легко убедиться, что круговая свертка периодических временных последовательностей соответствует перемножению их спектров: Пп) = Xi{n)X2(n). (6.30) Замечание 3 Помимо круговой свертки существует операция линейной свертки, которая применяется к дискретным последовательностям конечной длины. Линейная свертка является основой алгоритма дискретной фильтрации, речь о котором пойдет в § 6.9. Пример. Чтобы проиллюстрировать периодичность сигнала, подразумеваемую при использовании ДПФ, рассмотрим результаты применения этого преобразования к дискретному гармоническому сигналу s(k) = А cos((akT + ц>). (6.31) В первом случае (рис. 6.11, о) анализируемая последовательность содержит целое число периодов гармонического сигнала (т. е. отношение N(aT/(2n) является целым числом). Подставив (6.31) в формулу ДПФ (6.23), получим следующее: 1 I И! о I о 1 I I 1 \Х(п)\ 8 ,121 15 л
IX(n) 8 15 n Рис. 6.11. Дискретное преобразование Фурье для целого (с) и нецелого (б) числа периодов гармонического сигнала (слева - исходные последовательности, справа - их амплитудные спектры) Х(п) = ANeJ п = --N, 2п 2п в остальных случаях. Таким образом, аналогично спектру непрерывного гармонического сигнала, ДПФ отличается от нуля всего для двух значений п. Однако если отношение М(йТ/(2п) не является целым числом (см. рис. 6.И, б), спектр оказывается значительно более богатым. Этому можно дать простое объяснение: ведь в данном случае периодически продолженная последовательность, как показано на рисунке, уже не может являться набором отсчетов непре- рывной синусоиды. Поэтому, в полном соответствии со свойствами преобразования Фурье, в спектре появляются дополнительные составляющие. Восстановление непрерывного сигнала с помощью ДПФ. Являясь по своей сути спектром дискретного периодического сигнала, дискретное преобразование Фурье позволяет легко восстановить непрерывный периодический сигнал, занимающий ограниченную полосу частот. Для этого в формуле обратного ДПФ (6.24) необходимо заменить дискретный параметр (номер отсчета к) на непрерывный - нормированное время t/T, где Т- период дискретизации: х(0 = 1 N Е А'( )ехр| ( .2nnt NT ) (6.32) Следует обратить внимание на еще одно отличие этого соотношения от формулы (6.24): диапазон индексов суммирования смещен вниз на N/2 (при четном N); при нечетном N суммирование производится от n = -{N-\)/2 до (N- \)/2. Это необходимо, чтобы получить аналоговый сигнал, занимающий полосу частот от О до и/Т. Коэффициенты X(ji) с отрицательными номерами могут быть получены из соотношения симметрии (6.25). Результат восстановления непрерывного периодического сигнала с помощью ДПФ, разумеется, совпадает с результатами, получаемыми при использовании ряда Котельникова (6.5). Однако использование ДПФ в данном случае оказывается более предпочтительным, так как ряд Котельникова для периодического сигнала содержит бесконечное число слагаемых, а формула (6.32) - конечное. 6.7. БЫСТРОЕ ПРЕОБРАЗОВАНИЕ ФУРЬЕ Для вычисления одного коэффициента ДПФ по формуле (6.23) необходимо выполнить Л^ комплексных умножений и сложений. Таким образом, расчет всего ДПФ, содержащего Л^ коэффициентов, потребует Л^ операций умножение - сложение . Число операций возрастает пропорционально квадрату размерности ДПФ. Однако, если Л^ не является простым числом и может быть разложено на множители, процесс вычислений можно ускорить, разделив анализируемый набор отсчетов на части, вычислив их ДПФ и о&ьединив результаты. Рассмотрим этот процесс на примере деления набора отсчетов пополам. Итак, пусть Л' - четное число. Вьщелим в формуле (6 23) два слагаемых, соответствующих элементам исходной последовательности с четными и нечетными номерами: 2ж2тп --I Х(п) = X х(2т)е + х{2т + 1)е .2ж(2т+\)п Введем обозначения у(т) = х{2т) и z(m) = х(2т+\), а также вынесем из второй суммы общий множитель eJ /: .2птп .2птп Х(п)= ЯАи)е /2 Z{m)e (6.33) Две суммы в (6.33) представляют собой ДПФ последовательностей {у(т)} (отсчеты с четными номерами) и {z(m)} (отсчеты с нечетными номерами). Каждое из этих ДПФ имеет размерность N/2. Таким образом, .27СП Х{п) = Пп) + е ~Z(ji), (6.34) где Y(ji) и Z{n) - ДПФ, соответственно, последовательностей отсчетов с четными и нечетными номерами: .2птп .2ктп Z(n)= Е z(ni)e /2 Так как ДПФ размерности N/2 дает лишь N/2 спектральных коэффициентов, непосредственно использовать формулу (6.34) можно только при О < л < N/2. Для остальных п (N/2 < п < N) следует воспользоваться периодичностью спектра дискретного сигнала (и, соответственно, периодичностью результатов ДПФ): Y(n + ) = Yin), Zin + ) = Z(n). Рис. 6.12. Вычисление 8-точечного ДПФ с помощью двух 4-точечных ДПФ С учетом этого при п < N/2 формула (6.34) представляется в виде ( ) = Т(,1-у) + е Z(n -) = = T( -f)-.->-T>z( -). Процесс вычисления 8-точечнрго ДПФ путем разбиения его на два 4-точечных ДПФ иллюстрируется на рис. 6.12. Оценим количество операций, необходимое для вычисления ДПФ указанным образом. Каждое из двух ДПФ половинной размерности требует /4 операций. Кроме того, при вычислении окончательных результатов каждый спектральный коэффициент Z{n) умножается на экспоненциальный комплексный множитель. Это добавляет еще N/2 операций. Итого получается N N(N + 1) что почти вдвое меньше, чем при 4 2 2 вычислении ДПФ прямым способом. Если N/2 тоже является четным числом (т. е. если N делится на 4), можно продолжить описанную процедуру, выразив результат через четыре ДПФ размерности N/4. Это позволяет еще больше сократить число требуемых вычислительных операций. |