1. Home
2. Academy
3. State Machines from Zero
4. Volume 05

5.1 Binary and Gray encoding

Binary encoding numbers the states and uses the fewest flip-flops. Gray encoding orders the codes so that each usual step changes only one bit.

One machine for the whole volume

To compare encodings fairly, we will encode the same machine every time. It is a simple washing machine with five states:

Each arrow is labelled with the input that must be 1 to take it. The label "else" on a loop means "when that input is 0, stay". The machine has three outputs:

• valve lets water in. It is on in FILL.
• motor turns the drum. It is on in WASH and in SPIN.
• pump pumps water out. It is on in DRAIN and in SPIN.

Binary encoding

The simplest choice is to number the states in order - 0, 1, 2, 3, 4 - and write each number in binary. This is binary encoding. Five states need three flip-flops, because 2³ = 8 is the first power of two that is at least 5.

Now count how many bits change on each step around the machine. The number of bit positions in which two codes differ is called their Hamming distance:

Why the number of changing bits matters

On the step from DRAIN to SPIN, all three flip-flops change at once. In theory they change at the same instant. In a real chip, one is always a little faster than another. For a split second the state register may hold 111, or 000, or 101 - codes that are not the state you want. Anything decoded from those bits can glitch for that moment. Also, every bit that flips uses a little energy. More flips mean more power.

Gray encoding

Gray encoding chooses the codes so that each usual step changes only one bit - the same idea as the Gray-code order of a K-map in Volume 03:

Four of the five steps now change a single bit. The step from SPIN back to IDLE still changes two. That is not bad luck, as the box below explains.

5.2 One-hot and one-cold

One-hot encoding uses one flip-flop per state, with exactly one of them at 1. The state is simply "whichever flip-flop is hot".

One flip-flop per state

In one-hot encoding, every state gets its own flip-flop. At any moment, exactly one flip-flop holds 1 - it is "hot" - and all the others hold 0. You met this code already: the Medvedev traffic light in Volume 02 was one-hot.

Five states now need five flip-flops instead of three. What do we get for the extra two?

Decoding is free

To ask "is the machine in WASH?" with binary codes, you need a gate that checks all three bits: Q2'·Q1·Q0'. With one-hot, you just read the WASH flip-flop. No gates at all. The outputs become very simple:

• valve = FILL
• motor = WASH + SPIN
• pump = DRAIN + SPIN

Next-state logic you can read off the diagram

One-hot next-state logic follows one rule, and needs no K-maps:

Apply the rule to the washing machine:

Here, each flip-flop's logic looks at only two state bits and one input. In any one-hot machine, a flip-flop's logic grows only with the number of arrows into its own state - not with the size of the whole machine. In Verilog, you can write it exactly like that:

// one flip-flop per state: s[0]=IDLE s[1]=FILL s[2]=WASH s[3]=DRAIN s[4]=SPIN
reg [4:0] s;
always @(posedge clk)
  if (rst) s <= 5'b00001;                      // start with IDLE hot
  else begin
    s[0] <= (s[0] & ~start) | (s[4] &  done);  // IDLE
    s[1] <= (s[0] &  start) | (s[1] & ~full);  // FILL
    s[2] <= (s[1] &  full ) | (s[2] & ~done);  // WASH
    s[3] <= (s[2] &  done ) | (s[3] & ~empty); // DRAIN
    s[4] <= (s[3] &  empty) | (s[4] & ~done);  // SPIN
  end
assign valve = s[1];
assign motor = s[2] | s[4];
assign pump  = s[3] | s[4];

You will rarely write one-hot by hand like this - sub-module 5.5 shows that the tool can do it for you. But writing it once makes clear why one-hot logic is so small.

The price: many illegal codes

Five flip-flops can hold 2⁵ = 32 codes. Only 5 of them are real states. The other 27 are illegal states - for example 00110, where WASH and FILL are both hot, and the machine seems to be in two states at once. A correct one-hot machine never reaches them, but a glitch or a radiation hit could put it there. Volume 11 deals with that.

One-cold

One-cold encoding is the mirror image: one flip-flop per state, with exactly one of them at 0. It is rare, but it can suit outputs that are active low. Everything said about one-hot applies to it, turned upside down.

5.3 Johnson and custom encodings

A Johnson code moves through its states by shifting in the opposite of its last bit. An output-coded machine chooses its codes so that the outputs are the state bits themselves.

The Johnson code

Take three flip-flops in a row. On every step, shift the bits one place to the left, and feed the opposite of the leftmost bit into the right-hand end. Starting from 000:

This is a Johnson code. Three flip-flops give six states, and every step changes exactly one bit - including the step from the last state back to the first. In general, n flip-flops give 2n states. That is fewer than binary gives (2ⁿ), but more than one-hot gives (n).

