Winograd FFT in C++ or Java


apchar
01-18-2006, 05:01 PM
NR speaks briefly about the Winograd FFT for datasets that dont have 2^n datapoints but doesn't give the algorithm much less the code.
Does anyone know where I can find the code in Java, C++, or even just a raw algorithm?
Thanks,
Art.

cordery
02-19-2007, 03:39 PM
Try www.fftw.org for free efficient high quality dft's with source for arbitrary length arrays and multi-dimension arrays.

cheers,
Bob

lto
10-04-2007, 12:01 AM
I agree. fftw is the best.

Long

rafaels
10-21-2007, 11:35 PM
This book is a good reference if you are still looking for the raw algorithm:

- Digital Signal Processing Algorithms
(http://www.amazon.com/gp/redirect.html?ie=UTF8&location=http%3A%2F%2Fwww.amazon.com%2FDigital-Signal-Processing-Algorithms-Applications%2Fdp%2F0849371783%3Fie%3DUTF8%26s%3Db ooks%26qid%3D1193027319%26sr%3D1-2&tag=rafsblo-20&linkCode=ur2&camp=1789&creative=9325)

(do a search for "Winograd" inside the book, section 13.7)

Hope it helps,

- Rafael

kutta
01-31-2009, 08:16 AM
NR speaks briefly about the Winograd FFT for datasets that dont have 2^n datapoints but doesn't give the algorithm much less the code.
Does anyone know where I can find the code in Java, C++, or even just a raw algorithm?
Thanks,
Art.

Hello Comrade
Please find yourself to compute from the following Algo
//Wiograd's Matrix Multiplication-Algorithmic clarity
Input : A,B,m,n and q where A and B are m * n and n * q matrices,respectively
Output: Matrix C = AB.The m * q matrix C is passed in and the algorithm fills it.
void winograd(foat[][] A,float[] B,int n,int m,int q, float[] C)
int i,j,k;
int p=n/2;
float[] rowerm= new float[m+1];
float[] colmTerm= new float[q+1];
// The arrays are for the results of the "preprocessing"
//of the rows of A and the columns of B
//"Preprocess" rows of A
for (i=1;i<=m;i++)
rowTerm[i]= {ai,2j-1 *ai,2j;}{ while j=1 and tends to p};
//"Preprocess " columns of B
for(i=1;i<=q; i++)
colTerm[i]={ b2j-1,i *b2j.,i;}{while j=1 and tends to p};
//Compute entries of C
for(i=1;i<=m;i++)
for(j=1;j<=q;j++)

cij=(ai,2k-1+b2j,j) *(ai,2k+b2k +b2k +b2k-1,j)
-rowTerm[i]-colTerm[j];
// If n is odd add a final term to each entry of C
if(odd(n)0)
for(i=1;i,+m;i++)
for (j=1;j<= q; j++)
cij=cij+ain *bnj;


Hope this is useful.
Thanking You
AS
Kutta(C.R.Muthukumar)
:)