FFT анализ

Автор: Дмитрий Михайлов
Copyright (C) Dmitry Mihaylov (Дмитрий Михайлов)
http://www.mtu-net.ru/pinetar/dm, dmitry.mih@mtu-net.ru

Большинство сложных алгоритмов цифровой обработка звука сейчас работают с частотной информацией, в то время как в подавляющем большинстве случаев информация представлена в виде зависимости амплитуды от времени (.wav файлы). Для того, чтобы обработать информацию, приходится переводить её в частотный вид, обрабатывать, а затем переводить обратно. Сама обработка здесь пока не затрагивается, описаны лишь общие для всех подобных алгоритмов проблемы разложения сигнала на частотные составляющие.

Оговорюсь сразу - с точки зрения строгой математики - почти всё, что я тут напишу, если не ошибочно, то уж наверняка очень неточно. Это скорее общие рассуждения, чем строгие математические факты, которые при надобности можно прочесть в книжках.

Для разложения сигнал в его частотные составляющие используется дискретное преобразование Фурье. В нашем случае это преобразование переводит N последовательных значений амплитуды сигнала в N/2 +1 пар коэффициентов Re[n], Im[n].

Смысл преобразования в том, что если сложить N/2 +1 функций Re[n] * Sin + Im[n] * Cos, где функции Sin и Cos с периодом, повторяющимся соответственно от 0 (константа) до N/2 раз (0, 1, 2, 3, 4 и т.д. до N/2), то с некоторой степенью точности получится исходная функция - N значений амилитуды.

По формулам приведения можно преобразовать пару коэффициентов - амплитуд Sin и Cos - в другую, более полезную нам пару - амплитуду, перед Sin A[n], и фазу этой синусоиды Ph[n].

Таким образом, можно сказать, что преобразование Фурье переводит N значений амплитуд в N/2 синусоиды (отдельные частоты) с амплитудами A[n] и фазами Ph[n], плюс еще нулевая пара коэффициентов - просто константа (Sin и Cos с постоянным нулевым аргументом), отклонение от нуля.

Еще более простой пример, финальный, совсем уж в цифрах: Пусть, например, у нас есть аудио - данные, сэмплированные в 44.1 кГц, и мы, взяв 8 значений (отдельных отсчетов), хотим получить частотное разложение этого участка. В результате у нас получится 5 пар коэффициентов - 4 синусоиды с частотами 22.05 кГц, 16.5 кГц, 11.025 кГц, 5.51 кГц, и синусоида с частотой 0 кГц - то есть константа. Взяв 8 значений, мы можем разложить исходный сигнал на 4 гармоники (синусоиды, частоты). Про константу (нулевую гармонику) на время забудем - её надо просто прибавить при обратном преобразовании, а здесь она нас не интересует.

Взяв 16 отсчетов, мы получим 8 частот. Для 1024 - 512 частот. Шаг между ними, то есть частотное разрешение, составляет, в нашем примере с 44.1 кГц, (22.05 кГц)/ (N/2), или просто (44.1 кГц)/N. Частоты идут от нуля и выше, с этим шагом.

Вычисление дискретного преобразования Фурье можно осуществлять двумя способами. Я не буду описывать ни один из них, скажу лишь, что первый, так называемый стандартный способ, состоит в том, чтобы умножать исходную функцию на синусы и косинусы, суммировать всю дискретную функцию в одно число и записывая результат в коэффициенты. Еще этот метод называют метод корреляций - если очень уж на пальцах, если функция коррелирует с искомым Sin или Cos, (имеет с ними что-то общее), то сумма всех дискретных отсчетов получившегося произведения функций говорит нам, насколько много общего у них было. Тут вас гораздо обстоятельнее просветит любой учебник по математическому анализу для первого курса ВУЗ-а :). Этот способ довольно медленный, и используется только для вычисления небольших преобразований - около десяти-двадцати точек.

Для серьезного ускорения процесса существует хитрый алгоритм - быстрое преобразование Фурье, БПФ, или по английски - FFT. FFT работает с комплексными числами и размерами преобразований, представляющими из себя степень двойки (128, .., 1024, 2048 и т.д.). Не стоит однако думать, что FFT - это что-то другое, нежели разложение Фурье. Это абсолютно то же самое, просто в сотни раз быстрее. Комплексные коэффициенты - это не что иное, как просто коэффициенты перед Cos (Im[n]), а действительные - перед Sin. В большинстве современных алгоритмов применяется FFT, поэтому это название прочно закрепилось за всеми алгоритмами, которые раскладывают сигнал на частоты.

