FFT of input length 1536

Does anyone knows can i find a FFT of 1536 length input. Its a specification given in 3gpp Lte and we need a transform of 1536 input size which is neither a power of any number i would say. I just need a theoretical idea.

Note that $1536 = 3\cdot 512$. You can use a decimation in time method. See http://www.altera.com/literature/an/an480.pdf

I'll add some extra information here in response to your comment to sansuiso's answer (even though this comment actually referred to the pdf file I mentioned above in this answer). As explained in the above document, you need to compute 3 FFTs of length 512. You do this by taking time samples 0,3,6,9, ... and compute their FFT, then you take the samples 1,4,7,10,... and compute another FFT. Finally you compute the FFT of samples 2,5,8,11,... Then you combine the 3 FFTs using the appropriate twiddle factors to obtain the desired 1536-point FFT. This last step is the radix-3 stage. Have a look at Equation (2) on page 3 of the document (also Fig. 1 on page 4).

Also check out this blog post. It also includes a little Matlab program.

You can find a lot of information for very fast FFT with non-power-of-two data on the site of the fftw library. If you can use GPL software, it's a good library to work with.

• Well I have already seen the link of the pdf you pasted, but I guess they are using according to their architecture. I can't use fftw library due to some licensing problems in my company. So, any other solutions? – D X Apr 15 '13 at 14:50
• Are you referring to the pdf in my answer? You can directly use this method. Of course you need an implementation of an FFT algorithm but the method is totally independent of the architecture. Just use 3 512-point FFTs and combine the results appropriately (as described in the document). – Matt L. Apr 15 '13 at 15:41
• Yeah i am talking about ur document. Actually I don't understand the radix 3 stage.. Does it corresponds to the FFT radix 3 algorithm? What i understand is that we should consider three different sequences of 512 and calculate their dft separately and in the end just add them (not sure about this). Kindly give some feedback on my idea. – D X Apr 15 '13 at 16:02
• I am not understanding the last stage (radix 3). I would take fft as you have already mentioned and then add them all three of them( with twiddle factors applied to the output of 2nd and 3rd as given in the document). Radix 3 means after adding them I have to again apply the fft? Radix 3 means fft radix 3 algorithm ? – D X Apr 16 '13 at 12:22

Matlab reference code to do a 1536 FFT using 512 point base FFT

%% 1536 FFT based on three FFTs of 512 each
n = 1536;
% Create a piece of noise
x = randn(n,1);
% calcuate 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];
% calucate 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;
% calcualte the error
ferror = fy3-fx;
fprintf('Error = %6.2f dB\n',10*log10(sum(ferror.*conj(ferror))./sum(fx.*conj(fx))));

• That's correct, but note that the combination of the 3 length 512 FFTs can be achieved more efficiently by an efficient implementation of a length 3 DFT/FFT (which needs 4 real multiplications). See the Matlab/Octave program here. – Matt L. Jan 10 '15 at 16:57