What you will build
A traffic light controller for a crossing of a main road and a side road. The main road stays green until a car waits on the side road. It is a finite state machine, built from two D flip-flops, a 3-bit counter used as a timer, and gates. Plan about 2 hours. You should know D flip-flops, the Counter and Combinational Analysis.
All files are saved in the 5.0.0 format. There is no classic 2.7.1 version because the sequential test vectors need Evolution (test vectors).
The method in six steps
- List the states and what each one outputs.
- Draw the state diagram.
- Give every state a binary code.
- Write the state table.
- Derive the next-state and output equations.
- Build the circuit and test it.
States and the state diagram
| State | Code S1 S0 | Main road | Side road | Minimum time | Leaves when |
|---|---|---|---|---|---|
| S0 | 00 | green | red | 5 clock cycles | timer at least 4 and car = 1 |
| S1 | 01 | yellow | red | 2 clock cycles | timer at least 1 |
| S2 | 10 | red | green | 5 clock cycles | timer at least 4 |
| S3 | 11 | red | yellow | 2 clock cycles | timer at least 1 |
The main road stays green as long as no car waits on the side road.
The timer
Each state lasts a minimum time. A 3-bit Counter counts the clock cycles since the state changed. We need two facts from it: T2 means the timer is at least 1 (the OR of its three bits) and T5 means the timer is at least 4 (bit 2).
Configure the Counter with Data Bits 3, Maximum Value 7 and Action On Overflow set to Stay at value. The timer then stops at 7 instead of wrapping, so a long wait in S0 never loses the at-least-4 condition. The timer must restart at 0 whenever the state changes. Use the Counter’s Load input with a data input of 0: loading is synchronous, so it happens on the clock edge together with the state change.
Describe this circuit
Components: Input pin CLK; Input pin LOAD; Counter timer; Constant 1; Constant 2; Output pin Q.
- Input pin CLK connects to Counter timer (net CLK, clk).
- Input pin LOAD connects to Counter timer (net LOAD, change).
- Counter timer connects to Constant 1, 3 bits wide.
- Counter timer connects to Constant 2.
Download circ-traffic-light-timer.circ and its vector. The circuits are saved by 5.0.0 and need 4.1.0 or newer for the vector commands.
State table and equations
For every combination of the current state (S1 S0), the car sensor and the timer flags, the table gives the next state (D1 D0). Rows with T5 = 1 and T2 = 0 cannot happen because the timer cannot be at least 4 without being at least 1; they are in the table for completeness.
| # | S1 | S0 | car | T2 | T5 | D1 | D0 |
|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | |
| 0 | 0 | 0 | 0 | 1 | 0 | 0 | |
| 0 | 0 | 0 | 1 | 0 | 0 | 0 | |
| 0 | 0 | 0 | 1 | 1 | 0 | 0 | |
| 0 | 0 | 1 | 0 | 0 | 0 | 0 | |
| 0 | 0 | 1 | 0 | 1 | 0 | 1 | |
| 0 | 0 | 1 | 1 | 0 | 0 | 0 | |
| 0 | 0 | 1 | 1 | 1 | 0 | 1 | |
| 0 | 1 | 0 | 0 | 0 | 0 | 1 | |
| 0 | 1 | 0 | 0 | 1 | 0 | 1 | |
| 0 | 1 | 0 | 1 | 0 | 1 | 0 | |
| 0 | 1 | 0 | 1 | 1 | 1 | 0 | |
| 0 | 1 | 1 | 0 | 0 | 0 | 1 | |
| 0 | 1 | 1 | 0 | 1 | 0 | 1 | |
| 0 | 1 | 1 | 1 | 0 | 1 | 0 | |
| 0 | 1 | 1 | 1 | 1 | 1 | 0 | |
| 1 | 0 | 0 | 0 | 0 | 1 | 0 | |
| 1 | 0 | 0 | 0 | 1 | 1 | 1 | |
| 1 | 0 | 0 | 1 | 0 | 1 | 0 | |
| 1 | 0 | 0 | 1 | 1 | 1 | 1 | |
| 1 | 0 | 1 | 0 | 0 | 1 | 0 | |
| 1 | 0 | 1 | 0 | 1 | 1 | 1 | |
| 1 | 0 | 1 | 1 | 0 | 1 | 0 | |
| 1 | 0 | 1 | 1 | 1 | 1 | 1 | |
| 1 | 1 | 0 | 0 | 0 | 1 | 1 | |
| 1 | 1 | 0 | 0 | 1 | 1 | 1 | |
| 1 | 1 | 0 | 1 | 0 | 0 | 0 | |
| 1 | 1 | 0 | 1 | 1 | 0 | 0 | |
| 1 | 1 | 1 | 0 | 0 | 1 | 1 | |
| 1 | 1 | 1 | 0 | 1 | 1 | 1 | |
| 1 | 1 | 1 | 1 | 0 | 0 | 0 | |
| 1 | 1 | 1 | 1 | 1 | 0 | 0 |
Reading the table and simplifying gives:
- D1 = S1 XOR (S0 AND T2)
- D0 = (S0 AND NOT T2) OR (NOT S0 AND T5 AND (S1 OR car))
Entering the table in Combinational Analysis gives an equivalent but possibly different sum of products. It does not know that T5 implies T2, so it cannot use the impossible rows as don’t-cares.
The outputs depend only on the state (Moore): ns_g = NOT S1 AND NOT S0, ns_y = NOT S1 AND S0, ns_r = S1, ew_g = S1 AND NOT S0, ew_y = S1 AND S0, ew_r = NOT S1.
The timer restart signal, change, is true when the next state differs from the current one: S0 AND T2, or D0 XOR S0.
Build the controller
The controller is one circuit with the inputs reset, car and clk and the outputs state (2 bits) and the six lights. The clock is an input pin, not a Clock component, so a test vector can drive it. The state register is two D flip-flops whose Clear inputs are tied to reset, so the machine starts in S0. The timer’s Clear is also tied to reset.
Describe this circuit
Components: Input pin reset; Input pin car; Input pin clk; D Flip-Flop S1; D Flip-Flop S0; Counter timer; Constant 1; Splitter 1; OR Gate 1; Buffer 1; AND Gate 1; XOR Gate 1; NOT Gate 1; AND Gate 2; NOT Gate 2; OR Gate 2; AND Gate 3; OR Gate 3; XOR Gate 2; OR Gate 4; NOT Gate 3; AND Gate 4; AND Gate 5; AND Gate 6; AND Gate 7; Splitter 2; Output pin state; Output pin ns_r; Output pin ns_y; Output pin ns_g; Output pin ew_r; Output pin ew_y; Output pin ew_g.
- Input pin reset connects to D Flip-Flop S1, D Flip-Flop S0, Counter timer (net reset).
- Input pin car connects to OR Gate 2 (net car).
- Input pin clk connects to D Flip-Flop S1, D Flip-Flop S0, Counter timer (net clk).
- D Flip-Flop S1 connects to XOR Gate 1 (net d1).
- D Flip-Flop S1 connects to XOR Gate 1, OR Gate 2, NOT Gate 3, AND Gate 6, AND Gate 7, Splitter 2, Output pin ns_r (net s1, ns_r).
- D Flip-Flop S0 connects to OR Gate 3, XOR Gate 2 (net d0).
- D Flip-Flop S0 connects to AND Gate 1, AND Gate 2, NOT Gate 2, XOR Gate 2, AND Gate 5, AND Gate 7, Splitter 2 (net s0).
- Counter timer connects to Constant 1, 3 bits wide.
- Counter timer connects to OR Gate 4 (net change).
- Splitter 1 connects to OR Gate 1 (net t0).
- Splitter 1 connects to OR Gate 1 (net t1).
- Splitter 1 connects to OR Gate 1, Buffer 1 (net t2b).
- OR Gate 1 connects to AND Gate 1, NOT Gate 1 (net T2).
- Buffer 1 connects to AND Gate 3 (net T5).
- AND Gate 1 connects to XOR Gate 1, OR Gate 4 (net s0t2).
- NOT Gate 1 connects to AND Gate 2 (net nt2).
- AND Gate 2 connects to OR Gate 3 (net a0).
- NOT Gate 2 connects to AND Gate 3, AND Gate 4, AND Gate 6 (net ns0).
- OR Gate 2 connects to AND Gate 3 (net s1orcar).
- AND Gate 3 connects to OR Gate 3 (net b0).
- XOR Gate 2 connects to OR Gate 4 (net ch0).
- NOT Gate 3 connects to AND Gate 4, AND Gate 5, Output pin ew_r (net ns1, ew_r).
- AND Gate 4 connects to Output pin ns_g (net ns_g).
- AND Gate 5 connects to Output pin ns_y (net ns_y).
- AND Gate 6 connects to Output pin ew_g (net ew_g).
- AND Gate 7 connects to Output pin ew_y (net ew_y).
- Splitter 2 connects to Output pin state (net state), 2 bits wide.
Test it with a sequential test vector
The vector has two sets. Set 1 resets, runs 8 cycles with no car (the state must stay S0 and the timer saturates), sends a car for one cycle, then follows the whole cycle: S1 for 2 cycles, S2 for 5, S3 for 2, back to S0, and 6 more cycles in S0. Set 2 holds car at 1 from reset and checks that S0 lasts exactly 5 cycles. Every row checks the state and all six lights after each clock edge.
Show values as a table
| cycle | car | state | main red | main yellow | main green | side red | side yellow | side green |
|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 0 |
| 1 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 0 |
| 2 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 0 |
| 3 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 0 |
| 4 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 0 |
| 5 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 0 |
| 6 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 0 |
| 7 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 0 |
| 8 | 1 | 1 | 0 | 1 | 0 | 1 | 0 | 0 |
| 9 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 0 |
| 10 | 0 | 2 | 1 | 0 | 0 | 0 | 0 | 1 |
| 11 | 0 | 2 | 1 | 0 | 0 | 0 | 0 | 1 |
| 12 | 0 | 2 | 1 | 0 | 0 | 0 | 0 | 1 |
| 13 | 0 | 2 | 1 | 0 | 0 | 0 | 0 | 1 |
| 14 | 0 | 2 | 1 | 0 | 0 | 0 | 0 | 1 |
| 15 | 0 | 3 | 1 | 0 | 0 | 0 | 1 | 0 |
| 16 | 0 | 3 | 1 | 0 | 0 | 0 | 1 | 0 |
| 17 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 0 |
| 18 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 0 |
| 19 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 0 |
| 20 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 0 |
| 21 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 0 |
| 22 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 0 |
| 23 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 0 |
Download circ-traffic-light-fsm.circ and its vector. See test vectors for the file format and the set and seq columns.
The broken version
circ-traffic-light-broken-async-clear.circ is the same controller with the timer cleared through Clear. With the same vector it fails: 43 rows pass and 34 fail. The first failure is the first clock edge after the car arrives: the state stays at 00 where 01 is expected, and the lights stay with the main road green.
The intersection panel
The controller becomes a subcircuit named traffic_fsm. The main circuit holds one instance of it, a Clock on the clk input, a reset pin, a car pin and six LEDs that show the lamps. A 4-bit Counter on the same clock raises a halt pin after 16 ticks, so a headless run ends by itself. Each LED also drives an output pin, which lets a test read the lamps.
Describe this circuit
Components: traffic_fsm ctrl; Input pin reset; Input pin car; Clock 1; LED NS_red; Output pin ns_r; LED NS_yellow; Output pin ns_y; LED NS_green; Output pin ns_g; LED EW_red; Output pin ew_r; LED EW_yellow; Output pin ew_y; LED EW_green; Output pin ew_g; Counter ticks; Constant 1; Output pin halt.
- Clock 1 connects to Counter ticks.
- LED NS_red connects to Output pin ns_r (net ns_r).
- LED NS_yellow connects to Output pin ns_y (net ns_y).
- LED NS_green connects to Output pin ns_g (net ns_g).
- LED EW_red connects to Output pin ew_r (net ew_r).
- LED EW_yellow connects to Output pin ew_y (net ew_y).
- LED EW_green connects to Output pin ew_g (net ew_g).
- Counter ticks connects to Constant 1, 4 bits wide.
- Counter ticks connects to Output pin halt (net halt).
Open the file, choose Simulate, then Ticks Enabled (Ctrl+K), and click the car pin to set it to 1.
The traffic light panel circuit: a Clock, reset and car input pins, the traffic_fsm controller as a small box, six LEDs on the right and the matching output pins. NS green and EW red are lit.
The traffic light panel circuit with the NS red lamp and the EW green lamp lit, the car pin set to 1.
Download circ-traffic-light-panel.circ (car is a pin) and circ-traffic-light-panel-car.circ (car fixed at 1, with its expected rows).
Not tested
We ran the panel at the default tick frequency only. We did not try other tick frequencies, did not record a run, and did not test a second car arriving while the lights are yellow or on the side road. We therefore give no recommended tick frequency beyond the default.
Apply the method to your own FSM
A vending machine: the states are the money inserted so far, the inputs are the coin types, and the outputs are dispense and change. An elevator: the states are the floors and the door. Write the state list, then follow the six steps. One-hot encoding, with one flip-flop per state, gives simpler next-state logic at the cost of more flip-flops. Logisim-evolution has no FSM editor; the simulator Digital has one.
Common mistakes
- Asynchronous clear on the timer. See the danger box above.
- Gating the clock to pause the lights. Use enable inputs instead.
- Outputs built from inputs. The lights flicker when the sensor changes: you built a Mealy machine by accident.
- An unhandled state code. A design with three states leaves code 11 unreachable but undefined; define every code.
- A test vector without set and seq. Each row then starts a fresh circuit (test vectors).
- Building the state register from gates without a clock. Logisim then reports an oscillation (Oscillation apparent).
Downloads
Circuits: panel, panel with car fixed, timer, controller, broken twin. Vectors: timer, controller. All need Logisim-evolution 4.1.0 or newer for the vectors and 5.0.0 for the files. See all projects.