摘要：傅里葉變換的核心在于，“任何連續(xù)周期信號(hào)可以由一組適當(dāng)?shù)恼仪€組合而成”，在這個(gè)基礎(chǔ)上對(duì)信號(hào)的中特定頻率的正弦波進(jìn)行分解或者重組，基于頻率方面分析波形。

1、傅里葉變換的意義

近似周期性的方波（橙色），可采用6組正弦波（藍(lán)色）合成，這是傅里葉的基礎(chǔ)。

對(duì)數(shù)字信號(hào)處理或者工程數(shù)學(xué)有一定基礎(chǔ)，就明白傅里葉變換的價(jià)值。一般情況下的信號(hào)或者波形隨時(shí)間變化，稱為時(shí)域信號(hào)，時(shí)域（Time domain）是描述數(shù)學(xué)函數(shù)或物理信號(hào)對(duì)時(shí)間的關(guān)系。而以頻率和幅度表示信號(hào)稱為頻域，頻域（frequency domain）是描述信號(hào)在頻率方面特性時(shí)用到的一種坐標(biāo)系。其數(shù)學(xué)理論上暫且不理，針對(duì)嵌入式系統(tǒng)開(kāi)發(fā)，只探討其物理意義或者應(yīng)用場(chǎng)景。

時(shí)域和頻域是信號(hào)的基本性質(zhì)，時(shí)域的表示較為形象與直觀，比較符合一般認(rèn)知，而頻域分析則更為簡(jiǎn)練，剖析問(wèn)題更為深刻和方便。

例如下圖的左側(cè)時(shí)域信號(hào)，其可以分解為2路正弦波的疊加效果，右側(cè)為頻域信號(hào)，表示2路正弦波的頻率和幅度。傅里葉變化可簡(jiǎn)單理解為求解一段信號(hào)或波形，由哪些正弦波組成，也可以反向推導(dǎo)多路正弦波合并后的效果。

基于動(dòng)畫形式表現(xiàn)如下：

傅里葉變換是一種信號(hào)分析方法，讓我們對(duì)信號(hào)的構(gòu)成和特點(diǎn)進(jìn)行深入的、定量的研究。把信號(hào)通過(guò)頻譜的方式進(jìn)行準(zhǔn)確的、定量的描述。將原來(lái)難以處理的時(shí)域信號(hào)轉(zhuǎn)換成了易于分析的頻域信號(hào)，即傅里葉變換的核心是從時(shí)域到頻域的變換。

2、變換方式

數(shù)字信號(hào)屬于離散值，對(duì)應(yīng)的稱為離散傅里葉變換（DFT），是傅里葉變換在時(shí)域和頻域上都呈現(xiàn)離散的形式，將時(shí)域信號(hào)的采樣變換為在離散時(shí)間傅里葉變換（DTFT）頻域的采樣。在形式上，變換兩端（時(shí)域和頻域上）的序列是有限長(zhǎng)的，而實(shí)際上這兩組序列都應(yīng)當(dāng)被認(rèn)為是離散周期信號(hào)的主值序列。即使對(duì)有限長(zhǎng)的離散信號(hào)作DFT，也應(yīng)當(dāng)將其看作經(jīng)過(guò)周期延拓成為周期信號(hào)再作變換。

在實(shí)際應(yīng)用中通常采用快速傅里葉變換以高效計(jì)算效率，快速傅里葉變換 FFT（Fast Fourier Transformation）是離散傅里葉變換 DFT（Discrete Fourier Transform）的快速算法。采用這種算法能使計(jì)算機(jī)計(jì)算離散傅里葉變換所需要的乘法次數(shù)大為減少，特別是被變換的抽樣點(diǎn)數(shù)N越多，F(xiàn)FT算法計(jì)算量的節(jié)省就越顯著。同理，從頻域到時(shí)域的變換，稱為逆變換，快速傅里葉逆變換 IFFT和離散傅里葉逆變換IDFT。

3、應(yīng)用

一般嵌入式系統(tǒng)使用快速傅里葉變換是分析某段信號(hào)中混合的雜波干擾，或者剔除某個(gè)頻段后再逆變換。有些高端示波器可以對(duì)信號(hào)快速傅里葉變換 FFT，直接顯示高頻雜波的頻率或者較大幅度干擾源的頻率，以便由針對(duì)性的檢查電路竄擾。本文主要是講解使用fft/ifft進(jìn)行干擾信號(hào)的過(guò)濾。

