(New page: = 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 use...) |
|||
| Line 1: | Line 1: | ||
| − | = Embedded Fixed Point FFT = | + | = Embedded Fixed Point FFT = |
| − | ==== Motivation and Background ==== | + | ==== 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 [https://engineering.purdue.edu/VISE/ee438L/lab6/pdf/lab6b.pdf 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 < | + | 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 [https://engineering.purdue.edu/VISE/ee438L/lab6/pdf/lab6b.pdf 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 <span class="texhtml">2<sup>''n''</sup></span>, where n is the bit number. For binary fractions, the most significant bit corresponds to <span class="texhtml">''n'' = − 1</span>, the next bit to <span class="texhtml">''n'' = − 2</span>, and so on. This allows for storing a number between 0 and <span class="texhtml">1 − 2<sup> − ''N''</sup></span>, 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. |
| + | |||
| + | ==== Application Overview ==== | ||
| + | |||
| + | The example application will apply a 16 point FFT to an incoming signal using the 9S12C Microcontroller. There is an external analog LPF that bandlimits the signal to 20kHz. The audio is sampled at 44100 Hz, the typical audio sampling frequency. Each number is quantized to a signed 8 bit character. The The "twiddle factors" <math>W_{16}^{k}</math> are precalculated and stored in memory as #define statements. This allows the compiler to optimize math operations for the microcontroller. Because of the symmetric nature of the twiddle factors, 8 numbers are required (rather than all 16). The display needs to update at least every 1/60th of a second. This allows for persistance of vision to fill in the gaps between samples on the display. The 9S12C is operating at a clock speed of 24MHz, so in 1/60th of a second, the processor can use 400,000 clock cycles per calculation (ideally). There is overhead code required for the display and other operations, so it is important to avoid pushing the limit. Additionally, since the 9S12C is an 8 bit microcontroller, all 16 bit operations cannot be performed only by the ALU and the compiler must create assembly code that performs the desired operations. Another aspect of the calculation is finding the magnitudes of the numbers. Performing a square root is very computation intensitive, so the norm squared is often used if the actual magnitude isn't needed. In this application, the square root was calculated iteratively. | ||
| + | |||
| + | ==== C Code ==== | ||
| + | |||
| + | The C code for the calculation is included below. Unlike with MATLAB or C on a computer, recursion cannot be used on a microcontroller because of the risks of stack overflow. This required iterating through the FFT algorithm and writing each stage independently. | ||
Revision as of 08:45, 18 December 2014
Contents
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 2n, 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.
Application Overview
The example application will apply a 16 point FFT to an incoming signal using the 9S12C Microcontroller. There is an external analog LPF that bandlimits the signal to 20kHz. The audio is sampled at 44100 Hz, the typical audio sampling frequency. Each number is quantized to a signed 8 bit character. The The "twiddle factors" $ W_{16}^{k} $ are precalculated and stored in memory as #define statements. This allows the compiler to optimize math operations for the microcontroller. Because of the symmetric nature of the twiddle factors, 8 numbers are required (rather than all 16). The display needs to update at least every 1/60th of a second. This allows for persistance of vision to fill in the gaps between samples on the display. The 9S12C is operating at a clock speed of 24MHz, so in 1/60th of a second, the processor can use 400,000 clock cycles per calculation (ideally). There is overhead code required for the display and other operations, so it is important to avoid pushing the limit. Additionally, since the 9S12C is an 8 bit microcontroller, all 16 bit operations cannot be performed only by the ALU and the compiler must create assembly code that performs the desired operations. Another aspect of the calculation is finding the magnitudes of the numbers. Performing a square root is very computation intensitive, so the norm squared is often used if the actual magnitude isn't needed. In this application, the square root was calculated iteratively.
C Code
The C code for the calculation is included below. Unlike with MATLAB or C on a computer, recursion cannot be used on a microcontroller because of the risks of stack overflow. This required iterating through the FFT algorithm and writing each stage independently.
