One-Hot, Character Codes and Code Distance

Check a one-hot word, read the length of a UTF-8 character from its first byte, and measure the distance between two codewords.

You Will Be Able To

  • Check that a word is one-hot or one-cold, and say what one-hot costs.
  • Read ASCII bytes and tell a UTF-8 first byte from a continuation byte.
  • Place codewords on an n-cube and count the Hamming distance between them.
Lesson
G1.8
Time
25 min
Runs on
Your browser
Check
5 questions

A motor controller selects one of four phases with a one-hot word. After a radiation upset the word reads 0110. Two phases switch on at once and short the supply. One gate that checks the word would have stopped it.

Is This Word One-Hot?
23
22
21
20

Weights show bit magnitudes. For signed values, the leftmost bit has a negative weight.

Unsigned
6

Not one-hot: 2 bits are set.

  1. Two hot bits. 0110 has two bits set. It is not one-hot, and the controller must not drive it.
  2. One hot bit. 0100 has exactly one bit set: phase 2.
  3. No hot bit. 0000 has no bit set. It is not one-hot either.

Click any bit. The panel checks the word and names the active bit.

One-Hot and One-Cold

A one-hot code has exactly one 1 in each word. N values need N bits. A one-cold code is the inverse: exactly one 0.

One-hot costs bits but saves logic. Each bit already means "this value", so no decoder is needed. That is why small state machines often use it (lesson G7.6).

Any word with zero or two or more 1s is invalid. The check: the word is not zero, and x & (x - 1) is zero. Subtracting 1 clears the lowest 1, so the AND keeps only the 1s above it.

xx - 1x & (x - 1)x != 0One-hot?
010000110000yesyes
011001010100yesno: two 1s
000011110000nono: no 1s

Measured on the simulator: the test agrees with the built-in $onehot on all 16 words of four bits.

Characters as Bytes: ASCII and UTF-8

ASCII gives each letter, digit and sign a 7-bit code. A is 41 in hex and a is 61: upper and lower case differ in bit 5. The digit 0 is 30.

UTF-8 stores every Unicode character in one to four bytes. ASCII stays as one byte with a 0 on top. The first byte of a longer character starts with as many 1s as the character has bytes. Every later byte starts with 10.

CharacterNameUTF-8 bytes (hex)UTF-8 bytes (binary)
U+0041the letter A4101000001
U+00E9e with an acute accentc3 a911000011 10101001
U+20ACthe euro signe2 82 ac11100010 10000010 10101100
U+1F600a smiling-face emojif0 9f 98 8011110000 10011111 10011000 10000000

Encoded by Node's UTF-8 encoder. The simulator prints the same bytes for the first three.

First bits of a byteMeaningFrom the lab
0xxxxxxxa one-byte character (ASCII)from 00: length 1
10xxxxxxa continuation bytefrom 80: length 0
110xxxxxfirst of 2 bytesfrom c0: length 2
1110xxxxfirst of 3 bytesfrom e0: length 3
11110xxxfirst of 4 bytesfrom f0: length 4
11111xxxnever usedfrom f8: length -1

The lab decodes all 256 byte values with one casez and prints where the length changes. It reads the leading bits only: c0, c1 and f5 to ff never appear in valid UTF-8.

A receiver can join a stream at any byte. It skips bytes that start with 10 and starts at the next first byte.

Codewords on a Cube

Every n-bit word is a corner of an n-dimensional cube. Two corners share an edge when the words differ in one bit. The Hamming distance between two words is the number of bits in which they differ: the edges walked between them.

The 3-bit Words as a CubeEach box is a 3-bit word. A line joins two words that differ in one bit; its label names that bit.
  • Neutral
  • Structure
The 3-bit words as a cubeEach box is a 3-bit word. A line joins two words that differ in one bit; its label names that bit. neutral 000 neutral 001 neutral 010 neutral 100 neutral 011 neutral 101 neutral 110 neutral 111 bit 0bit 1bit 2bit 1bit 2bit 0bit 2bit 0bit 1bit 2bit 1bit 0
  1. neutral 001
    • bit 1 → 011
    • bit 2 → 101
  2. neutral 010
    • bit 0 → 011
    • bit 2 → 110
  3. neutral 100
    • bit 0 → 101
    • bit 1 → 110
  4. neutral 000
    • bit 0 → 001
    • bit 1 → 010
    • bit 2 → 100
  5. neutral 011
    • bit 2 → 111
  6. neutral 101
    • bit 1 → 111
  7. neutral 110
    • bit 0 → 111
  8. neutral 111
  1. One-hot words

    001, 010 and 100 are the one-hot words. Any two of them are two edges apart: distance 2.

  2. Even-parity words

    000, 011, 101 and 110 have an even number of 1s. No two of them share an edge, so one flipped bit always leaves the set.

  3. Distance 3

    000 and 111 differ in all three bits. The shortest walk between them takes three edges.

