Дискретне перетворення Фур’є. Лекція 2 презентация

Що чує вухо?

Тема лекції
Дискретне перетворення Фур’є
перехід в частотну область
«Будь-яка достатньо розвинена технологія нічим не відрізняється від магії» Артур С.Кларк

Важливо пам’ятати
Пряме перетворення Фур’є здійснює перехід з часової області сигналу в частотну (в результаті перетворення ми знаємо які частоти є в сигналі)
Зворотнє перетворення Фур’є здійснює перехід з частотної області сигналу в часову

Дискретне перетворення Фур’є використовується для дискретизованого сигналу
(вхідний сигнал)
N – кількість відліків, які слідують в часі з періодом дискретизації Т=Δt, та частотою дискретизації
Ω- частота першої гармоніки
N>>1

Формули розрахунку ДПФ
Враховуючи що

Приклад ДПФ для послідовності чотирьох чисел
N=4
Знайти X(0) X(1) X(2) X(3)

Приклад ДПФ для послідовності чотирьох чисел
N=4
Знайти X(0) X(1) X(2) X(3)

Приклад ДПФ для послідовності чотирьох чисел
N=4
Знайти X(0) X(1) X(2) X(3)

Важливі узагальнення
В результаті ДПФ над N числами отримуємо комплексний вектор чисел довжиною N.
Частина результуючого вектора до N/2 є комплексно спряженою до другої половини.
В ЦОС достатньо розглядати лише першу половину результуючого вектора, оскільки вона відповідає за частотний діапазон сигналу від 0 до fd/2 ≅fmax. Далі по частотній шкалі відбувається віддзеркалення спектру.
Графічна залежність ⏐Х⏐ від частоти (кратної до частоти дискретизації) отримала назву спектру сигналу.

Результат чисельний та графічний
Чисельний результат
Графічний
m=0..N/2
На графіку m=0..N

Зворотнє (обернене) перетворення Фур’є

Обчислювальна складність ДПФ
Наприклад для 8 точок
Висновок: через високу обчислювальну складність використовують алгоритми швидкого перетворення Фур’є

FFT fft ШПФ БПФ
алгоритм Кулі-Тьюкі (Cooley-Tukey)
Знижує об’єм обчислень
Використовує децимацію (проріджування) в часовій області
Використовується для послідовностей довжиною 2n
Де позначено
Легко довести

Основна ідея
Вхідну послідовність розбиваємо на дві: парну і непарну
Результатом є сума Фур’є перетворень для половини послідовності з ваговим коефіцієнтом W
Доведемо за допомогою формули ДПФ

Приклад «знайомої» послідовності
{1,0,0,1} чотирьохточкове перетворення FFT
x(0) x(1) x(2) x(3)
Розбиваємо на 2 по 2
x(0) x(2) x(1) x(3)
ДОПОМІЖНІ ОБЧИСЛЕННЯ W
Отримали такий самий результат як і при ДПФ

Схема метелика

Залежність кількості обчислень від кількості точок
Кількість обчислень при 1024 точках в 205 разів менша у ШПФ (FFT)
В результаті ДПФ та ШПФ отримуємо однаковий вектор комплексних чисел

У зв’язку з широким використанням FFT в усіх мовах програмування є бібліотеки, які його реалізують

Приклади сигналів та їх спектрів
Гармонічний
Прямокутні імпульси
Шум
Під сигналом будемо розуміти звуковий сигнал та генерувати його за допомогою звукового редактора

Гармонічний сигнал з частотою Гц та частотою дискретизації Гц

Спектр прямокутних імпульсів з частотою Гц
та частотою дискретизації Гц

Спектр білого шуму
Частота дискретизації сигналу 44100Гц

Рікі Мартін Live in La Vida Loka ☺