1、python生成正弦波，以及混合波形，提取數(shù)值作為c語(yǔ)言FFT/IFFT的數(shù)據(jù)源 

2、先進(jìn)行FFT，輸出幅頻數(shù)據(jù)，導(dǎo)入Excel看看效果 

3、對(duì)數(shù)據(jù)進(jìn)行簡(jiǎn)單過(guò)濾

4、過(guò)濾后的數(shù)據(jù)進(jìn)行IFFT運(yùn)算，再導(dǎo)入Excel看還原的效果 

5、關(guān)注微信公眾號(hào)  嵌入式系統(tǒng)

3.1 基于python生成數(shù)據(jù)源

# This is a Python script.

import numpy as np
import matplotlib.pyplot as plt
def sin_wave(A, f, fs, phi, t):
    '''
    :params A:    振幅
    :params f:    信號(hào)頻率
    :params fs:   采樣頻率
    :params phi:  相位
    :params t:    時(shí)間長(zhǎng)度
    '''
    # 若時(shí)間序列長(zhǎng)度為 t=1s,
    # 采樣頻率 fs=1000 Hz, 則采樣時(shí)間間隔 Ts=1/fs=0.001s
    # 采樣點(diǎn)個(gè)數(shù)為 n=t/Ts=1/0.001=1000, 即有1000個(gè)點(diǎn),每個(gè)點(diǎn)間隔為 Ts
    Ts = 1/fs
    n = t / Ts
    n = np.arange(n)
    y = A*np.sin(2*np.pi*f*n*Ts + phi*(np.pi/180))
    return y

fs = 360*40
my_sin1 = sin_wave(100, 100, fs=fs, phi=0, t=0.08)
my_sin2 = sin_wave(20, 500, fs=fs, phi=0, t=0.08)
my_sin3 = sin_wave(10, 1100, fs=fs, phi=0, t=0.08)

x = np.arange(0, 0.08, 1/fs)
plt.xlabel('x-t (samRate=14400)')
plt.ylabel('y-A')
plt.grid()
plt.plot(x, my_sin1, 'k--',label="f=100")
plt.plot(x, my_sin2, 'b--',label="f=500")
plt.plot(x, my_sin3, 'g--',label="f=1100")
plt.plot(x, my_sin1+my_sin2+my_sin3, 'r',label="mix")
plt.legend()
plt.show()

np.savetxt("sin.txt",my_sin1+my_sin2+my_sin3, fmt='%.06f')

def print_name(name):
    print(f'Hi, {name}')


if __name__ == '__main__':
    print_name('fft test')

生成的波形圖如下：

三種頻率的sin以及合成后的紅色曲線，變形的正弦波；同時(shí)也將數(shù)據(jù)存入文件sin.txt備用。

3.2 基于C驗(yàn)證算法

將前面生成的數(shù)據(jù)使用c語(yǔ)言的FFT/IFFT進(jìn)行處理，輸出結(jié)果，并導(dǎo)入Excels生成圖表展示效果。

#include <math.h>
#include <stdio.h>
#include "string.h"

typedef struct
{
    float real;
    float imag;
} complex_t;

#ifndef PI
#define PI             (3.14159265)
#endif

#define TYPE_FFT_E     float    /* Type is the same with complex_t member */

typedef complex_t TYPE_FFT;  /* Define complex_t in Config.h */
typedef unsigned int                      uint32_t;

#define     SAMPLE_NODES    (1024)
complex_t   fft_buff[SAMPLE_NODES];

