Рис 2.Дискретное представление непрерывной функции

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

Рис.3 .Быстрое преобразование Фурье

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

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

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

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

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

Удачный FFT		Неудачный FFT
Частоты	Коэффициенты (амплитуда)	Частоты	Коэффициенты (амплитуда)
95	0	91	0.04
96	0	93	0.11
97	0	96	0.14
98	0	99	0.85
99	0	102	0.19
100	1	105	0.15
101	0	108	0.09
102	0	111	0.02
103	0	114	0.001

Как видно, удачный FFT, который полностью 'попал' в искомую частоту, дал хороший,

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

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

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

нисколько. Поэтому смотрим, что делает наш фильтр с неудачным FFT разложением: он

обнуляет основную частоту, но остаются не обнуленными коэффициенты при 102, 105, 108 и т.д.Гц, которые содержали данные, необходимые для синтеза не представимой в данном разложении частоты 100 Гц. При синтезе после фильтрации эти осколки создадут нечто такое абстрактное с мощностью до 10% той частоты, которую мы фильтруем! Мы не просто некачественно фильтруем, не просто оставляем часть исходной частоты, а вносим что-то своё, то, чего раньше в сигнале не было.

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

Рис.4.Простейшая оконная функция

Соответственно, исходный блок:

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

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

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

Неудачный FFT		Неудачный FFT с Hamming
Частоты	Коэффициенты (амплитуда)	Частоты	Коэффициенты (амплитуда)
91	0.04	91	0.0011
93	0.11	93	0.013
96	0.14	96	0.021
99	0.85	99	0.93
102	0.19	102	0.14
105	0.15	105	0.011
108	0.09	108	0.003
111	0.02	111	0.0015
114	0.001	114	0.0001

К сожалению, второе действие - теперь и удачный 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 Гц - значит, мы либо только что сошли с участка, где её не было, либо вошли в участок, где она появилась. Это неприятное 'или', делающее почти бессмысленным наше достижение , можно устранить, идя непрерывно с самого начала и собирая статистику.

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

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

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

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

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

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

Рис.7.Анализ «одной секунды».

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

Рис.8.Исходный спектр.

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

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

Таким образом, любое, даже самое сложное по форме колебание (например, человеческий голос), можно представить суммой простейших синусоидальных колебании определенных частот и амплитуд. И наоборот, сгенерировав различные колебания и наложив их друг на друга (смикшировав, смешав), можно получить различные звуки.