Can a codeword contain a fraction of a bit?

An individual binary codeword has a whole-number length. Fractional average lengths arise by averaging different lengths over many symbols.

It rounds upward to the next integer, leaving an integer unchanged. For example, ceil(2.322)=3.

Why order symbols by probability?

The cumulative-probability construction uses nonincreasing probabilities to obtain its prefix-free assignment. Arbitrarily rearranging the same truncation procedure is not an interchangeable rule.

AI Glossary / MLOps and deployment / Intermediate

Shannon coding

Definition

Shannon coding is a method for constructing a variable-length, prefix-free code from symbol probabilities. In its binary form, a symbol with probability p receives a codeword of length ceil(−log2 p), with codewords obtained from cumulative probabilities in a specified probability order.

What it means

Frequent symbols deserve short descriptions, while rare symbols can take longer ones. Shannon coding makes this principle concrete by rounding each symbol's ideal information amount, −log2 p, upward to a whole number of bits.

The result provides a useful bridge between probability and lossless compression. It is not generally the shortest possible symbol code. Naming also varies across texts: some associate the name Shannon - Fano with several related constructions. Here, Shannon coding means the cumulative-probability construction, distinguished from Fano's recursive probability-splitting procedure and Shannon - Fano - Elias coding.

How it works

List symbols in nonincreasing probability order, using a consistent tie rule. For each symbol, compute the cumulative probability of all symbols preceding it. Write that cumulative value as a binary fraction, and take the first ceil(−log2 p) fractional bits as its codeword.

Under these conditions, the resulting code is prefix-free: no complete codeword starts another. The decoder can therefore recognize symbols by following the agreed code tree. Probabilities must be positive for symbols assigned codewords; unseen symbols need an explicit modeling or escape policy.

The expected length L satisfies H≤L<H+1 for the usual nondegenerate finite source, where H is its entropy in bits. This bounds average codeword length under the design probabilities, excluding any cost of communicating the codebook or framing messages.

Three practical examples

1. Compression education: a learner can calculate ideal information amounts, round them to integer lengths, and see how a concrete prefix code relates to entropy.

2. Small symbolic streams: an engineer can construct a simple probability-based baseline for event identifiers, then compare its complete encoded size with fixed-width or Huffman alternatives.

3. AI probability evaluation: a researcher can illustrate how predicted probabilities influence description lengths. Turning a model into a practical codec also requires synchronized probability calculations and a defined treatment of unsupported symbols.

Think of it this way

Think of allocating numbered lockers with shorter addresses for frequently used items. Probabilities determine the desired address lengths, and a careful construction ensures no short address is confused with the beginning of a longer one.

The analogy is limited: codewords are bit strings, and the efficiency guarantee concerns a probability-weighted average. A rare item can have a long address, and the construction need not minimize the total address length as well as another coding method.

Worked example

Take symbols A, B, C and D with probabilities 0.4, 0.3, 0.2 and 0.1. They are already in decreasing order. Their ideal information amounts are approximately 1.322, 1.737, 2.322 and 3.322 bits, giving rounded lengths 2, 2, 3 and 4.

The cumulative probabilities before the symbols are 0, 0.4, 0.7 and 0.9. Taking the required leading binary fractional bits gives A→00, B→01, C→101 and D→1110. None of these codewords is a prefix of another.

For example, CAD becomes 101|00|1110, or 101001110. A decoder following the code tree recovers C, then A, then D without needing a separator between them.

The expected codeword length is 0.4×2 + 0.3×2 + 0.2×3 + 0.1×4 = 2.4 bits per symbol. The entropy is about 1.846 bits, so the difference is approximately 0.554, below one bit as expected.

Nevertheless, four symbols fit a fixed-width two-bit code, which is shorter on average here. This example deliberately shows that the Shannon bound is not a promise to outperform every simple alternative for every distribution.

Illustrative case study

Fictional case: EventRibbon uses a small probability table to build a Shannon code for four event types. The team expects the unequal probabilities to guarantee savings over fixed-width identifiers.

Its first calculation reveals that rounding lengths upward produces a larger average than the two-bit baseline. The team compares Huffman coding and block-based approaches, counting codebook overhead and decoding complexity as well as payload bits.

It keeps the Shannon construction as a transparent teaching and validation baseline. This fictional case illustrates the difference between a provable distance from an information-theoretic limit and the best operational choice for a small alphabet.

Common misconceptions and mistakes

“Rounded information lengths alone define the bit patterns.” They define lengths. A valid assignment such as the cumulative construction is still needed to obtain decodable codewords.

“Shannon coding is Huffman coding.” Both can produce prefix codes, but use different constructions. Huffman optimizes expected length among binary prefix symbol codes for the given probabilities.

“The expected-length bound applies unchanged to different traffic.” It is computed using the assumed distribution. Changed symbol frequencies alter realized average length.

“A prefix code detects every corrupted bit.” Prefix freedom solves boundary ambiguity for intact strings. Error detection and correction require separate provisions.

Business use

Shannon coding is useful for understanding and checking probability-based representations. A business comparing compressors should treat it as one candidate or conceptual baseline, then measure full storage or transfer cost on representative traffic.

Specify the symbol alphabet, probability estimation, ordering and codebook distribution. If symbols are grouped into blocks, account for a larger alphabet and longer buffering delay. If an AI model supplies probabilities, include prediction cost and reproducibility. A mathematically short description is useful only when the receiving system can reconstruct exactly the same coding decisions.

Check your understanding

A Shannon code has average length 2.4 bits for four symbols. Is a fixed-width two-bit code impossible because the Shannon construction is near entropy?

Answer: No. Near-entropy does not mean optimal. The four-symbol fixed-width code can be valid and shorter for that distribution.

Related terms

Entropy
Prefix code
Shannon - Fano coding
Shannon - Fano - Elias coding
cumulative probability
Huffman coding
source coding theorem

Learn next

Practice converting cumulative probabilities into binary fractions, then compare Shannon and Huffman lengths on the same distribution. Next study block coding to see how rounding overhead can be spread over multiple source symbols.

Sources

Primary teaching material: Gadiel Seroussi and Marcelo Weinberger, “Lossless Source Coding,” includes the cumulative Shannon construction and its length bound: https://www.cs.purdue.edu/homes/spa/courses/msri04/data_comp_part1.pdf . The probability table, worked message and fictional scenario here are original illustrations.

Previous: Shampoo optimizer Next: Shannon - Fano coding