Tài liệu Bài giảng lý thuyết thông tin chương 4 - gv. huỳnh văn kha

Chương 4: Mã sửa sai 4.2 Ứng dụng lý thuyết nhóm cho mã kiểm tra chẵn lẻ 2 Huỳnh Văn Kha 9/30/2010 Mã 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ính Tậ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/2010 Ma 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/2010 Ví 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/2010 Bộ mã kiểm tra chẵn lẻ trong vd1 w1 w2 w3 w4 w5 w6 w7 w8 r1 0 0 1 1 1 1 0 0 r2 0 0 1 1 1 1 1 0 r3 0 1 1 0 0 1 1 0 r4 0 0 0 0 1 1 1 1 r5 0 0 1 1 0 0 1 1 r6 0 1 0 1 0 1 0 1 7 Huỳnh Văn Kha 9/30/2010 Vector 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/2010 Mẫ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/2010 Nhó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ất 1. a, b thuộc G thì a + b cũng thuộc G 2. (a + b) + c = a + (b + c) với mọi a, b, c trong G 3. Có phần tử 0 trong G sao cho a + 0 = 0 + a = a với mọi a trong G 4. Với mỗi a trong G có phần tử -a trong G sao cho a + (-a) = (-a) + a = 0 Nhó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/2010 Nhó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.4 Cho 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 chẵn lẻ A sao cho các tập các từ mã xác định bởi A là S. Như vậy một bộ mã kiểm tra chẵn lẻ có thể đồng nhất với một nhóm con của Bn 12 Huỳnh Văn Kha 9/30/2010 Chứng minh ñịnh lý 4.4 • Sắp các từ mã thành ma trận M gồm s hàng, n cột. Trong đó s là số từ mã. Ví dụ: w0 w1 w2 w3 w4 w5 w6 w7 r1 0 1 1 0 0 1 1 0 r2 0 0 1 1 1 1 0 0 r3 0 1 0 0 1 1 0 1 r4 0 0 0 1 0 1 1 1 r5 0 0 1 0 1 0 1 1 r6 0 1 0 1 1 0 1 0 13 Huỳnh Văn Kha 9/30/2010 Chứng minh ñịnh lý 4.4 • Gọi k là hạng của M và m = n – k. Thì k chính là số hàng tối đa độc lập tuyến tính, cũng là số cột tối đa độc lập tuyến tính • Giả sử k hàng đó là w1, w2, …, wk. Thì tất cả các các từ mã trong S có thể viết dưới dạng • Ngược lại mỗi từ mã có dạng trên đều thuộc S (do S là nhóm) • Mà các wi (i từ 1 đến k) độc lập tuyến tính. Vậy S có 2k từ mã 14 Huỳnh Văn Kha 9/30/2010 Chứng minh ñịnh lý 4.4 • Giả sử k cột cuối là độc lập tuyến tính. Khi đó m cột đầu có thể viết dưới dạng tổ hợp tuyến tính của k cột cuối • Hay 15 Huỳnh Văn Kha 9/30/2010 Chứng minh ñịnh lý 4.4 • Như vậy mọi từ mã đều thỏa AwT = 0 • Mặc khác, do tập nghiệm của AwT = 0 có 2k phần tử nên tập nghiệm của AwT = 0 chính là S • Đây là điều cần chứng minh 16 Huỳnh Văn Kha 9/30/2010 Ví dụ • Xét ví dụ bên trên, ta sẽ tìm ma trận chẵn lẻ tương ứng • Có 8 = 23 từ mã
số hàng độc lập tuyến tính tối đa là 3 • Do w1, w2, w5 là họ độc lập tuyến tính tối đa trong S nên ta chỉ cần tìm ma trận A thỏa cho ba từ mã này là đủ • Xét ma trận Q gồm ba từ mã này như sau 17 Huỳnh Văn Kha 9/30/2010 Ví dụ • Ba cột cuối là độc lập tuyến tính, viết ba cột đầu thành tổ hợp tuyến tính của ba cột cuối như sau • Cột đầu tiên • Suy ra a1 = a2 = a3 = 1 18 Huỳnh Văn Kha 9/30/2010 Ví dụ • Tương tự cho hai cột còn lại • Suy ra b1 = b2 = 1, b3 = 0 và c1 = c3 = 1, c2 = 0 19 Huỳnh Văn Kha Ví dụ • Và như vậy • Ma trận A là 9/30/2010 20 Huỳnh Văn Kha 9/30/2010 Lớp thương (coset) • Cho S là nhóm con của nhóm G , thì lớp thương ứng với phần tử z là một tập hợp mà các phần tử của nó có dạng z + w, với w nằm trong S. Lớp th ng ứng thương ng với v i z ký hiệu hi u là z + S • Ví dụ S = {0000, 0101, 1110, 1011}, thì ▫ ▫ ▫ ▫ 0110 + S = {0110, 0011, 1000, 1101} 1000 + S = 0110 + S 1111 + S = {1111, 1010, 0001, 0100} 0000 + S = S • Các lớp thương hoặc rời nhau hoặc trùng nhau