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.

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.

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

Every binary prefix code has expected length at least its source entropy; Shannon lengths achieve expected length strictly below $H+1$.

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