淺析FFT算法中對稱關系

李艷鳳， 陳后金， 胡 健

(北京交通大學 電子信息工程學院, 北京 100044)

淺析FFT算法中對稱關系

李艷鳳， 陳后金， 胡 健

(北京交通大學 電子信息工程學院, 北京 100044)

本文通過分析比較時間抽取FFT算法以及頻率抽取FFT算法的基本原理，揭示了FFT算法中存在的對稱關系，同時也給出了任意基FFT算法系數矩陣的產生機理。上述的分析比較有助于學生更好地理解和實現FFT算法，同時也可借鑒該算法的思想設計其他算法。

時間抽取FFT；頻率抽取FFT；對稱關系

0 引言

離散傅里葉變換DFT (Discrete Fourier Transform)在數字信號處理中的重要性早已被人們所認識，但其得到廣泛應用卻經歷了較長時間，其原因在于計算量太大難以實用[1]?？焖俑道锶~變換FFT(Fast Fourier Transform)是各種DFT快速算法的統稱，目前較為普遍使用的算法是基于Cooly和Tukey提出的FFT算法[2]。本文通過比較分析時間抽取FFT算法以及頻率抽取FFT算法的基本原理，揭示了FFT算法中存在的對稱關系，同時也給出了任意基FFT算法系數矩陣的產生機理。上述的比較分析充分展現了FFT算法中蘊含的對稱之美，有助于學生更好地理解和實現FFT算法，也有助于任意基FFT算法的學習和掌握。

1 時間抽取FFT

(1)基2時間抽取FFT：時域上將數據按照奇偶進行逐級拆分，最終得到多組兩點時域數據，通過計算兩點序列的DFT將時域變換到頻域，然后利用兩個短序列的DFT逐級合成長序列的DFT，該合成過程稱為頻域合成[3]。

兩點序列時域(x[0]和x[1])到頻域(X[0]和X[1])的矩陣表示式為

(1)

兩個短序列DFT(X1[m]和X2[m])合成長序列DFT(X[m])的頻域合成矩陣表示式為

(2)

式(2)中，等式右邊第一個矩陣為系數矩陣，第二個矩陣為旋轉因子矩陣。頻域合成的蝶形圖如圖1所示。

圖1 基2時間抽取頻域合成蝶形圖

(2)基4時間抽取FFT：時域上將數據按照基4進行逐級拆分，最終得到多組四點時域數據，通過計算四點序列的DFT將時域變換到頻域，然后利用四個短序列的DFT逐級合成長序列的DFT。

四點序列時域(x[0]、x[1]、x[2]和x[3])到頻域(X[0]、X[1]、X[2]和X[3])的矩陣表示式為

(3)

四個短序列DFT(X1[m]、X2[m]、X3[m]和X4[m])合成長序列DFT(X[m])的頻域合成矩陣表示式為

(4)

2 頻率抽取FFT

(1)基2頻率抽取FFT：時域上將一組長序列分解為兩組短序列，經過多次分解得到多組兩點時域序列，然后計算兩點時域序列的DFT將時域變換到頻域。

長序列時域數據(x[k])分解為兩組短序列時域數據(x1[k]和x2[k])的矩陣表示如式(5)所示，時域分解的蝶形圖如圖2所示。

(5)

圖2 基2頻率抽取時域分解蝶形圖

兩點序列時域到頻域的計算與基2時間抽取FFT中時域到頻域計算相同，得到X1[m]和X2[m]。短序列DFT與長序列DFT的關系為：X[2m]=X1[m]，X[2m+1]=X2[m]。

(2)基4頻率抽取FFT：時域上將一組長序列分解為四組短序列，經過多次分解得到多組四點時域序列，然后計算四點時域序列的DFT將時域變換到頻域。

長序列時域數據(x[k])分解為四組短序列時域數據(x1[k]、x2[k]、x3[k]和x4[k])的矩陣表示式為

(6)

四點序列時域到頻域的計算與基4時間抽取FFT中時域到頻域計算相同，得到X1[m]、X2[m]、X3[m]和X4[m]。短序列DFT與長序列DFT的關系為：X[4m]=X1[m]，X[4m+1]=X2[m]，X[4m+2]=X3[m]，X[4m+3]=X4[m]。

3 對稱性分析

對上述FFT算法進行分析，可以看到FFT算法蘊含的對稱關系。

4 系數矩陣的機理

基2時間或頻率抽取FFT算法的系數矩陣可用單位圓二等分(如圖3(a)所示)生成。W2m的值為單位圓二等分的值，系數矩陣的每行都是以W20為起點順時針等間隔采兩個點，第一行間隔W20，第二行間隔W21，如圖3(b)所示。

基4時間或頻率抽取FFT算法的系數矩陣可用單位圓四等分(如圖4(a)所示)生成。W4m的值為單位圓四等分的值，系數矩陣的每行都是以W40為起點順時針等間隔采四個點，第一行間隔W40，第二行間隔W41，第三行間隔W42，第四行間隔W43，如圖4(b)所示。

(a)單位圓表示

(b)系數矩陣圖3 基2抽取FFT算法中系數矩陣的生成

(a) 單位圓表示

(b) 系數矩陣圖4 基4抽取FFT算法中系數矩陣的生成

可以證明，對于基r抽取FFT算法，其系數矩陣也可采用單位圓r等分方法得到。如基3抽取FFT算法，其系數矩陣如圖5所示。

(a) 單位圓表示

(b) 系數矩陣

(李艷鳳等文)

5 結語

本文給出了時間抽取FFT算法以及頻率抽取FFT算法存在的對稱關系，同時也給出了任意基FFT算法系數矩陣的產生機理。該分析過程有助于學生更好地理解和實現任意基FFT算法，同時也可借鑒該算法的思路設計其他算法。

[1] 陳后金, 薛健, 胡健. 數字信號處理(第二版)[M]. 北京: 高等教育出版社, 2008年11月.

[2] 吳鎮揚. 數字信號處理(第二版)[M]. 北京: 高等教育出版社, 2010年4月.

[3] 陳后金, 李居朋, 姚暢, 李艷鳳(譯). 數字信號處理及MATLAB仿真[M]. 北京: 機械工業出版社, 2015年1月.

DiscussiononSymmetryinFFTAlgorithm

LIYan-feng，CHENHou-jin，HUJian

(SchoolofElectronicandInformationEngineering,BeijingJiaotongUniversity,Beijing100044,China)

This paper analyzes and compares the basic theory between the decimation-in-time FFT and decimation-in-frequency FFT. The symmetry in FFT algorithm is revealed. Moreover, the generation mechanism of the coefficient matrix in FFT under arbitrary base is given. The symmetry analysis can help student better understand and implement the FFT algorithm. Also, the idea of FFT can be applied when designing other algorithms.

decimation-in-time FFT; decimation-in-frequency FFT; symmetry

2017-10-11;

2017-01-03

國家級電子信息與計算機實驗中心建設項目(No．274020529)

李艷鳳(1988-)，女，博士，副教授，主要從事信號與信息處理以及模式識別教學與研究工作，E-mail：yf.li@bjtu.edu.cn 陳后金(1965-)，男，博士，教授，主要從事信號與信息處理教學與研究工作，E-mail：hjchen@bjtu.edu.cn 胡 健(1965-)，女，碩士，副教授，主要從事信號與系統以及數字信號處理教學工作，E-mail：jhu@bjtu.edu.cn

TN911.72

A

1008-0686(2017)05-0078-04