Быстрое преобразование Фурье
До сих пор, знакомясь с сущностью спектральных представлений, мы предполагали, что сигнал является аналоговым, т. е. описывается непрерывной функцией. На самом деле компьютер способен обрабатывать только цифровые сигналы — дискретные во времени и квантованные по уровню. Поэтому аналоговый сигнал подвергается аналого-цифровому преобразованию (АЦП). Затем с сигналом в цифровой форме выполняются все необходимые операции, в частности, спектральный анализ, причем вместо обычного спектрального преобразования производится так называемое дискретное преобразование Фурье (ДПФ). Непрерывное время и непрерывная частота заменяются на соответствующие дискретные величины, а вместо интегрирования выполняется суммирование.
Чтобы провести дискретное преобразование Фурье для последовательности из N элементов, требуется выполнить N2 операций с комплексными числами. Если длины обрабатываемых массивов цифровых отсчетов звуковых колебаний имеют порядок тысячи и больше, то использовать эти алгоритмы дискретного спектрального анализа затруднительно (особенно в реальном времени). Выходом из положения явился алгоритм быстрого преобразования Фурье (БПФ). Значительно сократить число выполняемых операций здесь удается за счет того, что обработка входного массива сводится к нахождению ДПФ массивов с меньшим числом элементов.
Приближенно можно считать, что объем вычислений по алгоритму БПФ пропорционален произведению N x log2N, где N — количество отсчетов сигнала. А если решать задачу расчета спектра "в лоб", не пользуясь алгоритмами быстрых преобразований, то объем вычислений ориентировочно будет пропорционален произведению N x N. Если бы не БПФ, то для фильтрации, спектрального анализа и синтеза сигналов не хватило бы быстродействия самого современного компьютера.
