Minimum bit-width for fixed point FFT outputs

Question

I was wondering if there is a formula to determine what the best case (minimum) bit-width should be for the imaginary and real outputs of an fixed-point FFT, assuming an input bit width of $M$ ($M$ bits for the real and $M$ bits for the imaginary portion of the input). Best case meaning there is no possibility of overflow, and I maintain the same number of fractional bits as the input.

I can sort of see that for a $N$-point FFT, there will be $\log_2(N)$ butterfly "passes" or "columns", and always the twiddles have complex magnitude of $1.0$, so a simple assumption would be: $M + \log_2(N)$. I think this is treating it as a worst-case adder assumption. But I know that the twiddles vary a lot after the first column, so this is probably not "best case" analysis.

Answer 1

it really depends on how the DFT is defined. usually we define the DFT and inverse DFT as:

$$ X[k] = \sum\limits_{n=0}^{N-1} x[n] \ e^{-j 2 \pi \tfrac{nk}{N}} $$

$$ x[n] = \frac{1}{N} \sum\limits_{k=0}^{N-1} X[k] \ e^{+j 2 \pi \tfrac{nk}{N}} $$

but they could just as well be defined as

$$ X[k] = \frac{1}{N} \sum\limits_{n=0}^{N-1} x[n] \ e^{-j 2 \pi \tfrac{nk}{N}} $$

$$ x[n] = \sum\limits_{k=0}^{N-1} X[k] \ e^{+j 2 \pi \tfrac{nk}{N}} $$

all of the theorems work exactly the same, except there will be a scaling difference in the convolution theorem and Parseval's theorem.

and, my suggestion, for fixed-point arithmetic is splitting the difference:

$$ X[k] = \frac{1}{\sqrt{N}} \sum\limits_{n=0}^{N-1} x[n] \ e^{-j 2 \pi \tfrac{nk}{N}} $$

$$ x[n] = \frac{1}{\sqrt{N}} \sum\limits_{k=0}^{N-1} X[k] \ e^{+j 2 \pi \tfrac{nk}{N}} $$

now, let's assume for shits and grins that $N$ is a power of 2, so there will be $\log_2(N)$ passes in the fixed-point FFT code.

in the first definition (at top), in the inverse FFT, there will be a division by 2 (an arithmetic shift right) for the results of the FFT butterflies in each inverse FFT pass (and none of this in the forward FFT). $X[k]$ will have a mean square that is $N$ times bigger than the mean square of $x[n]$. so $x[n]$ might be expected to padded with $\log_2(N)$ extended sign bits on the left to keep $X[k]$ from getting too big for the word width.

in the second definition (in the middle), the roles are reversed and in the forward FFT, there will be a division by 2 for every FFT butterfly. so, since the magnitude of $x[n]$ is expected to grow for each FFT pass, then $X[k]$ should be padded with $\log_2(N)$ guard bits on left.

in the third definition, $X[k]$ and $x[n]$ both have the same mean square or the same energy. and in both the forward and inverse FFT, for every alternate FFT pass, the outputs of the butterflies are divided by 2. now having the same mean square does not guarantee that word width limits are not exceeded. if the words going into the first FFT (i'll assume the first FFT is the forward FFT) are padded with $\tfrac12 \log_2(N)$ guard bits, then i would not expect any overflow. and if the processing in the frequency domain preserves the mean-square of $X[k]$, then i would not expect any overflow in the inverse FFT.

one totally different trick, if you have the code to efficiently do this, is to do "block-floating-point" arithmetic for the FFT. but that might not be a very fast FFT because it requires testing the magnitude of the outputs of each butterfly. the Mot DSP56002 and later chips (from the 1990s) had a sticky-bit in the status register that automatically detected this bit-width growth, and a selectable "divide-by-2" mode on the outputs, which both facilitated a very efficient block-floating-point FFT in the fixed-point processor.

Answer 2

Eventhough I have not implemented a fixed-point FFT before, here is answer for integer based representation for which I could still say that, as you have shortly defined, the minimum bit-width to create a proper dynamic range (to avoid clipping or overflow) of the output of an $N$-point FFT is determined by the expected maximum amplitude at the FFT output.

Therefore considering the worst case scenario as an input $x[n]$ with a fixed value of $K$ for all $n$, for which the maximum output occurs at index $k=0$ of a DFT $X[k]$, which measures the DC content. Then $X[0] = K\cdot N$. The number of bits required to hold this number is found as: $$n_{bits} = \lceil \log_2(KN) \rceil = \log_2(K) + \lceil \log_2(N) \rceil = M + \lceil \log_2(N) \rceil$$

Also including the sign bit: $n_{bits} = 1 + M + \lceil \log_2(N) \rceil$

This number of bits is specifically required at the outermost stage of the butterfly structure which requires the maximum number of bits. Due to the most general implementation of inplace computations, eventhough initial stages may require less number of bits, you will still use the maximum required bits to hold all those intermediate values which are bounded by the expected maximum as we used above.