7/2/2010
1
Chương 4: Mã sửa sai
4.1 Khoảng cách Hamming và chận
Hamming
Giới thiệu
•Ởchương này ta chỉxét kênh nhịphân đối xứng
•Các input của kênh được chọn từmột tập các từ
mã nhịphân chiều dài n, nghĩa là tập các dãy n
ký tự0 và 1
•Giảsửcác từmã xuất hiện với xác suất bằng nhau
•Do lỗi có thểxảy ra ởbất cứvịtrí nào của chuỗi
input nên output là tập 2ndãy nhịphân độdài n
•Bài toán đầu tiên là tìm phương án giải mã tối ưu
cho bộmã nói trên
7/2/2010
2
Huỳnh Văn Kha
7/2/2010
2
Giới thiệu
•Ký hiệu các từmã và các chuỗi output lần lượt là
w1, w2, …., wsvà v1, v2, …
•Phương án giải mã tối ưu là phương án làm cực
tiểu xác suất sai
•Khi nhận được v, nhưta đã biết, phương án giải
mã tối ưu là chọn wsao cho p(w|v)cực đại
•Nhưng do các từmã có cùng xác suất nên cực đại
p(w|v)tương đương với việc cực đại p(v|w)
7/2/2010
3
Huỳnh Văn Kha
Khoảng cách Hamming
•Ta định nghĩa khoảng cách d(v1, v2)giữa hai dãy
nhịphân nký tựv1, v2là sốvịtrí mà ởđó ký tự
mã của v1, v2khác nhau
•Ví dụ:v1= 011011, v2= 110001
Thì d(v1, v2) = 3
•Nếu input là wvà output là vthì khi đó kênh đã
truyền sai đúng d(w, v)ký tự. Do đó nếu xác suất
truyền sai của kênh là β, thì
7/2/2010
4
Huỳnh Văn Kha
7/2/2010
3
Cực ñại p(v|w)
•Ta sẽso sánh p(v|w1) và p(v|w2)
•Đặt d1= d(w1,v), d2= d(w2,v), ta có
•Chú ý, đối với kênh nhịphân đối xứng ta luôn giả
sử0< β < ½, và do đó (1 - β)/β >1. Vậy
p(v|w1) > p(v|w2) khi và chỉkhi d1< d2
•Vậy p(v|w) cực đại khi d(v,w) cực tiểu
7/2/2010
5
Huỳnh Văn Kha
ðịnh lý 4.1
Giảsửbộmã cho kênh nhịphân đối xứng gồm stừ
mã độdài ncó xác suất nhưnhau. Phương án giải
mã tối ưu là phương án làm cực tiểu khoảng
cách. Nghĩa là với mỗi dãy vnhận được, bộgiải
mã sẽchọn từmã wsao cho khoảng cách d(w,v)
là nhỏnhất
Nếu có nhiều hơn một cực tiểu thì chọn từmã nào
trong sốđó cũng không ảnh hưởng đến xác suất
sai
7/2/2010
6
Huỳnh Văn Kha
7/2/2010
4
Ví dụ
•Cho bộmã
•Tìm phương án giải mã tối ưu khi nhận được v=
01011, v’ = 00110?
w1= 00000
w2= 10011
w3= 11100
w4= 01111
7/2/2010
7
Huỳnh Văn Kha
Tính chất của khoảng cách
Ta có thểkiểm chứng rằng khoảng cách Hamming
là một metric, nghĩa là thỏa các tính chất sau
a. d(v1, v2) ≥ 0, d(v1, v2) = 0 khi và chỉkhi v1= v2
b. d(v1, v2) = d(v2, v1)
c. d(v1, v3) ≤ d(v1, v2) + d(v2, v3)
Bất đẳng thức cuối cùng là bất đẳng thức tam giác
•Do ta giải mã dãy vthành từmã gần với vnhất
nên xuất hiện khái niệm bộmã “tốt” là bộmã
có các từmã “ởxa” nhau
7/2/2010
8
Huỳnh Văn Kha
7/2/2010
5
Bổñề4.2
Gọi w1, w2, …, wslà các từmã nhịphân chiều dài
n, và elà một sốnguyên dương. Giảsử
d(wi, wj) ≥ 2e + 1, với mọi i ≠ j
Thì khi đó, mọi sựtruyền sai không quá ebit đều
có thểsửa được.
Nếu d(wi, wj) ≥ 2e, với mọi i ≠ j, thì mọi sựtruyền
sai không quá e-1 bit đều có thểsửa được và mọi
sựtruyền sai ebit đều có thểphát hiện được,
nhưng chưa chắc sửa được
7/2/2010
9
Huỳnh Văn Kha
Bổñề4.2
Ngược lại, bộmã có tính chất mọi sựtruyền sai
không quá ebit đều sửa được thì phải thỏa mãn
d(wi, wj) ≥ 2e + 1, với mọi i ≠ j
Một bộmã có tính chất mọi sựtruyền sai không
quá e-1 bit đều sửa được, và mọi sựtruyền sai
không quá ebit đều phát hiện được thì phải thỏa
mãn d(wi, wj) ≥ 2e , với mọi i ≠ j
7/2/2010
10
Huỳnh Văn Kha