Problems
Problem 9.1. Analyze the synchronous circuit of Fig. P9.1 (the clock is not shown, but is
implicit)
(a) Write down the excitation and output functions.
(b) Form the excitation and state tables.
(c) Give a word description of the circuit operation.
Step 1: JK Flip-Flop Characteristic Equation
Solution: For a JK flip-flop:
ˉ ˉ
𝑄+ = 𝐽𝑄 + 𝐾 𝑄
(a) J1 = y2
Step 2: Next-State Equations
K1 =y′ 2 For y₂
ˉ
+ ˉ
𝑦2 = 𝐽2 𝑦2 + 𝐾2 𝑦2
J2 =x + ˉ
𝑦2 = 𝑥𝑦2 + 𝑥𝑦2 = 𝑥
K2 =x′ y₂ simply follows input x
For y₁
z=x′y2+y1y′ 2+xy′ ˉ ˉ
𝑦1+ = 𝐽1 𝑦1 + 𝐾1 𝑦1
(b) Excitation/output tables 𝑦1+ =
ˉ
𝑦2 𝑦1 + 𝑦2 𝑦1 = 𝑦2
y₁ follows y₂
Solution continue…
(c)
From the state diagram, it is obvious that the machine produces a zero output value if and only if the last
three input values were identical (under the assumption that we ignore the first two output symbols)
2.
Problem 9.2. A long input sequence enters a one-input one-output synchronous sequential
circuit, that is required to produce an output symbol z = 1 whenever the sequence 1111 occurs.
Overlapping sequences are accepted; for example, if the input sequence is 01011111···, the
required output sequence is 00000011···.
(a) Draw a state diagram.
(b) Select an assignment and show the excitation and output tables.
(c) Write down the excitation functions for SR flip-flops, and draw the corresponding logic
diagram.
• Solution:
Given
• One input: x
• One output: z
• Synchronous sequential circuit
• Output z = 1 whenever the sequence 1111 occurs
Overlapping sequences allowed
• Example:
Input: 01011111…
Output: 00000011…
Continue…
(b) State Assignment
Let flip-flops be Q2 Q1 Q0
State Q2 Q1 Q0
S0 000
S1 001
S2 010
S3 011
S4 100
Continue..
the excitation and output tables
Present
x Next State z
State
000 (S0) 0 000 0
000 1 001 0
001 (S1) 0 000 0
001 1 010 0
010 (S2) 0 000 0
010 1 011 0
011 (S3) 0 000 0
011 1 100 0
100 (S4) 0 000 1
100 1 100 1
Continue…
SR Flip-Flop Excitation Table
Q Q⁺ S R
0 0 0 0
0 1 1 0
1 0 0 1
1 1 0 0
3.
Repeat Problem 9.2 for the sequence 01101, and implement the circuit
with T flip-flops as memory elements.
4.
Problem 9.4. Construct the state diagram for a one-input eight-state machine that is to produce
an output symbol z = 1 whenever the last string of five input symbols contains exactly three 1’s
and starts with two 1’s. After each string that starts with two 1’s, analysis of the next string does
not start until the end of this string of five symbols, whether it produces an output value 1 or
not. For example, if the input sequence is 11011010 then the output sequence is 00000000,
while an input sequence 10011010 produces an output sequence 00000001.
• Given
• One input: x
• One output: z
• Eight-state synchronous machine
• Output z = 1 when:
• The last five input symbols
• Start with two 1’s (11xxx)
• Contain exactly three 1’s
• Non-overlapping analysis:
• Once a string starting with 11 begins, the machine must wait for all five bits
• Next analysis starts only after the 5-bit string completes
• Otherwise, output z = 0
Continue…
Present State x=0 → Next x=1 → Next z
S0 S0 S1 0
S1 S0 S2 0
S2 S3 S3 0
S3 S4 S4 0
S4 S5 S5 0
S5 (valid 3 ones) S7 S7 1
S5 (invalid) S6 S6 0
S6 S0 S0 0
S7 S0 S0 1
5.
Problem 9.5. For each of the following cases, show the state table that
describes a one-input one-output machine having the following specifications.
(a) An output symbol z = 1 is to be produced to coincide with every
occurrence of the input symbol 1 following a string of two or three
consecutive 0’s at the input. At all other times, the output symbol is to be
0.
(b) Regardless of the input symbols, the first two output symbols are 0’s.
Thereafter, output symbol z is a replica of input symbol x but delayed by two
time units, that is, z(t) = x(t − 2) for t ≥ 3.
(c) The output z(t) is 1 if and only if x(t) = x(t −2). At all other times, z is to be 0.
(d) The output z has the value 1 whenever the last four input symbols
correspond to a BCD number that is a multiple of 3, i.e., 0,3,6,....
Solution:
(a)
• Specification:
Output z = 1 whenever an input 1 occurs after exactly two or three
consecutive 0’s.
At all other times, z = 0.
Present State x = 0 → Next / z x = 1 → Next / z
S0 S1 / 0 S0 / 0
S1 S2 / 0 S0 / 0
S2 S3 / 0 S0 / 1
S3 S3 / 0 S0 / 1
Solution:
(b) Specification:
• First two output symbols are 0
• Thereafter:
• 𝑧 𝑡 = 𝑥 𝑡 − 2 ,𝑡 ≥ 3
Present State x Next State z
S0 0 S1 0
S0 1 S1 0
S1 0 S2 0
S1 1 S2 0
Previous
S2 0 S2
x(t−2)
Previous
S2 1 S2
x(t−2)
Solution:
(c) Specification:
• 𝑧 𝑡 =1 ⟺ 𝑥 𝑡 =𝑥 𝑡−2
Present
x Next State z
State
S0 (00) 0 S0 1
S0 1 S2 0
S1 (01) 0 S0 0
S1 1 S2 1
S2 (10) 0 S1 1
S2 1 S3 0
S3 (11) 0 S1 0
S3 1 S3 1
Solution:
(d) Specification:
Output z = 1 when last four input bits form a BCD number that is a
multiple of 3
State Stored 4-bit value
Valid BCD multiples of 3:
S0 0000
• 0000 (0) S1 0001
• 0011 (3) S2 0010
S3 0011
• 0110 (6) State z
S4 0100
S0 (0000) 1
• 1001 (9) S5 0101
S3 (0011) 1
S6 0110
S6 (0110) 1 S7 0111
S9 (1001) 1 S8 1000
Others 0 S9 1001
Continue…
The labels of the states in (b), (c), and (d) were picked so that they will indicate the
past in put values, and make the construction of the state diagram easier.
6.
Problem 9.6. Design a one-input one-output synchronous sequential circuit that
pro duces an output symbol z = 1 whenever any of the following input sequences
occurs: 1100, 1010, or 1001. The circuit resets to its initial state after an output
symbol 1 has been generated.
(a) Form the state diagram or table. (Seven states are sufficient.)
(b) Choose an assignment, and show the excitation functions for JK flip-flops.
• Given
• One input: x
• One output: z
• Synchronous sequential circuit
• Output z = 1 whenever any one of the following sequences occurs:
• 1100
• 1010
• 1001
• After output z = 1, the circuit resets to the initial states
Solution:
(a) State Diagram / State Table
Present State x Next State z
S0 0 S0 0
S0 1 S1 0
S1 0 S3 0
S1 1 S2 0
S2 0 S4 0
S2 1 S2 0
S3 0 S6 0
S3 1 S5 0
S4 0 S0 1
S4 1 S1 0
S5 0 S0 1
S5 1 S1 0
S6 0 S0 0
S6 1 S0 1
Continue…
(b) State Assignment & JK Flip-Flop Excitation
• State Assignment
• Let flip-flops be Q₂ Q₁ Q₀
State Assignment JK Flip-Flop Excitation Table (Reminder)
S0 000 Q Q⁺ J K
S1 001
0 0 0 X
S2 010
0 1 1 X
S3 011
S4 100 1 0 X 1
S5 101 1 1 X 0
S6 110
Continue….
8.
Problem 9.9. Construct the state diagram for a synchronous sequential
machine that can be used to detect faults in coded messages of the 2-
out-of-5 type. That is, the machine examines the messages serially and
produces an output symbol 1 whenever an illegal message of five
binary digits is detected.
Given
• Messages are encoded using 2-out-of-5 code
• Each valid code word:
• Has exactly two 1’s and three 0’s
• Length = 5 bits
• The machine:
• Examines input serially
• Produces output z = 1 whenever an illegal 5-bit message is detected
• Synchronous sequential machine
Solution:
The FSM must:
• Count the number of 1’s
• Track the number of bits received (up to 5)
State Means
S0 Start / 0 bits received
S1 1 bit received, 0 ones
S2 1 bit received, 1 one
S3 2 bits received, 0 ones
S4 2 bits received, 1 one
S5 2 bits received, 2 ones
S6 3 bits received
S7 4 bits received
S8 5 bits received – VALID (2 ones)
S9 5 bits received – INVALID (fault)
Continue:
The states are labeled in such a way that all the necessary information about the past
input values is contained in the state label.
The left digit indicates the number of 1’s that have been received so far, and the right digit
indicates the number of 0’s
Problem 9.11. A new kind of flip-flop has been designed. It is equivalent to an SR
flip-flop with gated inputs, as shown in Fig. P9.11. A synchronous sequential circuit that
generates an output symbol z = 1 whenever the string 0101 is scanned in the input sequence is to
be designed. Overlapping strings are accepted; for example, corresponding to the input sequence
0010101, the required output sequence is 0000101. (a) Construct the state diagram and table for
the circuit, using the letters A, B, C, etc. (b) Make a state assignment (use a Gray code, starting
with an all-0 assignment for the initial state). (c) Realize the sequential circuit using the new flip-
flops as memory elements. Give the logic equations for the memory elements and the output.
Solution:
Given
• A new flip-flop equivalent to a gated SR flip-flop
• Design a synchronous sequential circuit
• Output z = 1 whenever the input sequence 0101 is detected
• Overlapping sequences are allowed Present State x Next State z
• Example: A 0 B 0
Input: 0010101
Output: 0000101 A 1 A 0
B 0 B 0
(a).
B 1 C 0
C 0 D 0
C 1 A 0
D 0 B 0
D 1 E 0
E 0 B 1
E 1 A 1
Solution:
(b) State Assignment (Gray Code)
• Using Gray code, starting with all-zero initial state:
State Q₂ Q₁ Q₀
A 000
B 001
C 011
D 010
E 110
Solution:
(c) Realization Using New Flip-Flops
Note that in the1→1case, we can choose U and V to be either 0’sor1’s, but they must
be identical From the above table, we find one possible set of
equations: U1 = x′y1y2+xy′ 1y2+xy1y′ 2
V1 = 1
U2 = y′ 1y2+y1y′ 2+x′y′ 1
V2 = 1
12
Solution:
(a)The excitation requirements for a single memory element can be
summarized as follows:
The state assignment must be chosen such that neither memory
element will ever be required to go from state1 to state1. There are
two such assignments:
Continue:
Assignment α yields the following excitation table and logic equations:
Y1 = x′+y′2
Y2 = x
z = xy′1
Assignment β yields the same equations except for an interchange of
subscripts 1 and 2.
(b).
• The constraint that no memory element can make a transition from state1
to state1 means that not all state tables can be realized with a number of
memory elements equal to the logarithm of the number of states.
• An n-state table can always be realized by using an n-variable assignment
in which each state is represented by a “one-out-of-n” coding. Such
assignments are not necessarily the best that can be achieved and, in
general, it may be very difficult to find an assignment using the minimum
number of state variables.
14.
Problem 9.14. The synchronous circuit shown in Fig. P9.14, where D
denotes a unit delay, produces a periodic binary output sequence.
Assume that initially x1 = 1, x2 = 1, x3 = 0, x4 = 0 and that the initial
output sequence is 1100101000. Thereafter, this sequence repeats
itself. Find a minimal expression for the combinational circuit
f(x1,x2,x3,x4).
Solution:
A synchronous circuit with four unit delays (D)
• State variables:
𝑥1 , 𝑥2 , 𝑥3 , 𝑥4
• Output is taken from x₁
• Feedback input to the first delay is: f(x1,x2,x3,x4)
Initial Conditions
𝑥1 = 1, 𝑥2 = 1, 𝑥3 = 0, 𝑥4 = 0
Output sequence
1100101000
• Step 1: Understand the Shift Register Operation
• From the figure:
• Each clock pulse:
• 𝑥1 𝑡+1 = 𝑥2 𝑡
• 𝑥2 𝑡+1 = 𝑥3 𝑡
• 𝑥3 𝑡+1 = 𝑥4 𝑡
• 𝑥4 𝑡+1 = 𝑓 𝑥1 𝑥2 𝑥3 𝑥4
• Output:
• 𝑧 𝑡 = 𝑥1 𝑡
Continue…
• Step 2: Write State Transitions Using Output Sequence
Initial state:
𝑥1 𝑥2 𝑥3 𝑥4 = 1100
• Since output is 𝑥1 ,the given output sequence directly gives the successive values
of 𝑥1.
Time x₁ x₂ x₃ x₄ f
0 1 1 0 0 1
1 1 0 0 1 0
2 0 0 1 0 0
3 0 1 0 0 1
4 1 0 0 1 0
5 0 0 1 0 1
6 0 1 0 1 0
7 1 0 1 0 0
8 0 1 0 0 1
9 0 0 0 1 1
Continue…
• Step 3: Identify When f = 1
From the table:
• 𝑓 = 1 for states:
1100, 0100, 0010, 0001
• Step 4: Boolean Expression for f
Write the sum of minterms:
𝑓 = 𝑚 12 4 2 1
• Step 5: Minimize f
• Using Boolean simplification / K-map:
ˉ ˉ ˉ ˉ ˉ ˉ ˉ ˉ ˉ ˉ ˉ
𝑓 𝑥1 𝑥2 𝑥3 𝑥4 = 𝑥1 𝑥2 𝑥3 𝑥4 + 𝑥1 𝑥2 𝑥3 𝑥4 + 𝑥1 𝑥2 𝑥3 𝑥4 + 𝑥1 𝑥2 𝑥3 𝑥4
• Minimal Factored Form
ˉ ˉ ˉ ˉ ˉ ˉ
𝑓 = 𝑥4 𝑥1 𝑥2 + 𝑥1 𝑥2 + 𝑥1 𝑥3 + 𝑥1 𝑥2 𝑥3 𝑥4
15
Problem 9.15. A synchronous machine N is part of a transmitter and is used to
encode binary serial messages. The coded messages are then transmitted to a
receiver, as shown in Fig. P9.l5. The receiver contains a synchronous machine M
that is used to decode the received messages. (a) Given that the initial state of
N is A, find the state diagram of machine M.
(b) Suppose the initial state of N is unknown and machine M received a 10 bit
message; which of the 10 bits can be uniquely decoded without an error?
Explain
Solution:
An output of 0 from machine N identifies the final state as B, while an
output of 1 identifies the final state as A. Once the state of N is known, it
is straightforward to determine the input to N and the state to which N
goes by observing its output. Consequently, except for the first bit, each
of the subsequent bits can be decoded.
16.
Problem 9.16. A palindrome is a sequence which reads the same backward
as forward, e.g., 11011 or 01010. Show the finite-state control of a Turing
machine that is capable of detecting arbitrarily long palindromes. Assume
that you are given a tape initially marked only with symbols #, 0, 1, where
the blanks (#) separate blocks of intermixed 0’s and 1’s. The machine will
be started on a # and then checks whether the sequence to its right is a
palindrome. If not, the machine should proceed to the next block. If the
sequence is a palindrome, the machine should stop at the # to the right of
the block. An example is shown in Fig. P9.16
Solution:
A simple strategy can be employed here whereby the head moves back
and forth across the block comparing the end symbols and, whenever
they are identical, replacing them with 2’s and 3’s (for 0’s and 1’s,
respectively). At the end of the computation, the original symbols are
restored.
Continue…
• state A. Starting state. The machine restores the original symbols of the present block and moves to test
the next block.
• state B. (columns 0,1): The head checks the leftmost original symbol of the block. (columns 2,3): A
palindrome has been detected.
• states C and D. (#,0,1,2,3): The head searches for the rightmost original symbol of the block. State C is
for the case that the leftmost symbol is a 0, and D for the case that it is a 1.
• states E and F. (0,1): The head checks the rightmost symbol and compares it with the leftmost symbol. (E
is for 0 and F is for 1.) (2,3): At this point, the machine knows that the current symbol is the middle of an
odd-length palindrome.
• state G. The symbols that were checked so far can be members of a palindrome. (0,1,2,3): The head
searches for the leftmost original symbol of the block.
• state H. At this point, the machine knows that the block is not a palindrome. (0,1,2,3): The head goes to
the beginning of the block, so that it will be ready to restore the original symbols (as indicated in state A).
• state I. The machine now knows that the block is a palindrome. Therefore, the head goes to the beginning
of the block, so that it will be ready to restore the original symbols (as indicated in state J).
• states J and Halt: The original symbols are restored and the machine stops at the first # to the right of the
block.
18.
Problem 9.18. An iterative network to be used for detecting faults in
Ringtail-coded messages is to be designed. The network consists of five
cells, each receiving a digit of the coded message, and is to produce an
output symbol 1 when and only when an illegal message is detected. (The
Ringtail code is defined in Problem 5.2.) (a) Construct a cell table. (b) Select
an assignment and derive the logic equations for the output carries and the
cell output. (c) Construct a typical cell using AND, OR, and NOT gates.
Solution:
Continue…
State I is an initial state and it appears only in the first cell. It is not a necessary state for all
other cells. We may design the network so that the first cell that detects an error will produce
output value 1 and then the output values of the next cells are unimportant. In such a case,
state E is redundant and the transitions going out from C and D with a 1 output value may be
directed to any arbitrary state φ. The reduced state and excitation tables are as follows:
zi = x′ iyi1yi2 +xiyi1y′ i2
Yi1 = x′ iyi2 +xiy′ i2 +yi1
Yi2 = xi
If state E is retained, the realization will require three state variables.
19
Problem 9.19. The cell output of a typical cell of an iterative network
has the value 1 if and only if the input pattern of the preceding cells
consists of groups of 0’s and 1’s such that each group contains an odd
number of members. (a) Construct a cell table. (b) Realize the typical
cell using AND, OR, and NOT gates.
State A corresponds to an even number of zeros, B to an odd number of zeros, C to an odd number of ones,
and D to an even number of ones
Continue….
(b) The assignment and the corresponding equations are given next: A
→ 00, B → 01, C → 11, D → 10.
Yi1 = xi
Yi2 = y′ i2 +xiy′ i1yi2 + x′ iyi1yi2
zi = xiy′ i1yi2 +x′ iyi1yi2.
20.
Problem 9.20. The typical cell of an iterative network has one binary
input xi and one binary output zi. The output zi = 1 if and only if xi =
xi−2. For the first two cells (i.e., i =1,2), assume that x−1 = x0 = 0. (a)
Construct a cell table. (b) Make a Gray-code state assignment and give
the output and carry functions.