Lý thuyết mã hóa thiết yếu [pdf]

• Cuốn sách này tổng hợp toàn diện các khái niệm cốt lõi của lý thuyết mã hóa và những phát triển hiện đại
• Trình bày các nguyên lý cơ bản của mã sửa lỗi, cấu trúc và giới hạn của nhiều loại mã khác nhau, cùng các lĩnh vực ứng dụng thực tế
• Giải thích tập trung về lý thuyết Shannon và mã Hamming, cũng như các loại mã được dùng rộng rãi trong thực tế như Reed-Solomon
• Cũng cung cấp có hệ thống các trường hợp ứng dụng trong các hệ thống CNTT hiện đại như băm, kiểm tra nhóm, bảo vệ thông tin sinh trắc học
• Bao gồm cả phụ lục, bài tập và tài liệu tham khảo, được cấu thành như một tài liệu tham khảo hiệu quả cho cả người học lẫn người làm thực tế

---

Lời nói đầu

• Cuốn sách này dựa trên ghi chú bài giảng về lý thuyết mã hóa của Venkatesan Guruswami, Atri Rudra và Madhu Sudan
• Dựa trên nội dung các khóa học được giảng dạy tại University of Washington, CMU, University at Buffalo SUNY, Harvard, MIT, v.v.
• Nhận hỗ trợ từ NSF CAREER grant CCF-0844796
• Quan điểm và kết quả của các tác giả không đại diện cho lập trường chính thức của NSF
• Có thể sử dụng theo giấy phép Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License

Tóm tắt mục lục

Chương 1: Những câu hỏi nền tảng

• Mục đích của lý thuyết mã hóa, các định nghĩa cơ bản và mã
• Khái niệm sửa lỗi và khoảng cách của mã, mã Hamming và các cận
• Phân loại các họ mã, kèm bài tập và tài liệu tham khảo

Phần I: Cơ sở

• Giới thiệu các cấu trúc toán học như mã tuyến tính, trường hữu hạn, không gian vector
• Giải thích giải mã hiệu quả cho mã Hamming và mã đối ngẫu
• Bao gồm bài tập và tài liệu tham khảo

Chương 3: Xác suất và hàm entropy q-ary

• Tìm hiểu cơ sở xác suất, phương pháp xác suất và hàm entropy q-ary
• Cung cấp bài tập và tài liệu tham khảo liên quan

Phần II: Tổ hợp

• Giải thích các cận mã và giới hạn như Hamming, Gilbert-Varshamov, Singleton, Plotkin
• Ứng dụng mã Reed-Solomon, đa thức và trường hữu hạn
• Mô hình nhiễu của Shannon và giới hạn truyền thông tin, so sánh với Hamming
• Mở rộng sang list decoding, Johnson Bound và dung lượng của list decoding
• Các lý thuyết giới hạn mới như Elias-Bassalygo, cận quy hoạch tuyến tính

Phần III: Các cấu trúc mã đa dạng

• Mã dựa trên đa thức và ứng dụng trên trường nhị phân, cấu trúc mã tổng quát
• Nối mã (concatenation), Zyablov Bound, các kỹ thuật nối nâng cao và phần tổng kết
• Đồ thị expander và mã expander, khuếch đại khoảng cách và các trường hợp ứng dụng

Phần IV: Thuật toán

• Các phương pháp giải mã hiệu quả cho Reed-Solomon, Reed-Muller và mã nối
• Phương pháp đạt dung lượng kênh BSCp và cấu trúc mã trong/ngoài
• Mã Polar, nguyên lý polarization và triển khai bộ mã hóa/bộ giải mã, năng lực list decoding
• Giải thích các mã có thể mã hóa thời gian tuyến tính và phục hồi cục bộ

Phần V: Ứng dụng

• Lý thuyết băm và tránh va chạm, hàm băm gần như phổ dụng, chứng minh sở hữu dữ liệu
• Khái niệm Fuzzy Vault để bảo vệ xác thực sinh trắc học (dấu vân tay)
• Hình thức hóa kiểm tra nhóm (Group Testing), các cận và ứng dụng vào thuật toán data stream
• Độ phức tạp của bài toán mã hóa: bài toán codeword gần nhất, giải mã dựa trên tiền xử lý, xấp xỉ hóa, bài toán khoảng cách tối thiểu, v.v.
• Các chủ đề hỗ trợ về độ phức tạp tính toán như độ phức tạp truyền thông, ngẫu nhiên hóa, Pseudorandomness, Hardcore Predicates, các bài toán độ khó trung bình, v.v.

