离散傅里叶变换的算术傅里叶变换算法
张宪超1，武继刚1，蒋增荣2，陈国良1
（1.中国科技大学计算机科学与技术系，合肥230027；2.国防科技大学系统工程与数学系，长沙410073）
摘要：离散傅里叶变换（DFT）在数字信号处理等许多领域中起着重要作用.本文采用一种新的傅里叶分析技术—算术傅里叶变换（AFT）来计算DFT.这种算法的乘法计算量仅为0（N）；算法的计算过程简单，公式一致，克服了任意长度DFT传统快速算法（FFT）程序复杂、子进程多等缺点；算法易于并行，尤其适合VLSI设计；对于含较大素因子，特别是素数长度的DFT，其速度比传统的FFT方法快；算法为任意长度DFT的快速计算开辟了新的思路和途径.
关键词：离散傅里叶变换（DFT）；算术傅里叶变换（AFT）；快速傅里叶变换（FFT）
中图分类号：TN917文献标识码：A文章编号：0372-2112（2000）05-0105-03
An Algorithm for Computing DFT Using Arithmetic Fourier Transform
ZHANG Xian-chao1，WU Ji-gang1，JIANG Zeng-rong2，CHEN Guo-iiang1
（1.Dept.of CompUter Science&Technology，Unio.of Science&Technology of China，Hefei230027，China；
2.Dept.of System Engineering&Mathematics，National Unio.of Defense Technology，Changsha410073，China）
Abstract：The Discrete Fourier Transform（DFT）piays an important roie in digitai signai processing and many other fieids.In this paper，a new Fourier anaiysis technigue caiied the arithmetic Fourier transform（AFT）is used to compute DFT.This aigorithm needs oniy0（N）muitipiications.The process of the aigorithm is simpie and it has a unified formuia，which overcomes the disadvantage of the traditionai fast method that has a compieX program containing too many subroutines.The aigorithm can be easiiy performed in paraiiei，especiaiiy suitabie for VLSI designing.For a DFT at a iength that contains big prime factors，especiaiiy for a DFT at a prime iength，it is faster than the traditionai FFT method.The aigorithm opens up a new approach for the fast computation of DFT.
Key words：discrete Fourier transform（DFT）；arithmetic Fourier transform（AFT）；fast Fourier transform（FFT）
!引言
离散傅里叶变换（DFT）在数字信号处理等许多领域中起着重要作用.但DFT的计算量很大（N点DFT需0（N2）乘法和加法）.因此，DFT的快速计算问题非常重要.1965年，Cooiey 和Tukey开创了快速傅里叶变换（FFT）方法，使N点DFT的计算量从0（N2）降到0（N iog N），开辟了DFT的快速计算时代.但FFT的计算仍较复杂，且对不同长度的DFT其计算公式不一致，致使任意长DFT的FFT程序非常复杂，包含大量子进程.
1988年，Tufts和Sadasiv［1］提出了一种用莫比乌斯反演公式（Mibius inversion formuia）计算连续函数的傅立叶系数的方法并命名为算术傅立叶变换（AFT）.AFT有许多良好的性质：其乘法量仅为0（N）；算法简单，并行性好，尤其适合VLSI设计.因此很快得到广泛关注，并在数字图像处理等领域得到应用.AFT已成为继FFT后一种新的重要的傅立叶分析技术［2~5］.
根据DFT和连续函数的傅立叶系数的关系，可以用AFT 计算DFT.这种方法保持了AFT的良好性质，且具有公式一致性.大量实验表明，同直接计算相比，AFT方法可以将DFT的计算时间减少90%，对含较大素因子，特别是其长度本身为素数的DFT，它的速度比传统的FFT快.从而它为DFT快速计算开辟了新的途径.
"算术傅立叶变换
本文采用文［3］中的算法.设A（t）为周期为T的函数，它的傅立叶级数只含有限项，即：
A（t）=a0+!N
n=1
a n cos2!f0t+!N
n=1
b n sin2!f0t（1）
其中：f0=1/T，a0=1
T"
T
A（t）dt.
令：B（2n，!）=1
2n
!
2n-1
m=0
（-1）m A（m
2n
T+!T），-1<!<1（2）则傅立叶系数a n和b n可以由下列公式计算：
a n=!
［N/n］
l=1，3，5，…
U（l）B（2nl，0）
b n=!
［N/n］
l=1，3，5，…
U（l）（-1）（l-1）/2B（2n，
1
4nl
），n=1，…，N（3）
第5期2000年5月
电子学报
ACTA ELECTR0NICA SINICA
Voi.28No.5
May2000
其中：!
（l ）=I ，（-I ）r ，0{
，l =I l =p I p 2…p r 3p 使p 2\l
为莫比乌斯（M bioLS ）函数.
这就是AFT ，其计算量为：加法：N 2+［N /2］+［N /3］+…
+I -2N ；乘法：2N.
AFT 需要函数大量的不均匀样本点，而在实际应用中，若计算函数前N 个傅立叶系数，根据奈奎斯特（NygLiSt ）抽样定
律，只需在函数的一个周期内均匀抽取2N 个样本点.这时可以用零次插值解决样本不一致问题.文献［2、3］已作了详细的分析，本文不再重复.
3
DFT 的AFT 算法
3.1
DFT 的定义及性质
定义1设X I 为一长度为N 的序列，它的DFT 定义为：
Y I =Z N-I
I =0
X I w II ，I =0，I ，…，N -I ；w =e -i 2!/N
（4）
性质1
用记号X I 、=、Y I 表示序列Y I 为序列X I 的
DFT ，G I 、=、H I ，
则：pX I +gG I 、=、pY I +gH I （5）因此，一个复序列的DFT 可以用两个实序列的DFT 计
算.故本文只讨论实序列DFT 的计算问题.
性质2
设X I 为一实序列，X I 、=、Y I ，
则：Re Y I =Re Y N -I ，Im Y I =-Im Y N -I （Re Y I 和Im Y I 分别代表Y I 的实部和虚部）
（6）
因此，对N 点实序列DFT ，只需计算：Re Y I 和Im Y I （I =0，…，「N /
2）.
3.2DFT 的AFT 算法
离散序列的DFT 和连续函数的傅立叶系数有着密切的联系.事实上，若序列X I 是一段区间［0，T ］上的函数A （t ）经过离散化后得到的，再设A （t ）的傅立叶级数只含前N /2项，即：
A （t ）=a 0+
Z
「N /2-I
I =I
a I coS2!f 0t +
Z傅里叶变换公式性质
「N /2-I
I =I
6I Sin2!f 0t
（7）
则DFT Y I 和傅立叶系数的关系为：
Re Y I =
「N /2a I /2Im Y I =
「N /26I /{
2，I =0，
…，「N /2（8）
式（7）中函数代表的是一种截频信号.对一般函数，式（8）中的
“=”要改为“匀”［7］
.因此，序列X I 的DFT 可以通过函数A （t ）的傅里叶系数计算.
对于一般给定序列X I ，注意到在任意一个区间上，经过离散后能得到序列X I 的函数有无穷多个.对所有这些插值函数，公式（8）都近似地满足（仅式（7）中的函数精确地满足式
（8））［7］.AFT 的零次插值实现实质上就是用这些插值函数中
的零次插值函数代替原来的函数进行计算的.而从AFT 的零次插值实现方法可知，用AFT 计算傅里叶系数，实际上参与计算的只是函数经离散化后得到的序列，而不必知道函数本身.因此，我们可以任取一个区间，在这个区间上，把序列X
算（8）中的“傅里叶系数”，再通过式（8），就可以计算出序列的DFT .
算法描述如下（采用［0，I ］
区间）：for I =I to 「N /2for m =0to 2I -I
B （2I ，0）：=B （2I ，0）+（-I ）m
X
［Nm /2I +0.5］B （2I ，I /4I ）：=
B （2I ，I /4I ）+（-I ）m
X
［Nm /2I +N /4I +0.5］endfor
B （2I ，0）：=B （2I ，0）/2I B （2I ，I /4I ）：=B （2I ，I /4I ）/2I endfor
for  =0to N -I a 0：=a 0+X （ ）/N for I =I to 「N /2
for I =I to
［「N /2/I ］by 2a I ：=a I +!（I ）B （2II ，0）
6I ：=6I +!（I ）（-I ）（K -I ）/2
B （2II ，I /4II ）
endfor
Re Y I ：=「N /2a I /2Re Y N -I ：=Re Y I Im Y I ：=「N /2a I /2Im Y N -I ：=-Im Y I endfor endfor
图I
DFT 的AFT 算法程序
AFT 方法的误差主要是由零次插值引起的，
大量实验表明，同FFT 相比，其误差是可以接受的（部分实验结果见附录）.
4
算法的性能
4.1
算法的程序
DFT 的AFT 算法具有公式一致性，且公式简单，因此算法的程序也很简单（图I ）.
图2
DFT 的AFT 算法进程示意
为便于比较，不妨看一下FFT 的流程.
图3FFT 算法进程示意
可以看出，FFT 的程序中包含大量子进程，
且这些子程序都较复杂.其中素数长度DFT 的FFT 算法程序尤其复杂.因此，任意长DFT 的FFT 算法其程序是非常复杂的.4.2
算法的计算效率
AFT 方法把DFT 的乘法计算量从0
（N 2）降到0（N ），它2电子学报2000年
计算时间减少90%.当DFT的长度!为2的幂时，FFT比AFT 方法快"对一般长度的DFT，当!含较大素因子时，AFT方法比FFT快；当!的因子都较小时，AFT方法不如FFT快.当DFT长度!本身为一较大素数时，AFT方法比FFT快"附录中给出部分实验结果以便比较"
特别指出，对素数长度DFT，FFT的计算过程非常复杂，很难在实际中应用.而AFT方法算法简单，提供了较好的素数长度DFT快速算法"表1是两种算法计算效率较详细的比较"
表1
长度52191197114832417
FFT效率67.30%68.03%72.50%71.23%76.22% AFT方法效率91.39#91.78#91.63#91.81#91.83# 4.3算法的并行性
AFT具有良好的并行性，尤其适合VLSI设计，已有许多
VLSI设计方案被提出，并在数字图像处理等领域得到应用.
DFT的AFT算法继承了AFT优点，同样具有良好的并行性"
5结论和展望
本文采用算术傅里叶变换（AFT）计算DFT.这种方法把AFT的各种优点引入DFT的计算中来，开辟了DFT快速计算的新途径.把AFT方法同FFT结合起来，还可以进一步提高DFT的计算速度"
参考文献
［1］  D.W.Tufts and G.Sadasiv.The arithmetic Fourier transform.IEEE ASSP Mag，Jan.1988：13~17
［2］I.S.Reed，D.W.Tufts，Xiao Yu，T.K.Troung，M.T.Shih and X.Yin.
Fourier anaiysis and signai processing by use of Mobius inversion for-
muiar.IEEE Trans.Acoust.Speech Speech Processing，Mar，1990，38
（3）：458~470
［3］I.S.Reed，Ming Tang Shih，T.K.Truong，R.Hendon and D.W.Tufts.
A VLSI architecture for simpiified arithmetic fourier transform aigo-
rithm.IEEE Trans.Signai Processing，May，1993，40（5）：1122~1132［4］H.Park and V.K.Prasanna.Moduiar VLSI architectures for computing the arithmetic fourier transform.IEEE.Signai Processing，June，1993，
41（6）：2236~2246
［5］Lovine.F.P，Tantaratanas.Some aiternate reaiizations of the arithmetic Fourier transform.Conference on Signai，system and Computers，1993，
（Cat，93，CH3312-6）：310~314
［6］蒋增荣，曾泳泓，余品能.快速算法.长沙：国防科技大学出版
社，1993
［7］E.0.布赖姆.快速傅立叶变换.上海：上海科学技术出版社，1976
附录：较详细的实验结果（机型：586微机，主频：166MHz单
位：秒）
2的幂长度
长度AFT方法基-2FFT直接算法
2560.005160.002400.11
5120.018600.004400.44
10240.075800.01100  1.81素数长度
长度AFT方法FFT直接算法
5210.03790.14390.44
9710.13400.4400  1.60
14830.3103  1.0904  3.79
24170.8206  2.389910.75
任意长度
长度因子分解AFT方法FFT直接算法
13462!6370.270.44  3.14
29862!1483  1.26  2.1414.82
35793!1193  1.81  1.9222.16
46374637  3.0821.4237.47
55742!3!929  4.45  2.4752.29
64364!1609  5.94  3.5772.62
78933!3!8778.96  1.92105.49
最大相对误差
长度AFT方法FFT
1024
实部  2.1939>10-2  2.3328>10-2
虚部  2.1938>10-29.9342>10-2 2048
实部  4.2212>10-3  1.1967>10-2
虚部  6.1257>10-3  4.9385>10-2 4096
实部  2.3697>10-3  6.0592>10-3
虚部  2.0422>10-3  2.4615>10-3
张宪超1971年生"1994年、1998年分别获
国防科技大学学士、硕士学位"现在中国科技大
学攻读博士学位"主要研究方向为信号处理的快
速、并行计算等"
武继刚1963年生"烟台大学副教授，现在
中国科技大学攻读博士学位"主要研究方向为算
法设计和分析等"
3
第5期张宪超：离散傅里叶变换的算术傅里叶变换算法

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。