Khoảng cách Hamming

Bách khoa toàn thư mở Wikipedia
Bước tới: menu, tìm kiếm

Trong lý thuyết thông tin, Khoảng cách Hamming (tiếng Anh: Hamming distance) giữa hai dãy ký tự (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 10111011001001 là 2.
  • Khoảng cách Hamming giữa 21438962233796 là 3.
  • Khoảng cách Hamming giữa "toned" và "roses" là 3.

Trọng lượng 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 lượng Hamming của dãy ký tự 11101 là 4.

Đặc tính[sửa | sửa mã nguồn]

Đố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) nữa.

Khoảng cách Hamming giữa hai từ ab còn được gọi là trọng lượng Hamming (Hamming weight) của phép toán ab, 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) ab, 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 giả phương cấp n (n-dimensional hypercube), trong đó n là chiều dài của các từ.

Lịch sử và ứng dụng[sửa | sửa mã nguồn]

Khoảng cách Hamming là cái tên được đặt theo tên của ông 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 lượng 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 chiếu[sửa | sửa mã nguồn]

Adapted in part from Federal Standard 1037C.

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

Xem thêm[sửa | sửa mã nguồn]