VietTechiesHIỂU CÔNG NGHỆ. MỞ GÓC NHÌN.
☰ Chuyên mục

Mã sửa lỗi Reed–Solomon: Vì sao 32 byte dư bảo đảm khôi phục 32 byte mất đã biết vị trí hoặc sửa 16 byte lỗi chưa biết vị trí?

25/10/2026 · VietTechies · Biên tập

Ảnh chụp cận cảnh từ bên cạnh các đĩa CD xếp chồng, cho thấy mép kim loại phản chiếu; mã sửa lỗi Reed–Solomon bảo vệ các bản âm thanh trên đĩa.


Trong mã Reed–Solomon, 32 byte dư có thể khôi phục 32 byte bị mất đã biết vị trí, nhưng chỉ sửa được 16 byte bị sai dữ liệu khi chưa biết vị trí lỗi. Sự đánh đổi này bắt nguồn từ các mã sửa lỗi mà Irving S. Reed và Gustave Solomon giới thiệu trong bài báo năm 1960, “Polynomial Codes over Certain Finite Fields.” Phương pháp của họ biểu diễn thông điệp bằng một đa thức rồi truyền thêm các giá trị tính từ đa thức đó, cung cấp đủ thông tin để bên nhận tái dựng dữ liệu bị hỏng trong một giới hạn xác định.

Reed và Solomon đề xuất mã hóa từng khối ký hiệu bằng cách tính giá trị đa thức trên một trường hữu hạn. Bài báo của họ lưu ý rằng việc nhóm các bit liên tiếp thành ký hiệu có thể khiến mã đặc biệt hữu ích khi lỗi xảy ra thành từng cụm.

Mã hóa bằng cách tính giá trị đa thức

Cơ chế cốt lõi của mã Reed–Solomon dựa trên đại số cơ bản. Hai giá trị của đa thức tại hai đầu vào khác nhau xác định duy nhất một đa thức có bậc không quá một. Ba giá trị tại ba đầu vào khác nhau xác định duy nhất một đa thức có bậc không quá hai. Tổng quát hơn, k giá trị tại các đầu vào khác nhau xác định duy nhất một đa thức mà ta biết có bậc nhỏ hơn k.

Để mã hóa dữ liệu theo nguyên lý này, bên gửi chia thông điệp thành từng khối gồm k ký hiệu, chẳng hạn các byte tám bit. k giá trị này đóng vai trò hệ số của một đa thức f(x) có bậc không quá k − 1. Thay vì chỉ truyền các hệ số ban đầu, bộ mã hóa tính giá trị đa thức tại n vị trí khác nhau, với n lớn hơn k. Các phép tính được thực hiện trên một trường hữu hạn, còn gọi là trường Galois: một tập giá trị cố định với các quy tắc cộng, trừ, nhân và chia cho giá trị khác không. Trường gồm 256 giá trị, viết là GF(256), biểu diễn các ký hiệu có kích thước một byte. Phép cộng dùng phép XOR (hoặc loại trừ) trên từng bit; phép nhân dùng các phép toán đa thức sao cho kết quả vẫn nằm trong cùng trường đó.

Vì đa thức ban đầu có bậc nhỏ hơn k, bên nhận chỉ cần thu được ít nhất k giá trị tính đúng từ đa thức là có thể lập một hệ phương trình tuyến tính và giải để tìm lại các hệ số ban đầu. Phép nội suy đa thức, chẳng hạn nội suy Lagrange, bảo đảm khôi phục chính xác thông điệp ban đầu từ bất kỳ tập con nào gồm các điểm tính giá trị còn nguyên vẹn và đáp ứng điều kiện trên.

Lượng dữ liệu dư: mất ký hiệu đã biết vị trí và lỗi chưa biết vị trí

Điểm đặc sắc của mã Reed–Solomon trong thực tế nằm ở cách tận dụng lượng dữ liệu dư. Hiệu giữa tổng số ký hiệu được truyền n và số ký hiệu của thông điệp ban đầu k chính là lượng ký hiệu kiểm tra chẵn lẻ, hay khả năng sửa chữa, n − k. Khả năng này phục hồi được bao nhiêu dữ liệu phụ thuộc trực tiếp vào việc bên nhận có biết dữ liệu hỏng ở đâu hay không.

Trong các hệ thống số, kỹ sư phân biệt hai dạng hư hại: mất ký hiệu đã biết vị trí (erasure) và lỗi chưa biết vị trí (unknown error). Trường hợp thứ nhất xảy ra khi hệ thống biết chính xác vị trí của ký hiệu bị mất. Chẳng hạn, trong mạng truyền gói tin, có thể dễ dàng nhận ra gói bị mất nhờ thông tin thứ tự trong phần đầu gói tin; trong bộ nhớ flash hoặc phương tiện lưu trữ từ tính, các dấu chỉ vị trí khuyết tật vật lý có thể chỉ ra những sector không đọc được. Khi đã biết vị trí ký hiệu, bộ giải mã chỉ cần tính các giá trị còn thiếu. Nếu chỉ có mất ký hiệu đã biết vị trí, mỗi ký hiệu dư có thể thay thế một ký hiệu bị mất. Một khối có n − k ký hiệu kiểm tra chẵn lẻ có thể khôi phục tối đa n − k ký hiệu bị mất đã biết vị trí.

