Bài giảng Lý thuyết thông tin: Chương 4.2 - ThS. Huỳnh Văn Kha

Chương này trình bày về ứng dụng lý thuyết nhóm cho mã kiểm tra chẵn lẻ. Các nội dung chính trong chương gồm có: Mã chẵn lẻ, định nghĩa (mã chẵn lẻ), ma trận chẵn lẻ, vector hiệu chỉnh, mẫu sai, nhóm (Group), nhóm và mã kiểm tra chẵn lẻ,... Mời các bạn cùng tham khảo.
Nội dung trích xuất từ tài liệu:
Bài giảng Lý thuyết thông tin: Chương 4.2 - ThS. Huỳnh Văn KhaChương 4: Mã sửa sai4.2 Ứng dụng lý thuyết nhóm chomã kiểm tra chẵn lẻ 2 Huỳnh Văn Kha 9/30/2010Mã 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 3 Huỳnh Văn Kha 9/30/2010ðị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 Huỳnh Văn Kha 9/30/2010Ma 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ã 5 Huỳnh Văn Kha 9/30/2010Ví 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 Huỳnh Văn Kha 9/30/2010Bộ 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 7 Huỳnh Văn Kha 9/30/2010Vector 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 Huỳnh Văn Kha 9/30/2010Mẫ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 9 Huỳnh Văn Kha 9/30/2010Nhó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” thỏa mãn tính chất1. a, b thuộc G thì a + b cũng thuộc G2. (a + b) + c = a + (b + c) với mọi a, b, c trong G3. Có phần tử 0 trong G sao cho a + 0 = 0 + a = a với mọi a trong G4. Với mỗi a trong G có phần tử -a trong G sao cho a + (-a) = (-a) + a = 0Nhóm G gọi là giao hoán nếu a + b = b + a, với mọi a, b trong G 10 Huỳnh Văn Kha 9/30/2010Nhóm và mã kiểm tra chẵn lẻ• Gọi Bn là tập các dãy nhị phân chiều dài n với phép cộng là cộng từng bit một theo mod 2. Thì Bn là một nhóm• Dễ dàng kiểm tra được rằng nếu S là bộ mã kiểm tra chẵn lẻ thì S là một nhóm, và gọi là nhóm con của Bn• Thật vậy, nếu w1, w2 là các từ mã thì A(w1 + w2)T = Aw1T + Aw2T = 0• Các tính chất khác được suy ra từ định nghĩa phép cộng theo mod 2 11 Huỳnh Văn Kha 9/30/2010ðịnh lý 4.4Cho S là nhóm con của Bn. Thì S là một bộ mã kiểm tra chẵn lẻ, nghĩa là tồn tại ma trận kiểm tra ...