Bỏ qua tới nội dung chính

Hướng dẫn học chủ đề

Lý thuyết thông tin và mã hóa

Nâng caokhoảng 70 giờ6 bước

Entropy, nén dữ liệu, dung lượng kênh, mã sửa lỗi (Hamming, mã chập, LDPC) — giới hạn cơ bản của mọi hệ thống truyền thông và lưu trữ.

Bắt đầu học

Bạn sẽ học được gì

  • Tính entropy, entropy có điều kiện, thông tin tương hỗ và khoảng cách Kullback – Leibler của các phân phối rời rạc
  • Giải thích tính chất phân hoạch đều tiệm cận và định lý mã hóa nguồn, xác định giới hạn nén của một nguồn
  • Cài đặt và phân tích mã Huffman và mã hóa số học, so sánh độ dài trung bình với entropy
  • Tính dung lượng của các kênh rời rạc cơ bản và cài đặt thuật toán Blahut – Arimoto
  • Áp dụng công thức dung lượng kênh Gauss và giới hạn Shannon để đánh giá một hệ thống truyền thông
  • Mã hóa và giải mã mã khối tuyến tính (Hamming), mã chập bằng thuật toán Viterbi và mã LDPC bằng truyền thông điệp
  • Mô phỏng tỉ lệ lỗi của các mã trên kênh nhị phân đối xứng và kênh AWGN, so sánh với dung lượng

Nên học trước

Giới thiệu

Lý thuyết thông tin do Claude Shannon đặt nền móng năm 1948 trả lời hai câu hỏi tưởng như triết học bằng những con số chính xác: một nguồn tin có thể nén tới mức nào, và một kênh có nhiễu có thể truyền tin cậy với tốc độ tối đa bao nhiêu? Câu trả lời — entropy và dung lượng kênh — là giới hạn mà mọi hệ thống nén dữ liệu và truyền thông, từ file ZIP đến 5G, đều bị ràng buộc. Mã hóa là nửa kỹ thuật của chủ đề: các thuật toán nén và mã sửa lỗi giúp tiến sát những giới hạn đó. Ở các trường kỹ thuật Việt Nam, nội dung này nằm trong học phần Lý thuyết thông tin và mã hóa của chuyên ngành điện tử – viễn thông; ở MIT tương ứng là 6.441 Information Theory (có trên MIT OpenCourseWare).

Entropy và nén dữ liệu

Chủ đề bắt đầu bằng xác suất và cách đo "lượng bất ngờ": entropy của một biến ngẫu nhiên, entropy đồng thời và có điều kiện, thông tin tương hỗ và khoảng cách Kullback – Leibler. Tính chất phân hoạch đều tiệm cận (AEP) cho thấy một chuỗi dài gồm các ký hiệu độc lập gần như chắc chắn rơi vào một "tập điển hình" có khoảng 2^(nH) phần tử — và từ đó suy ra định lý mã hóa nguồn: không thể nén trung bình dưới H bit mỗi ký hiệu mà vẫn khôi phục được. Về phía thuật toán, bạn sẽ cài đặt mã Huffman, bất đẳng thức Kraft và mã hóa số học — thứ tiến sát entropy với mọi mô hình xác suất và là lõi của nhiều chuẩn nén hiện đại.

Kênh có nhiễu và dung lượng

Kênh truyền được mô hình bằng xác suất chuyển từ đầu vào sang đầu ra; dung lượng là thông tin tương hỗ lớn nhất theo mọi phân phối đầu vào. Kênh nhị phân đối xứng có dung lượng 1 − H₂(p), kênh xóa nhị phân có 1 − ε. Định lý mã hóa kênh khẳng định điều gây sốc vào thời điểm đó: với mọi tốc độ nhỏ hơn dung lượng, tồn tại mã có xác suất lỗi nhỏ tùy ý — không cần giảm tốc độ về 0. Với kênh Gauss băng thông B, dung lượng là B log₂(1 + SNR), và khi băng thông tiến tới vô hạn, Eb/N0 nhỏ nhất để truyền tin cậy là khoảng −1,59 dB — giới hạn Shannon.

Mã sửa lỗi

Phần cuối là các họ mã thực tế: mã lặp và mã Hamming (7,4) như ví dụ nhập môn, mã khối tuyến tính với ma trận sinh, ma trận kiểm tra chẵn lẻ và giải mã theo syndrome; mã chập với thuật toán Viterbi; và các mã hiện đại tiến sát dung lượng: mã LDPC giải bằng truyền thông điệp (belief propagation) và mã turbo. Đây không phải lý thuyết suông: LDPC có trong Wi-Fi, DVB-S2 và kênh dữ liệu 5G NR, mã polar được dùng cho kênh điều khiển 5G, còn mã Reed – Solomon bảo vệ mã QR và đĩa quang.

