GATE 2018 EC Q.19: solution and answer

GATE 2018 · ECQ.19 · 1 mark · NAT

A traffic signal cycles from GREEN to YELLOW, YELLOW to RED and RED to GREEN. In each cycle, GREEN is turned on for 70 seconds, YELLOW is turned on for 5 seconds and the RED is turned on for 75 seconds. This traffic light has to be implemented using a finite state machine (FSM). The only input to this FSM is a clock of 5 second period. The minimum number of flip-flops required to implement this FSM is ________.

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

The FSM needs 30 states (150 s / 5 s), so the minimum number of flip-flops is $⌈ lo g_{2} 30 ⌉ = 5$ .

Official answer: 5Source: Official answer key, GATE 2018 EC (IIT Guwahati)

The FSM's only input is a clock with a 5 s period, so the only way it can keep time is by counting clock edges. It can change state only on a clock edge. All three durations (70 s, 5 s, 75 s) are multiples of 5 s, so every light change falls on a clock edge.
Length of one full cycle: $T = 70 + 5 + 75 = 150 s$ .
Clock periods in one cycle: $N = \frac{150 s}{5 s} = 30$ . GREEN lasts $70/5 = 14$ periods, YELLOW $5/5 = 1$ period and RED $75/5 = 15$ periods.
Why the machine needs at least 30 states: with no input other than the clock, the next state depends only on the present state. After at most $k$ clock periods (for a $k$ -state machine) some state repeats, and from then on the sequence of states repeats. The light pattern (14 GREEN, 1 YELLOW, 15 RED) repeats only every 30 periods and never sooner, so the repeating loop of states must be at least 30 states long. Two states in the same colour cannot be merged, because the machine has to know how many 5 s periods have passed to switch after the 14th GREEN or the 15th RED period.
$n$ flip-flops give at most $2^{n}$ distinct states, so we need the smallest $n$ with $2^{n} \geq 30$ : $2^{4} = 16 < 30 \leq 32 = 2^{5} \Rightarrow n = ⌈ lo g_{2} 30 ⌉ = 5$
Five flip-flops are enough: build a mod-30 counter (30 of the 32 codes used) and decode the light outputs from the count (GREEN for counts 0 to 13, YELLOW for 14, RED for 15 to 29). So the minimum number of flip-flops is 5.

KEY IDEA

With only a clock as input, the FSM can keep time only by counting clock periods. Its state loop must be as long as the full light cycle measured in clock periods: $150/5 = 30$ states. $n$ flip-flops give $2^{n}$ states, so $n = ⌈ lo g_{2} 30 ⌉ = 5$ .

WATCH OUT FOR

Counting only the three colours as three states, which gives 2 flip-flops. That machine cannot hold GREEN for 14 clock periods and RED for 15, because it has no input telling it when to move on. A second mistake is to size for the longest phase alone (15 states, 4 flip-flops) and forget that the count must cover the whole 150 s cycle.

From the GATE 2018 EC paper. Every question of this paper · Download the full paper · All 30 Sequential questions, with notes

GATE 2018 EC Q.19: solution and answer

Answer and solution

More Sequential questions