tailieunhanh - [Viễn Thông] Giáo Trình: Lý Thuyết Thông Tin phần 7

Sau khi hoàn tất bài học này bạn có thể: - Biết được Bổ đề về tự sửa lỗi, - Hiểu Định lý về cận Hamming, - Biết phân loại được các dạng lỗi, - Làm cơ sở lý thuyết cho các phương pháp sửa lỗi được trình bài trong các bài học tiếp theo. | Giáo trình Lý thuyết thông tin. Bài tập 1. Cho bộ mã W w1 000000 w2 101010 w3 111000 w4 111111 và nhận được dãy v 010111 khi đó giải mã về từ mã nào diễn giải 2. Cho bộ mã W w1 000000 w2 010101 w3 000111 w4 111111 và Nhận được dãy v 010111 khi đó giải mã về từ mã nào diễn giải Biên soạn TS. L ê Quy ết Thắng ThS. Phan Tấn Tài Ks. Dương Văn Hiếu. 61 Giáo trình Lý thuyết thông tin. BÀI BỔ ĐỀ VỀ Tự SỬA LỎI VÀ CẬN HAMMING Mục tiêu Sau khi hoàn tất bài học này bạn có thể - Biết được Bổ đề về tự sửa lỗi - Hiểu Định lý về cận Hamming - Biết phân loại được các dạng lỗi - Làm cơ sở lý thuyết cho các phương pháp sửa lỗi được trình bài trong các bài học tiếp theo. Bổ đề về tự sửa lỗi Đặt vấn đề một từ mã w dài n bit khi được truyền tuần tự từng bit có thể sai e bit. Vấn đề đặt ra là khoáng cách Hamming giữa các từ mã và sai số e quan hệ với nhau như thế nào để có thể phân biệt tốt nhất đồng thời tất cả các từ mã Bổ đề sau xác định quan hệ này. Bổ đề Xét bộ mã W wi w2 . ws gồm có s từ mã nhị phân dài n bit và 1 số nguyên dương e. 1. Nếu d wi Wj 2e 1 với V i j Khi đó tất cả các dãy nhận được v có số bit lỗi e thì v có thể tự điều chỉnh hay tự sửa lỗi . 2. Nếu d wi Wj 2e với V i j Khi đó tất cả các dãy nhận được v có số bit lỗi e thì v có thể tự điều chỉnh. Tất cả các dãy nhận được có số bit lỗi e thì ta chỉ phát hiện là v có lỗi và không thể tự điều chỉnh được. 3. Ngược lại Nếu v có số chữ số bit lỗi e và có thể tự điều chỉnh thì d wi Wj 2e 1 với V i j . Nếu v có số chữ số bit lỗi e-1 tự điều chỉnh được và tất cả các tín hiệu với số chữ số bit lỗi e được phát hiện thì khoảng cách giữa các từ mã luôn thỏa d wi Wj 2e với V tej . Chứng minh và minh họa bổ đề a. Giả sử d w w 2e 1 với V i j . Nếu w và w có cùng khoảng cách đối với dãy v thì d v w d v w e 1. Vậy nếu d v w e thì v có thể được giải mã ra w . b. Nếu d wi Wj 2e với V tej có khả năng có v w và w với số chữ số lỗi là d v w d v w e d v w d v w d w w 2e . Có thể phát hiện ra các từ mã gần v nhưng do tồn tại cùng lúc nhiều