FFT Fast Fourier Transform algorithm suitable for single-chip microcomputer, 51 single-chip microcomputer can be used

#define Sample_Frequency 800 //Sampling frequency 800Hz

#define Frequency 100 //Test signal 100Hz

for (i = 0; i < FFT_N; ++i) //Use the Refresh_Data(Compx, i, wave_data) function to fill in data. Here, a 100Hz square wave test signal is created.

{ 

if (sin(2 * PI * Frequency * i / Sample_Frequency) > 0)

Refresh_Data(Compx, i, 1);

else if (sin(2 * PI * Frequency * i / Sample_Frequency) < 0)

Refresh_Data(Compx, i, -1);

else

Refresh_Data(Compx, i, 0);

}

create_sin_tab(SIN_TAB); //Create a sine signal table, and then use the table lookup method to calculate the sine value to speed up the calculation

FFT(Compx); //Fast Fourier Transform

Get_Result(Compx, Sample_Frequency); //Get the modulus of the transformed result, store it in the real part of the complex number, store the frequency in the imaginary part of the complex number, and the valid data is the first FFT_N/2 numbers

Effect

Method to calculate frequency:

The sampling frequency is 800Hz, with a total of 16 points, so one grid = 800Hz / 16 = 50 Hz

As shown in the figure, there is a peak in the third grid and the seventh grid respectively, and the corresponding frequencies are 2 x 50Hz = 100Hz and 6 x 50Hz = 300Hz. The results have been calculated by the Get_Result function and stored in the imaginary part of the original array.

For an interpretation of the physical meaning, see How to use FFT (Fast Fourier Transform) to find amplitude and frequency (very detailed including the derivation process) - Xav Pan

performance

Crystal frequency 11.0592MHz 6T mode (22.1184MHz 12T)

The simulation time is about 0.13222819 - 0.06633789 = 0.0658903 (s)

That is, to complete a 16-point FFT transformation, the 11.0592MHz 6T 51 microcontroller takes 65.8903 ms.

The same program, using Vs 2015, runs 65536 points and the calculation results are:

The same data is calculated using Python for 800 points:

Source: The most detailed tutorial on implementing Fast Fourier Transform (FFT) using Python (scipy and numpy) - LoveMIss-Y

Other parts of the code

For some codes of dot matrix screen, please refer to [51 MCU Quick Start Guide] 2.4: IO Expansion (Serial to Parallel) and LED Dot Matrix Screen

main.c

#include

#include "intrins.h"

#include "stdint.h"

#include "FFT.h"

#include

#include "HC74595.h"

void main(void)

{

uint8_t i, j; 

double Largest = 0;

#define Sample_Frequency 800 //Sampling frequency 800Hz

#define Frequency 100 //Test signal 100Hz

for (i = 0; i < FFT_N; ++i) //Use the Refresh_Data(Compx, i, wave_data) function to fill in data. Here, a 100Hz square wave signal is created.

{ 

if (sin(2 * PI * Frequency * i / Sample_Frequency) > 0)

Refresh_Data(Compx, i, 1);

else if (sin(2 * PI * Frequency * i / Sample_Frequency) < 0)

Refresh_Data(Compx, i, -1);

else

Refresh_Data(Compx, i, 0);

}

create_sin_tab(SIN_TAB); //Create a sine signal table, and then use the table lookup method to calculate the sine value to speed up the calculation

FFT(Compx); //Fast Fourier Transform

Get_Result(Compx, Sample_Frequency); //Get the modulus of the transformed result, store it in the real part of the complex number, store the frequency in the imaginary part of the complex number, and the valid data is the first FFT_N/2 numbers

for (i = 0; i < FFT_N / 2; ++i) // Process the calculation results into the image part

{         

if(Compx[i].real > Largest)

Largest = Compx[i].real;

}

for(i = 0; i < 8; ++i)

{

for(j = 0; j < (uint8_t)((Compx[i].real / Largest) * 8 + 0.5); ++j)

Mat[8 - j - 1][i] = 1;

}

while(1)

{

imshow(Mat); //Display image

}

}