TAILIEUCHUNG - Mã sửa sai - Phần 3

Tham khảo tài liệu 'mã sửa sai - phần 3', công nghệ thông tin, quản trị mạng phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | 7 2 2010 Chương 4 Mã sửa sai 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 7 2 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ẻ. 1 7 2 2010 3 Huỳnh Văn Kha 7 2 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 T 0 0110 r 0101011 .0010111. 4 Huỳnh Văn Kha 7 2 2010 Định lý 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ý 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. 2 7 2 2010 5 Huỳnh Văn Kha 7 2 2010 Ví dụ 1-10000001011 0100000001 0010000101 0001000011 0000100110 0000010010 -0 000001110- 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 rs 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. 6 Huỳnh Văn Kha 7 2 2010 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à .

TỪ KHÓA LIÊN QUAN
Đã phát hiện trình chặn quảng cáo AdBlock
Trang web này phụ thuộc vào doanh thu từ số lần hiển thị quảng cáo để tồn tại. Vui lòng tắt trình chặn quảng cáo của bạn hoặc tạm dừng tính năng chặn quảng cáo cho trang web này.