Різниця між FFT та DFT

Швидке перетворення Фур'є (FFT) Vs. Дискретне перетворення Фур'є (DFT)

Технологія та наука йдуть рука об руку. І немає кращого прикладу цього, ніж цифрова обробка сигналів (DSP). Обробка цифрових сигналів - це процес оптимізації точності та ефективності цифрових комунікацій. Все - це дані - будь то зображення із зондів космічного простору або сейсмічні коливання та щось середнє. Для перетворення цих даних у читаний для людини формат за допомогою комп'ютерів - це цифрова обробка сигналів. Це одна з найпотужніших технологій, що поєднує в собі як математичну теорію, так і фізичну реалізацію. Вивчення DSP розпочалося як випускний курс з електротехніки, але з часом воно стало потенційним змінником ігор у галузі науки та техніки. Досить сказати, що без DSP інженери та вчені можуть припинити своє існування.

Перетворення Фур'є - це засіб відображення сигналу в часовій або просторовій області в його спектр у частотній області. Часові та частотні області - це лише альтернативні способи подання сигналів, а перетворення Фур'є - це математична залежність між двома поданнями. Зміна сигналу в одному домені також впливатиме на сигнал в іншому домені, але не обов'язково таким же чином. Дискретне перетворення Фур'є (DFT) - це перетворення, подібне перетворенню Фур'є, яке використовується з оцифрованими сигналами. Як випливає з назви, саме дискретна версія FT розглядає як часову, так і частотну область як періодичну. Швидка трансформація Фур'є (FFT) - це лише алгоритм швидкого та ефективного обчислення DFT.

Дискретне перетворення Фур'є (DFT)

Дискретна перетворення Фур'є (DFT) - один з найважливіших інструментів цифрової обробки сигналів, що обчислює спектр сигналу кінцевої тривалості. Дуже звичайно кодувати інформацію в синусоїдах, які утворюють сигнал. Однак у деяких додатках форма форми хвилі часової області не застосовується для сигналів, у цьому випадку вміст частоти сигналу стає дуже корисним іншими способами, ніж цифровими сигналами. Представлення цифрового сигналу з точки зору його частотної складової в частотній області є важливим. Алгоритм, який перетворює сигнали часової області в компоненти частотної області, відомий як дискретний перетворення Фур'є або DFT.

Швидке перетворення Фур'є (FFT)

Швидка трансформація Фур'є (FFT) - це реалізація DFT, яка дає майже ті ж результати, що і DFT, але вона неймовірно більш ефективна і набагато швидша, що часто значно скорочує час обчислення. Це просто обчислювальний алгоритм, який використовується для швидкого та ефективного обчислення DFT. Різні швидкі методи обчислення DFT, відомі в сукупності як швидке перетворення Фур'є або FFT. Гаусс першим запропонував методику обчислення коефіцієнтів у тригонометричній орбіті астероїда в 1805 р. Однак, лише в 1965 р. Семінарний документ Кулі і Тукі привернув увагу наукової та інженерної спільноти, яка також заклала основи дисципліни цифрової обробки сигналів.

Різниця між FFT і DFT

1. Значення FFT та DFT

Дискретна трансформація Фур'є, або її просто називають DFT, - алгоритм, який перетворює сигнали часової області в компоненти частотної області. DFT, як випливає з назви, справді дискретний; дискретні набори даних часової області перетворюються на дискретне представлення частоти. Простіше кажучи, він встановлює залежність між представленням часової області та поданням частотної області. Швидке перетворення Фур'є або FFT - це обчислювальний алгоритм, що скорочує час обчислення та складність великих перетворень. FFT - це лише алгоритм, який використовується для швидкого обчислення DFT.

2. Алгоритм FFT та DFT

Найпоширенішим алгоритмом FFT є алгоритм Cooley-Tukey, який був названий на честь Дж. У. Кулі та Джона Тукі. Це алгоритм розділення і підкорення для машинного розрахунку складних рядів Фур'є. Він розбиває DFT на більш дрібні DFT. Інші алгоритми FFT включають алгоритм Радера, алгоритм перетворення Фур'є Винограда, алгоритм перетворення Чірпа Z і т. Д. Алгоритми DFT можуть бути запрограмовані на цифрових комп'ютерах загального призначення або реалізовані безпосередньо спеціальним обладнанням. Алгоритм FFT використовується для обчислення DFT послідовності або її зворотного. DFT може бути виконаний як O (N²) у часовій складності, тоді як FFT зменшує складність часу в порядку O (NlogN).

3. Застосування FFT та DFT

DFT може бути використаний у багатьох системах цифрової обробки в різних сферах застосування, таких як обчислення частотного спектру сигналу, вирішення часткових диференціальних застосувань, виявлення цілей за допомогою радіолокаційних відлунь, кореляційний аналіз, обчислення множинного полінома, спектральний аналіз тощо. FFT широко застосовується для акустичних вимірювань у церквах та концертних залах. Інші програми FFT включають спектральний аналіз в аналогових відеовимірюваннях, велике ціле і поліноміальне множення, алгоритми фільтрування, обчислення ізотопних розподілів, обчислення коефіцієнтів ряду Фур'є, обчислення згортків, генерування низькочастотного шуму, проектування кіноформ, виконання щільних структурованих матриць, обробку зображень та більше.

FFT проти DFT: Порівняльна діаграма

Підсумок FFT Vs. DFT

У двох словах, дискретна перетворення Фур'є відіграє ключову роль у фізиці, оскільки вона може бути використана як математичний інструмент для опису взаємозв'язку між часовим доменним та частотним представленням дискретних сигналів. Це простий, але досить трудомісткий алгоритм. Однак для скорочення обчислювального часу та складності великих перетворень можна використовувати більш складний, але менш трудомісткий алгоритм, такий як швидка перетворення Фур'є. FFT - це реалізація DFT, що використовується для швидкого обчислення DFT. Коротше кажучи, FFT може робити все, що робить DFT, але ефективніше та набагато швидше, ніж DFT. Це ефективний спосіб обчислення DFT.