Giải thích mã sửa lỗi

Không có kênh truyền nào hoàn hảo. Tia vũ trụ lật các bit trong bộ nhớ, vết xước xóa mất một phần đĩa, và tín hiệu vô tuyến yếu dần. Thay vì trông chờ vào may mắn, các hệ thống số thêm vào phần dư thừa một cách khéo léo, để bên nhận có thể suy ra những gì đã được gửi ngay cả khi một phần đến nơi bị sai. Toán học của các mã này, khởi đầu vào cuối những năm 1940, đang âm thầm bảo vệ gần như mọi bit mà chúng ta lưu trữ hay gửi đi.

Ba vòng tròn chồng lên nhau chứa bảy bit của một từ mã Hamming, một vòng tròn được tô sáng tại nơi phép kiểm tra chẵn lẻ không đạt
Ba vòng tròn chồng lên nhau chứa bảy bit của một từ mã Hamming, một vòng tròn được tô sáng tại nơi phép kiểm tra chẵn lẻ không đạt

Phát hiện lỗi bằng tính chẵn lẻ

Cách bảo vệ đơn giản nhất là một bit chẵn lẻ duy nhất: thêm một số 1 hoặc 0 để tổng số chữ số 1 là chẵn. Nếu một bit bị lật trên đường truyền, số đếm trở thành lẻ và bên nhận biết đã có gì đó sai. Tính chẵn lẻ không thể cho biết bit nào sai, và hai lần lật triệt tiêu nhau mà không bị phát hiện, nhưng nó rẻ, và đã được dùng hàng chục năm trong bộ nhớ và các đường truyền nối tiếp. Tuy vậy, phát hiện lỗi mới chỉ là một nửa công việc: sau đó dữ liệu phải được gửi lại.

Sửa lỗi bằng cách lặp lại

Để sửa lỗi mà không phải yêu cầu gửi lại, bên nhận cần đủ dư thừa để áp đảo lỗi bằng biểu quyết. Gửi mỗi bit ba lần, 000 hoặc 111, cho phép bên nhận lấy theo đa số: một lần lật trong một bộ ba sẽ được sửa. Cái giá rất đắt: ba bit cho mỗi bit dữ liệu, và hai lần lật trong cùng một bộ ba vẫn thắng. Câu hỏi khởi đầu cho lý thuyết mã hóa là liệu có thể làm tốt hơn hay không.

Mã của Hamming

Năm 1947, Richard Hamming làm việc tại Bell Labs với một máy tính rơ-le đọc chương trình từ thẻ đục lỗ. Khi phát hiện lỗi vào cuối tuần, máy chỉ đơn giản dừng lại, và đến thứ Hai Hamming quay lại chỉ thấy những lượt chạy bị lãng phí. Ông tự hỏi: nếu một cỗ máy có thể phát hiện lỗi, tại sao nó không thể xác định vị trí và sửa lỗi đó? Câu trả lời của ông, công bố năm 1950, gửi 4 bit dữ liệu thành 7 bit. Ba bit chẵn lẻ, ở các vị trí 1, 2 và 4, mỗi bit kiểm tra một nhóm vị trí khác nhau chồng lên nhau, được chọn sao cho mỗi lỗi đơn làm hỏng một tổ hợp kiểm tra riêng biệt.

Syndrome

Bên nhận tính lại ba phép kiểm tra. Nếu tất cả đều đạt, từ mã được chấp nhận. Nếu có phép không đạt, việc viết các phép kiểm tra không đạt thành các chữ số nhị phân, với phép kiểm tra 4 là chữ số cao nhất, sẽ cho một số từ 1 đến 7: đó là syndrome (hội chứng), chính xác bằng vị trí của bit bị lật. Lật nó trở lại sẽ khôi phục từ mã. Mẹo này hiệu quả vì các vị trí được đánh số sao cho khai triển nhị phân của mỗi vị trí liệt kê các phép kiểm tra mà nó thuộc về, và đó cũng là lý do mã này trông thật gọn gàng khi được vẽ thành ba vòng tròn chồng lên nhau.

Khoảng cách Hamming

Khoảng cách Hamming giữa hai từ là số vị trí mà chúng khác nhau. Trong mã (7,4), hai từ mã bất kỳ cách nhau ít nhất 3. Một từ có một lỗi vẫn cách từ mã đã gửi 1 đơn vị và cách mọi từ mã khác ít nhất 2, nên giải mã về từ mã gần nhất sẽ sửa được lỗi đó. Nói chung, một mã có các từ mã cách nhau ít nhất d sẽ phát hiện được d − 1 lỗi và sửa được (d − 1)/2 lỗi, làm tròn xuống. Thêm một bit chẵn lẻ tổng thể sẽ nâng khoảng cách lên 4, cho ra mã mở rộng sửa được một lỗi và phát hiện được hai lỗi.

