THIS POST IS CONTRIBUTED BY ARPANA FROM NATIONAL INSTITUTE OF TECHNOLOGY, SILCHAR
PROBLEM:
DESIGN A TRAFFIC LIGHT SYSTEM USING D FLIP FLOP:
INTRODUCTION:
In this project, we
have to design a digital traffic light system
using D flip flop. In other words, we will design a synchronous digital
circuit, a Moore machine, which operates the traffic lights at a simple road
crossing.
ANALYSIS OF THE TRAFFIC LIGHT SYSTEM:
Traffic light system consists of six lights to operate. The Red, Amber, and Green lights in the North-South direction will be designated as R1, A1, G1. Similarly, the lights in the East-West direction will be called R2, A2, and G2.
When the digital signals are in the Logic-1 state they turn their respective lights on, otherwise the lights are off. A digital clock signal will be supplied and at each clock pulse the lights should change according the schedule given above. There are two types of road crossing: safe ones that require one sequence, and dangerous ones that require another (delayed green) sequence. One digital input signal called SAFE will indicate whether the road crossing is safe. Thus, we have a one-input, six-output synchronous system to design.
N-S E-W
SAFE
RED GREEN
RED AMBER
GREEN RED
AMBER RED
RED GREEN
UNSAFE
RED GREEN
RED AMBER
RED RED
GREEN RED
AMBER RED
RED RED
RED GREEN
DETERMINATION OF NUMBER OF STATES :
We have a one input six output system as shown in the above diagram and the transition table can be as follows:
|
SAFE=0 |
SAFE=1 |
|||||||||||||||
|
<-1-> |
<-2-> |
<-1-> |
<-2-> |
|||||||||||||
|
R |
A |
G |
R |
A |
G |
R |
A |
G |
R |
A |
G |
|||||
|
1 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
|||||
|
1 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
|||||
|
1 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
|||||
|
0 |
0 |
1 |
1 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
|||||
|
0 |
1 |
0 |
1 |
0 |
0 |
|
|
|||||||||
|
1 |
0 |
0 |
1 |
0 |
0 |
|||||||||||
|
1 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
|||||
From the table, there are six
states in the first column (dangerous intersection) and four states in the
second. All the four states in the second column are also included in the first
column so we don’t need to count the four states from the second column. So,
total states will be six.
|
STATE |
N-S
<-1-> |
E-W <-2-> |
||||
|
R |
A |
G |
R |
A |
G |
|
|
1 |
1 |
0 |
0 |
0 |
0 |
1 |
|
2 |
1 |
0 |
0 |
0 |
1 |
0 |
|
3 |
1 |
0 |
0 |
1 |
0 |
0 (A) |
|
4 |
0 |
0 |
1 |
1 |
0 |
0 |
|
5 |
0 |
1 |
0 |
1 |
0 |
0 |
|
6 |
1 |
0 |
0 |
1 |
0 |
0(B) |
The states labeled as A and B are
same but they can’t be merged because after state 3, the state is 4 but after
state 6 the state is 1
SELECTION OF NUMBER FLIP FLOPS:
There are six states, so we have
N = 6.
Solving 2^P–1 < N £
2^P for P, the number of flip–flops.
2^P–1 < 6 £ 2^P gives P = 3, because
2^2 < 6 £ 2^3
Since the number of states is
equal to six, the minimum number of flip-flops, which can support six states,
is three. The maximum number of flip-flops one may use is six (one flip-flop
per state). For this design example we will use three D-type flip-flops. There
will be two unused states.
ASSIGN STATE NUMBERS TO FLIP FLOP OUTPUTS AND
CONSTRUCTION OF TRANSITION TABLE:
We will minimize the K-maps only
for 1. Therefore, we will not use the two states 000 and 001, which will be the
two unused states 7 and 8. The idea behind this choice is that a large number
of 1s may provide easier minimization so we use states with few 1s for the
unused states. The rest of the flip-flop outputs are assigned in order while
constructing the transition table.
|
SAFE |
PRESENT STATE (tn) |
NEXT STATE(tn+1) |
|
0 |
1 |
2 |
|
0 |
2 |
3 |
|
0 |
3 |
4 |
|
0 |
4 |
5 |
|
0 |
5 |
6 |
|
0 |
6 |
1 |
|
0 |
7 |
U |
|
0 |
8 |
U |
|
1 |
1 |
2 |
|
1 |
2 |
4 |
|
1 |
3 |
U |
|
1 |
4 |
5 |
|
1 |
5 |
1 |
|
1 |
6 |
U |
|
1 |
7 |
U |
|
1 |
8 |
U |
TABLE:
state transitions using state numbers
|
STATE |
Qi(tn) |
Qi(tn+1) |
|
0 |
000 (7) |
XXX |
|
0 |
001 (8) |
XXX |
|
0 |
010 (1) |
011 (2) |
|
0 |
011 (2) |
100 (3) |
|
0 |
100 (3) |
101 (4) |
|
0 |
101 (4) |
110 (5) |
|
0 |
110 (5) |
111 (6) |
|
0 |
111 (6) |
010 (1) |
|
1 |
000 (7) |
XXX |
|
1 |
001 (8) |
XXX |
|
1 |
010 (1) |
011 (2) |
|
1 |
011 (2) |
101 (4) |
|
1 |
100 (3) |
XXX |
|
1 |
101 (4) |
110 (5) |
|
1 |
110 (5) |
010 (1) |
|
1 |
111 (6) |
XXX |
TABLE:
assignment of flip flop outputs
The modified transition table is
shown below where SAFE is replaced by S, the flip flop outputs are rearranged
and Qi(tn+1) is replaced by Di.
|
S |
Q1 |
Q2 |
Q3 |
D1 |
D2 |
D3 |
|
0 |
0 |
0 |
0 |
X |
X |
X |
|
0 |
0 |
0 |
1 |
X |
X |
X |
|
0 |
0 |
1 |
1 |
1 |
0 |
0 |
|
0 |
0 |
1 |
0 |
0 |
1 |
1 |
|
0 |
1 |
0 |
0 |
1 |
0 |
1 |
|
0 |
1 |
0 |
1 |
1 |
1 |
0 |
|
0 |
1 |
1 |
1 |
0 |
1 |
0 |
|
0 |
1 |
1 |
0 |
1 |
1 |
1 |
|
1 |
1 |
0 |
0 |
X |
X |
X |
|
1 |
1 |
0 |
1 |
1 |
1 |
0 |
|
1 |
1 |
1 |
1 |
X |
X |
X |
|
1 |
1 |
1 |
0 |
0 |
1 |
0 |
|
1 |
0 |
0 |
0 |
X |
X |
X |
|
1 |
0 |
0 |
1 |
X |
X |
X |
|
1 |
0 |
1 |
1 |
1 |
0 |
1 |
|
1 |
0 |
1 |
0 |
0 |
1 |
1 |
DETERMINATION OF LOGICAL EXPRESSIONS USING K
MAP:
The next step is to determine the required logic expressions for the three flip-flop inputs D1, D2, and D3. We are using K maps to minimize. We have to construct nine combinational logic circuits. In addition to the three circuits for the flip-flop inputs, six simpler (only three-input) output control circuits must be built for the six traffic light signals R1 to G2. The K-Maps minimize each circuit individually; however, when multiple outputs are required, minimization can arise by reusing expressions. For example, if for one circuit the term S'•Q1•Q3' appears, which appears for another circuit as well, this part of the circuit has to be built only once and the signal used as many times as needed. For this reason, we will not try to factorize the expressions until we have all nine expressions. Also, we have to check whether the circuit works.
K MAP FOR D1
D1= Q2’ + S’Q1 Q3’ + Q1’ Q3
K MAP FOR D2
D2= Q1 Q3 + Q2 Q3’
K MAP FOR D3
D3=S Q1’ + S’ Q3’
CONSTRUCTION OF DIAGRAM INCLUDING DON’T CARES:
Now, we will replace don’t care
conditions with the actual outputs and will check if the circuit behaves
properly or not.
|
S |
Q1 |
Q2 |
Q3 |
D1 |
D2 |
D3 |
|
0 (7) |
0 |
0 |
0 |
1 |
0 |
1 (4) |
|
0 (8) |
0 |
0 |
1 |
1 |
0 |
0 (3) |
|
0 (2) |
0 |
1 |
1 |
1 |
0 |
0 (3) |
|
0 (1) |
0 |
1 |
0 |
0 |
1 |
1 (2) |
|
0 (3) |
1 |
0 |
0 |
1 |
0 |
1 (4) |
|
0 (4) |
1 |
0 |
1 |
1 |
1 |
0 (5) |
|
0 (6) |
1 |
1 |
1 |
0 |
1 |
0(1) |
|
0 (5) |
1 |
1 |
0 |
1 |
1 |
1 (6) |
|
1 (3) |
1 |
0 |
0 |
1 |
0 |
0 (3) |
|
1 (4) |
1 |
0 |
1 |
1 |
1 |
0 (5) |
|
1 (6) |
1 |
1 |
1 |
0 |
1 |
0 (1) |
|
1 (5) |
1 |
1 |
0 |
0 |
1 |
0 (1) |
|
1 (7) |
0 |
0 |
0 |
1 |
0 |
1 (4) |
|
1 (8) |
0 |
0 |
1 |
1 |
0 |
1 (4) |
|
1 (2) |
0 |
1 |
1 |
1 |
0 |
1 (4) |
|
1 (1) |
0 |
1 |
0 |
0 |
1 |
1 (2) |
If the SAFE input is logic 1
(safe crossing) and the system finds itself in state 3 then it will be stuck in
state 3. We cannot allow this, we have to go back and change some "don't
care" bit(s) since we chose one value for it but could have chosen
another. The state in trouble is State 3, flip-flop outputs 100 and K-map entry
1100. Looking at the K-maps, we can see that by changing the 0 indicated for
this term in the K-map for D3 to a 1 will cause minimal damage (i.e. will add
one extra term to the expression.
The changed table is shown below. If we check
in the transition table the entry for 1100 will change to 1101 and the system
will move to State 4 from State 3 regardless of the SAFE input. We have
repaired our system. All other illegal states ultimately end up in a proper
state so we have a working system.
|
S |
Q1 |
Q2 |
Q3 |
D1 |
D2 |
D3 |
|
(7) 0 |
0 |
0 |
0 |
1 |
0 |
1 (4) |
|
(8) 0 |
0 |
0 |
1 |
1 |
0 |
0 (3) |
|
(2) 0 |
0 |
1 |
1 |
1 |
0 |
0 (3) |
|
(1) 0 |
0 |
1 |
0 |
0 |
1 |
1 (2) |
|
(3) 0 |
1 |
0 |
0 |
1 |
0 |
1 (4) |
|
(4) 0 |
1 |
0 |
1 |
1 |
1 |
0 (5) |
|
(6) 0 |
1 |
1 |
1 |
0 |
1 |
0 (1) |
|
(5) 0 |
1 |
1 |
0 |
1 |
1 |
1 (6) |
|
(3) 1 |
1 |
0 |
0 |
1 |
0 |
1(4) |
|
(4) 1 |
1 |
0 |
1 |
1 |
1 |
0 (5) |
|
(6) 1 |
1 |
1 |
1 |
0 |
1 |
0 (1) |
|
(5) 1 |
1 |
1 |
0 |
0 |
1 |
0 (1) |
|
(7) 1 |
0 |
0 |
0 |
1 |
0 |
1 (4) |
|
(8) 1 |
0 |
0 |
1 |
1 |
0 |
1 (4) |
|
(2) 1 |
0 |
1 |
1 |
1 |
0 |
1 (4) |
|
(1) 1 |
0 |
1 |
0 |
0 |
1 |
1 (2) |
The modified K map for D3 will be
D3=Q2’Q3’ + SQ1’ + S’Q3’
CONSTRUCTION OF OUTPUT CIRCUITS:
There are six such circuits but
fortunately they have three inputs only (Moore Machine). Their K Maps can be
filled out by the requirements of lights to be either ON or OFF for each given
state. Here we will ignore the two
unused states which will provide "don't care" outputs to find the
minimized circuits.
|
STATE |
Q1 |
Q2 |
Q3 |
R1 |
A1 |
G1 |
R2 |
A2 |
G2 |
|
7 |
0 |
0 |
0 |
X |
X |
X |
X |
X |
X |
|
8 |
0 |
0 |
1 |
X |
X |
X |
X |
X |
X |
|
2 |
0 |
1 |
1 |
1 |
0 |
0 |
0 |
1 |
0 |
|
1 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
|
3 |
1 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
|
4 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
|
6 |
1 |
1 |
1 |
1 |
0 |
0 |
1 |
0 |
0 |
|
5 |
1 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
K MAPS FOR ALL THE OUTPUT:
R1=Q1’ + Q2’Q3’ + Q2Q3
SUMMARY AND CIRCUIT DIAGRAM:
D1 = Q2' + S'•Q1•Q3' + Q1'•Q3
D2 = Q1•Q3 + Q2•Q3'
D3 = Q2'•Q3' + S'•Q3' + S•Q1'
R1 = Q1' + Q2'•Q3' + Q2•Q3
A1 = Q1•Q2•Q3' or Q2•Q1•Q3' The common terms are underlined
G1 = Q2'•Q3
R2 = Q1
A2 = Q1'•Q3
G2 = Q1'•Q3'
A MORE SIMPLE DESIGN BY CHANGING THE STATE
ASSIGNMENTS:
We can design a simpler overall
circuit by trying different flip-flop assignments for the states. We could,
make R1=Q1 and R2=Q2, if these
simple assignments will give us a correct complete state assignment. The third
output, Q3 has to be assigned such that all used states are distinct. One
possible set of assignments are shown below:
|
STATE |
Q1 |
Q2 |
Q3 |
R1 |
A1 |
G1 |
R2 |
A2 |
G2 |
|
7 |
0 |
0 |
0 |
X |
X |
X |
X |
X |
X |
|
8 |
0 |
0 |
1 |
X |
X |
X |
X |
X |
X |
|
4 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
|
5 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
|
1 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
|
2 |
1 |
0 |
1 |
1 |
0 |
0 |
0 |
1 |
0 |
|
3 |
1 |
1 |
1 |
1 |
0 |
0 |
1 |
0 |
0 |
|
6 |
1 |
1 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
R1=Q1
K MAP FOR A1
A1=Q1’Q3’
K MAP FOR G1
G1=Q1’Q3
R2=Q2
K MAP FOR A2
A2=Q2’Q3
K MAP FOR G2
G2=Q2’Q3’
Now,
we have to design the input with the new flip flop assignments. The transition
table and K map for the inputs are shown below:
|
STATE |
S |
Q1 |
Q2 |
Q3 |
D1 |
D2 |
D3 |
STATE |
|
7 |
0 |
0 |
0 |
0 |
X |
X |
X |
|
|
8 |
0 |
0 |
0 |
1 |
X |
X |
X |
|
|
4 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
5 |
|
5 |
0 |
0 |
1 |
0 |
1 |
1 |
0 |
6 |
|
1 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
2 |
|
2 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
3 |
|
3 |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
4 |
|
6 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
1 |
|
1 |
1 |
1 |
0 |
0 |
1 |
0 |
1 |
2 |
|
2 |
1 |
1 |
0 |
1 |
0 |
1 |
1 |
4 |
|
3 |
1 |
1 |
1 |
1 |
X |
X |
X |
|
|
6 |
1 |
1 |
1 |
0 |
X |
X |
X |
|
|
7 |
1 |
0 |
0 |
0 |
X |
X |
X |
|
|
8 |
1 |
0 |
0 |
1 |
X |
X |
X |
|
|
4 |
1 |
0 |
1 |
1 |
0 |
1 |
0 |
5 |
|
5 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
D1=S'•Q2' + Q3'
K MAP FOR D2
The state diagram is shown below:
SUMMARY AND CIRCUIT DIAGRAM:
D1 = S'•Q2' + Q3'
D2 = S'•Q1' + Q3
D3 = Q2' + Q1•Q3
R1 = Q1
A1 = Q1'•Q3'
G1 = Q1'•Q3
R2 = Q2
A2 = Q2'•Q3
G2 = Q2'•Q3'
0 Comments