An Error Analysis Model for Floating-Point DFT Algorithms

摘要

This paper presents a study of accuracy and hardware performance of floating-point (FP) implementations of the Discrete Fourier transform (DFT) and its fast algorithms. The studied formulations include Cooley-Tukey's, Pease's, and the Direct form as reference. Approximation and statistical methods were used to assess the accuracy of the FP treatments, while quantifying their normwise relative error. A hardware performance analysis was carried via FPGA synthesis, allowing for quantifying resource consumption and latency of each treatment. The results of the study showed significant differences in accuracy in the different treatments, and space-accuracy tradeoffs when this criteria was considered along with resource utilization and performance criteria. Our study also looked into how these tradeoffs changed as the transform sizes were scaled, reaching to unexpected and interesting findings for the fast formulations.