Worst-case error analysis for the fast fourier transform
作者:
Gabor C.Temes,
期刊:
IEE Journal on Electronic Circuits and Systems
(IET Available online 1977)
卷期:
Volume 1,
issue 3
页码: 110-115
年代: 1977
DOI:10.1049/ij-ecs.1977.0014
出版商: IEE
数据来源: IET
摘要:
Tight worst-case error bounds are derived for the results of the fast Fourier transform (f.f.t.). The following f.f.t. algorithms are analysed:(i) standard method of complex multiplication without scaling(ii) standard method with prescaling(iii) standard method with stagewise scaling(iv) Buneman's method of complex multiplication without scaling(v) Buneman's method with prescaling(vi) Buneman's method with stagewise scaling.The results establish the maximum number of least-significant bits which can become noisy in the computed spectrum for a given numberNof data points, a given accuracy in the arithmetic, and a given accuracy in the tabulated coefficients of the f.f.t. The results are compared with the r.m.s. errors obtained earlier from statistical considerations.2,3The comparison indicates that the worst-case values cannot be extrapolated from the r.m.s. values, since their dependence onNis different.
点击下载:
PDF
(737KB)
返 回