Bài giảng Lý thuyết thông tin: Chương 5 - Bùi Văn Thành

Chương 5 Mã hóa kênh truyền thuộc bài giảng lý thuyết thông tin, cùng nắm kiến thức trong chương này thông qua việc tìm hiểu các nội dung chính sau: khái niệm về mã phát hiện sai và sửa sai, mã khối tuyến tính.
Nội dung trích xuất từ tài liệu:
Bài giảng Lý thuyết thông tin: Chương 5 - Bùi Văn Thành CHƯƠNG 5 Mã hóa kênh truyền 1 Nội dung  Khái niệm về mã phát hiện sai và sửa sai. – Cơ chế phát hiện sai của mã hiệu. – Khả năng phát hiện và sửa sai. – Hệ số sai không phát hiện được.  Mã khối tuyến tính – Định nghĩa – Ma trận kiểm tra – Mạch mã hóa – Giải mã – Syndrome và sự phát hiện lỗi – Sửa lỗi 2 Vấn đề Lỗi khi truyền dữ liệu trên một hệ thống truyền tin: • Lỗi khi truyền tin là một điều khó tránh. • Nguyên nhân: Do nhiễu bên ngoài xâm nhập, tác động lên kênh truyền, làm thông tin truyền đi bị sai. 1→0 0→1 • Việc khắc phục và kiểm soát lỗi là một vấn đề hết sức quan trọng. 3 Nguyên lý mã hóa kiểm soát lỗi • Nguyên lý chung là thêm vào tập mã cần truyền một tập bit kiểm tra nào đó để bên nhận có thể kiểm soát lỗi. • Bên phát: Bổ sung thêm thông tin (thêm bit) vào bit cần gửi. • Bên thu: Nhận thông tin bổ sung ở phía phát, kiểm tra, phát hiện và sửa lỗi. k bit k+n-k = n bit Phát Bộ mã KSL Thu + (n-k) bit Thông tin Với n-k: bit kiểm tra 4 Khái niệm về mã phát hiện sai và sửa sai.  Dạng sai lầm của mã hiệu được truyền tuỳ thuộc tính chất thống kê của kênh:  sai độc lập dẫn đến sai ngẫu nhiên: 1 hoặc 2 sai.  Sai tương quan dẫn đến sai chùm (sai cụm)  Người ta thống kê: sai ngẫu nhiên xẩy ra 80%, sai chùm xảy ra 20%.  Xác suất xuất hiện một từ mã n ký hiệu có t sai bất kỳ: p(n,t) = Cntpst(1-ps)n-t 5 Cơ chế phát hiện sai của mã hiệu.  Số từ mã có thể có: N0 = 2n  Số từ mã mang tin: N = 2k.  Số từ mã không dùng đến: 2n –2k (số tổ hợp cấm)  Để mạch có thể phát hiện hết i lỗi thì phải thỏa mãn điều kiện: 2n 2k  1  E  Trong đó EΣ = E1 + E2+ . . . + Ei  E1, E2, . . Ei là tập hợp các vector sai 1,2 . . .i lỗi.  Để phát hiện và sửa hết sai 1 lỗi ta có: 2n 2k  n 1 6 Khả năng phát hiện và sửa sai  Trọng số Hamming của vector t: ký hiệu: w(t) được xác định theo số các thành phần khác không của vector.  Ví dụ: t1 = 1 0 0 1 0 1 1  w(t1) = 4  Khoảng cách giữa 2 vector t1, t2: ký hiệu, d(t1, t2) được định nghĩa là số các thành phần khác nhau giữa chúng.  Ví dụ: t2 = 0 1 0 0 0 1 1  d(t1, t2) = 3 chúng khác nhau ở vị trí 0, 1 và 3  Khoảng cách Hamming giữa 2 vector mã t1, t2 = trọng số của vector tổng t1 t2: d(t1, t2)=w(t1 t2) . t1 = 1 0 0 1 0 1 1  t2 = 0 1 0 0 0 1 1 t1 t2 = 1 1 0 1 0 0 0  w(t1 t2) = 3 = d(t1, t2) Điều kiện phát hiện sai  Điều kiện để một mã tuyến tính có thể phát hiện được t sai: d  t+1  ví dụ: t = 1  d  2; t = 2  d  3 t=5d6  Điều kiện để một mã tuyến tính có thể phát hiện và sửa được t sai: d  2t + 1 t = 1  d  3; t = 2  d  5; t = 5  d  11 8 Hệ số sai không phát hiện được  Ví dụ: đối với bộ mã (5,2) có trọng số Hamming w =2 ta xác định được hệ số sai không phát hiện được: p’ = C21pqC31 pq2 + C22p2C32p2q nếu p = 10-3  p’  6p2 = 6.10-6 nghĩa là có 106 bit truyền đi, 103 bit bị sai thì có 6 bit sai không phát hiện được. 9 Phương trình đường truyền • Gọi từ mã phát đi là T. • Gọi từ mã nhận được là R • Gọi từ mã sai do đường truyền gây ra là E. phương trình đường truyền: R=TE T=RE E=TR  Đối với mã nhị phân 3 phương trình trên tương đương nhau. 10 Vector sai – cô cheá söûa loãi  Vector sai: E = (e0, e1, …, en)  Ví dụ: E = (1 0 0 1 0 1 0)  sai ở vị trí 0, 3, 5  Trong các hệ thống truyền số liệu có 2 cơ chế sửa lỗi: • Cơ chế ARQ(Automatic Repeat Request-cơ chế tự động phát lại): cơ chế yêu cầu phát lại số liệu một cách tự động (khi phát hiện sai) . cơ chế này có 3 dạng cơ bản:  Cơ chế ARQ dừng & chờ (stop and wait ARQ)  Cơ chế ARQ quay ngược N vector (N go back ARQ).  Cơ chế ARQ chọn lựa việc lặp lại. • Cơ chế FEC (Forward Error Control): phát hiện và tự sửa sai sử dụng các loại mã sửa lỗi.  Khi có sai đơn (1 sai) người ta thường dùng các loại mã như: mã khối tuyến tính, mã Hamming, mã vòng…  Khi có sai chùm (> 2 sai) người ta thường dùng các loại mã như: mã BCH, mã tích chập, mã Trellis, mã Tubor, mã Tubor Block, mã tổng hợp GC… 11 Mã khối tuyến tính • Mã khối tuyến tính được xây dựng dựa trên các kết quả của đại số tuyến tính là một lớp mã được dùng rất phổ biến trong việc chống nhiễu. • Định nghĩa: • Một mã khối có chiều dài n, k bit gồm 2k từ mã tuyến tính C(n,k) nếu và chỉ nếu 2k từ mã hình thành một không gian vectơ k chiều 2n, gồm tất cả các vectơ n thành phần trên trường Galois sơ cấp GF(2) ( bao gồm 2 phần tử {0,1} với 2 phép tính + và *). • Mã tuyến tính C(n,k) có mục đích mã hóa những khối tin (hay thông báo) k bit thành những từ mã n bit. Hay nói cách khác trong n bit của từ mã có chứa k bit thông tin. • Ví dụ: C (7,4): Từ mã dài 7 bit. Thông tin cần truyền: 4 bit. 12 Cách biểu diễn mã – Ma trận sinh • Mã tuyến tính C(n,k) là một không gian k chiều ...