maxim1000,  что-то я совсем запутался... Давай по порядку.
Возьмем вектора A - 5 элементов и вектор В - 6 элементов.

В нашем случае разбивать то не надо, у нас же уже вектора и так 2.


Что это значит - по-простому найти коэффициент свертки?
Если да, то зачем нам надо 3 шаг. 



maxim1000, если есть ссылки, дай их, пожалуйста.

это я всё говорил про БПФ - ведь его нужно применять к каждому вектору, потом перемножить результаты поэлементно, потом - обратное БПФ

так вот предыдущий текст был объяснением, почему длины векторов, которые подаются на вход БПФ должны быть степенями двойки (ну или, по крайней мере, почему в этом случае всё значительно проще)

посмотрел wikipedia (БПФ), там в конце есть ссылка:
http://alglib.sources.ru/fft/
на первый взгляд интересная
там, кстати, в числе прочего обсуждается, что наиболее распространённый алгоритм - для векторов длины степени двойки, но есть и куча других

Спасибо! Поглядим

 Есть обобщенные методы - которые позволяют организовать вычисление БПФ для практически любого основания. Но их "быстрость" серьезно уступает RADIX-алгоритмам (2, 4, 8, 16 ... etc.) RADIX использует периодичность и симметрию матрицы преобразования - которая появляется в следствие использования гармонических функций как базиса. Простыми словами в ДПФ одни и те же отсчеты функции много раз (вот тут то и избыток) перемножаются с одними и теми же значениями базисных функций - а RADIX этот избыток убирает. Но... Вот тут самое интересное. Зачем автору топика гармонические функции??? Корреляция с ними будет вычислена с погрешностью и для float и для int! Метод даст толко приблизительное решение! FFT "проканывает" в радиотехнике и других измерениях где погрешность методики можно свести к величине меньшего порядка нежели погрешность самого измерения (АЦП) - но для численных методов математики это вызывает большие затруднения! Не грамотнее ли будет выбрать другой базис - так называемые теоретико-числовые преобразования. Это специально разработанный базис из дискретных целочисленных(!!!) функций - дает 0-ю погрешность при вычислениях свертки для int!!!
Во всем остальном он очень похож на Фурье - подходят теже алгоритмы (RADIX например) но без комплексной арифметики (в ДПФ/БПФ это обусловленно функцией основания exp(w)=cos(w)+j*sin(w)). Если свертка циклическая (т.е. за пределами окра рассмотрения ничего нет - как раз наш случай) то тоже дополняется "0"-ми при несовпадении длин последовательностей...

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

Это сообщение отредактировал(а) DRUID3 - 31.5.2008, 20:12

DRUID3
Во, спасибо, меня как раз интересует модификация ДПФ для целочисленной арифметики. Что-то никак не получалось сделать, чтобы работало. Попробую поискать эту книгу fxtbook...

Ну не надо путать одно с другим. Теоретико-числовые преобразования - это свертка с "0"-й погрешностью. А челочисленное FFT это целочисленное FFT ))).
В БПФ Вы, наверное, просто не делаете масштабирования результатов после каждого прохода бабочек - а для intFFT это принципиально - иначе на любом мало-мальски длинном промежутке вычислений набежит просто ужаснейшая погрешность из-за переполнения типа данных int. Быстрое переполнение типа или задействованного регистра на операции умножение с накоплением (а это основа ЦОС в современном его представлении) это "бич" всех целочисленных вычислений и вычислителей - от микроконтроллеров до ПЛИС - для того в DSP и применяют аккумуляторную архитектуру с 48 битами. Вобщем масштабируйте и будет Вам счастье...
Вот книга http://www.jjj.de/fxt/ + уникальнейшая библиотека ЦОС исходников! Не первый год тестируемая и в своем составе с тестовыми алгоритмами, если захотите изменить исходник...

Вот FFT на все случаи жизни http://www.jjj.de/fft/fftpage.html Покопайтесь, там есть и целочисленные и очень редкие типа RADIX5...

Это сообщение отредактировал(а) DRUID3 - 31.5.2008, 21:50

DRUID3
Не, у меня вообще чушь получалась. даже для размеров 2x2 )
А вообще, раз тут (в intFFT) тоже возникают проблемы, может, лучше уж писать обычное FFT и не париться... )
В любом случае, спасибо за ссылки.

   обычное в смысле где? если там где требуется свертка целочисленных отсчетов функций - то FFT вообще применять не стоит. А автору топика нужна именно она. А если где-то лежит выбор между intFFT и floatFFT - то следует выбрать плавающую точку если это позволяет процессор. А если не позволяет - ARM7, BlackFin, AVR32 etc. то intFFT вполне реализуемый алгоритм. И так просто от него отказываться не стОит, написав его самостоятельно получите уникальные навыки - я сам начал заниматься ЦОС именно с написания своего FFT   

Это сообщение отредактировал(а) DRUID3 - 31.5.2008, 23:37

Ссылка хорошая... наверно ))
Скачал fxt-2008.04.10.tgz, там внутри файл с расширением 10. Что с ним делать-то?
Скачал PDF в архиве fxtbook.pdf.gz, Acrobat Reader говорит что файл повреждён...

 linuxовый архив поврежден, а там есть вообще без архива pdf-ка ее и качать...

 Файл с расширением .10 это такая шутка от юниксоидов. Но 7-zip его элементарно открывает, исходники внутри этого файла...

Это сообщение отредактировал(а) DRUID3 - 2.6.2008, 09:36

Точно. Усё получилось