Lỗi chưa biết vị trí tốn khả năng sửa chữa hơn nhiều. Khi các ký hiệu nhận được mang giá trị sai nhưng chưa biết sai ở đâu, bộ giải mã phải làm hai việc riêng biệt: xác định ký hiệu nào sai, rồi tính giá trị đúng của chúng. Do việc tìm vị trí lỗi đòi hỏi thêm các ràng buộc toán học, sửa một lỗi chưa biết vị trí tiêu tốn hai ký hiệu dư kiểm tra chẵn lẻ. Mã có n − k ký hiệu kiểm tra chẵn lẻ bảo đảm khôi phục duy nhất thông điệp với mọi cách phân bố tối đa floor((n − k) / 2) lỗi ký hiệu chưa biết vị trí; floor là phép lấy phần nguyên dưới. Khi có cả lỗi và ký hiệu bị mất đã biết vị trí, điều kiện bảo đảm là hai lần số lỗi chưa biết vị trí cộng với số ký hiệu bị mất đã biết vị trí không vượt quá n − k.

Một ví dụ điển hình là mã RS(255, 223) được dùng phổ biến, hoạt động trên các byte tám bit. Trong mỗi từ mã dài 255 byte, 223 byte chứa dữ liệu ban đầu và 32 byte chứa thông tin kiểm tra chẵn lẻ. 32 byte dư đó có thể tái dựng tối đa 32 byte bị mất đã biết vị trí, hoặc tìm và sửa tối đa 16 byte bị sai ở bất cứ đâu trong khối. Với cách mã hóa RS(255, 223) dạng hệ thống, 223 byte dữ liệu ban đầu được giữ nguyên bên cạnh 32 byte kiểm tra chẵn lẻ. Một cách xây dựng phổ biến là nối thêm các byte kiểm tra chẵn lẻ tính bằng phép chia đa thức; những cách xây dựng dạng hệ thống khác dùng ma trận sinh.

Từ không gian xa xôi đến đĩa CD

Quy trình giải mã ban đầu xét các tập con của những giá trị đa thức nhận được, nên rất tốn công tính toán với các khối dài. Các thuật toán ra đời sau tránh được cách xét vét cạn này: thuật toán giải mã Berlekamp–Massey xuất hiện vào cuối thập niên 1960, còn Berlekamp và Lloyd Welch phát triển một phương pháp hiệu quả khác vào thập niên 1980.

Khi việc giải mã hiệu quả trở nên khả thi, mã Reed–Solomon trở thành hạ tầng thiết yếu trong lưu trữ số và viễn thông. Trong lĩnh vực điện tử tiêu dùng, đĩa quang Compact Disc (CD) sử dụng mã Reed–Solomon đan xen chéo để bảo vệ âm thanh số. Vết xước hoặc bụi có thể cản trở việc đọc các ký hiệu được ghi liên tiếp. Mã Reed–Solomon đan xen chéo (CIRC) dùng ký hiệu tám bit và đan xen dữ liệu giữa các khối mã hóa kế tiếp để phân tán hư hại dạng cụm sang nhiều từ mã. Trong giới hạn sửa lỗi, bộ giải mã khôi phục âm thanh ban đầu; những lỗi chưa sửa được có thể được che đi bằng cách ước tính các mẫu âm thanh còn thiếu.

Trong lĩnh vực hàng không vũ trụ, Cơ quan Hàng không và Vũ trụ Quốc gia Hoa Kỳ (NASA) triển khai mã Reed–Solomon cho các sứ mệnh thăm dò hành tinh Voyager. Trong những lần Voyager 2 tiếp cận Sao Thiên Vương và Sao Hải Vương, mã Reed–Solomon giúp bảo vệ dữ liệu đo đạc từ xa trước lỗi truyền dẫn ở khoảng cách liên lạc xa hơn, kết hợp với mã chập để giảm tỷ lệ lỗi trong thông tin nhận được.

Giới hạn của khả năng khôi phục

Dù có khả năng sửa lỗi cao, mã Reed–Solomon vẫn chịu những giới hạn toán học nghiêm ngặt. Nếu không có thông tin bổ sung, khi mất quá n − k ký hiệu đã biết vị trí, số giá trị đa thức còn lại sẽ quá ít để xác định duy nhất thông điệp. Khi số lỗi vượt quá giới hạn sửa lỗi được bảo đảm, bộ giải mã được thiết kế để trả về một thông điệp trong giới hạn đó có thể báo thất bại hoặc trả về một khối sai. Một số cách phân bố lỗi vẫn cho phép khôi phục; một phương pháp khác, gọi là giải mã danh sách, có thể trả về nhiều thông điệp ứng viên khi vượt quá giới hạn ấy.

Các tài liệu kỹ thuật Internet thuộc loạt Request for Comments (RFC), trong đó có RFC 3453 và RFC 5510, mô tả cách sửa lỗi chuyển tiếp hỗ trợ truyền đa hướng (multicast) tin cậy: gửi dữ liệu đến nhiều bên nhận. Các lượt truyền dữ liệu sửa chữa có thể giúp nhiều bên nhận dù mỗi bên mất những phần dữ liệu khác nhau. Với mỗi khối nguồn, việc khôi phục đòi hỏi k ký hiệu mã hóa khác nhau bất kỳ, được nhận đúng và đã biết vị trí; mỗi gói tin có thể mang một hoặc nhiều ký hiệu.

Câu hỏi thực tế là bên nhận đã biết ký hiệu nào bị mất hay còn phải tìm ra ký hiệu nào bị sai. Trong ví dụ khối 255 byte, cùng 32 byte bổ sung cho phép khôi phục 32 byte bị mất đã biết vị trí hoặc sửa 16 byte bị lỗi chưa biết vị trí. Biết dữ liệu hỏng ở đâu giúp tăng gấp đôi số byte bị ảnh hưởng mà mã bảo đảm khôi phục được.

Bài liên quan

Đọc bằng ngôn ngữ khác: English

Nguồn