Page 468 - DSP Integrated Circuits

10.7 Finite State Machines (FSMs) 453

The self-timed PE is pro-
vided with a local ring
counter that generates a
clock signal guaranteed to
be lower than the speed of
the PE. This can be accom-
plished, in spite of speed
variations between individ-
ual chips due to process
variations, if the ring
counter is placed close to the Figure 10.28 Self-timed processing element.
PE. The ring counter is
started by the signal Start and stopped after a given number of clock cycles. In thi
way, the circuit design problem is simplified significantly. The circuit has only to b
sufficiently fast.

10.7 FINITE STATE MACHINES (FSMs)

Finite state machines (FSMs) are used in many digital systems. An FSM can be
described by

where s(n), x(n), andy(n) are the state, input, and output at time instant n, while
T and U are the state transition function and output function, respectively.
An FSM has an infinite memory span if the present state is determined by an
infinite number of past states. Compare this with an IIR filter. The throughput for
such an FSM is therefore limited by the iteration period bound, obtained from
Equation (10.4). Techniques similar to the ones discussed in Chapter 6 have also
been developed for decreasing the iteration period bound for this class of FSM [14].
An FSM has a finite memory span if the current state is determined by a
finite number of past states. Hence, such FSMs have no iteration period bounds,
and can therefore achieve arbitrarily large throughputs by using pipelining and
interleaving in the same way as nonrecursive FIR filters. We will not therefore dis-
cuss this class of FSM further.
There are two basic ways to increase the throughput of a recursive algorithm.
The first way is to reduce the computation time for the critical loop—for example,
by removing unnecessary operations from the critical loop. This approach is obvi-
ously application dependent and relaxes only the iteration period bound. The sec-
ond way is to use various forms of look-ahead and block processing techniques, as
was done in section 6.9.

10.7.1 Look-Ahead FSMs
The basic principle of look-ahead techniques is to iterate Equations (10.4) and (10.5)
N times so that N inputs are used to compute N output values in each iteration step.
This approach effectively increases the number of delay elements in the critical loop.