Phụ lục

• Bảng ký hiệu, các bất đẳng thức và đẳng thức hữu ích, ký hiệu tiệm cận, nền tảng cơ bản về thuật toán và độ phức tạp
• Thuật toán đại số, giới thiệu trường hữu hạn và phép toán đa thức
• Các khái niệm chính của lý thuyết thông tin: entropy, entropy có điều kiện, thông tin tương hỗ, v.v.

Đặc điểm và giá trị ứng dụng

• Cung cấp toàn diện nền tảng lý thuyết và cách áp dụng thực tiễn cho các thuật toán sửa lỗi thiết yếu trong thông tin liên lạc hiện đại, lưu trữ dữ liệu, hệ mật mã
• Sắp xếp từ khái niệm cơ bản đến xu hướng mới nhất và ứng dụng thực tế, truyền tải kiến thức rộng cho lập trình viên mới, nhà nghiên cứu và người làm CNTT
• Mỗi chương đều có bài tập và tài liệu tham khảo, thuận lợi cho học tập và tự học
• Có thể tự do sử dụng cho mục đích học thuật/phi thương mại theo giấy phép Creative Commons

[GN⁺]

Ý kiến trên Hacker News

• Tôi muốn nhấn mạnh rằng "The Mathematical Theory of Communication" của Claude Shannon là một tài liệu nền tảng về lý thuyết thông tin được giải thích đủ dễ để hầu như ai cũng có thể đọc, ngay cả khi không có nền tảng toán học sâu liên kết

  • Tôi muốn nói rằng Shannon thực sự là một nhân vật rất phù hợp để bắt đầu làm quen với tư duy toán học. Ban đầu ông đã xây dựng khái niệm entropy thông tin chỉ dựa trên các tính chất cần có, mà không gán cho nó bất kỳ ý nghĩa nào. Điều đáng kinh ngạc là định nghĩa được tạo ra một cách gần như tình cờ này lại gần như trùng khớp với entropy nhiệt động học trong vật lý, và Von Neumann là người đã chỉ ra điều đó rồi đặt tên cho nó. Toán học thường phát triển theo kiểu lập luận logic như "nếu nó phải thỏa mãn các quy tắc này", nên đó cũng là một trong những lý do khiến nhiều người thấy nó khó. Bài báo của Shannon chỉ đặt ra bộ khung cho lý thuyết mã hóa, còn cách triển khai thực tế thì không có trong bài. Trước đây tôi từng điều hành một câu lạc bộ đọc sách ở startup cũ, nơi chúng tôi cùng đọc bản sách của bài báo này, và tôi muốn khuyến nghị đây là một trải nghiệm rất tốt để hiểu lý thuyết thông tin cũng như toán học nói chung

• Vì lĩnh vực nén không mất dữ liệu có liên hệ chặt chẽ với AI tạo sinh, nên sẽ thú vị hơn nếu bổ sung thêm nội dung về phần này. Tôi muốn giới thiệu một luận án tiến sĩ trình bày rất tốt về mối liên hệ giữa nén không mất dữ liệu và machine learning liên kết

  • Thực ra cũng không nhất thiết phải giới hạn điều này chỉ trong nén không mất dữ liệu. Gần như mọi machine learning đều có thể được hiểu như một dạng nén nào đó, chủ yếu là nén mất dữ liệu. Ví dụ, nếu chỉ gửi semantic embedding qua kênh truyền thì vẫn có thể thực hiện tác vụ mà không cần toàn bộ văn bản gốc, vì bản thân các giá trị embedding đã chứa đủ thông tin. Phân loại dữ liệu rốt cuộc cũng là quá trình giữ lại chỉ biểu diễn tiềm ẩn của các danh mục chung rồi loại bỏ phần còn lại. Với AI tạo sinh, chính vì chúng ta thực hiện 'nén mất dữ liệu' nên nó mới hoạt động tốt. Ta cố ý vứt bỏ một phần thông tin, và chỉ khi phải suy luận lấp các khoảng trống đó thì con đường khái quát hóa mới mở ra. Một LLM không mất dữ liệu thực ra cũng không có gì đặc biệt thú vị trong sử dụng thực tế. Tuy vậy, bài báo tôi gợi ý rất đặc biệt ở chỗ nó bàn về nén không mất dữ liệu, điều hiếm thấy ngay cả trong lĩnh vực machine learning

