2014 dxdy logo

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

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


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

Если Вы зададите новый вопрос в существующей теме, то в случае нарушения оформления или других правил форума Ваше сообщение и все ответы на него могут быть удалены без предупреждения.

Не ищите на этом форуме халяву, правила запрещают участникам публиковать готовые решения стандартных учебных задач. Автор вопроса обязан привести свои попытки решения и указать конкретные затруднения.

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Дискретное преобразование фурье и свертка
Сообщение24.09.2014, 13:44 


20/09/14
17
Здравствуйте, начал интересоваться численными методами нахождениями(циклической) свертки сигналов на основе ДПФ.Для опробации взял два треугольных сигнала(прямой и перевернутый, например
$\tt {a}=0, 0.2, 0.4, 0.6, 0.8, 1, 0.8, 0.6, 0.4, 0.2, 0;  \tt {b}=1, 0.8, 0.6, 0.4, 0.2, 0, 0.2, 0.4, 0.6, 0.8, 1$.При вычислении свертки двух сигналов размерностей $N_1$и $N_2$ на выходе получается сигнал размерностью $N_1+N_2-1$.При помощи ДПФ оба сигнала подгоняются под одну размерность $ \tt {N}$, свертка ищется как $$ c_k = \sqrt N \sum_{n=0}^{N-1} (A_k B_k) e^{- \frac {2\pi i}{kn}kn},  k=0..N-1$$
,где $A_k, B_k$- ДПФ сигналов $ \tt{a}$ и  $\tt{b}$.(В маткаде записывается $c=\sqrt N  \bold {icfft(\overrightarrow{\bold {cfft(a)cfft(b)}}})$. Но в результате этого получается сигнал размерности $\tt{N}$, и это только половина свертки.В случае симметричных треугольных сигналов результат легко достроить до целого,но как быть в других случаях?Пробовал в маткаде способ($ \tt {fft,ifft}$) , где входные данные должны иметь размерность $2^L$(с прореживанием по времени?),дописывая нули до конца, но тогда результат вообще очень сильно искажается(Нули портят свертку?)

 Профиль  
                  
 
 Posted automatically
Сообщение24.09.2014, 20:28 
Супермодератор
Аватара пользователя


20/11/12
5728
 i  Тема перемещена из форума «Помогите решить / разобраться (М)» в форум «Карантин»
Причина переноса: формулы не оформлены $\TeX$ом

Logrus
Наберите все формулы и термы $\TeX$ом.
Инструкции по оформлению формул здесь или здесь (или в этом видеоролике).
См. также тему Что такое карантин, и что нужно делать, чтобы там оказаться.
После исправлений сообщите в теме Сообщение в карантине исправлено, и тогда тема будет возвращена.

 i  Тема перемещена из форума «Карантин» в форум «Помогите решить / разобраться (М)»
Вернул

 Профиль  
                  
 
 Re: Дискретное преобразование фурье и свертка
Сообщение24.09.2014, 20:34 


07/08/14
4231
а под размерностью сигнала что понимается?
количество отсчетов?

 Профиль  
                  
 
 Re: Дискретное преобразование фурье и свертка
Сообщение24.09.2014, 20:39 


20/09/14
17
upgrade
ну да, количество точек разбития(дискретизация), а так сигнал одномерный

 Профиль  
                  
 
 Re: Дискретное преобразование фурье и свертка
Сообщение24.09.2014, 21:40 


07/08/14
4231
Из сообщения лично я понял, что в первом случае вы делаете свертку двух сигналов, а во втором ищете спектр одного из них, поскольку количество данных меньше степени двойки допмсываете нули. И не понимаете что спектр симметричный (потому и половину показывает, вторая половина такая же)

-- 24.09.2014, 21:45 --

"дискретизация" это частота шага , а не количество шагов

 Профиль  
                  
 
 Re: Дискретное преобразование фурье и свертка
Сообщение24.09.2014, 21:50 


20/09/14
17
upgrade
То, что спектр симметричный, я понимаю, я как раз говорю, что свертка 2 сигналов размера $\tt {N}$ должна быть размера $\tt {2N-1}$,и в общем случае( если оба сигнала не симметричны) несимметричная, тогда как вычисление через ДПФ (как часто и делают) дает только первые $\tt {N}$ значений(так как ДПФ и обратное ДПФ не меняют, в отличии от свертки, размер сигнала), и я не пойму, как находить вторую половину свертки?А дописывание нулей в конце сигнала вообще, похоже, в корне меняет результат(хотя при прямом вычислении свертки такого быть не должно)

 Профиль  
                  
 
 Re: Дискретное преобразование фурье и свертка
Сообщение24.09.2014, 22:16 


07/08/14
4231
Вот ссылка о свертках сигналов
http://www.dsplib.ru/content/conv/conv.html
Вы так как по ссылке размерность определяете для сигналов, когда их спектры ищете?

 Профиль  
                  
 
 Re: Дискретное преобразование фурье и свертка
Сообщение24.09.2014, 22:31 


20/09/14
17
Да, судя по тому сайту, действительно циклическая свертка имеет размер $ \tt{N}$, как у обоих сигналов,то есть меньше ,чем у линейной свертки $ \tt{2N-1}$,так что, возможно, она и правильно у меня считалось.
Вообще я считал ее изначально (прямым образом) в Mathematica командой $ \tt{ListConvolve}$,и там что линейная, что что циклическая давали одинаковый размер $ \tt{2N-1}$(для данного набора 21). Вообще свертка в разных пакетах считается как-то по-разному :facepalm:

 Профиль  
                  
 
 Re: Дискретное преобразование фурье и свертка
Сообщение24.09.2014, 22:43 


07/08/14
4231
Нет, для циклической сигналы предварительно готовят - дополняют нулями до одинакового размера.
А для БПФ - дополняют до степени двойки.
Если сигналы уже свернуты каждый в спектр, тоих свертка друг с другом- это просто перемножение спекторв.
Может вы данные спектра загоняете в преобразование фурье?

 Профиль  
                  
 
 Re: Дискретное преобразование фурье и свертка
Сообщение24.09.2014, 22:59 


20/09/14
17
В моем случае оба сигнала одинаковога размера (два треугольных сигнала),я делаю БПФ каждого, перемножаю, и выполняю обратное преобразование.В маткаде 2 метода ДПФ, дело в том, что если использовать тот, где нужно дополнять нулями, то получается результат совсем другой(даже по графику), притом не похожий на правду.
UPD: только что проверил. Если в том методе, где не обязательно дополнять нулями, все-таки дополнять до размера 16, результаты становятся похожи, но очень сильно изменяются(даже по форме) по сравнению с первым.Прямо шаманство какое-то.
Посмотрел в википедии, при дополнени нулями получаем другую, апериадическую свертку, но при этом в моём случае нужно дополнять до длины$ 11+11-1=21$, так что метод(Cooley-Tukey)с требованиями к длине исходного сигнала $2^L$ не подходит.
Остается открытым вопрос, можно ли найти последние $  {N-1}$ значений круговой свертки 2 сигналов длины $  {N}$, зная первые $  {N}$, поскльку Mathematica и Matlab выдают $  {2N-1}$-значный результат.

 Профиль  
                  
 
 Re: Дискретное преобразование фурье и свертка
Сообщение25.09.2014, 09:16 


07/08/14
4231
1. вы задаете сигнал вида $1,2,3,...32,31,30,...0$
2. второй сигнал вида $-1,-2,-3,...-32,-32,-30,...0$
3. БПФ $1$-го сигнала
4. БПФ $2$-го сигнала
5. поточечное перемножение
6. обратное БПФ
7. строим по значениям график
8. на графике косинус?

-- 25.09.2014, 09:56 --

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

 Профиль  
                  
 
 Re: Дискретное преобразование фурье и свертка
Сообщение25.09.2014, 13:26 


20/09/14
17
Проделал, как указано в инструкции. Действительно, получается что-то вроде косинуса.Еще раз перечитал информацию из dsplib.А увеличив последовательность в 2 раза, дополнив нулями, можно получить еще и линейную свертку. А математика и матлаб выдают увеличенную последовательнось из $ 2N-1$ чисел , видимо, считая циклическую свертку по 2 периодам. Спасибо за помощь! 8-)

 Профиль  
                  
 
 Re: Дискретное преобразование фурье и свертка
Сообщение25.09.2014, 15:18 


20/09/14
17
Проверил, линейная свертка через ДПФ совпадает, а циклическая, видимо,периодична при любых данных(значения после первых $ N$ повторяются)

 Профиль  
                  
 
 Re: Дискретное преобразование фурье и свертка
Сообщение25.09.2014, 16:53 


07/08/14
4231
upgrade в сообщении #911666 писал(а):
Нет, для циклической сигналы предварительно готовят - дополняют нулями до одинакового размера.

извините, тут наврал :-) для БЫСТРОГО Фурье готовят.

 Профиль  
                  
 
 Re: Дискретное преобразование фурье и свертка
Сообщение26.09.2014, 10:56 
Модератор
Аватара пользователя


16/02/11
3788
Бурашево
Logrus в сообщении #911384 писал(а):
Но в результате этого получается сигнал размерности $\tt{N}$, и это только половина свертки.
Вот тут находится корень зла, который мешает вам разобраться. Всё дело в том, что обратное дискретное преобразование Фурье дает периодический дискретный сигнал, с периодом $N$, равным объёму преобразования. Да и вообще пара ДПФ связывает две периодические последовательности чисел, несмотря на то, что в самих вычислениях участвует только один их период.

Результат циклической свёртки сигналов $\{x_n\}_{n=0}^{N-1}$ и $\{y_n\}_{n=0}^{N-1}$ является свёрткой периодических дискретных сигналов, периода $N$, получаемых периодическим повторением $x_n$ и $y_n$. И ДПФ+перемножение+ОДПФ всегда будет давать именно циклическую свёртку. Если этим методом требуется выполнить обычную свёртку, то следует один период сигнала дополнить нулями (не менее $N$ нулевых отсчётов), чтобы отсчёты с других периодов "не лезли" в вычисления.

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

Модераторы: Модераторы Математики, Супермодераторы



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

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


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

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