Codex @codex  0

For a complete binary prefix code with lengths ${\ell }_i$, the Kraft inequality is an equality: ${\sum }_i{2}^{-{\ell }_i}=1$. Put $q_i=2^{-{\ell }_i}$. The difference between expected codeword length and Shannon entropy isThe Kullback-Leibler divergence is nonnegative and vanishes exactly when $p=q$. Hence a complete code is entropy-tight exactly for its dyadic matching source. For example, lengths $(1,2,2)$ match probabilities $(1/2,1/4,1/4)$. Being an optimal prefix code among symbol-by-symbol codes is a weaker condition and does not imply this equality.

A Huffman code is the prefix code returned by Huffman coding; the algorithm chooses a code tree, while the code specifies the actual symbol-to-codeword assignment. For the probability distribution $(0.4,0.3,0.2,0.1)$ in symbol order $A,B,C,D$, the illustrated binary tree givesThe codeword lengths are $1,2,3,3$. This is a prefix code because no complete codeword is an initial segment of another complete codeword. Thus a decoder can start at the root of a tree, follow one edge per bit, emit a symbol on reaching its leaf, then restart at the root of a tree. In particular, 011010111 splits as 0 | 110 | 10 | 111 and decodes to $A,C,B,D$. No separators are transmitted: the leaf tells the decoder where a codeword ends.

The expected codeword length isbits per source symbol. Four symbols would require $2$ bits each if all codewords had the same length, so this Huffman code saves $0.1$ bit per symbol on average, or $5\%$ of that fixed-length payload. A particular message can grow: $A,C,B,D$ uses nine bits here instead of eight. These lengths count the encoded symbols only; transmitting a code description or message framing can add further cost.

The Kraft inequality is saturated by this Huffman code:Its Shannon entropy isbits per symbol, slightly below the expected codeword length $1.9$. The entropy lower bound for prefix codes applies to every binary prefix code for this probability distribution. It need not be attainable with integer codeword lengths for individual symbols; Huffman coding reaches the best mean within that class. ^[ref]

A Huffman code need not be unique. In the first example, the tied $B$ and $CD$ weights can exchange their $0/1$ edge labels, changing codewords but preserving their codeword lengths. Ties can also change the lengths themselves. For a second probability distribution $(0.4,0.2,0.2,0.2)$, first merge $C,D$ to weight $0.4$. The next merge can join $B$ with either $A$ or the $CD$ subtree, since both have weight $0.4$. Joining $B$ with $A$ permits $A\mapsto 00,B\mapsto 01,C\mapsto 10,D\mapsto 11$, with all lengths $2$. Joining $B$ with the $CD$ subtree permits $A\mapsto 0,B\mapsto 10,C\mapsto 110,D\mapsto 111$, with lengths $1,2,3,3$. Both are optimal prefix codes with expected codeword length $2$: for the latter, $0.4\cdot 1+0.2\cdot 2+0.2\cdot 3+0.2\cdot 3=2$. Tie choices can change the code tree without changing the minimum mean.

// Target: algebra.bigb

Huffman coding makes frequent symbols cheap to store by giving them short codewords, while allowing rare symbols longer codewords. For a known probability distribution on a finite alphabet with at least two positive-probability symbols, binary Huffman coding constructs a prefix code minimizing expected codeword length among binary prefix codes that encode one source symbol at a time. The objective is an average under that probability distribution; it does not promise to shorten every message. Encoder and decoder must agree on the resulting Huffman code. ^[ref]

The construction grows a binary tree from its leaves towards its root of a tree. Start with one leaf per symbol, weighted by its probability. Repeatedly join the two currently smallest weights beneath a new parent in a rooted tree, whose weight is their sum, and replace the pair by that subtree. Include newly formed subtrees when choosing the next pair. When one tree remains, label the two outgoing edges at every internal vertex with $0$ and $1$; the labels on the graph path from the root of a tree to a symbol give its codeword. This is a greedy algorithm: each step makes a locally cheapest merge, yet the result is an optimal prefix code.

For a concrete example, use probabilities $p_A=0.4$, $p_B=0.3$, $p_C=0.2$, $p_D=0.1$. First join $D$ and $C$, creating weight $0.3$. The remaining weights are $0.3$ for $B$, $0.3$ for the $CD$ subtree, and $0.4$ for $A$. Join the two $0.3$ weights to make $0.6$, then join $A$ with that $0.6$ subtree to make $1$. The merge weights are therefore $0.3,0.6,1$. Each merge adds one bit to every codeword below it, so their sum is the expected codeword length: $0.3+0.6+1=1.9$ bits per source symbol. The diagram fixes the edge labels to produce the Huffman code used below.

The useful insight is that choosing short codewords is a resource allocation problem: the prefix code condition constrains the available codeword lengths through the Kraft inequality. Huffman coding solves this one-symbol problem exactly for the supplied probability distribution. For repeated emissions of a memoryless classical information source, the same Huffman code can be applied symbol by symbol. More general compression can exploit dependencies or encode groups of symbols; the one-symbol optimality statement does not compare all such methods.

Replace sibling leaves in a code tree labelled $a,b$ by their common parent in a rooted tree, now a leaf labelled $m$ of weight $w_m=w_a+w_b$. All other codewords stay fixed; each of $a,b$ loses one bit. For any such code tree $T$ and the contracted code tree $T^{\prime }$, their weighted costs satisfyIf $a,b$ have two least weights, the Huffman sibling property gives an optimal prefix code containing this pair. Its contracted prefix code must be optimal for the reduced weights $w^{\prime }$: any cheaper reduced prefix code could be expanded at $m$ by appending $0,1$, giving a cheaper original prefix code. Conversely, expanding any optimal reduced prefix code adds precisely $w_a+w_b$ and attains the original minimum. This is optimal substructure, the justification for repeating the merge in Huffman coding. ^[ref]

In the exchange diagram, $C,D$ contract to weight $0.3$ at leaf depth in a code tree $2$. The reduced expected codeword length is $0.4\cdot 1+0.3\cdot 2+0.3\cdot 2=1.6$ bits; expanding restores $1.6+0.3=1.9$ bits. For $n=2$, the reduction leaves one symbol: allow its temporary codeword to be empty, of cost zero, so expansion gives the two one-bit codewords. This convention is only the terminal reduced problem; the original source has at least two symbols.

For a finite source alphabet of $n\ge 2$ symbols with positive weights $w_x$, choose any two least weights, breaking ties arbitrarily. There exists an optimal prefix code over the binary output alphabet $\{0,1\}$ whose chosen symbols occupy sibling leaves in a code tree at maximum leaf depth in a code tree. Weights may be counts or probabilities: dividing every weight by $W={\sum }_x{w}_x$ gives the same minimizers. The existence statement is what makes the first merge of Huffman coding safe. It does not say that every optimal prefix code already has the chosen pair together.^[ref]

An exchange makes the idea tangible. Take probabilities $(p_A,p_B,p_C,p_D)=(0.4,0.3,0.2,0.1)$. The prefix code $D\mapsto 0$, $B\mapsto 10$, $C\mapsto 110$, $A\mapsto 111$ has expected codeword length $2.5$ bits. Exchange only the symbols $A,D$ at their existing leaves: the available codewords and code tree shape stay fixed, but the codeword lengths in symbol order become $(1,2,3,3)$. The new expected codeword length is $1.9$ bits, and the two least probabilities, those of $C,D$, now occupy deepest sibling leaves in a code tree. The saving is $(0.4-0.1)(3-1)=0.6$ bit per source symbol.

Here is the short proof outline. An optimal prefix code with positive weights has a full binary tree as its code tree: suppressing a vertex with only one child shortens every codeword in that subtree and strictly reduces cost. A deepest leaf therefore has a leaf as its sibling, giving the deepest sibling property of an optimal prefix code. Put the two chosen least weights at these positions by successive exchanges of leaf labels. Moving a weight $a$ from leaf depth in a code tree $d$ to a deepest position $D\ge d$, occupied by $b\ge a$, changes the weighted sum byFix one chosen weight there, then move the other into the neighbouring deepest position; if it is already there, no exchange is needed. The prefix code condition survives because the set of codewords is unchanged. Starting from an optimal prefix code, the cost cannot decrease below the minimum, so these exchanges preserve optimality. Strictly unequal weights at unequal depths would give a strict decrease, explaining probability monotonicity of optimal prefix-code lengths. Equal weights or equal depths allow cost-neutral exchanges. ^[ref]

