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

[temp03]

Здравствуйте! Начал разбираться с преобразованием Фурье тут, посмотрел поиск, но никак не могу понять: есть сигнал $x_0, x_1,x_2,..$. Есть частоты 100 Герц, 200 Герц, 300 Герц, 400 Герц. Как его разложить в Фурье по этим частотам?
Насколько я понял, надо выделить каждую гармонику, а потом их все сложить (если сложить для проверки результата), должна в сумме получиться исходная амплитуда.

-- Сб ноя 10, 2012 21:24:23 --

Ответ должен быть что-то вроде:

$f(100) = 2\sin\left(\dfrac{\pi*100}{x_1}\right)$

$x_1(100)_{t_1} = f(100)(x_1 - x_1(100)_{t_0})$

Т.е. составляющая по частоте 100 от сигнала в момент $t_1$ находится от момента $t_0$

[Pphantom]

temp03 в сообщении #642682 писал(а):

Как его разложить в Фурье по этим частотам?

А чем Вас обычное определение дискретного преобразования Фурье не устраивает?

temp03 в сообщении #642682 писал(а):

Насколько я понял, надо выделить каждую гармонику, а потом их все сложить, должна в сумме получиться исходная.

Зачем?

[temp03]

Pphantom в сообщении #642692 писал(а):

Зачем?

Потому что сумма составляющих равна целому (сложить - имелось в виду для проверки верности результата)

-- Сб ноя 10, 2012 22:02:27 --

Да! И ещё вопрос если можно, мне непонятно: если на входе в преобразование $N$ элементов (или как принято - отсчётов), то и на выходе тоже $N$? Т.е. это преобразование типа $N\sim N$?

[Alex-Yu]

temp03 в сообщении #642700 писал(а):

Да! И ещё вопрос если можно, мне непонятно: если на входе в преобразование $N$ элементов (или как принято - отсчётов), то и на выходе тоже $N$? Т.е. это преобразование типа $N\sim N$?

Да. Кстати, дискретное ПФ -- это то же самое. Просто быстрое преобразование -- более эффективный алгоритм. Результат же в точности тот же самый.

[profrotter]

Полагаю речь всё же идёт о дискретном преобразовании Фурье. Рассматриваем линейное пространство периодических последовательностей $\{x_n\}_{n=0}^{N-1}$ с периодом $N$ на $0\leq n\leq N-1$ со скалярным произведением

$$(x,y)=\sum\limits_{n=0}^{N-1}x_ny^{*}_{n}.$$

Нетрудно показать, что система решетчатых функций $\varphi_k(n)=\frac {1}{N}e^{j\frac{2\pi}{N}nk},0\leq k\leq N-1$ ортонормирована на $0\leq n\leq N-1$. Тогда каждый из сигналов можно представить в виде разложения по этой системе функций:

$$x_n=\sum\limits_{n=0}^{N-1}X_k\varphi_k(n)=\frac {1}{N}\sum\limits_{n=0}^{N-1}X_ke^{j\frac{2\pi}{N}nk},$$

где $X_k=(x,\varphi_k)=\sum\limits_{n=0}^{N-1}x_ne^{-j\frac{2\pi}{N}nk}.$
Собственно последние две формулы и называются дискретным преобразованием Фурье (обратное и прямое), кратко ДПФ, и ставят в соответствие друг другу две дискретные последовательности конечной длины $\{x_n\}_{n=0}^{N-1}$ и $\{X_k\}_{k=0}^{N-1}$. Быстрое преобразование Фурье - это алгоритм, который позволяет эффективно вычислять дискретное преобразование Фурье, понижая, например при основании алгоритма 2, количество комплексных умножений с $N^2$ до $N \log_2N$.
Обратное преобразование Фурье можно рассматривать и как разложение дискретного сигнала с периодом дискретизации $T$ по системе дискретных тригонометрических функций с частотами $\omega_k=\frac{2\pi}{NT}k$, действительно, в частном случае, когда рассматривается действительный сигнал, получим для обратного ДПФ:

$$x_n=\frac {1}{N}\sum\limits_{n=0}^{N-1}|X_k|\cos\left(\frac{2\pi k}{NT}nT+\psi_k\right),$$

где $\psi_k=\arg X_k$.

[ewert]

