thuat toan hamming trong kiến trúc máy tính [bách khoa tòan thư wikipedia]

Ví dụ dùng (11,7) mã Hamming
Lấy ví dụ chúng ta có một từ dữ liệu dài 7 bit với giá trị là "0110101". Để chứng minh phương pháp các mã Hamming được tính toán và được sử dụng để kiểm tra lỗi, xin xem bảng liệt kê dưới đây. Chữ d (data) được dùng để biểu thị các bit dữ liệu và chữ p (parity) để biểu thị các bit chẵn lẻ (parity bits).
Đầu tiên, các bit của dữ liệu được đặt vào vị trí tương thích của chúng, sau đó các bit chẵn lẻ cho mỗi trường hợp được tính toán dùng quy luật bit chẵn lẻ số chẵn[1].
Thứ tự bit 1 2 3 4 5 6 7 8 9 10 11
Vị trí bit chẵn lẻ và các bit dữ liệu p1 p2 d1 p3 d2 d3 d4 p4 d5 d6 d7
Nhóm dữ liệu (không có bit chẵn lẻ): 0 1 1 0 1 0 1
p1 1 0 1 0 1 1
p2 0 0 1 0 0 1
p3 0 1 1 0
p4 0 1 0 1
Nhóm dữ liệu (với bit chẵn lẻ): 1 0 0 0 1 1 0 0 1 0 1
Cách tính các bit chẵn lẻ trong mã Hamming (từ trái sang phải)
Nhóm dữ liệu mới (new data word) - bao gồm các bit chẵn lẻ - bây giờ là "10001100101". Nếu chúng ta thử cho rằng bit cuối cùng bị thoái hóa (gets corrupted) và bị lộn ngược từ 1 sang 0. Nhóm dữ liệu mới sẽ là "10001100100"; Dưới đây, chúng ta sẽ phân tích quy luật kiến tạo mã Hamming bằng cách cho bit chẵn lẻ giá trị 1 khi kết quả kiểm tra dùng quy luật số chẵn bị sai.
Thứ tự bit 1 2 3 4 5 6 7 8 9 10 11
Vị trí bit chẵn lẻ và các bit dữ liệu p1 p2 d1 p3 d2 d3 d4 p4 d5 d6 d7 Kiểm chẵn lẻ Bit chẵn lẻ
Nhóm dữ liệu nhận được: 1 0 0 0 1 1 0 0 1 0 0 1
p1 1 0 1 0 1 0 Sai 1
p2 0 0 1 0 0 0 Sai 1
p3 0 1 1 0 Đúng 0
p4 0 1 0 0 Sai 1
Kiểm tra các bit chẵn lẻ (bit bị đảo lộn có nền thẫm)
Bước cuối cùng là định giá trị của các bit chẵn lẻ (nên nhớ bit nằm dưới cùng được viết về bên phải - viết ngược lại từ dưới lên trên). Giá trị số nguyên của các bit chẵn lẻ là 11(10), và như vậy có nghĩa là bit thứ 11 trong nhóm dữ liệu (data word) - bao gồm cả các bit chẵn lẻ - là bit có giá trị không đúng, và bit này cần phải đổi ngược lại.
p4 p3 p2 p1
Nhị phân 1 0 1 1
Thập phân 8 2 1 Σ = 11


Khi hai bit dữ liệu (3,7) có cùng bit chẵn lẻ kiểm tra tại vi trí 2k - ví dụ (1,2) - biến đổi giá trị (lỗi trong truyền thông) thì giá trị của bit chẵn lẻ vẫn đúng như giá trị gốc (0,1)
Việc đổi ngược giá trị của bit thứ 11 làm cho nhóm
10001100100
trở lại thành
10001100101.
Bằng việc bỏ đi phần mã Hamming, chúng ta lấy được phần dữ liệu gốc với giá trị là
0110101.
Lưu ý, các bit chẵn lẻ không kiểm tra được lẫn nhau, nếu chỉ một bit chẵn lẻ bị sai thôi, trong khi tất cả các bit khác là đúng, thì chỉ có bit chẵn lẻ nói đến là sai mà thôi và không phải là các bit nó kiểm tra (not any bit it checks).
Cuối cùng, giả sử có hai bit biến đổi, tại vị trí x và y. Nếu x và y có cùng một bit tại vị trí 2k trong đại diện nhị phân của chúng, thì bit chẵn lẻ tương ứng với vị trí đấy kiểm tra cả hai bit, và do đó sẽ giữ nguyên giá trị, không thay đổi. Song một số bit chẵn lẻ nào đấy nhất định phải bị thay đổi, vì x ≠ y, và do đó hai bit tương ứng nào đó có giá trị x và y khác nhau. Do vậy, mã Hamming phát hiện tất cả các lỗi do hai bit bị thay đổi — song nó không phân biệt được chúng với các lỗi do 1 bit bị thay đổi