skip to content

The source-coding theorem bounds an optimal prefix code's expected length by H <= L < H+1, where H is the source's Shannon entropy in bits - where does that extra bit come from?

level: seniorimportance: should knowfreq 40%

answer

  1. codeword lengths are whole numbers
  2. the ideal length is fractional
  3. rounding up costs something
  4. worst on a very skewed source
  5. content below one bit per symbol

basics

~20 s

From rounding. The ideal length for a symbol of probability p is the generally fractional value log2(1/p), but a codeword is a whole number of bits, so each symbol pays up to one bit of rounding - and at least one bit even when its ideal length is far below that.

solid answer

~50 s

Entropy `H` is an average of the ideal per-symbol costs `log2(1/p)`, and those are almost never whole numbers. A codeword has to be an integer number of bits, so a symbol whose ideal cost is 0.081 bits still occupies at least 1. Rounding each ideal length up gives lengths that satisfy Kraft's inequality and an expected length below `H + 1`, which is where the theorem's upper end comes from; the lower end, `L >= H`, holds for any uniquely decodable code. The gap closes to zero only when every probability is a power of one half. It is worst on very skewed sources: a two-symbol source at 0.99/0.01 has `H` of about 0.081 bits, yet no symbol code beats 1 bit per symbol - more than a tenfold overhead. Coding blocks of symbols together amortises the same single bit over the whole block.

go deeper

for a junior

Hold on to the shape of the result: entropy is the floor in bits per symbol, and a code that emits one whole codeword per symbol can end up to a bit above it.

for a middle

Explain the rounding: the ideal length log2(1/p) is usually fractional, codeword lengths are integers, and rounding each up both satisfies Kraft's inequality and lands under H plus one.

for a senior

Judge the gap against H rather than against zero. One bit is noise at four bits per symbol and a tenfold penalty on a field whose content is a tenth of a bit, and say which restructuring you would reach for.

for a principal

The lead-level view is whether to spend engineering on the coder at all: compare the achievable saving against a cheaper change to the data model or the schema that lowers the entropy itself.

## Two different currencies Shannon entropy `H` measures a source's average content in bits per symbol, as the probability-weighted average of each symbol's ideal cost `log2(1/p)`. That ideal cost is a **real number**. A codeword, by contrast, is a **whole number of bits** - there is no way to write 2.4 bits into a stream with a symbol code that emits one codeword per symbol. The one-bit gap in `H <= L < H+1` is entirely the price of converting one currency to the other. ## Where each end of the bound comes from **The floor, `L >= H`.** No uniquely decodable code has an expected length below the entropy. The reason is the Kraft budget: the lengths must satisfy the sum of `2^-li` at most 1, and given that constraint the expected length `sum(pi * li)` is minimised when `li = log2(1/pi)` exactly, which makes the expected length equal `H`. Any other length assignment is strictly worse. So the floor is not an artefact of a particular scheme - it is what the code space allows. **The ceiling, `L < H + 1`.** Take the ideal lengths and round each one up: `li = ceil(log2(1/pi))`. Two things are true of that choice: 1. It is feasible. Each `2^-li` is at most `pi`, so the sum is at most 1 and Kraft's converse says a prefix code with these lengths exists. 2. It is close. Each `li` is below `log2(1/pi) + 1`, so the weighted average is below `H + 1`. Since this specific code achieves it, the **optimal** code is at least as good, and the strict upper bound follows. Note the direction carefully: the theorem promises the optimum is under `H + 1`; it does not claim the optimum is `H` rounded up, and it says nothing about any particular code you happened to build. ## When the gap is nothing and when it is everything | source | `H` (bits/symbol) | best symbol-code `L` | overhead | |---|---|---|---| | two symbols at 0.5 / 0.5 | 1.0 | 1.0 | 0 | | four symbols at 0.5 / 0.25 / 0.125 / 0.125 | 1.75 | 1.75 | 0 | | three equally likely symbols | about 1.585 | about 1.667 | about 0.08 | | two symbols at 0.99 / 0.01 | about 0.081 | 1.0 | about 0.919 | The pattern in the first two rows is the equality case: **`L = H` exactly when every probability is a power of one half** (a *dyadic* source), because then every ideal length is already a whole number and nothing is rounded. Note that 'equally likely' is only dyadic when the alphabet size is itself a power of two - three equal symbols already lose a little. The last row is the case worth remembering, because it is the one that matters in practice. A field that is almost always the same value carries about 0.081 bits, yet a symbol code must still spend a full bit on every occurrence. The overhead is not one bit in the abstract - it is more than ten times the actual content. This is the standard rebuttal to 'we will just Huffman-code the flags': when per-symbol content drops well below one bit, a one-codeword-per-symbol scheme cannot follow it down. ## What you do about it The wasted bit is a consequence of the **one codeword per symbol** structure, so the ways out change that structure rather than the code: - **Block the symbols.** Treat `k` consecutive symbols as one super-symbol over the product alphabet. The theorem still promises under one bit of overhead, but now over the whole block, so the per-symbol overhead is under `1/k`. The cost is an alphabet that grows exponentially in `k`. - **Leave integer codeword lengths behind.** Coders that spend fractional bits per symbol avoid the rounding entirely; that mechanism is a separate subject from the bound itself. - **Change the model.** If the skew comes from context - this field is almost always the same *given the previous one* - a conditional model lowers `H` itself, which is a different lever from lowering the gap to `H`. ## What an interviewer is checking They want to hear that the extra bit is **rounding a fractional ideal length up to an integer**, not framing, not headers, not a table of codeword lengths in the payload. The strong follow-through is that one bit is negligible when `H` is several bits per symbol and catastrophic when `H` is a fraction of a bit - so the bound alone is not a verdict, and you must compare the gap to `H`, not to zero.

  • When is the expected length exactly equal to the entropy?
    When every symbol probability is a power of one half, so each ideal length log2(1/p) is already a whole number and nothing has to be rounded. A source at 0.5, 0.25, 0.125, 0.125 codes at exactly 1.75 bits per symbol. Equal probabilities qualify only when the alphabet size is a power of two - three equally likely symbols are already non-dyadic and lose a fraction of a bit.
  • Does the H <= L floor apply to codes that are not prefix-free?
    Yes. Every uniquely decodable code satisfies the same Kraft sum bound, by the Kraft-McMillan result, and the floor follows from that bound rather than from the prefix structure. So giving up instantaneous decoding does not let expected length drop below the entropy; it only costs you lookahead.
  • A team reports their coder beats the entropy of their data. What has usually happened?
    The entropy was computed against the wrong model. A figure measured from the marginal symbol frequencies ignores structure the coder is exploiting - repetition, correlation with neighbouring symbols, a restricted value range - so the true conditional entropy of the source is lower than the number they quoted. Other common causes are excluding headers or a shared table from the measured output.
  • Coding two symbols at a time halves the per-symbol overhead. Why not take k much larger?
    Because the alphabet is the product alphabet: k symbols drawn from an alphabet of size m give m to the power k super-symbols, so the code table grows exponentially while the benefit only shrinks as 1/k. The table itself must also be built, stored and often transmitted, so past small k the overhead you added exceeds the fraction of a bit you saved.

saying these in an interview costs you the question

  • Claims an optimal code always reaches the entropy exactly.
  • Says the extra bit is framing, headers or table overhead.
  • Thinks the bound is per message rather than per symbol.
  • Believes a symbol code can go below one bit per symbol on a skewed source.
  • Treats the entropy floor as something a clever code can beat.