Главная  Теоретические основы радиотехнологии 

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 л

т

1 .

tt !t

1 It

.. IP.

t 1 \

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. Это позволяет еще больше сократить число требуемых вычислительных операций.



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