Khoảng cách Hamming

Khoảng cách Hamming

Trong lý thuyết thông tin, Khoảng cách Hamming (tiếng Anh: Hamming distance) giữa hai xâu (strings) có chiều dài bằng nhau là số các ký hiệu ở vị trí tương đương có giá trị khác nhau. Nói một cách khác, khoảng cách Hamming đo số lượng thay thế cần phải có để đổi giá trị của một dãy ký tự sang một dãy ký tự khác, hay số lượng lỗi xảy ra biến đổi một dãy ký tự sang một dãy ký tự khác.

Lấy ví dụ:

• Khoảng cách Hamming giữa 1011101 và 1001001 là 2.
• Khoảng cách Hamming giữa 2143896 và 2233796 là 3.
• Khoảng cách Hamming giữa "toned" và "roses" là 3.

Trọng số Hamming (Hamming weight) của một dãy ký tự là khoảng cách Hamming từ một dãy ký tự toàn số không có cùng chiều dài. Có nghĩa là số phần tử trong dãy ký tự không có giá trị không (0): đối với một dãy ký tự nhị phân (binary string), nó chỉ là số các ký tự có giá trị một (1), lấy ví dụ trọng số Hamming của dãy ký tự 11101 là 4.

Đặc tính

Đối với một chiều dài cố định "n", khoảng cách Hamming là độ đo trên không gian vectơ của các từ có chiều dài đó, vì nó thỏa mãn yêu cầu về tính chất số không âm (non-negativity) (số tuyệt đối), hiện thân của tính bất khả phân định (indiscernibles) và tính đối xứng (symmetry), và nó có thể được chứng minh một cách dễ dàng bằng phép quy nạp toàn phần (complete induction) rằng nó còn thỏa mãn bất đẳng thức tam giác (triangle inequality).

Khoảng cách Hamming giữa hai từ a và b còn được gọi là trọng số Hamming (Hamming weight) của phép toán a−b, dùng một toán tử thích hợp thay thế cho toán tử "−".

Đối với hai dãy ký tự nhị phân (binary strings) a và b, phép toán này tương đương với phép toán a XOR b. Khoảng cách Hamming của các dãy ký tự nhị phân còn tương đương với khoảng cách Manhattan (Manhattan distance) giữa hai giao điểm của một hình siêu lập phương n-chiều (n-dimensional hypercube), trong đó n là chiều dài của các từ.

Lịch sử và ứng dụng

Khoảng cách Hamming là cái tên được đặt theo tên của Richard Hamming, người giới thiệu lý thuyết này trong tài liệu có tính cơ sở của ông về mã phát hiện lỗi và sửa lỗi (error-detecting and error-correcting codes). Nó được sử dụng trong kỹ thuật viễn thông để tính số lượng các bit trong một từ nhị phân (binary word) bị đổi ngược, như một hình thức để ước tính số lỗi xảy ra trong quá trình truyền thông, và vì thế, đôi khi, nó còn được gọi là khoảng cách tín hiệu (signal distance). Việc phân tích trọng số Hamming của các bit còn được sử dụng trong một số ngành, bao gồm lý thuyết tin học, lý thuyết mã hóa, và mật mã học. Tuy vậy, khi so sánh các dãy ký tự có chiều dài khác nhau, hay các dãy ký tự có xu hướng không chỉ bị thay thế không thôi, mà còn bị ảnh hưởng bởi dữ liệu bị lồng thêm vào, hoặc bị xóa đi, phương pháp đo lường phức tạp hơn, như khoảng cách Levenshtein (Levenshtein distance) là một phương pháp có tác dụng và thích hợp hơn.

Tham khảo

Phỏng theo một phần từ Federal Standard 1037C.

Richard W. Hamming. Error-detecting and error-correcting codes, Bell System Technical Journal 29(2):147-160, 1950.

Xem thêm

• Trọng số Hamming
• Khoảng cách Levenshtein, tổng quát hóa của khoảng cách Hamming
• Tính đồng dạng (toán học)
• Không gian đồng dạng trong phân loại số (similarity space on numerical taxonomy)