Nên học thế nào

  • Nền tảng cần có: xác suất và quá trình ngẫu nhiên vững (phân phối đồng thời, kỳ vọng, luật số lớn), đại số tuyến tính trên trường hai phần tử cho phần mã khối, và lập trình Python.
  • Sách chính: Information Theory, Inference, and Learning Algorithms của David MacKay — đọc miễn phí trên màn hình, viết sinh động, nhiều bài tập có lời giải và nối lý thuyết thông tin với suy luận Bayes và học máy. Elements of Information Theory (Cover và Thomas) là giáo trình chuẩn mực, chặt chẽ, dùng để đọc chứng minh.
  • Học bằng lập trình: cài Huffman và mã hóa số học rồi so với gzip; cài thuật toán Blahut – Arimoto tính dung lượng; mô phỏng mã Hamming, Viterbi và LDPC trên kênh nhị phân đối xứng và kênh AWGN để thấy đường cong tỉ lệ lỗi tiến dần về giới hạn Shannon.
  • Cẩn thận với trực giác: định lý mã hóa kênh là định lý tồn tại, chứng minh bằng mã ngẫu nhiên; việc tìm mã có cấu trúc giải được nhanh mà vẫn gần dung lượng mất gần nửa thế kỷ.

Học xong, bạn biết ước lượng giới hạn lý thuyết của một hệ thống, chọn và mô phỏng được mã sửa lỗi phù hợp, và có nền cho thông tin vô tuyến, mật mã, nén đa phương tiện và học máy.

Giáo trình & sách tham khảo

Xem tất cả trong tab Sách

Giáo trình chính

Information Theory, Inference, and Learning Algorithms

David J. C. MacKay · 2003 · Bản thứ 1

Miễn phíNâng caoTiếng Anh640 trang

Vì sao chọn: Giáo trình của David MacKay (Cambridge), đọc miễn phí trên màn hình theo cho phép của tác giả, bản quyền thuộc Cambridge University Press. Chọn làm sách chính vì viết sinh động, nhiều bài tập có lời giải, đi thẳng tới các mã hiện đại tiến sát dung lượng và nối lý thuyết thông tin với suy luận Bayes.

Nên đọc: Chương 1–2 (nhập môn, xác suất và entropy); Chương 4–6 (định lý mã hóa nguồn, mã ký hiệu, mã dòng); Chương 8–11 (kênh có nhiễu, định lý mã hóa kênh, kênh thực); Chương 13 Binary Codes; Chương 47–48 (LDPC, mã chập và turbo)

Elements of Information Theory

Thomas M. Cover, Joy A. Thomas · 2006 · Bản thứ 2

Có phíNâng caoTiếng Anh792 trang

Giáo trình lý thuyết thông tin chuẩn mực (bản thứ hai, 2006), dùng ở hầu hết các khóa sau đại học. Đọc song song với MacKay để có chứng minh chặt chẽ của các định lý; các chương sau (tốc độ – méo, thông tin mạng) dành cho người muốn đi sâu. Sách trả phí.

Nên đọc: Chương 2–3 (entropy, AEP); Chương 5 Data Compression; Chương 7–9 (dung lượng kênh, entropy vi phân, kênh Gauss)

Các bước học

