Định lýĐã chứng minh

Định lý mã hóa nguồn Shannon

Phát biểu

Cho một nguồn rời rạc không nhớ phát ra các ký hiệu từ một bảng chữ cái theo phân phối xác suất có entropy $H$ (đơn vị bit, dùng $\log_2$ ). Khi đó với mọi $\varepsilon > 0$ , tồn tại một phép mã hóa khối không mất mát với độ dài trung bình mỗi ký hiệu nhỏ hơn $H + \varepsilon$ khi độ dài khối $n$ đủ lớn; ngược lại, không phép mã hóa không mất mát nào có thể đạt độ dài trung bình mỗi ký hiệu nhỏ hơn $H$ . Nói ngắn gọn, entropy $H$ chính là số bit trung bình tối thiểu có thể đạt được cho mỗi ký hiệu.

Vì sao đúng?

Một thông điệp chỉ cần dài bằng đúng mức 'bất ngờ' mà nó mang theo: một ký hiệu xuất hiện gần như chắc chắn hầu như không cần bit nào để truyền, còn một ký hiệu hiếm cần nhiều bit. Entropy lấy trung bình mức 'bất ngờ' này (đo bằng $-\log_2 p$ ) trên toàn nguồn, tạo ra một ngưỡng cứng: bạn có thể nén bớt các khuôn mẫu thường gặp, nhưng không bao giờ nén một nguồn ngẫu nhiên xuống dưới độ khó đoán thực sự vốn có trong thống kê của chính nó.

Phác thảo chứng minh

Với khối dài $n$ ký hiệu độc lập cùng phân phối, tính chất phân hoạch đều tiệm cận cho thấy hầu hết xác suất tập trung vào một 'tập điển hình' gồm khoảng $2^{nH}$ dãy, mỗi dãy có xác suất gần $2^{-nH}$ . Gán từ mã ngắn (khoảng $nH$ bit) chỉ cho tập điển hình này, và từ mã dài hơn cho phần còn lại không đáng kể, đạt độ dài trung bình gần $H$ mỗi ký hiệu; chiều ngược lại suy ra vì bất kỳ mã nào gán trung bình ít hơn $nH$ bit sẽ không đủ số từ mã để phủ tập điển hình mà không trùng lặp, theo lập luận đếm.

Người phát biểu

Claude Shannon

Chủ đề chứa định lý này

Lý thuyết thông tin

Chứng minh từng bước

Chưa có chứng minh từng bước cho định lý này.

Tài liệu tham khảo

Claude E. Shannon (1948). A Mathematical Theory of Communication
Thomas M. Cover, Joy A. Thomas (2006). Elements of Information Theory