Теоретичні відомості. Швидке перетворення Фур’є (БПФ) засноване на дискретному перетворенні Фур’є (ДПФ|)

Швидке перетворення Фур’є (БПФ) засноване на дискретному перетворенні Фур’є (ДПФ|). Дискретне перетворення застосовується до дискретних сигналів. Дискретний сигнал отримують з аналогового сигналу шляхом квантування його в часі з кроком . Для прикладу на рис.3.1, а зображений аналоговий сигнал, а на рис.3.1, б відповідний йому дискретний сигнал, Т – період сигналу.

Дискретний сигнал можна представити динамічною моделлю:

, (3.1)

де - число дискретних значень сигналу на періоді,

- імпульсна функція (дельта-функція Дираку).

Розкладемо сигнал (3.1) в комплексний ряд Фур’є

. (3.2)

Для моменту часу :

. (3.3)

Рисунок 3.1

Коефіцієнти у формулі (3.2) обчислюються таким чином:

. (3.4)

Підставимо в дану формулу ряд (3.1) і виконаємо перетворення, помінявши місцями інтеграцію і підсумовування. Замінимо змінну інтеграції і врахуємо властивості імпульсної функції, що фільтрують. В результаті отримаємо:

. (3.5)

Формули (3.3), (3.5) є дискретним перетворенням Фур’є (ДПФ|). Ці формули зазвичай записують в симетричній формі щодо числа N дискретних значень сигналу:

, (3.6)

, (3.7)

де .

Розрахунок за формулами (3.6), (3.7) вимагає операцій, що складаються з множення двох комплексних чисел з подальшим складанням. Якщо число N розкласти на множники і виконувати дії над групами елементів, то можна істотно скоротити число операцій. Найбільший ефект досягається при представленні числа N ступенем числа 2. Відповідні цьому уявленню алгоритми обчислень за формулами (3.6), (3.7) називаються швидким перетворенням Фур’є (БПФ) і вимагають всього операцій.

Алгоритм прямого БПФ реалізовано у функції fft(v) (Fast Fourier Trasform – швидке перетворення Фур’є). Аргументом функції є вектор v, представлений дійсними числами (дискретними значеннями сигналу), кількість яких повинна бути рівною, де р – ціле число. Результат роботи функції – вектор, складений з комплексних амплітуд гармонік спектру сигналу. Довжина вектора . Таким чином, довжина вихідного вектора в два рази менше вхідного.

Алгоритм зворотного БПФ реалізовано у функції ifft(w). Аргументом функції є вектор w, представлений комплексними гармоніками спектру сигналу, кількість яких повинна бути рівною, де р – ціле число. Результат роботи функції – вектор, складений з дійсних чисел, відповідних дискретним значенням сигналу, синтезованого за його спектром. Довжина вектора . Таким чином, довжина вихідного вектора в два рази більше вхідного.