Three codes for four states

An encoding assigns a bit pattern to each state. Binary packs states into few bits, one-hot spends one bit per state, and gray orders binary codes so neighbours differ by one bit.

Down the chain S0 to S1 to S2 to S3, the gray column flips exactly one bit per step. That single-bit property is the whole point of gray.

What each code costs

Binary uses the fewest flops but each transition test decodes the full code. One-hot tests a single bit per transition, which shortens next-state paths at the price of more flops.

Gray keeps the binary flop count and cuts switching on machines that walk neighbour to neighbour, such as counters. No encoding always wins: the machine shape, the library and the timing target decide.

course.lib teaching-library areas (library units, not a process): DFF = 8
binary state flops:   2 flops x 8 = 16 area units
one-hot state flops:  4 flops x 8 = 32 area units
the flop part is exact; next-state gates and the clock tree vary with the machine, so totals still need the mapped netlist

Counting next-state literals

A simple structural estimate counts, per transition arc, the state bits the arc must test plus its guard literals. Binary tests two bits per arc here; one-hot tests one.

The stated example machine has states S0 to S3 and arcs: S0 to S1 on go, S0 to S0 on not go, S1 to S2 always, S2 to S3 always, S3 to S0 on go, S3 to S3 on not go. The program below recomputes both totals from that arc list.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

import sys

# Stated example machine: arcs of (source, guard literals, dest).
# An empty guard means an unconditional arc (0 guard literals).
TRANSITIONS = [
    ("S0", ("go",), "S1"),
    ("S0", ("~go",), "S0"),
    ("S1", (), "S2"),
    ("S2", (), "S3"),
    ("S3", ("go",), "S0"),
    ("S3", ("~go",), "S3"),
]

FLOPS = {"binary": 2, "one-hot": 4}
DECODE = {"binary": 2, "one-hot": 1}

def totals(encoding):
    flops = FLOPS[encoding]
    decode = DECODE[encoding]
    lits = 0
    for i in range(len(TRANSITIONS)):
        src, guard, dst = TRANSITIONS[i]
        lits = lits + decode + len(guard)
    return flops, lits

bin_flops, bin_lits = totals("binary")
oh_flops, oh_lits = totals("one-hot")

checks = [
    (bin_flops, 2),
    (oh_flops, 4),
    (bin_lits, 16),
    (oh_lits, 10),
]

for i in range(len(checks)):
    got, want = checks[i]
    if got != want:
        print("FAIL: check " + str(i + 1) + " got " + str(got) + " want " + str(want))
        sys.exit(1)

print("PASS: binary 2 flops 16 literals, one-hot 4 flops 10 literals")

Hand check: binary arcs cost 3, 3, 2, 2, 3, 3 literals, which sum to 16. One-hot arcs cost 2, 2, 1, 1, 2, 2, which sum to 10.

Power follows activity

Clock pins toggle every cycle, so each extra state flop adds clock-pin power. Data pins add further power only when they switch.

EXAMPLE parameters (illustrative, not a process): C 5 fF per clock pin, V 0.8 V, f 500 MHz, activity 1
P = alpha x C x V^2 x f = 1 x 5e-15 F x 0.64 V^2 x 5e8 Hz
  = 5 x 0.64 x 5 e(-15 + 8) W = 16e-7 W = 1.6e-6 W = 1.6 uW per clock pin
binary:   2 pins x 1.6 uW = 3.2 uW of clock-pin power
one-hot:  4 pins x 1.6 uW = 6.4 uW of clock-pin power
clock-pin part only; data switching adds on top and can favour either side

Related topics

• Up: FSM Synthesis

• Next: Unreachable states

• Area, Power and Timing Trade-offs