2
$\begingroup$

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.

I add MATLAB output:

enter image description here

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?

$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$ Nov 14, 2021 at 23:50

1 Answer 1

3
$\begingroup$

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?

Let's start with the energy conserving definition of the FFT

$$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.

I would start with

  1. use $\sqrt{N}$ scaling, i.e. right shift by 1 the results of every second stage
  2. All the twiddle factors are equal or smaller than 1. You can represent them as Q0.15
  3. Your data is Q13.0 so a multiplication would result in Q13.15
  4. For a 1024 bit FFT you should add at least 5 guard bits, so all intermediate results and the output should probably be in Q18.15 or Q19.15.
  5. Perform all butterflies with the data in Q19.15 and the twiddle factors in Q0.15. Truncate the result down to Q19.15 and repeat.
  6. Scale every second stage by 0.5 (right shift) or scale every stage by sqrt(0.5) if it's cheap to do so.
  7. Your output will be in Q19.15, so you can truncate/round this back to whatever format or bit depth you need. You just need to make sure you can accommodate the crest factor of the output
  8. If you are limited to 32 bits, then I would go with Q18.13 and the twiddles in Q0.13. You'll take a 12 dB hit in signal to noise ratio, but that may be good enough.
$\endgroup$
2
  • $\begingroup$ Good answer, maybe maybe you should suggest rounding instead of truncating. $\endgroup$
    – Ben
    Nov 13, 2021 at 23:16
  • $\begingroup$ Really thank you so much @Hilmar. Your explanation is really stimulate, especially part of bit truncate and energy conversion relation. $\endgroup$
    – bb0667
    Nov 17, 2021 at 20:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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