Xem mẫu
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ẻ
2
Huỳnh Văn Kha 9/30/2010
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.
• 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ẻ.
3
Huỳnh Văn Kha 9/30/2010
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 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:
4
Huỳnh Văn Kha 9/30/2010 ðị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.
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.
5
Huỳnh Văn Kha 9/30/2010
Ví dụ
• 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.
...
- tailieumienphi.vn
nguon tai.lieu . vn