skip to content

A binary envelope packs variable-length field tags back to back with no separator bits - why must those tag codewords be prefix-free?

level: middleimportance: must knowfreq 62%

answer

  1. no fences between codewords
  2. boundaries must be self-evident
  3. no codeword starts another
  4. a leaf ends a symbol
  5. decode without lookahead

basics

~20 s

Prefix-free means no codeword is the opening of another, so a decoder reading bit by bit knows a symbol has ended the instant it recognises one. Without that property it must look ahead or carry explicit lengths and separators.

solid answer

~40 s

The stream carries no boundaries, so the boundaries have to be implied by the code itself. A code is **prefix-free** when no codeword is a prefix of any other; that is exactly the condition that lets a decoder walk a binary code tree from the root, one bit per edge, and emit a symbol the moment it lands on a leaf, then restart at the root. No separator pattern is needed - and a separator would need escaping anyway, because any bit pattern can occur inside a codeword. Prefix-free codes are also called *instantaneous*: the decoder commits to a symbol without seeing a single bit beyond it. Drop the property and decoding may still be possible, but only with lookahead and buffering, which buys you nothing in size.

code

pseudocode · 9 lines
pseudocode
node = root
for each bit b in stream:
    node = child(node, b)        // 0 -> left edge, 1 -> right edge
    if is_leaf(node):
        emit symbol(node)
        node = root

if node is not root:
    error "stream ended mid-codeword"

go deeper

for a junior

Remember the one-line statement: no codeword may be the beginning of another. That is what lets a reader tell where one symbol stops and the next starts when nothing separates them.

for a middle

Be able to explain the decoding procedure, not just the definition: walk a code tree one bit per edge, emit on reaching a leaf, reset to the root. Say why every codeword must sit at a leaf.

for a senior

Show the trade-off against fixed-width tags and length prefixes, and be honest that a prefix code gives framing but no error detection - a flipped bit yields a legal walk and silently wrong output.

for a principal

The judgement is whether the tag distribution is skewed enough to repay variable-length decoding at all, and what the decode cost and the loss of random access mean for the readers you are asking to adopt the format.

## A stream with no fences The envelope is a run of bits. Field tags are written one after another with nothing between them - no separator byte, no length prefix, no alignment padding. The decoder receives `01101110...` and has to answer a question the bits never state: **where does the first codeword end?** Nothing in the stream marks it. If the answer is not derivable from the code itself, the decoder is guessing, and one wrong boundary shifts every symbol after it. There are only three ways to supply that boundary: make every codeword the same known width, write an explicit length before each one, or design the code so the boundary is self-evident. The third is what a prefix code does, and it is the only one of the three that costs zero extra bits. ## What prefix-free says, precisely A code is **prefix-free** (or *prefix*, or *instantaneous*) when **no codeword is a prefix of any other codeword**. Note what that does *not* say: - It is not the statement that codewords are distinct - distinctness is far weaker, and `0` and `01` are distinct while one opens the other. - It is not a claim about lengths. Codewords may have wildly different lengths; `0`, `10`, `110`, `1110`, `1111` is prefix-free with lengths 1, 2, 3, 4 and 4. - It is not required for decodability in general. Some codes that fail it can still be decoded, just not instantaneously. The property has a picture: build a binary tree where a `0` takes the left edge and a `1` the right, and place each codeword at the node its bits spell out. The code is prefix-free **exactly when every codeword sits at a leaf** - because a codeword parked at an internal node is, by construction, the beginning of every codeword below it. ## Decoding is a walk of that tree | field | codeword | length | |---|---|---| | A | `0` | 1 | | B | `10` | 2 | | C | `110` | 3 | | D | `1110` | 4 | | E | `1111` | 4 | The decoder holds one piece of state, the current node, starting at the root. Each bit moves it down one edge. Reaching a leaf means: a complete codeword has just been consumed, emit that field's tag and reset to the root. It never reads ahead of the symbol it emits, never backs up, and never needs to buffer. On `0 1 1 0 1 0`, it emits A, then C, then B, and ends back at the root. Two useful consequences fall out of the same walk: 1. **Errors are self-announcing at the end.** If the stream runs out while the decoder is sitting on an internal node, the last codeword was truncated - a real, detectable framing error. 2. **Errors are not self-correcting in the middle.** A flipped bit produces a different but perfectly legal walk, so a prefix code detects nothing by itself; wrong tags simply appear. Integrity is a separate mechanism layered on top. ## What breaks when the property is dropped Take tags coded `0`, `01` and `11`. Reading the stream `011`, the decoder sees `0` and cannot commit: the symbol may be the one-bit codeword, or the first half of `01`. Here the tie is resolved only by what follows - `011` parses as `0` then `11`, while `0111` parses as `01` then `11`. The **first** symbol changes because of the **fourth** bit. That code is not broken - every bit string it produces has exactly one parse - but the decoder must hold bits back and look ahead, and the amount of lookahead is a property of the code, not a constant you can assume is one bit. ## The alternatives, and what they cost | scheme | boundary comes from | cost | |---|---|---| | fixed-width tag | a width both sides agree on | every tag pays the widest tag's size | | explicit length prefix | bits written before each codeword | the length field itself, on every symbol | | separator pattern | a reserved bit pattern | escaping, because the pattern can occur inside data | | prefix-free code | the code's own structure | none in bits; a tree walk in the decoder | Fixed width is the right answer when the tag set is small and uniform - it is simpler, seekable and branch-free. Prefix-free coding wins when the frequency distribution is skewed, because it is what lets the common tags be short while rare ones stay long, with no framing overhead to pay it back. ## What an interviewer is listening for The expected answer names the property, states it as a statement about *codewords*, and connects it to a decoding procedure - leaf, emit, reset. Strong answers add that the property is about instantaneity rather than decodability, and that the prefix-free structure is the reason a variable-length encoding can be read straight off the wire without a single framing bit.

  • The stream ends while the decoder is on an internal node. What has happened, and what should it report?
    The final codeword was cut short: the bits consumed so far are a proper prefix of at least one codeword and of no complete one. That is a genuine framing error - truncated input, a wrong declared payload length, or a corrupted tail - and it is one of the few errors a prefix code detects on its own. The decoder should fail rather than emit a guess for the partial walk.
  • When is a fixed-width tag the better choice than a prefix-free variable-width one?
    When tags are roughly equally frequent, so there is little skew to exploit; when the reader wants to skip fields by arithmetic rather than by decoding; or when decode cost matters more than size, since a fixed width is a single masked read instead of a per-bit tree walk. Prefix-free coding pays off only in proportion to how skewed the tag distribution actually is.
  • Does a prefix code protect against a flipped bit in the stream?
    No. A flipped bit usually produces a different but entirely legal walk, so the decoder emits wrong tags with no complaint, and because codeword lengths differ, every later boundary can shift too. The only case it catches is a walk left stranded on an internal node at end of stream. Detection and repair are separate mechanisms placed around the coded bits.

A dialling plan where no number is the start of a longer number: the exchange can connect you the moment you press the last digit, with no need for a terminating key or a pause.

saying these in an interview costs you the question

  • Says any variable-length code can be decoded as long as you know the alphabet.
  • Thinks a separator pattern is free and can never occur inside a codeword.
  • Claims prefix-free just means the codewords are all different.
  • Believes the decoder must buffer the whole stream before it can start.
  • Assumes making codewords shorter is what makes a code prefix-free.