Đăng nhập để đánh dấu các bước đã hoàn thành.

  1. Bước 1: Xác suất, entropy và thông tin tương hỗ

    khoảng 12 giờ

    Đọc phần nhập môn về truyền tin qua kênh nhiễu với mã lặp và mã Hamming (7,4); ôn xác suất và suy luận Bayes; học entropy, entropy đồng thời và có điều kiện, quy tắc dây chuyền, thông tin tương hỗ, khoảng cách Kullback – Leibler, bất đẳng thức Jensen và bất đẳng thức xử lý dữ liệu. Bài tập: viết chương trình Python ước lượng entropy theo ký tự của một văn bản tiếng Việt dài (sau khi chuẩn hóa Unicode) và so với log₂ của số ký tự khác nhau; tính thông tin tương hỗ giữa hai ký tự liền nhau.

  2. Bước 2: Tính chất phân hoạch đều tiệm cận và định lý mã hóa nguồn

    khoảng 10 giờ

    Học luật số lớn yếu, tập điển hình, tính chất phân hoạch đều tiệm cận và định lý mã hóa nguồn cho nguồn độc lập cùng phân phối. Bài tập: với nguồn nhị phân p = 0,1, tính entropy, đếm số chuỗi điển hình dài n = 20, 100 và vẽ xác suất của tập điển hình theo n bằng Python để thấy AEP "xuất hiện".

  3. Bước 3: Mã hóa nguồn: Huffman và mã hóa số học

    khoảng 12 giờ

    Học mã không tổn hao, mã tiền tố, bất đẳng thức Kraft, mã Huffman và tính tối ưu, mã hóa số học và mô hình xác suất thích nghi, mã Lempel – Ziv. Bài tập: cài đặt mã Huffman và mã hóa số học (có mô hình thích nghi bậc 0) trong Python, nén một file văn bản tiếng Việt, so độ dài trung bình với entropy ở bước 1 và với kết quả của gzip.

  4. Bước 4: Kênh có nhiễu và định lý mã hóa kênh

    khoảng 14 giờ

    Học biến ngẫu nhiên phụ thuộc, mô hình kênh rời rạc không nhớ, dung lượng kênh của kênh nhị phân đối xứng, kênh xóa và kênh đối xứng tổng quát, định lý mã hóa kênh và ý tưởng chứng minh bằng mã ngẫu nhiên, đảo định lý và bất đẳng thức Fano. Bài tập: cài đặt thuật toán Blahut – Arimoto tính dung lượng của một kênh rời rạc bất kỳ cho bằng ma trận chuyển, kiểm tra với công thức 1 − H₂(p) của kênh nhị phân đối xứng.

  5. Bước 5: Kênh Gauss và giới hạn Shannon

    khoảng 8 giờ

    Học entropy vi phân, kênh Gauss, dung lượng kênh Gauss băng thông giới hạn, giới hạn Shannon theo Eb/N0, phân bổ công suất đổ nước cho các kênh song song, và khoảng cách giữa mã thực tế với dung lượng. Bài tập: tính dung lượng kênh 20 MHz ở SNR 20 dB; vẽ đường giới hạn hiệu suất phổ theo Eb/N0 và đặt lên đó các điểm của BPSK, QPSK, 16-QAM không mã tại tỉ lệ lỗi bit 10⁻⁵.

  6. Bước 6: Mã sửa lỗi: mã khối, mã chập, LDPC và turbo

    khoảng 14 giờ

    Học mã khối tuyến tính, khoảng cách tối thiểu, giải mã syndrome; mã chập, lưới trạng thái và thuật toán Viterbi; mã LDPC, đồ thị Tanner và giải mã truyền thông điệp; mã turbo và giải mã lặp. Bài tập: cài mã Hamming (7,4) với giải mã syndrome và mã chập tốc độ 1/2 (đa thức sinh 7, 5 hệ bát phân) với giải mã Viterbi quyết định cứng và mềm; mô phỏng một mã LDPC ngắn trên kênh AWGN với BPSK và vẽ tỉ lệ lỗi bit theo Eb/N0 cùng với đường không mã.

Khái niệm chính

Entropy (Shannon)
H(X) = −Σ p(x) log₂ p(x), độ bất định trung bình của biến ngẫu nhiên tính bằng bit; đạt cực đại log₂ của số giá trị khi phân phối đều.
Thông tin tương hỗ
I(X;Y) = H(X) − H(X|Y), lượng thông tin về X nhận được khi quan sát Y; luôn không âm và bằng 0 khi X, Y độc lập.
Khoảng cách Kullback – Leibler
D(p‖q) = Σ p log(p/q), đo độ khác biệt giữa hai phân phối; không âm, bằng 0 khi và chỉ khi p = q, nhưng không đối xứng nên không phải khoảng cách theo nghĩa metric.
Tính chất phân hoạch đều tiệm cận (AEP)
Với chuỗi dài n ký hiệu độc lập cùng phân phối, xác suất của chuỗi gần như chắc chắn xấp xỉ 2^(−nH); tập các chuỗi như vậy (tập điển hình) có khoảng 2^(nH) phần tử.
Định lý mã hóa nguồn
Nguồn độc lập cùng phân phối có thể nén tới H bit mỗi ký hiệu với xác suất lỗi nhỏ tùy ý khi khối đủ dài, và không thể nén tốt hơn.
Bất đẳng thức Kraft và mã tiền tố
Mã tiền tố với độ dài từ mã lᵢ tồn tại khi và chỉ khi Σ 2^(−lᵢ) ≤ 1; độ dài trung bình của mã tiền tố tối ưu nằm trong khoảng [H, H + 1).
Mã Huffman
Thuật toán tham lam ghép dần hai ký hiệu ít xác suất nhất, cho mã tiền tố có độ dài trung bình nhỏ nhất với phân phối đã biết.
Mã hóa số học
Mã hóa cả chuỗi thành một khoảng con của [0, 1) có độ dài bằng xác suất của chuỗi; tiến sát entropy và dễ kết hợp với mô hình xác suất thích nghi.
Dung lượng kênh
C = max I(X;Y) theo phân phối đầu vào; kênh nhị phân đối xứng xác suất lật p có C = 1 − H₂(p), kênh xóa nhị phân xác suất xóa ε có C = 1 − ε.
Định lý mã hóa kênh
Với mọi tốc độ R < C tồn tại mã có xác suất lỗi nhỏ tùy ý khi độ dài khối đủ lớn; với R > C xác suất lỗi bị chặn dưới bởi một hằng số dương.
Dung lượng kênh Gauss và giới hạn Shannon
C = B log₂(1 + SNR) bit/s; khi băng thông tiến tới vô hạn, Eb/N0 tối thiểu để truyền tin cậy là ln 2, khoảng −1,59 dB.
Mã khối tuyến tính
Tập từ mã là không gian con của không gian vectơ nhị phân, mô tả bằng ma trận sinh G và ma trận kiểm tra H; giải mã bằng syndrome, khoảng cách tối thiểu quyết định số lỗi sửa được.
Mã chập và thuật toán Viterbi
Mã chập tạo bit mã từ cửa sổ trượt của bit vào; thuật toán Viterbi tìm đường có metric tốt nhất trên lưới trạng thái, là giải mã hợp lẽ cực đại.
Mã LDPC và truyền thông điệp
Mã khối có ma trận kiểm tra thưa, giải mã lặp bằng truyền thông điệp tổng – tích trên đồ thị Tanner; đạt hiệu năng rất gần dung lượng, dùng trong Wi-Fi, DVB-S2 và 5G NR.
Mã turbo
Ghép song song hai mã chập qua bộ xáo trộn, giải mã lặp trao đổi thông tin mềm giữa hai bộ giải mã; lần đầu cho thấy hiệu năng cách giới hạn Shannon dưới 1 dB.

