Low-Power Encoding: Buses, Counters and State Machines

Send the same values with fewer wire changes, and tell when a code pays for the logic it adds.

You Will Be Able To

  • Count the wire changes of a bus for a given stream of words.
  • Choose between plain binary, bus-invert and Gray code from the kind of traffic.
  • Explain what a state encoding costs in flip-flops as well as in toggles.
Lesson
W2.6
Time
25 min
Runs on
Your browser
Check
5 questions

A sensor chip sends random readings over a 16-bit bus that leaves the package, so each wire change charges a large load. In 1,000 transfers the wires change 7,818 times.

The Same Six Words, Sent Plain and Bus-InvertedAn 8-bit bus that starts at 00. toggles counts the wires that change in each transfer; for the inverted bus it includes the invert line inv.
0123456datax0ff0ff01fe03plain_bus000ff0ff01fe03plain_toggles0484787inverted_bus000ffffefcinvinverted_toggles0415212
Scroll horizontally ↔
  1. Cycle 1

    0f against 00: four wires would change. That is not more than half of eight, so the word goes out plain.

  2. Cycle 2

    f0 against 0f: all eight would change. The encoder sends the complement, 0f, and raises inv. Only one wire moves: inv.

  3. Cycle 3

    ff against 0f: four would change, so ff goes out plain and inv falls. Five wires move.

  4. Cycle 4

    01 against ff: seven would change. The encoder sends fe with inv high: two wires move instead of seven.

  5. Cycle 5

    fe against the bus value fe: nothing would change. It goes out plain; only inv falls.

    More context

    The encoder compares the new word with what the wires hold now, not with the previous data word.

  6. Cycle 6

    03 against fe: seven would change, so fc goes out inverted. In all: 15 wire changes against 38.

Computed from the rule: invert when more than half of the data wires would change. The receiver undoes it with inv.

Bus-invert coding sends each word or its complement, whichever moves fewer wires, plus one wire that says which.

Bus-Invert Coding

A wire change costs the same energy whatever the value means. So a code can send the same information with fewer changes, if it knows the traffic.

A Bus-Invert Encoder and DecoderArrows show data. The encoder compares the new word with the value the wires hold now.
  • I/O
  • Datapath
  • Bus
  • Data
  • Control
A bus-invert encoder and decoderArrows show data. The encoder compares the new word with the value the wires hold now. io New word 16 bits datapath Count changes ones(bus XOR word) datapath Word orcomplement invert if count > 8 bus Bus wires 16 data + inv datapath Decoder XOR with inv io Word again at the receiver wordinvert?bus, invcurrent busbus, invword
  1. io New word16 bits
    • word → Count changes
  2. datapath Count changesones(bus XOR word)
    • invert? → Word or complement
  3. bus Bus wires16 data + inv
    • current bus → Count changes
    • bus, inv → Decoder
  4. datapath Word or complementinvert if count > 8
    • bus, inv → Bus wires
  5. datapath DecoderXOR with inv
    • word → Word again
  6. io Word againat the receiver
  1. Count

    XOR the new word with the current bus value and count the ones. That is how many wires would change.

  2. Decide

    If more than 8 of the 16 would change, send the complement. Then at most 8 data wires change.

  3. Drive

    The bus carries the chosen value, and inv says which it is. inv may change too, so the worst case is 8 + 1 = 9 wires.

  4. Decode

    The receiver XORs every bit with inv. It gets the original word back in one gate delay.

Read the diagram as text
  • New word: 16 bits
  • Count changes: ones(bus XOR word)
  • Word or complement: invert if count > 8
  • Bus wires: 16 data + inv
  • Decoder: XOR with inv
  • Word again: at the receiver
  • New word → Count changes: word
  • Count changes → Word or complement: invert?
  • Word or complement → Bus wires: bus, inv
  • Bus wires → Count changes: current bus
  • Bus wires → Decoder: bus, inv
  • Decoder → Word again: word

Stan and Burleson proposed this code in 1995; their rule also counts the inv wire. This page uses the simpler data-only rule. The extra cost is one wire, a ones counter and a row of XOR gates.

The lab sends 1,000 words of four kinds of traffic and counts the wire changes of each code, including inv.

