Bell Labs, 1947
Richard Hamming gia nhập Phòng thí nghiệm Bell Telephone vào năm 1946. Các máy tính relay ở đó chỉ chạy vào các ngày trong tuần, khi các kỹ thuật viên có thể khởi động lại chúng sau các lỗi. Vào cuối tuần, các máy dừng lại bất cứ khi nào có điều gì đó sai — để lại các công việc xếp hàng cho đến thứ Hai.
Hamming đã tức giận. 'Nếu máy có thể phát hiện một lỗi,' anh nghĩ, 'tại sao nó không thể xác định vị trí và sửa nó?' Sự bực bội này, kết hợp với sự quen thuộc sâu sắc với số học nhị phân và kiểm tra chẵn lẻ, đã tạo ra sân khấu.
Cái Nhìn Sâu Sắc Đầu Tiên: Mã Hình Chữ Nhật
Ý tưởng đầu tiên của Hamming: sắp xếp các bit tin nhắn trong một hình chữ nhật m×n, thêm một kiểm tra chẵn lẻ vào mỗi hàng & mỗi cột. Một lỗi đơn tạo ra chính xác một kiểm tra hàng bị lỗi & một kiểm tra cột bị lỗi. Giao điểm của chúng đặt tên cho vị trí của lỗi.
Tỷ lệ dự phòng: (m+1)(n+1) / mn. Phép tính cho bạn biết một hình vuông giảm thiểu điều này cho kích thước tin nhắn cố định. Nhưng khi m & n tăng lên, một lỗi đôi trở nên có khả năng hơn — một quyết định kỹ thuật không có câu trả lời phổ quát.
Giảm Thiểu Dự Phòng Hình Chữ Nhật
Một hình chữ nhật 4×4 mang 16 bit tin nhắn với 4 kiểm tra hàng & 4 kiểm tra cột, cộng với 1 bit chẵn lẻ góc = 9 bit kiểm tra cho 16 bit tin nhắn.
Tỷ lệ dự phòng: (m+1)(n+1) / mn = 25/16 ≈ 1,56.
Đối với một hình chữ nhật 10×10: 100 bit tin nhắn, 121 bit tổng cộng, dự phòng ≈ 1,21.
Hội Chứng Như Một Số Nhị Phân
Một vài tuần sau khi có cái nhìn sâu sắc về mã hình chữ nhật, Hamming đang cưỡi ngựa về phía New York qua New Jersey farmland, tâm trí anh đang xem xét lại những thành công của anh. Ý tưởng mã hình tam giác xảy ra với anh — dự phòng tốt hơn. Sau đó là hình lập phương. Sau đó là 4 chiều, 5 chiều...
Mỗi chiều thêm vào đã cải thiện dự phòng. Một siêu hình lập phương của cạnh 2 trong n chiều sử dụng chỉ n+1 kiểm tra chẵn lẻ cho 2^n đỉnh. Nhưng điều này có tối ưu không?
Lập Luận Đếm
n+1 bit chẵn lẻ tạo ra một hội chứng: một số nhị phân (n+1)-bit. Hội chứng đó cần xác định 2^n + 1 kết quả riêng biệt: mỗi trong số 2^n vị trí lỗi, cộng với kết quả đặc biệt 'không có lỗi'.
2^(n+1) = 2·2^n — gần như đủ. Thiếu một hệ số 2. Hamming đã để vấn đề này sang một bên.
Cái Nhìn Sâu Sắc Chính
Sau đó, Hamming quay lại với một ý tưởng mới: sử dụng hội chứng tự nó như một số nhị phân đặt tên cho vị trí lỗi. Vị trí 1 = nhị phân 001, vị trí 2 = nhị phân 010, vị trí 3 = nhị phân 011, v.v. Dành tất cả các số không cho 'không có lỗi'.
Điều này biến đổi hội chứng từ một kết quả của các kiểm tra chẵn lẻ thành một địa chỉ. Các kiểm tra chẵn lẻ được thiết kế để tạo ra chính xác địa chỉ đúng khi bất kỳ bit nào lật.
Thiết Kế Mã (7,4)
Đối với một mã 7-bit (3 bit chẵn lẻ, 4 bit tin nhắn), vị trí 1 đến 7 ở dạng nhị phân là: 001, 010, 011, 100, 101, 110, 111.
Kiểm tra chẵn lẻ 1 bao gồm các vị trí nơi bit 0 = 1: vị trí 1, 3, 5, 7.
Kiểm tra chẵn lẻ 2 bao gồm các vị trí nơi bit 1 = 1: vị trí 2, 3, 6, 7.
Kiểm tra chẵn lẻ 3 bao gồm các vị trí nơi bit 2 = 1: vị trí 4, 5, 6, 7.
Các bit chẵn lẻ chiếm các vị trí lũy thừa-của-2: 1, 2, 4. Các bit tin nhắn chiếm phần còn lại: 3, 5, 6, 7.
Nếu bit 6 lật, các kiểm tra chẵn lẻ 2 & 3 bị lỗi (110 ở dạng nhị phân = 6). Hội chứng đọc 110 = 6. Lật vị trí 6. Xong.
Hiệu Chỉnh Lỗi Đơn, Phát Hiện Lỗi Đôi
Mã Hamming (7,4) hiệu chỉnh các lỗi đơn. Nhưng điều gì sẽ xảy ra nếu hai bit lật? Mà không có bảo vệ thêm, bộ giải mã áp dụng quy tắc hội chứng và 'sửa' từ mã thành tin nhắn sai — một sửa chữa âm thầm sai lầm.
SECDED: Một Bit Chẵn Lẻ Khác
Thêm một bit chẵn lẻ đơn p₀ bao gồm toàn bộ từ mã (tất cả 7 bit). Bây giờ hội chứng có 4 mục nhập: 3 kiểm tra gốc cộng với p₀.
``
hội chứng cũ p₀ mới ý nghĩa
000 0 chính xác
000 1 lỗi chỉ trong p₀
xxx 1 lỗi đơn, hội chứng cũ đặt tên cho nó
xxx 0 lỗi đôi — cáo buộc nó
``
Bốn trường hợp là toàn bộ. Một lỗi đôi lật hai bit: hội chứng cũ sẽ không đọc 000 (cả hai bit cùng nhau làm hỏng hai trong số kiểm tra của nó), nhưng p₀ lật hai lần và trở lại 0. Mẫu xxx + 0 là không thể hiểu lầm.
Tại Sao SECDED Hoạt Động
Quy tắc SECDED khai thác cấu trúc mô đun của chẵn lẻ. Với chẵn lẻ chẵn, bất kỳ lần lật nào thay đổi p₀. Bất kỳ lần lật đôi nào để p₀ không thay đổi. Vì vậy p₀ đếm các lỗi theo mô đun 2.
Bức Tranh Hình Học
Hamming đến cùng một nơi từ một hướng khác: hình học phân tích. Biểu diễn mỗi chuỗi n-bit như một đỉnh của một siêu hình lập phương n-chiều. Một lần lật bit di chuyển một điểm một chiều cạnh dọc theo một trục. Hai lần lật: hai cạnh. Số liệu là khoảng cách Hamming.
Xác định một quả cầu Hamming bán kính t xung quanh một từ mã c: tất cả các điểm trong t bit-lật của c. Để hiệu chỉnh lỗi đơn, t = 1.
Điều kiện để hiệu chỉnh lỗi đơn: các quả cầu bán kính 1 xung quanh mỗi cặp từ mã riêng biệt phải không overlapping. Nếu chúng overlapping, một từ nhận được trong overlapping có thể thuộc về bất kỳ từ mã nào và bộ giải mã bị lỗi.
Điều này dịch trực tiếp thành khoảng cách tối thiểu: hai quả cầu bán kính 1 không overlapping nếu và chỉ nếu các từ mã cách nhau ít nhất 3 (d_min ≥ 3).
Mã (7,4) đạt d_min = 3. Giới hạn Hamming: 2^7 / (1 + 7) = 16 = 2^4. Chính xác 16 từ mã. Một mã hoàn hảo: 16 quả cầu bán kính 1 ốp {0,1}^7 mà không có khoảng trống hoặc overlapping.
Quyết Định Kỹ Thuật
Hamming là rõ ràng: các mã hiệu chỉnh lỗi liên quan đến các quyết định kỹ thuật, không phải toán học thuần túy.
Độ dài tin nhắn: các tin nhắn dài hơn cho phép mã hóa hiệu quả hơn (log n bit chẵn lẻ cho n bit tin nhắn). Nhưng các tin nhắn dài hơn cũng tích lũy nhiều nhiễu hơn, làm tăng nguy cơ một lỗi đôi trượt qua như một hiệu chỉnh sai lầm đơn.
Mức độ hiệu chỉnh so với phát hiện: đổi một hiệu chỉnh lỗi cho hai phát hiện lỗi bổ sung. Sự chia tách tối ưu tùy thuộc vào các đặc điểm nhiễu của kênh.
Giá trị bảo dưỡng tại chỗ: khi thiết bị trở nên phức tạp hơn, các kỹ thuật viên tại chỗ không thể chẩn đoán mỗi lỗi từ các nguyên tắc đầu tiên. Một hệ thống tự chẩn đoán giảm đáng kể kỹ năng cần thiết cho bảo dưỡng. Hamming gọi đây là một trong những lợi ích quan trọng nhất, thường quan trọng hơn lợi ích lợi nhuận độ tin cậy thô.
Kiểu Dáng: Vận May Ưu Ái Tâm Trí Chuẩn Bị
Hamming đóng Chương 12 với một thách thức trực tiếp. Anh mô tả khám phá như yêu cầu ba đến sáu tháng làm việc, chủ yếu vào những lúc lẻ loi trong khi thực hiện các nhiệm vụ chính của anh tại Bell Labs.
Anh xác định ba điều làm cho nó có thể:
1. Chuẩn bị: sự quen thuộc sâu sắc với các kiểm tra chẵn lẻ, số học nhị phân, & lý thuyết nhóm, trước khi vấn đề xuất hiện.
2. Xem xét lại những thành công: thói quen để phát lại các giải pháp quá khứ để có được nội tại kiểu dáng của chúng. Ý tưởng mã hình tam giác xảy ra với anh khi tâm trí xem xét lại mã hình chữ nhật trên một chuyến đi.
3. Không thỏa mãn với 'trông tốt': anh đã bị bỏng tay một lần bằng cách chấp nhận sự tối ưu rõ ràng. Anh đã đẩy cho đến khi anh có thể chứng minh mã là tốt nhất.