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.
Weights show bit magnitudes. For signed values, the leftmost bit has a negative weight.
- Unsigned
- 6
Not one-hot: 2 bits are set.
- Two hot bits. 0110 has two bits set. It is not one-hot, and the controller must not drive it.
- One hot bit. 0100 has exactly one bit set: phase 2.
- 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.
| x | x - 1 | x & (x - 1) | x != 0 | One-hot? |
|---|---|---|---|---|
| 0100 | 0011 | 0000 | yes | yes |
| 0110 | 0101 | 0100 | yes | no: two 1s |
| 0000 | 1111 | 0000 | no | no: 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.
| Character | Name | UTF-8 bytes (hex) | UTF-8 bytes (binary) |
|---|---|---|---|
| U+0041 | the letter A | 41 | 01000001 |
| U+00E9 | e with an acute accent | c3 a9 | 11000011 10101001 |
| U+20AC | the euro sign | e2 82 ac | 11100010 10000010 10101100 |
| U+1F600 | a smiling-face emoji | f0 9f 98 80 | 11110000 10011111 10011000 10000000 |
Encoded by Node's UTF-8 encoder. The simulator prints the same bytes for the first three.
| First bits of a byte | Meaning | From the lab |
|---|---|---|
| 0xxxxxxx | a one-byte character (ASCII) | from 00: length 1 |
| 10xxxxxx | a continuation byte | from 80: length 0 |
| 110xxxxx | first of 2 bytes | from c0: length 2 |
| 1110xxxx | first of 3 bytes | from e0: length 3 |
| 11110xxx | first of 4 bytes | from f0: length 4 |
| 11111xxx | never used | from 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.
- Neutral
- Structure
- One-hot words
001, 010 and 100 are the one-hot words. Any two of them are two edges apart: distance 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.
- 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
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.
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.
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.
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 -1Check Yourself
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).
ok = (x & (x - 1)) == 0;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.