Дискретное преобразование фурье и свертка

[Logrus]

Здравствуйте, начал интересоваться численными методами нахождениями(циклической) свертки сигналов на основе ДПФ.Для опробации взял два треугольных сигнала(прямой и перевернутый, например
$\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$(с прореживанием по времени?),дописывая нули до конца, но тогда результат вообще очень сильно искажается(Нули портят свертку?)

[Deggial]

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

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

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

[upgrade]

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

[Logrus]

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

[upgrade]

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

-- 24.09.2014, 21:45 --

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

[Logrus]

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

[upgrade]

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

[Logrus]

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

[upgrade]

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

[Logrus]

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

[upgrade]

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 --

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

[Logrus]

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

[Logrus]

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

[upgrade]

upgrade в сообщении #911666 писал(а):

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

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

[profrotter]

Logrus в сообщении #911384 писал(а):

Но в результате этого получается сигнал размерности $\tt{N}$, и это только половина свертки.

Вот тут находится корень зла, который мешает вам разобраться. Всё дело в том, что обратное дискретное преобразование Фурье дает периодический дискретный сигнал, с периодом $N$, равным объёму преобразования. Да и вообще пара ДПФ связывает две периодические последовательности чисел, несмотря на то, что в самих вычислениях участвует только один их период.

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