Máy tính bỏ dở công việc của Richard Hamming hai cuối tuần liền. Ông đáp lại bằng mã Hamming.

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

Năm 1947, một máy tính rơ-le của Bell Labs bỏ dở các phép tính của Richard Hamming hai cuối tuần liền, và câu hỏi mà ông đặt ra sau chuyện đó đã dẫn tới mã Hamming. Ngày nay, các biến thể của mã này vẫn đang sửa lỗi trong bộ nhớ máy tính.

Cỗ máy biết rằng đã có gì đó trục trặc. Chính điều đó mới khiến người ta phát điên.

Hamming là một nhà toán học, vào làm ở Bell Labs từ năm 1946. Ông đang dùng một máy tính rơ-le do công ty chế tạo cho khu thử nghiệm Aberdeen Proving Ground của Lục quân Mỹ, một trong những cỗ máy mà bài báo năm 1950 của ông gọi là Model 5. Cỗ máy này hoạt động tại tòa nhà West Street của Bell Labs ở Manhattan. Hamming làm việc ở Murray Hill, bang New Jersey, và có thể đi nhờ chiếc xe limousine chở thư của công ty để vào thành phố.

Rơ-le hỏng đủ thường xuyên để thành vấn đề. Bài báo năm 1950 của Hamming cho biết trong thời gian đầu hoạt động, hai cỗ máy chế tạo cho Aberdeen, với tổng cộng 8.900 rơ-le, gặp khoảng hai hoặc ba lần hỏng rơ-le mỗi ngày, tức chừng một lần trên hai đến ba triệu lượt đóng ngắt. Các cỗ máy phát hiện những lỗi đó bằng mã hai-trong-năm (two-out-of-five), loại mã cũng được dùng trong hệ thống chuyển mạch điện thoại của Bell: mỗi chữ số hợp lệ có đúng hai trong năm vị trí ở trạng thái bật, nên một lỗi đơn lẻ sẽ tạo ra một tổ hợp mà máy có thể loại bỏ.

Khi một phép kiểm tra không đạt, máy thử lại. Sau ba lần thất bại, máy bỏ dở bài toán đó và chuyển sang bài tiếp theo.

Hamming thường giao việc cho máy vào cuối ngày thứ Sáu, rồi thứ Hai quay lại lấy kết quả. Một thứ Hai nọ, mọi bài toán đều đã bị máy bỏ dở. Sang cuối tuần sau, chuyện đó lặp lại.

Về sau, ông nhớ lại phản ứng của mình trong một cuộc phỏng vấn ghi âm, được trích trong cuốn sách năm 1983 của Thomas M. Thompson về lịch sử các mã sửa lỗi: “Chết tiệt, nếu máy đã phát hiện được lỗi thì sao nó lại không thể xác định vị trí của lỗi rồi sửa lỗi đó?”

Trong một bài giảng năm 1995, Hamming giải thích vì sao chỉ cần biết vị trí là đủ. Ở hệ nhị phân, một bit sai chỉ có thể nhận đúng một giá trị khác: “nếu máy có thể cho tôi biết lỗi nằm ở đâu, tôi có thể đổi bit đó từ 1 thành 0, hoặc từ 0 thành 1.”

Hamming đi từ lưới kiểm tra chẵn lẻ đến mã của mình như thế nào

Cách khắc phục dễ thấy nhất thì tốn kém. Hamming từng bàn đến cách này từ nhiều năm trước: chế tạo ba cỗ máy rồi để các mạch điện biểu quyết theo đa số. Ông hỏi các sinh viên của mình: “Nhưng ai lại muốn chế tạo ba cỗ máy, kèm cả các mạch so sánh chúng với nhau chứ?”

Ông vốn thông thạo phép kiểm tra chẵn lẻ (parity), tức thêm một bit phụ để tổng số bit 1 thành số chẵn. Nếu xếp các bit dữ liệu thành một hình chữ nhật, mỗi hàng và mỗi cột đều có một phép kiểm tra chẵn lẻ, thì một lỗi đơn lẻ sẽ khiến một phép kiểm tra hàng và một phép kiểm tra cột không đạt. Như ông nói, ghép hai kết quả ấy lại thì “tôi sẽ có tọa độ”.

Hình chữ nhật càng gần hình vuông thì càng cần ít bit kiểm tra, và ông đã bằng lòng với điều đó. Rồi trong một lần đi nhờ chiếc xe limousine chở thư ấy băng qua miền bắc New Jersey — lúc đang “điểm lại những thành công của mình”, theo lời ông — ông nhận ra rằng một hình tam giác với các bit kiểm tra xếp dọc đường chéo sẽ còn tốt hơn. Ông kể rằng mình thấy bẽ mặt. Lâu nay ông vẫn tự nhủ hình vuông là tốt nhất có thể; giờ thì ông tự nhủ: “Hamming, mày sẽ phải tìm ra mã tốt nhất có thể.”

