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