Computer Science 150 Homework Assignment 6
Spring 1997 Solutions
1. A two-button electrical lock
will actuate according to the following sequence:
A: 0 1 1 1 1 0 1
B: 0 0 1 0 1 1 1
Z: 0 0 0 0 0 0 1
Z=1 opens the lock and is the circuit
output while A and B correspond to the two buttons. A switch being depressed
(pushed and held down) corresponds to a 1 and a switch being released (removing
one’s finger from the button) corresponds to a zero. Releasing both buttons
clears the circuit and only one button may be pressed or released at
a time, as is the case in the above sequence.
(a) Obtain a primitive flow
table for the circuit. [20]
STATE
|
NS (IN=AB)
|
Z
|
|
00
|
01
|
11
|
10
|
|
A(00)
|
A
|
H
|
-
|
B
|
0
|
B(00,10)
|
A
|
-
|
C
|
B
|
0
|
C(00,10,11)
|
-
|
H
|
C
|
D
|
0
|
D(00,10,11,10)
|
A
|
-
|
E
|
D
|
0
|
E(00,10,11,10,11)
|
-
|
F
|
E
|
J
|
0
|
F(00,10,11,10,11,01)
|
A
|
F
|
G
|
-
|
0
|
G(00,10,11,10,11,01,11)
|
-
|
H
|
G
|
J
|
1
|
H(01)
|
A
|
H
|
I
|
-
|
0
|
I(11)
|
-
|
H
|
I
|
J
|
0
|
J(10)
|
A
|
-
|
I
|
J
|
0
|
(b) Obtain a reduced, merged
flow table by eliminating any redundant states and by merging equivalent
states. Show your merger diagram. [20]
No reductions are possible (no rows with stable states in the same column
can be combined).
Merger Diagram:
Merged, Reduced Flow Table:
STATE
|
NS (IN=AB)
|
Z
|
|
00
|
01
|
11
|
10
|
|
A(00 / 00,01)
|
A
|
H
|
C
|
A
|
0
|
C(00,10,11)
|
-
|
H
|
C
|
D
|
0
|
D(00,10,11,10)
|
A
|
-
|
E
|
D
|
0
|
E(00,10,11,10,11)
|
-
|
F
|
E
|
H
|
0
|
F(00,10,11,10,11,01)
|
A
|
F
|
G
|
-
|
0
|
G(00,10,11,10,11,01,11)
|
-
|
H
|
G
|
H
|
1
|
H(01 / 11 / 10)
|
A
|
H
|
H
|
H
|
0
|
(2) Consider the merged flow table
shown opposite:
Perform a race-free state-assignment
using as few internal state variables as possible. Indicate all required
adjacency constraints and list your final state codes. Be very
clear in explaining how you arrived at your result. [40]
Translating the table to use the lettered states instead of the numbered
states (since 8,9, and 10 are the same state, h), and assuming fundamental
mode, we get the following flow table:
|
00
|
01
|
11
|
10
|
a
|
a
|
h
|
-
|
b
|
b
|
a
|
-
|
c
|
b
|
c
|
-
|
h
|
c
|
d
|
d
|
a
|
-
|
e
|
d
|
e
|
-
|
f
|
e
|
h
|
f
|
a
|
f
|
g
|
-
|
g
|
-
|
h
|
g
|
h
|
h
|
a
|
h
|
h
|
h
|
adjacency constraints:
a->h,b
b->a,c
c->h,d
d->a,e
e->f,h
f->a,g
g->h
h->a
We are using 4 bits state codes because we're assuming that glitches are
not okay. If it were assumed that glitches on the ouput were okay,
then it was not necessary to use 4 state bits (3 would have been okay,
but you'd have to modify the flow table to reuse existing stes as transition
states, which may cause unwanted/incorrect/glitched outputs). There
is no set method to find state assignment using the fewest number of additional
states without essentially trying every possibility. Here is one
possible race-free state assignment that uses 3 additional states done
by trial-and-error:
S1S0\S3S2
|
00
|
01
|
11
|
10
|
00
|
a
|
b
|
c
|
h
|
01
|
t1
|
t2
|
d
|
e
|
11
|
t3
|
|
|
f
|
10
|
|
|
|
g
|
The assignment satisfies all transitions but d->a (on input 00) and f->a
(on input 00). t1 and t2 are used as transition states for d->a (so
it goes d->t2->t1->a). t3 and t1 are used for f->a (so it goes f->t3->t4->a).
Note that t1 used to eliminate both races.
The resulting race-free flow table:
|
00
|
01
|
11
|
10
|
a
|
a
|
h
|
-
|
b
|
b
|
a
|
-
|
c
|
b
|
c
|
-
|
h
|
c
|
d
|
d
|
t2
|
-
|
e
|
d
|
e
|
-
|
f
|
e
|
h
|
f
|
t3
|
f
|
g
|
-
|
g
|
-
|
h
|
g
|
h
|
h
|
a
|
h
|
h
|
h
|
t1
|
a
|
-
|
-
|
-
|
t2
|
t1
|
-
|
-
|
-
|
t3
|
t1
|
-
|
-
|
-
|
You can verify that the flow table is race-free by checking that the next-states
of each row are all adjacent to the present state (the state the row corresponds
to).
State Codes: a=0000, b=0100, c=1100, d=1101, e=1001, f=1011, g=1010, h=1000,
t1=0001, t2=0101, t3=0011