//python生成的3個(gè)sin混合的波形數(shù)組
float my_sin_wave_table[] =
{
    0.000000,13.308217,25.359460,35.142296,42.082633,46.140080,47.788611,47.887148,47.470293,47.507139,48.682920,51.252751,
    55.000000,59.307883,63.326941,66.199152,67.286436,66.350198,63.639610,59.866963,56.074110,53.418823,52.928233,55.274323,
    60.621778,68.582540,78.287693,88.561119,98.156743,106.007043,111.428222,114.237346,114.756729,113.706291,112.009861,
    110.560634,110.000000,110.560634,112.009861,113.706291,114.756729,114.237346,111.428222,106.007043,98.156743,88.561119,
    78.287693,68.582540,60.621778,55.274323,52.928233,53.418823,56.074110,59.866963,63.639610,66.350198,67.286436,66.199152,
    63.326941,59.307883,55.000000,51.252751,48.682920,47.507139,47.470293,47.887148,47.788611,46.140080,42.082633,35.142296,
    25.359460,13.308217,0.000000,-13.308217,-25.359460,-35.142296,-42.082633,-46.140080,-47.788611,-47.887148,-47.470293,
    -47.507139,-48.682920,-51.252751,-55.000000,-59.307883,-63.326941,-66.199152,-67.286436,-66.350198,-63.639610,-59.866963,
    -56.074110,-53.418823,-52.928233,-55.274323,-60.621778,-68.582540,-78.287693,-88.561119,-98.156743,-106.007043,-111.428222,
    -114.237346,-114.756729,-113.706291,-112.009861,-110.560634,-110.000000,-110.560634,-112.009861,-113.706291,-114.756729,
    -114.237346,-111.428222,-106.007043,-98.156743,-88.561119,-78.287693,-68.582540,-60.621778,-55.274323,-52.928233,
    -53.418823,-56.074110,-59.866963,-63.639610,-66.350198,-67.286436,-66.199152,-63.326941,-59.307883,-55.000000,
    -51.252751,-48.682920,-47.507139,-47.470293,-47.887148,-47.788611,-46.140080,-42.082633,-35.142296,-25.359460,
    -13.308217,-0.000000,13.308217,25.359460,35.142296,42.082633,46.140080,47.788611,47.887148,47.470293,47.507139,
    48.682920,51.252751,55.000000,59.307883,63.326941,66.199152,67.286436,66.350198,63.639610,59.866963,56.074110,
    53.418823,52.928233,55.274323,60.621778,68.582540,78.287693,88.561119,98.156743,106.007043,111.428222,114.237346,
    114.756729,113.706291,112.009861,110.560634,110.000000,110.560634,112.009861,113.706291,114.756729,114.237346,
    111.428222,106.007043,98.156743,88.561119,78.287693,68.582540,60.621778,55.274323,52.928233,53.418823,56.074110,
    59.866963,63.639610,66.350198,67.286436,66.199152,63.326941,59.307883,55.000000,51.252751,48.682920,47.507139,
    47.470293,47.887148,47.788611,46.140080,42.082633,35.142296,25.359460,13.308217,0.000000,-13.308217,-25.359460,
    -35.142296,-42.082633,-46.140080,-47.788611,-47.887148,-47.470293,-47.507139,-48.682920,-51.252751,-55.000000,
    -59.307883,-63.326941,-66.199152,-67.286436,-66.350198,-63.639610,-59.866963,-56.074110,-53.418823,-52.928233,
    -55.274323,-60.621778,-68.582540,-78.287693,-88.561119,-98.156743,-106.007043,-111.428222,-114.237346,-114.756729,
    -113.706291,-112.009861,-110.560634,-110.000000,-110.560634,-112.009861,-113.706291,-114.756729,-114.237346,-111.428222,
    -106.007043,-98.156743,-88.561119,-78.287693,-68.582540,-60.621778,-55.274323,-52.928233,-53.418823,-56.074110,-59.866963,
    -63.639610,-66.350198,-67.286436,-66.199152,-63.326941,-59.307883,-55.000000,-51.252751,-48.682920,-47.507139,-47.470293,
    -47.887148,-47.788611,-46.140080,-42.082633,-35.142296,-25.359460,-13.308217,-0.000000,13.308217,25.359460,35.142296,
    42.082633,46.140080,47.788611,47.887148,47.470293,47.507139,48.682920,51.252751,55.000000,59.307883,63.326941,66.199152,
    67.286436,66.350198,63.639610,59.866963,56.074110,53.418823,52.928233,55.274323,60.621778,68.582540,78.287693,88.561119,
    98.156743,106.007043,111.428222,114.237346,114.756729,113.706291,112.009861,110.560634,110.000000,110.560634,112.009861,
    113.706291,114.756729,114.237346,111.428222,106.007043,98.156743,88.561119,78.287693,68.582540,60.621778,55.274323,
    52.928233,53.418823,56.074110,59.866963,63.639610,66.350198,67.286436,66.199152,63.326941,59.307883,55.000000,51.252751,
    48.682920,47.507139,47.470293,47.887148,47.788611,46.140080,42.082633,35.142296,25.359460,13.308217,0.000000,-13.308217,
    -25.359460,-35.142296,-42.082633,-46.140080,-47.788611,-47.887148,-47.470293,-47.507139,-48.682920,-51.252751,-55.000000,
    -59.307883,-63.326941,-66.199152,-67.286436,-66.350198,-63.639610,-59.866963,-56.074110,-53.418823,-52.928233,-55.274323,
    -60.621778,-68.582540,-78.287693,-88.561119,-98.156743,-106.007043,-111.428222,-114.237346,-114.756729,-113.706291,
    -112.009861,-110.560634,-110.000000,-110.560634,-112.009861,-113.706291,-114.756729,-114.237346,-111.428222,-106.007043,
    -98.156743,-88.561119,-78.287693,-68.582540,-60.621778,-55.274323,-52.928233,-53.418823,-56.074110,-59.866963,-63.639610,
    -66.350198,-67.286436,-66.199152,-63.326941,-59.307883,-55.000000,-51.252751,-48.682920,-47.507139,-47.470293,-47.887148,
    -47.788611,-46.140080,-42.082633,-35.142296,-25.359460,-13.308217,-0.000000,13.308217,25.359460,35.142296,42.082633,
    46.140080,47.788611,47.887148,47.470293,47.507139,48.682920,51.252751,55.000000,59.307883,63.326941,66.199152,67.286436,
    66.350198,63.639610,59.866963,56.074110,53.418823,52.928233,55.274323,60.621778,68.582540,78.287693,88.561119,98.156743,
    106.007043,111.428222,114.237346,114.756729,113.706291,112.009861,110.560634,110.000000,110.560634,112.009861,113.706291,
    114.756729,114.237346,111.428222,106.007043,98.156743,88.561119,78.287693,68.582540,60.621778,55.274323,52.928233,53.418823,
    56.074110,59.866963,63.639610,66.350198,67.286436,66.199152,63.326941,59.307883,55.000000,51.252751,48.682920,47.507139,
    47.470293,47.887148,47.788611,46.140080,42.082633,35.142296,25.359460,13.308217,0.000000,-13.308217,-25.359460,-35.142296,
    -42.082633,-46.140080,-47.788611,-47.887148,-47.470293,-47.507139,-48.682920,-51.252751,-55.000000,-59.307883,-63.326941,
    -66.199152,-67.286436,-66.350198,-63.639610,-59.866963,-56.074110,-53.418823,-52.928233,-55.274323,-60.621778,-68.582540,
    -78.287693,-88.561119,-98.156743,-106.007043,-111.428222,-114.237346,-114.756729,-113.706291,-112.009861,-110.560634,
    -110.000000,-110.560634,-112.009861,-113.706291,-114.756729,-114.237346,-111.428222,-106.007043,-98.156743,-88.561119,
    -78.287693,-68.582540,-60.621778,-55.274323,-52.928233,-53.418823,-56.074110,-59.866963,-63.639610,-66.350198,-67.286436,
    -66.199152,-63.326941,-59.307883,-55.000000,-51.252751,-48.682920,-47.507139,-47.470293,-47.887148,-47.788611,-46.140080,
    -42.082633,-35.142296,-25.359460,-13.308217,-0.000000,13.308217,25.359460,35.142296,42.082633,46.140080,47.788611,47.887148,
    47.470293,47.507139,48.682920,51.252751,55.000000,59.307883,63.326941,66.199152,67.286436,66.350198,63.639610,59.866963,
    56.074110,53.418823,52.928233,55.274323,60.621778,68.582540,78.287693,88.561119,98.156743,106.007043,111.428222,114.237346,
    114.756729,113.706291,112.009861,110.560634,110.000000,110.560634,112.009861,113.706291,114.756729,114.237346,111.428222,
    106.007043,98.156743,88.561119,78.287693,68.582540,60.621778,55.274323,52.928233,53.418823,56.074110,59.866963,63.639610,
    66.350198,67.286436,66.199152,63.326941,59.307883,55.000000,51.252751,48.682920,47.507139,47.470293,47.887148,47.788611,
    46.140080,42.082633,35.142296,25.359460,13.308217,0.000000,-13.308217,-25.359460,-35.142296,-42.082633,-46.140080,-47.788611,
    -47.887148,-47.470293,-47.507139,-48.682920,-51.252751,-55.000000,-59.307883,-63.326941,-66.199152,-67.286436,-66.350198,
    -63.639610,-59.866963,-56.074110,-53.418823,-52.928233,-55.274323,-60.621778,-68.582540,-78.287693,-88.561119,-98.156743,
    -106.007043,-111.428222,-114.237346,-114.756729,-113.706291,-112.009861,-110.560634,-110.000000,-110.560634,-112.009861,
    -113.706291,-114.756729,-114.237346,-111.428222,-106.007043,-98.156743,-88.561119,-78.287693,-68.582540,-60.621778,-55.274323,
    -52.928233,-53.418823,-56.074110,-59.866963,-63.639610,-66.350198,-67.286436,-66.199152,-63.326941,-59.307883,-55.000000,
    -51.252751,-48.682920,-47.507139,-47.470293,-47.887148,-47.788611,-46.140080,-42.082633,-35.142296,-25.359460,-13.308217,
    -0.000000,13.308217,25.359460,35.142296,42.082633,46.140080,47.788611,47.887148,47.470293,47.507139,48.682920,51.252751,
    55.000000,59.307883,63.326941,66.199152,67.286436,66.350198,63.639610,59.866963,56.074110,53.418823,52.928233,55.274323,
    60.621778,68.582540,78.287693,88.561119,98.156743,106.007043,111.428222,114.237346,114.756729,113.706291,112.009861,
    110.560634,110.000000,110.560634,112.009861,113.706291,114.756729,114.237346,111.428222,106.007043,98.156743,88.561119,
    78.287693,68.582540,60.621778,55.274323,52.928233,53.418823,56.074110,59.866963,63.639610,66.350198,67.286436,66.199152,
    63.326941,59.307883,55.000000,51.252751,48.682920,47.507139,47.470293,47.887148,47.788611,46.140080,42.082633,35.142296,
    25.359460,13.308217,0.000000,-13.308217,-25.359460,-35.142296,-42.082633,-46.140080,-47.788611,-47.887148,-47.470293,
    -47.507139,-48.682920,-51.252751,-55.000000,-59.307883,-63.326941,-66.199152,-67.286436,-66.350198,-63.639610,-59.866963,
    -56.074110,-53.418823,-52.928233,-55.274323,-60.621778,-68.582540,-78.287693,-88.561119,-98.156743,-106.007043,-111.428222,
    -114.237346,-114.756729,-113.706291,-112.009861,-110.560634,-110.000000,-110.560634,-112.009861,-113.706291,-114.756729,
    -114.237346,-111.428222,-106.007043,-98.156743,-88.561119,-78.287693,-68.582540,-60.621778,-55.274323,-52.928233,-53.418823,
    -56.074110,-59.866963,-63.639610,-66.350198,-67.286436,-66.199152,-63.326941,-59.307883,-55.000000,-51.252751,-48.682920,
    -47.507139,-47.470293,-47.887148,-47.788611,-46.140080,-42.082633,-35.142296,-25.359460,-13.308217,-0.000000,13.308217,
    25.359460,35.142296,42.082633,46.140080,47.788611,47.887148,47.470293,47.507139,48.682920,51.252751,55.000000,59.307883,
    63.326941,66.199152,67.286436,66.350198,63.639610,59.866963,56.074110,53.418823,52.928233,55.274323,60.621778,68.582540,
    78.287693,88.561119,98.156743,106.007043,111.428222,114.237346,114.756729,113.706291,112.009861,110.560634,110.000000,
    110.560634,112.009861,113.706291,114.756729,114.237346,111.428222,106.007043,98.156743,88.561119,78.287693,68.582540,
    60.621778,55.274323,52.928233,53.418823,56.074110,59.866963,63.639610,66.350198,67.286436,66.199152,63.326941,59.307883,
    55.000000,51.252751,48.682920,47.507139,47.470293,47.887148,47.788611,46.140080,42.082633,35.142296,25.359460,13.308217,
    0.000000,-13.308217,-25.359460,-35.142296,-42.082633,-46.140080,-47.788611,-47.887148,-47.470293,-47.507139,-48.682920,
    -51.252751,-55.000000,-59.307883,-63.326941,-66.199152,-67.286436,-66.350198,-63.639610,-59.866963,-56.074110,-53.418823,
    -52.928233,-55.274323,-60.621778,-68.582540,-78.287693,-88.561119,-98.156743,-106.007043,-111.428222,-114.237346,-114.756729,
    -113.706291,-112.009861,-110.560634,-110.000000,-110.560634,-112.009861,-113.706291,-114.756729,-114.237346,-111.428222,
    -106.007043,-98.156743,-88.561119,-78.287693,-68.582540,-60.621778,-55.274323,-52.928233,-53.418823,-56.074110,-59.866963,
    -63.639610,-66.350198,-67.286436,-66.199152,-63.326941,-59.307883,-55.000000,-51.252751,-48.682920,-47.507139,-47.470293,
    -47.887148,-47.788611,-46.140080,-42.082633,-35.142296,-25.359460,-13.308217,-0.000000,13.308217,25.359460,35.142296,
    42.082633,46.140080,47.788611,47.887148,47.470293,47.507139,48.682920,51.252751,55.000000,59.307883,63.326941,66.199152,
    67.286436,66.350198,63.639610,59.866963,56.074110,53.418823,52.928233,55.274323,60.621778,68.582540,78.287693,88.561119,
    98.156743,106.007043,111.428222,114.237346,114.756729,113.706291,112.009861,110.560634,110.000000,110.560634,112.009861,
    113.706291,114.756729,114.237346,111.428222,106.007043,98.156743,88.561119,78.287693,68.582540,60.621778,55.274323,52.928233,
    53.418823,56.074110,59.866963,63.639610,66.350198,67.286436,66.199152,63.326941,59.307883,55.000000,51.252751,48.682920,
    47.507139,47.470293,47.887148,47.788611,46.140080,42.082633,35.142296,25.359460,13.308217,0.000000,-13.308217,-25.359460,
    -35.142296,-42.082633,-46.140080,-47.788611,-47.887148,-47.470293,-47.507139,-48.682920,-51.252751,-55.000000,-59.307883,
    -63.326941,-66.199152,-67.286436,-66.350198,-63.639610,-59.866963,-56.074110,-53.418823,-52.928233,-55.274323,-60.621778,
    -68.582540,-78.287693,-88.561119,-98.156743,-106.007043,-111.428222,-114.237346,-114.756729,-113.706291,-112.009861,
    -110.560634,-110.000000,-110.560634,-112.009861,-113.706291,-114.756729,-114.237346,-111.428222,-106.007043,-98.156743,
    -88.561119,-78.287693,-68.582540,-60.621778,-55.274323,-52.928233,-53.418823,-56.074110,-59.866963,-63.639610,-66.350198,
    -67.286436,-66.199152,-63.326941,-59.307883,-55.000000,-51.252751,-48.682920,-47.507139,-47.470293,-47.887148,-47.788611,
    -46.140080,-42.082633,-35.142296,-25.359460,-13.308217,
};