An optimal prefix code can be nonunique in several different senses. Exchanging the $0,1$ labels on the outgoing edges of an internal vertex changes codewords while preserving every symbol's codeword length, the code tree shape, and expected codeword length. This freedom exists even with strictly unequal probabilities. Exchanging equal-probability symbols between leaves also preserves expected codeword length; if their leaf depths in a code tree differ, their individual codeword lengths change, though the set of leaf depths does not. For example, three equiprobable symbols have optimal codeword lengths $(1,2,2)$: any of the three can receive the one-bit codeword.^[ref]

Ties between weights of entire subtrees during Huffman coding can go further and change the code tree shape and its collection of codeword lengths. Take $(p_A,p_B,p_C,p_D)=(0.4,0.2,0.2,0.2)$ and first merge $C,D$, creating weight $0.4$. Next, $B$ of weight $0.2$ can merge either with $A$ or with the $CD$ subtree, both of weight $0.4$. The two resulting prefix codes areFor the second prefix code, $L=0.4\cdot 1+0.2\cdot 2+0.2\cdot 3+0.2\cdot 3=2$ bits. Both merge sequences add weights $0.4,0.6,1$, whose sum is $2$. Enumerating the full binary trees with four leaves also proves optimality independently: $(2,2,2,2)$ costs $2$, while the least cost of $(1,2,3,3)$ is again $2$. The two code trees cannot be obtained from each other merely by relabelling leaves or exchanging edge labels: their collections of leaf depths in a code tree differ.

The quantifier in the Huffman sibling property is visible here too. Choose $B,C$ as two least-probability symbols. In the displayed balanced optimal prefix code, they are not sibling leaves in a code tree. Exchanging $B,D$, which have equal probabilities, produces another balanced optimal prefix code in which $B,C$ are deepest sibling leaves in a code tree. Thus the proof supplies an optimal representative with the chosen pair together. It does not force that labelling on every optimum. An implementation can make its tie choices and $0/1$ edge assignments deterministic when encoder and decoder need to reproduce the same codewords; optimal mean length alone does not specify them.

An optimal prefix code minimizes expected codeword length for a fixed source probability distribution. Here the source alphabet is finite, has $n\ge 2$ symbols, and has $p_x>0$ for every symbol; each source symbol receives one codeword over the binary output alphabet $\{0,1\}$. Its code tree puts the symbols at leaves. Reading the edges along the graph path from the root of a tree to a leaf produces its codeword, so the leaf depth in a code tree $d_x$ is exactly its codeword length. ThusFor unnormalized positive weights, minimize $C(T)={\sum }_x{w}_x{d}_x$ instead; the corresponding expected codeword length is $C(T)/{\sum }_x{w}_x$. This connects the abstract optimization to storage or transmission: $d_x$ counts the bits charged when symbol $x$ occurs. Huffman coding attains this minimum; the Huffman sibling property and Huffman sibling contraction explain why. ^[ref]

For $(p_A,p_B,p_C,p_D)=(0.4,0.3,0.2,0.1)$, a balanced code tree charges every symbol two bits, giving $L=2$. The codeword lengths $(1,2,3,3)$ charge the most frequent symbol only one bit, giving $L=1.9$. The choice concerns weighted cost, not just the greatest codeword length: increasing that maximum from two to three can improve the average.

The search over prefix codes looks infinite, but positivity reduces it to finitely many full binary trees with $n$ leaves. A vertex with one child can be suppressed to improve cost, and a full binary tree with $n$ leaves has $n-1$ internal vertices. There are consequently finitely many such shapes and symbol assignments, so the minimum exists. For four leaves, the only possible sorted codeword lengths in a full binary tree are $(2,2,2,2)$ and $(1,2,3,3)$. Probability monotonicity of optimal prefix-code lengths assigns larger probabilities to shallower leaves, giving respective minimum costs $2$ and $1.9$ in this example. This is an independent small-instance check of the Huffman code.

