Page 35 - DSP Integrated Circuits

20 Chapter 1 DSP Integrated Circuits

Hierarchical abstraction is the iterative replacement of groups of modules.
Note that using hierarchy alone does not reduce the complexity. A design that can
be completely described by using modules (abstractions) is modular and will have
low complexity. If the design has only a few types of modules, the complexity is even
lower. Such designs have a high degree of regularity. A regularity factor can be
denned as the ratio of the total number of modules to the number of different mod-
ules. Standardization that restricts the design domain can be applied at all levels
of the design to simplify modules and increase the regularity, thereby reducing the
complexity. It is widely believed that the adoption of highly structured design meth-
odologies making extensive use of the ideas just discussed, is a necessity for a suc-
cessful design of complex systems.

1.6.5 The Divide-And-Conquer Approach

A well-known approach to derive low-complexity algorithms is the divide-and-con-
quer approach which is based on the fact that many large problems can be decom-
posed into several smaller problems that are easier to solve than the larger one.
The decomposition is done recursively until the remaining problems are so small
that they can be solved directly. Finally, the solutions are combined to obtain a
solution for the original problem [7]. The approach is described by the pseudo-code
shown in Box 1.1.

function Solve(P);
var

begin
if size(P) < MinSize
then Solve := Direct_Solution(P)
else
begin
Decompose(P, PI, P^,..., P&);
for i := 1 to b do
Si := Solve(Pj);
Solve := CombineGSi, S 2,..., S b)
end;
end;

Box 1.1. The divide-and-conquer algorithm

The amount of time required at each step is

where n is the size of the problem, a is the time required to solve the minimum-
size problem, b is the number of subproblems in each stage, nlc is the size of the
subproblems, and d • n is the linear amount of time required for decomposition