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.

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

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

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 assigns a symbol of probability $p_i$ a prefix-code length near $-{\log }_2{p}_i$.

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