Теперь перейдем к свойствам этих преобразований, важных нам. Термин 'размер преобразования' ('FFT size'), или просто 'размер FFT' обозначает количество точек исходной функции, с которыми мы работаем. То есть, для размера FFT в 1024 мы должны взять 1024 отсчета.

Непосредственные свойства преобразования:

• В реальных приложениях можно считать, что разложив и сложив обратно сигнал, мы никогда ничего не теряем. Это очень важное свойство.
• Разрешение по частоте зависит от размера преобразования, и составляет половину от этого размера. при FFT=512 мы получаем в результате амплитуды и фазы 256-ти равномерно расположенных частот.

Вообще говоря, перевод сигнала в частотное представление возможен только блоками (окнами). В нашем случае - FFT блоками. Мы делим исходный сигнал на блоки и говорим: в этом блоке имеются такие-то частоты. Вернее, так: его можно получить, сложив такие-то частоты.

Это очень важно понимать: FFT раскладывает функцию не на её гармоники, а на свои гармоники. Допустим, в исходной функции была лишь частота точно 100 Гц, а мы с помощью FFT раскладываем функцию в частоты 96, 99, 102, 105 Гц - как вы думаете, что получится в результате? :) Ничего полезного. FFT по прежнему будет способна полностью точно восстановить исходную функцию, однако полученный нами спектральный состав будет бестолковым:

Как видно, удачный FFT, который полностью 'попал' в искомую частоту, дал хороший, правильный, с нашей точки зрения, спектр. Неудачный же - нехороший спектр. Мы можем только догадываться, что в исходном сигнале была сильная частота в примерно 100 Гц. Важно понимать, что при синтезе обоих этих разложений мы получим в точности исходную функцию, несмотря на то, что второе разложение с нашей точки зрения и бестолково.

Вывод из вышесказанного: строго говоря, нельзя трактовать результат разложения как спектр сигнала. Разложение - это просто данные, применив к которым обратное преобразование, можно получить исходную функцию.

А теперь, для смеха и понимания, рассмотрим задачу из жизни - простейший FFT фильтр. :-) Исходные данные - как в первом примере, частота 100 Гц. Цель фильтрации - оставить все частоты выше 101 Гц. Алгоритм: обнулить в FFT разложении все частоты ниже 100 кГц включительно, а потом сложить функцию обратно. При удачном FFT разложении (см. выше) результат получается именно такой, какой нам нужно. Но спросите себя, много ли в исходных фонограммах частот, которые точно соответствуют частотам нашего FFT разложения? Да нисколько. Поэтому смотрим, что делает наш фильтр с неудачным FFT разложением: он обнуляет основную частоту, но остаются не обнуленными коэффициенты при 102, 105, 108 и т.д. Гц, которые содержали данные, необходимые для синтеза не представимой в данном разложении частоты 100 Гц. При синтезе после фильтрации эти осколки создадут нечто такое абстрактное с мощностью до 10% той частоты, которую мы фильтруем!

Мы не просто некачественно фильтруем, не просто оставляем часть исходной частоты, а вносим что-то своё, то, чего раньше в сигнале не было.

Для ликвидации этого неприятного явления применяются так называемые оконные функции. Блок перед FFT разложением помножается на сглаживающую оконную функцию. Простейшая оконная функция - Hamming, имеет примерно такой вид:

Hamming - функция

Соответственно:

Исходный блок

Блок после  Hamming функции

Поверьте, трудно объяснить, почему воздействие сглаживающей оконной функции улучшает полезность (для нас) спектрального разложения. Я потратил на понимание этого много времени, и не берусь объяснить это в двух словах. Проще просто поверить. Разговор про эту функцию зашел не для понимания её сути, а просто для того, чтобы вы представляли себе, что это такое.

Действие любой (полезной) оконной функции заключается в двух вещах: с одной стороны, она сильно стягивает неприятный эффект размазывания непопадающих в разложение частот по всему спектру:

