Three ways to number five states

An encoding assigns one bit pattern to each state, and the receiver needs five. Binary packs the states into three bits in counting order. One-hot spends one flop per state, with exactly one asserted at a time. Gray keeps the three-bit width but orders the codes so neighbours on the packet walk differ in a single bit, as the table shows.

The script below runs the same receiver three times, changing only the code assignment. The one-hot run recodes with fsm_recode -encoding one-hot and the binary run with -encoding binary: the two recodings this build's flag applies to a real machine (check with yosys -h fsm_recode), so the gray run keeps hand-written gray codes and maps without a recode step. Anything left to the auto default is mapped per machine instead — one-hot here, the written codes kept where recoding buys nothing — and each run asserts the flop count its encoding implies alongside its ABC report, liberty stat report, and mapped netlist.

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94

read_verilog <<EOV
module pkt_rx (input wire clk, input wire rst, input wire start, input wire byte_valid, input wire last_byte, input wire crc_ok,
  output reg ready, output reg accept, output reg err);
  localparam [2:0] IDLE = 3'd0, HDR = 3'd1, PAYLOAD = 3'd2, CRC = 3'd3, DONE = 3'd4;
  reg [2:0] state, next;
  always @(posedge clk) if (rst) state <= IDLE; else state <= next;
  always @(*) begin
    next = state; ready = 1'b0; accept = 1'b0; err = 1'b0;
    case (state)
      IDLE: begin ready = 1'b1; if (start) next = HDR; end
      HDR: begin if (byte_valid) next = PAYLOAD; end
      PAYLOAD: begin if (byte_valid && last_byte) next = CRC; end
      CRC: begin if (crc_ok) next = DONE; else begin next = IDLE; err = !crc_ok; end end
      DONE: begin accept = 1'b1; next = IDLE; end
      default: next = IDLE;
    endcase
  end
endmodule
module pkt_gray (input wire clk, input wire rst, input wire start, input wire byte_valid, input wire last_byte, input wire crc_ok,
  output reg ready, output reg accept, output reg err);
  localparam [2:0] IDLE = 3'b000, HDR = 3'b001, PAYLOAD = 3'b011, CRC = 3'b010, DONE = 3'b110;
  reg [2:0] state, next;
  always @(posedge clk) if (rst) state <= IDLE; else state <= next;
  always @(*) begin
    next = state; ready = 1'b0; accept = 1'b0; err = 1'b0;
    case (state)
      IDLE: begin ready = 1'b1; if (start) next = HDR; end
      HDR: begin if (byte_valid) next = PAYLOAD; end
      PAYLOAD: begin if (byte_valid && last_byte) next = CRC; end
      CRC: begin if (crc_ok) next = DONE; else begin next = IDLE; err = !crc_ok; end end
      DONE: begin accept = 1'b1; next = IDLE; end
      default: next = IDLE;
    endcase
  end
endmodule
EOV
design -save rtl
design -load rtl
hierarchy -top pkt_rx
proc
opt_clean
fsm_detect
fsm_extract
fsm_opt
opt_clean
fsm_opt
select -assert-count 1 t:$fsm
fsm_recode -encoding one-hot
fsm_map
techmap
opt_clean
dfflibmap -liberty course.lib
tee -o abc_oh.txt abc -liberty course.lib -constr typical.constr -D 1000
tee -o stat_oh.txt stat -liberty course.lib
write_json net_oh.json
select -assert-count 5 t:DFF
design -load rtl
hierarchy -top pkt_rx
proc
opt_clean
fsm_detect
fsm_extract
fsm_opt
opt_clean
fsm_opt
select -assert-count 1 t:$fsm
fsm_recode -encoding binary
fsm_map
techmap
opt_clean
dfflibmap -liberty course.lib
tee -o abc_bin.txt abc -liberty course.lib -constr typical.constr -D 1000
tee -o stat_bin.txt stat -liberty course.lib
write_json net_bin.json
select -assert-count 3 t:DFF
design -load rtl
hierarchy -top pkt_gray
proc
opt_clean
fsm_detect
fsm_extract
fsm_opt
opt_clean
fsm_opt
select -assert-count 1 t:$fsm
fsm_map
techmap
opt_clean
dfflibmap -liberty course.lib
tee -o abc_gray.txt abc -liberty course.lib -constr typical.constr -D 1000
tee -o stat_gray.txt stat -liberty course.lib
write_json net_gray.json
select -assert-count 3 t:DFF
log PASS: one-hot binary and gray receivers map with five three and three flops

What the three runs printed

Read the delay column first: one-hot answers in 291.61 ps because every transition test watches a single state bit, while binary must decode up to three bits and lands at 506.03 ps. Now read the chip column the other way: the one-hot register needs two more flops than either three-bit code, and the one-hot chip against 66 for binary shows the machine paying for its speed in flops. Gray is the compromise the table promises: three flops like binary, a delay of 426.46 ps between the other two, and the smallest switching total of the three, for a chip between the other two — because its neighbour-to-neighbour hops keep both the decode and the switching small.

The recorded one-hot netlist below shows where the area goes: five blue state flops on the left, one per state, feeding the next-state and output decode. Compare it with the three-flop binary netlist in the Yosys FSM passes lesson and the cost is visible before any number is read.

Counting the bit flips

