2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Can you specifically define your fixed point representation? I misunderstood it as an integer and provided an answer, but I think you should describe your fractional point as well, to define the maximum representable range with that given fixed point format. $\endgroup$ – Fat32 May 23 '16 at 20:54
  • $\begingroup$ Fat, it doesn't really matter what the specific fixed-point representation is. what is needed is knowing how many "guard bits" on the left are needed, and as shown below, that depends on the specific definition of the fixed-point DFT. $\endgroup$ – robert bristow-johnson May 24 '16 at 6:19
  • $\begingroup$ You don't want best case in practice. Your input is already quantized, so it has an SNR. Define an acceptable SNR loss and spread that out over each pass. $\endgroup$ – Michael Grant May 24 '16 at 12:14
  • $\begingroup$ @robertbristow-johnson that is I think what I wanted to ask. Number of fractional bits and those guard bits as you defined. But then what does the minimum bits refer to? the guard bits or the guard bits plus the fractional bits? $\endgroup$ – Fat32 May 24 '16 at 13:42
  • 1
    $\begingroup$ I'm actually more concerned with the number of "guard bits" to prevent overflow. $\endgroup$ – user2913869 May 24 '16 at 13:54
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Interesting! Block-floating-point seems like it could be very advantageous in a hardware implementation (such as on an FPGA). Thanks for the tips! $\endgroup$ – user2913869 May 24 '16 at 14:13
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ In my experience this gives an extremely conservative result. If you go experimentally you can save quite a bit. $\endgroup$ – Michael Grant May 24 '16 at 12:12
  • $\begingroup$ Besides, the complex twiddle factors are irrational so no number of bits is enough to avoid loss. $\endgroup$ – Michael Grant May 24 '16 at 12:15
  • $\begingroup$ @Michael Grant I think I have provided something not the OP was actually looking for, but anyway, here I provided the necessary number of integer bits to hold the full dynamic range of the output of an FFT based on N samples. imho the fixed point implementation should also provide a resolution requirement so as to find the actual number of bits to hold the dynamic range... $\endgroup$ – Fat32 May 24 '16 at 13:39
  • 1
    $\begingroup$ I do want to do what I'm asking, Michael Grant, because I need the FFT answer guaranteed to be correct. There are a plethora of mission critical applications that are required to put more computation and resources in order to guarantee that there will be no overflow. I was simply wondering if I could reduce my integer bit count AND guarantee no overflow. $\endgroup$ – user2913869 May 24 '16 at 14:08
  • 1
    $\begingroup$ ? I'm afraid I don't understand. I'm just saying that you and others are doing just fine answering his question and I will bow out! $\endgroup$ – Michael Grant May 25 '16 at 11:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.