3.4 Швидке перетворення Фур’є

Перетворення Фур’є широко використовується в інженерній практиці для аналізу як періодичних, так і неперіодичних сигналів.

Перетворення Фур’є дійсної функції , яка визначена на нескінченому інтервалі, обчислюється за формулою

,

де - частота;

- уявна одиниця.

Якщо область інтегрування не обмежена, то у загальному випадку перетворення Фур’є не існує. Для кінцевого інтервалу

часу можна отримати фінітне перетворення Фур’є

.

Допустимо, що величина спостерігається у дискретні моменти часу , де , ; - крок дискретності. Тоді інтеграл в останньому співвідношенні можна замінити сумою

.

Для обчислення вибирають, як правило, дискретні значення частот

, .

Тоді

.

Підставляючи в останню формулу замість його значення, отримуємо

.

Якщо ввести позначення , то

, (3.6)

Величина носить назву множника повороту (рис. 3.5).

Рисунок 3.5 – Геометрична інтерпретація множника повороту

Вектор , компоненти якого визначаються формулою (3.6), називається дискретним перетворенням Фур’є (Discrete Fourier Transform, DFT) вектора і позначається таким чином: .

В алгоритмі дискретного перетворення Фур’є використовуються властивості комплексних коренів із одиниці.

Комплексним коренем степеня із одиниці називають таке комплексне число , що

. (3.7)

Рівняння (3.7) має рівно комплексних коренів

, (3.8)

де ; - уявна одиниця.

Комплексні корені із одиниці рівномірно розподілені на колі одиничного радіуса з центром у нулі (рис. 3.6). Значення

(3.9)

називається головним значенням кореня степені із одиниці. Інші корені із одиниці є його степенями.

Рисунок 3.6 – Значення на комплексній площині ( )

Наведемо основні властивості коренів із одиниці.

Властивість 1. для будь-яких цілих , і

. (3.10)

Відповідно до (3.8)

. (3.11)

Властивість 2. Для будь-якого парного

. (3.12)

Використовуючи співвідношення (3.8), можемо записати . Згідно з формулою Ейлера . Із рівності (3.9) випливає, що , тобто має місце формула (3.11).

Властивість 3 (ділення наполовину). Якщо парне, то, піднісши до квадрату всі комплексних коренів степеня із одиниці, отримаємо всі комплексні корені степені із одиниці.

Із властивості 1, коли випливає, що , тобто

.

Властивість 4 (додавання). Для будь-якого і невід’ємного числа , яке не є кратним до , має місце рівність

. (3.13)

Ряд представляє собою геометричну прогресію, у якої перший член - , знаменник - і останній член прогресії .

Тому . Оскільки . Оскільки , то . Отже, маємо

.

Знаменник не перетворюється у нуль, так як не кратне .

Властивість 5. Величина періодична як по , так і по з періодом .

Нехай і будь-які цілі числа. Тоді повинно мати місце таке співвідношення:

. (3.14)

Дійсно . Величина є цілим числом, оскільки всі множники і всі доданки цілі числа. Знайдемо . Таким чином має місце рівність (3.14).

Властивість 6. Для справедлива формула

. (3.15)

Очевидно, що . Оскільки , то має місце співвідношення (3.15).

Для розв’язку FFT-задачі використаємо метод «розділяй і володарюй». Допускаємо, що степінь полінома (3.14) є степенем числа 2, тобто , де - ціле додатне число. Якщо це не так, то поліном (3.14) доповнюється до полінома степені , з нульовими коефіцієнтами при відповідних степенях. Суму у правій частині рівняння (3.6) розіб’ємо на дві частини – одна із них буде вміщувати тільки парні індекси, а інша лише немарні індекси при коефіцієнтах , тобто

, ,

і відповідно

.

Із останньої формули випливає, що

,

де ; ; .

Враховуючи те, що і .

Тоді відповідно до властивості 3 можемо записати, що

, (3.16)

де ; , .

Формула (3.16) дає змогу обчислити ординати перетворення Фур’є для значень від 0 до .

У виразах для і замінимо на . В силу того, що парне число і відповідно до властивості 5, будемо мати . Крім того, якщо взяти до уваги властивість 6, то отримаємо формулу

, (3.17)

де ; ; .

У формулі (3.17) замінимо на . Тоді

, . (3.18)

Формули (3.16) і (3.18) дають змогу скоротити число множень вдвічі, якщо обчислювати не послідовно від 0 до , а попарно - і , де .