UP | HOME

Kraft-McMillan Inequality

We have a source alphabet with \(S=\{s_1,s_2,...\}\). We encode into an alphabet with \(r\) symbols. The code is uniquely decodable, which means that given the entire coded sequence, we can recover the source sequence. The encodings have lengths \(l_{1},l_{2}, \cdots\). Then, \[\sum_i \left(\frac{1}{r}\right)^{l_1} \leq 1\]