Page 240 - DSP Integrated Circuits

DSP ALGORITHMS

6.1 INTRODUCTION

In this chapter, we will discuss the computational properties of digital signal pro-
cessing systems. We will describe a DSP system as a hierarchy of computational
structures. Each structure (algorithm) involves a set of basic operations called pro-
cesses. At the higher levels of the hierarchy these processes correspond to large
DSP tasks (for example FFTs, DCTs, and digital filters) while the lowest-level pro-
cesses involve arithmetic operations. The computational properties of the algo-
rithms at the different hierarchical levels will limit the achievable performance of
the system. We will introduce a number of graphs that will allow us to determine
the computational properties of a DSP algorithm. Properties of interest are the
order of execution of the arithmetic operations (processes), the number of opera-
tions that can be executed in parallel, and the shortest possible execution time.
Some of these graphs will serve as a basis for the scheduling of the operations that
will be discussed in Chapter 7. The computational properties of the higher-level
processes can be analyzed in a manner similar to the arithmetic operations. We
will also discuss a formal method to derive the difference equations in a comput-
able order from the signal-flow graph. In this form the set of difference equations
can be translated directly into code for a standard signal processor or a multicom-
puter. Various methods of improving the computational properties of recursive
algorithms will also be discussed.

6.2 DSP SYSTEMS

Generally, any reasonably complex DSP system can be described, as illustrated in
Figure 6.1, by a hierarchy of cooperating processes. We use the concept of process
to denote a structural component that performs a function at a given hierarchical
level. Examples of processes at the higher levels in the system hierarchy are FFTs,
DCTs, and digital filters. The inner structure of these processes can be further
described by another computational structure. At the lower levels of the hierarchy
processes typically describe the algorithms that realize the basic arithmetic opera-
tions. Note that storage may also be described as a process. Typically, several algo-
rithms at various hierarchical levels can be identified within a DSP system.

225