A proposed tag code is uniquely decodable but not prefix-free - what does allowing that lookahead actually buy you?
answer
- decodable is weaker than instantaneous
- lookahead can still resolve it
- reverse the codewords and look
- the same sum bound still applies
- buys complexity, not bits
basics
~20 sNothing in size. The Kraft-McMillan result says every uniquely decodable code satisfies the same sum bound as a prefix code, so a prefix code exists with exactly the same codeword lengths - the lookahead costs buffering and decode complexity for zero saved bits.
solid answer
~50 sUnique decodability is weaker than the prefix property: it only asks that no two symbol strings share an encoding, while the prefix property also demands you can tell where a codeword ends without reading past it. Codes exist in the gap - `0`, `01`, `11` is one, since the stream `011` decodes as `0` then `11` while `0111` decodes as `01` then `11`, so the *first* symbol is decided by the *fourth* bit. What McMillan showed is that any uniquely decodable code's lengths still satisfy the sum of `2^-li` at most 1, and Kraft's converse then builds a prefix code with those very lengths. So the gap is real but worthless: you can always take the instantaneous code, and you would, because lookahead means buffering, a more complex decoder and a longer distance to resynchronise after a corrupt bit.
go deeper
The takeaway is the ordering: a code can be decodable without being decodable on the fly, and the on-the-fly kind is the one worth using.
Be able to show a concrete code that needs lookahead and say which later bit decides an earlier symbol, rather than asserting the distinction abstractly.
State the payoff: the same length bound holds for both classes, so a prefix code of equal expected length always exists, and the lookahead only costs buffering and resynchronisation.
Treat it as a design rule for any encoding your teams own - if a proposal needs lookahead to parse, an instantaneous alternative of identical size exists, and accepting the proposal buys complexity for nothing.
## Three properties, not two Candidates usually hold two ideas - 'the code works' and 'the code is prefix-free' - when the material has three levels, each strictly stronger than the last: | property | what it demands | example | |---|---|---| | **non-singular** | different symbols get different codewords | `0`, `1`, `01` (a stream is still ambiguous) | | **uniquely decodable** | no two symbol *sequences* produce the same bit string | `0`, `01`, `11` | | **prefix-free (instantaneous)** | no codeword opens another, so boundaries need no lookahead | `0`, `10`, `11` | The middle row is the interesting one. A uniquely decodable code always has exactly one correct interpretation of any stream it produced - it is never ambiguous - but finding that interpretation may require reading beyond the symbol you are trying to emit. ## A worked example of the lookahead Take the tags coded `0`, `01` and `11`, and read left to right: - `011` parses as `0` then `11` - the alternative start `01` leaves a stranded `1`, which is not a codeword. - `0111` parses as `01` then `11` - starting with `0` would leave `111`, which splits as `11` then a stranded `1`. The first emitted symbol differs between those two streams, and the bit that decides it is the fourth. Nothing is ambiguous; the decoder simply cannot commit early. This particular code is a **suffix code** - reverse every codeword and you get `0`, `10`, `11`, which is prefix-free - so it can also be decoded unambiguously by reading the stream backwards from the end. That is a neat property and a terrible operational one: it requires the whole stream before the first symbol is known. ## Why the trade buys nothing The reason to care is a single result, usually stated as the **Kraft-McMillan inequality**: 1. **McMillan's direction:** every *uniquely decodable* code's lengths satisfy the sum of `2^-li` at most 1 - the same bound that constrains prefix codes. 2. **Kraft's converse:** any length list satisfying that bound is realised by *some prefix code*. Put them together and the conclusion is sharp: for every uniquely decodable code there is a prefix code with **exactly the same multiset of codeword lengths**, hence exactly the same expected length on any source. The gap between the two classes contains no shorter codes at all. You are free to give up instantaneous decoding, and you get nothing back. That also closes a question about the entropy floor: since `L >= H` follows from the Kraft sum bound rather than from the tree structure, it constrains uniquely decodable codes too. Abandoning the prefix property does not sneak under the entropy of the source. ## The operational costs you do pay - **Buffering.** The decoder must hold undecided bits. How many depends on the code, and it is not generally one bit; a code can need lookahead that grows with the stream. - **Decoder complexity.** Instead of one node pointer walked one bit at a time, you carry a set of candidate parses and prune it as bits arrive. - **Worse behaviour on corruption.** A prefix code already loses synchronisation after a flipped bit; a lookahead code additionally defers the point where the problem becomes visible, and may keep a whole candidate set alive. - **No streaming guarantee.** A suffix code that must be read from the end cannot be decoded incrementally at all. ## Checking whether a code is even decodable A code that is neither prefix-free nor obviously structured needs an actual test, and the standard one works by tracking **dangling suffixes**: whenever one codeword is a prefix of another, the leftover tail is recorded as a suffix that must still be explainable, and the process is repeated on the growing set. If a codeword ever turns up as a dangling suffix, two different symbol sequences produce the same bit string and the code is ambiguous; if the set stops growing without that happening, the code is uniquely decodable. That the check is a whole procedure - rather than a glance at the codewords, as with the prefix property - is itself an argument for staying prefix-free. ## The interview answer Name the three-level hierarchy, give a concrete lookahead example, and land on Kraft-McMillan: the weaker property permits no shorter codes, so the prefix property is free. Engineers who state this as a design rule - 'if it is decodable at all, an instantaneous code of the same size exists, so use it' - are showing exactly the judgment the question is testing.
- How would you check that a set of codewords is uniquely decodable at all?Run the dangling-suffix procedure: whenever one codeword is a prefix of another, record the leftover tail, then keep extending the set by comparing those tails against the codewords. If a codeword ever appears as a dangling suffix, two symbol sequences encode to the same bits and the code is ambiguous. If the set closes without that, it is uniquely decodable. The prefix property needs no such procedure, which is part of its appeal.
- Is every suffix code uniquely decodable?Yes. If no codeword is a suffix of another, then reversing every codeword yields a prefix-free code, and reading the stream backwards decodes it unambiguously. The catch is operational rather than theoretical: decoding from the end means the whole stream must arrive before the first symbol is known, which rules out streaming and makes truncation unrecoverable.
saying these in an interview costs you the question
- Treats uniquely decodable and instantaneously decodable as the same property.
- Claims dropping the prefix property lets codewords get shorter.
- Thinks any code with a prefix collision must be ambiguous.
- Says the sum bound on codeword lengths applies only to prefix codes.
- Assumes lookahead in such codes is always just one bit.