More design examples, state assignment and reduction

Page 1
 Serial Parity Checker

 We have only 2 states (S0, S1): correspond to an even and odd

number of 1’s received so far.

D Q
x
FF
Clock

 Z = 1 whenever circuit is in state S1 or in State S0 and X = 1

 Z = 0 whenever circuit is in state S0 or in State S1 and X = 1

X/Q 0 1

state codes: 0 0 1 D=X’Q+XQ’

S0 :0
S1 :1 1 1 0

Next State KM

Page 2
 Serial Comparator

 Inputs: data inputs (A,B),; an enable input (E) A

1, if A>b B comparator
Z
 Output: z= E
0, otherwise
Clock
 when enable is low, the output is zero
 when enable is high, the circuit compares A EAB
and B numerically (assuming the values are A>B
presented with the most-significant bit, 1xx /1
first) and outputs 1 if A>B. 0xx
110
Three states implies at least 2 flip flops. 101
One encoding is ??/
0xx, A<
•00 for state: ?? 0
100, B/0
•10 for state: A>B, 111 0xx
•01 for state: A<B
1xx

Page 3
 A>B EAB
00 01 11 10
1xx /1
000 0 0 0 0 0xx
001 0 0 0 0
110
 Output equation: 011 0 0 0 0 101
A>B = Q1Q0 (simplify to Q1) 0xx, ??/ A<
010 0 0 0 0
 Next state equations: 100, 0 B/0
100 0 0 0 1 111 0xx
DQ1=(Q1+Q0AB )E
=(Q1+Q0AB )E 101 0 0 0 1

DQ0=(Q0+Q1Q0AB )E
1xx
111 0 0 0 1
=(Q0+Q1AB )E 110 1 0 0 1
Present Next
State Inputs State Output
Q1 Q1Q0 EAB Q1Q0 A>B

00 0xx 00 0
00 100 00 0
00 111 00 0
00 110 10 0
00 101 01 0
10 1xx 10 1
10 0xx 00 1
01 1xx 01 0
01 0xx 00 0
Page 4
Example using JK

PS X NS Using JK
Q1Q0 Q1Q0 00
JK=1x 11
0 0 0 0 0 X=1
JK=x0
0 0 1 0 1 X=0
0 1 X 1 0 0 1 01
10
1 0 X 1 1
JK=0x
1 1 X 0 0 JK=x1
X=0 X=1 X=0 X=1
J(Q1) Q1Q0 Q1Q0
00 (0->0):0 (0->0)0 00 X X
01 (0->1):1 (0->1)1 01 1 X
K(Q1)
10 (1->1):X (1->1)X 10 0 0
11 (1->0):X (1->0)X 11 1 1

Page 5
State Assignment

 Selecting binary patterns for the symbolic states impacts circuit complexity.

 Outputs and FF input equations depend on current state and are therefore
influenced by the assignment of binary values to states.

 We also have an option in how many flip-flops we use.

 We can use more than the minimum number of flip-flops and this might result in
much simpler logic equations for the flip-flop inputs and circuit outputs.

 We will consider several different encoding schemes.

E&CE 223 Digital Circuits and Systems (A. Kennings) Page 6

Example

 Assume we have the following state diagram. Circuit requires 7 states (S0, … , S6)
and has 3 inputs (R, B, W). Circuit has 4 outputs (say A, B, C and D).

R S2/0100
!W

R W RB R R
S0/0000 S1/0000 S3/1000 S4/1001 S5/1010 S6/1011

R !B
R

E&CE 223 Digital Circuits and Systems (A. Kennings) Page 7

Encoding Scheme – Targeting Minimum FF Count

 With n-bits (i.e., n flip-flops) we can encode 2n states. This always gives the
minimum number of flip-flops required.

 In our example, we have 7 states and therefore would need 3 bits for encoding.

 S0 Ã 000, S1 Ã 001
 S2 Ã 010, S3 Ã 011
 S4 Ã 100, S5 Ã 101
 S6 Ã 110

 Note: There is still “room” for one more state to be encoded.

 Note: No particular method for assigning any given binary pattern to any particular
symbolic state.

 Will need to derive next state equations and output equations…

E&CE 223 Digital Circuits and Systems (A. Kennings) Page 8

Encoding Scheme – Output Encoding Method

 Sometimes, we can encode the states such that the output of the flip-flops are
ALSO the outputs of the circuit!!!

 Counters are circuits that are good examples of output encodeing...

 We will see this again later when we talk about counters…

 Consider listing the states of the system, along with their outputs.

