李艷鳳， 陳后金， 胡 健

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

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

李艷鳳， 陳后金， 胡 健

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

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

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

0 引言

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

1 時(shí)間抽取FFT

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

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

(1)

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

(2)

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

圖1 基2時(shí)間抽取頻域合成蝶形圖

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

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

(3)

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

(4)

2 頻率抽取FFT

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

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

(5)

圖2 基2頻率抽取時(shí)域分解蝶形圖

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

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

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

(6)

四點(diǎn)序列時(shí)域到頻域的計(jì)算與基4時(shí)間抽取FFT中時(shí)域到頻域計(jì)算相同，得到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算法蘊(yùn)含的對稱關(guān)系。

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

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

基4時(shí)間或頻率抽取FFT算法的系數(shù)矩陣可用單位圓四等分(如圖4(a)所示)生成。W4m的值為單位圓四等分的值，系數(shù)矩陣的每行都是以W40為起點(diǎn)順時(shí)針等間隔采四個(gè)點(diǎn)，第一行間隔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é)語

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

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

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

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

國家級電子信息與計(jì)算機(jī)實(shí)驗(yàn)中心建設(shè)項(xiàng)目(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