Mã Hamming

Lịch sử

Trong những năm của thập niên kỷ 1940, Hamming làm việc tại Bell Labs trên máy tính Bell Model V, một máy điện cơ (electromechanical) dùng rơ-le (relay-based), với tốc độ rất chậm, mấy giây đồng hồ một chu kỳ máy. Nhập liệu được cho vào máy bằng những cái thẻ đục lỗ (punch cards), và hầu như máy luôn luôn gây lỗi trong khi đọc. Trong những ngày làm việc trong tuần, những mã đặc biệt được dùng để tìm ra lỗi và mỗi khi tìm được, nó nhấp nháy đèn báo hiệu, báo cho người điều khiển biết để họ sửa, điều chỉnh máy lại. Trong thời gian ngoài giờ làm việc hoặc trong những ngày cuối tuần, khi người điều khiển máy không có mặt, mỗi khi có lỗi xảy ra, máy tính tự động bỏ qua chương trình đương chạy và chuyển sang công việc khác.
Hamming thường làm việc trong những ngày cuối tuần và ông càng ngày càng trở nên bực tức mỗi khi ông phải khởi động lại các chương trình ứng dụng từ đầu, do chất lượng kém, không đáng tin cậy (unreliability) của bộ máy đọc các thẻ đục lỗ. Mấy năm tiếp theo đó, ông dồn tâm lực vào việc xây dựng hằng loạt các thuật toán có hiệu quả cao để giải quyết vấn đề sửa lỗi. Năm 1950, ông đã công bố một phương pháp mà hiện nay được biết là Mã Hamming. Một số chương trình ứng dụng hiện thời vẫn còn sử dụng mã này của ông.

Các mã trước thời kỳ của Hamming

Nhiều mã phát hiện lỗi đơn giản đã được sử dụng trước khi có mã Hamming, nhưng không có mã nào hiệu quả bằng mã Hamming với một tổng phí tương đương.

Mã hai-trong-năm

Trong những năm của thập niên kỷ 1940, Bell có sử dụng một mã hiệu phức tạp hơn một chút, gọi là mã hai-trong-năm (two-out-of-five code). Mã này đảm bảo mỗi một khối 5 bit (còn được gọi là khối-5) có chính xác hai bit có giá trị bằng 1. Máy tính có thể nhận ra là dữ liệu nhập vào có lỗi nếu trong một khối 5 bit không 2 bit có giá trị bằng 1. Tuy thế, mã hai-trong-năm cũng chỉ có thể phát hiện được một đơn vị bit mà thôi; nếu trong cùng một khối, một bit bị lộn ngược thành giá trị 1, và một bit khác bị lộn ngược thành giá trị 0, quy luật hai-trong-năm vẫn cho một giá trị đúng (remained true), và do đó nó không phát hiện là có lỗi xảy ra.

Mã Hamming (7,4)

Hiện thời, khi nói đến mã Hamming chúng ta thực ra là muốn nói đến mã (7,4) mà Hamming công bố năm 1950. Với mỗi nhóm 4 bit dữ liệu, mã Hamming thêm 3 bit kiểm tra. Thuật toán (7,4) của Hamming có thể sửa chữa bất cứ một bit lỗi nào, và phát hiện tất cả lỗi của 1 bit, và các lỗi của 2 bit gây ra. Điều này có nghĩa là đối với tất cả các phương tiện truyền thông không có chùm lỗi đột phát (burst errors) xảy ra, mã (7,4) của Hamming rất có hiệu quả (trừ phi phương tiện truyền thông có độ nhiễu rất cao thì nó mới có thể gây cho 2 bit trong số 7 bit truyền bị đảo lộn).

Mã Hamming và bit chẵn lẻ bổ sung

Nếu chúng ta bổ sung thêm một bit vào mã Hamming, thì mã này có thể dùng để phát hiện những lỗi gây ra do 2 bit bị lỗi, và đồng thời nó không cản trở việc sửa các lỗi do một bit gây ra.  Nếu không bổ sung một bit vào thêm, thì mã này có thể phát hiện các lỗi do một bit, hai bit, ba bit gây ra, song nó sẽ cản trở việc sửa các lỗi do một bit bị đảo lộn. Bit bổ sung là bit được áp dụng cho tất cả các bit sau khi tất cả các bit kiểm của mã Hamming đã được thêm vào.
Khi sử dụng tính sửa lỗi của mã, nếu lỗi ở một bit chẵn lẻ bị phát hiện và mã Hamming báo hiệu là có lỗi xảy ra thì chúng ta có thể sửa lỗi này, song nếu chúng ta không phát hiện được lỗi trong bit chẵn lẻ, nhưng mã Hamming báo hiệu là có lỗi xảy ra, thì chúng ta có thể cho rằng lỗi này là do 2 bit bị đổi cùng một lúc. Tuy chúng ta phát hiện được nó, nhưng không thể sửa lỗi được.