# How to avoid FFT Bit Growth?

I try to implementation radix-2 DIT FFT algorithm in FPGA. However, I don't understand that how to set to bit growth for multiply and add process of twiddle factor and input data.

For instance, my input data is 13 bit signed number with a fraction of 0 bit (sfix13_0) and my twiddle factor is 16 bit signed number fraction is 15 bit (sfix16_15). So first step is multiply these two numbers. After that, I add first sample of input and output of multiply operation . I get 32 bit signed number with a fraction of 15 bit. There is the problem is that if I do 10 stages for FFT algorithm, my output has really big bit depth.

How to set bit depth after multiply and add operations for every stage? What kind of operation should be done without spoiling the FFT result and how can we explain it theoretically?

For example, I simulate bit growth in MATLAB for 16 point FFT and 4 stages. However, I reach 128 bit signed number with 60 bit fraction. I think if I apply this approach for 10 stages, the output would be achieved very very high bit depths.

This image has input and output data. In the left hand side in picture shows inputs, in the right hand side in the picture show outputs, middle in the picture shows multiply and add operations (called butterfly).

How can I handle this bit growth especially integer part while doing 1024 point FFT?

• the best thing to do is Block Floating Point. It is essentially fixed-point, but with a single exponent word that applies to the entire FFT data array. You want to initially pad two bits on the left, so if your fixed-point (now an integer) signal is varying from $-2^{15}$ to $+2^{15}$, you want to scale it so that it varies as from $-2^{13}$ to $+2^{13}$. Then in doing the FFT, if any computed result exceeds that $2^{13}$ magnitude, we get to set a flag that will shift the FFT values by nudging them over a bit in the following pass. Nov 14, 2021 at 23:50

Fixed point FFT is tricky. Unfortunately this depends a lot on the class of signals that you are dealing with.

how can we explain it theoretically?

$$X[k] = \frac{1}{\sqrt{N}}\sum_{n=0}^{N-1}x[n] \cdot e^{-j2\pi\frac{kn}{N}}$$

This preserves the energy in both domains, i.e. $$\sum x^2[n] = \sum |X[k]|^2$$.

If you apply this to "noise like" signals, the output will generally have the same range of amplitudes than the input, so just adding a few guard bits will do the trick.

However, if you apply it to a sine wave, the peak amplitude will be about $$\sqrt{N}$$ larger, that means you need at least $$\log_2(N)/2$$ guard bits to accommodate the very large crest factor of the frequency domain signal.

How to set bit depth after multiply and add operations for every stage?

That depends lot on the specific requirements of your implementation: what is the required SNR, what are the types of input signals , how sensitive are you against occasional clipping, etc. This is always a trade off between signal to noise ratio, risk of clipping (which is just a different type of noise) and how much bits you want to spend.

1. use $$\sqrt{N}$$ scaling, i.e. right shift by 1 the results of every second stage