2014 dxdy logo

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

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




На страницу 1, 2  След.
 
 Дискретное преобразование фурье и свертка
Сообщение24.09.2014, 13:44 
Здравствуйте, начал интересоваться численными методами нахождениями(циклической) свертки сигналов на основе ДПФ.Для опробации взял два треугольных сигнала(прямой и перевернутый, например
$\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 
Аватара пользователя
 i  Тема перемещена из форума «Помогите решить / разобраться (М)» в форум «Карантин»
Причина переноса: формулы не оформлены $\TeX$ом

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

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

 
 
 
 Re: Дискретное преобразование фурье и свертка
Сообщение24.09.2014, 20:34 
а под размерностью сигнала что понимается?
количество отсчетов?

 
 
 
 Re: Дискретное преобразование фурье и свертка
Сообщение24.09.2014, 20:39 
upgrade
ну да, количество точек разбития(дискретизация), а так сигнал одномерный

 
 
 
 Re: Дискретное преобразование фурье и свертка
Сообщение24.09.2014, 21:40 
Из сообщения лично я понял, что в первом случае вы делаете свертку двух сигналов, а во втором ищете спектр одного из них, поскольку количество данных меньше степени двойки допмсываете нули. И не понимаете что спектр симметричный (потому и половину показывает, вторая половина такая же)

-- 24.09.2014, 21:45 --

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

 
 
 
 Re: Дискретное преобразование фурье и свертка
Сообщение24.09.2014, 21:50 
upgrade
То, что спектр симметричный, я понимаю, я как раз говорю, что свертка 2 сигналов размера $\tt {N}$ должна быть размера $\tt {2N-1}$,и в общем случае( если оба сигнала не симметричны) несимметричная, тогда как вычисление через ДПФ (как часто и делают) дает только первые $\tt {N}$ значений(так как ДПФ и обратное ДПФ не меняют, в отличии от свертки, размер сигнала), и я не пойму, как находить вторую половину свертки?А дописывание нулей в конце сигнала вообще, похоже, в корне меняет результат(хотя при прямом вычислении свертки такого быть не должно)

 
 
 
 Re: Дискретное преобразование фурье и свертка
Сообщение24.09.2014, 22:16 
Вот ссылка о свертках сигналов
http://www.dsplib.ru/content/conv/conv.html
Вы так как по ссылке размерность определяете для сигналов, когда их спектры ищете?

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

 
 
 
 Re: Дискретное преобразование фурье и свертка
Сообщение24.09.2014, 22:43 
Нет, для циклической сигналы предварительно готовят - дополняют нулями до одинакового размера.
А для БПФ - дополняют до степени двойки.
Если сигналы уже свернуты каждый в спектр, тоих свертка друг с другом- это просто перемножение спекторв.
Может вы данные спектра загоняете в преобразование фурье?

 
 
 
 Re: Дискретное преобразование фурье и свертка
Сообщение24.09.2014, 22:59 
В моем случае оба сигнала одинаковога размера (два треугольных сигнала),я делаю БПФ каждого, перемножаю, и выполняю обратное преобразование.В маткаде 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 
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 
Проделал, как указано в инструкции. Действительно, получается что-то вроде косинуса.Еще раз перечитал информацию из dsplib.А увеличив последовательность в 2 раза, дополнив нулями, можно получить еще и линейную свертку. А математика и матлаб выдают увеличенную последовательнось из $ 2N-1$ чисел , видимо, считая циклическую свертку по 2 периодам. Спасибо за помощь! 8-)

 
 
 
 Re: Дискретное преобразование фурье и свертка
Сообщение25.09.2014, 15:18 
Проверил, линейная свертка через ДПФ совпадает, а циклическая, видимо,периодична при любых данных(значения после первых $ N$ повторяются)

 
 
 
 Re: Дискретное преобразование фурье и свертка
Сообщение25.09.2014, 16:53 
upgrade в сообщении #911666 писал(а):
Нет, для циклической сигналы предварительно готовят - дополняют нулями до одинакового размера.

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

 
 
 
 Re: Дискретное преобразование фурье и свертка
Сообщение26.09.2014, 10:56 
Аватара пользователя
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