Định lý mã hóa nguồn không nhiễu của Shannon

Với cận dưới, gọi $l_i$ là độ dài của một mã tiền tố bất kỳ, nên $\sum_{i=1}^n 2^{-l_i} \le 1$. Đặt $q_i = 2^{-l_i}/Z$ với $Z=\sum_j 2^{-l_j} \le 1$, khi đó $q$ là một phân phối xác suất. Theo bất đẳng thức Gibbs, $0 \le D(p\|q) = \sum_i p_i \log_2(p_i/q_i) = \sum_i p_i\log_2 p_i - \sum_i p_i \log_2(2^{-l_i}/Z) = -H(X) + \sum_i p_i l_i + \log_2 Z$. Vì $Z \le 1$ nên $\log_2 Z \le 0$, do đó $0 \le -H(X) + L + \log_2 Z \le -H(X) + L$, biến đổi ra $L \ge H(X)$.

Với cận trên (tính khả đạt), chọn $l_i = \lceil -\log_2 p_i \rceil$ cho mỗi $i$ (làm tròn lên độ dài lý tưởng thành số nguyên gần nhất). Các độ dài này thỏa bất đẳng thức Kraft vì $2^{-l_i} \le 2^{-(-\log_2 p_i)} = p_i$, nên $\sum_i 2^{-l_i} \le \sum_i p_i = 1$; theo cách dựng Kraft–McMillan, các độ dài như vậy luôn có thể hiện thực hóa thành một mã tiền tố thực sự (xây mã bằng cách gán các chuỗi nhị phân theo từng tầng trong một cây nhị phân).

Theo định nghĩa của hàm trần, $l_i < -\log_2 p_i + 1$. Nhân với $p_i \ge 0$ và lấy tổng theo $i$ ta được $L = \sum_i p_i l_i < \sum_i p_i(-\log_2 p_i + 1) = H(X) + 1$.

Kết hợp hai phần, cách dựng này đạt được $H(X) \le L < H(X) + 1$.