I have already asked this question 2 times, but still i am confused because this is not available anywhere on the internet and explained properly. I found some information in this document and i am going to apply their method , but confused to understand. here is the document http://www.altera.com/literature/an/an480.pdf. If anyone have some time to explain me kindly explain me where is radix 2 stage in this document to calculate the fft of size 512 because it has been broken into 3 small sequences of length 512 and then applied the fft on small lengths and then calculated it with combining and multiplying it with twiddle factors respectively. Kindly help me i am stuck in here for more than a week.
It's hard to see what could be added to Peter K.'s answer to make it any clearer. Here is a snippet of MATLAB code that shows the whole process in all it's glory. Just copy and paste in MATLAB or octave and you can step through it one line at a time.
%% 1536 FFT based on three FFTs of 512 each n = 1536; % Create a piece of noise x = randn(n,1); % calculate FFT using MATLAB native fft() function. % We'll use this as a reference to prove it works fx = fft(x); % Break down into three signals of 512 points each p = x(1:3:end); q = x(2:3:end); r = x(3:3:end); % FFT each of those. This is a 512 power-of-two standard FFT fp = fft(p); fq = fft(q); fr = fft(r); % Do three times periodic extention (just repeat it three times) fp3 = [fp; fp; fp]; fq3 = [fq; fq; fq]; fr3 = [fr; fr; fr]; % calculate the 1536 twiddle factors k3 = (0:n-1)'; W3 = exp(-j*2*pi*k3/n); % assemble the result fy3 = fp3 + W3.*fq3 + W3.^2.*fr3; % calculate the error ferror = fy3-fx; fprintf('Error = %6.2f dB\n',10*log10(sum(ferror.*conj(ferror))./sum(fx.*conj(fx))));
Your FFT size is $1536 = 3 \times 512$. The FFT radixes you need are, therefore, 3 and 2 (or some other power of 2).
The way the FFT works is by decomposing the full length DFT into smaller (prime-number-length), simpler FFTs. The way you decompose a particular length is by looking at the prime factors of the length.