快速傅里葉變換(FFT)

一、FFT出現的原因

對x（n）進行N點DFT計算，一共有N² 次乘法，N²次加法
如果N=1024，則有2*1048576次計算，計算量過于龐大。
FFT的思想就是：不斷把長序列的DFT分解成幾個短序列的DFT，并利用W_N^kn的周期性和對稱性來減少DFT的運算次數。

二、DIT-FFT

（1）8點DFT一次時域抽取分解運算

經過一次分解后，計算1個N點DFT共需要計算兩個N/2點DFT和N/2個蝶形運算。而計算一個N/2點DFT需要(N/2)²次復數乘法和N/2(N/2-1)次復數加法。僅僅經過一次分解，就使運算量減少近一半。

（2）8點DFT二次時域抽取分解運算

經過第二次分解，又將N/2點DFT分解為2個N/4點DFT和N/4個蝶形運算，而1點DFT就是時域序列本身。

（3）DIT-FFT與DFT運算量的比較

設N=2^M ,有M級蝶形。每一級都由N/2個蝶形運算構成。每一級運算都需要N/2次復數乘和N次復數加

下圖顯示了DIT-FFT與DFT運算量的比較，可以直觀看出FFT算法的優越性。N越大時，優越性就越明顯。

三、用Python實現FFT算法

import numpy as np from scipy.fftpack import fft, ifft import matplotlib.pyplot as plt from matplotlib.pylab import mplmpl.rcParams['font.sans-serif'] = ['SimHei'] # 顯示中文 mpl.rcParams['axes.unicode_minus'] = False # 顯示負號# 采樣點選擇1400個 x = np.linspace(0, 1, 1400)# 設置需要采樣的信號，頻率分量有200，400和600 y = 7 * np.sin(2 * np.pi * 200 * x) + 5 * np.sin(2 * np.pi * 400 * x) + 3 * np.sin(2 * np.pi * 600 * x)fft_y = fft(y) # 快速傅里葉變換N = 1400 x = np.arange(N) # 頻率個數 half_x = x[range(int(N / 2))] # 取一半區間abs_y = np.abs(fft_y) # 取復數的絕對值，即復數的模(雙邊頻譜) angle_y = np.angle(fft_y) # 取復數的角度 normalization_y = abs_y / N # 歸一化處理（雙邊頻譜） normalization_half_y = normalization_y[range(int(N / 2))] # 由于對稱性，只取一半區間（單邊頻譜）plt.subplot(411) plt.plot(x[0:50],y[0:50]) plt.title('原始波形')plt.subplot(412) plt.plot(x, angle_y, 'violet') plt.title('雙邊相位譜', fontsize=9, color='violet')plt.subplot(413) plt.plot(x, normalization_y, 'g') plt.title('雙邊振幅譜', fontsize=9, color='green')plt.subplot(414) plt.plot(half_x, normalization_half_y, 'blue') plt.title('單邊振幅譜', fontsize=9, color='blue')plt.show()

總結

以上是生活随笔為你收集整理的数字信号处理学习笔记（二）|快速傅里叶变换的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。