Delay is only half the trade; the other half is how many state bits move on each hop. A hop that flips two bits charges two flop inputs and briefly presents a wrong code to every decoder watching the register. The program below adds up the Hamming distance over the six arcs that leave a state, checks each total against a hand count, and fails loudly on any mismatch.

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

import sys

# Packet-receiver arcs that leave a state: (source, dest).
ARCS = [("IDLE", "HDR"), ("HDR", "PAYLOAD"), ("PAYLOAD", "CRC"),
        ("CRC", "DONE"), ("CRC", "IDLE"), ("DONE", "IDLE")]

BIN = {"IDLE": 0b000, "HDR": 0b001, "PAYLOAD": 0b010, "CRC": 0b011, "DONE": 0b100}
OH = {"IDLE": 0b00001, "HDR": 0b00010, "PAYLOAD": 0b00100, "CRC": 0b01000, "DONE": 0b10000}
GRAY = {"IDLE": 0b000, "HDR": 0b001, "PAYLOAD": 0b011, "CRC": 0b010, "DONE": 0b110}

def ham(a, b):
    return bin(a ^ b).count("1")

def total(code):
    return sum(ham(code[s], code[d]) for s, d in ARCS)

bin_total, oh_total, gray_total = total(BIN), total(OH), total(GRAY)

checks = [(bin_total, 10), (oh_total, 12), (gray_total, 7)]
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)

# One-hot flips exactly two bits on every hop between distinct states.
for s, d in ARCS:
    if ham(OH[s], OH[d]) != 2:
        print("FAIL: one-hot hop " + s + " to " + d + " flips not 2")
        sys.exit(1)

print("PASS: hamming totals binary 10 one-hot 12 gray 7 over six arcs")

The asserted totals are 10 for binary, 12 for one-hot and 7 for gray, and the one-hot figure deserves a second look because it surprises most readers. Every one-hot hop flips exactly two bits, one flop turning off and the next turning on, so its six arcs cost twelve flips, the most of the three. Binary flips vary from one to three bits per hop and totals ten. Gray flips one bit on every forward hop and pays two only on the DONE to IDLE return, totalling seven. One-hot wins the decode depth at one bit tested per transition and loses the switching count at two bits flipped per hop; gray wins the switching and keeps the flop count, but only on machines that mostly walk between neighbours.

Power follows the clock pins

Clock power is the part of the bill no encoding can dodge, because every state flop has a clock pin that toggles each cycle whether the state moves or not. The one-hot register drives five clock pins against three for either three-bit code, and the arithmetic below turns that pin count into watts with illustrative parameters, labelled so; the data switching on top follows the flip totals of the previous section.

EXAMPLE parameters (illustrative, not a process): C 5 fF per clock pin, V 0.8 V, f 500 MHz, activity 1
P = activity 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.6 uW per clock pin
binary and gray:   3 pins x 1.6 uW = 4.8 uW of clock-pin power
one-hot:           5 pins x 1.6 uW = 8.0 uW of clock-pin power
clock-pin part only; data-pin switching follows the 10 / 12 / 7 flip totals above

Break it: let the stock flow choose

All three runs above chose their encoding explicitly. The script below chooses nothing: it runs the binary-written receiver through the stock synthesis flow, which performs its own detection, extraction and recoding with default settings, then maps and reports. If the default were to keep the written codes, the run would land on three flops and the binary chip area.

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

read_verilog <<EOV
module pkt_rx (input wire clk, input wire rst, input wire start, input wire byte_valid, input wire last_byte, input wire crc_ok,
  output reg ready, output reg accept, output reg err);
  localparam [2:0] IDLE = 3'd0, HDR = 3'd1, PAYLOAD = 3'd2, CRC = 3'd3, DONE = 3'd4;
  reg [2:0] state, next;
  always @(posedge clk) if (rst) state <= IDLE; else state <= next;
  always @(*) begin
    next = state; ready = 1'b0; accept = 1'b0; err = 1'b0;
    case (state)
      IDLE: begin ready = 1'b1; if (start) next = HDR; end
      HDR: begin if (byte_valid) next = PAYLOAD; end
      PAYLOAD: begin if (byte_valid && last_byte) next = CRC; end
      CRC: begin if (crc_ok) next = DONE; else begin next = IDLE; err = !crc_ok; end end
      DONE: begin accept = 1'b1; next = IDLE; end
      default: next = IDLE;
    endcase
  end
endmodule
EOV
hierarchy -top pkt_rx
synth -top pkt_rx
dfflibmap -liberty course.lib
tee -o abc_stock.txt abc -liberty course.lib -constr typical.constr -D 1000
tee -o stat_stock.txt stat -liberty course.lib
select -assert-count 5 t:DFF
log PASS: stock flow recodes the receiver to five state flops

The recorded stock run lands on 5 state flops with chip area 79, within two units of the explicit one-hot chip. The tool recoded the machine on its own, to the one-hot shape: Yosys recodes to one-hot by default, without looking at any delay target or flop budget. That is the honest meaning of an encoding default: not keeping your codes, but applying the tool's own choice. Pin the encoding you evaluated whenever the choice matters, and assert the flop count so a tool update cannot silently change it.

Related topics

• Up: FSM Synthesis

• Next: Unreachable states

• Area, Power and Timing Trade-offs