//fft算法來(lái)自開(kāi)源 https://github.com/xiahouzuoxin/fft

const float sin_tb[] =    // 精度(PI PI/2 PI/4 PI/8 PI/16 ... PI/(2^k))
{
        0.000000, 1.000000, 0.707107, 0.382683, 0.195090, 0.098017,
        0.049068, 0.024541, 0.012272, 0.006136, 0.003068, 0.001534,
        0.000767, 0.000383, 0.000192, 0.000096, 0.000048, 0.000024,
        0.000012, 0.000006, 0.000003
        };

const float cos_tb[] =    // 精度(PI PI/2 PI/4 PI/8 PI/16 ... PI/(2^k))
{
        -1.000000, 0.000000, 0.707107, 0.923880, 0.980785, 0.995185,
        0.998795, 0.999699, 0.999925, 0.999981, 0.999995, 0.999999,
        1.000000, 1.000000, 1.000000, 1.000000, 1.000000, 1.000000,
        1.000000, 1.000000, 1.000000
        };


int ones_32(uint32_t n)
{
    unsigned int c = 0 ;
    for(c = 0; n; ++c)
    {
        n &= (n - 1) ;
    }

    return c ;
}


uint32_t floor_log2_32(uint32_t fft_buff)
{
    fft_buff |= (fft_buff >> 1);
    fft_buff |= (fft_buff >> 2);
    fft_buff |= (fft_buff >> 4);
    fft_buff |= (fft_buff >> 8);
    fft_buff |= (fft_buff >> 16);

    return (ones_32(fft_buff >> 1));
}