E&CE 223 Digital Circuits and Systems (A. Kennings) Page 9

Encoding Scheme – Output Encoding Method

 When we list outputs along with states, we will see one of two cases:

 CASE 1: Outputs for each state are distinct (output value becomes the state
encoding).

 CASE 2: Outputs for some states are identical (add additional bits to
distinguish those states with identical outputs).

E&CE 223 Digital Circuits and Systems (A. Kennings) Page 10

Encoding Scheme – Output Encoding Method

 In our example, we need to add an extra bit to distinguish between S0 and S1:

 Can encode states using 5 flip-flops (let don’t cares be 0 for illustration purposes):
 S0 Ã 00000, S1 Ã 00001, S2 Ã 01000, S3 Ã 10000
 S4 Ã 10010, S5 Ã 10100, S6 Ã 10110

E&CE 223 Digital Circuits and Systems (A. Kennings) Page 11

Encoding Scheme – Output Encoding Method

 Uses more flip-flops that minimum flip-flop method.

 However, no output equations (less logic, less output delays) since outputs come
directly from flip-flop outputs.

 Potentially many unused states, and we might need to be careful about unused
states.

E&CE 223 Digital Circuits and Systems (A. Kennings) Page 12

Encoding Scheme – One-Hot Encoding

 Use 1 flip-flop per state (i.e., n states means n flip-flops).

 Only the output of 1 flip-flop is ever high at any given time. When the flip-flop
output is 1, then we know which state we are in.

 Generally (although not always), one-hot encoding reduces logic required for
output equations and next state equations, but uses more flip-flops.

 For our example we have 7 states, so with one hot encoding, we would need 7 flip-
flops and use the following encoding scheme:

 S0 Ã 0000001, S1 Ã 0000010, S2 Ã 0000100, S3 Ã 0001000

 S4 Ã 0010000, S5 Ã 0100000, S6 Ã 1000000

E&CE 223 Digital Circuits and Systems (A. Kennings) Page 13

State Reduction

 In generating a state table/diagram from a verbal description, can get more states
than required.

 The number of flip-flops, complexity of next state and output equations, etc. all
depend on the number of states, it is reasonable to ask if a state table/diagram can
be simplified to remove redundant states.

 Sometimes, states are equivalent to each other and can be combine into a single
state.

E&CE 223 Digital Circuits and Systems (A. Kennings) Page 14

Equivalent States

 Two states are said to be equivalent if:

 For each circuit input, the states give exactly the same outputs, AND

 For each circuit input, the states give the same next state or an equivalent
next state.

E&CE 223 Digital Circuits and Systems (A. Kennings) Page 15

State Reduction

 “Row Matching” is based on the state-transition table:

• If two states
 have the same output and both transition to the same next state
 or both transition to each other
 or both self-loop
 then they are equivalent.
• Combine the equivalent states into a new renamed state.
• Repeat until no more states are combined

State Transition Table

NS output
PS x=0 x=1
S0 S0 S1 0
S1 S1 S2 1
S2 S2 S1 0
Row Matching Example
Row Matching Example
 Call d

Call e

Page 19
Reduced states

Reduced State Transition Diagram

E&CE 223 Digital Circuits and Systems (A. Kennings) Page 20

State Reduction Methods

 Other methods for state reduction:

 Implication charts and merger diagrams.

 Partitioning.

E&CE 223 Digital Circuits and Systems (A. Kennings) Page 21

Example – Implication Charts and Merger Diagrams

 Consider the following state table for a 1-input, 1-output circuit.

 Our initial design resulted in a state table with 5 states and needs at least 3 flip-
flops. But, we can do better…

E&CE 223 Digital Circuits and Systems (A. Kennings) Page 22

Implication Charts

 We can tabulate equivalencies in a so-called implication chart.

 The implication chart looks like the lower triangle of a matrix – each entry is
intended to tell us under what conditions two states are equivalent.

S1

S2

S3

S4

S0 S1 S2 S3

State table Implication chart

E&CE 223 Digital Circuits and Systems (A. Kennings) Page 23

Implication Charts

 We begin by marking entries in the implication chart with an “x” if two states
cannot be equivalent due to different output values.

S1

S2

S3

S4

S0 S1 S2 S3

State table Implication chart

E&CE 223 Digital Circuits and Systems (A. Kennings) Page 24

