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.
toggles counts the wires that change in each transfer; for the inverted bus it includes the invert line inv.- Cycle 1
0f against 00: four wires would change. That is not more than half of eight, so the word goes out plain.
- Cycle 2
f0 against 0f: all eight would change. The encoder sends the complement, 0f, and raises
inv. Only one wire moves:inv. - Cycle 3
ff against 0f: four would change, so ff goes out plain and
invfalls. Five wires move. - Cycle 4
01 against ff: seven would change. The encoder sends fe with
invhigh: two wires move instead of seven. - Cycle 5
fe against the bus value fe: nothing would change. It goes out plain; only
invfalls.More context
The encoder compares the new word with what the wires hold now, not with the previous data word.
- 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.
- I/O
- Datapath
- Bus
- Data
- Control
- Count
XOR the new word with the current bus value and count the ones. That is how many wires would change.
- Decide
If more than 8 of the 16 would change, send the complement. Then at most 8 data wires change.
- Drive
The bus carries the chosen value, and
invsays which it is.invmay change too, so the worst case is 8 + 1 = 9 wires. - 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 binary | Gray code | Bus-invert | Worst transfer: plain | Worst transfer: bus-invert |
|---|---|---|---|---|---|
| Random words | 7,818 | 7,998 | 6,864 | 13 | 9 |
| Addresses counting up | 1,991 | 1,001 | 1,989 | 10 | 9 |
| Zero 7 times in 8, else random | 1,282 | 1,332 | 1,218 | 11 | 9 |
| Each second word the complement of the one before | 12,089 | 4,432 | 4,037 | 16 | 9 |
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).
*_toggles counts the bits that change on the step into that column.- Cycle 1
0 to 1: both codes change one bit.
- Cycle 2
1 to 2: binary changes two bits (001 to 010). Gray changes one (001 to 011).
- Cycle 4
3 to 4: binary changes all three bits. Gray still changes one (010 to 110).
- 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.
- Control / FSM
- Control
- The main loop
IDLE, ADDR, DATA, RESP and back. Each arrow joins two codes that differ in one bit.
- 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 code | Flip-flops | State-register toggles | Toggles per state change |
|---|---|---|---|
| Binary (IDLE = 0 ... RESP = 4) | 3 | 3,578 | 1.35 |
| Gray-assigned (the figure) | 3 | 2,650 | 1.00 |
| One-hot | 5 | 5,300 | 2.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
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.
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.
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?
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 togglesCheck Yourself
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.