/*
 * FFT Algorithm
 * === Inputs ===
 * fft_buff : complex numbers
 * N : nodes of FFT. @N should be power of 2, that is 2^(*)
 * === Output ===
 * the @fft_buff contains the result of FFT algorithm, so the original data
 * in @fft_buff is destroyed, please store them before using FFT.
 */
int fft(TYPE_FFT *fft_buff, uint32_t N)
{
    int i, j, l, k, ip;
    static uint32_t M = 0;
    static int le, le2;
    static TYPE_FFT_E sR, sI, tR, tI, uR, uI;

    M = floor_log2_32(N);

    /*
     * bit reversal sorting
     */

    l = N >> 1;
    j = l;
    ip = N - 2;
    for(i = 1; i <= ip; i++)
    {
        if(i < j)
        {
            tR = fft_buff[j].real;
            tI = fft_buff[j].imag;
            fft_buff[j].real = fft_buff[i].real;
            fft_buff[j].imag = fft_buff[i].imag;
            fft_buff[i].real = tR;
            fft_buff[i].imag = tI;
        }

        k = l;

        while(k <= j)
        {
            j = j - k;
            k = k >> 1;
        }

        j = j + k;
    }

    /*
     * For Loops
     */

    for(l = 1; l <= M; l++)  /* loop for ceil{log2(N)} */
    {
        le  = (int)(1 << l);
        le2 = (int)(le >> 1);
        uR = 1;
        uI = 0;

        k = floor_log2_32(le2);
        sR = cos_tb[k];
        sI = -sin_tb[k];

        for(j = 1; j <= le2; j++)  /* loop for each sub DFT */
        {
            for(i = j - 1; i < N; i += le) /* loop for each butterfly */
            {
                ip = i + le2;
                tR = fft_buff[ip].real * uR - fft_buff[ip].imag * uI;
                tI = fft_buff[ip].real * uI + fft_buff[ip].imag * uR;
                fft_buff[ip].real = fft_buff[i].real - tR;
                fft_buff[ip].imag = fft_buff[i].imag - tI;
                fft_buff[i].real += tR;
                fft_buff[i].imag += tI;
            }  /* Next i */

            tR = uR;
            uR = tR * sR - uI * sI;
            uI = tR * sI + uI * sR;

        } /* Next j */

    } /* Next l */

    return 0;
}


