FPGA Intellectual Property
PCI Express*, Networking and Connectivity, Memory Interfaces, DSP IP, and Video IP
6513 Discussions

FFT - block floating point scaling (AN 404)

Altera_Forum
Honored Contributor II
1,626 Views

I have been trying to understand some equations mentioned in AN404, I was wondering whether someone can help me out. 

 

The equations are: 

P = ceil(log4(N)) 

R = 1 if log2(N) is odd and 0 if log2(N) is even 

 

(1) Single output engine: maximum: -3P+R minimum: P+R-4 

(2) Quad output engine: maximum: -3P+R+1 minimum: P+R-7 or (P+R-4)-3 

 

I know that: 

  • P is equal to the number of 4 input butterflies 

  • R is the# of 2-input butterfly that is needed, i.e. if log2(N) is even, then you do not need 2-input butterfly. 

 

 

This is what I understand about the maximum equations. 

  • -3P (for total# of multiplier in the 4-input butterflies)  

  • + R (in a 2 input butterfly, you either add or subtract, and the subtraction can potentially decrease the scaling value). 

 

 

For each 4-input butterfly, there are 3 complex multipliers, with that I can understand -3P+R. With that being said, I am not sure why quad output is one more than single output for maximum. How does one justify the 1? 

 

For the minimum equations, this is what I understand: 

  • P + R is the total# of stages, it is assuming that scaling value can go up by one at each stage. 

 

 

However, I am not sure why: 

  1. Why single output engine is three more than quad output? 

  2. Also where does the -4 come from? 

0 Kudos
1 Reply
Altera_Forum
Honored Contributor II
848 Views

I think I figured out those equations myself... 

 

Minimum: 

  • Single: -3P + R 

  • Quad: -3P + R + 1 

 

 

-3P => P is# of 4-input butterfly unit and 3 is maximum# of bits growth per each 4-input butterfly unit 

 

R => for the last stage, either a 4 or a 2 -input butterfly. The 2-input butterfly unit discards one less bit than the 4-input butterfly unit. 

 

1 => I am assuming that this is purely due to implementation differences between Quad and Single. 

 

Also several assumptions are made to derive the maximum outputs: 

1) If scaling occurs, each stage (4-input butterfly unit) can scale up to maximum of 4. 

2) Assuming that no scaling occurs for the last stage of quad 

3) Assuming that no scaling occurs during the first stage. 

4) P and R => total# of 4-input and 2-input butterfly units respectively  

 

Given the above assumptions, then the equations for maximum are: (minimum) + (max amount of scaling) 

 

Single : (-3P + R) + ((P-1)*4) = P+R -4 

Quad : -(3P + R + 1) + ((P-2)*4) = P+R-7 

 

Seeing how equations work out... my assumptions are probably correct then...
0 Kudos
Reply