Information Technology Reference
In-Depth Information
=( p 2
( p 1
c 0
g 1 )
g 2 , p 2
( p 1
c 0
g 1 ))
=(( p 2
p 1 )
c 0
( g 2
p 2
g 1 )) , p 2
( p 1
c 0
g 1 ))
=( c 2 , s 2 )
It follows that c 2 can be computed from p = p 2
p 1 and g = g 2
p 2
g 1 and c 0 .The
value of s 2 is obtained from p 2 and c 1 . Thus the mapping Δ p 1 , g 1
Δ p 2 , g 2 is defined by p and
g , quantities obtained by combining the pairs ( p 1 , g 1 ) and ( p 2 , g 2 ) using the same associative
operator
defined for the carry-lookahead adder in Section 2.7.1 .
To summarize, the state-to-state mappings corresponding to subsequences of an input
string (( u 0 , v 0 ) , ( u 1 , v 1 ) , ... , ( u n− 2 , v n− 2 ) , ( u n− 1 , v n− 1 )) can be computed by representing
this string by the carry-propagate, carry-generate string (( p 0 , g 0 ) , ( p 1 , g 1 ) , ... , ( p n− 2 , g n− 2 ) ,
( p n− 1 , g n− 1 )) , computing the prefix operation on this string using the operator
,thencom-
puting c i from c 0 and the carry-propagate and carry-generate functions for the i th stage and s i
from this carry-propagate function and c i− 1 . This leads to the carry-lookahead adder circuit
of Section 2.7.1 .
3.3 Designing Sequential Circuits
Sequential circuits are concrete machines constructed of gates and binary memory devices.
Given an FSM, a sequential machine can be constructed for it, as we show.
A sequential circuit is constructed from a logic circuit and a collection of clocked binary
memory units, as suggested in Figs. 3.12 (a) and 3.15 .(ShowninFig. 3.12 (a) is a simple
sequential circuit that computes the EXCLUSIVE OR of the initial value in memory and the
external input to the sequential circuit.) Inputs to the logic circuit consist of outputs from the
binary memory units as well as external inputs. The outputs of the logic circuit serve as inputs
to the clocked binary memory units as well as external outputs.
A clocked binary memory unit is driven by a clock , a periodic signal that has value 1 (it is
high ) during short, uniformly spaced time intervals and is otherwise 0 (it is low ), as suggested
in Figs. 3.12 (b). For correct operation it is assumed that the input to a memory unit does not
change when the clock is high. Thus, the outputs of a logic circuit feeding the memory units
cannot change during these intervals. This in turn requires that all changes in the inputs to
Clock
s
M
1
0
Clock
x
Time
(a)
(b)
Figure 3.12 (a) A sequential circuit with one gate and one clocked memory unit computing
the EXCLUSIVE OR of its inputs; (b) a periodic clock pattern.
 
Search WWH ::




Custom Search