Unique decodability

Unique decodability means that every encoded message has at most one decomposition into codewords.

A code is decipherable, or uniquely decodable, when every finite concatenation of codewords has at most one decomposition into source codewords.

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.

For a fixed source distribution and code alphabet, an optimal uniquely decodable code minimizes expected codeword length. Huffman coding gives an optimal binary prefix code, and the equivalence of attainable uniquely-decodable and prefix-code lengths gives the same minimum for both classes.

In a prefix code no codeword is the prefix of another, so concatenated messages have unique instantaneous decoding.

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 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.

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.

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.

Replacing every quaternary digit by its fixed two-bit representation preserves the prefix code property: a binary prefix between translated codewords would end at an even position and hence imply a quaternary prefix. Thus a translated quaternary Huffman code cannot beat binary Huffman coding in expected codeword length.

For the reverse bound, binary prefix code lengths ${\ell }_i$ give candidate quaternary lengths $k_i=\lceil {\ell }_i/2\rceil$. Since ${\sum }_i{4}^{-k_i}\le {\sum }_i{2}^{-{\ell }_i}\le 1$, the Kraft inequality supplies such a quaternary prefix code. Optimality of quaternary Huffman coding and $2\lceil {\ell }_i/2\rceil \le {\ell }_i+1$ give $2L_4^{\ast }\le L_2^{\ast }+1$. These quantities are expected codeword lengths for the same source probability distribution.

For a success index $J$ with geometric distribution of parameter $q=2^{-n}$, write $J-1=2^{n}Q+R$, $0\le R<2^n$. Encode $Q$ by $Q$ ones followed by zero, then encode $R$ in exactly $n$ bits. This prefix code has length $n+Q+1$. Since $\mathbb{P}(Q\ge k)=(1-q{)}^{k{2}^n}$, its expected length is the displayed expression, at most $n+e/(e-1)$. Thus a very rare success can be communicated in approximately the logarithm of its inverse probability, rather than one bit per trial.

// Target: quantum-theory.bigb

The prefix tree of a code has vertices corresponding to prefixes of codewords, with one edge for each next symbol. The root represents the empty word. In a prefix code, complete codewords are leaves, and their depths are their codeword lengths.

// Target: computer-science.bigb

The lengths of every decipherable binary code satisfyConversely, any positive integer lengths satisfying this bound can be realized by a prefix code.

The lengths of a finite uniquely decodable code satisfy ${\sum }_a{2}^{-l(a)}\le 1$, even when the code is not a prefix code. Distinct concatenations of $r$ codewords remain distinct; counting the possible binary strings of each total length bounds $({\sum }_a{2}^{-l(a)}{)}^r$ by $r{\max }_{a}l(a)$. Taking $r$th roots proves the claim.

Prescribed positive word lengths admit a decipherable code if and only if they admit a prefix code. Counting length-$L$ concatenations of $m$ words proves the Kraft inequality for any decipherable code; choosing free vertices of the ordered $D$-ary tree constructs a prefix code whenever this inequality holds. Each prefix code has unique decodability.

If a decipherable binary code has $N$ codewords of lengths $l_1,\dots ,l_N$, thenThis follows by applying the entropy lower bound with the uniform source distribution.

Shannon-Fano coding comprises two related prefix code constructions. Shannon coding assigns lengths $\lceil -{\log }_2{p}_i\rceil$ to symbols of probability $p_i$; Fano coding recursively partitions the ordered symbols into groups of nearly equal total probability and assigns a bit at each partition.

Recursively split an ordered list of positive source probabilities into contiguous blocks, choosing each cut to minimize the difference between the total masses of the two children. The resulting binary prefix code has expected codeword length less than $H+2$, where $H$ is its source Shannon entropy. If the probabilities were in nonincreasing order, its expected length is less than $H+1$.

