Approximate Signal Processing Using Incremental Refinement And Deadline-Based Algorithms

A framework for approximate signal processing is introduced which can be used to design novel classes of algorithms for performing DFT and STFT calculations. In particular, we focus on the derivation of multi-stage incremental refinement algorithms that meet a variety of design criteria on the tradeoff achieved at each stage between solution quality and computational cost. 1. INTRODUCTION In any given problem-solving domain, an approximation to a given algorithm may be defined as an algorithm which offers a reduced computational cost but produces a lower quality answer according to some standard of accuracy, certainty, and/or completeness. The approximate algorithm may be said to carry out approximate processing in the domain under consideration. Such algorithms have previously been studied in the context of various applications, including real-time vehicular tracking [1, 2] and real-time database query processing [3]. In real-time applications, any individual task must generally be ..