Shannon Gọi Thông Tin Là Gì
Shannon xác định thông tin bằng cách đo lường sự bất ngờ. Một thông điệp với xác suất p mang:
I = −log₂(p) bit
Một sự kiện chắc chắn (p = 1) mang 0 bit — không bất ngờ, không có thông tin. Một sự kiện hiếm (p = 1/1024) mang 10 bit.
Hamming ngay lập tức chỉ ra vấn đề: đây là công thức đo lường một đại lượng, không phải định nghĩa của khái niệm. Nó đo sự bất ngờ giống máy, không phải ý nghĩa con người. Một học sinh đã biết câu trả lời cho một câu hỏi nhận được 0 bit từ câu trả lời — bất kể câu trả lời đó quan trọng như thế nào đối với những người khác.
Công thức áp dụng tốt cho các hệ thống điện thoại, radio, máy tính. Nó áp dụng kém cho giao tiếp con người, sinh học, hoặc ý nghĩa. Tên ưa thích của Hamming: 'Lý thuyết Giao tiếp', không phải 'Lý thuyết Thông tin'.
Entropy
Đối với bảng chữ cái gồm q ký hiệu với xác suất p₁, p₂, ..., p_q, thông tin trung bình trên mỗi ký hiệu là entropy:
H = −Σᵢ pᵢ log₂(pᵢ)
H đạt cực đại khi tất cả xác suất bằng nhau: H_max = log₂(q) bit. Bất kỳ phân bố không đều nào cũng có entropy thấp hơn.
Tính Entropy
Entropy nhị phân: một nguồn có hai ký hiệu, P(0) = p, P(1) = 1−p.
H(p) = −p log₂(p) − (1−p) log₂(1−p)
H(p) = 0 tại p = 0 hoặc p = 1 (hoàn toàn có thể dự đoán). H(p) = 1 bit tại p = 0,5 (hoàn toàn không thể dự đoán).
Bất đẳng thức Gibbs & Mã hóa Không Nhiễu
Bất đẳng thức Gibbs: đối với bất kỳ hai phân bố xác suất p = {pᵢ} và q = {qᵢ}:
−Σ pᵢ log₂(pᵢ) ≤ −Σ pᵢ log₂(qᵢ)
với đẳng thức chỉ khi p = q. Điều này dựa trên thực tế cơ bản là ln(x) ≤ x − 1 với mọi x > 0, với đẳng thức tại x = 1.
Hệ quả: entropy H(p) được tối đa hóa khi tất cả các ký hiệu đều có xác suất bằng nhau. Đối với q ký hiệu: H_max = log₂(q).
Định lý mã hóa không nhiễu: cho một mã giải mã duy nhất, bất đẳng thức Kraft yêu cầu Σ 2^(−lᵢ) ≤ 1 trong đó lᵢ là độ dài của mã cho ký hiệu i. Theo bất đẳng thức Gibbs, độ dài mã trung bình L = Σ pᵢ lᵢ thỏa mãn:
L ≥ H(p) = −Σ pᵢ log₂(pᵢ)
Bạn không thể làm tốt hơn entropy trên trung bình. Mã hóa Huffman đạt L < H + 1.
Năng lực Kênh
Một kênh nhị phân đối xứng (BSC) lật mỗi bit độc lập với xác suất lỗi Q = 1 − P. Năng lực của BSC — tốc độ thông tin đáng tin cậy tối đa — là:
C = 1 + P log₂(P) + Q log₂(Q) = 1 − H(Q)
trong đó H(Q) = −Q log₂(Q) − (1−Q) log₂(1−Q) là entropy nhị phân của tỷ lệ lỗi.
Tại Q = 0 (không có lỗi): C = 1 bit/truyền (kênh hoàn hảo). Tại Q = 0,5 (lật ngẫu nhiên): C = 0 (kênh không mang thông tin). Tại Q = 1 (tất cả bit lật): C = 1 (bạn biết chính xác những gì người gửi đã gửi, chỉ cần lật mọi thứ ngược lại).
C đo tốc độ tối đa R mà bạn có thể truyền với xác suất lỗi tùy ý nhỏ. Nếu R < C, các mã như vậy tồn tại. Nếu R > C, chúng không tồn tại — không có mã nào có thể vượt quá năng lực.
Tính Năng lực Kênh
Với P = 0,9 (tỷ lệ lỗi 10%, Q = 0,1):
C = 1 + 0,9 log₂(0,9) + 0,1 log₂(0,1)
log₂(0,9) ≈ −0,152, log₂(0,1) ≈ −3,322
C ≈ 1 + 0,9×(−0,152) + 0,1×(−3,322) = 1 − 0,137 − 0,332 ≈ 0,531 bit/truyền
Định lý Chứng minh Gì
Định lý cơ bản của Shannon: với bất kỳ tốc độ R < C, có các mã độ dài khối n (với n → ∞) đạt xác suất lỗi P_E → 0.
Chứng minh sử dụng một lập luận bất ngờ: mã ngẫu nhiên. Thay vì xây dựng một mã cụ thể, Shannon lấy trung bình trên tất cả các sách mã ngẫu nhiên có thể (mã hóa lật đồng xu). Ông chỉ ra rằng lỗi trung bình trên tất cả các sách mã nhỏ. Nếu trung bình nhỏ, ít nhất một mã đạt lỗi nhỏ.
Phân tích dựa trên hình cầu: người gửi chọn thông điệp aᵢ → hình cầu bán kính n(Q + ε₂) xung quanh aᵢ trong không gian nhị phân n chiều. Đối với n lớn, từ nhận bⱼ nằm bên trong hình cầu này với xác suất cao. Bộ giải mã giải mã thành từ mã có hình cầu chứa bⱼ.
Bốn trường hợp xác định xác suất lỗi P_E:
``
aᵢ trong hình cầu aⱼ khác trong hình cầu kết quả
có không đúng (không có lỗi)
có có mơ hồ → lỗi
không có giải mã sai → lỗi
không không ngoài tất cả hình cầu → lỗi
``
Giới hạn trên P_E tính ra là: P_E ≤ d + M × 2^(n × (H(Q+ε₂) − C)) với d và ε₂ được chọn thích hợp. Chọn ε₂ để H(Q+ε₂) < C làm số mũ âm. Đối với n lớn, số hạng thứ hai → 0.
Bản chất Tồn tại của Định lý
Hamming chính xác về những gì định lý làm và không làm.
Những gì nó chứng minh: giao tiếp đáng tin cậy ở tốc độ R < C là có thể, về nguyên tắc, với n đủ lớn.
Những gì nó không cung cấp: xây dựng mã tường minh. Một mã ngẫu nhiên có độ dài n đủ lớn để tiếp cận năng lực có một sách mã kích thước M × n bit, trong đó cả M và n đều rất lớn. Bạn không thể lưu trữ hoặc tính toán với nó.
Mã hiệu chỉnh lỗi so với Shannon: mã hiệu chỉnh lỗi (Hamming, Reed-Solomon, turbo, LDPC) cung cấp xây dựng tường minh, có thể tính toán. Chúng hy sinh một số khoảng cách từ năng lực để trao đổi lấy bộ mã hóa & giải mã thực tế. Khi n tăng và các lỗi được sửa hơn trên mỗi khối, các mã thực tế có thể tiếp cận năng lực sát sao.
Ví dụ vệ tinh không gian: Voyager và Pioneer sử dụng các mã hiệu chỉnh lỗi mạnh mẽ để giao tiếp qua hàng tỉ dặm trên 5–20 watt công suất. Độ dài khối dài cho phép sửa chữa các lỗi nhiều hơn trên mỗi khối, đẩy gần năng lực mặc dù nhiễu khổng lồ từ khoảng cách.
Đánh giá Tỷ lệ
Hamming kết thúc Chương 13 bằng một tiếng nói rộng hơn về các định nghĩa trong khoa học. Công thức thông tin của Shannon đo sự bất ngờ giống máy, không phải ý nghĩa con người. Tên 'Lý thuyết Thông tin' hứa quá nhiều. Phép loại sư lưới cá: một ngư dân chỉ bắt được những con cá lớn hơn lưới của mình kết luận không có những con cá nhỏ hơn. Những hạn chế của công cụ trở thành những ràng buộc rõ ràng của thế giới.
Vấn đề với Định nghĩa
Hamming sử dụng lý thuyết thông tin để đưa ra một điểm phương pháp luận lớn hơn: các định nghĩa ban đầu xác định những gì bạn tìm thấy, nhiều hơn hầu hết mọi người nhận ra.
Shannon chọn xác định 'thông tin' như bất ngờ. Định nghĩa đó rất hiệu quả cho kỹ thuật giao tiếp. Nhưng nó nhập khẩu một phạm vi cụ thể — các hệ thống giống máy — thành một từ ('thông tin') gợi ý tính khả năng phổ quát.
Phép loại lưới cá: một lưới có lỗ 6 inch chỉ bắt được những con cá lớn. Ngư dân kết luận: kích thước cá tối thiểu là 6 inch. Kết luận phản ánh công cụ, không phải thế giới.
IQ như một song song: một bài kiểm tra được thiết kế để đo 'trí thông minh', được hiệu chỉnh để tạo ra một phân bố bình thường, sau đó được sử dụng để xác định trí thông minh. Công cụ định hình khái niệm.
Khuyến cáo của Hamming: bất cứ khi nào bạn gặp một định nghĩa, hãy hỏi (1) nó đồng ý bao nhiêu với trực giác trước đó của bạn? (2) nó biến dạng bao nhiêu? (3) nó được đóng khung dưới những điều kiện nào? (4) nó có được áp dụng bây giờ dưới những điều kiện khác không?