К сожалению, второе действие - теперь и удачный FFT стал немного размазанным. Полезных результатов, впрочем, больше, поэтому оконные функции и используются. Разные функции приводят к разным результатам, и все они располагаются в некий спектр, от почти-ничего-не-делания до сильного вмешательства в спектральное разложение. Перечисляю этот спектр известных функций, от самых безобидных до ядреных: Triangular, Hanning, Hamming, Blackman, Welch (распределение Гаусса), Blackman-Harris.

Ежу понятно, что после применения любой оконной функции речь уже не идет о том, чтобы просто синтезировать сигнал обратно и получить исходную функцию. Информация с концов блока почти не используется, мы её просто не восстановим. Синтезировать, однако, можно, если пользоваться более хитрыми приемами работы. Тут мы подходим ко второму важному принципу работы с FFT, не очень обязательному при работе с полными блоками, но уже почти обязательному при работе с оконными функциями: блоки FFT обработки должны перекрываться.

Так или иначе, в FFT анализе применяются две технологии. Первая - использование результатов FFT разложения для синтеза лишь центральной части исходной функции. Например, FFT = 1024, но мы используем данные FFT преобразования для обратного синтеза лишь, к примеру, центральных 600 отсчетов, а не всех 1024-х. Соответственно, второй принцип, следующий из этого - исходные FFT блоки тоже должны перекрываться, хотя бы для того, чтобы мы могли исходно синтезировать сигнал обратно. Бывает полезно, однако, перекрывать их еще сильнее, используя усреднение результатов на стыке блоков. Это - обычно тот параметр, который отвечает за качество FFT разложения (и, соответственно, обработки). Но обработки мы пока не касаемся - это тема для отдельного большого разговора...

Продолжаем, однако, с FFT анализом. Вернемся к частотному разрешению. Что же такое, по сути, есть размер FFT блока? Рассмотрим анализ с блоком 65536. Нелишне будет напомнить, что это - более секунды для стандартной частоты дискретизации 44.1 кГц. Разрешение по частотам впечатляет - сетка частот FFT чуть менее одного герца. Одна лишь проблема - информация по частотам усреднена за более чем секунду исходного материала. Но зато, проведя такой анализ, мы можем наверняка сказать, есть ли в этом секундном сигнале частота 50 Гц, или нет - она либо ложится в нашу сетку, либо проходит настолько близко к какой-либо базовой частоте, что мы хорошо разглядим это. А если нас интересует другое? Если частота 50 Гц то появляется, то исчезает за эту секунду, скажем, 10 раз, и нас интересует именно эта динамика - что тогда? А, пардон, например удар тарелочек - мы определили его местоположение с точностью до секунды?? Молодцы мы. В анализе это не очень страшно, но при обработке с помощью FFT может привнести неприятные эффекты. Правда, не такие, о которых вы скорее всего подумали... но это не тема этой статьи.

Взять более мелкий FFT (например, 1024) чтобы увеличить разрешение по времени - не всегда выход. Причина - мы катастрофически теряем частотное разрешение. С FFT = 1024 шаг сетки частот составляет 43 Гц! Это частоты 43, 86, 132 и т.д. Гц - в такой сетке мы ни в жизни не разглядим 50 Гц, так как частоты, допустим, в 60 и 30 Гц войдут в те же гармоники нашей сетки, что и 50. Мы не сможем выделить нужную нам частоту.

Help к любой программе звукообработки скажет нам одну простую истину, которая звучит так: выигрывая в разрешении по времени, мы проигрываем в разрешении по частоте, и наоборот. Это, однако, сильно упрощенная картина. Более того, для голого анализа - даже неверная :-). Дело в том, что вышеописанная проблема имеет простое решение. Ничего не мешает нам взять, допустим, 1000 отсчетов, дополнить их еще 64536 нулями справа и подвергнуть получившуюся штуку разложению с FFT = 65536. Таким образом мы получим большое разрешение и по времени, и по частоте. Побочные эффекты? Лишь уменьшение амплитуды спектра и изменение до неузнаваемости фазовых компонент. Но мы ведь их и так не используем, мы лишь строим спектр! Амплитуду можно поправить, её изменение вычисляется. Вывод: при одном лишь анализе мы можем получить какое угодно разрешение по времени и по частоте одновременно.

