Быстрая свёртка, Вычисление не через преобразование Фурье Опции

[Eugeno]

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

[fontp]

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

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

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

[bve]

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

[evgeniy_s]

Поскольку свёртка, по существу, эквивалентна корреляции, то её можно производить несколькими способами, которые различаются используемыми функциями. По крупному эти функции делятся на два больших класса: непрерывные и дискретные. К методам, использующим непрерывные функции относятся: преобразование Фурье (Быстрое Преобразование Фурье - БПФ), косинусное и синусное преобразования (разновидности преобразования Фурье) и их производные (например, Чётное Симметричное Косинусное Преобразование - ЧСКП). Среди дискретных преобразований можно выделить преобразования, использующие функции Уолша или Пэли. В частности наиболее известное - преобразование Уолша-Адамара (Быстрое Преобразование Уолша-Адамара - БПУА). В отличие от Фурье-преобразований, дискретные используют действительные числа, а не комплексные и, более того, все операции умножения/деления заменяются на сложения/вычитания. Советую почитать книги
1. Ахмед Н., Рао К.Р. Ортогональные преобразования при обработке цифровых сигналов: пер. с англ./ Под ред. И.Б. Фоменко. М.: «Связь», 1980. – 248 с., ил.
2. Трахтман А.М., Трахтман В.А. Основы теории дискретных сигналов на конечных интервалах. М.: «Советское радио», 1975. – 208 с.
Если свёртка Вас интересует с точки зрения сравнения двух сигналов (распознавание), могу выложить свою работу, в которой исследуются с точки зрения эффективности два способа: ЧСКП и БПУА. Там же и литературку посмотрите.

[zhorro]

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

[Eugeno]

Jörg Arndt, грамотный и нежадный автор, разместил замечательную книгу и С-библиотеку FXT относящуюся к этой теме
http://www.jjj.de/fxt/fxtpage.html#fxtbook

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

[iit]

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

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

[evgeniy_s]

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

Нет проблем, выкладываю:
 Hadamar.rar ( 339.87 килобайт ) Кол-во скачиваний: 1412

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