Complex DFT and FFT Algorithm Implementation Using C++ Programming Language

All four types of Fourier Transform family can be carried out with either real number or complex number. In my previous post, I shared how to implement real DFT algorithm using C++. In this post, I will implement the complex number version of DFT algorithm using C++. After that, I will also implement the Fast Fourier Transform (FFT) algorithm. FFT is another method for calculating the DFT. While it produces the same result as the DFT algorithm, it is incredibly more efficient, often reducing the computation time by hundreds. The algorithm that I use in this post is based on The Scientist and Engineer's Guide to Digital Signal Processing book. This book is very good for beginner to learn DSP.

The complex DFT transforms two N point time domain signals into two N point frequency domain signals. The two time domain signals are called the real part and the imaginary part, just as are the frequency domain signals. You can calculate the real DFT using complex DFT by move the N point signal into the real part of the complex DFT's time domain, then set all of the samples in the imaginary part to zero. Samples from 0 to N/2 of complex DFT correspond to the real DFT's spectrum.

ARM Cortex-M3 (STM32F103) Project - 32 Point DFT Audio Spectrum Analyzer

In this project, I made an audio spectrum analyzer project using ARM Cortex-M3 (STM32F013C8) and LCD 16x2. This project is the application of the real DFT algorithm from my previous post. I used 32 point real DFT for this project. 32 point DFT will transform 32 samples of time domain signal to 17 point frequency domain signal. The first point of frequency domain signal is DC. I will only display AC part (16 point) of frequency domain signal, which is from index 1 to 17 into 16 columns of LCD 16x2.

My audio sampling rate is 35.15kHz. So, the maximum frequency domain signals that can be displayed is up to 17.5kHz (Nyquist's theorem) and the resolution is 17.5kHz/16≈1kHz.

The circuit for this project is same with the circuit for my simple audio effect project. The only differences is the LCD 16x2 and there is no dip switch circuit. You can see the detail about this circuit on this post. For the LCD, I used the custom character feature to create 8 type of bar graph. If you want to learn how to create custom char on LCD 16x2, you can see this tutorial.

Real DFT Algorithm Implementation Using C++ Programming Language

Fourier analysis is a family of mathematical techniques for decomposing signals into sinusoids. Discrete Fourier Transform (DFT) is one of the Fourier transform family. There are four types of Fourier transform:

• Fourier Transform: is used for signals that are continious and aperiodic.
• Fourier Series: is used for signals that are continious and periodic.
• Discrete Time Fourier Transform (DTFT): is used for signals that are discrete and aperiodic.
• Discrete Fourier Transform (DFT): is used for signals that are discrete and periodic.

The only type of Fourier transform that can be used in DSP is the DFT. Because digital computers can only work with information that is discrete and finite in length. Real DFT is a version of the DFT that uses real numbers to represent the input and output signals. While the DFT is uses complex numbers to represent the input and output signals. In this post I will focus on how to implement real DFT algorithm using C++. This post is based on The Scientist and Engineer's Guide to Digital Signal Processing book. This book is very good for beginner to learn DSP.