To prove this, an interior node of mass $S$ with child masses $A,B$ contributes $S$ to the expected path length and $Sh(A/S)$ to the Shannon entropy, by the chain rule for information entropy. The inequality $1-h(t)\le |2t-1|$ bounds that node's redundancy by $|A-B|$. If the cut is between probabilities $p_k,p_{k+1}$, shifting the cut by one position cannot improve the imbalance. On the heavier side this gives $|A-B|\le p_k$ or $p_{k+1}$, respectively; a singleton heavier side gives the same inequality directly. Thus $|A-B|\le \max (p_k,p_{k+1})$.

Every original inter-symbol gap is used once in the recursive tree. Summing over gaps bounds total redundancy by ${\sum }_{k=1}^{m-1}(p_k+p_{k+1})=2-p_1-p_m<2$. In sorted order it is instead at most ${\sum }_{k=1}^{m-1}{p}_k=1-p_m<1$. These are expected-length guarantees, not an assertion that the resulting code is always optimal.

For source probabilities $p_i>0$, Shannon coding chooses binary lengths ${\ell }_i=\lceil -{\log }_2{p}_i\rceil$. They satisfy ${\sum }_i{2}^{-{\ell }_i}\le {\sum }_i{p}_i=1$, so the Kraft inequality ensures that a binary prefix code with these lengths exists.

Its expected length obeys $H\le {\sum }_i{p}_i{\ell }_i<H+1$, where $H=-{\sum }_i{p}_i{\log }_2{p}_i$ is the source entropy. For probabilities $(1/2,1/4,1/4)$, the words $0,10,11$ achieve the lengths $1,2,2$ exactly. The construction rounds each information content up separately; Huffman coding can improve the expected length by optimizing the whole code tree.^[ref]

Order source probabilities as $p_1\ge \cdots \ge p_N$, putand take the first $l_i$ binary digits of $b_i$ as the codeword for symbol $i$. Since $b_j-b_i\ge p_i\ge 2^{-l_i}$ for $j>i$, two cumulative probabilities cannot lie in the same dyadic interval selected by the earlier codeword. The resulting code is prefix-free.

If the Shannon length is $l_S(x)=\lceil {\log }_2(1/p_x)\rceil$ and $l_C$ is the length of any binary decipherable code, thenThus the probability that the Shannon code loses to another code by $k$ or more bits decreases exponentially in $k$.

For a finite source alphabet with probabilities $p_i>0$ and binary prefix code lengths ${\ell }_i$, the expected length satisfiesTo see this, let $K={\sum }_i{2}^{-{\ell }_i}\le 1$ by Kraft inequality and put $q_i=2^{-{\ell }_i}/K$. Direct calculation givesusing nonnegativity of relative entropy. Thus the information entropy measures the unavoidable average description length, rather than the length of every individual message.

If at least two symbols have positive probability, the Shannon lengths ${\ell }_i=\lceil -{\log }_2{p}_i\rceil$ are positive, satisfy Kraft inequality, and obey $H(p)\le \overline{\ell }<H(p)+1$. For a one-symbol source, $H=0$; if codewords must have positive length, a one-bit codeword has expected length $1$, so the strict upper bound requires that separate convention or a nontrivial alphabet.

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.

For a finite-alphabet memoryless classical information source with information entropy $H$, every uniquely decodable code for blocks of $m$ source symbols has expected binary length at least $mH$. This follows from Kraft inequality for uniquely decodable codes and the entropy lower bound for prefix codes.

If at least two source symbols have positive probability, give each positive-probability block $w$ Shannon length $\ell (w)=\lceil -{\log }_{2}p(w)\rceil$. These lengths satisfy Kraft inequality, so a prefix code exists, and independence givesThus coding longer blocks approaches the information entropy in expected bits per source symbol. This is an average-length statement: rare blocks can have long codewords.

For a source with only one possible symbol, a one-bit codeword for each length-$m$ block gives rate $1/m\to 0=H$ when positive codeword lengths are required. The limiting theorem therefore remains true, although the strict one-block bound $\overline{\ell }<H+1$ needs the nontrivial-alphabet assumption. Countably infinite alphabets require additional care about finite information entropy and the chosen code construction.