Read the diagram as text
  • 000
  • 001
  • 010
  • 100
  • 011
  • 101
  • 110
  • 111
  • 000 → 001: bit 0
  • 000 → 010: bit 1
  • 000 → 100: bit 2
  • 001 → 011: bit 1
  • 001 → 101: bit 2
  • 010 → 011: bit 0
  • 010 → 110: bit 2
  • 100 → 101: bit 0
  • 100 → 110: bit 1
  • 011 → 111: bit 2
  • 101 → 111: bit 1
  • 110 → 111: bit 0

A code whose words are all at least d apart is said to have minimum distance d. Lesson G1.9 uses this to detect and correct errors.

To compute the distance, XOR the two words and count the 1s. That is one XOR per bit and a count, which hardware does with a small adder tree.

Asked in interviews
  1. When would you choose one-hot encoding?

    For a small state machine or a select signal. There one flip-flop per state is cheap, and each output is a single bit. Not for a wide counter.

  2. How do you check that a word is one-hot?

    It is not zero, and x & (x - 1) is zero. In SystemVerilog, $onehot(x) does the same.

  3. What is the Hamming distance, and why does it matter?

    The number of bits in which two words differ. If every pair of codewords is at least d apart, d - 1 flipped bits cannot turn one codeword into another.

Try It

Only the four words with a single 1 pass the one-hot check. Zero fails because of x != 0; every word with two or more 1s fails the AND.

The UTF-8 decoder runs over all 256 byte values. Each line marks where the length changes: 00 to 7f are ASCII, 80 to bf continue a character, and so on.

Delete (x != 0) && from the checker and run. The word 0000 joins the list.

RUNIcarus Verilog · in your browser
Edit the code, then run it
Expected: one-hot words: 0001 0010 0100 1000 from 00: length 1 from 80: length 0 from c0: length 2 from e0: length 3 from f0: length 4 from f8: length -1

Check Yourself

Predict the outputThe program reads the first byte of a UTF-8 character. What exact line does it print?
module tb;
  logic [7:0] b;
  int n;
  initial begin
    b = 8'he2;
    casez (b)
      8'b0???????: n = 1;
      8'b10??????: n = 0;
      8'b110?????: n = 2;
      8'b1110????: n = 3;
      8'b11110???: n = 4;
      default:     n = -1;
    endcase
    $display("%0d", n);
  end
endmodule
Spot the bugEach option sets ok when the byte x is one-hot. The bench tries all 256 bytes. Which option fails?
ConceptWhat is a UTF-8 byte of the form 10xxxxxx?
ConceptWhat is the Hamming distance between any two different one-hot words?
ConceptASCII A is 41 in hex. What is a?

Common Mistakes

Wrong Check one-hot with (x & (x - 1)) == 0 alone.

That test also passes the all-zero word, which has no hot bit.

Fix Also require x != 0, or use $onehot(x).

Before
ok = (x & (x - 1)) == 0;
After
ok = (x != 0) &&
     ((x & (x - 1)) == 0);

Wrong Encode one-hot to binary with an OR of the bits and no check.

A two-hot word then gives the OR of two indices, a third state that was never meant.

Fix Flag every word that is not one-hot, and decide what the output is then.

Wrong Treat every UTF-8 byte as the start of a character.

A byte 10xxxxxx continues the character before it. Counting it as a character gives the wrong length.

Fix Count only bytes that do not start with 10.

Wrong Use one-hot for a wide counter.

A 256-state counter needs 256 flip-flops in one-hot and 8 in binary.

Fix Use one-hot for small state machines, where fast decoding pays for the flip-flops.

Remember

  • One-hot: exactly one 1 per word; one flip-flop per value, no decoder.
  • Valid one-hot: x != 0 and x & (x - 1) == 0, or $onehot(x).
  • ASCII is 7 bits; UTF-8 keeps ASCII and marks longer characters by the leading 1s of the first byte.
  • Hamming distance is the count of differing bits: the edges walked on the n-cube.

Practice

Report a problem with this page