Бързо дискретно преобразуване на Фурие (FFT)

Чачба А.Н. попълни половината от всички попълнени елементи (а именно 1.1, 1.2, 1.6, 1.8, 1.9) и изгради информационна графика на алгоритъма, Костоев Р.С. е написал програма и е изпълнил поредица от изпълнения на суперкомпютър и е попълнил втората половина от елементите. И двамата след попълване коригираха грешките, открити във всички точки.

Съдържание

1.1 Общо описание на алгоритъма

Преобразуването на Фурие е едно към едно преобразуване на една функция [math] f [/ math] на реална променлива, наречена целеви сигнал, с друга функция [math] \ hat [/ math] на реална променлива, наречена изображение на Фурие, или спектъра на оригиналната функция, съгласно формулата:

Дискретното преобразуване на Фурие от своя страна е аналог на непрекъснатото преобразуване на Фурие, но за дискретен сигнал, съдържащ [math] N [/ math] проби. Той се използва широко в цифровата обработка на сигнала, теорията на вероятностите, криптографията и акустиката. Трансформацията на Фурие е обратима, а обратната трансформация има практически същата форма като директната. Преобразуването на Фурие има сложност на [math] O (N ^ 2) [/ math], но има бърза версия на преобразуването на Fourier със сложност на [math] O (N \ log) [/ math]. Тази скорост се постига чрез използването на схемата "разделяй и владей". Общият изглед на трансформацията ви позволява да разделите масива на няколко части по такъв начин, че чрез прилагане на преобразуването на Фурие към отделните му части и комбиниране на резултатите по специален начин (с помощта на ротационни фактори и повторно прилагане на трансформацията), получавате изображението на оригиналния вектор на изхода. Но поради разделянето на масива от оригиналния размер на части, общата асимптотична сложност на алгоритъма намалява.

1.2 Математическо описание на алгоритъма

Нека оригиналният сигнал има стойностите [math] x_n, \ quad n = 0, \ dots, N-1 [/ math], тогава дискретното директно преобразуване на Фурие (DFT) има формата:

[math] X_k = \ sum_ ^ x_ne ^ kn>, \ quad k = 0, \ точки, N-1 [/ math]

Ние обозначаваме [math] \ varepsilon_ = e ^> [/ math], тогава DFT може да бъде пренаписан в матрична форма:

[math] \ bar X = A \ bar x [/ math]

1.3 Изчислително ядро на алгоритъма

Нека за простота [math] N = km [/ math], след това рекурсивното изпълнение на преобразуването на Фурие, дължащо се на [math] [/ math] рекурсии на първия етап и [math] m [/ math] в последен етап, има обща сложност [math] O (Nk + Nm + km) = O (N (k + m)) [/ math] .

В случая, например [math] N = 2 ^ n [/ math], сложността на FFT е [math] O (N \ log) [/ math] .

В общия случай, когато [math] N = \ prod_ ^ np_i [/ math] сложността на FFT е [math] O (N (\ sum_ ^ np_i)) [/ math]. Тъй като рекурсията се прилага всеки път, когато се раздели един фактор, можем да заключим, че дълбочината на рекурсията на алгоритъма е [math] O (n) [/ math], където [math] n [/ math] е броят на факторите във факторизацията [математика] N [/ математика] .

На свой ред, ако числото [math] N [/ math] не е взето предвид в произведението на прости фактори (т.е. [math] N [/ math] е просто число), тогава този алгоритъм не е пряко приложим. Той е заменен от алгоритъма на Rader, който в известен смисъл намалява проблема с измерението [math] N [/ math] до подпроблема на проблема за измерението [math] N \ pm 1 [/ math] за изчисляване на конволюцията, в което също е възможно да се увеличи размерът до съставно число.

1.4 Алгоритъмна макроструктура

Макроструктурата на FFT за случая [math] N = km [/ math] е описана рекурсивно: