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ả
Nội dung trích xuất từ tài liệu:
Mã sửa sai - Phần 2 7/2/2010Chương 4: Mã s a sai4.2 ng d ng lý thuy t nhóm chomã ki m tra ch n l 2 7/2/2010 Huỳnh Văn KhaMã 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 7/2/2010 Huỳnh Văn Khað nh nghĩa (mã ch n l )Cho h phương trình tuy n tínhT 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 aij, 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.1 = 1; 1.0 = 0.1 = 0.0 = 0 4 7/2/2010 Huỳnh Văn KhaMa tr n ch n l• Ma tr n A = [aij] 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 rj (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 7/2/2010 Huỳnh Văn KhaVí d 1• Cho h sau• 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 = 0, r5 = 1, r6 = 0. Ta đư c r1 = 1, r3 = 1, r2 = 1. Và t mã 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 6 7/2/2010 Huỳnh Văn KhaB mã ki m tra ch n l trong vd1 r1 r2 r3 r4 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 3 7/2/2010 7 7/2/2010 Huỳnh Văn KhaVector hi u ch nh• Gi s dãy bit r1, r2, …, rn đư c truy n qua kênh nh phân đ i x ng, dãy nh n đư c là r1’, r2’, …, rn’• Ta tính• Và g i vector c t c = (c1, c2, …, cm)T là vector hi u ch nh ng v i dãy v = (r1’, r2’, …, rm’)• Dư i d ng ma tr n là c = AvT• Chú ý vT là ký hi u cho chuy n v c a v 8 7/2/2010 Huỳnh Văn KhaM u sai• Gi s w = (r1, r2, …, rn) đư c truy n và dãy nh n đư c là v = (r1’, r2’, …, rn’)• Dãy z = v – w = (r1’ – r1, r2’ – r2, …, rn’ – rn) g i là m u sai c a w và v• Vector hi u ch nh c a v là c = A(zT + wT) = AzT + AwT = AzT• N u z có giá tr 1 t i các bit th j1, j2, …, je và 0 t i các bit còn l i thì vector AzT là t ng các c t th j1, j2, …, je c a A 4 7/2/2010 9 7/2/2010 Huỳnh Văn KhaNhóm (Group)M t nhóm là m t t p h p G trên đó có xác đ nh phép toán g i là phép “c ng” ...