Шаг 4. Быстрое преобразование Фурье

В технике есть достаточное количество методик, которые производят аналоговое преобразование Фурье. Даже есть системы которые это делают мгновенно со скоростью света. Однако в цифровой технике, где применяются дискретные сигналы, использование аналоговых преобразователей зачастую не уместно. В результате, огромную популярность получил математический алгоритм, который позволяет быстро получить спектр сигнала. Алгоритм получил название «быстрое преобразование Фурье» (Fast Fourie Transform, FFT), его упрощённая схема показана на рисунке ниже.

1. Быстрое преобразование Фурье работает с дискретными сигналами. Дискретный сигнал — это набор чисел, взятых через определённый промежуток времени из значений аналогового сигнала.
2. Дискретизация сигнала выполняется по определённым правилам. Это тема отдельного разговора. Кому интересно, можно поискать статьи или книги по тематике теоремы Котельникова (Шеннона). Если каждое число из набора дискретного сигнала представить в виде бинарного кода, то получится цифровой сигнал. В конечном счёте, из аналогового сигнала длительность T получается массив из N чисел (точек).
3. Задача дискретного преобразования Фурье состоит в том, чтобы получить из массива отсчётов сигнала массив чисел спектра. Эти числа являются коэффициентами при ортогональных функциях разложения, о которых говорилось выше. Дискретную форму преобразования Фурье из аналоговой получить довольно просто. Конечный вид можно посмотреть на картинке (под номером 3).
4. С этого момента начинается непосредственно алгоритм быстрого преобразования Фурье. Алгоритм лучшим образом работает для массивов, размер которых кратен степени двойки. Поэтому, если количество отчётов отличное от степени двойки, то их увеличивают, округляя в большую сторону, с заполнением недостающих элементов нулевыми значениями. Всю последовательность разбивают на две части: чётные и нечётные отсчёты. Длины полученных последовательностей составляют N/2.
5. Несложными математическими преобразованиями показывается, что для отсчётов до N/2 справедлива формула, приведённая на рисунке (под номером 5).
6. Для значений на второй половине отсчётов: от N/2 до N можно перейти также к несложной формуле. Она получается на основании периодичности коэффициентов С. В итоге полная формула для любого коэффициента C может быть записана так, как показано на рисунке (под номером 6).
7. В данном виде алгоритм даёт некоторый выигрыш в скорости. Если из дискретного сигнала получать спектр «в лоб» (формула под номером 3 на рисунке), то на это потребуется N операций умножения на комплексное число да к тому же N сложений. И это только, чтобы получить один спектральный коэффициент, а их всего N. В конце концов, чтобы получить все коэффициенты надо выполнить N² умножений и N² сложений. Если использовать выражение, полученное выше (формула под номером 6 на рисунке), то потребуется 2(N/2)²+N умножений. Это почти в два раза меньше. Разбиением каждой последовательности, вплоть до двухэлементных массивов, можно ещё больше уменьшить количество вычислений, что показано на рисунке (под номером 7). Такая методика приводит примерно к N log₂N операциям умножения. Например, для 1024 отсчётов количество операций умножения уменьшается в 100 раз! Это значительно упрощает применение преобразования Фурье в технике.