Вышеописанный алгоритм можно использовать для более точного спектрального анализа малых объемов данных. Возьмите на заметку, так как этот прием почти нигде не описан.

Еще один прием, если у нас всё же имеется много информации. Перевести сигнал в меньшую частоту дискретизации - например, 8 кГц. В таком случае при FFT = 65536 мы анализируем в одном блоке аж 8 секунд информации, но разрешение по частоте получается почти 0.1 Гц - этого хватит на все практические нужды. Ну, не считая того, что максимальная частота в этом случае - 4 кГц... :) Мы как бы сузили анализируемый диапазон с 22 кГц до 4 кГц, сохранив при этом разрешение.

Однако для обработки сигналов мы не можем использовать такие трюки, поэтому для обработки вышеописанная фраза остается, по сути, аксиомой. Не нерушимым принципом, нет, но обычно - именно таким компромиссом нас всё время будут сдерживать.

Еще немного о разрешении по времени. Допустим, у нас есть блок FFT = 65536, и мы шагаем по исходным данным с огромными перекрытиями - допустим, по 1024. То есть коэффициент перекрытия составляет 64 раза. Кроме того, что это сильно неэффективно, мы всё же получаем увеличение не то чтобы разрешения во времени, но информации о расположении частот во времени. Ведь если на очередном шаге мы получили увеличение содержания частоты 50 Гц - значит, мы либо только что сошли с участка, где её не было, либо вошли в участок, где она появилась. Это неприятное 'или', делающее почти бессмысленным наше достижение :-), можно устранить, идя непрерывно с самого начала и собирая статистику.

Собственно, похожие эффекты можно наблюдать при построении сонограммы:

Сонограмма высокого разрешения (по времени)

Для каждого вертикального столбика выполняется FFT небольшим размером (около 256), результаты которого потом представляются в виде более ярких точек на местах более сильных амплитуд. Если расстояние, которое соответствует двум соседним линиям на экране, меньше размера FFT - получается перекрывающаяся сонограмма, которая уже отражает больше информации о времени, чем это возможно просто не перекрывающимися блоками. Как видно, частотные изменения во времени (горизонтальная плоскость) происходят плавно - это результат частичного перекрытия блоков FFT.

Поговорим о спектральном шуме. В принципе такого понятия в природе нет :-). Мы придумали его лишь для того, чтобы проиллюстрировать некоторые неприятные эффекты частотного анализа. Посмотрим на результат типичного FFT = 256 анализа:

Результат единственного FFT

В общем то результат как результат. Однако возьмем одну секунду информации, пройдемся по ней блоками FFT, хотя бы без перекрытия, как это делает CoolEdit, и увидим вот что:

Обратите внимание на пики около 8.5 и 11 кГц, мы никогда не разглядели бы их при одиночном анализе. То, что мешало нам разглядеть это - спектральный шум, непостоянство спектральных коэффициентов. Усредненная картина иногда гораздо более информативна. CoolEdit, однако, не использует другого, часто более полезного метода усреднения - анализ большими блокам (FFT порядка 8192), чтобы потом сгладить сам спектр. Исходно, этот спектр жутко шумный:

Однако содержит всю интересную нам информацию - холмики на 8.5 и 11 кГц, хорошо видную только при его сглаживании. К сожалению, картинку показать не могу, придется поверить на слово :-). Усреднять один спектр порой гораздо более полезно в том случае, если нас интересуют эффекты высокого частотного разрешения. Мы можем иметь всего три секунды информации и желать узнать спектральный пик с точностью в 1 Гц - то есть нам нужно FFT = 65536. Из трех секунд мы можем либо получить один FFT, усреднив (сгладив) его спектр, либо вынуждены будем посчитать с десяток FFT с перекрытием, усреднив их спектры между собой - а это уже гораздо более медленная операция.

FFT анализатор SoundForge может сглаживать спектры и усреднять их между собой, а также идти с заданными перекрытиями. CoolEdit - лишь усреднять спектры, идя без перекрытий.

Это пожалуй всё, что я счел возможным в двух словах рассказать о FFT анализе. Эта страничка, собственно, является предисловием к статьям в гораздо более практической плоскости - например, о FFT обработке (фильтрация, шумоподавление, и т.д.). Чтобы каждый раз не тыкаться в основы, они один раз описаны здесь, и более эти вопросы мною не затрагиваются.