Traffic (1,000 words)Plain binaryGray codeBus-invertWorst transfer: plainWorst transfer: bus-invert
Random words7,8187,9986,864139
Addresses counting up1,9911,0011,989109
Zero 7 times in 8, else random1,2821,3321,218119
Each second word the complement of the one before12,0894,4324,037169

Measured by the lab on Icarus. Bus-invert counts 17 wires; the others count 16.

On random words bus-invert saves 12 %. On the swinging traffic it saves 67 %. The worst transfer never exceeds 9 wires, half the width plus one, in any traffic.

On addresses that count up it saves nothing: 1,989 against 1,991. A counter rarely changes more than half its bits, so the encoder almost never inverts.

Gray Code for Counting

A binary counter changes 1 bit on half of its steps, 2 bits on a quarter, and so on. On average that is close to 2 bits per step. At the wrap all bits change at once.

Gray code orders the values so that each step changes exactly one bit, including the wrap. The code of a count b is b ^ (b >> 1).

A 3-bit Count, Binary and Gray, for One Full Lap*_toggles counts the bits that change on the step into that column.
012345678count012345670binary000001010011100101110111000binary_toggles012131213gray000001011010110111101100000gray_toggles
Scroll horizontally ↔
  1. Cycle 1

    0 to 1: both codes change one bit.

  2. Cycle 2

    1 to 2: binary changes two bits (001 to 010). Gray changes one (001 to 011).

  3. Cycle 4

    3 to 4: binary changes all three bits. Gray still changes one (010 to 110).

  4. Cycle 8

    7 back to 0: binary changes three bits again. Gray goes from 100 to 000: one bit.

Computed from the two codes. Over the lap binary changes 14 bits and Gray changes 8.

In the lab, the bus carrying counting addresses changed 1,991 times in binary and 1,001 times in Gray: about half. The receiver needs a Gray-to-binary decoder if it must do arithmetic on the value.

Gray code has a second use. A pointer that crosses between clock domains changes one bit at a time. So the other side never samples a mix of old and new bits (lesson R6.4).

Gray code is useless for unrelated values. Random words gave 7,998 changes in Gray against 7,818 in binary.

State Encoding: Binary, Gray or One-Hot

A state machine stores its state in flip-flops, and the code of each state is a choice. The lab runs a small bus controller for 10,000 cycles.

The Controller and Its Gray-Assigned CodesArrows show state changes. Each label is the 3-bit code of the Gray-assigned version.
  • Control / FSM
  • Control
The controller and its Gray-assigned codesArrows show state changes. Each label is the 3-bit code of the Gray-assigned version. control IDLE 000 control ADDR 001 control DATA 011 control WAIT 111 control RESP 010 requeststallgo4 beats
  1. control IDLE000
    • request → ADDR
  2. control ADDR001
    • DATA
  3. control DATA011
    • stall → WAIT
    • 4 beats → RESP
  4. control RESP010
    • IDLE
  5. control WAIT111
    • go → DATA
  1. The main loop

    IDLE, ADDR, DATA, RESP and back. Each arrow joins two codes that differ in one bit.

  2. The stall loop

    DATA and WAIT differ in one bit as well (011 and 111), so a stall costs one toggle each way.

Read the diagram as text
  • IDLE: 000
  • ADDR: 001
  • DATA: 011
  • WAIT: 111
  • RESP: 010
  • IDLE → ADDR: request
  • ADDR → DATA
  • DATA → WAIT: stall
  • WAIT → DATA: go
  • DATA → RESP: 4 beats
  • RESP → IDLE

With natural binary codes (IDLE = 0 to RESP = 4), two arrows change two bits. They are ADDR to DATA (001 to 010) and DATA to RESP (010 to 100).

State codeFlip-flopsState-register togglesToggles per state change
Binary (IDLE = 0 ... RESP = 4)33,5781.35
Gray-assigned (the figure)32,6501.00
One-hot55,3002.00

Measured by the lab: 2,650 state changes in 10,000 cycles. The controller is idle most of the time.

One-hot always changes two bits per transition: one flop falls and one rises. It also has more flip-flops, and every flip-flop clock pin burns power in every cycle. For this mostly idle controller both counts favour the 3-bit codes.

One-hot has a real strength: its next-state and output logic is shallow, so it can be fast. That logic is not counted here. Measure the whole block (W1.5) before you decide on a large machine.