Giới hạn Shannon

Năm 1948, hai năm trước bài báo của Hamming, Claude Shannon đã chứng minh một định lý đáng kinh ngạc. Mỗi kênh nhiễu đều có một dung lượng, và dữ liệu có thể được gửi ở bất kỳ tốc độ nào dưới mức đó với số lỗi ít tùy ý, bằng cách dùng các mã đủ dài; vượt quá mức đó thì không thể tránh khỏi lỗi. Shannon chứng minh rằng những mã như vậy tồn tại nhưng không chỉ ra cách xây dựng chúng. Việc tìm ra các mã thực tế tiến gần đến giới hạn của ông mất nửa thế kỷ, từ mã Reed-Solomon năm 1960 đến mã turbo năm 1993 và việc tái phát hiện mã kiểm tra chẵn lẻ mật độ thấp (LDPC).

Claude Shannon, năm 1948 tại Bell Labs đã xác định chính xác lượng thông tin trong một thông điệp và đo bằng bit.
Claude Shannon, năm 1948 tại Bell Labs đã xác định chính xác lượng thông tin trong một thông điệp và đo bằng bit.

Mã ở quanh ta

Mã Reed-Solomon giúp đĩa CD vẫn phát được dù bị trầy xước và mã QR vẫn quét được khi có tới 30% ký hiệu bị hỏng. Bộ nhớ máy chủ dùng mã Hamming mở rộng để sửa các bit đơn bị lật do tia vũ trụ. Những bức ảnh các hành tinh vòng ngoài của Voyager được bảo vệ bằng mã Golay và sau đó là mã Reed-Solomon, còn các mã LDPC và mã cực của 5G và Wi-Fi khai thác gần như từng bit mà kênh truyền cho phép. Ngay cả mã vạch trên một cuốn sách và chữ số cuối cùng của số tài khoản ngân hàng cũng là những mã phát hiện lỗi đơn giản.

Khám phá

Hãy mở trình mô phỏng mã sửa lỗi để mã hóa bốn bit dữ liệu bất kỳ bằng mã Hamming (7,4), lật các bit bằng cách nhấp vào chúng trong các vòng tròn hoặc trong hàng, và xem các vòng tròn không đạt cùng syndrome chỉ ra lỗi trước khi bộ giải mã sửa nó. Hãy bật bit chẵn lẻ bổ sung để thấy lỗi kép được phát hiện, và gửi một thông điệp qua kênh nhiễu để so sánh những gì nhận được khi có và không có mã.

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

Phát hiện lỗi và sửa lỗi khác nhau như thế nào?

Phát hiện lỗi chỉ cho bên nhận biết có gì đó sai, nên bên nhận phải yêu cầu gửi lại dữ liệu; bit chẵn lẻ hay tổng kiểm tra (checksum) làm việc này. Sửa lỗi cho phép bên nhận tái tạo bản gốc mà không cần yêu cầu, điều này cần nhiều dư thừa hơn. Các hệ thống không thể yêu cầu gửi lại, như một tàu thăm dò vũ trụ cách xa hàng triệu kilômét hay một đĩa DVD, phải dựa vào sửa lỗi.

Sao không gửi mọi thứ hai lần cho xong?

Hai bản sao cho thấy đã có lỗi xảy ra nhưng không cho biết bản nào đúng, và chúng làm chi phí tăng gấp đôi. Ba bản sao cho phép biểu quyết theo đa số nhưng làm chi phí tăng gấp ba. Mã Hamming sửa được một lỗi trong mỗi khối bảy bit với số bit chưa đến gấp đôi, và các mã dài hơn còn làm tốt hơn nhiều.

Richard Hamming là ai?

Một nhà toán học người Mỹ (1915–1998), từng làm việc trong Dự án Manhattan và sau đó ba mươi năm tại Bell Labs. Ngoài các mã của mình, ông còn được biết đến với cửa sổ Hamming trong xử lý tín hiệu, với khoảng cách Hamming và với bài giảng You and Your Research. Ông nhận Giải thưởng Turing năm 1968.

Một mã có thể sửa bất kỳ số lỗi nào không?

Chỉ khi có đủ dư thừa. Một mã có thể sửa tối đa (d − 1)/2 lỗi mỗi khối, trong đó d là khoảng cách nhỏ nhất giữa các từ mã, và các mã dài hơn với nhiều bit kiểm tra hơn đạt được d lớn hơn. Định lý Shannon đặt ra giới hạn tối thượng: không mã nào có thể vượt qua dung lượng của kênh.

Sẵn sàng thử chưa?

Mở PictorX trong trình duyệt — không cần cài đặt, không cần thẻ tín dụng để bắt đầu.

Mở trình mô phỏng mã sửa lỗi