/*
 * Inverse FFT Algorithm
 * === Inputs ===
 * fft_buff : complex numbers
 * N : nodes of FFT. @N should be power of 2, that is 2^(*)
 * === Output ===
 * the @fft_buff contains the result of FFT algorithm, so the original data
 * in @fft_buff is destroyed, please store them before using FFT.
 */

int ifft(TYPE_FFT *fft_buff, uint32_t N)
{
    int k = 0;

    for(k = 0; k <= N - 1; k++)
    {
        fft_buff[k].imag = -fft_buff[k].imag;
    }

    fft(fft_buff, N);    /* using FFT */

    for(k = 0; k <= N - 1; k++)
    {
        fft_buff[k].real = fft_buff[k].real / N;
        fft_buff[k].imag = -fft_buff[k].imag / N;
    }

    return 0;
}

static void import_data(void)
{
    int i;

    for(i = 0; i < SAMPLE_NODES; i++)
    {
        fft_buff[i].real = my_sin_wave_table[i];//取前1024個(gè)數(shù)進(jìn)行fft變換
        fft_buff[i].imag  = 0.0f;
    }
}


int main(int argc, char *argv[])
{
    int i;
    int f;//頻率
    float a;//幅度
    int fd;
    float t;

    printf("FFTrn");

    import_data();

    fft(fft_buff, SAMPLE_NODES);

    //fft后的結(jié)果在fft_buff
    //將其實(shí)部與虛部處理，輸出頻點(diǎn)與幅度值，導(dǎo)入Excel看效果
    //因?yàn)槭侵芷谛再|(zhì)，取前半部分即可

    //數(shù)據(jù)采樣頻率是360*40，均分到SAMPLE_NODES，則對(duì)應(yīng)頻點(diǎn)間隔是 360*40/SAMPLE_NODES
    fd=360*40/SAMPLE_NODES;

    for(i = 0; i < SAMPLE_NODES / 2; i++)
    {
        f = i *fd;
        a = (double)sqrt(fft_buff[i].real * fft_buff[i].real + fft_buff[i].imag * fft_buff[i].imag)/ (SAMPLE_NODES / 2);//轉(zhuǎn)換幅度
        //printf("%d,%fn", f, a);//>>導(dǎo)入excel查看幅頻圖效果
    }

    //過(guò)濾高頻部分
    //將幅度小于某個(gè)值的，以30為例過(guò)濾
    for(i = 0; i < SAMPLE_NODES; i++)
    {
        a = (double)sqrt(fft_buff[i].real * fft_buff[i].real + fft_buff[i].imag * fft_buff[i].imag)/ (SAMPLE_NODES / 2);
        if(a<30)
        {
            fft_buff[i].real = 0;
            fft_buff[i].imag = 0;
        }
    }

    //再進(jìn)行逆運(yùn)算還原
    ifft(fft_buff, SAMPLE_NODES);
    for(i = 0; i < SAMPLE_NODES; i++)
    {
        t=1.0/(360*40)*i;//結(jié)合采樣頻率步進(jìn)，方便查看波形效果
        //printf("%f,%fn", t,fft_buff[i].real);//>>導(dǎo)入excel查看還原后的sin效果
    }

    return 0;
}

