Embedded Fixed Point FFT

Motivation and Background

Performing an FFT analysis on incoming signals can be used in many applications. Frequency analysis of signals can be used in fields as diverse as compression to sound visualization. Additionally, real time FFT analysis can be useful when debugging RF and audio systems as well as analyzing EMI compliance. In Week 2 of the DFT lab, a recursive FFT was implemented in MATLAB. It was found that this FFT was significantly faster than performing a DFT; however, the system performing the math was significantly more powerful than an embedded microprocessor. Performing frequency analysis on a microcontroller adds many additional layers of complexity, stemming from quantization issues of the analog to digital converters, memory limitations, and perhaps most importantly- fixed point arithmetic. Applications such as MATLAB utilize floating point numbers. These numbers have a fixed number of significant figures but can have the decimal point moved in the number. Many microcontrollers and embedded FFT algorithms utilize binary fractions. Binary numbers have each bit correspond to a $ 2^{n} $, where n is the bit number. For binary fractions, the most significant bit corresponds to $ n=-1 $, the next bit to $ n=-2 $, and so on. This allows for storing a number between 0 and $ 1-2^{-N} $, where N is the number of bits in the stored number. This has some obvious limitations including but not limited to the fact that numbers cannot be stored that are greater than one and resolution is limited to powers of 2. This adds some issues to FFT calculation in the embedded world, but it can all be worked around. In the example application, an FFT audio visualizer will be created to demonstrate the fixed point FFT.