интегралы через быстрое преобразование Фурье

[Sommer]

кто - нибудь занимался реализацией этого?...

[RXL]

Сейчас разбераюсь...
Какой иммено вопрос?

[Sommer]

RXL,
вопрос в дискретной свертке
в алгоритме ее реализации посредством FFT
если занимаешься этим - очень бы хотелось пообщаться
я не совсем понимаю как реализовать сам алгоритм дискретной сертки..
пользую FFT с www.fftw.org

[RXL]

Свертка (convolution) и FFT - вещи разные.
Свертка делает умножение двух сигналов, а FFT разложение на состовляющие синусоиды.

Что именно ты хочешь проинтегрировать? Сам сигнал, или некоторую составляющую?

[Sommer]

задача состоит в реализации дискретной свертки посредством FFT - об этом можно почитать у Баскакова в РЦИС

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

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

[RXL]

Чесно говоря, я почти ни чего не понял... Видимо, мы разную литературу читаем  

Мне кажется, что я бы быстрее и правильнее понял, если бы ты сказал своими словами, без математики, тау и прочих китов.  
Ты хочешь сделать свою реализацию FFT?

[Sommer]

RXL, есть какая-то программа, которая вычисляет кучу вложенных интегнралов месяцы

моя задача используя FFT (его писать ИМХО самому бессмысленно - легче и умнее взять с www.fftw.org) решать те же задачи во много раз быстрее

используется свойство дискретной сверки(интеграл произведения 2 - х функций) - ее можно представиь через произведение коэф - в дискретного преобразования Фурье тех сигнналов, интеграл проризведения которых мы берем

ты сам чем конкретно занимаешься?
меня интересует алгоритм программирования этой дискретной свертки

[Sommer]

RXL,
нужен алгоритм дискретной свертки через FFT

FFT уже есть

[RXL]

Я читаю литературу отсюда: http://www.dspguide.com/
Точнее: http://www.dspguide.com/pdfbook.htm
А DFT детально описывается тут:
http://www.dspguide.com/ch8.htm
http://www.spectrumsdi.com/ch8.pdf
На нем я пока и остановился.
-------
Мне ранее приходилось сталкиваться с вопросами обнаружения сигналов в телефонии, а сейчас решил изучить вопрос детальнее.

[RXL]

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

Сама свертка представляет собой простую формулу: y[n]=sum(h*x[n-i]), где x - входной сигнал, h - "импульсный отклик" (impulse responce), y - выходной сигнал, n - число отсчетов в выходном сигнале, i - длина h[], длина входного сигнала n-i+1.

[Sommer]

RXL,
дискретная свертка через FFT :
C[f[k]] = C[x[k]] * C[y[k]]
литературу, по преобразованиям Фурье я уже указывал - есть в любой библиотеке

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

я вроде разобрался в алгоритме...
сделаю - выложу - он простой
проблема была не втом как пограммировать, а как вообще его себе представить\осознать...

--
а как ты обнаруживал сигналы в телефонии?....

[RXL]

Несколько дальше нашел перемещение свертки из time domain в frequency domain - похоже ты от этом говоришь. Действительно простая вещь - оба сигнала (одной длины - самый короткий дополняется нулями) проходят FFT, а потом просто перемножаются коэффициенты с одним индексом. Упомянается, что это полезно при большой длине импульсного отклика (рекомендуют для длины больше 32).
 Ты об этом говорил?
-----
Есть алгоритм Goertzel-я для обнаружения заранее известного набора частот. Значительно проще и быстрее FFT. Кроме того, в АОН-е (всмысле, тел. аппарате с запросом АОН-а) на Z80 был реализован тот же алгоритм, только для однобитного (!) сигнала. Время вычисления для 7 частот составляло около 15мс на процессоре в 4МГц.

[Diletant]

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

[Sommer]

Diletant,
да именно это имелось в виду
я внес тему  именно в этот форум т.к. нужен алгоритм на С++

правда пока полемика вокруг понимания алгоритма впринципе

RXL, ясно, спасибо

[Diletant]

 нужен алгоритм на С++

Алгоритм на языке программирования, IMHO, нонсенс. Или вопрос в том как комплексную арифметику на С реализовать? А так берется "алгоритм" на Фортране и аккуратно переписывается. Тем более вся программка строк этак в двести. Если же речь идет об FFT, оптимизированном под конкретный процессор, то тема обсуждалась на  www.shelek.com/club, там еще ссылки на специализированные сайты приводились

[Sommer]

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