3.3 幅頻圖

混合波形使用FFT后的幅頻圖：

看圖可知對(duì)應(yīng)的頻點(diǎn)和幅度，與原始混合波形的3種正弦波吻合。

柵欄效應(yīng)：其中頻點(diǎn)與采樣頻率和FFT轉(zhuǎn)換的采樣數(shù)有關(guān)，需要結(jié)合實(shí)際定義，因?yàn)閿?shù)字離散信號(hào)，頻點(diǎn)并不是連續(xù)的，如上大概相差14，因?yàn)閿?shù)據(jù)點(diǎn)數(shù)N為1024點(diǎn)，原始信號(hào)的采樣頻率為fs=14400Hz，則頻率間隔fs/N約等于14Hz。這樣看頻譜圖只有fs/N倍數(shù)的，例如沒(méi)有410Hz，只能看到相鄰頻率406Hz和420Hz處頻譜泄漏的數(shù)據(jù)，相當(dāng)于透過(guò)柵欄觀賞風(fēng)景，只能看到頻譜的一部分，而其它頻率點(diǎn)看不見(jiàn)，因此很可能部分有用的頻率成分被漏掉，這種現(xiàn)象被稱為柵欄效應(yīng)。

3.4 逆變換還原

FFT后的幅頻數(shù)據(jù)過(guò)濾其中2個(gè)頻點(diǎn)的小幅度波形，還原后的效果如下圖：

過(guò)濾還原后的波形，與原始圖，前面python生成的黑色虛線吻合。

4、應(yīng)用

傅里葉變換在數(shù)字信號(hào)領(lǐng)域中應(yīng)用廣泛，在嵌入式系統(tǒng)中，一般用來(lái)分析ADC高速采集的數(shù)據(jù)、濾波處理，或者對(duì)音頻進(jìn)行簡(jiǎn)單分析。但傅里葉變換算法內(nèi)存消耗有點(diǎn)大，低端設(shè)備可能無(wú)法運(yùn)行。