A car counter keeps track of number of cars parked in a garage with a maximum ca
ID: 3666079 • Letter: A
Question
A car counter keeps track of number of cars parked in a garage with a maximum capacity of 3 cars. The counter uses a two-bit register to represent its current state, and the state value is equal to the number of cars currently parked in the garage. The input In is 1 when a new car enters the garage, and 0 otherwise. The input Out is 1 when a car leaves the garage, and 0 otherwise. In and Out can never be 1 at the same time. The output Full is used to indicate if the garage is full (1) or not (0).
Fill in the following state table for the Mealy version of the car counter FSM.
P1
P0
In
Out
N1
N0
Full
0
0
0
0
0
0
0
1
0
0
1
0
0
0
1
1
0
1
0
0
0
1
0
1
0
1
1
0
0
1
1
1
1
0
0
0
1
0
0
1
1
0
1
0
1
0
1
1
1
1
0
0
1
1
0
1
1
1
1
0
1
1
1
1
Provide the function formulas for N1, N0and Full for the above table. Do not show the K-maps. Show just the function formulas.
P1
P0
In
Out
N1
N0
Full
0
0
0
0
0
0
0
1
0
0
1
0
0
0
1
1
0
1
0
0
0
1
0
1
0
1
1
0
0
1
1
1
1
0
0
0
1
0
0
1
1
0
1
0
1
0
1
1
1
1
0
0
1
1
0
1
1
1
1
0
1
1
1
1
Explanation / Answer
Next State Present State In 1 1 1 1 1 1 Z 1 1 1 n0 1 1 n1 x 1 x 1 1 n2 …… 1 1 1 1 1 p0 1 1 1 p1 1 1 p2 1 1 1 1 …… X X X 1 11 X X 1 01 1 01 1 11 10 1 00 10 00 1 1 1 1 1 1 1 Out Next State Present State In 1 1 1 1 1 1 Z 1 1 1 n0 1 1 n1 x 1 x 1 1 n2 …… 1 1 1 1 1 p0 1 1 1 p1 1 1 p2 1 1 1 1 …… X 20 Digital Design Copyright © 2006 Frank Vahid Mealy FSM vs. Moore FSM • Output – Mealy: depends on both inputs and presents – Moore: doesn’t depend on inputs • State Diagram – Mealy: less states -> less number of flip-flops – Moore: more states than Mealy -> bigger implementation • Speed of output response to the inputs – Mealy: quick, as soon as input changes – Moore: as long as one clock cycle delay • TIMING ISSUE – Mealy: asynchronous, may cause serious problem – Moore: synchronous, more stable 21 Digital Design Copyright © 2006 Frank Vahid Mealy vs. Moore • Q: Which is Moore, and which is Mealy? Inputs: b; Outputs: s1, s0, p Time Alarm Date Stpwch b’/s1s0=00, p=0 b/s1s0=00, p=1 b/s1s0=01, p=1 b/s1s0=10, p=1 b/s1s0=11, p=1 b’/s1s0=01, p=0 b’/s1s0=10, p=0 b’/s1s0=11, p=0 Inputs: b; Outputs: s1, s0, p Time S2 Alarm b b b b b b b s1s0=00, p=0 s1s0=00, p=1 s1s0=01, p=0 s1s0=01, p=1 s1s0=10, p=0 s1s0=10, p=1 s1s0=11, p=0 s1s0=11, p=1 S4 Date S6 Stpwch S8 b’ b’ b’ b’ Mealy Moore • A: Mealy on left, Moore on right – Mealy outputs on arcs, meaning outputs are function of state AND INPUTS – Moore outputs in states, meaning outputs are function of state only 22 Digital Design Copyright © 2006 Frank Vahid Mealy and Moore can be Combined • Final note on Mealy/Moore – May be combined in same FSM Inputs: b; Outputs: s1, s0, p Time Alarm Date Stpwch b’/p=0 b/p=1 s1s0=00 s1s0=01 b/p=1 b/p=1 s1s0=10 b/p=1 s1s0=11 b’/p=0 b’/p=0 b’/p=0 Combined Moore/Mealy FSM for beeping wristwatch example 23 Digital Design Copyright © 2006 Frank Vahid Optimization by State Reduction • Goal : Reduce number of states in FSM without changing behavior – Fewer states potentially reduces size of state register • Consider the two FSMs below with x =1, then 1, then 0, 0 x state y x state y S0 S0 S1 S1 S1 S1 S2 S0 S2 S0 S0 S1 y=0 y=1 S2 y=0 S3 y=1 x x x x’ x’ x x’ x’ Inputs: x; Outputs: y S0 S1 y=0 y=1 x’ x x x’ For the same sequence of inputs, the output of the two FSMs is the same a 24 Digital Design Copyright © 2006 Frank Vahid S0 S1 y=0 y=1 S2 y=0 S3 y=1 x x x x’ x’ x x’ x’ Inputs: x; Outputs: y Another Method for State Reduction 1 S3 S3 1 1 1 1 Z S0 S3 S2 S1 S2 S1 S0 N.S. S3 S2 S2 S1 S1 S0 S0 P.S. 1 1 1 X Can’t reduce more, No equivalent states 25 Digital Design Copyright © 2006 Frank Vahid • State reduction through state table inspection isn’t optimal • A more methodical approach – Implication Tables • Example: State Reduction with Implication Tables S0 S1 y=0 y=1 S2 y=0 S3 y=1 x x x x’ x’ x x’ x’ Inputs: x; Outputs: y Redundant Diagonal S0 S0 S1 S2 S3 S1 S2 S3 – To compare every pair of states, construct a table of state pairs (above right) – Remove redundant state pairs, and state pairs along the diagonal since a state is equivalent to itself (right) S0 S0 S1 S2 S3 S1 S2 S3 S0 S1 S2 S1 S2 S3 26...
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.