Преобразоваине Фурье гласит что любой сигнал может быть представлен в виде суммы разных просты сигналов, что собственно и позволяет переносить сигнал из временного домена в частотный.

Прежде чем копать далеко, сначала надо немного освежить наш математический базис.

Математика
Формула Эйлера: e^{jx} = cos(x)+jsin(x) cos(x)=\frac{e^{jx}+e^{-jx}}{2} sin(x)=\frac{e^{jx}-e^{-jx}}{2j} Тригонометрия: cos(x)cos(y)=0.5(cos(x-y)+cos(x+y)) sin(x)sin(y)=0.5(cos(x-y)-cos(x+y)) cos^2(x)=0.5(1+cos(2x)) \int_{-\pi}^{\pi} cos^2(x) \,dx=\int_{-\pi}^{\pi} {(1+cos(2x))} \,dx=0.5(x+sin(x)cos(x))\Biggr|_{-\pi}^{\pi}=\pi cos(-x)=cos(x) - even\ function, sin(-x)=-sin(x) - odd\ function

OK, теоретическая база слегка подобрана, можем расписать теперь собственно само преобразование.

Преобразование фурье

Любой сигнал мы можем представить в следующем виде: f(x)=\sum_{n=0}^{\infty} a_ncos(nx) + \sum_{n=1}^{\infty} b_nsin(nx) Как получить эти коэффициенты? Используя ортогональные функции: как известно если проинтегрировать sin(x)cos(x) от -pi до +pi, результатом будет 0. Это и можем быть использовано для наших вычислений – просто умножаем на синус или косинус и смотрим нулевой ли результат. Например, если мы хотим посчитать a коэффициент то домножаем все на cos(kx), не нулевой результат будет только в случае если k = n, то бишь: \int_{-\pi}^{\pi} f(x)cos(kx) \,dx=\int_{-\pi}^{\pi} a_kcos^2(kx) \,dx=a_k\pi Коэффициенты получаются: a_k=\frac{1}{\pi}\int_{-\pi}^{\pi} f(x)cos(kx) \,dx b_k=\frac{1}{\pi}\int_{-\pi}^{\pi} f(x)sin(kx) \,dx Осталось только определить нулевые коэффициенты, b_k в любому случае нулевой, а вот a_k нет: a_0=\frac{1}{2\pi}\int_{-\pi}^{\pi} f(x) \,dx

Ну в приципе для варианта с косинусами и синусами более менее базис готов. Попробуем чтоли какую-нибудь функцию расписать.

Пример 1: Дельта функция

\delta(x)=\infty\ for\ x=0\ and\ \delta(x)=0\ for\ x<>0

Интеграл от дельта функции равен 1, это важно. Дельта функция – четная функция, значит коэффициенты с синусом тут не присутствуют, только косинус:

a_0=\frac{1}{2\pi}\int_{-\pi}^{\pi} \delta(x) \,dx=\frac{1}{2\pi}

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

a_k=\frac{1}{\pi}\int_{-\pi}^{\pi} \delta(x)cos(kx) \,dx=\frac{1}{\pi}

Что означат что вообще все коэффициенты равны 1/pi, и результат будет:

\delta(x)=\frac{1}{2\pi}+\frac{1}{\pi}(cosx + cos(2x) + cos(3x) + cos(4x) + ... )

Чем больше гармоник мы включим в этот ряд, тем ближе к идеальной форме кривая приближается:

Пример 2: Чето я даже не знаю как она по русски, знаковая плохо звучит но ладно

Эта функция равна +1 от 0 до pi, и равна -1 от -pi до 0:

Смотря на эту кривую мы можем сказать что это нечетная функция. Значит не будет косинусов плюс еще одно полезное свойство нечетное функции – мы можем интегрировать только половину периода и умножить результат на два чтобы получить правильный результат.

b_k=\frac{2}{\pi}\int_{0}^{\pi} f(x)sin(kx) \,dx=\frac{2}{\pi}\int_{0}^{\pi} sin(kx) \,dx=\frac{2}{\pi}(\frac{-cos(kx)}{k})\Biggr|_{0}^{\pi}=\frac{2}{\pi}(\frac{2}{1};\frac{0}{2};\frac{2}{3};\frac{0}{4};\frac{2}{5};...)

Теперь, подставим коэффициенты в нашу изначальную формулу Фурье:

\frac{4}{\pi}(sin(x)+sin(3x)+sin(5x)+...)=\frac{4}{\pi}\sum_{k=1}^{\infty} \frac{sin((2k-1)x)}{2k-1}

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

У меня сразу пока я ковырялся возникает вопрос, а чем будет отличаться результат если сдвинуть фазу этой функции?

Сейчас функция четная, и теперь выживают только косинусы, начнем с нулевого коэффициента а0:

Есть соблазн конечно сделать вот так:

a_0=\frac{1}{2\pi}\int_{-\pi}^{\pi} f(x) \,dx=\frac{1}{2\pi}\int_{-\pi}^{\pi} (-1) \,dx=(-x)\Biggr|_{-\pi}^{\pi}=0

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

a_{k*}=\frac{1}{\pi}\int_{-\pi}^{\frac{-\pi}{2}} f(x)cos(kx) \,dx=\frac{1}{\pi}(-\frac{sin(kx)}{k}\Biggr|_{-\pi}^{\frac{-\pi}{2}})=\frac{1}{\pi}(1;\frac{-1}{3};\frac{1}{5};...)

