В прошлый раз мы остановились на том, что при помощи преобразования Фурье разные сложные функции и описываемые ими сигналы (звуковые, электрические и т.д.) можно раскладывать на сумму простых и понятных синусов и косинусов. Но вот незадача: работа эта неблагодарная и тяжелая, т.к. синусов-косинусов этих может потребоваться тысячи. Математики 19-го столетия страдали.
Так бы это уныние и длилось, но тут внезапно наступил век двадцатый и на выручку пришел научно-технически прогресс в виде этих ваших цифровых технологий. С их помощью сигнал можно оцифровать и из непрерывной кривой-загогулины (с которой компьютер не справляется) получить набор точек (хотя и довольно большой) для компьютера подъемный.
Это оказалось очень кстати, т.к. в начале 20-го в. появлялись работы по дискретному Фурье преобразованию, как раз подходящего для работы с дискретными же (точечными), а не непрерывными функциями.
Тем не менее алгоритм оставался все еще несовершенным, для N точек требовалось N^2 операций обсчета, что надолго подгружало маломощные компьютеры середины 20-го века. Нужно было что-то еще.
На помощь пришли американские математики Джеймс Кули и Джон Тьюки, которые в 1965 г. опубликовали алгоритм быстрого преобразования Фурье – его величество FFT. Интересно, что похожие идеи предлагал Карл Гаусс еще в начале 19-го века.
Какие операции требовалось провести в обычном дискретном Фурье преобразовании? Нужно было, чтобы каждая точка «провзаимодействовала» со всеми точками в наборе. Это и было очень долго. В FFT поступили хитрее. Сперва разбили все точки на два ряда: четные и нечетные. Затем каждый из этих рядов опять на два ряда четных и нечетных и так далее.
С каждым таким биением длина ряда укорачивалась и в пределе получалось большое количество рядков, состоящих из пар точек. «Взаимодействие» проводили не «всех со всеми», а то только внутри каждой из пар после чего объединяли результат и получали ответ такой же точный как при помощи дискретного преобразования только быстрее.
Сегодня FFT применяется повсюду для преобразования сигнала, например, в том же Шазаме, который мы недавно обсуждали. Другой наглядный пример – эквалайзеры в музыкальных установках. А все началось с абстрактной на первый взгляд математики больше 200 лет назад.