Some complexity issues in digital signal processing

Abstract

Over the past decade a large class of problems, called NP-complete [5], have been shown to be equivalent in the sense that if a fast algorithm can be found for one, fast algorithms can be found for all. At the same time, despite much effort, no fast algorithms have been found for any, and these problems are widely regarded as intractable. This class includes such notoriously difficult problems as the traveling salesman problem, graph coloring, and satisfiability of Boolean expressions. Using FIR filter implementation as an illustration, we describe some problems in digital signal processing that are NP-complete. These include: 1) minimize the number of additions needed to implement a fixed FIR filter; 2) minimize the number of registers needed to implement a fixed FIR filter; and 3) minimize the time to perform the additions of such an FIR filter using P adders. Large-seale instances of such problems may become important with the use of programmable chips to implement signal processing. Our main purpose in this paper is to illustrate the usefulness of asymptotic complexity theory in the field of digital signal processing. The theory discriminates between tractable and intractable problems, Sometimes identifies fast algorithms for the former, and justifies heuristics for the latter.