a_{k**}=\frac{1}{\pi}\int_{\frac{\pi}{2}}^{\pi} f(x)cos(kx) \,dx=\frac{1}{\pi}(-\frac{sin(kx)}{k}\Biggr|_{\frac{\pi}{2}}^{\pi})=\frac{1}{\pi}(1;\frac{-1}{3};\frac{1}{5};...)

a_{k***}=\frac{1}{\pi}\int_{\frac{-\pi}{2}}^{\frac{\pi}{2}} f(x)cos(kx) \,dx=\frac{1}{\pi}(\frac{sin(kx)}{k}\Biggr|_{\frac{-\pi}{2}}^{\frac{\pi}{2}})=\frac{2}{\pi}(1;\frac{-1}{3};\frac{1}{5};...)

А теперь просуммируем все части:

a_{k*}+a_{k**}+a_{k***}=\frac{4}{\pi} \sum_{k=1}^{\infty}\frac{cos((2k-1)x)}{(2k-1)(-1)^(k+1)}

Попробуем заплотить функцию:

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

Комплексное преобразование Фурье.

Как известно из формулы Эйлера любой синус или косинус можно представить в виде суммы экспонент, соответственно и преобразование Фурье также может быть представлено в комплексном виде.

f(x)=\frac{a_0}{2} + \sum_{n=1}^{\infty} (a_ncos(nx) + b_nsin(nx))=\frac{a_0}{2} + \sum_{n=1}^{\infty}\frac{a_n-jb_n}{2}e^{jnx} + \sum_{n=1}^{\infty}\frac{a_n+jb_n}{2}e^{-jnx} = \sum_{-\infty}^{\infty}c_ne^{jnx}

c_0=\frac{a_0}{2}, c_n=\frac{a_n-jb_n}{2}, c_{-n}=\frac{a_n+jb_n}{2}

Получаем три коэффициента, нулевой и два комплексно сопряженных:

c_0=\frac{1}{2\pi}\int_{-\pi}^{\pi} f(x) \,dx

Расписываем их:

c_n=\frac{1}{2\pi}\int_{-\pi}^{\pi} f(x)e^{-jnx} \,dx, n=0,\pm1,\pm2,\pm3...

Давайте снова попробуем посчитать коэффициенты для нашей функции Дирака. C_0 так и остается 0, а вот остальные считаем:

c_n=\frac{1}{2\pi}\int_{-\pi}^{\pi} f(x)e^{-jnx} \,dx=\frac{1}{2\pi}(\int_{-\pi}^{0} (-1)e^{-jnx} \,dx+\int_{0}^{\pi} e^{-jnx} \,dx)=\frac{1}{n\pi}(\frac{e^{jn\pi}+e^{-jn\pi}}{2}-1)=\frac{1}{n\pi}(cos(n\pi)-1)=\frac{1}{n\pi}((-1)^n-1)

Если n четный, то коэффициенты равны 0, если же нечетный (equal to 2k-1) то они равны:

c_{2k-1}=-\frac{2j}{(2k-1)\pi}

И само преобразование Фурье будет выглядеть так:

f(x)=sign(x)=-\frac{2j}{\pi}\sum_{k=-\infty}^{\infty}\frac{e^{j(2k-1)x}}{2k-1}

Пробуем строить в Octave, вроде как все сходится, похоже на правду:

А теперь попробуем посчитать что то еще:

f(x)=sin(8x)+sin(9x)+cos(x)

Вроде бы и все просто выглядит, бери себе функцию да вгоняю в октав и считай интегралы. Но нет, оказалось что Octave для решения интегралов использует функцию написанную еще на Фортране, quad эта функция/алгоритм именуется. Питон оказалось тоже его же юзает, а этот алгоритм не может решать комплексные интегралы. Матлаб может а октав не может, но матлаб стоит дофига а октав бесплатный :). Так что я просто в общем то знал какие гармоники проверять и тупо загнал интегралы в wolfram alpha web, там все посчиталось и эти коэффициенты и я использовал в след коде для октавы чтобы заплотить функцию:

clf;
clear;
st = pi/256;
step = -pi:st:pi;
y = (sin(8*step)+sin(9*step)+cos(step));

plot(step,y)
hold on;


n = 9;

c_p(1) = 0.5;
c_p(2) = 0;
c_p(3) = 0;
c_p(4) = 0;
c_p(5) = 0;
c_p(6) = 0;
c_p(7) = 0;
c_p(8) = -0.5*j;
c_p(9) = -0.5*j;


c_n(1) = 0.5;
c_n(2) = 0;
c_n(3) = 0;
c_n(4) = 0;
c_n(5) = 0;
c_n(6) = 0;
c_n(7) = 0;
c_n(8) = 0.5*j;
c_n(9) = 0.5*j;

y_aprox = 0;

for i = 1:n
  y_aprox = y_aprox + c_p(i)*exp(j*i*step) + c_n(i)*exp(-j*i*step);
endfor

plot(step, y_aprox)
legend("original", "approximated")
hold on
grid on

Ну и так как тут уже все гармоники и перечислены то фунцкия совпала идеально:

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