Page 36 - DSP Integrated Circuits

1.6 DSP System Design 21

and combination of the problems. MinSize is the size of a problem that is so small
that it can be solved immediately.
When comparing different alternative design algorithms it is of interest to
determine how rapidly the execution time grows as the problem size increases. We
will compare different algorithms by using the notation O(f(n)). A function g(n) is
a member ofO(f(n)) if

If the limit exists and const < °°, then function g(ri) grows no faster than func-
tion f(ri). Usually, both g(ri) and f(n) —> °o when n —» °°. Hence, the limit becomes
undetermined, but can often be determined using L'Hopital's rule:

It can be shown (see Problem 3.5) that divide-and-conquer algorithms have
the time-complexity:

Thus, recursively dividing a problem, using a linear amount of time, into two
problems (b = 2) of size n/2 (c = 2) results in an algorithm with time-complexity of
O(n Iog2(ft)). The fast Fourier transform (FFT), which is discussed in Chapter 3, is
an example of this type of algorithm.
If the number of subproblems were b = 3, 4, or 8, then the required execution
3
2
time would be Ofa^zffl), O(n \ or O(n ), respectively. The execution time grows
very rapidly for the last three types of algorithms.
1.6.6 VHDL

Many errors resulting from a faulty specification can be avoided if design ideas
can be tested and verified in an early phase of the design process. The use of a
hardware description language (HDL) is one approach used to avoid expensive
redesigns.
2
One such language, VHDL has become a de facto standard [2, 3, 6]. The lan-
guage structure (but not the semantics) is inspired by Ada. VHDL provides most of
the features of a high-level programming language plus facilities for the treatment
of time.
The main use of VHDL is for documentation and simulation, but a VHDL
description of the design problem may also serve as a specification or as the
input to automatic logic synthesis tools. It is also possible to use it to validate, by

2
- The VHDL hardware description language is a result of the VHSIC (Very High Speed
Integrated Circuit) program started in 1983 by the U.S. Department of Defense. MIL-STD-
454L. VHDL has been standardized by IEEE Std. 1076-1987.