Bit bị lật
Syndrome
Đã nhận
Bit dữ liệu trên mỗi bit gửi

Thêm về mã sửa lỗi

Mô phỏng mã sửa lỗi

Mọi thông điệp truyền qua dây dẫn, qua không khí hay qua một chiếc đĩa bị trầy xước đều nhiễm lỗi: các bit bị lật từ 0 thành 1 và ngược lại. Mã sửa lỗi thêm vào vài bit phụ được chọn cẩn thận để bên nhận có thể tìm ra và sửa chỗ hỏng mà không phải yêu cầu gửi lại. Hãy nhập bốn bit dữ liệu, xem mã của Richard Hamming biến chúng thành bảy bit, lật bất kỳ bit nào bạn muốn và xem ba vòng tròn chồng lên nhau chỉ thẳng vào lỗi. Sau đó hãy gửi cả một thông điệp qua kênh nhiễu và so sánh những gì nhận được khi có và không có mã. Hãy nhập bốn bit dữ liệu, chẳng hạn 1011, và ứng dụng sẽ thêm ba bit chẵn lẻ để tạo thành một từ mã Hamming 7 bit. Nhấp vào bất kỳ bit nào, trong các vòng tròn hoặc trong hàng, để lật nó như nhiễu sẽ làm; nhấp lần nữa để lật nó trở lại. Mỗi vòng tròn phải chứa một số chẵn chữ số 1: các vòng tròn không đạt sẽ chỉ ra bit sai, và bộ giải mã lật nó trở lại. Hãy bật bit chẵn lẻ bổ sung để thấy hai lỗi được phát hiện thay vì bị sửa sai. Bên dưới, hãy gửi một đoạn văn bản qua kênh nhiễu, có và không có mã.

Cách nó hoạt động

  1. Nhập bốn bit dữ liệu và xem từ mã bảy bit cùng ba bit chẵn lẻ của nó, trong các vòng tròn và trên một hàng.
  2. Nhấp vào các bit để lật chúng và quan sát vòng tròn nào không đạt, syndrome chỉ đến đâu và bộ giải mã có sửa lại được từ mã hay không.
  3. Bật bit chẵn lẻ bổ sung, rồi gửi một thông điệp qua kênh nhiễu và so sánh kết quả khi có và không có mã.

Mã Hamming tìm ra lỗi như thế nào

Bảy bit được đánh số từ 1 đến 7. Các bit 1, 2 và 4 là bit chẵn lẻ, còn bốn bit dữ liệu nằm ở vị trí 3, 5, 6 và 7. Bit chẵn lẻ 1 làm cho số chữ số 1 là chẵn trong các vị trí 1, 3, 5 và 7, tức là những vị trí có số thứ tự viết ở hệ nhị phân tận cùng bằng 1; bit 2 làm điều tương tự cho 2, 3, 6 và 7, và bit 4 cho 4, 5, 6 và 7. Khi vẽ thành ba vòng tròn chồng lên nhau, mỗi bit nằm đúng trong những vòng tròn kiểm tra nó. Khi một bit bị lật, các vòng tròn chứa nó trở thành lẻ. Hãy đọc các phép kiểm tra không đạt như một số nhị phân, gọi là syndrome, và bạn sẽ có vị trí của bit sai.

Một bit bổ sung mang lại gì

Khi có hai bit bị lật, syndrome chỉ đến một bit thứ ba vô can, và bộ giải mã khiến mọi chuyện tệ hơn. Thêm một bit thứ tám làm cho cả từ mã có tính chẵn sẽ khắc phục điều đó: một lỗi làm thay đổi tính chẵn lẻ tổng thể, còn hai lỗi giữ nó chẵn trong khi một số vòng tròn không đạt. Mã mở rộng, được gọi là SECDED, viết tắt của sửa lỗi đơn, phát hiện lỗi kép, sửa được một lỗi và phát hiện tin cậy hai lỗi, để bên nhận có thể yêu cầu gửi lại khối đó. Đây là mã được dùng trong bộ nhớ ECC của máy chủ. Trên một kênh nhiễu, mã này biến nhiều lỗi rải rác thành chỉ vài lỗi, miễn là hai lần lật hiếm khi rơi vào cùng một khối.

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

Vì sao các bit chẵn lẻ nằm ở vị trí 1, 2 và 4?

Vì đó là các lũy thừa của hai, và mỗi số chỉ có đúng một chữ số 1 trong hệ nhị phân. Bit chẵn lẻ 2ᵏ kiểm tra mọi vị trí có số nhị phân mang chữ số 1 ở hàng k. Một bit bị lật ở vị trí 6 = 110 trong hệ nhị phân làm hỏng các phép kiểm tra của 2 và 4 mà không ảnh hưởng đến 1, và các phép kiểm tra không đạt ghép lại thành 110, chính là vị trí đó.

Sự bảo vệ này tốn bao nhiêu?

Mã (7,4) gửi 7 bit cho mỗi 4 bit dữ liệu, tức tỉ lệ 4/7: thêm 75%. Mã mở rộng gửi 8 cho 4, gấp đôi. Các mã Hamming dài hơn thì rẻ hơn: 15 bit mang 11 bit dữ liệu, 31 bit mang 26. Các mã hiện đại như LDPC và mã cực (polar), được dùng trong Wi-Fi và 5G, tiến rất gần đến tỉ lệ tốt nhất mà Claude Shannon đã chứng minh là khả thi vào năm 1948.

Điều gì xảy ra khi có ba lỗi?

Mã Hamming thông thường có thể bị đánh lừa hoàn toàn: hai từ mã bất kỳ khác nhau ở ít nhất ba bit, nên ba lần lật có thể biến một từ mã hợp lệ thành một từ mã khác, và không phép kiểm tra nào thất bại. Ứng dụng báo trường hợp này là lỗi không bị phát hiện. Các hệ thống thực tế giữ cho những trường hợp như vậy hiếm xảy ra bằng cách chọn một mã đủ mạnh so với mức nhiễu.

Mã sửa lỗi được dùng ở đâu?

Gần như ở mọi nơi dữ liệu số được truyền đi hoặc lưu trữ: bộ nhớ máy tính ECC, ổ cứng và SSD, đĩa CD, DVD và Blu-ray, mã QR vẫn đọc được khi bị rách mất một phần, điện thoại di động và Wi-Fi, truyền hình số và tin nhắn từ các tàu thăm dò vũ trụ như Voyager, vốn vẫn đang gửi dữ liệu từ bên ngoài Hệ Mặt Trời.

Thông điệp của tôi có bị gửi đi đâu không?

Không. Kênh nhiễu được mô phỏng ngay trong trình duyệt của bạn, và thông điệp cùng các thiết lập của bạn được lưu trong bộ nhớ cục bộ của trình duyệt này.

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.

Tới trình chỉnh sửa