# Solution for FFT size 1536

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.

• Your FFT size is $1536 = 3 \times 512$. The FFT radixes you need are 3 and 2, the prime factors of your FFT size. – Peter K. Apr 16 '13 at 14:52
• Can you tell me why are you doing periodic extension three times. What is the purpose of doing it ? – D X Apr 22 '13 at 13:51
• Because the full FFT is 3 $\times$ as long as each individual FFT; you still need to evaluate the final answer over 0..$N$, not from 0..$N/3$. – Peter K. Apr 22 '13 at 13:54

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))));

• Thanks, Hilmar! Perhaps the MATLAB code will get it through. – Peter K. Apr 19 '13 at 22:07
• One question why did u do three times periodic extension(just repeat it three times) – D X Apr 22 '13 at 12:16
• Because the full FFT is 3 $\times$ as long as each individual FFT; you still need to evaluate the final answer over 0..$N$, not from 0..$N/3$. – Peter K. Apr 22 '13 at 13:00

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.

See the wikipedia entry on the Split Radix FFT Algorithm for more detail.

EDIT

Then see this link, which has this derivation: • I have already seen the split radix algorithm that is why i am asking you.. Do you think that split radix algorithm will work for fft of size 1536? Only this is my question. The approach you were telling me before 1536=3x512 I know it already , but i think its difficult to implement. – D X Apr 16 '13 at 15:22
• So, it's clear you don't want to use a radix-3 as part of your FFT. Why not just zero-pad to, say, 2048 points and use a power-of-2 FFT? I do not believe it's not possible to use a radix-2 (only) FFT to perform a 1536-length (only) transform... at least, not efficiently. – Peter K. Apr 16 '13 at 15:25
• So you mean that if i want to use split radix algorithm i should have an input length which should be a power of 2,3,4 or any number ? 1536 is not a power of any number . I understand this. Ok now we come back to your previous idea for 1536 =512 x 3, since i found this solution in some document as well. But how do we implement it ? Can you read this link (page 2,3,4) altera.com/literature/an/an480.pdf.I don't understand the radix 3 stage. Does radix 3 stage means using radix-3 algorithm?Or can you elaborate your comment. How to implement this in C programming just a rough idea. – D X Apr 16 '13 at 15:36
• Thank you sir. It would be of great help if you can comment on my last comment regarding the idea i am thinking – D X Apr 17 '13 at 8:00
• Please update THE QUESTION with the extra information you require. – Peter K. Apr 17 '13 at 12:05