Asked in interviews
  1. What is bus-invert coding?

    The encoder sends either the word or its complement, whichever changes fewer wires than the current bus value. An extra line tells the receiver which one it sent. At most half the width plus one wires change per transfer.

  2. When would you Gray-code a bus?

    When consecutive values usually differ by one, as with counters, pointers and sequential addresses. Each step then changes one bit. On random data it saves nothing.

  3. Is one-hot encoding low power?

    Not by default. It toggles two bits per transition and needs more flip-flops, whose clock pins burn power every cycle. A Gray-assigned binary code often toggles less. One-hot wins on decode depth and speed.

Try It

Run it. The bench sends four kinds of traffic through three codes and prints the wire changes of each. Then it runs the controller and counts its state-register toggles.

Change > 8 to > 4 in the bus-invert line. The encoder now inverts too often. Predict which totals rise, then run.

Change the IDLE line so that a request comes in one cycle of two: lfsr[0] == 0. The controller is busier. Predict the toggles per state change of each code, then run. Which ratios cannot move, and why?

RUNIcarus Verilog · in your browser
Edit the code, then run it
Expected: random: raw=7818 gray=7998 bus-invert=6864 | worst raw=13 bus-invert=9 sequential: raw=1991 gray=1001 bus-invert=1989 | worst raw=10 bus-invert=9 sparse: raw=1282 gray=1332 bus-invert=1218 | worst raw=11 bus-invert=9 swings: raw=12089 gray=4432 bus-invert=4037 | worst raw=16 bus-invert=9 fsm: 10000 cycles, 2650 state changes fsm binary (3 flops): 3578 toggles fsm gray-assigned (3 flops): 2650 toggles fsm one-hot (5 flops): 5300 toggles

Check Yourself

Predict the outputA 3-bit counter steps once around its full range and back to 0. The bench counts the bits that change, in binary and in Gray code. What exact line does it print?
module tb;
  function automatic int ones(input logic [2:0] v);
    ones = v[0] + v[1] + v[2];
  endfunction
  logic [2:0] b = 0, nb, g, ng;
  int t_bin = 0, t_gray = 0;
  initial begin
    repeat (8) begin                 // one full lap: 0, 1, ... 7 and back to 0
      nb = b + 3'd1;
      g  = b ^ (b >> 1);
      ng = nb ^ (nb >> 1);
      t_bin  += ones(b ^ nb);
      t_gray += ones(g ^ ng);
      b = nb;
    end
    $display("binary=%0d gray=%0d", t_bin, t_gray);
  end
endmodule
Predict the outputThe receiver of a bus-inverted bus sees these wire values. What exact line does it print?
module tb;
  logic [7:0] bus = 8'h0F;   // what the wires carry
  logic       inv = 1'b1;    // the invert line is high
  logic [7:0] data;
  initial begin
    data = inv ? ~bus : bus;
    $display("data=%h", data);
  end
endmodule
ConceptA 32-bit address bus carries addresses that mostly count up by one. Which code cuts its wire changes the most?
ConceptHow many wires can change in one transfer of a 16-bit bus with bus-invert coding, counting the invert line?
ConceptA controller with five states idles most of the time. Why did the 3-bit Gray-assigned code beat one-hot on power in the lab?

Common Mistakes

Wrong Add bus-invert coding to a short bus inside one block.

The encoder adds a comparator, an inverter row and an extra wire, and a short wire has little capacitance to save.

Fix Use it on long, heavily loaded wires, such as an off-chip or cross-chip bus.

Wrong Gray-code a data bus that carries unrelated values.

Gray code helps only when the next value is the previous one plus 1. On random words it gave 7,998 changes against 7,818 for plain binary.

Fix Keep Gray code for counters, pointers and addresses that step by one.

Wrong Pick a one-hot state register "for low power" without counting its flip-flops.

Each flip-flop's clock pin burns power in every cycle, whether the state changes or not (W1.2).

Fix Count toggles and flip-flops together, on the controller's real traffic.

Remember

  • A wire change costs energy whatever it means. A code can carry the same values with fewer changes.
  • Bus-invert sends the word or its complement and caps each transfer at half the width plus one.
  • Gray code changes one bit per step. It suits counters and sequential addresses, not random data.
  • State encoding is a power choice: count toggles and flip-flops on the real traffic.
  • Every code adds logic and sometimes a wire. It pays only on wires with a large load.

Practice

Report a problem with this page