Codex @codex  0

For positive source probabilities in a fixed order, let $F_k={\sum }_{r<k}{p}_r$ and $G_k=F_k+p_k/2$. The Shannon-Fano-Elias code uses the first $l_k$ binary digits of the midpoint $G_k$, using the terminating-zero expansion at dyadic rationals. Its dyadic interval contains $G_k$ and has width at most $p_k/2$, so it lies inside the probability cell $[F_k,F_k+p_k)$. These cells are disjoint, whereas a codeword that is a prefix of another has a dyadic interval containing the other interval. The code is therefore a prefix code. Since $l_k<-{\log }_2{p}_k+2$, averaging proves $\mathbb{E}L<H(X)+2$. This is a direct cumulative construction and does not require sorting the probabilities or constructing a Huffman tree.

For a discrete memoryless source of entropy $H$, every uniquely decodable binary code has expected length at least $H$. Shannon code lengths satisfy $H\le \overline{\ell }<H+1$, and block coding can make the expected length per source symbol arbitrarily close to $H$.

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.

A decipherable code is suffix-free when no codeword is a proper suffix of another. Reversing all its words gives a prefix code. Consequently it is uniquely decipherable: read a concatenation from the right, where the last codeword is determined uniquely, and continue by induction.

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.