[Eugeno 0]

А не подскажет ли кто, можно ли найти свёртку двух сигналов быстрыми методами не через преобразование Фурье, а через другие ортагональные преобразования? :unsure:

[fontp 0]

Может быть выгодным пользоваться производными от Фурье преобразованиями - например, преобразование Хартли имеет примерно те же свойства для свёртки, но - действительное, а не комплексное. Есть ещё теоретико-числовые преобразования - но это тоже преобразования Фурье, но в конечных полях.

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

Возможность факторизации свёртки напрямую связано с тем, что векторы базиса Фурье являются собствеными векторами оператора сдвига.

 

Jörg Arndt, грамотный и нежадный автор, разместил замечательную книгу и С-библиотеку FXT относящуюся к этой теме

 

http://www.jjj.de/fxt/fxtpage.html#fxtbook

[bve 1]

В небезизвестной книге "Рейдер, Макленнан" есть алгоритмы вычисления "прямой" свертки,

например, через ректангулярные преобразования. При фиксированном одном из векторов свертки

можно получить алгоритм, экономнее чем БПФ.

[evgeniy_s 0]

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

1. Ахмед Н., Рао К.Р. Ортогональные преобразования при обработке цифровых сигналов: пер. с англ./ Под ред. И.Б. Фоменко. М.: «Связь», 1980. – 248 с., ил.

2. Трахтман А.М., Трахтман В.А. Основы теории дискретных сигналов на конечных интервалах. М.: «Советское радио», 1975. – 208 с.

Если свёртка Вас интересует с точки зрения сравнения двух сигналов (распознавание), могу выложить свою работу, в которой исследуются с точки зрения эффективности два способа: ЧСКП и БПУА. Там же и литературку посмотрите. :)

[zhorro 0]

Есть интересный алгоритм быстрой свертки без перехода в другой базис

Если рассматривать сигнал как сумму четных отсчетов и нечетных и тоже самое с импульсной характеристикой. Теперь, если рассматривать свертку, как умножение двух полиномов

нетрудно получить зависимости выхода фильтра от его входа, получаеться тот же эффект, что и в БПФ, т.е. за обин "такт" работы системы вычисляеться сразу два отсчета с использованием 3х фильтров, импульсные характеристики которых в два раза короче

[Eugeno 0]

Jörg Arndt, грамотный и нежадный автор, разместил замечательную книгу и С-библиотеку FXT относящуюся к этой теме

http://www.jjj.de/fxt/fxtpage.html#fxtbook

Отличная ссылка. Остановился на теоретико-числовых преобразованиях. Для входных целых данных никаких погрешностей при вычислениях. А по скорости вычислений - можно реализовать не медленней остальных преобразований.

[iit 0]

Если свёртка Вас интересует с точки зрения сравнения двух сигналов (распознавание), могу выложить свою работу, в которой исследуются с точки зрения эффективности два способа: ЧСКП и БПУА. Там же и литературку посмотрите. :)

 

Будте добры выложите или на мыло Vavilov_Danil[at]mail[dot]ru. Меня свертка интересует именно с точки зрения распознавания.

[evgeniy_s 0]

Будте добры выложите или на мыло Vavilov_Danil[at]mail[dot]ru. Меня свертка интересует именно с точки зрения распознавания.

Нет проблем, выкладываю:

Hadamar.rar

Желаю успеха в работе.