Cyclic Convolution

[EXcell]

Hello, everybody!

I'm searching for algorithms for implemantation fast cyclic convolution. For example standart way, we have 2 polynomials g(x) and d(x), i want to see on the output coefficients of it convolution. Did you see such algorithms ever? I want to see some implementation on C/C++ , that I can easily proved with matlab for example with standart function conv(). I have one algorithm but i have a problems with it realisation.

[kumaresh_ana]

I want to see some implementation on C/C++We can help you do this. I have one algorithm but i have a problems with it realisation.Post the algorithm and you difficulty in acheiveing it.

Also convolution can be computed faster through fourier domain. Convolution is multiplication in fourier domain. There are several FFT algorithms out there to compute DFT efficiently. Wikipedia gives me these (http://en.wikipedia.org/wiki/Discrete_Fourier_transform#Circular_convolution_theorem_and_cross-correlation_theorem)

[EXcell]

This example uses quite special structures for storing data, so nevertheless i can snow a code partially, because actually I dont understand well, how is it work properly.
So description is:
on input:
Signal - massive under that we proceed a convolution. Lenght from 0 to SignalLEn
Response - second massive, that consist of two parts, negative response corresponds to values of massive from 0 to NegativeLen, and positive response correspnds to values from NegativeLen+1 to PositiveLen respectively.
Out of borders [-NagativeLen;PositiveLen] response is equal zero.
on output:
Signal - values od convolution function in points from 0 to SignalLen-1

maybe I call this function to properly?
Let's look on my call:

#include <stdio.h>
#include <conio.h>
#include <iostream.h>
#include "ap.h"
#include "realfft.cpp"
#include "fastconvolution.cpp"

int main(int argc, char* argv[])
{
ap::real_1d_array g;
ap::real_1d_array d;
int n, i;
double k;
clrscr();
cout <<"---Compute a linear convoltion s(x)=g(x)*d(x)---"<<endl;
cout <<"Insert a lenght of signals g(x) and d(x):"<<endl;
cin >>n;
g.setbounds(0,n-1);
d.setbounds(0,n-1);
cout <<"Insert a coefficiaents of polynom g(x):"<<endl;
for (i=0;i<=n-1;i++)
g(i) = scanf("%lf",&k);
cout <<"Insert a coefficiaents of polynom d(x):"<<endl;
for (i=0;i<=n-1;i++)
d(i) = scanf("%lf",&k);
fastconvolution(g,n,d,0,n-1);
cout <<"Convolution coefficients are:"<<endl;
for (i=0;i<=n-1;i++)
cout <<g(i)<<" ";
getch();
return 0;
}
so maybe i made some mistake, can you see it?

[kumaresh_ana]

It seems you are utilising the class correctly. Do you have readme or documentation for the file fastconvolution.cpp? Also did you refer any fft algorithms so that you can do everything from scratch?

[EXcell]

I have a documentation to class ap only, but not to fastconvolution.cpp
fft algorithm using above is attached