Học xong để làm gì

  • Nén dữ liệu không tổn hao (ZIP, PNG, các bộ mã hóa entropy trong chuẩn nén ảnh và video)
  • Mã sửa lỗi của Wi-Fi, 4G/5G, truyền hình số vệ tinh DVB-S2 và thông tin vũ trụ
  • Bảo vệ dữ liệu lưu trữ: ổ SSD, đĩa quang, mã QR (Reed – Solomon) và hệ thống lưu trữ phân tán
  • Đánh giá giới hạn lý thuyết khi thiết kế hệ thống truyền thông và tuyến vệ tinh
  • Học máy và thống kê: hàm mất mát entropy chéo, cây quyết định, suy luận Bayes
  • Mật mã học và bảo mật thông tin: độ bất định của khóa, bảo mật lớp vật lý

Câu hỏi thường gặp

Lý thuyết thông tin có phải chỉ dành cho người làm viễn thông?

Không. Entropy và thông tin tương hỗ xuất hiện trong nén dữ liệu, học máy (entropy chéo, cây quyết định), thống kê, vật lý thống kê, sinh học và mật mã. Sách chính của MacKay cố ý nối lý thuyết thông tin với suy luận và mạng nơ-ron.

Vì sao chọn sách MacKay làm sách chính thay vì Cover và Thomas?

MacKay đọc miễn phí trên màn hình, giàu ví dụ, bài tập có lời giải và dẫn tới mã LDPC hiện đại; Cover và Thomas chặt chẽ và đầy đủ hơn về chứng minh nhưng khô hơn cho người tự học. Lộ trình dùng cả hai song song.

Cần toán đến mức nào?

Xác suất vững là đủ cho phần lớn chủ đề; phần mã khối cần đại số tuyến tính trên trường hai phần tử (cộng modulo 2), phần kênh Gauss cần tích phân và bất đẳng thức Jensen.

Định lý Shannon nói mã tốt tồn tại, vậy vì sao phải học nhiều loại mã?

Chứng minh dùng mã ngẫu nhiên, giải mã cần thời gian mũ theo độ dài khối nên không dùng được. Các họ mã có cấu trúc (Hamming, chập, LDPC, turbo, polar) là lời giải kỹ thuật cân bằng giữa hiệu năng, độ trễ và độ phức tạp.

Có thư viện nào để thử mã sửa lỗi mà không tự viết hết?

Nên tự viết mã Hamming và Viterbi để hiểu. Với LDPC và mã polar, có thể dùng các thư viện mã nguồn mở như AFF3CT hoặc Sionna để so sánh hiệu năng sau khi đã tự cài bản đơn giản.

Chọn nguồn tự học

Cần vững xác suất; đọc song song một giáo trình kinh điển với một nguồn nhiều ví dụ, và tự cài đặt mã Huffman, mã Hamming bằng Python để kiểm tra lý thuyết.