Here you can ask questions and find or give answers to organizational, academic and other questions about studying computer science.

1.1k questions

1.2k answers


543 users

0 votes

In the introduction of the recusion step, there was the assumption chosen that n=2m, so an even number.

0) If the m is a odd number the recursion would end just end after one recusive step, which will not be the idea, right?
1)Will the fast fourier transformation still work with only one or none (or n is a odd number) recursiv step with Dept=O(log(N)) and Work=O(N*log (N))?
2)Is it okay to extend the F(w,n) Matrix to a F(w,2l) Matrix where 2is the next potence of 2 by adding (0,0,....,0) rows and extend x by 2-n '0' rows?

in * TF "Emb. Sys. and Rob." by (810 points)

1 Answer

+1 vote
Best answer
The Fast Fourier Transform is only defined for powers of 2 so that we can benefit from the symmetries of the Fourier matrix which allows one to reduce FFT(n) to two independent FFT(n/2) computations. Since the latter two can be done in parallel, we obtain a O(log(n)) time parallel algorithm with an overall work of O(n\log(n)) with n=2^k.

If for a given problem, n is not a power of 2, one has to adjust the problem by prepending 0s.
by (166k points)
selected by
ah, I see. Yeah, I thought right how to extend to the matrix with power of 2 size

Related questions

0 votes
1 answer
0 votes
1 answer
0 votes
1 answer
Imprint | Privacy Policy