# 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 Altera Application Note 480: 1536-Point FFT for 3GPP Long Term Evolution. 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, 2013 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, 2013 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, 2013 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, 2013 at 22:07
• One question why did u do three times periodic extension(just repeat it three times)
– D X
Apr 22, 2013 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, 2013 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, 2013 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, 2013 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, 2013 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, 2013 at 8:00
• Please update THE QUESTION with the extra information you require.
– Peter K.
Apr 17, 2013 at 12:05

1.- Spectrum is in high demand

Very expensive, really.

Mobile commns operators have to administer spectrum very carefully to maximise gain.

When I started the mobile comms module at university the professor started right-away with the water-filling tank algorithm, that in a nutshell is about serving first those terminals with higher sustained demand for data, while leaving the lower demand terminals to either 'ask for more' or remain stuck in lower rates, despite all paying the same. or similar monthly bills for trumpeted 'unlimited' data.

From figure 8.1.2.2.1 in TR 25.814

TR 25.814 available directly from 3GPP PRG : here

With a 20MHz bandwidth (20MHz is the widest available) mobile-tower link with range 3km is considered edge-of-cell link.

The operators have to, or should, satisfy the data rates they advertise ANYWHERE across all cells (or most of them).

So in this conservative case the baseline overhead looks like 182Mbps but this is without splitting channels.

This is, a single stream, just raw bits on a single channel, test-only case, not really useful to any mobile phone.

Do not bring in IoT devices because IoT uses such raw data, but a far lower data rate, and far lower frequencies, to trade off hungry fancy apps for reliable low data rate, as simplified as possible, often with just that baseline stream.

But 4G 5G are complex standards with wide access capabilities, and they have to make sure users do not listen one another.

So, As shown in the previous graph the standard only requires a baseline overhead of 100Mbps.

When all 3G 4G 5G signalling channels splitting is done, for 2-atenna TX (tower) MIMO, 2-antenna serving the same mobile phone the mobile phone can get up to 128Mbps.

Either FDD/TDD and 64QAM.

Often QAM modulation has to lower the amount of points to avoid cuts.

Again towers diverting 4-antenna serving same mobile phone is a luxury that nation-wide operators have to be careful serving as well.

2.- Altera gets the 1536 FFT size from table 7.1.1

3.- Now let's have a look at the Altera specs mention in the question

This is the Altera clock

The standard suggests parallel processing

QUOTE

" .. The possibility to concatenate multiple sub-frames into longer TTIs, e.g. for improved support for lower data rates and QoS optimization, should be considered .."

UNQUOTE

Observe that 1536 is not for widest 20MHz, for the one below 15MHz. Squeezing a bit the channel in frequency may avoid causing interference to adjacent channels.

1536 FFT is the one for the designer to go for : if 1536 FFT works, the lower data rates that are going to be far more common, those are going to work too.

1536/2 doesn't fit the basic Altera block 512 because some points are wasted and 4x512 again wasting resources that may suit the top 20MHz bandwidth.

Given the clock limitation just mentioned above, processing 3x512 in parallel allows the circuit to keep pace.

It's not a coincidence. Manufacturers work in close contact with operators : Operators need devices to meet tech specs and be reasonable cheap, and with the current cut-throat market situation no manufacturer can afford selling cheap Ferraris, in a way to speak, or selling Nivas and Yugos when customers want/can pay for mid/high end devices.

3.- Higher radix processing shortens calculation delay

Radix increase (above 2), when it's done, and it comes the cost of more transistors, it is done to shorten calculation times.