Back to the on-screen lesson ·
What makes a code decodable at all: distinct codewords, one reading per bit string, and the prefix property that lets a decoder stop.
Paper packet. Every task here also exists on screen, where it is checked automatically; answers written on paper are not assessed by Nydus. When you are back at a device, enter your answers there.
By the end of this lesson you will be able to draw the binary tree of a prefix code and read the prefix property off it, sort codes into singular, nonsingular, uniquely decodable and prefix-free, decode a bit stream symbol by symbol without lookahead, count how many codewords of a given length a code still has room for, and recognise the same condition in a dialling plan that has to know when a number is finished.
Entropy as the least average number of bits per symbol that any description can reach. This unit builds the descriptions themselves, and this lesson settles what makes a code usable at all, before any question of how short it is.
A code is nonsingular when distinct symbols get distinct codewords, uniquely decodable when every string of bits has only one reading, and prefix-free (also called a prefix code or an instantaneous code) when no codeword is the beginning of another. Drawn as a tree, the codewords of a prefix code are its leaves.
A binary symbol code assigns each source symbol a codeword, a finite string of bits, and a message is coded by concatenating codewords. The code is nonsingular if distinct symbols get distinct codewords, uniquely decodable if every concatenation parses in only one way, and prefix-free (a prefix code or instantaneous code) if no codeword is the beginning of another. A prefix code is decoded on the fly: each codeword is recognised the moment its last bit arrives, with no lookahead. Picture the codewords as leaves of a binary tree, left branch $0$, right branch $1$; prefix-free means no codeword sits on the path to another. The code $\{0, 10, 11\}$ is a prefix code; $\{0, 01, 11\}$ is uniquely decodable (read it backwards) but needs lookahead; $\{0, 1, 01\}$ is not uniquely decodable since $01$ could be $a\,b$ or $c$. Every uniquely decodable code can be replaced by a prefix code with the same lengths (McMillan), so prefix codes lose nothing.
Another way: picture
A binary tree: root at the top, $0$ to the left, $1$ to the right. The codewords $0$, $10$, $11$ are three leaves; nothing hangs below a leaf. Decoding walks from the root, one bit per step, and outputs a symbol whenever it lands on a leaf.
Another way: steps
Each property is stronger than the one before it: prefix-free implies uniquely decodable implies nonsingular, and none of the arrows reverses.
| Code for $\{a, b, c\}$ | nonsingular | uniquely decodable | prefix-free | why |
|---|---|---|---|---|
| $0, 0, 1$ | no | no | no | two symbols share a codeword |
| $0, 1, 01$ | yes | no | no | $01$ parses as $ab$ or as $c$ |
| $0, 01, 11$ | yes | yes | no | decodable, but only with lookahead |
| $0, 10, 11$ | yes | yes | yes | no codeword begins another |
The third row matters: $\{0, 01, 11\}$ is uniquely decodable even though $0$ begins $01$. Read a long string from the right and every parse is forced, so nothing is ambiguous; but a decoder must wait, sometimes for many bits, before it can commit. A prefix code never waits, which is why it is also called instantaneous.
Start at the root; each bit takes the left branch ($0$) or the right one ($1$); when you land on a leaf, output its symbol and jump back to the root. Decoding $100110$ with $a = 0$, $b = 10$, $c = 11$:
| bits so far | at the tree | output |
|---|---|---|
| $1$ | right child, not a leaf | — |
| $10$ | leaf $b$ | $b$ |
| $0$ | leaf $a$ (back at the root) | $a$ |
| $1$ | right child | — |
| $11$ | leaf $c$ | $c$ |
| $0$ | leaf $a$ | $a$ |
The message is $b\,a\,c\,a$. Every practice string uses this same code, so learn its three rules: a leading $0$ is always $a$; $10$ is $b$; $11$ is $c$. Read the bits strictly left to right and never look ahead.
Common mistakes
The first error is treating distinct codewords as enough: $\{0, 1, 01\}$ has three different codewords and still cannot be decoded, because $01$ reads two ways. The second is assuming that only prefix codes are uniquely decodable; $\{0, 01, 11\}$ is a counterexample, decodable with lookahead. The third is reading a chain of extensions such as $\{1, 10, 100\}$ as a prefix code because the codewords differ in length: each one begins the next, which is precisely what prefix-free forbids. And the test is against every longer codeword, not only the next one in the list.
Code $a = 0$, $b = 10$, $c = 11$; received $1 0 0 1 1 0$.
$1$: wait; $10 = b$. $0 = a$. $1$: wait; $11 = c$. $0 = a$. Message $b\,a\,c\,a$, decided bit by bit.
No lookahead needed.
Code $a = 0$, $b = 1$, $c = 01$. The string $01$ is $a\,b$ and also $c$.
Two parsings.
Not uniquely decodable; and Kraft's sum $\tfrac{1}{2} + \tfrac{1}{2} + \tfrac{1}{4} > 1$ already rules out any prefix code with lengths $1, 1, 2$.
$0 \to a$, $0 \to a$.
A leading zero is always the whole codeword $a$.
$11 \to c$.
$10 \to b$: the message is $a\,a\,c\,b$.
Check against the table of decodings: 001110 decodes to aacb.
A prefix code already uses $3$ codewords of length $2$. How many of length $4$ can join it?
Depth $4$ has $2^4 = 16$ nodes; each length-$2$ codeword blocks $2^{4 - 2} = 4$ of them.
$16 - 3 \cdot 4 = 4$ codewords of length $4$ remain: exactly the subtree under the one unused length-$2$ node.
All codewords have the same length, so none can be a proper prefix of another.
Yes: every fixed-length code is a prefix code, with Kraft sum exactly $1$.
Build the binary tree of the code $a = 0$, $b = 10$, $c = 11$. Join each node to the node reached by appending one more bit.
This task has no paper form; do it on a device.
Match each binary code for $\{a, b, c\}$ to the strongest description that fits it.
| A prefix code: decodes instantly | Uniquely decodable, but needs lookahead | Nonsingular, but not uniquely decodable | Singular: two symbols share a codeword | |
|---|---|---|---|---|
| $a = 0,\ b = 10,\ c = 11$ | ||||
| $a = 0,\ b = 01,\ c = 11$ | ||||
| $a = 0,\ b = 1,\ c = 01$ | ||||
| $a = 0,\ b = 0,\ c = 1$ |
A binary prefix code already has $2$ codewords of length $3$. How many codewords of length $5$ can still be added?
Answer:
With the prefix code $a = 0$, $b = 10$, $c = 11$, the receiver is sent the bits $01110$. Put the three symbols in the order they are decoded.
Number the steps in order (write the number in the box):
A telephone exchange must connect a call as soon as the last digit is dialled, with no pause and no timer. The plan below lists every number in use. Select every number that the exchange cannot act on the moment it is complete.
This task has no paper form; do it on a device.
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
The code $a = 0$, $b = 01$, $c = 11$ is not a prefix code. Is it uniquely decodable?
You can tell which codes decode, which decode instantly, and which cannot be decoded at all. Say in your own words why distinct codewords are not enough for a code to be usable. Next: Kraft's inequality, which decides exactly which sets of codeword lengths are possible.
13. Your turn: is $\{00, 01, 10, 11\}$ a prefix code?, step 2