A Johnson code has one more gift: any state can be recognised from just two neighbouring bits. For example, 011 is the only code whose left bit is 0 and whose middle bit is 1. So each state needs only one 2-input gate to decode, however many flip-flops there are. Johnson counters come back in Volume 07.

For the five-state washing machine, a 3-bit Johnson code gives IDLE = 000, FILL = 001, WASH = 011, DRAIN = 111, SPIN = 110. The step from SPIN back to IDLE skips the sixth code, 100, and so changes two bits.

Output encoding: make the outputs the state

Now look at the washing machine's outputs in each state:

Every row is different. So use each row as the state code: IDLE = 000, FILL = 100, WASH = 010, DRAIN = 001, SPIN = 011, with the bits in the order valve, motor, pump. This is output encoding. The state register now drives the valve, the motor and the pump directly. There is no output logic, and the outputs can never glitch. It is the Medvedev machine from Volume 02, built on purpose.

5.4 Area, speed and power trade-offs

Choosing an encoding trades flip-flops against logic. Fewer flip-flops usually means more complicated logic; more flip-flops usually means simpler, faster logic.

Here is the washing machine in every encoding from this volume:

Area

Area means how much of the chip the machine uses: flip-flops plus gates.

• Binary and Gray use the fewest flip-flops, ⌈log₂N⌉. But each next-state bit may depend on every state bit, so the gates grow as the machine grows.
• One-hot uses N flip-flops. Its gates stay small, because each flip-flop's logic only looks at the states with arrows into it.
• Johnson sits between the two: about N/2 flip-flops, and simple decoding.

Speed

The fastest clock a circuit can use is set by its slowest path of logic between two flip-flops - its critical path. In a state machine, that path usually runs through the next-state logic. One-hot keeps that logic shallow - two or three gates - so one-hot machines usually run fastest. Binary logic that must look at every state bit is deeper, and slower. Volume 13 measures this properly.

Power

Power in a digital circuit comes mostly from signals changing. How often they change is called their switching activity. Count the flip-flops that change per step around the washing machine:

One-hot changes the most flip-flops - two on every step, one off and one on - but its small logic switches less. Gray and Johnson change the fewest bits. The real winner depends on the whole design, and is found by measuring, not guessing.

The summary

5.5 What synthesis tools do to your encoding

Synthesis tools usually recognise state machines and may give them new codes. The codes you wrote are not always the codes in the hardware.

The tool finds your state machine

When you write a state machine in the style of Volume 04, synthesis tools such as Vivado recognise it. They notice a register whose next value is chosen by a case statement on its own current value. This is called FSM extraction. The tool then works out the states and the arrows - and often re-encodes the machine. On FPGAs it usually picks one-hot, for the reasons in sub-module 5.4. The synthesis log reports each state with its old and its new code.

So you can write your states with any names and codes you like, and still get one-hot hardware. For most machines, that is good news.

When re-encoding is a problem

Sometimes you need the codes you wrote:

• Output-coded machines. The outputs are the state bits. Re-encoding would break them.
• State read from outside. Another block, a debug probe, or software may read the state register and expect your codes.
• Safe machines. Recovery from illegal states can be removed during re-encoding - Volume 11.
• Debugging on hardware. You probe the state register and see values you never wrote, because the tool changed them.

Telling the tool what you want

You control the choice with a tool setting, or with a synthesis attribute - a note in the code that the tool reads. In Vivado, the attribute is fsm_encoding:

(* fsm_encoding = "one_hot" *)  reg [2:0] state;   // make it one-hot
(* fsm_encoding = "gray" *)     reg [2:0] state;   // or Gray
(* fsm_encoding = "none" *)     reg [2:0] state;   // keep exactly the codes I wrote

Vivado also accepts "sequential" (binary), "johnson" and "auto", and it has a project-wide setting for the same choice. Other tools have their own names for it, so check the tool's documentation. For more about attributes, see synthesis attributes in the FPGA course.

What you learned

• Binary uses the fewest flip-flops, but some steps change many bits at once.
• Gray codes change one bit on each usual step - though a loop of an odd number of states cannot be all one-bit steps.
• One-hot uses one flip-flop per state. Decoding is free, and the next-state logic can be read straight off the diagram.
• A Johnson code gives 2n states from n flip-flops, changes one bit per step, and decodes any state with a 2-input gate.
• Output encoding makes the outputs the state bits: no output logic, no glitches.
• Fewer flip-flops usually means deeper logic; one-hot is usually fastest, and best on FPGAs.
• Synthesis tools often re-encode state machines. Use a setting or attribute when you need your own codes.

Key words from this volume

Every word below has a plain-English entry in the glossary.

• Binary encoding
• Hamming distance
• Glitch
• Gray encoding
• One-hot encoding
• Illegal state
• One-cold encoding
• Johnson code
• Output encoding
• Critical path
• Switching activity
• FSM extraction
• Synthesis attribute

Practice

Interview corner

Next, Volume 06 puts everything so far to work on the most famous state machine problem of all: the sequence detector.