Prefix-free Code

Given a random variable \(X\) with sample sapce \(\mathcal{X}\) and a \(D\) -ary alphabet, a prefix-free code (also just called a prefix code) is a code \(\mathcal{C} : \mathcal{X} \to D^*\) where in the set of codewords \(\{\mathcal{C}(x) \: : \: x\in \mathcal{X}\}\), no codeword is a prefix of any other codeword. E.g.

\(x\)	\(\mathcal{C}(x)\)
A	0
B	10
C	110
D	1111

Prefix codes can be represented as a \(D\) -ary tree, where each edge represents a symbol from the \(D\) -ary alphabet and each leaf represents a codeword traced from the path from the root to that leaf. A sequence of codewords from a prefix code can be decoded by creating such a tree, and separating the codewords in the sequence by tracing the tree and placing a delimeter whenever a leaf is reached.