• Có một tài liệu tốt được biên soạn gần đây là giáo trình <i>Information Theory: From Coding to Learning</i>. Cũng có bản PDF trực tuyến nên đáng để tham khảo liên kết

  • Tôi cũng muốn giới thiệu cuốn <i>Information Theory, Inference, and Learning Algorithms</i> của David MacKay liên kết

• Để trả lời câu hỏi "coding" ở đây có nghĩa là gì, thì trong ngữ cảnh này nó chỉ hành vi encoding/decoding nhằm chuyển đổi thông tin từ một biểu diễn sang một biểu diễn khác. Những hệ thống như vậy được gọi là code, và được thiết kế để chống lại nhiễu, biến đổi hoặc nghe lén trong quá trình truyền thông tin. Nói cách khác, code (coding) được sử dụng trong rất nhiều lĩnh vực như nén dữ liệu, mã hóa, phát hiện và sửa lỗi, truyền và lưu trữ dữ liệu liên kết

  • Đặc biệt, cuốn sách được nhắc tới tập trung vào error correcting code. Khi truyền thông điệp, người ta gắn thêm dữ liệu để có thể khôi phục phần bị mất. Khó khăn cần giải quyết là thiết kế dữ liệu bổ sung sao cho có thể phục hồi đủ số lỗi với overhead tối thiểu và thời gian tính toán hợp lý. Kỹ thuật này thực sự được dùng ở rất nhiều nơi như WiFi, ổ cứng, mã QR và RAM. Ví dụ, ECC trong ECC RAM chính là error correcting code. Gần đây đây là công nghệ đã được bắt buộc một phần trong DDR5

• Vì đang có không khí chia sẻ ebook CS miễn phí, tôi cũng rất muốn giới thiệu cuốn Algorithms của Jeff E. Đây là sách phải đọc đối với ai muốn học thuật toán hoặc ôn lại kỹ năng liên kết

• Tôi đã đọc vài chương của cuốn này và thực sự rất hài lòng. Tôi dự định sẽ đọc chậm rãi trong vài tuần, hoặc thậm chí vài tháng tới

• Nếu muốn học sâu hơn về lý thuyết thông tin và lý thuyết mã hóa, tôi cũng muốn giới thiệu các tài liệu sau. Về error correcting code, có "Error-Correcting Codes" của W. Wesley Peterson và E. J. Weldon, Jr.; còn về đại số trừu tượng, đặc biệt là lý thuyết trường, thì "Commutative Algebra" của Oscar Zariski và Pierre Samuel là tài liệu tham khảo đáng xem

  • Lệnh LaTeX không hoạt động ở đây

• Nếu phải chọn vài cuốn sách muốn giới thiệu cho người mới bắt đầu, thì sẽ là:

  1. <i>An Introduction to Information Theory, Symbols, Signals and Noise</i> của John R. Pierce - một tác phẩm kinh điển rất phù hợp để hiểu khái niệm và xây dựng trực giác. Các sách khác của cùng tác giả cũng rất xuất sắc
  2. <i>Information Theory: A Tutorial Introduction</i> của James V. Stone - một sách nhập môn dễ đọc và chất lượng. Các tài liệu tutorial khác của tác giả này cũng hữu ích
  3. <i>A Student's Guide to Coding and Information Theory</i> của Stefan Moser và Po-ning chen - một cẩm nang ngắn gọn, rõ ràng; các sách khác trong cùng bộ cũng đáng để giới thiệu

• Mỗi khi ai đó nói "đây là thứ thiết yếu", với một người như tôi chỉ mới từng chạm nhẹ vào chủ đề đó trong khoa, đó lúc nào cũng là một khoảnh khắc hơi đáng sợ

  • "Thiết yếu" trong môn học này không có nghĩa là nội dung mà mọi sinh viên khoa học máy tính đều nhất thiết phải biết, mà là nó chứa đựng tinh túy của lý thuyết mã hóa. Đồng tác giả của cuốn sách hiện đang trực tiếp giảng dạy tại trường chúng tôi, và đây là một môn tự chọn bậc trên với khối lượng toán học áp đảo. Trong chương trình khoa học máy tính 4 năm, chủ yếu chỉ một số rất ít sinh viên năm cuối học môn này, và những người bạn quanh tôi từng học đều là những người thích chứng minh toán học. Họ rất thích môn này

  • Hễ thấy ghi "thiết yếu" hoặc "nhập môn" thì đó thường là dấu hiệu báo trước một giáo trình cực kỳ cô đọng đang chờ bạn