Implication Chart – Equivalent States

 Next, we mark entries that are definitely equivalent. We also mark entries that
are equivalent under implied decisions.

S1

S2

(S0,S1)

S3 (S3,S4)

(S0,S2) (S1,S2)

S4 (S1,S3)

S0 S1 S2 S3

State table Implication chart

E&CE 223 Digital Circuits and Systems (A. Kennings) Page 25

Implication Chart

 Finally, we perform passes over the entries from top-left to bottom-right trying to
cross out those states that cannot be equivalent due to implied decisions.

S1

S2

(S0,S1)

S3 (S3,S4)

(S0,S2) (S1,S2)

S4 (S1,S3)

S0 S1 S2 S3

State table Implication chart

E&CE 223 Digital Circuits and Systems (A. Kennings) Page 26

Merger Diagram

 From the implication chart, we can built a graph (Merger Diagram) that shows
merges. Nodes are states and edges represent equivalency.

 Boxes with any “x” in them represent non-equivalent states. Boxes with all “v” in
them represent equivalency and are represented by an edge.

S1
S0

S2

(S0,S1)
S2
S3 (S3,S4) S1
(S0,S2) (S1,S2)

S4 (S1,S3)

S3 S4
S0 S1 S2 S3

Implication chart Merger Diagram

E&CE 223 Digital Circuits and Systems (A. Kennings) Page 27

Important…

 We need to make sure each state is included somewhere:

 We are okay, since S0, … , S4 are all included.

 We need to check the implied decisions hold…

 E.g., (S0,S2) are always equivalent, so this is okay.

 E.g., (S1,S4) required that (S0,S2) are implied (see implication chart). We
have this merge, so it is true, and we are okay.

 Since implied decisions all check out, our reduction is good and we are done.

E&CE 223 Digital Circuits and Systems (A. Kennings) Page 28

Final Result

 Merge (S0,S2), (S1,S4) and

(S3).

 Our original state table that

had 5 states and needed at
least 3 flip-flops.

 Our new, and reduced, state

table that has only 3 states
and needs only 2 flip-flops.

 Both tables will implement the

same design, but the reduced
state stable will likely result in
a simpler and smaller circuit.

E&CE 223 Digital Circuits and Systems (A. Kennings) Page 29

Textbook

 Reduction of state tables using implication charts and merger diagrams is covered in
Chapter 9, Section 9.5 of the course textbook.

E&CE 223 Digital Circuits and Systems (A. Kennings) Page 30

Example - Partitioning

 Consider the following state table for a circuit with 1 input A and 1 output Z:

 Can divide states into partitions (or groups) of equivalent states.

E&CE 223 Digital Circuits and Systems (A. Kennings) Page 31

Partitioning - Procedure

 Procedure:
 FIRST: Group states according to circuit outputs produced.
 States are only equivalent if their outputs are the same for all input
patterns.
 So, we get groups in which all the states in each group might be
equivalent.
 LOOP: For each group, consider each input pattern.
 If, for any input pattern, different states in a group result in a
transition to a different other groups, then those states are not
equivalent.
 So, we separate the group in to two smaller groups.

 Continue dividing groups into smaller partitions until all the states in any group
transition to the SAME other group for ANY input pattern.

 Once we reach the point where further division of groups is not required, we have
identified the equivalent states.

E&CE 223 Digital Circuits and Systems (A. Kennings) Page 32

Partitioning - Illustration

 Consider our example… We can see that, in fact, there are only 3 required states
(and not 5) since some states are equivalent.

 This means less flip-flops and (likely) less logic to produce next state and
output equations.

(S0,S2) (S0,S2)

(S1,S4)

(S0,S1,S2,S3,S4)

(S1,S3,S4) (S3)

divide based on outputs divide based on next state

E&CE 223 Digital Circuits and Systems (A. Kennings) Page 33

Partitioning – Final Result

 We can merge together equivalent states and end up with a smaller state diagram
and state table:
1
1

(S0,S2) (S0,S2)
(S0,S2)

0 0
(S1,S4)
1
0 (S1,S4)
0
1
(S0,S1,S2,S3,S4)
0

(S1,S3,S4) (S3)
0
1
(S3)
divide based on outputs divide based on next state
1

E&CE 223 Digital Circuits and Systems (A. Kennings) Page 34

Textbook

 State assignment and state reduction is covered in the textbook in Chapter 5,

Section 5.6

E&CE 223 Digital Circuits and Systems (A. Kennings) Page 35