Must symbols be sorted by probability?

No. The standard midpoint construction works with an agreed ordering and positive probabilities. The order changes interval locations and codewords.

Is this the same as Elias gamma coding?

No. Elias gamma is a particular universal integer code. The shared name does not make their input assumptions or constructions identical.

Why retain one more bit than ceil(−log2 p)?

The extra precision ensures that the binary interval identified by the truncated midpoint fits within the symbol's probability interval, yielding a prefix-free code.

AI Glossary / MLOps and deployment / Intermediate

Shannon - Fano - Elias coding

Definition

Shannon - Fano - Elias coding is a prefix-code construction that assigns each symbol a probability interval, takes that interval's midpoint, and represents the midpoint with enough leading binary digits to identify the symbol unambiguously. It connects probability-based symbol coding with the interval ideas used in arithmetic coding.

What it means

Imagine dividing the interval from zero to one into adjacent pieces whose widths equal the symbol probabilities. Each piece belongs to one symbol. A number near the middle of a piece can serve as its address, provided the address retains enough precision to stay safely inside the piece.

Unlike the cumulative Shannon construction, the midpoint method does not require sorting symbols by decreasing probability; it needs an agreed order. The added precision costs an extra bit in the standard length formula. This makes it a useful theoretical construction rather than a guarantee of the shortest possible individual-symbol code.

How it works

For symbol i, let F_i be the sum of probabilities of all earlier symbols in the agreed order. Its interval is [F_i,F_i+p_i), and its midpoint is F_i+p_i/2. Express this midpoint as a binary fraction.

Keep l_i=ceil(−log2 p_i)+1 digits after the binary point. Truncation, rather than arbitrary rounding to a nearby number, defines the codeword. The extra bit makes the associated binary interval narrow enough to lie inside the symbol's probability interval. Since those symbol intervals do not overlap, no codeword is a prefix of another.

The average codeword length is below H+2 bits for a finite positive-probability alphabet, where H is entropy. Encoder and decoder must share the probabilities, ordering and numerical conventions; the mathematical construction alone is not a complete interoperable file format.

Three practical examples

1. Information-theory teaching: interval midpoints provide a geometric explanation of prefix-free coding and of why probability determines useful description length.

2. Arithmetic-coding study: treating whole sequences as outcomes shows how one interval can represent a block. The midpoint construction helps explain a principled way to select a finite binary description inside that interval.

3. Probability-model experiments: a researcher can compare model-derived description lengths across symbol distributions. A deployment experiment must also count model metadata and the cost of reproducing probabilities at the decoder.

Think of it this way

Think of giving directions to the center of a reserved parking space instead of to its boundary. Enough address precision keeps the destination within that space and prevents confusion with the next one.

The analogy is limited: codewords identify binary subintervals, not physical positions. Extra precision has a calculable bit cost, and a wider probability interval represents a more likely symbol rather than a larger real-world object.

Worked example

Use symbols A, B and C in that order, with probabilities 1/4, 1/2 and 1/4. They are deliberately not arranged in decreasing probability order.

A receives [0,0.25), with midpoint 0.125, whose binary expansion is 0.001. Its code length is ceil(−log2(0.25))+1=3, so A→001.

B receives [0.25,0.75), with midpoint 0.5, written as 0.1000… in binary. Its length is ceil(−log2(0.5))+1=2, so B→10. C receives [0.75,1), with midpoint 0.875=0.111 in binary, giving C→111 with length three.

The word BCA becomes 10|111|001. None of the three codewords is a prefix of another. For example, B's two-bit prefix 10 represents binary values in [0.5,0.75), entirely inside B's allotted interval.

Average length is 0.25×3 + 0.5×2 + 0.25×3 = 2.5 bits per symbol. Entropy is 1.5 bits, so this construction uses one extra bit on average. A different prefix code can achieve 1.5 for these probabilities. The calculation illustrates the midpoint construction and its overhead, not an optimality claim.

Illustrative case study

Fictional case: IntervalNote builds an educational coding tool. Its first implementation rounds midpoints using ordinary decimal display precision, then turns the rounded values into binary strings of a fixed length.

The examples look plausible, but they no longer implement the specified code construction. The team changes the tool to calculate the required length for each symbol and truncate the binary fractional expansion consistently. It adds exact rational test cases and checks the prefix property.

The interface then displays the probability interval alongside the narrower binary interval. This fictional case shows why a geometric intuition is helpful, but precise numerical and length rules are still necessary for a correct coding procedure.

Common misconceptions and mistakes

“A distinct midpoint automatically gives a finite prefix code.” Distinct real numbers are not enough. The chosen finite prefixes must retain sufficient precision, which is the purpose of the length rule.

“The extra bit makes this Huffman-optimal.” It provides a simple sufficient construction, not minimum expected length among symbol codes.

“All methods with Shannon and Fano in their names are identical.” Cumulative truncation, recursive splitting and midpoint coding have different rules. State which construction is intended.

“Arithmetic coding is just a huge stored midpoint table.” Practical arithmetic coders update intervals sequentially and manage finite precision. The midpoint concept explains part of the theory, not the entire implementation.

Business use

The main business value of understanding Shannon - Fano - Elias coding is the connection it makes between probability estimates and compact, reversible representations. It helps teams reason about model-based compression without assuming that better prediction automatically supplies a usable byte format.

For any implementation inspired by this idea, define symbol ordering, probability precision, codeword termination and unsupported-symbol handling. Compare complete encoded size and decoding cost with established alternatives. If blocks replace individual symbols, include buffering and model complexity. A simple mathematical bound is useful evidence, but it does not settle latency, interoperability or storage economics.

Check your understanding

Two systems use the same probabilities but different symbol orders. Can they assume their midpoint codewords match?

Answer: No. Ordering changes cumulative interval positions. They must communicate or agree on the order as part of the coding contract.

Related terms

Learn next

Draw probability intervals and their midpoint binary intervals for small alphabets. Then apply the idea to short blocks and study how practical arithmetic coding updates intervals without enumerating a giant table of all possible sequences.

Arithmetic coding

Sources

Primary teaching sources: Carnegie Mellon's “Arithmetic Coding and Universal Codes,” Section 9.2.2: https://www.cs.cmu.edu/~aarti/Class/10704/lec9-arithmeticcoding.pdf ; Stanford Statistics 47N assignment describing the midpoint formula: https://web.stanford.edu/class/stats47n/coursework/assignments/assignment3.pdf . The three-symbol example and fictional tool are original illustrations.

Previous: Shannon - Fano coding Next: Shannon's source coding theorem