Bổ đề về tự sửa lỗi và cận hamming

Đặt vấn đề: một từ mã w dài n bit khi được truyền tuần tự từng bit có thể sai e bit. Vấn đề đặt ra là khoáng cách (Hamming) giữa các từ mã và sai số e quan hệ với nhau như thế nào để có thể phân biệt tốt nhất đồng thời tất cả các từ mã? Bổ đề sau xác định quan hệ này.

Bổ đề:

Xét bộ mã W={w₁, w₂, …, w_s} gồm có s từ mã nhị phân dài n bit và 1 số nguyên dương e.

Nếu d(w_i, w_j) _>2e+1 (với mọi i khac j )

Khi đó: tất cả các dãy nhận được v có số bit lỗi <_ e thì v có thể tự điều chỉnh (hay tự sửa lỗi).

Nếu d(w_i, w_j) _>2e (với mọi i khac j )

Khi đó: tất cả các dãy nhận được v có số bit lỗi < e thì v có thể tự điều chỉnh. Tất cả các dãy nhận được có số bit lỗi = e thì ta chỉ phát hiện là v có lỗi và không thể tự điều chỉnh được.

Ngược lại;

Nếu v có số chữ số bit lỗi <_ e và có thể tự điều chỉnh thì d(w_i, w_j)_>2e+1 (với mọi i khac j ).

Nếu v có số chữ số bit lỗi <_ e-1 tự điều chỉnh được và tất cả các tín hiệu với số chữ số bit lỗi <_ e được phát hiện thì khoảng cách giữa các từ mã luôn thỏa: d(w_i,w_j) _>2e (với mọi i khac j ).

Chứng minh và minh họa bổ đề

Giả sử: d(w, w’) _>2e+1 với mọi i khac j . Nếu w và w’ có cùng khoảng cách đối với dãy v thì d(v,w)=d(v,w’)_> e+1. Vậy , nếu d(v, w*) <_ e thì v có thể được giải mã ra w*.

Nếu d(w_i,w_j)_>2e với mọi i khac j, có khả năng có v, w và w’ với số chữ số lỗi là: d(v,w)=d(v,w’)=e (d(v,w)+ d(v,w’) _> d(w,w’)_>2e). Có thể phát hiện ra các từ mã gần v, nhưng do tồn tại cùng lúc nhiều từ mã gần nhất với v dẫn đến không giải mã được, ngược lại hoàn toàn tương tự.

Minh họa:

d(w_i, w_j­)= 2e+1= 7, e=3

Nếu v∈B_i thì v được giải mã về w_i

Nếu v∈B_j thì v được giải mã về w_j

d(w_i, w_j­) = 2e = 8 (e = 4, e - 1=3)

nếu v∉B_i , v∉B_j => các điểm cách tâm khoảng cách 3 thì luôn được giải mã, còn các điểm cách tâm 4 thì chỉ phát hiện lỗi chứ không thể giải mã được.

Mã 3 chiều (x, y, z) bắt đầu từ gốc 000. Cứ một tín hiệu thay đổi thì mã bị đẩy đi theo 1 cạnh, chẳng hạn:

000 cách 010, 001 bởi 1 cạnh,

011 cách 010, 111 và 001 bởi 1 cạnh.

Như vậy, nếu ta chọn w₁=010, w₂=001, w₃=111 thì khoảng cách giữa chúng là 2

d(w₁, w₂)=d(w₁, w₃)=d(w₂, w₃)=2

yvậy nếu có lỗi phát sinh thì chỉ phát hiện chứ không sửa được.

Cận Hamming.

Đặt vấn đề: trong tổng số 2ⁿ dãy nhị nhân dài n bit có thể chọn ra bao nhiêu dãy để tạo thành một bộ mã có thể tự điều chỉnh được e bit lỗi. Định lý cận Hamming cho chúng ta xác định số từ mã có độ dài n bit với giả thiết: có khả năng tự sửa được e bit lỗi (điều kiện cần tự sửa lỗi).

Định lý: Nếu bộ mã W có s từ mã có độ dài n bit có thể tự sửa được e bit lỗi thì

Ghi chú: C_nⁱ = n!/(i!*(n-i)!)

Chứng minh:

Xét từ mã nhị phân w_i có độ dài n bit và có khả năng tự sửa được e bit lỗi.

Số dãy v_j sai khác với w_i từ 0 đến e bit là

:

Tương ứng với s từ mã, tổng số dãy v_j có thể tự sửa lỗi là :

(2ⁿ là tổng số dãy nhị phân dài n bits).

Phân các dạng lỗi

Giả sử ta truyền từ mã n bit w_i ∈ W ( 1 <_ i <_ s) và nhận được dãy n bit v_j ( 1<_ j <_ 2ⁿ).

Các loại lỗi có thể phát hiện sau:

Lỗi có thể tự điều chỉnh:

Trong trường hợp này tồn tại duy nhất từ mã w*_i sao cho d(v_j, w*_i)= Min d(v_j, w_k) với mọiw_k ∈ W.

=> v_j được giải mã về w*_i

Lỗi chỉ phát hiện không điều chỉnh được:

Trong trường hợp này tồn tại từ mã w*_i và w**_i sao cho

d(v_j, w*_i)= d(v_j, w**_i)=Min d(v_j, w_k) với mọiw_k ∈ W

=> v_j không thể giải mã chính xác.

Lỗi không phát hiện được.

Trong trường hợp ta giải mã ra w*_i nhưng khác với w_i đã truyền.

Bài tập

Cho n=7 và e=2, hãy áp dụng định lý cận Hamming cho biêt số từ mã tối đa của bộ mã W.

Cho n=7 và e=2, hãy áp dụng định lý cận Hamming cho biêt số từ mã tối đa của bộ mã W.

Hãy cho một ví dụ cụ thể minh họa các trường hợp phân loại lỗi.