FFT on ATMega32 - Fourier Analysis

When I was studying at King’s College, I remember the professor started out the class explaining that a periodic function with a base frequency ω can be written as a sum of sines and cosines whose frequencies are integer multiples of ω.

The sum of sine and cosine terms representing a complex periodic function is something Jean Baptiste Joseph Fourier thought of. He was a Frenchman who lived from 1768 to 1830.

Interestingly, Fourier was not noble-born. He was not aristocratic or blue-blooded and therefore not allowed to work with all the other "toffs" of that time; however, his skills and aptitude were the same as Newton’s.

Learning about the Fast Fourier Transform (FFT) and signal processing was one of the reasons why I decided to study Electronic Engineering in 1992. Unfortunately, the only place I could afford to study was at my local college in Croydon.

I have always been very interested in the implementation of the FFT. At university, I wrote my first program in C utilising a DFT algorithm. Later, I wrote another program implementing a FFT algorithm. Although C was fast, I realised that I could make it faster using assembly language.

In 2004, I ported my assembly language code to the AVR microcontrollers. Fourier was also one of the reasons why I decided to continue assembly language and keep up my practice. My current FFT implementation for the ATMega32 is in assembly language, and is the fastest utilising the built in hardware multiplier.

When most engineers evaluate the ATMega32, they tend to focus on blinking LEDs, and port operations. They do not realise that it has powerful math functions. The MAC (Multiply and Accumulate) feature is hardware based and performs very fast multiplication operations, which is ideal for implementing FFT algorithms.

Domains, Spatial, and Space

Understanding Fourier transforms is actually very simple; however, the problem is with the mathematicians because they love to invent confusing new terms, and since only they know their language it all becomes closed off to others.

Time varying data is in the time domain; however, some books will also refer to this as space varying data.

Frequency varying data is in the frequency domain however, some books refer to this as frequency space, and spatial frequency.

The total energy contained in a signal will be the same in both the time domain and the frequency domain; however, Fourier analysis allows one to see how that energy distributes in the time domain and how it distributes in the frequency domain.

This Article Continues...