Свойства дискретного преобразования Фурье

1. Линейность ДПФ. ДПФ суммы дискретных последовательностей длительности N равно сумме ДПФ слагаемых суммы и имеет длину N:

;                                          (3.6)

.                                        (3.7)

2. ДПФ сумм последовательностей разной длины. Если в исходной сумме последовательностей  разные длины: N₁, N₂, N₃, …, то перед вычислением ДПФ всей последовательности необходимо привести последовательности к одинаковой длине N, равной максимальной длине исходных последовательностей, за счет дополнения нулями.  

 

3. Сдвиг ДПФ. Сдвиг ДПФ по оси k вправо на величину k₀ соответствует умножению исходной последовательности на комплексную экспоненту:

 

.                                         (3.8)

 

4. Сдвиг исходной последовательности. Сдвиг последовательности вправо на m отсчетов (задержка последовательности) соответствует умножению ДПФ на комплексную экспоненту:

.                                (3.9)

5. Теорема Парсеваля.

.                                (3.10)

Теорема Парсеваля утверждает, что энергию сигнала можно вычислить как во временной, так и в частотной области.

 

6. Свойство симметрии. Свойство симметрии вещественной последовательности:

,                                        (3.11)

,                                        (3.12)

;                                (3.13)

 

 ось симметрии проходит через точку .

Для четного N:

, .                      (3.14)

 

Из последнего равенства следует, что  и  всегда действительные числа.

 

7. ДПФ вещественной последовательности. ДПФ вещественной последовательности полностью определено на интервале , который соответствует основному спектру сигнала.

 

Литература

Романюк Ю.А. Дискретное преобразование Фурье в цифровом спектральном анализе. Учебное пособие. – М.: МФТИ, 2007. – 120 с.

 

 

Лекция 4. Быстрое преобразование Фурье

Общие сведения о БПФ

Термином «быстрое преобразование Фурье» (БПФ: FFT) описывают алгоритмы вычисления дискретного преобразования Фурье (ДПФ: DFT), обеспечивающие экономию в числе арифметических операций и в первую очередь операций умножения.

Для вычисления одного коэффициента ДПФ необходимо выполнить  операций комплексного умножения и суммирования. Расчет всего ДПФ, содержащего  спектральных коэффициентов, потребует   пар операций «умножение – сложение».

Если  не является простым числом и может быть разложено на множители (является целочисленной степенью 2: N= ,  - целое число), то процесс вычислений можно ускорить, разделив исходную последовательность на части, вычислив для них ДПФ и объединив результаты.

При реализации БПФ возможно несколько вариантов организации вычислений в зависимости от способа деления исходной последовательности на части: прореживание по времени или по частоте, и от того, на сколько фрагментов производится разбиение последовательности на каждом шаге (основание БПФ).?

Первый алгоритм БПФ с основанием 2, известный как алгоритм БПФ Кули-Тьюки был опубликован в 1965 г. в США учеными Кули и Тьюки.