Bài giảng Chương 4: Mã sửa sai

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ẻ 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 9/30/2010 2 Huỳnh Văn Kha 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 = 0modulo 2 ðịnh nghĩa (mã chẵn lẻ) Cho hệ phương trình tuyến tính 9/30/2010 3 Huỳnh Văn Kha 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 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 9/30/2010 4 Huỳnh Văn Kha 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ã Ví dụ 1 • Cho hệ sau 9/30/2010 5 Huỳnh Văn Kha • 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 Bộ 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 9/30/2010 6 Huỳnh Văn Kha 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 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 9/30/2010 7 Huỳnh Văn Kha • 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 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 9/30/2010 8 Huỳnh Văn Kha 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 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 9/30/2010 9 Huỳnh Văn Kha 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 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 9/30/2010 10 Huỳnh Văn Kha • 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 = Aw1 T + Aw2 T = 0 • Các tính chất khác được suy ra từ định nghĩa phép cộng theo mod 2 ðị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 9/30/2010 11 Huỳnh Văn Kha 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 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ụ: 9/30/2010Huỳnh Văn Kha 12 r1 r2 r3 r4 r5 r6 w0 0 0 0 0 0 0 w1 1 0 1 0 0 1 w2 1 1 0 0 1 0 w3 0 1 0 1 0 1 w4 0 1 1 0 1 1 w5 1 1 1 1 0 0 w6 1 0 0 1 1 1 w7 0 0 1 1 1 0 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 9/30/2010Huỳnh Văn Kha 13 • 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ã 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 9/30/2010Huỳnh Văn Kha 14 • Hay 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 9/30/2010Huỳnh Văn Kha 15 tử nên tập nghiệm của AwT = 0 chính là S • Đây là điều cần chứng minh 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 9/30/2010Huỳnh Văn Kha 16 đ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 Ví dụ • Ba cột cuối là độc lập tuyến tính, viết ba cột đầu 9/30/2010Huỳnh Văn Kha 17 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 Ví dụ • Tương tự cho hai cột còn lại 9/30/2010Huỳnh Văn Kha 18 • Suy ra b1 = b2 = 1, b3 = 0 và c1 = c3 = 1, c2 = 0 Ví dụ • Và như vậy 9/30/2010Huỳnh Văn Kha 19 • Ma trận A là 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 v i z ký hi u là z + S 9/30/2010 20 Huỳnh Văn Kha ươ ứ ớ ệ • 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 Bảng các lớp thương w0 w1 w2 w3 0000 0101 1110 1011 9/30/2010 21 Huỳnh Văn Kha 0110 0011 1000 1101 1111 1010 0001 0100 0010 0111 1100 1001 Bổ ñề 4.5 Cho bộmã chẵn lẻ S. Nếu có từmã wi và mẫu sai z sao cho d(wi + z, wi) ≤ d(wi + z, wj) 9/30/2010 22 Huỳnh Văn Kha với mọi từmã wj. Thì khi đó d(w + z, w) ≤ d(w+ z, w’) với mọi từmã w, w’ Ta thấy rằng một mẫu sai hoặc là luôn sửa được hoặc là luôn không sửa được Chứng minh bổ ñề 4.5 • Dễ dàng kiểm tra được rằng d(v1 + v3, v2 + v3) = d(v1, v2) • Do đó 9/30/2010 23 Huỳnh Văn Kha ðịnh lý 4.6 Để xây dựng phương án giải mã cực tiểu khoảng cách, thì trong mỗi lớp thương, ta chỉ cần chọn các mẫu sai z có số ký tự 1 cực tiểu. Khi đó mỗi 9/30/2010 24 Huỳnh Văn Kha dãy nhận được có dạng z + w (w là từmã) thì sẽ được giải mã thành w Chứng minh: Ta có Theo Bổ đề 4.5 ta có điều cần chứng minh Ví dụ w0 w1 w2 w3 0000 0101 1110 1011 9/30/2010 25 Huỳnh Văn Kha 1000 1101 0110 0011 0001 0100 1111 1010 0010 0111 1100 1001 ðịnh lý 4.7 Tất cả các dãy trong cùng một lớp thương của bộ mã nhóm S đều có cùng một vector hiệu chỉnh Hai dãy trong hai lớp thương khác nhau có các 9/30/2010 26 Huỳnh Văn Kha vector hiệu chỉnh khác nhau Dựa vào hai định lý 4.6 và 4.7 ta chứng minh được định lý 4.8 sau. Định lý 4.8 cho phép việc giải mã nhanh hơn. Đó là thay vì phải lưu trữ toàn bộ 2n dãy nhị phân, ta chỉ cần lưu các vector hiệu chỉnh và các mẫu sai tương ứng là đủ ðịnh lý 4.8 Việc giải mã theo cách làm cực tiểu khoảng cách có thể thực hiện theo cách sau 1. Với mỗi dãy v nhận được, ta tính các vector 9/30/2010 27 Huỳnh Văn Kha hiệu chỉnh c tương ứng 2. Trong tất cả các dãy z thỏa AzT = c, giả sử z0 có số ký tự 1 ít nhất, ta giảmã v thành v – z0 Ví dụ Với ma trận kiểm tra chẵn lẻ 9/30/2010 28 Huỳnh Văn Kha Lập bảng giải mã