文件名称:
An Algorithm for the Machine Calculation of Complex Fourier Series.pdf
开发工具:
文件大小: 373kb
下载次数: 0
上传时间: 2019-09-02
详细说明：关于 cooley-tukey 算法的理论论文，1967年发表在AMS上。MACHINE CALCULATION OF COMPLEX FOURIER SERIES
299
whose values run as follows
g27
1.88
34567890
2.00
2.15
2.31
2.4
2.67
2.82
3.01
The use of ri=3 is formally most efficient, but the gain is only about 6% over
the use of 2 or 4, which have other advantages. If necessary, the use of r; up to 10
can increase the number of computations by no more than 50%. Accordingly, we
can find"highly composite)values of n within a few percent of any given large
number
Whenever possible, the use ofN=?"withr =2 or 4 offers important advantages
for computers with binary arithmetic, both in addressing and in multiplication
economy.
The algorithm with r= 2 is derived by expressing the indices in the form
十∴十j2+j0,
(14)
k km-1
十…十k1·2+k,
where j, and hy are equal to o or l and are the contents of the respective bit positions
in the binary representation of i and k. All arrays will now be written as functions
of the bits of their indices. With this convention(1)is written
(15)X(in1,…,j)=∑∑…∑A(km-1,…,ko)·W地
m-1+…+正
where the sums are over k,=0. 1. Since
(16)
W0km-1·2m-1
the innermost sum of (15), over km-1, depends only on jo, km-2,.., ko and can
be written
(17)A1(j,km2,…,k)=∑A(km-1,…,k)·W0m-12mn-
k
Proceeding to the next innermost sum, over km-2, and so on, and using
(18)
2m
W(-124-1+…,+10m-12m=
one obtains successive arrays,
A2(o
3J-1,6m-l-1
ko)
(19)
=∑A1(3i,…,江2,km-1,…,k0)·W(-12-2+…+0m-12m-2
forl=1,2,……,m.
JAMES W. COOLEY AND john W. TUKEY
Writing out the sum this appears as
A(jo
l-1,Km-l-1,
A1-1(j0,……,j-2,0,km-l-1,…,ko)
(20)
+(-1)
A-1(1
k
W
刀
according to the indexing convention, this is stored in a location whose index is
21)
n+…+j1·2″-+k
…·+ko
It can be seen in(20)that only the two storage locations with indices having 0 and
I in the 2m- bit position are involved in the computation. Parallel computation is
permitted since the operation described by(20 )can be carried out with all values of
jo,..., jl-2, and ko,...,km-I-1 simultaneously. In some applications it is con
venient to use(20)to express A in terms of Al-2, giving what is equivalent to an
algorithm with r 4
The last array calculated gives the desired Fourier sums
(22)
X(
in such an order that the index of an X must have its binary bits put in reverse
order to yield its index in the array A
In some applications, where Fourier sums are to be evaluated twice, the above
procedure could be programmed so that no bit-inversion is necessary. For example,
consider the solution of the difference equation
(23)
ax(+1)+ bX(+cX(-1)=F()
The present method could be first applied to calculate the Fourier amplitudes of
FG from the formula
(24)
B(k
FGW
The Fourier amplitudes of the solution are, then
(25)
A(ke)
B(k)
awk+b+cw-k
The B(k)and A(k)arrays are in bit-inverted order, but with an obvious modifi
cation of(20), A(k)can be used to yield the solution with correct indexing
A computer program for the IBM 7094 has been written which calculates three
dimensional Fourier sums by the above method The computing time taken for co-
puting three-dimensional 22 x 2 arrays of data points was as follows
*A multiple-p
Processin
g circuit using this algorithm was designed by R. E. Miller and s
Winograd of the IBM Watson Research Center. In this case r 4 was found to be most practi
cal
MACHINE CALCULATION OF COMPLEX FOURIER SERIES
C
No. Pts
Time(minutes
414255
b4040450
911
02
11
02
040430
222222
223
47
0
12
13
13
13
IBM Watson Research Center
Yorktown Heights, New York
Bell Telephone Laboratories
Murray Hill, New Jersey
Princeton Universit
Princeton, New Jersey
1. G.E.P. Box, L R. CONNOR, W.R. CoUSINS, O. L. DAVIES(Ed), F. R. HIRNSWORTH
G. P. SILITTo, The Design and Analysis of Industrial Experiments, Oliver Boyd, Edinburgh,
1954
2. I.J. GOoD, The interaction algorithm and practical Fourier series, ,J. Roy Statist
Soc.Ser,B.,v.20,1958,p.361-372; Addendum,v.22,1960,p.372375.MR21修1674;MR23
%A4231
(系统自动生成,下载前可以参看下载内容)
下载文件列表
相关说明
- 本站资源为会员上传分享交流与学习,如有侵犯您的权益,请联系我们删除.
- 本站是交换下载平台，提供交流渠道，下载内容来自于网络，除下载问题外，其它问题请自行百度。
- 本站已设置防盗链，请勿用迅雷、QQ旋风等多线程下载软件下载资源，下载后用WinRAR最新版进行解压.
- 如果您发现内容无法下载，请稍后再次尝试；或者到消费记录里找到下载记录反馈给我们.
- 下载后发现下载的内容跟说明不相乎，请到消费记录里找到下载记录反馈给我们，经确认后退回积分.
- 如下载前有疑问，可以通过点击"提供者"的名字，查看对方的联系方式，联系对方咨询.
