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

Tham khảo tài liệu 'mã sửa sai - phần 1', 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 Khoảng cách Hamming và chận Hamming 2 Huỳnh Văn Kha 7 2 2010 Giới thiệu Ở chương này ta chỉ xét kênh nhị phân đối xứng Các input của kênh được chọn từ một tập các từ mã nhị phân chiều dài n nghĩa là tập các dãy n ký tự 0 và 1 Giả sử các từ mã xuất hiện với xác suất bằng nhau Do lỗi có thể xảy ra ở bất cứ vị trí nào của chuỗi input nên output là tập 2n dãy nhị phân độ dài n Bài toán đầu tiên là tìm phương án giải mã tối ưu cho bộ mã nói trên 1 7 2 2010 3 Huỳnh Văn Kha 7 2 2010 Giới thiệu Ký hiệu các từ mã và các chuỗi output lần lượt là w1 w2 . ws và v1 v2 . Phương án giải mã tối ưu là phương án làm cực tiểu xác suất sai Khi nhận được v như ta đã biết phương án giải mã tối ưu là chọn w sao cho p w v cực đại Nhưng do các từ mã có cùng xác suất nên cực đại p w v tương đương với việc cực đại p v w Huỳnh Văn Kha 7 2 2010 Khoảng cách Hamming Ta định nghĩa khoảng cách d v1 v2 giữa hai dãy nhị phân n ký tự v1 v2 là số vị trí mà ở đó ký tự mã của v1 v2 khác nhau Ví dụ v1 011011 v2 110001 Thì d v1 v2 3 Nếu input là w và output là v thì khi đó kênh đã truyền sai đúng d w v ký tự. Do đó nếu xác suất truyền sai của kênh là p thì p v w 2 7 2 2010 5 Huỳnh Văn Kha 7 2 2010 Cực đại p v w Ta sẽ so sánh p v w1 và p v w2 Đặt d1 d w1 v d2 d w2 v ta có P v wị _ _ fl-pỵdz dí p v w2 d2 l - n-d2 3 Chú ý đối với kênh nhị phân đối xứng ta luôn giả sử 0 p V2 và do đó 1 - p p 1. Vậy p v w1 p v w2 khi và chỉ khi d1 d2 Vậy p v w cực đại khi d v w cực tiểu 6 Huỳnh Văn Kha 7 2 2010 Định lý Giả sử bộ mã cho kênh nhị phân đối xứng gồm s từ mã độ dài n có xác suất như nhau. Phương án giải mã tối ưu là phương án làm cực tiểu khoảng cách. Nghĩa là với mỗi dãy v nhận được bộ giải mã sẽ chọn từ mã w sao cho khoảng cách d w v là nhỏ nhất Nếu có nhiều hơn một cực tiểu thì chọn từ mã nào trong số đó cũng không ảnh hưởng đến xác suất sai