Page 458 - Engineering Digital Design

428 CHAPTER 10 / INTRODUCTION TO SYNCHRONOUS STATE MACHINE DESIGN

with both the a —*• b and the a —> c branching paths. Thus, if XY -> XY while in state
a, malfunction of the FSM is likely to occur. In Fig. 10.9b is the input/state map showing
violation of Eq. (10.4) under input condition XY shared by branching paths a —> b and
a —> c. Thus, if the mutually exclusive requirement is to hold for a given state, the input/state
map must not have cells containing more than one state identifier.

When Rules Can Be Broken There are conditions under which violation of the sum rule
or of the mutual exclusion requirement is permissible. Simply stated, these conditions are
as follows: If certain branching conditions can never occur or are never permitted to occur,
they can be excluded from the sum rule and from the mutually exclusive requirement. This
means that Eqs. (10.3) and (10.4) need not be satisfied for the FSM to operate properly. As an
example, suppose that in Fig. 10.6 the branching condition is Y for branching path b -> c.
Thus, the sum rule holds since XY + X + Y = 1. However, the branching condition XY is
common to both the b -> c and b -> d branching paths with branching conditions Y and
X, respectively. Clearly, the mutually exclusive requirement of Eq. (10.4) is not satisfied,
which is of no consequence if the input condition XY can never occur. But if the input
condition XY is possible, then branching from state b under XY is ambiguous, leading to
possible FSM malfunction. See Problem 10.24b for a more direct means of testing for the
mutual exclusivity of branching conditions.

10.4 THE BASIC MEMORY CELLS

Developing the concept of memory begins with the basic building block for memory called
the basic memory cell or simply basic cell. A basic cell plays a major role in designing a
memory device (element) that will remember a logic 1 or a logic 0 indefinitely or until it
is directed to change to the other value. In this section two flavors of the basic cell will be
heuristically developed and used later in the design of important memory elements called
flip-flops.

10.4.1 The Set-Dominant Basic Cell

Consider the wire loop in Fig. lO.lOa consisting of a fictitious lumped path delay (LPD)
memory element At and two inverters whose function it is to maintain an imaginary signal.
The LPD memory element is the path delay for the entire wire loop including inverters
concentrated (lumped) in At, hence the meaning of the word "fictitious." But since there
is no external access to this circuit, introduction of such a signal into this circuit is not
possible. This can be partially remedied by replacing one of the inverters with an NAND
gate performing the OR operation as in Fig. 10.1 Ob. Now, a Set (0 —> 1) can be introduced
into the circuit if S(L) = 1(L). This can be further understood by an inspection of the
Boolean expression Q t+\ = S + Q, for the circuit in Fig. 10.1Gb, where the following
definitions apply:

Q t+} = Next state

Q t = Present state.