mã hamming

MÃ HAMMING

Mục tiêu

Sau khi hoàn tất bài học này bạn có thể:

• Hiểu Mã Hamming,
• Hiểu tính chất của mã Hamming.

Mã Hammin

Mã Hamming là một dạng mã nhóm (mã kiểm tra chẵn lẻ) được xác định từ ma trận kiểm tra chẵn lẻ A có dạng sau:

• Cột thứ j của ma trận A là biểu diễn nhị phân m bit (m là số bit kiểm tra chẵn lẻ) của số j theo qui ước biểu diễn nhị phân của số j được viết theo thứ tự từ dưới lên trên (viết theo cột), tương đương với viết từ trái sang phải (viết theo dòng).
• Các bit ở vị trí 2ⁱ ( i = 0, 1, 2, …) được chọn làm bit kiểm tra.

Ví dụ 1: biểu diễn nhị phân của số j = 3 có m = 3 bit như sau:

Viết theo dòng: 011 (viết từ trái sang phải)

Viết theo cột:

(viết từ dưới lên)

Ví dụ 2: ma trận kiểm tra chẵn lẻ với n=6, m=3 có thể viết như sau:

Từ mã Hamming có dạng: w=r₁r₂r₃r₄r₅r_6. Trong đó, r₁r₂r₄ là các bit kiểm tra và r₃r₅r₆ là các bit thông tin (vì các bit ở vị trí 2ⁱ (với i = 0, 1, 2, …) được chọn làm bits kiểm tra).

Tính chất

Nếu cho trước số bit (m) và số bit lỗi tự sửa (e) thì số bit tối đa của bộ mã Hamming (n) có thể được ước lượng từ bất đẳng thức sau:

Ví dụ minh họa

Tìm bộ mã Hamming với n = 6 và m =3

Ta có thể viết ngay ma trận kiểm tra chẵn lẻ cho bộ mã Hamming

Từ A => k = n – m = 3.

Các bit ở các vị trí 1, 2, 4 được chọn làm các bit kiểm tra.

=> số từ mã của bộ mã Hamming là s = 2^k = 8

Tìm k từ mã độc lập tuyến tính có dạng:

w’₁=r₁r₂0r₄01

w’₂=r₁r₂0r₄10

w’₃=r₁r₂1r₄00

Giải các hệ phương trình: A.w₁=0, A.w₂=0, A.w₃=0

Các từ mã còn lại được xác định theo phương pháp sinh mã nhanh.

Ghi chú: Kết quả chi tiết xây dựng bảng mã Hamming dành cho sinh viên tự làm.

Bài tập

Viết ma trận kiểm tra chẵn lẻ cho bộ mã Hamming với n = 15.

Từ kết quả bài tập 1, hãy tìm các từ mã Hamming độc lập tuyến tính tương ứng.

Xét bộ mã Hamming với số bit kiểm tra cho trước là m, khi đó:

• Độ dài mã tối thiểu là bao nhiêu?
• Độ dài mã tối đa là bao nhiêu?