2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Быстрое преобразование Фурье FFT
Сообщение10.11.2012, 20:16 
Заблокирован


16/06/09

1547
Здравствуйте! Начал разбираться с преобразованием Фурье тут, посмотрел поиск, но никак не могу понять: есть сигнал $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$

 Профиль  
                  
 
 Re: Быстрое преобразование Фурье FFT
Сообщение10.11.2012, 20:29 
Заслуженный участник


09/05/12
25179
temp03 в сообщении #642682 писал(а):
Как его разложить в Фурье по этим частотам?

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

temp03 в сообщении #642682 писал(а):
Насколько я понял, надо выделить каждую гармонику, а потом их все сложить, должна в сумме получиться исходная.

Зачем?

 Профиль  
                  
 
 Re: Быстрое преобразование Фурье FFT
Сообщение10.11.2012, 20:36 
Заблокирован


16/06/09

1547
Pphantom в сообщении #642692 писал(а):
Зачем?
Потому что сумма составляющих равна целому (сложить - имелось в виду для проверки верности результата)

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

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

 Профиль  
                  
 
 Re: Быстрое преобразование Фурье FFT
Сообщение11.11.2012, 01:34 
Заслуженный участник


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


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

 Профиль  
                  
 
 Re: Быстрое преобразование Фурье FFT
Сообщение11.11.2012, 12:03 
Модератор
Аватара пользователя


16/02/11
3788
Бурашево
Полагаю речь всё же идёт о дискретном преобразовании Фурье. Рассматриваем линейное пространство периодических последовательностей $\{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$.

 Профиль  
                  
 
 Re: Быстрое преобразование Фурье FFT
Сообщение11.11.2012, 12:28 
Заслуженный участник


11/05/08
32166
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$.

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

 Профиль  
                  
 
 Re: Быстрое преобразование Фурье FFT
Сообщение11.11.2012, 12:46 
Заблокирован


16/06/09

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

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

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

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

-- Вс ноя 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$.
Далее повторяем по всем частотам. Верно?

 Профиль  
                  
 
 Re: Быстрое преобразование Фурье FFT
Сообщение11.11.2012, 12:59 
Модератор
Аватара пользователя


16/02/11
3788
Бурашево
$$(\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$$.

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

 Профиль  
                  
 
 Re: Быстрое преобразование Фурье FFT
Сообщение11.11.2012, 13:05 
Заблокирован


16/06/09

1547
profrotter в сообщении #642877 писал(а):
Честно говоря вопросы не понятны.

temp03 в сообщении #642873 писал(а):
научите меня делать прямое/обратное преобразование Фурье из данных по частотам:
Что конкретно непонятно? Как научить непонятно?

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

profrotter в сообщении #642877 писал(а):
Никакой комплексной частью пренебрегать нельзя.
Почему нельзя? я видел в интернете варианты (рабочие), где можно. Нулями её забивают.

 Профиль  
                  
 
 Re: Быстрое преобразование Фурье FFT
Сообщение11.11.2012, 13:14 
Заслуженный участник


09/08/09
3438
С.Петербург
temp03 в сообщении #642700 писал(а):
Да! И ещё вопрос если можно, мне непонятно: если на входе в преобразование $N$ элементов (или как принято - отсчётов), то и на выходе тоже $N$? Т.е. это преобразование типа $N\sim N$?
Если у Вас на входе 15 отсчетов, снятых с периодом 1 с, то в результате ДПФ Вы получите разложение этого сигнала на составляющие с периодами 0 с, 1 с, 2 с, ..., 14 с.

 Профиль  
                  
 
 Re: Быстрое преобразование Фурье FFT
Сообщение11.11.2012, 13:17 
Заблокирован


16/06/09

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

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

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

 Профиль  
                  
 
 Re: Быстрое преобразование Фурье FFT
Сообщение11.11.2012, 14:12 
Заслуженный участник


09/08/09
3438
С.Петербург
В Вашем случае ДПФ даст разложение по частотам

$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$ - круговая частота.

 Профиль  
                  
 
 Re: Быстрое преобразование Фурье FFT
Сообщение11.11.2012, 14:19 


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

 Профиль  
                  
 
 Re: Быстрое преобразование Фурье FFT
Сообщение11.11.2012, 14:28 
Заслуженный участник


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



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

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

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



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

 Профиль  
                  
 
 Re: Быстрое преобразование Фурье FFT
Сообщение11.11.2012, 14:53 
Заслуженный участник


09/08/09
3438
С.Петербург
Alex-Yu в сообщении #642958 писал(а):
Во-вторых, сигнал на КОНЕЧНОМ временном отрезке разлагается не в интеграл Фурье, а в ряд Фурье.
Мы же вроде про дискретные сигналы говорим.

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 24 ]  На страницу 1, 2  След.

Модераторы: photon, whiterussian, profrotter, Jnrty, Aer, Парджеттер, Eule_A, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group