Здравствуйте!

Краткое описание:
Передо мной стояла задача реализовать алгоритм дискретной свертки двух сигналов, не прибегая к какой-либо внешней помощи.
Я свел задачу к вычислению всех диагоналей произвольной (в общем случае) матрицы и получил решение.
Я новичек и было бы здорово услышать Вашу оценку и критику

Алгоритм:
Имеются два одномерных числовых массива(arrayX, arrayH) произвольной длины (N и M), которые почленно (x1 * (h1, h2, ..., hm), x2 * (h1, h2,...,hm), ...) перемножаются в матрицу размера [NxM].
Таким образом матрица будет содержать все слагаемые для свертки (в процессе свертки каждый элемент одного массива перемножается
с каждым элементом другого массива).
Таким образом каждая диагональ получившейся матрицы будет представлять собой элемент свертки, так что задача как раз сводится, в моем случае, к вычислению всех диагоналей данной матрицы.
Подсчет диагоналей осуществляется от левого верхнего элемента, то есть, если мы имеем матрицу:

1 2 3
4 5 6
7 8 9

То диагонали будут соответственно: 1, 2 + 4, 3 + 5 + 7, 6 + 8, 9
 
 

Примечания:
В тексте кода расчитываются не все диагонали матрицы, а только верхняя их часть.
Для расчета диагоналей нижней части и получения полного решения, достаточно транспонировать имеющуюся матрицу и 
снова применить к ней этот же алгоритм. 

Топик на этом форуме является обращением к внешней помощи   



Зачем промежуточные произведения сводить в матрицу, забивать память? Суммируй их сразу.

ksili, 
хех, спасибо!
Вообще меня более всего интересует, насколько хорош выбранный мной путь решения такой задачи?
А, в целом, сведение аналитиеской задачи к операциям над матрицей довольно распространенная практика...
Но не могу не согласиться что вставлять промежуточную матрицу в код это была лишняя нагрузка.
Думаю, стоит такие действия выполнять на бумаге, а в код забивать уже более концентрированную идею.

inamozov, не вникал в алгоритм. Просто брасается в глаза.

Здесь j никогда не будет равно m

volatile,
спасибо, это (!(j == m)) надо вообще убирать.

надеюсь скоро довести до одного общего, без транспонирования


довел

Это сообщение отредактировал(а) inamozov - 3.5.2012, 01:29

inamozov, я вам помогу, чуток, ок?

В итоге в массиве  sum [] у нас сумма всех диагоналей.

зачем без транспонирования? можно вообще без матрицы.

Сколько не видел FFT, FWT и прочих реализаций матпреобразований - все они в чем-то разные, а ведь кажется математика это нечто общее для всех...    математика то общее, а ее восприятие у каждого свое...

Одномерную свертку я представляю так как когда-то ее объяснил один преподаватель "радиотехнических сигналов и систем" - берем два графика, один обращаем вспять(как если бы перевернули лист на другую сторону) и поточечно перемножаем и суммируем(вот почему умножение с накоплением основная операция в DSP). Сдвигаем графики навстречу друг другу на одну точку  и снова повторяем... И так бесконечно.  .
 Прилагаю маленький проектик FIR-фильтра(та же свертка).

P.S.: ...я не говорю, что у топикстартера идея/реализация неверно(я не проверял   ) просто он видит так, а я эдак. Проект мой скорее учебный (не особо оптимизированный, да и свертку влоб профи часто заменяют перемножением в частотной области или в вейвлетотображении) но зато с тестом - можно проверять свои реализации. 

P.P.S.: если в комментах грамматические оПшиПки - сообщите - это да, грамАта ниККаДДа не Пыла мАим сильным местАм   

Присоединённый файл ( Кол-во скачиваний: 3 )
 uFIR_test.zip 9,02 Kb

Бесконечно - это в циклической свёртке.
А так, длина результирующей последовательности равна N+M-1.

Вот вариант, от 2.05.2012, где происходит подсчет диагоналей (гипотетической  ) матрицы свертки.
В итоге цельный алгоритм реализован путем обхода по матрице слева направо а потом сверху вниз.

Есть такое понятие, Бритва Оккама, соблюдение которого еще никому никогда не помешало.
Зачем здесь столько нагорожено?
Нужно быть проще, задача то элементарная. (см. мой пост выше.)
Сами не разберетесь в своем коде через пару месяцев.
К тому-же, чисто по опыту скажу: очень вероятно, что в такой мешанине не один баг зарыт.

volatile, стараюсь придерживаться принципа доводить начатое до конца.

Ваш алгоритм:



замечательно прост и красив, только еще не было времени "разобраться" с ним.
Спасибо.

inamozov, на самом деле, там много времени не нужно.
Попробую объяснить.

Например, возьмем ячейку sum[0]
В ней будет сумма тех элементов, чьи индексы дают в сумме 0.
Таких элементов, как не трудно догадаться, всего один, это matrix[0][0];
это наша первая диагональ, которая состоит из одной клетки (0,0)

возьмем ячейку sum[1]
В ней будет сумма тех элементов, чьи индексы дают в сумме 1.
Таких элементов, уже два, это matrix[0][1], и matrix[1][0];
это наша 2-я диагональ, которая состоит из 2-ух клеток (0,1) (1,0)

возьмем ячейку sum[2]
В ней будет сумма тех элементов, чьи индексы дают в сумме 2.
Таких элементов, уже 3, это matrix[0][2], matrix[1][1], и matrix[2][0];
это наша 3-я диагональ, которая состоит из 3-ех клеток (0,2) (1,1) (2,0)

Ну и так далее... 

Для матрицы 4*4, например вся картина будет такой:

Все ведь просто.

volatile, у меня возник к Вам вопрос: получается, что Ваш алгоритм оперирует не самой реализацией матрицы - ее елементами (как делал я), а, скорее, на уровне свойств этой матрицы - в данном случае порядковых номеров элементов. Посоветовали бы вы при операциях над матрицами строить алгоритмы на уровне свойтв этих сущностей не "опускаясь" до их реализации?

Ну почему же. Алгоритм оперирует именно элементами. Проходит их все, от первого до последнего.
Ну и да, при этом использует свойство индексов.   


Даже не знаю что ответить... Единого рецепта видимо нет.
Больше программируйте, больше изучайте чужие программы.
С опытом придет понимание что лучше в конкретном случае.