Khả năng sửa sai
• Như đã biết, số từ mã tăng sẽ làm giảm khả năng
sửa sai của bộ mã. Ta sẽ cố gắng định lượng mối
liên hệ này.
9/30/2010
2
Huỳnh Văn Kha
• Trong phần này, ta giải quyết bài toán sau: cần
chọn ma trận kiểm tra chẵn lẻ như thế nào để bộ
mã thu được sửa sai được e bit trở lại.
• Xét trường hợp e = 1. Ta xây dựng bộ mã sửa sai
được 1 bit.
• Nếu bit sai ở vị trí thứ j thì vector hiệu chỉnh
tương ứng là cột thứ j của ma trận chẵn lẻ.
14 trang |
Chia sẻ: phuongt97 | Lượt xem: 475 | 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 3), để 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.3 Chận trên và dưới cho khả năng
sửa sai của bộmã kiểm tra chẵn lẻ
Khả năng sửa sai
• Như đã biết, số từmã tăng sẽ làm giảm khả năng
sửa sai của bộmã. Ta sẽ cố gắng định lượng mối
liên hệ này.
9/30/2010
2
Huỳnh Văn Kha
• Trong phần này, ta giải quyết bài toán sau: cần
chọn ma trận kiểm tra chẵn lẻ như thế nào để bộ
mã thu được sửa sai được e bit trở lại.
• Xét trường hợp e = 1. Ta xây dựng bộmã sửa sai
được 1 bit.
• Nếu bit sai ở vị trí thứ j thì vector hiệu chỉnh
tương ứng là cột thứ j của ma trận chẵn lẻ.
Khả năng sửa sai
• Ta chọn ma trận chẵn lẻ sao cho n cột của nó
khác nhau đôi một (và khác 0).
• Khi đó mọi dãy sai một bit đều có các vector hiệu
9/30/2010
3
Huỳnh Văn Kha
chỉnh khác nhau. Do đó mọi lỗi sai 1 bit đều sửa
sai được.
• Ví dụ, nếu n = 7, k = 4, ta có thể chọn ma trận
chẵn lẻ như sau:
ðịnh lý 4.9
Bộmã kiểm tra chẵn lẻ xác định bởi ma trận A sẽ
sửa sai được e bit trở lại nếu và chỉ nếu mọi tập 2e
cột của A đều độc lập tuyến tính.
9/30/2010Huỳnh Văn Kha
4
Chứng minh:
Theo định lý 4.8, mọi lỗi sai không quá e bit sẽ được
làm đúng nếu và chỉ nếu các mẫu sai ≤ e bit có các
vector hiệu chỉnh phân biệt nhau. Nghĩa là nếu và
chỉ nếu không có tổ hợp tuyến tính của e (hoặc ít
hơn) cột nào trong A bằng với một tổ hợp tuyến tính
khác (cũng của e cột (hoặc ít hơn) trong A).
Điều này tương đương với mỗi tập 2e cột của A đều
phải độc lập tuyến tính.
Ví dụ
9/30/2010Huỳnh Văn Kha
5
• Có thể thấy mỗi tập gồm 4 cột của A là độc lập
tuyến tính. Bộmã ứng với A có thể sửa sai 2 bit
• Tuy nhiên: c(r1)+c(r8)+c(r9)=c(r3)+c(r4)+c(r6)
• Do đó các dãy sai ở ba cột 1, 8, 9 và các dãy sai ở
ba cột 3, 4, 6 có cùng vector hiệu chỉnh
• Như vậy sai 3 bit chưa chắc sửa được.
Chận trên và dưới cho khả năng sửa
sai của bộ mã kiểm tra chẵn lẻ
• Giả sử ta cần xây dựng bộmã kiểm tra chẵn lẻ
sửa sai được e bit (chiều dài từmã n cố định)
• Vấn đề đặt ra là cần bao nhiêu bit kiểm tra để xây
9/30/2010Huỳnh Văn Kha
6
dựng bộmã như vậy
• Ta muốn càng ít bit kiểm tra càng tốt. Do số bit
kiểm tra càng ít thì số bit thông tin càng lớn và ta
có càng nhiều từmã
• Tổng quát thì không thể xác định chính xác số bit
kiểm tra cực tiểu. Nhưng ta có thể ước lượng chận
dưới và chận trên như các định lý sau
ðịnh lý 4.10
(Chận dưới Hamming cho số bit kiểm tra)
Số bit kiểm tra trong một bộmã chẵn lẻ sửa sai
được e bit cần thỏa:
9/30/2010Huỳnh Văn Kha
7
Trong đó: n = chiều dài từmã
m = số bit kiểm tra = n - k
Chứng minh ñịnh lý 4.10
• Để bộmã kiểm tra chẵn lẻ sửa sai được e bit trở
lại thì các lỗi sai e bit hoặc ít hơn có các vector
hiệu chỉnh khác nhau đôi một.
9/30/2010Huỳnh Văn Kha
8
• Nếu từmã có chiều dài n thì số lỗi sai đúng i bit
là tổ hợp chập i của n.
• Số các vector hiệu chỉnh là 2m.
• Do đó để các vector hiệu chỉnh là duy nhất cho
mỗi lỗi sai e bit trở lại thì:
Chú ý
• Chận dưới Hamming cho số bit kiểm tra chính là
chận trên Hamming cho số từmã (định lý 4.3)
• Chận dưới Hamming là điều kiện cần nhưng
không đủ cho việc xây dựng bộmã kiểm tra chẵn
lẻ sửa sai được e bit.
9/30/2010Huỳnh Văn Kha
9
• Nói cách khác, nếu gọi m0 là số nguyên nhỏ nhất
thỏa định lý 4.10 (với n và e cho trước) thì có thể
không có bộmã nào sửa sai được e bit mà chỉ sử
dụng có m0 bit kiểm tra.
• Ví dụ với n = 10, e = 2 ta có m0 = 6. Tuy nhiên
không có bộmã chẵn lẻ nào sửa sai được 2 bit mà
sử dụng ít hơn 7 bit kiểm tra
ðịnh lý 4.11
(Điều kiện Varsharmov-Gilbert-Sacks)
Một bộmã kiểm tra chẵn lẻ sửa sai được e bit với
chiều dài từmã là n có thể xây dựng được nếu số
9/30/2010Huỳnh Văn Kha
10
bit kiểm tra m thỏa điều kiện:
Đây là chận trên cho số bit kiểm tra cần thiết cho
việc xậy dựng bộmã chẵn lẻ sửa sai e bit
Chú ý
• Điều kiện trong định lý 4.11 là điều kiện đủ nhưng
không cần.
• Nói cách khác, cố định n và e, gọi m1 là số nguyên
dương nhỏ nhất thỏa định lý 4.11. Thì theo định lý
4.11 có thể xây dựng bộmã sửa sai e bit sử dụng
9/30/2010Huỳnh Văn Kha
11
m1 bit kiểm tra. Tuy nhiên, trong một số trường
hợp, ta cũng có thể xây dựng bộmã sửa sai e bit
mà chỉ sử dụng ít hơn m1 bit kiểm tra.
• Ví dụ với n = 10, e = 2, ta có m1 = 8. Tuy nhiên ta
có thể xây dựng bộmã sửa sai 2 bit mà chỉ sử
dụng 7 bit kiểm tra như ví dụ sau định lý 4.9
Chứng minh ñịnh lý 4.11
• Ta sẽ xây dựng bộmã thỏa yêu cầu bằng cách chỉ
ra các cột c(r1), c(r2), , c(rn) của ma trận chẵn lẻ
tương ứng.
9/30/2010Huỳnh Văn Kha
12
• Các cột này cần phải thỏa điều kiện: mọi tập gồm
2e cột đều độc lập tuyến tính.
• Đầu tiên, chọn c(r1) khác 0 tùy ý
• Chọn c(r2) sao cho c(r2) ≠ 0, c(r2) ≠ c(r1)
• Chọn c(r3) sao cho c(r3) ≠ 0, c(r3) ≠ c(r1), c(r3)
≠ c(r2), c(r3) ≠ c(r1)+c(r2)
Chứng minh ñịnh lý 4.11
• Giả sử đã chọn được c(r1), c(r2), , c(rn-1), ta
chọn c(rn) thỏa:
9/30/2010Huỳnh Văn Kha
13
Chứng minh ñịnh lý 4.11
• Số các tổ hợp nói trên, không vượt quá:
9/30/2010Huỳnh Văn Kha
14
(Chú ý: không nhất thiết tất cả các tổ hợp nói trên
phân biệt nhau, do đó số tổ hợp có thể nhỏ hơn)
• Như vậy, nếu tổng trên ≤ 2m thì hiển nhiên ta
chọn được c(rn). Và do đó định lý được chứng
minh.
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_3.pdf