Быстрое преобразование Фурье
До сих пор, знакомясь с сущностью спектральных представлений, мы предполагали, что сигнал является аналоговым, т. е. описывается непрерывной функцией. На самом деле компьютер способен обрабатывать только цифровые сигналы — дискретные во времени и квантованные по уровню. Поэтому аналоговый сигнал подвергается аналого-цифровому преобразованию (АЦП). Затем с сигналом в цифровой форме производятся все необходимые операции, в частности, спектральный анализ, причем вместо обычного спектрального преобразования производится так называемое дискретное преобразование Фурье (ДПФ). Непрерывное время и непрерывная частота заменяются на соответствующие дискретные величины, а место взятия интегралов осуществляется суммирование.
Однако на практике мало кто пользуется ДПФ. Дело в том, что для вычисления дискретного преобразования Фурье последовательности N элементов требуется выполнить N2 операций с комплексными числами. Если длины обрабатываемых массивов цифровых отсчетов звуковых колебаний имеют порядок тысячи и более, то использовать эти алгоритмы дискретного спектрального анализа затруднительно (особенно в реальном времени). Выходом из положения явился алгоритм быстрого преобразования Фурье (БПФ). Значительно сократить число выполняемых операций здесь удается за счет того, что обработка входного массива сводится к нахождению ДПФ-массивов с меньшим числом элементов. Для метода БПФ существенно, что число отсчетов составляет целую степень двойки (N =2p, где р — целое число). Это обусловлено тем, что одной из операций, входящей в алгоритм БПФ, является последовательное деление интервала вычисления ДПФ на две части. Поэтому точное вычисление БПФ возможно лишь в случае, когда число отсчетов в сигнале равно 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, IP. Если данное условие не выполняется, приходится дополнять сигнал некоторым количеством отсчетов, имеющих нулевое значение. Например, для выполнения БПФ сигнал, содержащий 60 значащих отсчетов, нужно дополнить четырьмя нулевыми отсчетами. Конечно, приписка отсчетов равноценна изменению сигнала, что приводит к возникновению дополнительной погрешности вычисления спектра. Но, как правило, погрешность невелика и, учитывая заметное повышение скорости расчетов, с ней можно смириться.
Приближенно можно считать, что объем вычислений по алгоритму БПФ пропорционален произведению N х log2N, где N — количество отсчетов сигнала. А если решать задачу расчета спектра "в лоб", не пользуясь алгоритмами быстрых преобразований, то объем вычислений ориентировочно будет пропорционален произведению N х N. Если бы не БПФ, то для фильтрации, спектрального анализа и синтеза сигналов не хватило бы быстродействия самого современного компьютера. Не верится? Давайте прикинем. Очень скоро вы узнаете, что в примере установок параметров, соответствующих рис. 1.27, сигнал представлен 4096-ю отсчетами. Тогда для БПФ: 4096 х log24096 = 4096 х 12 = 49152, а для "небыстрого" алгоритма: 4096 х 4096 = 16777216. Отношение 16777216/49152 = 341,(3) приблизительно равно выигрышу во времени выполнения вычислений по алгоритму БПФ.
О чем говорят эти цифры? Пусть на вашем компьютере для расчета фильтра по алгоритму БПФ требуется 10 секунд. Та же самая задача при использовании обычного алгоритма спектрального анализа заняла бы почти час. Какое уж тут может быть творчество! Либо, чтобы все-таки уложиться в 10 секунд, потребовался бы компьютер, работающий в 341 раз быстрее, чем ваш.
При расчете спектра протяженных сигналов приходится не дополнять отсчеты до целой степени двойки, а поступать совершенно наоборот: использовать для вычислений не все отсчеты сигнала, а, к примеру, каждый сотый, тысячный, десятитысячный. Судите сами. В одной секунде оцифрованного стереофонического звука при частоте дискретизации 44,1 кГц содержится 88200 отсчетов. Тогда в одной минуте — 5292000, а в 4 минутах (типичная длительность композиции) — 21168000 отсчетов. В качестве примера средствами Cubase SX мы проанализировали спектр 4-минутной композиции. На нашем компьютере для этого понадобилось 10 секунд. При этом было выбрано число отсчетов, равное 4096 (что для анализатора спектра Cubase SX в два раза меньше максимального). Если бы программа использовала для вычислений все отсчеты, которыми представлена композиция (более 21 миллиона отсчетов), то для решения этой задачи ей потребовалось бы непрерывно работать больше 14 часов.
Существуют аудиоредакторы, позволяющие не только анализировать текущий и мгновенный спектры, но также и редактировать звуковой сигнал, представленный в спектральной форме. Примером подобной программы может служить аудиоредактор Cool Edit Pro 2. Конечно, от такой универсальной программы, как Cubase SX, нельзя требовать, чтобы она позволяла обращаться со спектром так же свободно, как и специализированный звуковой редактор. Вместе с тем, в Cubase SX возможности для проведения спектрального анализа все же имеются.
