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

1、傅里葉變換的意義

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

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

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

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

2、變換方式

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

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

3、應(yīng)用

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

1、python生成正弦波，以及混合波形，提取數(shù)值作為c語言FFT/IFFT的數(shù)據(jù)源?
2、先進(jìn)行FFT，輸出幅頻數(shù)據(jù)，導(dǎo)入Excel看看效果?
3、對數(shù)據(jù)進(jìn)行簡單過濾
4、過濾后的數(shù)據(jù)進(jìn)行IFFT運算，再導(dǎo)入Excel看還原的效果?
5、關(guān)注微信公眾號 ?嵌入式系統(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:????信號頻率
????:params?fs:???采樣頻率
????:params?phi:??相位
????:params?t:????時間長度
????'''
????#?若時間序列長度為?t=1s,
????#?采樣頻率?fs=1000?Hz,?則采樣時間間隔?Ts=1/fs=0.001s
????#?采樣點個數(shù)為?n=t/Ts=1/0.001=1000,?即有1000個點,每個點間隔為?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ù)據(jù)存入文件sin.txt備用。

3.2 基于C驗證算法

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

#include?
#include?
#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個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算法來自開源?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?????????{
????????????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?<????????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?/*?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?????{
????????fft_buff[i].real?=?my_sin_wave_table[i];//取前1024個數(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("FFT\r\n");

????import_data();

????fft(fft_buff,?SAMPLE_NODES);

????//fft后的結(jié)果在fft_buff
????//將其實部與虛部處理，輸出頻點與幅度值，導(dǎo)入Excel看效果
????//因為是周期性質(zhì)，取前半部分即可

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

????for(i?=?0;?i?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,%f\n",?f,?a);//>>導(dǎo)入excel查看幅頻圖效果
????}

????//過濾高頻部分
????//將幅度小于某個值的，以30為例過濾
????for(i?=?0;?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)行逆運算還原
????ifft(fft_buff,?SAMPLE_NODES);
????for(i?=?0;?i?????{
????????t=1.0/(360*40)*i;//結(jié)合采樣頻率步進(jìn)，方便查看波形效果
????????//printf("%f,%f\n",?t,fft_buff[i].real);//>>導(dǎo)入excel查看還原后的sin效果
????}

????return?0;
}

3.3 幅頻圖

混合波形使用FFT后的幅頻圖：看圖可知對應(yīng)的頻點和幅度，與原始混合波形的3種正弦波吻合。

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

3.4 逆變換還原

FFT后的幅頻數(shù)據(jù)過濾其中2個頻點的小幅度波形，還原后的效果如下圖：過濾還原后的波形，與原始圖，前面python生成的黑色虛線吻合。

4、應(yīng)用

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

嵌入式算法-傅里葉變換算法

1、傅里葉變換的意義