Lý thuyết thông tin

Logarit là hàm lõm, nên "trung bình" nó nằm dưới tiếp tuyến của mình. Bất đẳng thức Gibbs chính là bất đẳng thức Jensen áp dụng cho hàm lõm $\log_2$, với trọng số $p$: nó nói rằng thay mỗi tỉ số $q_i/p_i$ bằng trung bình có trọng số $p$ của chúng (bằng $1$) bên trong logarit chỉ có thể làm tăng tổng, buộc độ phân kỳ phải không âm.

Bắt đầu từ bất đẳng thức sơ cấp $\ln x \le x - 1$ với mọi $x > 0$, đẳng thức chỉ xảy ra tại $x=1$ (điều này đúng vì $f(x) = \ln x - (x-1)$ có $f(1)=0$, $f'(x) = 1/x - 1$, dương khi $x<1$ và âm khi $x>1$, nên $f$ có cực đại duy nhất tại $x=1$). Chia cho $\ln 2$ ta được $\log_2 x \le (x-1)/\ln 2$.

Áp dụng điều này với $x = q_i/p_i$ cho mỗi $i$: $\log_2(q_i/p_i) \le (q_i/p_i - 1)/\ln 2$. Nhân cả hai vế với $p_i > 0$ (không đổi chiều bất đẳng thức) và lấy tổng theo $i$: $\sum_i p_i \log_2(q_i/p_i) \le \frac{1}{\ln 2}\sum_i (q_i - p_i) = \frac{1}{\ln 2}\left(\sum_i q_i - \sum_i p_i\right) = \frac{1}{\ln 2}(1 - 1) = 0$, vì cả $p$ và $q$ đều là phân phối xác suất có tổng bằng $1$.

Vế trái chính là $-D(p\|q)$ (chú ý dấu đảo ngược do $q_i/p_i$ thay vì $p_i/q_i$ trong logarit), nên điều này chứng minh $D(p\|q) \ge 0$.

Đẳng thức toàn phần đòi hỏi đẳng thức trong $\ln x \le x-1$ với mọi $i$ có $p_i > 0$, điều này chỉ xảy ra khi $q_i/p_i = 1$ với mọi $i$ như vậy, tức là $p = q$.

Cận dưới cho biết entropy là một sàn cứng: không mã tiền tố không mất mát nào có thể, trung bình, vượt qua $H(X)$ bit trên mỗi kí hiệu, vì làm tốt hơn sẽ đòi hỏi phân phối do mã sinh ra khác với phân phối thật của $X$ theo cách mà bất đẳng thức Gibbs cấm. Cận trên cho biết sàn này gần như đạt được: làm tròn lên mỗi độ dài lý tưởng $-\log_2 p_i$ thành số nguyên chỉ lãng phí ít hơn một bit trung bình.

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

Dung lượng không chỉ là một công thức tiện lợi — nó là một bức tường thực sự. Dưới ngưỡng đó, trải mỗi thông điệp trên một khối đủ dài giúp các từ mã trông ngẫu nhiên vẫn phân biệt được dù có nhiễu, nên lỗi có thể được đưa về không; trên ngưỡng đó, kênh phá hủy thông tin nhanh hơn bất kỳ mã nào có thể bảo vệ, dù mã có tinh vi đến đâu.

**Chiều đảo ($R > C \Rightarrow P_e \not\to 0$).** Bất đẳng thức Fano chặn độ bất định còn lại của bên nhận về thông điệp khi biết đầu ra nhiễu: $H(X\mid Y) \le 1 + P_e \log_2(n-1)$, với $n$ là số thông điệp có thể. Đồng thời, cấu trúc xử lý dữ liệu của kênh buộc $I(X;Y) \le C$ ở mỗi lần dùng, nên trên một khối $N$ lần dùng kênh, tổng thông tin bên nhận có thể trích ra tối đa là $NC$ bit. Nếu tốc độ thật là $R > C$ bit mỗi lần dùng, thông điệp mang $NR$ bit entropy nhưng kênh chỉ cung cấp khoảng $NC < NR$ bit về nó; bất đẳng thức Fano khi đó buộc $P_e$ phải giữ khoảng cách khỏi $0$ khi $N$ tăng, vì độ bất định còn lại $H(X\mid Y)$ không thể triệt tiêu được.

**Phác thảo chiều thuận ($R < C \Rightarrow P_e \to 0$).** Cố định một phân phối đầu vào $p(x)$ đạt dung lượng và sinh ngẫu nhiên độc lập một bảng mã gồm $2^{NR}$ từ mã độ dài $N$ từ $p(x)^N$. Để giải mã, bên nhận tìm từ mã duy nhất đồng điển hình với chuỗi nhận được (nghĩa là có các mẫu thống kê giống một cặp đầu vào–đầu ra thật). Vì $R < C$, số từ mã ứng viên ($2^{NR}$) nhỏ hơn nhiều so với số đầu ra kênh phân biệt được về mặt thống kê ($\approx 2^{NC}$), nên khi $N \to \infty$ khả năng một từ mã khác, không được gửi, tình cờ trông đồng điển hình với chuỗi nhận được giảm về $0$, và xác suất lỗi giải mã cũng vậy, tính trung bình theo lựa chọn ngẫu nhiên của bảng mã — do đó phải tồn tại ít nhất một bảng mã đạt được $P_e$ nhỏ tùy ý.