profrotter в сообщении #642857 писал(а):

Нетрудно показать, что система решетчатых функций $\varphi_k(n)=\frac {1}{N}e^{j\frac{2\pi}{N}nk},0\leq k\leq N-1$ ортонормирована на $0\leq n\leq N-1$.

Надо сказать, что довольно трудно (они орто-, но не нормированны).

[temp03]

В общем, всем огромное спасибо за отзывы, но вы меня неправильно поняли: научите меня делать прямое/обратное преобразование Фурье из данных по частотам:
1) вход (формат данных: сигнал, частоты)
2) выход (формат данных: только сигнал? - точнее зависит от вида преобразования - либо домен частот (разбивка исходника), либо наоборот собранный сигнал - обратка);
3) Alex-Yu, почему и на входе и на выходе $N\sim N$? Ведь это абсолютно разные вещи: вход - данные, сигнал и частоты, по которым разбиваем
- выход - уже разбитые частоты, т.е. получается, что выход должен палюбому отличаться от входа.
___________________

Объясните дураку

-- Вс ноя 11, 2012 13:49:06 --

profrotter
По поводу FFT:
Да, это упрощёнка от дискретного, то бишь без интегралов и прочей лабуды. Даже, в принципе, я надеюсь! комплексной частью можно пренебречь, но! тут важно, не повлияет ли это на результат? В чём её роль при разбивке сигнала, если можно тоже поясните. Ни фига не понимаю с этим "Фурье"...

-- Вс ноя 11, 2012 13:59:04 --

В общем, я тут знакомился с "литературой", пока время было, накопал следующее:
1) берём нужную функцию, то бишь сигнал. Умножаем на $\cos\left(\pi\cdot\text{частота разбивки}\right)$, то бишь $f(x)\cos\left(\pi\omega\right)$
2) дальше как-то хитро считаем интеграл от этой лабуды (то бишь $\int\limit_t^{t+\Delta t}{f(x)\cos\left(\pi\omega\right)dx}$) на интервале $[t, t+\Delta t]$ - я не понял как, кто может поясните. Просто суммируем? Тогда что суммируем?
Это будет реальная часть
3) потом то же самое проделываем с синусом - imaginary (мнимая часть)
Потом складываем.

Результат - то что нам нужно, то бишь Фурье сигнала по $\omega$.
Далее повторяем по всем частотам. Верно?

[profrotter]

$$(\varphi_k,\varphi_m)=\sum\limits_{n=0}^{N-1}\varphi_k(n)\varphi_m^{*}(n)=\frac {1}{N^2}\sum\limits_{n=0}^{N-1}e^{j\frac{2\pi}{N}nk}e^{-j\frac{2\pi}{N}nm}=\frac {1}{N^2}\sum\limits_{n=0}^{N-1}e^{j\frac{2\pi}{N}n(k-m)}$$

При $m=k$ $(\varphi_k,\varphi_m)=||\varphi_k||^2=\frac {1}{N^2}N=\frac {1}{N}$. Ну да ошибся - не ортонормированы.
При $m\neq k$ с учётом формулы частичной суммы геометрической прогрессии получим

$$(\varphi_k,\varphi_m)=\frac {1}{N^2}\sum\limits_{n=0}^{N-1}e^{j\frac{2\pi}{N}n(k-m)}=\frac {1}{N^2}\frac {1-e^{j\frac{2\pi}{N}(k-m)N}}{1-e^{j\frac{2\pi}{N}(k-m)}}=0$$

.

Никакой комплексной частью пренебрегать нельзя. Честно говоря вопросы не понятны.

[temp03]

profrotter в сообщении #642877 писал(а):

Честно говоря вопросы не понятны.

temp03 в сообщении #642873 писал(а):

научите меня делать прямое/обратное преобразование Фурье из данных по частотам:

Что конкретно непонятно? Как научить непонятно?

-- Вс ноя 11, 2012 14:06:43 --

profrotter в сообщении #642877 писал(а):

Никакой комплексной частью пренебрегать нельзя.

Почему нельзя? я видел в интернете варианты (рабочие), где можно. Нулями её забивают.

[Maslov]

temp03 в сообщении #642700 писал(а):

