All notes

Prefix code

Wikipedia: Prefix code.

Prefix Property
There is no code word in the system that is a prefix (initial segment) of any other code word in the system.
Example: a code with code words {9, 55} has the prefix property; a code consisting of {9, 5, 59, 55} does not, because "5" is a prefix of "59" and also of "55".

A prefix code is a type of code system in posession of "prefix property".

A prefix code is a uniquely decodable code: a receiver can identify each word without requiring a special marker between words.

Prefix codes are not error-correcting codes.
In practice, a message might first be compressed with a prefix code, and then encoded again with channel coding (including error correction) before transmission.
Kraft's inequality characterizes the sets of code word lengths that are possible in a uniquely decodable code

A suffix code is a set of words none of which is a suffix of any other.
A bifix code is a set of words which is both a prefix and a suffix code.

Kraft's inequality


It gives both a necessary and sufficient condition for the existence of a prefix code for a given set of codeword lengths.

Definition. Given a list of symbols, there exists a prefix code with a set of codewords ($\sigma_1, \sigma_2, \ldots, \sigma_r$) where the length of each codeword $\|\sigma_i\|=n_i$, $\forall i$ if and only if $$ \sum_{i=1}^r s^{−n_i} \le 1$$ where $s$ is the size of the alphabet $S$.

Suppose: $$ \begin{equation} \left\{ \begin{aligned} a & \rightarrow 0 \\ b & \rightarrow 10 \\ c & \rightarrow 110 \\ d & \rightarrow 111 \\ \end{aligned} \right. \end{equation} $$ $a, b, c, d$ are symbols, $\{0,1\}$ is the alphabet, and $0, 10, 110, 111$ are codewords. $$ 2^{-1} + 2^{-2} + 2^{-3} + 2^{-3} \leq 1 $$ And, for the non-prefix: $$ \left\{ \begin{aligned} a & \rightarrow 0 \\ b & \rightarrow 01 \\ c & \rightarrow 011 \\ d & \rightarrow 0111 \\ \end{aligned} \right. $$ $$ 2^{-1} + 2^{-2} + 2^{-3} + 2^{-4} \leq 1 $$

Kraft's inequality limits the lengths of codewords in a prefix code: if one takes an exponential of the length of each valid codeword, the resulting set of values must look like a probability mass function, that is, it must have total measure less than or equal to one. $$ \sum_{l \in leaves} 2^{-depth(l)} \le 1 $$

Kraft's inequality can be thought of in terms of a constrained budget to be spent on codewords, with shorter codewords being more expensive.

Forward error correction

Forward error correction (FEC) or channel coding is a technique used for controlling errors in data transmission over unreliable or noisy communication channels. The central idea is the sender encodes the message in a redundant way by using an error-correcting code (ECC).
The first error-correcting code in 1950: the Hamming (7,4) code.

Huffman coding

A particular type of optimal prefix code that is commonly used for lossless data compression.

The algorithm was developed by David A. Huffman while he was a Ph.D. student at MIT, and published in the 1952 paper "A Method for the Construction of Minimum-Redundancy Codes".