tailieunhanh - Mã sửa sai - Phần 2

Tham khảo tài liệu 'mã sửa sai - phần 2', 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 Ứng dụng lý thuyết nhóm cho mã kiểm tra chẵn lẻ 2 Huỳnh Văn Kha 7 2 2010 Mã chẵn lẻ Mã chẵn lẻ ban đầu được xây dựng rất đơn giản Cho trước bộ mã gồm các từ mã n bit nhị phân. Một bit chẵn lẻ được thêm vào mỗi từ mã sao tổng số bit một mỗi từ mã là chẵn hoặc lẻ Ví dụ bộ mã ban đầu là 00 01 10 11 thì bộ mã chẵn lẻ thu được là 000 011 101 110 Dễ dàng thấy rằng mọi sự truyền sai e bit với e lẻ đều phát hiện được Gọi r1 r2 . rn là các bit của một từ mã số bit 1 là chẵn được viết là r1 r2 . rn 0 modulo 2 1 7 2 2010 3 Huỳnh Văn Kha 7 2 2010 Định nghĩa mã chẵn lẻ Cho hệ phương trình tuyến tính ữiiĩì a12r2 alnrn 0 mod 2 hnlTl I h I 0 Tập nghiệm của hệ trên gọi là một bộ mã kiểm tra chăn lẻ hay bộ mã nhóm Chú ý Các aịj ri là các số 0 1. Phép cộng nhân theo modulo 2 được định nghĩa như sau 0 0 1 1 0 0 1 1 0 1 1 0 4 Huỳnh Văn Kha 7 2 2010 Ma trận chẵn lẻ Ma trận A aj gọi là ma trận kiểm tra chẵn lẻ Nếu A có hạng t và các cột j1 . jt là độc lập tuyến tính thì có n -t k các r j j1 . jt có thể được chọn tùy ý và ta gọi là các bit thông tin Các bit thứ j1 . jt gọi là các bit kiểm tra Mỗi khi cho giá trị của các bit thông tin ta được một từ mã duy nhất Bộ mã kiểm tra chẵn lẻ có 2k từ mã 2 7 2 2010 5 Huỳnh Văn Kha 7 2 2010 Ví dụ 1 Cho hệ sau ri r4 r5 0 r2 r3 r4 r6 0 mod 2 rì r3 4- r4 6 0 Có thể chọn r1 r2 r3 làm bit kiểm tra và r4 r5 r6 làm bit thông tin Cho r4 o r 1 r6 0. Ta được r1 1 r3 1 r2 1. Va từ ma thu được là 111010 Cho các giá trị khác cho r4 r5 r6 ta được 23 8 từ mã. Toàn bộ từ mã được cho trong bảng sau Huỳnh Văn Kha 7 2 2010 Bộ mã kiểm tra chẵn lẻ trong vd1 r1 r 2 r 3 r 4 r5 r6 w1 0 0 0 0 0 0 w2 0 0 1 0 0 1 w3 1 1 1 0 1 0 w4 1 1 0 0 1 1 w5 1 1 0 1 0 0 w6 1 1 1 1 0 1 w7 0 1 1 1 1 0 w8 0 0 0 1 1 1