Приложение 2.А. Быстрое преобразование Фурье
Кратко рассмотрим БПФ. Более подробные сведения читатель может найти в литературе по обработке сигналов. В качестве отправного пункта воспользуемся
зуемся уравнением (2.3), заменив в нем показательную функцию на 
как это сделано в разд. 2.2:
Введем новый индекс суммирования 
который пробегает значения от 0 до 
и связан с прежним индексом суммирования к следующими соотношениями:
Тогда уравнение 
можно переписать следующим образом:
Пусть далее 
отмегим, что 
. В таком случае уравнение 
можно 
где 
— новые функции, полученные в результате разделения точек, соответствующих четным и нечетным значениям аргумента. Две суммы, входящие в уравнение 
очень сильно напоминают фурье-преобразования функций, заданных М отсчетами, с тем отличием, что в формулах, определяющих эти фурье-преобразования, индекс суммирования и пробегает значения от 0 до 
Обратим внимание, что
поскольку 
Таким образом, по 
значениям фурье-образа функции 
можно тривиально найти 
значений. Следовательно, для вычисления фурье-преобразования справедливо следующее рекуррентное соотношение:
Соотношение 
является основой БПФ. Во-первых, соответствующая вычислительная процедура легко программируется. Запишем ее в виде алгоритма 
