Which test tells you whether a prefix code exists with codeword lengths of 1, 2, 3, 3 and 3 bits?
answer
- lengths are a budget
- each codeword claims a share
- sum two to the minus length
- one is the whole code space
- over one means impossible
basics
~20 sKraft's inequality: sum two to the minus each codeword length and compare with 1. For 1, 2, 3, 3 and 3 that sum is 1.125, above the budget, so no prefix code has those lengths.
solid answer
~50 sKraft's inequality says a prefix code with lengths `l1..ln` exists **if and only if** the sum of `2^-li` is at most 1. Think of it as a budget: the whole code space is 1, and a codeword of length `l` claims the fraction `2^-l` of it, because choosing it forbids every string that extends it. Here the sum is `1/2 + 1/4 + 1/8 + 1/8 + 1/8 = 1.125`, which overspends, so those lengths are impossible - no cleverness in assigning the bits will help. Lengths 1, 2, 3, 4, 4 sum to exactly 1 and are realised by `0`, `10`, `110`, `1110`, `1111`. The inequality is a **feasibility** test, not an optimality test: it says whether a code shaped like that can exist, never whether it is a good code for your data.
code
pseudocode · 16 linestotal = 0
for each length l in lengths:
total = total + 2^(-l)
if total > 1:
reject "no prefix code has these lengths"
// converse: the bound holds, so build one
sort lengths ascending
code = 0
prev = first length
for each length l in lengths:
code = code shifted left by (l - prev)
emit codeword = code written in exactly l bits
code = code + 1
prev = lgo deeper
Remember the shape of the test: add up two to the minus each codeword length; at most 1 means such a prefix code can exist, above 1 means it cannot. The arithmetic is halves, quarters and eighths.
Explain why a codeword of length l claims exactly the fraction two to the minus l - it reserves the whole subtree below it - and state the converse, that any list meeting the bound can actually be built.
Use it as a review reflex on a proposed encoding, and read the leftover budget: slack means either a codeword that could be shorter or deliberate room for symbols not defined yet.
The call is what to do with the slack across a format's lifetime: spending the budget to the last leaf buys bits today and makes every future symbol a change to existing codewords.
## The code space is a budget Every prefix code lives in a binary tree: `0` goes left, `1` goes right, and every codeword occupies a leaf. Picking a codeword of length `l` does not just consume one node - it **consumes the whole subtree beneath it**, because any longer string starting with those bits would violate the prefix property. That subtree is the fraction `2^-l` of the tree. So a code's lengths are a spending plan, and the total budget is 1. That is exactly **Kraft's inequality**: > A prefix code over a binary alphabet with codeword lengths `l1, l2, ..., ln` exists **if and only if** the sum of `2^-li` over all codewords is less than or equal to 1. Both directions matter, and interviews ask for both: - **Necessity.** Any prefix code's lengths satisfy the sum bound - the reserved subtrees are disjoint, so their fractions cannot total more than the whole tree. - **Sufficiency (the converse).** If a length list satisfies the bound, some prefix code with exactly those lengths can be built. The construction is mechanical: sort the lengths ascending and hand out codewords in order, shifting the running counter left as the required length grows. ## Working the proposed vector Lengths 1, 2, 3, 3 and 3 give: | length | claim `2^-l` | running total | |---|---|---| | 1 | 0.5 | 0.5 | | 2 | 0.25 | 0.75 | | 3 | 0.125 | 0.875 | | 3 | 0.125 | 1.0 | | 3 | 0.125 | **1.125** | The fourth codeword exhausts the budget; the fifth has nowhere to live. Concretely, spending `0` on the first tag kills half the tree, `10` kills half of what remains, and the depth-3 layer beneath `11` holds only two leaves - `110` and `111` - not the three the vector asks for. The vector is **impossible**, not merely awkward, and no ordering, renaming or bit-flipping rescues it. The cheapest repairs are to lengthen one of the depth-3 codewords to 4 bits (giving 1, 2, 3, 3, 4 with sum 1.0) or to push the whole shape down (1, 2, 3, 4, 4, also exactly 1.0, realised as `0`, `10`, `110`, `1110`, `1111`). ## Slack, and what an unused leaf means When the sum comes out **below** 1, the code is *incomplete*: part of the tree is unclaimed. Take `00`, `01`, `10`, `110` - lengths 2, 2, 2, 3, summing to `0.25 + 0.25 + 0.25 + 0.125 = 0.875`. The missing `0.125` is one whole depth-3 leaf, `111`, sitting unused. Slack is a fact with two readings: 1. **As waste.** Some codeword could have been one bit shorter for free. An optimal code for a given source never leaves slack - if it did, shortening a codeword would lower the expected length without breaking the prefix property. 2. **As room.** An unclaimed leaf is exactly where a future symbol can be added without touching any existing codeword. A code whose sum is exactly 1 is **complete**, and adding anything to it forces an existing codeword to grow. ## What the inequality does not tell you This is where candidates overreach. Kraft's inequality is about **shape**, and it knows nothing about your data: - It does not say the lengths are good. Lengths 1, 2, 3, 4, 4 are feasible whether or not the first symbol is the most common one; assigning short codewords to frequent symbols is a separate question about the source. - It does not distinguish a code from a permutation of it. Feasibility depends only on the multiset of lengths. - It says nothing about error detection or synchronisation after a corrupted bit. - It is not restricted to prefix codes. In the stronger form usually credited as the **Kraft-McMillan inequality**, the same bound is satisfied by *every* uniquely decodable code - which is why abandoning the prefix property cannot buy shorter codewords. ## Using it in an interview The useful move is to treat the inequality as a fast reality check on a proposed encoding. Someone claims a tag scheme with a 1-bit common tag and several 3-bit rare ones; you sum `2^-l` on the whiteboard and either find the design is impossible, or find leftover budget and ask what it is being saved for. Both outcomes are concrete, and both take about ten seconds.
- The sum comes out at 0.875 rather than 1. What is the code missing, and is that a defect?The missing 0.125 is one unused depth-3 leaf. As a code for a fixed symbol set it is wasteful, because some codeword could be shortened by a bit at no cost, so an optimal code never leaves slack. As an evolving encoding it is deliberate: that free leaf is where a new symbol can be added without lengthening anything already deployed. Which reading applies depends on whether the alphabet is closed.
- Does satisfying Kraft's inequality mean the lengths are the right ones for your data?No. The inequality is purely a feasibility test on the multiset of lengths - it tells you a prefix code of that shape exists and nothing more. Whether those lengths are good depends on the symbol probabilities, since expected length is the sum of probability times length; matching short codewords to frequent symbols is a separate construction step.
- Does the same bound apply to codes over an alphabet with more than two symbols?Yes, with the base changed: for a code over `D` output symbols the sum of `D^-li` must be at most 1, for the same reason - a codeword of length `l` reserves the `D^-l` fraction of a `D`-ary tree. Binary is just the case `D = 2`, and the if-and-only-if structure, including the construction in the converse, carries over unchanged.
saying these in an interview costs you the question
- Treats the inequality as a test of whether a code is optimal.
- Thinks a sum below one means the lengths are invalid.
- Reads a sum of exactly one as a violation of the bound.
- Believes any length vector works if you assign the bits cleverly.
- Applies the check only after building a code, never to a proposal.