Я хочу рассказать о преобразовании Фурье. Это очень большое и интересное понятие. Я хочу дать базовое и крепкое представление, без двусмысленностей и неопределенности. Поэтому мы не будем трогать непрерывное преобразование Фурье, обобщенные функции и всю хитрую математику.
Начнем с простого. Для начала разберемся с тем, что такое базис. Здесь будет немного математики, но в ней, уверяю, нужно хорошенько разобраться.
Базис - это основа. Базис - это то, через что можно выразить всё остальное. В математическом смысле, базис - это набор некоторых элементов (b1 ... bn), такие, что любой другой элемент выражается через них:
a = a1b1 + ... + anbn
Причем сами базисные элементы при этом друг через друга не выражаются. Возьмём к примеру, трехмерное пространство:
Каждый элемент в этом пространстве имеет координаты, поэтому можно записывать его в виде (a,b,c). Элементы (1,0,0), (0,1,0) и (0,0,1) являются базисом, потому что любой элемент раскладывается следующим образом:
(a, b, c) = a(1, 0, 0) + b(0, 1, 0) + c(0, 0, 1)
Вполне очевидно, что эти базисные элементы нельзя представить друг через друга, поскольку у каждого своя собственная координата и сколько не складывай на другую координату не перейдешь. Но оказывается, что бывают и другие базисы для трехмерного пространства. Например, такой: (1,0,1), (0,1,1), (1,1,0). С ними уже по-сложнее. Уже не так очевидно, что один через другой не выражается. (Для более детальной информации по базисам и пространствам стоит полистать курс линейной алгебры, который читают в любом техническом вузе на первом курсе.)
Теперь подумаем: как можно произвольный элемент разложить в базис? Если посмотреть на картинку, то понятно - нужно спроектировать этот элемент на все оси, тогда получим координаты. А как проектировать если базис какой-то другой? Для этого есть простая процедура связанная со скалярным проиведением векторов. Но сначала вспомним что такое скалярное произведение:
(a, b, c)(x, y, z) = ax + by + cz;
Далее, чтоб не запутаться, элементы пространства буду писать полужирным, а просто числа обычным шрифтом. Скалярное произведение тем хорошо, что для произвольных элементов v1, v2 и v3 выполняется следующее:
v1(v2 + v3) = v1v2 + v1v3
Если v1v2 = 0, то есть скалярное произведение двух элементов равно нулю, то мы в таком случае говорим, что эти элементы ортогональны (т.е. угол между ними 90o).
Так вот. Пусть мы построили базис из трех элементов b1, b2 и b3, и эти элементы ортогональны между собой. Т.е. справедливо следующее:
b1b2 = 0
b1b3 = 0
b2b3 = 0
Это т.н. ортогональный базис. Тогда для того чтобы узнать коэффициенты при разложении в ортогональный базис, нужно вычислить скалярные произведения этого элемента на базисные элементы. Действительно, допустим наш элемент раскладывается в базис вот так:
v = x b1 + y b2 + z b3
Но мы этого еще не знаем. У нас есть просто элемент v и три базисных элемента. И еще мы умеем скалярно перемножать. Что нам делать? Как узнать x, y и z? А вот так:
vb1 = (x b1 + y b2 + z b3) b1 = x b1b1
vb2 = (x b1 + y b2 + z b3) b2 = y b2b2
vb3 = (x b1 + y b2 + z b3) b3 = z b3b3
При раскрытии скобок все остальные произведения превратились в ноль (помните про ортогональность?). А значения b1b1, b2b2 и b3b3 мы можем с легкостью вычислить. Поэтому коэффициенты мы можем явно найти:
x = vb1 / b1b1
y = vb2 / b2b2
z = vb3 / b3b3
Эти три формулы нам пригодятся для дискретного преобразования Фурье.
Подведём итоги.
Перейдем теперь к звуку. Как я уже говорил, это последовательность чисел. Сейчас мы рассмотрим периодические сигналы. Это означает, что звук - наша последовательность чисел - будет повторяться. Иными словами, звук - это повторение одной и той же последовательности из n элементов. Теория Фурье сообщает нам хорошую новость: любой периодический сигнал выражается через базовые периодические.
Все периодические сигналы с периодом n - это пространство. Один сигнал - это элемент этого пространства. Базовые периодические - это базис. Всё через него выражается. Каждый сигнал определяется n числами, поэтому будем записывать этот сигнал так: (a1 ... an) - как последовательность отсчетов внутри одного цикла:
Для начала определим базисы.
В случае, если n - нечетно. То есть n = 2k + 1. Базис:
Иными словами, это постоянная и гармонические колебания укладывающиеся в период целое количество раз.
В случае, если n - четно. То есть n = 2k. Базис:
Как видите, в таком случае предпоследний элемент пропадает. Почему? Это легкое упражнение, которое вы можете выполнить самостоятельно.
Таким образом, каждый сигнал (a1 ... an) раскладывается в таком базисе:
(a1 ... an) = f1 b1 + ... + fn bn;
Значит, каждый периодический сигнал имеет два представления: одно - это (a1 ... an), а другое - это (f1 ... fn). Переход от одного к другому и есть преобразование Фурье.
(a1 ... an) -> (f1 ... fn) Прямое преобразование Фурье.
(f1 ... fn) -> (a1 ... an) Обратное преобразование Фурье.
Самое замечательное, что построенный базис ортогональный, относительно вот такого вот скалярного произведения:
(c1 ... cn)(d1 ... dn) = c1d1 + ... + cndn
А это означает, что вы теперь можете вычислять прямое преобразование Фурье. Для этого нужно вычислить все b1b1, ... ,bnbn. А затем пользуясь формулами в конце прошлой главки про базис и формулой скалярного произведения, определить коэффициенты.
Обратное преобразование Фурье - для этого нужно просто просуммировать базисные элементы с нужными коэффициентами.
Для дискретного преобразования Фурье необходимо сделать порядка n2 умножений. Если вы берете для разложения участок в 5000 отсчетов (около десятой части секунды), то вам необходимо будет сделать около 250 000 000 операций умножения. Однако, для десятой части секунды для современных компьютеров - это практически вся их вычислительная мощность. Поэтому дискретное преобразование хорошо для понимания, но плохо для использования.
В следующий раз я расскажу на чем здесь можно сэкономить, конкретно про быстрое преобразование Фурье.