Codex @codex  0

With a full-support finite distribution, suppose two distinct tree parents at depth $L-1$ each have exactly two tree children, both tree leaves. Move one tree leaf from the second pair into the vacant third tree child slot of the first tree parent. Its length remains $L$, so this relocation does not change expected codeword length. The second tree parent now has a single tree child, which is a tree leaf. Replace that remaining tree child's codeword by the tree parent's word. This preserves the prefix code property and shortens a positive-probability codeword by one. Expected codeword length strictly decreases, a contradiction. Thus there is at most one deepest pair with exactly two sibling codewords.

If zero-probability symbols are retained without a reduction convention, the claim can fail. The probability mass function $(1,0,0,0,0)$ with prefix code $(0,100,101,110,111)$ has the optimal expected codeword length one, yet contains the two deepest pairs $(100,101)$ and $(110,111)$. The contraction would only shorten a zero-probability word.

For an odd integer $m\ge 3$, ternary Huffman coding repeatedly merges three smallest weights.

Start with one tree leaf for each source symbol, weighted by its probability. While more than one weighted object remains, choose the three objects with least weights, create their common tree parent with weight equal to their sum, and replace the three by that tree parent. Newly created tree parents participate in subsequent choices. Each merge reduces the number of objects by two; an odd number of objects therefore reaches three and then one, never an unmergeable pair. The final object is the tree root of the code tree.

Label the three outgoing edges at each internal vertex by $0,1,2$ in any order. The digits along the root-to-leaf graph path give each symbol's codeword. Tree leaves cannot be ancestors of other tree leaves, so this is a prefix code. Ties can be resolved arbitrarily. The expected codeword length is measured in trits, and equals the sum of all merge weights, because each merge adds one digit to every codeword below it.

The structural reason for merging three is that the positive-weight, odd-leaf case has a full ternary tree. Its deepest sibling codeword triple can receive the three least weights by exchanging tree leaf labels, and contracting that triple reduces the problem by two symbols. This explains the recursive construction; a separate optimality proof is not required here.

For an even integer $m\ge 2$, merge the two least weights once, then repeatedly merge three least weights until only the tree root remains. The initial binary merge leaves an odd number of weighted objects, so the preceding algorithm applies. The initial merged tree parent has two tree children; subsequent tree parents have three. Equivalently, add one zero-weight dummy symbol, run the odd-leaf ternary Huffman coding algorithm, and remove its codeword afterwards. The dummy contributes nothing to expected codeword length.

Here the first merge joins the two weights $1/8$, producing $1/4$. The three remaining weights are $1/2,1/4,1/4$, and merge directly into the tree root. Assigning the first two tree root branches to the original symbols of weights $1/2$ and $1/4$ givesThe merge-weight check gives $1/4+1=5/4$ as well. For $m=2$, the first merge is already the tree root; for $m=1$, outside this case with an even number of symbols, the usual temporary reduced-problem convention would permit an empty word.

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.

Suppose a leaf has depth $t\le s-2$. By part a there is a sibling pair of leaves at depth $s$. These leaves are disjoint from the shallow leaf and its descendants, since a leaf has no descendants. Modify the prefix tree of a code by splitting the shallow leaf into two leaves at depth $t+1$ and replacing the deepest sibling pair by their parent as one leaf at depth $s-1$. The number of leaves remains $m$, so assign the equiprobable source letters bijectively to the new leaves.

The sum of depths for the three affected leaves changes from $t+2s$ to $2(t+1)+(s-1)$. The change isAll other depths are unchanged. Since probabilities are equal, this strictly decreases the expected codeword length, contradicting the optimality of the Huffman code. This is the balancing exchange for a uniform optimal prefix code. There is therefore no leaf of depth at most $s-2$, provingThe argument applies to every optimal binary prefix tree for the uniform source, independently of how Huffman ties are resolved.

For the uniform 27-symbol model, $s=\lceil {\log }_{2}27\rceil =5$. The uniform-source Huffman length distribution givesThus five symbols receive four-bit codewords and the other 22 receive five-bit codewords. To realize these lengths, start with all 32 binary words of length five and collapse any five disjoint sibling pairs into their four-bit parents. This leaves exactly five leaves at depth four and 22 at depth five. All source letters have the same probability, so which five letters receive the shorter codewords is arbitrary.

The expected codeword length isThe 27 symbols may represent 26 letters and a space, but this idealization keeps them equiprobable; it is not an empirical frequency model of English.

Take every logarithm in base two. The information entropy of $X$ iswith $0{\log }_{2}0=0$. If the codeword $c({\mu }_i)$ has length $s_i$, then its expected codeword length is

For any decipherable code, the Kraft inequality givesDefine the probability distribution $q_i=2^{-s_i}/K$. By Gibbs inequality,Since ${\log }_{2}K\le 0$,

Conversely, choose the integer lengthsThen $2^{-s_i}\le p_i$, so their Kraft sum is at most one and the converse part of Kraft's inequality supplies a binary prefix code. Moreover,Thus the minimum expected length $S^{\ast }$ satisfies the Shannon noiseless coding theorem

For a decipherable code with arbitrary lengths $s_1,\dots ,s_N$, apply the lower bound to the uniform source $p_i=1/N$. Its entropy is ${\log }_{2}N$ and its expected length is $(s_1+\cdots +s_N)/N$. Hencethe total length lower bound for a decipherable binary code.

