Probabilistic complexity analysis for a class of approximate DFT algorithms

作     者：Winograd, JM Nawab, SH 

作者机构：Boston Univ Boston United States 

出 版 物：《JOURNAL OF VLSI SIGNAL PROCESSING SYSTEMS FOR SIGNAL IMAGE AND VIDEO TECHNOLOGY》 (J VLSI Signal Process)

年 卷 期：1996年第14卷第2期

页      面：193-205页

核心收录：

主　　题：Digital signal processing 

摘      要：We present a probabilistic complexity analysis of a class of multi-stage algorithms which incrementally refine DFT approximations. Each stage of any algorithm in this class improves the results of the previous stage by a fixed increment in one of three dimensions: SNR, frequency resolution, or frequency coverage. However, the complexity of each stage is probabilistically dependent upon certain characteristics of the input signal. Assuming that an algorithm has to be terminated before its arithmetic cost exceeds a given limit, we have formulated a method for predicting the probability of completion of each of the algorithm s stages. This analysis is useful for low-power and real-time applications where FFT algorithms cannot meet the specified limits on arithmetic cost.