1 Basic Concepts of Code Length
1.1 Definition and measurement (symbols vs. bits)
Code length is the number of characters used to represent a message’s symbol or block under a specified coding scheme. If the code alphabet is binary, code length is commonly measured in bits; if the code alphabet has more than two symbols, lengths are typically measured in “code symbols” or “digits” in that alphabet. In many information-theoretic treatments, a consistent base is assumed so that lengths can be compared via logarithms tied to the source and channel assumptions.
In variable-length coding, different source symbols may map to codewords of different lengths, so “code length” often refers to the length associated with a particular symbol, with analysis focusing on statistics such as expected length over the source distribution.
1.2 Codebooks, alphabets, and encoding functions
A codebook specifies the set of codewords available for each source symbol (or each source block). The source alphabet contains the symbols being encoded, while the code alphabet contains the symbols allowed in the transmitted representation. The encoding function maps each source symbol (or block of source symbols) to a codeword drawn from the code alphabet.
When the same encoding method is used repeatedly, the codebook effectively determines the length profile of the resulting stream. In practice, constraints on the encoding function determine whether decoding can be performed unambiguously while reading the stream left-to-right.
1.3 Length of codewords and message-to-code mapping
Let a codeword for a particular symbol be a sequence of code-alphabet symbols; its length is the number of positions in that sequence. The mapping from messages to codewords determines which lengths occur and with what frequencies, influencing the average cost of representing typical messages.
For block encoding, mapping is applied to groups of source symbols. The resulting codeword length can grow with the block length, enabling trade-offs between efficiency and other implementation considerations such as buffering and latency.
2 Code Length in Source Coding
2.1 Average and expected code length
In source coding, code length is evaluated statistically using the probability distribution of the source. The most common metric is the expected code length, computed by weighting each symbol’s codeword length by the probability that the symbol occurs.
Expected length is often the quantity of interest because it corresponds to the average storage or transmission cost under the assumed source model.
2.1.1 Probability-weighted length
If the source emits symbol \(x\) with probability \(p(x)\) and the code assigns a codeword of length \(L(x)\), then the expected code length is \[ \mathbb{E}[L] = \sum_x p(x)\,L(x). \] This formula captures how often each length occurs. In general, variable-length codes reduce expected length by assigning shorter codewords to more probable symbols and longer codewords to less probable ones.
2.1.1.1 Conditional expected length for sources with context
| For sources with memory or when context is available, coding may be performed conditionally on previously observed symbols or on a context variable. If the encoder uses a context \(c\) and assigns code lengths \(L(x | c)\) based on conditional probabilities, the overall expected length becomes an expectation over both context and emitted symbol: |
|---|
\[
| \mathbb{E}[L] = \sum_c p(c)\sum_x p(x | c)\,L(x | c). |
|---|
\] This approach can improve efficiency by tailoring the code to the distribution that actually applies in each context.
2.2 Redundancy and inefficiency
Redundancy measures how far a code’s expected length is from an information-theoretic limit. Even with optimal design under given constraints, expected length may exceed the theoretical ideal due to integrality constraints, finite alphabet effects, and the requirement of decodability.
Inefficiency is often quantified as the gap between expected length and entropy (in the same logarithmic base). The size of the gap indicates how much extra average cost remains after optimization.
2.3 Length variance and tail behavior
Beyond mean performance, the distribution of codeword lengths matters. The variance of length reflects how much code length fluctuates around its average, while tail behavior describes how likely extremely long codewords are.
In practical systems, long tails can create latency spikes. Even if the expected length is good, a small probability of very long codewords can affect buffer sizing, real-time constraints, or error propagation characteristics.
3 Optimal Coding Principles
3.1 Uniquely decodable codes
A code is uniquely decodable if every finite encoded string corresponds to exactly one source message. This property ensures that a decoder can reconstruct the original sequence without ambiguity.
Unique decodability is a general requirement, weaker in structure than prefix-freeness but stronger in effect than allowing arbitrary concatenations. The design goal in many settings is to achieve low expected length among all uniquely decodable codes subject to the decodability constraint.
3.2 Prefix-free codes
A prefix-free (instantaneous) code is one in which no codeword is a prefix of another. This guarantees that decoding can proceed symbol-by-symbol as the stream arrives: once a valid codeword is recognized, the next codeword begins immediately.
Prefix-freeness often simplifies decoding and supports efficient implementation, at the cost of restricting the set of allowed codes relative to general uniquely decodable codes.
3.2.1 Kraft inequality
For a prefix-free code over a code alphabet of size \(D\), the assigned codeword lengths \(l_1,\dots,l_m\) must satisfy Kraft’s inequality: \[ \sum_{i=1}^m D^{-l_i} \le 1. \] Conversely, given lengths that satisfy the inequality, a prefix-free code with those lengths exists (up to assignment details). This provides a characterization that is central for designing optimal prefix codes.
3.2.2 Huffman coding (optimality for prefix codes)
Huffman coding constructs a prefix-free code that minimizes expected code length for a known discrete distribution when lengths are measured in code symbols of the same alphabet as the code. The algorithm repeatedly combines the least probable symbols, producing a tree whose leaf depths yield the codeword lengths.
For fixed code alphabet size, Huffman coding yields optimal average length among all prefix-free codes, making it a standard method in source coding practice.
3.3 Shannon coding and near-optimal length assignments
Shannon-style coding provides a simple way to assign code lengths based on the distribution’s probabilities. A common assignment is to set lengths proportional to \(-\log p(x)\), typically rounded to integers to satisfy coding constraints.
The resulting codes are often near-optimal: their expected length is within a small constant (measured in log units tied to the code alphabet) of the entropy. Such schemes are frequently used when one wants a fast length assignment procedure rather than running a full Huffman optimization.
4 Theoretical Limits and Entropy Links
4.1 Entropy of a discrete memoryless source
Entropy quantifies the uncertainty of a discrete random source. For a memoryless source with distribution \(p(x)\), the entropy \(H\) is \[ H = -\sum_x p(x)\log p(x), \] where the logarithm base determines the unit (e.g., base 2 for bits). Entropy sets a benchmark for the minimum achievable average code length in an idealized sense.
For memoryless sources, entropy governs the fundamental limit on compressibility: no coding scheme can reduce expected length below the entropy when length is measured in compatible units.
4.2 Lower bounds on average code length
Lower bounds formalize the idea that each symbol carries at least a certain amount of information on average, which must be “paid for” by code length under decodability constraints.
4.2.1 Relationship between entropy and expected length
For uniquely decodable codes with lengths measured in code symbols of size \(D\), expected length satisfies bounds of the form \[ \mathbb{E}[L] \ge H_D, \] where \(H_D\) denotes entropy computed with logarithms base \(D\). More refined statements relate the gap between expected length and entropy to properties of the code, including whether the code is prefix-free and how probabilities interact with integer-length assignments.
4.3 Upper bounds and coding gaps
Upper bounds show that practical coding schemes can come close to the entropy limit. The remaining difference is the coding gap, caused by rounding to integer lengths and structural restrictions such as prefix-freeness.
4.3.1 Log-base conventions and normalization
Because entropy and length depend on logarithm base and code alphabet size, comparisons require normalization. If entropy is computed in bits but the code outputs symbols from a \(D\)-ary alphabet, then code lengths correspond to different units; converting between units uses the identity \[ \log_D p = \frac{\log p}{\log D}. \] Correct normalization ensures that bounds are interpreted consistently.
4.4 Asymptotic behavior for long blocks
When coding is extended from single symbols to blocks of \(n\) symbols, the effective uncertainty scales roughly linearly with \(n\) for memoryless sources. In asymptotic regimes, the average length per source symbol can approach the entropy arbitrarily closely for sufficiently large blocks.
This asymptotic closeness reflects that integer-length constraints become less restrictive when operating on large blocks, enabling finer-grained probability matching.
5 Block Codes and Extensions
5.1 Fixed-length vs. variable-length coding
Fixed-length coding assigns the same number of code symbols to every source symbol (or block), which is simple but may waste capacity when the distribution is skewed. Variable-length coding adapts codeword lengths to probability, potentially reducing the average length.
In block settings, a fixed-length scheme at the block level can still outperform fixed-length symbol-by-symbol encoding, because block probabilities combine to produce a more favorable distribution over block types.
5.2 Block coding (n symbols at a time)
Block coding maps sequences of \(n\) source symbols into codewords. The source distribution over length-\(n\) blocks induces a distribution over block “super-symbols,” and optimal or near-optimal coding can be applied to that induced distribution.
5.2.1 Trade-offs between block length and delay
Encoding \(n\) symbols at once introduces delay: the encoder must collect a full block before it can output the corresponding codeword. Larger \(n\) can improve efficiency by enabling better matching between code lengths and block probabilities, but it increases buffering and latency.
Thus, the choice of block length balances compression gains against real-time constraints.
5.3 Typical sequences and practical length guarantees
In many sources, most probability mass concentrates on a set of sequences called typical sequences. Coding schemes can use this structure to guarantee that codeword lengths for typical sequences are close to the length predicted by entropy, while atypical sequences may receive longer codes.
This yields practical assurances: although worst-case lengths can be large, the probability of extremely long encodings becomes small under typicality assumptions.
5.4 Canonical codes and implementation-friendly representations
Canonical codes are standardized forms of code assignments that preserve codeword lengths while imposing a deterministic rule for mapping lengths to specific bit patterns. This makes them convenient for storage and transmission of code descriptions, since only the list of lengths (not the full codebook) may need to be communicated.
Canonical representations support efficient decoders and reduce the risk of inconsistencies across implementations.
6 Code Length Under Constraints
6.1 Finite expected length vs. worst-case constraints
A code may have finite expected length yet still contain arbitrarily long codewords with small probability. This distinction matters when designing for systems that impose hard limits on maximum length.
Analysis often separates average-cost criteria (expected length) from guarantees on the probability of exceeding a length threshold.
6.2 Maximum code length limitations
Imposing an explicit maximum length restricts the set of valid codes, typically increasing expected length relative to unconstrained optimal coding. Designers may treat the maximum length as a requirement and search among codes that satisfy both decodability and length caps.
Such constrained optimization is especially relevant in systems with strict framing or hardware limits.
6.3 Delay constraints in streaming scenarios
Streaming applications require bounds on how quickly the decoder can determine symbol boundaries. For variable-length codes, prefix-free structure is a key enabler, but additional constraints such as bounded lookahead or bounded buffering can further restrict feasible codes.
Designers may need to limit the maximum depth of the prefix tree or ensure that the decoder’s decision latency meets system specifications.
6.4 Alphabet-size effects (code alphabet larger than binary)
Using a code alphabet larger than binary (e.g., ternary, quaternary) can change the relationship between entropy and achievable average length. With a larger alphabet, each code symbol can carry more potential information, which can reduce the number of transmitted code symbols needed.
However, practical considerations such as symbol error rates and hardware representation may counteract theoretical savings, so alphabet-size effects are often treated as part of a broader system design.
7 Special Cases and Examples
7.1 Uniform distributions and constant-length codes
When a source distribution is uniform, all symbols are equally probable. In this case, the entropy is maximized, and there is little benefit to variable-length coding: optimal strategies typically assign equal-length codewords to each symbol.
As a result, constant-length codes arise naturally as optimal or near-optimal solutions under uniformity.
7.2 Highly skewed distributions and long-tail probabilities
When probabilities are highly skewed, coding can assign extremely short codewords to common symbols while allocating longer codewords to rare ones. This can reduce expected length substantially.
The cost is that rare symbols may receive long encodings, producing heavy tails in the length distribution. Such tails influence delay and buffer requirements even if the mean length is small.
7.3 Small toy examples (manual Huffman trees)
For small alphabets, Huffman coding can be demonstrated by hand using a tree construction. The least probable symbols are merged iteratively, and their depths determine code lengths.
These toy examples make clear how probability ordering and rounding to integer depths shape the final expected length and illustrate why Huffman coding is optimal within the class of prefix-free codes.
7.4 Comparing coding schemes by expected length
To compare coding schemes, expected length is computed under the same assumed source distribution and measured in consistent units. A fair comparison requires aligning: (i) the code alphabet size, (ii) whether symbols are coded singly or in blocks, and (iii) whether the scheme is decodability-complete under the decoding assumptions.
Expected length alone may not capture all practical issues, so comparisons often consider variance, tail probabilities, and operational constraints such as latency.