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
9/30/2010
2
Huỳnh Văn Kha
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 2n dã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
15 trang |
Chia sẻ: phuongt97 | Lượt xem: 603 | Lượt tải: 0
Nội dung tài liệu Bài giảng Lý thuyết thông tin - Chương 4: Mã sửa sai (Phần 1), để tải tài liệu về máy bạn click vào nút DOWNLOAD ở trên
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
9/30/2010
2
Huỳnh Văn Kha
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 2n dã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
Giới thiệu
• Ký hiệu các từmã và các chuỗi output lần lượt là
w1, w2, ., ws và v1, v2,
• Phương án giải mã tối ưu là phương án làm cực
9/30/2010
3
Huỳnh Văn Kha
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 w sao 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)
Khoảng cách Hamming
• Ta định nghĩa khoảng cách d(v1, v2) giữa hai dãy
nhị phân n ký tự v1, v2 là số vị trí mà ở đó ký tự
mã của v1, v2 khác nhau
9/30/2010
4
Huỳnh Văn Kha
• Ví dụ: v1 = 011011, v2 = 110001
Thì d(v1, v2) = 3
• Nếu input là w và output là v thì 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ì
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ó
9/30/2010
5
Huỳnh Văn Kha
• Chú ý, đối với kênh nhị phân đối xứng ta luôn giả
sử 01. 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
ðịnh lý 4.1
Giả sử bộmã cho kênh nhị phân đối xứng gồm s từ
mã độ dài n có 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
9/30/2010
6
Huỳnh Văn Kha
cách. Nghĩa là với mỗi dãy v nhận được, bộ giải
mã sẽ chọn từmã w sao 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
Ví dụ
• Cho bộmã
w1 = 00000
w = 10011
9/30/2010
7
Huỳnh Văn Kha
• Tìm phương án giải mã tối ưu khi nhận được v =
01011, v’ = 00110?
2
w3 = 11100
w4 = 01111
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
9/30/2010
8
Huỳnh Văn Kha
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 v thành từmã gần với v nhấ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
Bổ ñề 4.2
Gọi w1, w2, , ws là các từmã nhị phân chiều dài
n, và e là một số nguyên dương. Giả sử
d(wi, wj) ≥ 2e + 1, với mọi i ≠ j
9/30/2010
9
Huỳnh Văn Kha
Thì khi đó, mọi sự truyền sai không quá e bit đề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 e bit đều có thể phát hiện được,
nhưng chưa chắc sửa được
Bổ ñề 4.2
Ngược lại, bộmã có tính chất mọi sự truyền sai
không quá e bit đều sửa được thì phải thỏa mãn
d(wi, wj) ≥ 2e + 1, với mọi i ≠ j
9/30/2010
10
Huỳnh Văn Kha
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á e bit đều phát hiện được thì phải thỏa
mãn d(wi, wj) ≥ 2e , với mọi i ≠ j
Chứng minh bổ ñề 4.2
wi wj wi wj
9/30/2010
11
Huỳnh Văn Kha
• Giả sửw được truyền và chuỗi nhận được là v.
Xét w’ là từmã khác w
• Đầu tiên giả sử khoảng cách cực tiểu của hai từ
mã ít nhất là 2e+1, ta có
d(w,v) + d(w’,v) ≥ d(w,w’) ≥ 2e+1
d(wi, wj) = 2e+1 d(wi, wj) = 2e
Chứng minh bổ ñề 4.2
• Để bộ giãi mã v thành w’ thì d(w,v) ≥ e + 1.
Nghĩa là để giải mã sai thì phải truyền sai ít nhất
e + 1 ký tự
9/30/2010
12
Huỳnh Văn Kha
• Nếu khoảng cách giữa hai từmã ít nhất là 2e thì
d(w,v) + d(w’,v) ≥ d(w,w’) ≥ 2e
• Nếu sai đúng e ký tự và d(w’,v) = e thì giải mã
thành w hay w’ đều được, nghĩa là có thể sai
• Nếu sai ít hơn e ký tự thì d(w,v) là nhỏ nhất và sẽ
giải mã đúng.
• Chiều ngược lại tương tự
Chận Hamming
Khi e lớn thì khoảng cách giữa các từmã cũng lớn
hơn và dẫn tới số từmã ít đi. Câu hỏi đặt ra là có
nhiều nhất bao nhiêu từmã trong một bộmã có
9/30/2010
13
Huỳnh Văn Kha
thể sửa được mọi sự truyền sai không quá e ký tự
Định lý 4.3:
Nếu bộmã chứa s dãy nhị phân chiều dài n có thể
sửa sai mọi sự truyền sai không quá e ký tự, thì:
Chứng minh ñịnh lý 4.3
• Gọi các từmã là w1, w2, , ws. Vẽ các “mặt cầu”
“tâm” wi “bán kính” e. Mỗi “mặt cầu” như vậy
chứa tất cả dãy nhị phân v thỏa d(wi,v) ≤ e
9/30/2010
14
Huỳnh Văn Kha
• Do bộmã sửa được mọi sự truyền sai e ký tự nên
các “mặt cầu” là rời nhau
• Số dãy nhị phân trong mỗi mặt cầu là
• Do đó
Chú ý
• Cố định e, n và gọi s là số nguyên lớn nhất thỏa
điều kiện định lý 4.3 thì chưa chắc tồn tại bộmã
sửa sai được e ký tự chứa s từmã chiều dài n
9/30/2010
15
Huỳnh Văn Kha
• Ví dụ, nếu e = 1, n = 4 ta có 2n/(1+n) = 16/5 và số
nguyên lớn nhất thỏa là s = 3
• Tuy nhiên không có bộmã nào sửa sai được 1 ký
tựmà có số từmã nhiều hơn 2 (kiểm tra)
• Vậy chận Hamming là điều kiện cần nhưng chưa
đủ cho sự tồn tại của của bộmã sửa sai e ký tự
Các file đính kèm theo tài liệu này:
- bai_giang_ly_thuyet_thong_tin_chuong_4_ma_sua_sai_phan_1.pdf