淺析FFT算法中對稱關(guān)系

李艷鳳， 陳后金， 胡 健

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

淺析FFT算法中對稱關(guān)系

李艷鳳， 陳后金， 胡 健

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

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

時間抽取FFT；頻率抽取FFT；對稱關(guān)系

0 引言

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

1 時間抽取FFT

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

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

(1)

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

(2)

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

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

(2)基4時間抽取FFT：時域上將數(shù)據(jù)按照基4進(jìn)行逐級拆分，最終得到多組四點時域數(shù)據(jù)，通過計算四點序列的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：時域上將一組長序列分解為兩組短序列，經(jīng)過多次分解得到多組兩點時域序列，然后計算兩點時域序列的DFT將時域變換到頻域。

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

(5)

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

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

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

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

(6)

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

3 對稱性分析

對上述FFT算法進(jìn)行分析，可以看到FFT算法蘊含的對稱關(guān)系。

4 系數(shù)矩陣的機理

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

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

(a)單位圓表示

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

(a) 單位圓表示

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

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

(a) 單位圓表示

(b) 系數(shù)矩陣

(李艷鳳等文)

5 結(jié)語

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

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

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

[3] 陳后金, 李居朋, 姚暢, 李艷鳳(譯). 數(shù)字信號處理及MATLAB仿真[M]. 北京: 機械工業(yè)出版社, 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

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

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

TN911.72

A

1008-0686(2017)05-0078-04