Швидке́ перетво́рення Фур'є́ (часто FFT від англ. Fast Fourier Transform) — швидкий алгоритм обчислення дискретного перетворення Фур'є. Якщо для прямого обчислення дискретного перетворення Фур'є з N точок даних потрібно O(N 2) арифметичних операцій, то FFT дозволяє обчислити такий же результат використовуючи O(N log N) операцій. Алгоритм FFT часто використовується для цифрової обробки сигналів для перетворення дискретних даних з часового у частотний діапазон.
Основний алгоритм
Покажемо як виконати дискретне перетворення Фур'є за обчислень при
. Зокрема, при
знадобиться
обчислень.
Дискретне перетворення Фур'є перетворює набір чисел в набір чисел
, такий, що
, де
і
при
. Алгоритм швидкого перетворення Фур'є може бути застосований до будь-яких комутативних асоціативних кілець з одиницею. Найчастіше цей алгоритм застосовують до поля комплексних чисел (з
) і до кілець залишків за модулем n.
Основний крок алгоритму полягає у зведенні задачі для чисел до задачі для
чисел, де
— дільник
. Нехай ми вже вміємо вирішувати задачу для
чисел. Застосуємо перетворення Фур'є до наборів
для
. Тепер покажемо, як за
обчислень розв'язати вихідну задачу. Зауважимо, що
. Вирази в дужках нам уже відомі — це
-те число після перетворення Фур'є
-тої групи. Таким чином, для обчислення кожного
потрібно
обчислень, а для обчислення всіх
—
обчислень.
Обернене перетворення Фур'є
Для оберненого перетворення Фур'є можна застосовувати алгоритм прямого перетворення Фур'є — потрібно лише використовувати замість
(або застосувати операцію комплексного спряження спочатку до вхідних даних, а потім до результату, отриманого після прямого перетворення Фур'є) і остаточний результат поділити на
.
Загальний випадок
Загальний випадок можна звести до попереднього. Нехай . Зауважимо, що
. Позначимо
. Тоді
, якщо покласти
при
.
Таким чином, задачу зведено до обчислення згортки, але це можна зробити за допомогою трьох перетворень Фур'є для елементів. Спочатку виконаємо пряме перетворення Фур'є для
і
, далі перемножимо поелементно результати і виконаємо обернене перетворення Фур'є.
Обчислення всіх i
потребує
операцій, три перетворення Фур'є виконується за
операцій, перемноження результатів перетворень Фур'є вимагає
операцій; знаючи значення згортки обчислення всіх
вимагає
операцій. Усього для дискретного перетворення Фур'є потрібно
дій для будь-якого
.
Цей алгоритм швидкого перетворення Фур'є може працювати над кільцем тільки коли відомі первісні корені з одиниці ступенів і
.
Висновок перетворення з ДПФ
Дискретне перетворення Фур'є для вектора , Що складається з
елементів, має вигляд:
елементи матриці мають вигляд:
.
Нехай парне, тоді ДПФ можна переписати таким чином:
Коефіцієнти і
можна переписати наступним чином
:
У результаті отримаємо:
Тобто дискретне перетворення Фур'є від вектора, що складається з відліків, звелося до лінійної композиції двох ДПФ від
відліків, і якщо для початкової задачі потрібно
операцій, то для отриманої композиції —
. Якщо
є степенем двійки, то цей поділ можна продовжувати рекурсивно доти, поки не дійдемо до двоточкового перетворення Фур'є, яке обчислюється за такими формулами:
Алгоритм Кулі-Тьюкі
Найбільш розповсюдженим алгоритмом розрахунку FFT є алгоритм Кулі — Тьюкі, запропонований Джеймсом Кулі та Джоном Тьюкі в 1965 році. Як з'ясувалося згодом, цей алгоритм був винайдений Карлом Гаусом ще в 1805 році.
Алгоритм заснований на рекурсивному розділенні перетворення на кожному кроці на дві частини розміром . Якщо
не ділиться на два, то робиться факторизація. Для розрахунку застосовують корені з одиниці.
Дискретне перетворення Фур'є величини 2n визначається як:
Якщо позначити вклади парних індексів як
- x'0 = x1, x'1 = x2, …, x'n-1 = x2n-2
та їхні перетворення величини n як
- f'0, …, f'n-1;
та вклади непарних індексів
- x"0 = x1, x"1 = x3, …, x"n-1 = x2n-1
та їхні перетворення величини n як
- f"0, …, f"n-1.
тоді:
Інші алгоритми ШПФ
Крім алгоритму Кулі—Тьюкі існують також інші. Для зі взаємно простими
і
, можна застосувати алгоритм Гуда—Томаса розкладу на прості дільники (Prime-Factor Algorithm), заснований на китайській теоремі про залишки, щоб факторизувати ДПФ аналогічно Кулі—Тьюкі, але без коефіцієнтів повороту.
Див. також
Джерела
- James W. Cooley, John W. Tukey: An algorithm for the machine calculation of complex Fourier series. In: Math. Comput. 19, 1965, S. 297—301.
Посилання
- Brigham, E.O. (2002), The Fast Fourier Transform, New York: Prentice-Hall
- . Цифрові сигнальні процесори TMS320C55x фірми Texas Instruments (Курс лабораторних робіт). Архів оригіналу за 8 травня 2013.
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Shvidke peretvo rennya Fur ye chasto FFT vid angl Fast Fourier Transform shvidkij algoritm obchislennya diskretnogo peretvorennya Fur ye Yaksho dlya pryamogo obchislennya diskretnogo peretvorennya Fur ye z N tochok danih potribno O N 2 arifmetichnih operacij to FFT dozvolyaye obchisliti takij zhe rezultat vikoristovuyuchi O N log N operacij Algoritm FFT chasto vikoristovuyetsya dlya cifrovoyi obrobki signaliv dlya peretvorennya diskretnih danih z chasovogo u chastotnij diapazon Osnovnij algoritmPokazhemo yak vikonati diskretne peretvorennya Fur ye za O N p 1 p n displaystyle O N p 1 cdots p n obchislen pri N p 1 p 2 p n displaystyle N p 1 p 2 cdots p n Zokrema pri N 2 n displaystyle N 2 n znadobitsya O N log N displaystyle O N log N obchislen Diskretne peretvorennya Fur ye peretvoryuye nabir chisel a 0 a n 1 displaystyle a 0 dots a n 1 v nabir chisel b 0 b n 1 displaystyle b 0 dots b n 1 takij sho b i j 0 n 1 a j e i j displaystyle b i sum j 0 n 1 a j varepsilon ij de e n 1 displaystyle varepsilon n 1 i e k 1 displaystyle varepsilon k neq 1 pri 0 lt k lt n displaystyle 0 lt k lt n Algoritm shvidkogo peretvorennya Fur ye mozhe buti zastosovanij do bud yakih komutativnih asociativnih kilec z odiniceyu Najchastishe cej algoritm zastosovuyut do polya kompleksnih chisel z e e 2 p i n displaystyle varepsilon e 2 pi i n i do kilec zalishkiv za modulem n Osnovnij krok algoritmu polyagaye u zvedenni zadachi dlya N displaystyle N chisel do zadachi dlya p N q displaystyle p N q chisel de q displaystyle q dilnik N displaystyle N Nehaj mi vzhe vmiyemo virishuvati zadachu dlya N q displaystyle N q chisel Zastosuyemo peretvorennya Fur ye do naboriv a i a q i a q p 1 i displaystyle a i a q i dots a q p 1 i dlya i 0 1 q 1 displaystyle i 0 1 dots q 1 Teper pokazhemo yak za O N p displaystyle O Np obchislen rozv yazati vihidnu zadachu Zauvazhimo sho b i j 0 q 1 e i j k 0 p 1 a k q j e k i q displaystyle b i sum j 0 q 1 varepsilon ij sum k 0 p 1 a kq j varepsilon kiq Virazi v duzhkah nam uzhe vidomi ce i mod p displaystyle i pmod p te chislo pislya peretvorennya Fur ye j displaystyle j toyi grupi Takim chinom dlya obchislennya kozhnogo b i displaystyle b i potribno O q displaystyle O q obchislen a dlya obchislennya vsih b i displaystyle b i O N q displaystyle O Nq obchislen Obernene peretvorennya Fur yeDlya obernenogo peretvorennya Fur ye mozhna zastosovuvati algoritm pryamogo peretvorennya Fur ye potribno lishe vikoristovuvati e 1 displaystyle varepsilon 1 zamist e displaystyle varepsilon abo zastosuvati operaciyu kompleksnogo spryazhennya spochatku do vhidnih danih a potim do rezultatu otrimanogo pislya pryamogo peretvorennya Fur ye i ostatochnij rezultat podiliti na N displaystyle N Zagalnij vipadokZagalnij vipadok mozhna zvesti do poperednogo Nehaj 4 N gt 2 k 2 N displaystyle 4N gt 2 k geq 2N Zauvazhimo sho b i e i 2 2 j 0 N 1 e i j 2 2 e j 2 2 a j displaystyle b i varepsilon i 2 2 sum j 0 N 1 varepsilon i j 2 2 varepsilon j 2 2 a j Poznachimo a i e i 2 2 a i b i e i 2 2 b i c i e 2 N 2 i 2 2 displaystyle bar a i varepsilon i 2 2 a i bar b i varepsilon i 2 2 b i c i varepsilon 2N 2 i 2 2 Todi b i j 0 2 N 2 i a j c 2 N 2 i j displaystyle bar b i sum j 0 2N 2 i bar a j c 2N 2 i j yaksho poklasti a i 0 displaystyle bar a i 0 pri i N displaystyle i geq N Takim chinom zadachu zvedeno do obchislennya zgortki ale ce mozhna zrobiti za dopomogoyu troh peretvoren Fur ye dlya 2 k displaystyle 2 k elementiv Spochatku vikonayemo pryame peretvorennya Fur ye dlya a i i 0 i 2 k 1 displaystyle bar a i i 0 i 2 k 1 i c i i 0 i 2 k 1 displaystyle c i i 0 i 2 k 1 dali peremnozhimo poelementno rezultati i vikonayemo obernene peretvorennya Fur ye Obchislennya vsih a i displaystyle bar a i i c i displaystyle c i potrebuye O N displaystyle O N operacij tri peretvorennya Fur ye vikonuyetsya za O N log N displaystyle O N log N operacij peremnozhennya rezultativ peretvoren Fur ye vimagaye O N displaystyle O N operacij znayuchi znachennya zgortki obchislennya vsih b i displaystyle b i vimagaye O N displaystyle O N operacij Usogo dlya diskretnogo peretvorennya Fur ye potribno O N log N displaystyle O N log N dij dlya bud yakogo N displaystyle N Cej algoritm shvidkogo peretvorennya Fur ye mozhe pracyuvati nad kilcem tilki koli vidomi pervisni koreni z odinici stupeniv 2 N displaystyle 2N i 2 k displaystyle 2 k Visnovok peretvorennya z DPFDiskretne peretvorennya Fur ye dlya vektora x displaystyle vec x Sho skladayetsya z N displaystyle N elementiv maye viglyad X A x displaystyle vec X hat A vec x dd elementi matrici A displaystyle hat A mayut viglyad a N m n exp 2 p i m n N displaystyle a N mn exp left 2 pi i frac mn N right Nehaj N displaystyle N parne todi DPF mozhna perepisati takim chinom X m n 0 N 1 x n a N m n n 0 N 2 1 x 2 n a N 2 n m n 0 N 2 1 x 2 n 1 a N 2 n 1 m displaystyle X m sum n 0 N 1 x n a N mn sum n 0 N 2 1 x 2n a N 2nm sum n 0 N 2 1 x 2n 1 a N 2n 1 m dd Koeficiyenti a N 2 n m displaystyle a N 2nm i a N 2 n 1 m displaystyle a N 2n 1 m mozhna perepisati nastupnim chinom M N 2 displaystyle M N 2 a N 2 n m exp 2 p i 2 m n N exp 2 p i m n N 2 a M n m displaystyle a N 2nm exp left 2 pi i frac 2mn N right exp left 2 pi i frac mn N 2 right a M nm a N 2 n 1 m exp 2 p i m N a M n m displaystyle a N 2n 1 m exp left 2 pi i frac m N right a M nm dd U rezultati otrimayemo X m n 0 M 1 x 2 n a M n m exp 2 p i m N n 0 M 1 x 2 n 1 a M n m displaystyle X m sum n 0 M 1 x 2n a M nm exp left 2 pi i frac m N right sum n 0 M 1 x 2n 1 a M nm dd Tobto diskretne peretvorennya Fur ye vid vektora sho skladayetsya z N displaystyle N vidlikiv zvelosya do linijnoyi kompoziciyi dvoh DPF vid N 2 displaystyle frac N 2 vidlikiv i yaksho dlya pochatkovoyi zadachi potribno N 2 displaystyle N 2 operacij to dlya otrimanoyi kompoziciyi N 2 2 displaystyle frac N 2 2 Yaksho M displaystyle M ye stepenem dvijki to cej podil mozhna prodovzhuvati rekursivno doti poki ne dijdemo do dvotochkovogo peretvorennya Fur ye yake obchislyuyetsya za takimi formulami X 0 x 0 x 1 X 1 x 0 x 1 displaystyle begin cases X 0 x 0 x 1 X 1 x 0 x 1 end cases dd Algoritm Kuli TyukiDokladnishe Algoritm Kuli Tyuki Najbilsh rozpovsyudzhenim algoritmom rozrahunku FFT ye algoritm Kuli Tyuki zaproponovanij Dzhejmsom Kuli ta Dzhonom Tyuki v 1965 roci Yak z yasuvalosya zgodom cej algoritm buv vinajdenij Karlom Gausom she v 1805 roci Algoritm zasnovanij na rekursivnomu rozdilenni peretvorennya na kozhnomu kroci na dvi chastini rozmirom N 2 displaystyle N 2 Yaksho N displaystyle N ne dilitsya na dva to robitsya faktorizaciya Dlya rozrahunku zastosovuyut koreni z odinici Diskretne peretvorennya Fur ye velichini 2n viznachayetsya yak f m k 0 2 n 1 x k e 2 p i 2 n m k m 0 2 n 1 displaystyle f m sum k 0 2n 1 x k e frac 2 pi i 2n mk qquad m 0 dots 2n 1 Yaksho poznachiti vkladi parnih indeksiv yak x 0 x1 x 1 x2 x n 1 x2n 2 ta yihni peretvorennya velichini n yak f 0 f n 1 ta vkladi neparnih indeksiv x 0 x1 x 1 x3 x n 1 x2n 1 ta yihni peretvorennya velichini n yak f 0 f n 1 todi f m k 0 n 1 x 2 k e 2 p i 2 n m 2 k k 0 n 1 x 2 k 1 e 2 p i 2 n m 2 k 1 k 0 n 1 x k e 2 p i n m k e p i n m k 0 n 1 x k e 2 p i n m k f m e p i n m f m m lt n f m n e p i n m n f m n m n displaystyle begin aligned f m amp sum k 0 n 1 x 2k e frac 2 pi i 2n m 2k sum k 0 n 1 x 2k 1 e frac 2 pi i 2n m 2k 1 0 5em amp sum k 0 n 1 x k e frac 2 pi i n mk e frac pi i n m sum k 0 n 1 x k e frac 2 pi i n mk 0 5em amp begin cases f m e frac pi i n m f m amp text m lt n 0 5em f m n e frac pi i n m n f m n amp text m geq n end cases end aligned Inshi algoritmi ShPFKrim algoritmu Kuli Tyuki isnuyut takozh inshi Dlya N N 1 N 2 displaystyle N N1 times N2 zi vzayemno prostimi N 1 displaystyle N1 i N 2 displaystyle N2 mozhna zastosuvati algoritm Guda Tomasa rozkladu na prosti dilniki Prime Factor Algorithm zasnovanij na kitajskij teoremi pro zalishki shob faktorizuvati DPF analogichno Kuli Tyuki ale bez koeficiyentiv povorotu Div takozhPeretvorennya Fur ye Diskretne peretvorennya Fur ye Algoritm Shonhage ShtrassenaDzherelaJames W Cooley John W Tukey An algorithm for the machine calculation of complex Fourier series In Math Comput 19 1965 S 297 301 PosilannyaBrigham E O 2002 The Fast Fourier Transform New York Prentice Hall Cifrovi signalni procesori TMS320C55x firmi Texas Instruments Kurs laboratornih robit Arhiv originalu za 8 travnya 2013