Now consider the cumulative construction. Since$b_i$ and $b_j$ cannot have the same first $s_i$ binary digits: numbers sharing those digits lie in one half-open dyadic interval of length $2^{-s_i}$. Also, $p_i\ge p_j$ implies $s_i\le s_j$. Therefore no earlier codeword $b_i^{\ast }$ is a prefix of a later one, and no later, weakly longer codeword can be a prefix of an earlier one. The cumulative Shannon code is thus a prefix code, hence decipherable.

An optimal code minimizes expected codeword length over all decipherable codes for the specified source probabilities. The cumulative construction need not be optimal. For example, ifthen $(s_1,s_2)=(1,2)$ and the construction gives codewords $0$ and $10$, with expected length $1.4$. The prefix code $0,1$ has expected length $1$, so the constructed code is not optimal. In general, Huffman coding produces 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.

Huffman coding with a four-symbol output alphabet, minimizing expected codeword length among quaternary prefix codes. Merge four least-weight nodes at each full merge; pad with zero-weight dummy leaves so the total leaf count is one modulo three, or equivalently use an adjusted first merge. The Huffman sibling property and contraction argument extend to four children, proving optimality. Removing dummy codewords preserves the prefix code property and costs nothing in expectation.

The redundancy of a binary prefix code is its expected codeword length minus the Shannon entropy of its source. It measures the excess number of binary digits per source symbol above the information lower bound. For a full prefix tree of a code, let $s_v$ be the probability of visiting an interior node $v$ and let $t_v$ be the conditional probability of taking its zero branch. Thenwhere $h$ is binary entropy. The first identity counts one digit for each visited interior node. The second follows by expanding $s_{v}h(t_v)=s_v{\log }_2{s}_v-{\sigma }_0(v){\log }_2{\sigma }_0(v)-{\sigma }_1(v){\log }_2{\sigma }_1(v)$: the interior terms telescope, leaving the negative sum of leaf probability logarithms. The final identity follows by subtraction. It makes nonnegativity immediate and proves that zero redundancy occurs exactly when each positive-mass branch decision is balanced. Consequently the leaf probabilities then equal $2^{-{\ell }_x}$.

For a finite source alphabet with at least two symbols and strictly positive weights, every ternary prefix code minimizing weighted codeword length has all internal vertices of outdegree three, except possibly one of outdegree two whose tree children are deepest tree leaves.

To prove this, let $L$ be the greatest tree leaf depth. A missing tree child at any depth $n<L$ would permit moving a deepest tree leaf into that vacant branch, strictly reducing its positive weighted cost. Thus all internal vertices above depth $L-1$ have three tree children. Tree parents at depth $L-1$ have only tree leaves as tree children; one tree child would permit contraction and strict improvement. If two such tree parents each had two tree children, move one tree child of the second into the first tree parent's third slot, preserving its depth, and contract the second tree parent's remaining tree child. This again strictly improves cost. There is therefore at most one binary tree parent. If the number of symbols is an odd number, the leaf-count formula for a full ternary tree forces $N_2$ to be an even integer; since $N_2\le 1$, there is no binary tree parent.

Strict positivity matters. For probabilities $(1,0,0)$, the prefix code $(0,10,110)$ minimizes expected codeword length at one trit, yet has unary vertices and a deepest tree leaf without a sibling codeword. Removing or rearranging zero-weight branches can select a reduced minimizer, but arbitrary minimizers need not have the positive-weight shape.

The three-symbol output version of Huffman coding. For an odd number $m\ge 3$ of source symbols, repeatedly merge the three least current weights, replacing them by their sum. Each merge reduces the number of weighted objects by two until one tree root remains. Label each tree parent's outgoing edges $0,1,2$ to obtain a ternary prefix code. The merge weights sum to the expected codeword length in trits.

For an even number of source symbols, first merge the two least weights, then continue with triples. Equivalently, add one zero-weight dummy symbol, use triple merges throughout, and finally remove the dummy word. Ties may be resolved arbitrarily. This minimizes expected codeword length. The shape of minimum-cost positive-weight ternary prefix trees, followed by exchanging the least weights into a deepest sibling codeword triple, reduces the case of an odd number of symbols to the same optimization with two fewer symbols. If there is a binary deepest tree parent when the number of symbols is an even number, the two least weights can be placed there first. Contracting the chosen sibling codewords changes every competing cost by their fixed weight sum. This gives the same optimal-substructure proof as Huffman sibling contraction, with a triple or the initial pair replacing a binary pair.

A prefix code whose codewords use a three-symbol alphabet, conventionally $\{0,1,2\}$. No complete codeword is a prefix of another, permitting sequential decoding by following a code tree to a tree leaf. Its expected codeword length is ${\sum }_i{p}_i|c(i)|$ trits per source symbol. For source probabilities $(1/2,1/4,1/8,1/8)$, the codewords $(0,1,20,21)$ give expected codeword length $5/4$ trits.

A ternary digit, taking one of three values. A codeword of length $l$ over a three-symbol alphabet uses $l$ trits. If the trit is uniform its information entropy is ${\log }_{2}3$ bits; an arbitrary ternary digit can have less information entropy. Expected codeword length in trits must therefore be distinguished from source information entropy measured in bits.