2024年5月8日发(作者：益新烟)
第
5
期
2000
年
5
月
电子学报
ACTAELECTR0NICASINICA
Voi.28No.5
May2000
离散傅里叶变换的算术傅里叶变换算法
张宪超
1
，武继刚
1
，蒋增荣
2
，陈国良
1
（
1.
中国科技大学计算机科学与技术系，合肥
230027
；长沙
410073
）
2.
国防科技大学系统工程与数学系，
要：离散傅里叶变换（
DFT
）在数字信号处理等许多领域中起着重要作用
.
本文采用一种新的傅里叶分析技
术—算术傅里叶变换（
AFT
）来计算
DFT.
这种算法的乘法计算量仅为
0
（
N
）；算法的计算过程简单，公式一致，克服了
任意长度
DFT
传统快速算法（
FFT
）程序复杂、子进程多等缺点；算法易于并行，尤其适合
VLSI
设计；对于含较大素因
子，特别是素数长度的
DFT
，其速度比传统的
FFT
方法快；算法为任意长度
DFT
的快速计算开辟了新的思路和途径
.
关键词：离散傅里叶变换（
DFT
）；算术傅里叶变换（
AFT
）；快速傅里叶变换（
FFT
）
TN917
文献标识码：
A
文章编号：
0372-2112
（
2000
）
05-0105-03
中图分类号：
摘
AnAlgorithmforComputingDFTUsingArithmeticFourierTransform
ZHANGXian-chao
1
，
WUJi-gang
1
，
JIANGZeng-rong
2
，
CHENGuo-iiang
1
（
UterScience&Technology
，
nce&TechnologyofChina
，
Hefei230027
，
China
；
emEngineering&Mathematics
，
nseTechnology
，
Changsha410073
，
China
）
（
DFT
）
ract
：
TheDiscreteFourierTransform
thispaper
，
anewFourieranaiysistechniguecaiiedthearithmeticFouriertransform
（
AFT
）
gorithm
（
N
）
cessoftheaigorithmissimpieandithasaunifiedformuia
，
needsoniy0whichovercomesthedisadvantage
ofthetraditioorithmcanbeeasiiyperformedin
paraiiei
，
Tataiengththatcontainsbigprimefactors
，
especiaiiyforaDFTataprime
iength
，
orithmopensupanewapproachforthefastcomputationofDFT.
（
DFT
）；（
AFT
）；（
FFT
）
Keywords
：
discreteFouriertransformarithmeticFouriertransformfastFouriertransform
!
引言
离散傅里叶变换（
DFT
）在数字信号处理等许多领域中起
性
.
大量实验表明，同直接计算相比，
AFT
方法可以将
DFT
的
对含较大素因子，特别是其长度本身为计算时间减少
90%
，
素数的
DFT
，它的速度比传统的
FFT
快
.
从而它为
DFT
快速计
算开辟了新的途径
.
着重要作用
.
但
DFT
的计算量很大（
N
点
DFT
需
0
（
N
2
）乘法
和加法）
.
因此，
DFT
的快速计算问题非常重要
.1965
年，
Cooiey
和
Tukey
开创了快速傅里叶变换（
FFT
）方法，使
N
点
DFT
的计
算量从
0
（
N
2
）降到
0
（
NiogN
），开辟了
DFT
的快速计算时代
.
但
FFT
的计算仍较复杂，且对不同长度的
DFT
其计算公式不
一致，致使任意长
DFT
的
FFT
程序非常复杂，包含大量子进
程
.
1988
年，
Tufts
和
Sadasiv
提出了一种用莫比乌斯反演公
式（
Mibiusinversionformuia
）计算连续函数的傅立叶系数的方
法并命名为算术傅立叶变换（
AFT
）
.AFT
有许多良好的性质：
其乘法量仅为
0
（
N
）；算法简单，并行性好，尤其适合
VLSI
设
计
.
因此很快得到广泛关注，并在数字图像处理等领域得到应
用
.AFT
已成为继
FFT
后一种新的重要的傅立叶分析技
［
2~5
］
术
.
根据
DFT
和连续函数的傅立叶系数的关系，可以用
AFT
计算
DFT.
这种方法保持了
AFT
的良好性质，且具有公式一致
［
1
］
"
算术傅立叶变换
本文采用文［
3
］中的算法
.
设
A
（
t
）为周期为
T
的函数，它
的傅立叶级数只含有限项，即：
N
n
=
1
N
（
t
）
A=a
0
+
!
a
n
cos2
!
f
0
t+
!
b
n
sin2
!
f
0
t
n
=
1
（
1
）
其中：
f
0
=1/T
，
a
0
=
令：（
2n
，
B=
!
）
1
T
（
t
）
dt.
"
A
0
T
m
1
m
（
-1
）（
T+
!
，
AT
）
-1<
!
<1
2n
2
n
!
m
=
0
则傅立叶系数
a
n
和
b
n
可以由下列公式计算：
［
N/n
］
2n
-
1
（
2
）
a
n
=
［
N/n
］
…
l
=
1
，
3
，
5
，
!
（
l
）（
2nl
，
UB0
）
b
n
=
1
（
l-1
）
/2
（
l
）（
-1
）（
2n
，），…，
UBn=1
，
N
（
3
）
4nl
…
l
=
1
，
3
，
5
，
!
2
电子学报
2000
年
r
l=pp
…
p
其中：（
l
）
=
（
-I
），
I2r
!
2
0
，
3
p
使
pl
为莫比乌斯（
M bioLS
）函数
.
这就是
AFT
，其计算量为：加法：［
N/2
］［
N/3
］
N
2
+++
…
{
I
，
l=I
算（
8
）中的“傅里叶系数”，再通过式（
8
），就可以计算出序列的
DFT.
算法描述如下（采用［
0
，区间）：
I
］
forI=Ito
「
N/2
form=0to2I-I
m
（
2I
，：（
2I
，（
-I
）［
Nm/2I+0.5
］
B0
）
=B0
）
+X
+I-2N
；乘法：
2N.
而在实际应用中，若
AFT
需要函数大量的不均匀样本点，
计算函数前
N
个傅立叶系数，根据奈奎斯特（
NygLiSt
）抽样定
律，只需在函数的一个周期内均匀抽取
2N
个样本点
.
这时可
以用零次插值解决样本不一致问题
.
文献［
2
、已作了详细的
3
］
（
2I
，：
BI/4I
）
=
m
（
2I
，（
-I
）［
Nm/2I+N/4I+0.5
］
BI/4I
）
+X
endfor
（
2I
，：（
2I
，
B0
）
=B0
）
/2I
分析，本文不再重复
.
3DFT
的
AFT
算法
3.1DFT
的定义及性质
定义
1
设
X
I
为一长度为
N
的序列，它的
DFT
定义为：
N-I
Y
I
=
Z
X
I
w
II
，
I=0
，
I
，…，
N-I
；
w=e
-i2
!
/N
（
4
）
I
=
0
性质
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
，则：
ReY
I
=ReY
N-I
，
ImY
I
=-ImY
N-
（
I
ReY
I
和
ImY
I
分别代表
Y
I
的实部和虚部）（
6
）
因此，对
N
点实序列
DFT
，只需计算：
ReY
I
和
ImY
（
I
I=
0
，…，「
N/2
）
.
3.2DFT
的
AFT
算法
离散序列的
DFT
和连续函数的傅立叶系数有着密切的
联系
.
事实上，若序列
X
I
是一段区间［
0
，
T
］上的函数
A
（
t
）经
过离散化后得到的，再设
A
（
t
）的傅立叶级数只含前
N/2
项，
即：
「
N/2
-
I
「
N/2
-
I
A
（
t
）
=a
0
+
Z
a
I
coS2
!
f
0
t+6
I
Sin2
!
f
0
t
（
7
）
I
=
I
Z
I
=
I
则
DFTY
I
和傅立叶系数的关系为：
{
ReY
I
=
「
N/2a
I
/2
Im
Y
，
I=0
，…，「
N/2
（
8
）
I
=
「
N/26
I
/2
式（
7
）中函数代表的是一种截频信号
.
对一般函数，式（
8
）中的
=
”要改为“
匀
”
［
7
］
.
因此，序列
X
I
的
DFT
可以通过函数
A
（
t
）
的傅里叶系数计算
.
对于一般给定序列
X
I
，注意到在任意一个区间上，经过
离散后能得到序列
X
I
的函数有无穷多个
.
对所有这些插值函
数，公式（
8
）都近似地满足（仅式（
7
）中的函数精确地满足式
8
））
［
7
］
.AFT
的零次插值实现实质上就是用这些插值函数中
的零次插值函数代替原来的函数进行计算的
.
而从
AFT
的零
次插值实现方法可知，用
AFT
计算傅里叶系数，实际上参与
计算的只是函数经离散化后得到的序列，而不必知道函数本
身
.
因此，我们可以任取一个区间，在这个区间上，把序列
X
B
（
2I
，
I/4I
）：
=B
（
2I
，
I/4I
）
/2I
endfor
for =0toN-I
a
0
：
=a
0
+X
（
）
/N
forI=Ito
「
N/2
forI=Ito
［「
N/2/I
］
by2
a
I
：
=a
I
+
!
（
I
）
B
（
2II
，
0
）
6
I
：
=6
I
+
!
（
I
）（
-I
）
（
K-I
）
/2
B
（
2II
，
I/4II
）
endfor
ReY
I
：
=
「
N/2a
I
/2
ReY
N-I
：
=ReY
I
ImY
I
：
=
「
N/2a
I
/2
Im
Y
N-I
：
=-ImY
I
endfor
endfor
图
IDFT
的
AFT
算法程序
AFT
方法的误差主要是由零次插值引起的，大量实验表
明，同
FFT
相比，其误差是可以接受的（部分实验结果见附
录）
.
4
算法的性能
4.1
算法的程序
DFT
的
AFT
算法具有公式一致性，且公式简单，因此算法
的程序也很简单（图
I
）
.
图
2DFT
的
AFT
算法进程示意
为便于比较，不妨看一下
FFT
的流程
.
图
3FFT
算法进程示意
可以看出，
FFT
的程序中包含大量子进程，且这些子程序
都较复杂
.
其中素数长度
DFT
的
FFT
算法程序尤其复杂
.
因
此，任意长
DFT
的
FFT
算法其程序是非常复杂的
.
4.2
算法的计算效率
AFT
方法把
DFT
的乘法计算量从
0
（
N
2
）降到
0
（
N
），它
“
（
第
5
期张宪超：离散傅里叶变换的算术傅里叶变换算法
素数长度
长度
521
971
1483
2417
任意长度
长度
1346
因子分解
2
!
637
AFT
方法
0.27
FFT
0.44
AFT
方法
0.0379
0.1340
0.3103
0.8206
FFT
0.1439
0.4400
1.0904
2.3899
直接算法
0.44
1.60
3.79
10.75
3
计算时间减少
90%.
当
DFT
的长度
!
为
2
的幂时，
FFT
比
AFT
方法快
"
对一般长度的
DFT
，当
!
含较大素因子时，
AFT
方法
当
!
的因子都较小时，比
FFT
快；
AFT
方法不如
FFT
快
.
当
DFT
长度
!
本身为一较大素数时，
AFT
方法比
FFT
快
"
附录中
给出部分实验结果以便比较
"
特别指出，对素数长度
DFT
，
FFT
的计算过程非常复杂，
很难在实际中应用
.
而
AFT
方法算法简单，提供了较好的素
数长度
DFT
快速算法
"
表
1
是两种算法计算效率较详细的比
较
"
直接算法
3.14
表
1
长度
522417
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
］
ASSPMag
，
Jan.1988
：
13~17
2
］
，
，
XiaoYu
，
，
.
FourieranaiysisandsignaiprocessingbyuseofMobiusinversionfor-
SpeechProcessing
，
Mar
，
1990
，
38
（
3
）：
458~470
3
］
，
MingTangShih
，
，
.
AVLSIarchitectureforsimpiifiedarithmeticfouriertransformaigo-
Processing
，
May
，
1993
，
40
（
5
）：
1122~1132
4
］
rVLSIarchitecturesforcomputing
Processing
，
June
，
1993
，
41
（
6
）：
2236~2246
5
］
Lovine.F.P
，
ternatereaiizationsofthearithmetic
enceonSignai
，
systemandComputers
，
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.011001.81
29862
!
14831.262.1414.82
35793
!
11931.811.9222.16
463746373.0821.4237.47
55742
!
3
!
9294.452.4752.29
64364
!
16095.943.5772.62
78933
!
3
!
8778.961.92105.49
最大相对误差
长度
AFT
方法
FFT
实部
2.1939>10
-2-2
1024
2.3328>10
虚部
2.1938>10
-2
9.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
年生
"
烟台大学副教授，现在
中国科技大学攻读博士学位
"
主要研究方向为算
法设计和分析等
"
［
［
［
［
［
［
［
2024年5月8日发(作者：益新烟)
第
5
期
2000
年
5
月
电子学报
ACTAELECTR0NICASINICA
Voi.28No.5
May2000
离散傅里叶变换的算术傅里叶变换算法
张宪超
1
，武继刚
1
，蒋增荣
2
，陈国良
1
（
1.
中国科技大学计算机科学与技术系，合肥
230027
；长沙
410073
）
2.
国防科技大学系统工程与数学系，
要：离散傅里叶变换（
DFT
）在数字信号处理等许多领域中起着重要作用
.
本文采用一种新的傅里叶分析技
术—算术傅里叶变换（
AFT
）来计算
DFT.
这种算法的乘法计算量仅为
0
（
N
）；算法的计算过程简单，公式一致，克服了
任意长度
DFT
传统快速算法（
FFT
）程序复杂、子进程多等缺点；算法易于并行，尤其适合
VLSI
设计；对于含较大素因
子，特别是素数长度的
DFT
，其速度比传统的
FFT
方法快；算法为任意长度
DFT
的快速计算开辟了新的思路和途径
.
关键词：离散傅里叶变换（
DFT
）；算术傅里叶变换（
AFT
）；快速傅里叶变换（
FFT
）
TN917
文献标识码：
A
文章编号：
0372-2112
（
2000
）
05-0105-03
中图分类号：
摘
AnAlgorithmforComputingDFTUsingArithmeticFourierTransform
ZHANGXian-chao
1
，
WUJi-gang
1
，
JIANGZeng-rong
2
，
CHENGuo-iiang
1
（
UterScience&Technology
，
nce&TechnologyofChina
，
Hefei230027
，
China
；
emEngineering&Mathematics
，
nseTechnology
，
Changsha410073
，
China
）
（
DFT
）
ract
：
TheDiscreteFourierTransform
thispaper
，
anewFourieranaiysistechniguecaiiedthearithmeticFouriertransform
（
AFT
）
gorithm
（
N
）
cessoftheaigorithmissimpieandithasaunifiedformuia
，
needsoniy0whichovercomesthedisadvantage
ofthetraditioorithmcanbeeasiiyperformedin
paraiiei
，
Tataiengththatcontainsbigprimefactors
，
especiaiiyforaDFTataprime
iength
，
orithmopensupanewapproachforthefastcomputationofDFT.
（
DFT
）；（
AFT
）；（
FFT
）
Keywords
：
discreteFouriertransformarithmeticFouriertransformfastFouriertransform
!
引言
离散傅里叶变换（
DFT
）在数字信号处理等许多领域中起
性
.
大量实验表明，同直接计算相比，
AFT
方法可以将
DFT
的
对含较大素因子，特别是其长度本身为计算时间减少
90%
，
素数的
DFT
，它的速度比传统的
FFT
快
.
从而它为
DFT
快速计
算开辟了新的途径
.
着重要作用
.
但
DFT
的计算量很大（
N
点
DFT
需
0
（
N
2
）乘法
和加法）
.
因此，
DFT
的快速计算问题非常重要
.1965
年，
Cooiey
和
Tukey
开创了快速傅里叶变换（
FFT
）方法，使
N
点
DFT
的计
算量从
0
（
N
2
）降到
0
（
NiogN
），开辟了
DFT
的快速计算时代
.
但
FFT
的计算仍较复杂，且对不同长度的
DFT
其计算公式不
一致，致使任意长
DFT
的
FFT
程序非常复杂，包含大量子进
程
.
1988
年，
Tufts
和
Sadasiv
提出了一种用莫比乌斯反演公
式（
Mibiusinversionformuia
）计算连续函数的傅立叶系数的方
法并命名为算术傅立叶变换（
AFT
）
.AFT
有许多良好的性质：
其乘法量仅为
0
（
N
）；算法简单，并行性好，尤其适合
VLSI
设
计
.
因此很快得到广泛关注，并在数字图像处理等领域得到应
用
.AFT
已成为继
FFT
后一种新的重要的傅立叶分析技
［
2~5
］
术
.
根据
DFT
和连续函数的傅立叶系数的关系，可以用
AFT
计算
DFT.
这种方法保持了
AFT
的良好性质，且具有公式一致
［
1
］
"
算术傅立叶变换
本文采用文［
3
］中的算法
.
设
A
（
t
）为周期为
T
的函数，它
的傅立叶级数只含有限项，即：
N
n
=
1
N
（
t
）
A=a
0
+
!
a
n
cos2
!
f
0
t+
!
b
n
sin2
!
f
0
t
n
=
1
（
1
）
其中：
f
0
=1/T
，
a
0
=
令：（
2n
，
B=
!
）
1
T
（
t
）
dt.
"
A
0
T
m
1
m
（
-1
）（
T+
!
，
AT
）
-1<
!
<1
2n
2
n
!
m
=
0
则傅立叶系数
a
n
和
b
n
可以由下列公式计算：
［
N/n
］
2n
-
1
（
2
）
a
n
=
［
N/n
］
…
l
=
1
，
3
，
5
，
!
（
l
）（
2nl
，
UB0
）
b
n
=
1
（
l-1
）
/2
（
l
）（
-1
）（
2n
，），…，
UBn=1
，
N
（
3
）
4nl
…
l
=
1
，
3
，
5
，
!
2
电子学报
2000
年
r
l=pp
…
p
其中：（
l
）
=
（
-I
），
I2r
!
2
0
，
3
p
使
pl
为莫比乌斯（
M bioLS
）函数
.
这就是
AFT
，其计算量为：加法：［
N/2
］［
N/3
］
N
2
+++
…
{
I
，
l=I
算（
8
）中的“傅里叶系数”，再通过式（
8
），就可以计算出序列的
DFT.
算法描述如下（采用［
0
，区间）：
I
］
forI=Ito
「
N/2
form=0to2I-I
m
（
2I
，：（
2I
，（
-I
）［
Nm/2I+0.5
］
B0
）
=B0
）
+X
+I-2N
；乘法：
2N.
而在实际应用中，若
AFT
需要函数大量的不均匀样本点，
计算函数前
N
个傅立叶系数，根据奈奎斯特（
NygLiSt
）抽样定
律，只需在函数的一个周期内均匀抽取
2N
个样本点
.
这时可
以用零次插值解决样本不一致问题
.
文献［
2
、已作了详细的
3
］
（
2I
，：
BI/4I
）
=
m
（
2I
，（
-I
）［
Nm/2I+N/4I+0.5
］
BI/4I
）
+X
endfor
（
2I
，：（
2I
，
B0
）
=B0
）
/2I
分析，本文不再重复
.
3DFT
的
AFT
算法
3.1DFT
的定义及性质
定义
1
设
X
I
为一长度为
N
的序列，它的
DFT
定义为：
N-I
Y
I
=
Z
X
I
w
II
，
I=0
，
I
，…，
N-I
；
w=e
-i2
!
/N
（
4
）
I
=
0
性质
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
，则：
ReY
I
=ReY
N-I
，
ImY
I
=-ImY
N-
（
I
ReY
I
和
ImY
I
分别代表
Y
I
的实部和虚部）（
6
）
因此，对
N
点实序列
DFT
，只需计算：
ReY
I
和
ImY
（
I
I=
0
，…，「
N/2
）
.
3.2DFT
的
AFT
算法
离散序列的
DFT
和连续函数的傅立叶系数有着密切的
联系
.
事实上，若序列
X
I
是一段区间［
0
，
T
］上的函数
A
（
t
）经
过离散化后得到的，再设
A
（
t
）的傅立叶级数只含前
N/2
项，
即：
「
N/2
-
I
「
N/2
-
I
A
（
t
）
=a
0
+
Z
a
I
coS2
!
f
0
t+6
I
Sin2
!
f
0
t
（
7
）
I
=
I
Z
I
=
I
则
DFTY
I
和傅立叶系数的关系为：
{
ReY
I
=
「
N/2a
I
/2
Im
Y
，
I=0
，…，「
N/2
（
8
）
I
=
「
N/26
I
/2
式（
7
）中函数代表的是一种截频信号
.
对一般函数，式（
8
）中的
=
”要改为“
匀
”
［
7
］
.
因此，序列
X
I
的
DFT
可以通过函数
A
（
t
）
的傅里叶系数计算
.
对于一般给定序列
X
I
，注意到在任意一个区间上，经过
离散后能得到序列
X
I
的函数有无穷多个
.
对所有这些插值函
数，公式（
8
）都近似地满足（仅式（
7
）中的函数精确地满足式
8
））
［
7
］
.AFT
的零次插值实现实质上就是用这些插值函数中
的零次插值函数代替原来的函数进行计算的
.
而从
AFT
的零
次插值实现方法可知，用
AFT
计算傅里叶系数，实际上参与
计算的只是函数经离散化后得到的序列，而不必知道函数本
身
.
因此，我们可以任取一个区间，在这个区间上，把序列
X
B
（
2I
，
I/4I
）：
=B
（
2I
，
I/4I
）
/2I
endfor
for =0toN-I
a
0
：
=a
0
+X
（
）
/N
forI=Ito
「
N/2
forI=Ito
［「
N/2/I
］
by2
a
I
：
=a
I
+
!
（
I
）
B
（
2II
，
0
）
6
I
：
=6
I
+
!
（
I
）（
-I
）
（
K-I
）
/2
B
（
2II
，
I/4II
）
endfor
ReY
I
：
=
「
N/2a
I
/2
ReY
N-I
：
=ReY
I
ImY
I
：
=
「
N/2a
I
/2
Im
Y
N-I
：
=-ImY
I
endfor
endfor
图
IDFT
的
AFT
算法程序
AFT
方法的误差主要是由零次插值引起的，大量实验表
明，同
FFT
相比，其误差是可以接受的（部分实验结果见附
录）
.
4
算法的性能
4.1
算法的程序
DFT
的
AFT
算法具有公式一致性，且公式简单，因此算法
的程序也很简单（图
I
）
.
图
2DFT
的
AFT
算法进程示意
为便于比较，不妨看一下
FFT
的流程
.
图
3FFT
算法进程示意
可以看出，
FFT
的程序中包含大量子进程，且这些子程序
都较复杂
.
其中素数长度
DFT
的
FFT
算法程序尤其复杂
.
因
此，任意长
DFT
的
FFT
算法其程序是非常复杂的
.
4.2
算法的计算效率
AFT
方法把
DFT
的乘法计算量从
0
（
N
2
）降到
0
（
N
），它
“
（
第
5
期张宪超：离散傅里叶变换的算术傅里叶变换算法
素数长度
长度
521
971
1483
2417
任意长度
长度
1346
因子分解
2
!
637
AFT
方法
0.27
FFT
0.44
AFT
方法
0.0379
0.1340
0.3103
0.8206
FFT
0.1439
0.4400
1.0904
2.3899
直接算法
0.44
1.60
3.79
10.75
3
计算时间减少
90%.
当
DFT
的长度
!
为
2
的幂时，
FFT
比
AFT
方法快
"
对一般长度的
DFT
，当
!
含较大素因子时，
AFT
方法
当
!
的因子都较小时，比
FFT
快；
AFT
方法不如
FFT
快
.
当
DFT
长度
!
本身为一较大素数时，
AFT
方法比
FFT
快
"
附录中
给出部分实验结果以便比较
"
特别指出，对素数长度
DFT
，
FFT
的计算过程非常复杂，
很难在实际中应用
.
而
AFT
方法算法简单，提供了较好的素
数长度
DFT
快速算法
"
表
1
是两种算法计算效率较详细的比
较
"
直接算法
3.14
表
1
长度
522417
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
］
ASSPMag
，
Jan.1988
：
13~17
2
］
，
，
XiaoYu
，
，
.
FourieranaiysisandsignaiprocessingbyuseofMobiusinversionfor-
SpeechProcessing
，
Mar
，
1990
，
38
（
3
）：
458~470
3
］
，
MingTangShih
，
，
.
AVLSIarchitectureforsimpiifiedarithmeticfouriertransformaigo-
Processing
，
May
，
1993
，
40
（
5
）：
1122~1132
4
］
rVLSIarchitecturesforcomputing
Processing
，
June
，
1993
，
41
（
6
）：
2236~2246
5
］
Lovine.F.P
，
ternatereaiizationsofthearithmetic
enceonSignai
，
systemandComputers
，
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.011001.81
29862
!
14831.262.1414.82
35793
!
11931.811.9222.16
463746373.0821.4237.47
55742
!
3
!
9294.452.4752.29
64364
!
16095.943.5772.62
78933
!
3
!
8778.961.92105.49
最大相对误差
长度
AFT
方法
FFT
实部
2.1939>10
-2-2
1024
2.3328>10
虚部
2.1938>10
-2
9.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
年生
"
烟台大学副教授，现在
中国科技大学攻读博士学位
"
主要研究方向为算
法设计和分析等
"
［
［
［
［
［
［
［