Decipherable code

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

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