Да! И ещё вопрос если можно, мне непонятно: если на входе в преобразование $N$ элементов (или как принято - отсчётов), то и на выходе тоже $N$? Т.е. это преобразование типа $N\sim N$?

Если у Вас на входе 15 отсчетов, снятых с периодом 1 с, то в результате ДПФ Вы получите разложение этого сигнала на составляющие с периодами 0 с, 1 с, 2 с, ..., 14 с.

[temp03]

Maslov в сообщении #642887 писал(а):

Если у Вас на входе 15 отсчетов, снятых с периодом 1 с, то в результате ДПФ Вы получите разложение этого сигнала на составляющие с периодами 0 с, 1 с, 2 с, ..., 14 с.

Так! Интересно. Спасибо. Ещё раз: на входе 256 отсчётов, т.е. $2^8$, снятых с $10$ килоГерц (это сигнал), т.е. я получу 256 составляющих ??? Зачем мне столько, мне нужно по 4 частотам.

Т.е. мне потом ещё результаты Фурье обрабатывать, чтобы получить заданные 4 частоты, или как ? Или потом просто надо выделить из полученного в результате FFT домена частот - 4 штуки, скажем: 3с, 7с, 9с, 11с - т.е. которые мне нужны?

Всё равно не вижу связи между периодами и частотами, ведь это разные вещи

[Maslov]

В Вашем случае ДПФ даст разложение по частотам

$0, 1\cdot \dfrac {10000}{256}, 2\cdot \dfrac {10000}{256}, ..., 254\cdot \dfrac {10000}{256}, 255\cdot \dfrac {10000}{256}$ (0 Гц, 39.0625 Гц, 78.1250 Гц, ...)

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

temp03 в сообщении #642873 писал(а):

комплексной частью можно пренебречь

В результате ДПФ получается набор комплексных коэффициентов. Что Вы называете комплексной частью?

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

temp03 в сообщении #642890 писал(а):

Всё равно не вижу связи между периодами и частотами, ведь это разные вещи

$T = \dfrac 1 f$, где $f$ - частота в герцах, или $T = \dfrac {2 \pi} \omega$, где $\omega$ - круговая частота.

[_Ivana]

Интернет по данной теме велик и обширен, но могу порекомендовать почитать http://www.dsplib.ru/content/dft/dft.html и другие статьи с того сайта. Человек старался, писал - почему бы не прочитать

[Alex-Yu]

temp03 в сообщении #642873 писал(а):

3) Alex-Yu, почему и на входе и на выходе $N\sim N$? Ведь это абсолютно разные вещи: вход - данные, сигнал и частоты, по которым разбиваем
- выход - уже разбитые частоты, т.е. получается, что выход должен палюбому отличаться от входа.

Во-первых, не имеет смысла брать частоты выше половинной частоты дискретизации (теорема Котельникова), там просто периодически повторяется все то же самое. Во-вторых, сигнал на КОНЕЧНОМ временном отрезке разлагается не в интеграл Фурье, а в ряд Фурье. Так что набор частот дискретный. Если дискретный набор чисел обрезать сверху, то получится конечный набор. В общем если это внимательно проанализировать, получается отображение N чисел в N других чисел. Точнее так для комплексного входного сигнала. Ну а при действительном есть еще соотношение, что при отрицательной частоте фурье-образ равен комплексному сопряжению от такой же положительной частоты. Что уменьшает число независимых чисел в два раза.

-- Вс ноя 11, 2012 18:36:38 --

temp03 в сообщении #642890 писал(а):

Так! Интересно. Спасибо. Ещё раз: на входе 256 отсчётов, т.е. $2^8$, снятых с $10$ килоГерц (это сигнал), т.е. я получу 256 составляющих ??? Зачем мне столько, мне нужно по 4 частотам.

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

[Maslov]

Alex-Yu в сообщении #642958 писал(а):

Во-вторых, сигнал на КОНЕЧНОМ временном отрезке разлагается не в интеграл Фурье, а в ряд Фурье.

Мы же вроде про дискретные сигналы говорим.

Есть четыре преобразования:
непрерывный сигнал в непрерывный спектр - преобразование Фурье
непрерывный сигнал в дискретный спектр - ряд Фурье
дискретный сигнал в непрерывный спектр - Discrete-time Fourier transform
дискретный сигнал в дискретный спектр - ДПФ