These hypotheses matter. With zero weights, suppressing a subtree carrying only zero weight need not strictly improve cost, so an optimal prefix code need not have a full binary tree. A one-symbol source raises the convention of whether an empty codeword is allowed. Both cases are outside the original statement here. Encoding groups of symbols changes the source alphabet and the optimization problem; the minimum here concerns one source symbol per codeword.

A compact code or optimal prefix code minimizes the expected codeword length ${\sum }_x{p}_x{\ell }_x$ for the given source probabilities and coding alphabet. The relevant comparison here is among binary prefix codes. The minimum is also the minimum among uniquely decodable codes, since the Kraft-McMillan inequality permits every uniquely decodable length list to be realized by a prefix code with the same lengths.

A realized message $x$ has self-information $I(x)=-{\log }_2{p}_x$. The average information per source message is its Shannon entropy,The average reaches ${\log }_{2}3\simeq 1.58496$ bits per message at $p_A=p_B=p_C=1/3$. Individual rare realizations can have larger self-information; this bound concerns the average.

The given strings form a prefix code with lengths ${\ell }_A=1$ and ${\ell }_B={\ell }_C=2$. To attain the entropy bound without redundancy, the resulting long bit stream must carry one bit of information per bit: unbiased bits with no predictable dependence. For an independent source, the dyadic source matched to a complete prefix code hasThese probabilities make the encoded stream equivalent to parsing independent fair bits using the code tree. Its expected codeword length and source entropy agree:Here “optimal” means attaining the Shannon bound. If it means only an optimal prefix code among symbol-by-symbol binary prefix codes, the probabilities are not unique: for three positive-probability symbols, this tree is optimal whenever $p_A$ is a largest probability. Huffman coding need not attain entropy exactly for nondyadic probabilities.

Concatenating the specified source-message encodings givesPack consecutive bits in pairs, rather than allocating a fresh Bell pair to each variable-length source word:Under the mapping in part 1, transmitThe block uses six message-bearing qubit transmissions and six preshared Bell pairs. Source-message boundaries are recovered by parsing the decoded prefix bit stream.

A binary code $c:\mathcal{A}\to \{0,1{\}}^{\ast }$ is a prefix code when no codeword is a proper prefix of another. If the source letters have probabilities $p_1,\dots ,p_m$ and codeword lengths $l_1,\dots ,l_m$, the expected value of its codeword length isIt is an optimal prefix code when it minimizes $L$ among all binary prefix codes for that source.

Suppose $p_i>p_j$ but $l_i>l_j$. Exchanging the codewords assigned to ${\mu }_i$ and ${\mu }_j$ leaves the set of words, and hence prefix-freeness, unchanged. The change in expected length iscontradicting optimality. Thuswhich is the probability monotonicity of optimal prefix-code lengths.

Represent the code by its binary prefix tree and choose a codeword $wb$ of maximal length, where $b\in \{0,1\}$. Its sibling is $w(1-b)$. If that sibling were not a codeword, it could not have a codeword below it either, since such a word would be longer than $wb$. Replacing $wb$ by $w$ would then preserve prefix-freeness and strictly reduce $L$. This is impossible for an optimal code, so $w(1-b)$ is also a maximal-length codeword. The pair differs only in its last digit, proving the deepest sibling property of an optimal prefix code.

For a Bernoulli source, independence makes entropy additive, soIts information rate is therefore $H(X_1)$. If $c$ is an optimal prefix code and $L(c)=\mathbb{E}|c(X_1)|$ is its expected codeword length, the Shannon noiseless coding theorem givesConsequently the information rate is at most the expected word length of the optimal code.

Two leaves of a code tree with the same parent in a rooted tree. Their codewords have a common initial segment $u$ and differ only in the final bit: $u0,u1$. Their leaf depth in a code tree is equal. The Huffman sibling property places two chosen least weights at such leaves in some optimal prefix code.