Nguồn → Kênh: Mã hóa Hai Giai đoạn
Chương 10 của Hamming bắt đầu với mô hình truyền thông của Shannon, áp dụng cho mọi hệ thống di chuyển thông tin: cuộc gọi điện thoại, radio, ổ cứng, sao chép DNA, bộ nhớ máy tính.
Kiến trúc Hai Giai đoạn
Giai đoạn 1: Mã hóa nguồn (nén dữ liệu). Chuyển đổi thông điệp nguồn thành biểu diễn nhỏ gọn. Mục tiêu: loại bỏ tính dư thừa có sẵn từ nguồn. Mã Morse làm điều này: các chữ cái phổ biến nhận mã ngắn, các chữ cái hiếm nhận mã dài.
Giai đoạn 2: Mã hóa kênh (bảo vệ lỗi). Thêm tính dư thừa được kiểm soát thích ứng với đặc điểm nhiễu của kênh. Một đường dây điện thoại nhiễu cần tính dư thừa hơn cáp quang. Hai giai đoạn tách rời: tối ưu hóa mỗi giai đoạn độc lập cho nhiệm vụ của nó.
Giao diện chung giữa hai giai đoạn — một luồng bit chuẩn — có nghĩa là bất kỳ nguồn nào cũng có thể kết hợp với bất kỳ kênh nào. Tính mô-đun này là cái nhìn sâu sắc về kiến trúc chính của Shannon.
Lưu trữ như truyền thông. Hamming lưu ý rằng gửi một thông điệp qua không gian (truyền tải) và gửi nó qua thời gian (lưu trữ) sử dụng cùng một mô hình. Ổ đĩa sao lưu là một kênh nhiễu trong thời gian.
Vai trò của Nhiễu
Mô hình của Shannon đưa ra một giả định cơ bản: nhiễu là không thể tránh được. Mỗi kênh, mỗi phương tiện lưu trữ, mỗi mạch chuyển mạch đều giới thiệu một số xác suất lỗi. Câu hỏi không phải là 'chúng ta làm sao loại bỏ nhiễu?' mà là 'chúng ta làm sao phục hồi thông điệp gốc mặc dù có nhiễu?'
Điều này tương phản với vật lý cổ điển, nơi nhiễu xuất hiện như một suy nghĩ thêm (nguyên lý bất định). Shannon coi nhiễu là điều kiện nền tảng — tất cả lý thuyết được xây dựng từ nó.
Hiện tại, Chương 10 tập trung vào trường hợp không có nhiễu: mã hóa nguồn mà không có lỗi. Bài toán mã hóa kênh (sửa lỗi) đợi đến các chương sau.
Khi nào bạn có thể Giải mã Duy nhất?
Để một mã độ dài biến đổi hữu ích, người nhận phải giải mã một luồng bit không có tính mơ hồ. Hamming minh họa với mã 4-ký hiệu không vượt qua bài kiểm tra này, sau đó giới thiệu sửa chữa: mã không có tiền tố.
Điều kiện Không có Tiền tố
Một mã là không có tiền tố (hoặc tức thì) nếu không có từ mã nào là tiền tố của bất kỳ từ mã nào khác. Cho một luồng bit nhận được, bạn biết một ký hiệu đã kết thúc vào lúc bạn đạt đến một nút lá trong cây giải mã — không cần nhìn trước.
Ví dụ mã không có tiền tố cho {s1, s2, s3, s4}: s1 = 0, s2 = 10, s3 = 110, s4 = 111.
Xác minh: 0 không phải là tiền tố của 10, 110, hoặc 111. 10 không phải là tiền tố của 110 hoặc 111 (10 theo sau bởi thêm bit cho 100... hoặc 101..., cả hai đều không bắt đầu bằng 110 hoặc 111). Mã đủ tiêu chuẩn.
Quy trình giải mã: theo dõi cây, nhánh trên mỗi bit đến, phát hành ký hiệu khi bạn chạm vào lá, quay lại gốc.
Bất đẳng thức Kraft
Đối với bất kỳ mã nhị phân không có tiền tố nào với độ dài từ mã l_1, l_2, ..., l_n:
Σ 2^(−l_i) ≤ 1
Đẳng thức giữ khi mã là hoàn chỉnh (các lá lát toàn bộ cây nhị phân mà không có khoảng cách). Đây là điều kiện cần thiết: không có mã không có tiền tố nào có thể vi phạm nó. Ngược lại, đối với bất kỳ tập hợp độ dài nào thỏa mãn bất đẳng thức Kraft, một mã không có tiền tố tồn tại.
Áp dụng Bất đẳng thức Kraft
Cho độ dài từ mã, xác minh Kraft: Σ 2^(−l_i) ≤ 1.
Đối với {s1=0, s2=10, s3=110, s4=111}: độ dài là 1, 2, 3, 3.
Σ = 2^(−1) + 2^(−2) + 2^(−3) + 2^(−3) = 1/2 + 1/4 + 1/8 + 1/8 = 1. ✓
Shannon Entropy
Độ dài mã hóa trung bình của một mã độ dài biến đổi: L = Σ p_i · l_i, trong đó p_i là xác suất ký hiệu s_i và l_i là độ dài từ mã của nó.
L có thể ngắn đến mức nào? Câu trả lời của Shannon: không phải bên dưới entropy của nguồn.
Shannon entropy: H = −Σ p_i · log₂(p_i) (đơn vị: bit/ký hiệu)
Entropy đo lượng thông tin trung bình trên mỗi ký hiệu. Entropy cao có nghĩa là các ký hiệu có khả năng xảy ra gần như bằng nhau (không thể dự đoán tối đa). Entropy thấp có nghĩa là một số ký hiệu chiếm ưu thế (khả năng dự đoán cao, có thể nén hơn).
Định lý Mã hóa không Nhiễu
Đối với bất kỳ mã không có tiền tố nào, H(nguồn) ≤ L ≤ H(nguồn) + 1.
Không có mã nào có thể vượt qua entropy. Mã hóa Huffman (chương tiếp theo) đạt được giới hạn trên: L < H + 1. Đối với các mã khối trên n ký hiệu, giới hạn được siết chặt hơn: H ≤ L/n < H + 1/n.
Entropy cũng là giới hạn nén lý thuyết: bạn không thể nén một nguồn dưới H bit trên ký hiệu mà không mất thông tin.
Tính Entropy
Ví dụ: 4 ký hiệu với xác suất p = [1/2, 1/4, 1/8, 1/8].
H = −(1/2)·log₂(1/2) − (1/4)·log₂(1/4) − (1/8)·log₂(1/8) − (1/8)·log₂(1/8)
= (1/2)·1 + (1/4)·2 + (1/8)·3 + (1/8)·3
= 0.5 + 0.5 + 0.375 + 0.375 = 1.75 bit/ký hiệu
Và mã Huffman {0, 10, 110, 111} đạt L = 1.75 = H chính xác.
Tại sao Entropy Là Giới hạn Dưới
Giới hạn dưới của định lý mã hóa không nhiễu không chỉ là một công thức — nó phản ánh điều gì đó sâu sắc về thông tin: bạn không thể nén những gì đã tối đa không thể dự đoán.
Khi tất cả các ký hiệu có khả năng xảy ra bằng nhau (phân bố đồng nhất), entropy H = log₂(n) cho n ký hiệu. Một mã khối độ dài log₂(n) bit đạt được chính xác H. Không có mã nào có thể làm tốt hơn.
Khi một ký hiệu chiếm ưu thế (nói H là p(A) = 0.99, p(B) = 0.01), H là nhỏ — gần 0. Một mã độ dài biến đổi có thể gán cho A một mã rất ngắn, mã hóa luồng rất hiệu quả.
Kết luận thực tế: lợi nhuận nén lớn chỉ tồn tại khi xác suất ký hiệu khác nhau đáng kể. Nếu nguồn đã 'đồng nhất' (trông ngẫu nhiên), mã hóa Huffman không đạt được gì cả.