Ví dụ ông đem ra giảng có bảy vị trí — cỡ mã lớn kế tiếp, ngay sau cách đơn giản là gửi mỗi bit ba lần. Các vị trí 1, 2 và 4 chứa bit kiểm tra; các vị trí 3, 5, 6 và 7 chứa dữ liệu. Phép kiểm tra thứ nhất xét các vị trí 1, 3, 5 và 7, phép thứ hai xét 2, 3, 6 và 7, còn phép thứ ba xét 4, 5, 6 và 7. Nếu bit ở vị trí 6 bị lật, phép kiểm tra thứ hai và thứ ba sẽ không đạt, còn phép thứ nhất vẫn đạt. Ghi mỗi phép không đạt là 1, mỗi phép đạt là 0, bắt đầu từ phép thứ ba, bạn sẽ được 110 — số sáu viết theo hệ nhị phân. Mã này không chỉ báo rằng có gì đó sai. Nó gọi đích danh bit sai.

Thêm bit thứ tám — một bit kiểm tra chẵn lẻ cho toàn bộ từ mã — thì mã còn phát hiện được hai lỗi xảy ra cùng lúc, dù không sửa được chúng. Bài báo năm 1950 của ông cũng mô tả phần mở rộng này, đồng thời định nghĩa khoảng cách giữa hai từ mã là số vị trí mà chúng khác nhau, ngày nay gọi là khoảng cách Hamming.

Sửa một lỗi, đồng thời phát hiện hai lỗi: đó là cơ chế mà phần lớn bộ nhớ ECC (bộ nhớ có mã sửa lỗi) áp dụng, theo dạng của Hamming hoặc một biến thể ra đời năm 1970. Hamming nhận Giải thưởng Turing năm 1968, lần thứ ba giải này được trao, “vì công trình của ông về phương pháp số, các hệ thống lập trình tự động, cùng các mã phát hiện lỗi và mã sửa lỗi”.

Ba chi tiết mà giai thoại về hai cuối tuần bỏ qua

Mã Hamming đã được công bố trước bài báo của ông. Bài “Error Detecting and Error Correcting Codes” của Hamming đăng trên tạp chí Bell System Technical Journal vào tháng 4 năm 1950. Nhưng từ tháng 7 năm 1948, cũng trên tạp chí này, bài “A Mathematical Theory of Communication” của Claude Shannon đã đưa ra một mã bảy ký hiệu sửa được lỗi đơn, “tìm ra bằng một phương pháp của R. Hamming”.

Một bằng sáng chế đã níu chân bài báo của Hamming. Theo lời ông, việc công bố bị chậm “chừng mười tám tháng vì rắc rối về bằng sáng chế”. Bằng sáng chế Mỹ số 2.552.629, nộp đơn vào tháng 1 năm 1950 và được cấp vào tháng 5 năm 1951, đứng tên Hamming và một đồng nghiệp ở Bell Labs là B. D. Holbrook.

Mã này mất nhiều tháng mới thành hình, không phải một sớm một chiều. Hai cuối tuần ấy đem lại câu hỏi. Còn câu trả lời, theo chính Hamming ước tính, mất ba đến sáu tháng tranh thủ “những lúc rảnh rỗi”, kể cả buổi tối và cuối tuần. Về bước xếp bit thành hình chữ nhật, ông nói rằng với người đã biết hệ nhị phân và kiểm tra chẵn lẻ thì “đây không phải là một phát minh cao siêu”. Ông cho rằng công lao thuộc về sự chuẩn bị: “May mắn mỉm cười với trí óc có chuẩn bị.”

Câu hỏi của Hamming vẫn giải thích được gì về việc sửa lỗi

Phát hiện lỗi và sửa lỗi là hai mức bảo đảm khác nhau. Mã hai-trong-năm của chiếc máy tính rơ-le có thể cho biết một chữ số không hợp lệ, nhưng không chỉ ra được rơ-le nào đã hỏng, nên máy chỉ có hai cách xử lý an toàn: thử lại hoặc bỏ cuộc. Một mã có cấu trúc chặt chẽ hơn sẽ biến lời báo “có gì đó sai” thành một địa chỉ, và trong hệ nhị phân, biết địa chỉ là sửa được.

Sự bực tức của Hamming cũng quan trọng. Ông từng nói với sinh viên rằng những công trình lớn đến từ những người dồn hết cảm xúc vào công việc, và ví dụ ông đưa ra chính là bản thân mình: một nhà toán học không chịu cho qua chuyện mất trắng hai cuối tuần.

Chiếc máy tính rơ-le ở West Street chỉ biết báo rằng một chữ số bị sai. Còn bộ nhớ ECC, khi lặng lẽ lật một bit sai về lại như cũ, là đang trả lời câu hỏi mà Hamming đặt ra sau cuối tuần mất trắng thứ hai.

Bài liên quan

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