Transcript EEE515J1_L4+tut_answers

EEE515J1
ASICs and DIGITAL DESIGN
EGBCDCNT.pdf
An example of a synchronous sequential
machine by the generalised method
Ian McCrum
Room 5D03B
Tel: 90 366364 voice mail on 6th ring
Email: [email protected]
Web site:
http://www.eej.ulst.ac.uk
www.eej.ulster.ac.uk/~ian/modules/EEE515J1/
EEE515J1_L4-1/12
In general designing FSMs depends on
•defining a STATE DIAGRAM and then
•a CRUDE STATE TABLE.
•Flipflop types are chosen,
•their characteristic equations and tables identified. The next stage is to
decide
•what binary patterns will be used for each state, this is the STATE
ASSIGNMENT. The rest of the stages are straightforward , if a bit tedious:
•a FULL STATE TABLE is drawn. From this, KMAPS of the circuits that
feed the flipflop inputs are drawn and minimised.
•The resulting circuit implements the FSM. In some cases
•STATE REDUCTION may be possible.
www.eej.ulster.ac.uk/~ian/modules/EEE515J1/
EEE515J1_L4-2/12
•It is important you realise that shortcuts are possible: these save time
but may obscure your understanding of the complete process. We will
skip many of the steps above in this particular example. There are a
number of reasons for this. Counters with no inputs are very simple.
•In counter design the states of our circuit are usually chosen to be the
same as our desired outputs, this saves gates. This is possible only if all
outputs in our sequence are unique. Every state must have a unique
binary code. The second simplificatioin is that because we are
implementing using a FPGA we are forced to use D-Types and Logic
Minimisation is not necessary. In fact designing with D-Types is also
particularly easy though I will use the longwinded approach to D-types
below, you may observe I have added columns that are not needed. This
is to show the general purpose full state table which we will use for JK
and other implementations.
www.eej.ulster.ac.uk/~ian/modules/EEE515J1/
EEE515J1_L4-3/12
•Example A BCD counter that sequences from 0 to 9 as the clock
pulses.
•A state diagram for a simple counter is trivial.... merely 10 state circles
looped in a circle
•In general there are two ways of drawing State Diagrams, with outputs
associated with the states alone or associated with both a state and an
input condition. ( Moore type and Mealy type).
A
B
C
D
E
F
G
H
I
J
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
www.eej.ulster.ac.uk/~ian/modules/EEE515J1/
EEE515J1_L4-4/12
The crude state table merely lists the present states, coded as a letter or
symbol and the next states. It also lists the desired present outputs for
each present state. Normally this table must take into account all
possible input patterns, though here we have no inputs.
PRESENT
STATE
NEXT
STATE
PRESENT OUTPUT
A
B
0000
B
C
0001
C
D
0010
D
E
0011
E
F
0100
F
G
0101
G
H
0110
H
I
0111
I
J
1000
J
A
1001
www.eej.ulster.ac.uk/~ian/modules/EEE515J1/
EEE515J1_L4-5/12
In general we choose flipflop types and the STATE ASSIGNMENT
For fairly obvious reasons we will choose the following state codes
State
Code
State
Code
A
0000
F
0101
B
0001
G
0110
C
0010
H
0111
D
0011
I
1000
E
0100
J
1001
www.eej.ulster.ac.uk/~ian/modules/EEE515J1/
EEE515J1_L4-6/12
Consider the D-Type flipflop.
We use verbs of Action to denote changes of state. These changes
do not occur until the clock changes. Thus the verb of RESET is
initiated by putting D low but the output of the flipflop will not
change until the active transition of the clock, either the
appropriate edge or the appropriate level
D Input
Action
0
RESET
1
SET
Using this information we can draw up a FULL STATE TABLE.
www.eej.ulster.ac.uk/~ian/modules/EEE515J1/
EEE515J1_L4-7/12
PRESENT
NEXT
STATE
NEXT STATE BITS. We look at each bit of the next state in turn and state what
ACTION is required of our flipflops to cause the next bit to become the correct
value. We also write down what INPUT to our flipflops will cause this action.
STATE
P
PQRS
DP
Q
DQ
R
DR
S
DS
A
0000
B
PQRS
0001
B
0001
C
0010
RESET
0
RESET
0
SET
1
RESET
0
C
0010
D
0011
RESET
0
RESET
0
SET
1
SET
1
D
0011
E
0100
RESET
0
SET
1
RESET
0
RESET
0
E
0100
F
0101
RESET
0
SET
1
RESET
0
SET
1
F
0101
G
0110
RESET
0
SET
1
SET
1
RESET
0
G
0110
H
0111
RESET
0
SET
1
SET
1
SET
1
H
0111
I
1000
SET
1
RESET
0
RESET
0
RESET
0
I
1000
J
1001
SET
1
RESET
0
RESET
0
SET
1
J
1001
A
0000
RESET
0
RESET
0
RESET
0
RESET
0
REST
-
xxxx
-
x
-
x
-
x
-
x
RESET
0
RESET
0
RESET
0
SET
1
www.eej.ulster.ac.uk/~ian/modules/EEE515J1/
EEE515J1_L4-8/12
From the table above we see that we want to generate DP = 1 when we are in a
present state of H or I. In other words if the four flipflops are presently
outputting { 0111 or 1000}. We have a combinational network, called the
NEXT STATE FORMING network, or the NEXT STATE DECODER that
generates
DP= /P* Q* R* S + P*/Q*/R*/S
DQ= /P*/Q*R* S + /P*Q*/R*/S +/P* Q* /R* S +/P* Q* R* /S
DR= /P*/Q*/R* S + /P*/Q* R* /S +/P* Q* /R* S +/P* Q* R* /S
DS= /P*/Q*/R*/S + /P*/Q* R* /S +/P* Q* /R*/S +/P* Q* R* /S + P*/Q*/R*/S
www.eej.ulster.ac.uk/~ian/modules/EEE515J1/
EEE515J1_L4-9/12
The steps in designing a counter or any clocked sequential machine that
has inputs are as follows
•
1) Produce a formal specification for the design; usually a state
diagram, sometimes a timing diagram
•
2) Produce a crude state table, this has letters representing states and
is just a text version of the state diagram.
•
3) If the state diagram is complex it may be that superfluous states
exist. The technique of state reduction is simple but tedious, it finds
what states can be considered equivalent and allows a simpler state
diagram to be drawn. Equivalent states have identical outputs for all
possible inputs and also have identical next states for all inputs. (or
the next states must subsequently proven to be equivalent)
•
4) Decide what binary code should be used for each state, if you have
many outputs it may be sensible to use the actual output code as the
state code. The only rule is that each state must have a unique code.
This problem is called the state assignment problem; two common
assignments are straight binary where A=00, B=01, C=10 and D=11 for a 4state machine or the one hot code where we use one bit per state and have
only one bit "hot", the code for a 4 bit problem would be (0001,0010,0100
and 1000). One hot codes are very inefficient but very easy to design
with. If implementing designs in a register rich device it may be worth
using it. The third option is to use the desired outputs, possibly with
the addition of an extra bit or two to ensure every state is unique. A
fourth option is to apply state assignment guidelines to find a pattern
that minimises the cost of the final combinational network.
www.eej.ulster.ac.uk/~ian/modules/EEE515J1/
EEE515J1_L4-10/12
Continued
•
•
•
•
5) Once the code is known, the flipflop type can be chosen, D-Types are
the easiest while JK or T-Types offer more minimal logic, the
combinational next state decoder will have fewer gates. Such flipflops are
more expensive so it is not always worth the added expense (I use a cost
model of 6p and 9p for Ds and Others)
6) The full state table can now be drawn up. It must show the present and
next state bits. The change from one to the other must be analysed and
expressed in a verb that the flipflop is capable of supplying: D-types can
reset or set the next state, T-types can hold or toggle a bit and JKs can
Hold, Reset, Set or toggle a bit (the verbs of action for JKs are often
expressed as stay at zero, stay at one, goto 1 and goto 0)
7) Once we know what actions we require of our flipflops we can write
down what pattern of 0s and 1s we must apply to the flipflop inputs to
cause this to occur, you will need 2n patterns to control n JK flipflops.
We write these into the full state table using the characteristic table
for the relevant flipflop.
8) We can now design the combinational network that takes the present
state of the circuit, the present output of the flipflops and the present
inputs and produces the required signals to the flipflops so that they
will click to the correct next state when the clock pulse arrives, the
output circuit can also be drawn. The combinational circuits can be
minimised with KMAPS. This gives the solution as the specification for the
Next State Decoder and the Output Decoder
www.eej.ulster.ac.uk/~ian/modules/EEE515J1/
EEE515J1_L4-11/12
Exercise:Tut 1
• (a)
Design a counter that counts from 0 to
15 but misses out 13 (a superstitious counter)
• (b)
Design an excess-3 counter that counts
from binary 0011 to 1100 by
• (b)(i) Designing a counter that uses the
desired outputs as the actual state codes.
• (b)(ii) Designing an output combinational
circuit that has a 4 bit BCD input and a 4 bit
Excess-3 output
• (c) Design an Up/Down Counter that counts 0 to
7, the circuit has one input labeled DIRN.
www.eej.ulster.ac.uk/~ian/modules/EEE515J1/
EEE515J1_L4-12/12
(a)
Design a counter that counts from 0 to 15 but
misses out 13 (a superstitious counter)
0000
0001
0010
0011
0001
0010
0011
0100
0
0
0
0
0
0
0
1
0
1
1
0
1
0
1
0
0100
0101
0110
0111
0101
0110
0111
1000
0
0
0
1
1
1
1
0
0
1
1
0
1
0
1
0
1000
1001
1010
1011
1001
1010
1011
1100
1
1
1
1
0
0
0
1
0
1
1
0
1
0
1
0
1100
1101
1110
1111
1110
xxxx
1111
0000
1
x
1
0
1
x
1
0
1
x
1
0
0
x
1
0
Dp:=
/PQRS + P/Q + PQ/S
1
(last two on-terms combined
because R does not matter)
Dq:= /P/QRS + /PQ/R
+ /PQR/S + P/QRS + PQS/
Dr:= /P/RS + /PR/S + P/RS + PR/S
+ PQ/R/S
Combine two red ovals by
eliminating Q + /Q
Ds:=/P/S
+ P/Q/S + PQR/S
www.eej.ulster.ac.uk/~ian/modules/EEE515J1/
EEE515J1_L4-13/12