Chương 5 Mã hóa kênh truyền

CHƯƠNG 5 Mã hóa kênh truyền 1  Khái niệm về mã phát hiện sai và sửa sai. – Cơ chế phát hiện sai của mã hiệu. – Khả năng phát hiện và sửa sai. – Hệ số sai không phát hiện được.  Mã khối tuyến tính – Định nghĩa – Ma trận kiểm tra – Mạch mã hóa – Giải mã – Syndrome và sự phát hiện lỗi – Sửa lỗi Nội dung 2 Vấn đề 3 Lỗi khi truyền dữ liệu trên một hệ thống truyền tin: • Lỗi khi truyền tin là một điều khó tránh. • Nguyên nhân: Do nhiễu bên ngoài xâm nhập, tác động lên kênh truyền, làm thông tin truyền đi bị sai. 1 → 0 0 → 1 • Việc khắc phục và kiểm soát lỗi là một vấn đề hết sức quan trọng. Nguyên lý mã hóa kiểm soát lỗi 4 • Nguyên lý chung là thêm vào tập mã cần truyền một tập bit kiểm tra nào đó để bên nhận có thể kiểm soát lỗi. • Bên phát: Bổ sung thêm thông tin (thêm bit) vào bit cần gửi. • Bên thu: Nhận thông tin bổ sung ở phía phát, kiểm tra, phát hiện và sửa lỗi. Với n-k: bit kiểm tra Bộ mã KSL + (n-k) bit k bit Thông tin k+n-k = n bit Phát Thu  Dạng sai lầm của mã hiệu được truyền tuỳ thuộc tính chất thống kê của kênh:  sai độc lập dẫn đến sai ngẫu nhiên: 1 hoặc 2 sai.  Sai tương quan dẫn đến sai chùm (sai cụm)  Người ta thống kê: sai ngẫu nhiên xẩy ra 80%, sai chùm xảy ra 20%.  Xác suất xuất hiện một từ mã n ký hiệu có t sai bất kỳ: p(n,t) = Cn tps t(1-ps) n-t 5 Khái niệm về mã phát hiện sai và sửa sai.  Số từ mã có thể có: N0 = 2 n  Số từ mã mang tin: N = 2k.  Số từ mã không dùng đến: 2n –2k (số tổ hợp cấm)  Để mạch có thể phát hiện hết i lỗi thì phải thỏa mãn điều kiện:  Trong đó EΣ = E1 + E2+ . . . + Ei  E1, E2, . . Ei là tập hợp các vector sai 1,2 . . .i lỗi.  Để phát hiện và sửa hết sai 1 lỗi ta có: 6 Cơ chế phát hiện sai của mã hiệu.    E n k 1 2 2 1 2 2   n n k  Trọng số Hamming của vector t: ký hiệu: w(t) được xác định theo số các thành phần khác không của vector.  Ví dụ: t1 = 1 0 0 1 0 1 1  w(t1) = 4  Khoảng cách giữa 2 vector t1, t2: ký hiệu, d(t1, t2) được định nghĩa là số các thành phần khác nhau giữa chúng.  Ví dụ: t2 = 0 1 0 0 0 1 1  d(t1, t2) = 3 chúng khác nhau ở vị trí 0, 1 và 3  Khoảng cách Hamming giữa 2 vector mã t1, t2 = trọng số của vector tổng t1 t2: d(t1, t2)=w(t1 t2) . t1 = 1 0 0 1 0 1 1  t2 = 0 1 0 0 0 1 1 t1 t2 = 1 1 0 1 0 0 0  w(t1 t2) = 3 = d(t1, t2) Khả năng phát hiện và sửa sai  Điều kiện để một mã tuyến tính có thể phát hiện được t sai: d  t+1  ví dụ: t = 1  d  2; t = 2  d  3 t = 5  d  6  Điều kiện để một mã tuyến tính có thể phát hiện và sửa được t sai: d  2t + 1 t = 1  d  3; t = 2  d  5; t = 5  d  11 8 Điều kiện phát hiện sai  Ví dụ: đối với bộ mã (5,2) có trọng số Hamming w =2 ta xác định được hệ số sai không phát hiện được: p’ = C2 1pqC3 1 pq2 + C2 2p2C3 2p2q nếu p = 10-3  p’  6p2 = 6.10-6 nghĩa là có 106 bit truyền đi, 103 bit bị sai thì có 6 bit sai không phát hiện được. 9 Hệ số sai không phát hiện được • Gọi từ mã phát đi là T. • Gọi từ mã nhận được là R • Gọi từ mã sai do đường truyền gây ra là E. phương trình đường truyền: R = T  E T = R  E E = T  R  Đối với mã nhị phân 3 phương trình trên tương đương nhau. 10 Phương trình đường truyền  Vector sai: E = (e0, e1, …, en)  Ví dụ: E = (1 0 0 1 0 1 0)  sai ở vị trí 0, 3, 5  Trong các hệ thống truyền số liệu có 2 cơ chế sửa lỗi: • Cơ chế ARQ(Automatic Repeat Request-cơ chế tự động phát lại): cơ chế yêu cầu phát lại số liệu một cách tự động (khi phát hiện sai) . cơ chế này có 3 dạng cơ bản: Cơ chế ARQ dừng & chờ (stop and wait ARQ) Cơ chế ARQ quay ngược N vector (N go back ARQ). Cơ chế ARQ chọn lựa việc lặp lại. • Cơ chế FEC (Forward Error Control): phát hiện và tự sửa sai sử dụng các loại mã sửa lỗi. Khi có sai đơn (1 sai) người ta thường dùng các loại mã như: mã khối tuyến tính, mã Hamming, mã vòng… Khi có sai chùm (> 2 sai) người ta thường dùng các loại mã như: mã BCH, mã tích chập, mã Trellis, mã Tubor, mã Tubor Block, mã tổng hợp GC… 11 Vector sai – cô cheá söûa loãi Mã khối tuyến tính 12 • Mã khối tuyến tính được xây dựng dựa trên các kết quả của đại số tuyến tính là một lớp mã được dùng rất phổ biến trong việc chống nhiễu. • Định nghĩa: • Một mã khối có chiều dài n, k bit gồm 2k từ mã tuyến tính C(n,k) nếu và chỉ nếu 2k từ mã hình thành một không gian vectơ k chiều 2n, gồm tất cả các vectơ n thành phần trên trường Galois sơ cấp GF(2) ( bao gồm 2 phần tử {0,1} với 2 phép tính + và *). • Mã tuyến tính C(n,k) có mục đích mã hóa những khối tin (hay thông báo) k bit thành những từ mã n bit. Hay nói cách khác trong n bit của từ mã có chứa k bit thông tin. • Ví dụ: C (7,4): Từ mã dài 7 bit. Thông tin cần truyền: 4 bit. Cách biểu diễn mã – Ma trận sinh 13 • Mã tuyến tính C(n,k) là một không gian k chiều của không gian vectơ n thành phần, cho nên tồn tại k từ mã độc lập tuyến tính (g0,g1,…,gk-1) sao cho mỗi từ mã trong C là một tổ hợp tuyến tính của k từ mã này : • k từ mã này tạo thành một ma trận sinh cấp k x n như sau: Với: gi = (gi0, gi1… gi(n-1)) với i = 0, 1, …, k-1 )1,...,1,0}1,0{( ... 111100    kia gagagaw i kk                                  )1)(1(1)1(0)1( )1(11110 )1(00100 1 1 0 ... ... ... ... nkkk n n k nk ggg ggg ggg g g g G  Cách mã hóa 14 • Nếu u = (a0,a1,…,ak-1) , với ai =0/1 và 0i k-1, là thông tin cần được mã hóa. • Goïi t laø töø maõ phaùt ñi: t = t0 t1 ….tn-1 , Vôùi tj = 0 hoaëc 1 vaø 0  j  k-1 thì từ mã w tương ứng với t được hình thành bằng cách lấy t x G w = t x G = a0g0 + a1g1 +…+ ak-1gk-1 • Vì các từ mã tương ứng với các thông báo được sinh ra bởi G theo cách trên nên G được gọi là ma trận sinh của bộ mã. • Maõ khoái tuyeán tính heä thoáng coù caáu truùc: n-k bits kiểm tra K bits mang tin  Độ dài từ mã : n Ví dụ 15 • Cho ma trận sinh của một mã tuyến tính C(7,4) sau: • Nếu u = (u0 u1 u2 u3) = (1101) là thông tin cần mã hóa thì từ mã tương ứng là: t0 = u0.1 + u1.0 + u2.1 + u3.1 = u0+ u2 + u3 = 1 + 0 +1 = 0 t1 = u0.1 + u1.1 + u2.1 + u3.0 = u0 + u1 + u2 = 1+ 1 +0 = 0 t2 = u0.0 + u1.1 + u2.1 + u3.1 = u1 + u2 + u3 = 1+0+ 1 = 0 t3 = u0.1 + u1.0 + u2.0 + u3.0 = u0 = 1 t4 = u0.0 + u1.1 + u2.0 + u3.0 = u1 = 1 t5 = u0.0 + u1.0 + u2.1 + u3.0 = u2= 0 t6 = u0.0 + u1.0 + u2.0 + u3.1 = u3= 1 • => w = (0001101)                         1 1 0 0 0 1 0 0 0 0 1 0 0 0 1 1 1 0 1 0 0 1 0 1 1 0 1 1 g g g g G 3 2 1 0 74 (u0, u1, u2, u3) 1 1 0 1 0 0 0 0 1 1 0 1 0 0 1 1 1 0 0 1 0 1 0 1 0 0 0 1  ~~ .Gut • Bất kỳ k từ mã độc lập tuyến tính nào cũng có thể được dùng để làm ma trận sinh cho bộ mã. • Một bộ mã tuyến tính (không gian mã) có thể có nhiều ma trận sinh khác nhau cùng biểu diễn. • Mỗi ma trận sinh tương ứng với một cách mã hóa khác nhau. 16 Ma trận sinh Cách giải mã 17 • Từ ma trận sinh ở ví dụ trước, gọi: u = (a0, a1, a2, a3) là thông tin, w = (b0, b1, b2, b3 , b4 , b5 , b6) là từ mã tương ứng. • Ta có hệ phương trình liên hệ giữa u và w w = u x G ↔ b0 = a0 + a1 + a3 (1) b1 = a0 + a2 (2) b2 = a1 + a3 (3) b3 = a0 + a1 (4) b4 = a1 (5) b5 = a2 (6) b6 = a2 + a3 (7)                           1 1 0 0 0 1 0 0 0 0 1 0 0 0 1 1 1 0 1 0 0 1 0 1 1 0 1 1 4 3 1 0 74 g g g g G Cách giải mã (tt) 18 • Chọn bốn phương trình đơn giản nhất để giải các ai theo các b1 • Chọn các phương trình (4), (5), (6), (7) ta giải được: a0 = b3 + b4 a1 = b4 a2 = b5 a3 = b5 + b6 • Hệ phương trình trên gọi là hệ phương trình giải mã. • Có thể có nhiều hệ phương trình giải mã khác nhau, nhưng kết quả sẽ giống nhau.                           1 1 0 0 0 1 0 0 0 0 1 0 0 0 1 1 1 0 1 0 0 1 0 1 1 0 1 1 4 3 1 0 74 g g g g G Mã tuyến tính hệ thống 19 • Một mã tuyến tính C(n,k) được gọi là mã tuyến tính hệ thống nếu mỗi từ mã có một trong hai dạng sau: • Dạng 1: Từ mã bao gồm phần thông tin k bit đi trước và phần còn lại (gồm n-k bit) đi sau (phần này còn được gọi là phần dư thừa hay phần kiểm tra) • Dạng 2: Ngược lại của dạng 1, từ mã bao gồm phần kiểm tra đi trước và phần thông tin đi sau. . k bit thông tin n - k bit kiểm tra n - k bit kiểm tra k bit thông tin Ma trận sinh hệ thống 20 • Ví dụ:              1 1 1 0 0 1 1 1 1 1 0 1 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 )74(htG Mã hóa u = 1101 → w = u x Ght = 1101000 Giãi mã w = 0110100 → u = 0110                                          )( )1)(1( )1(0 1)1( 11 01 0)1( 10 00 )( )1(1 1 0 0 0 1 0 0 0 1 | knk knk kn kk kk knkkknk P P P P P P P P P PIG kn xét mã khối tuyến tính C(7,4)có thông báo cần mã hóa u = (u0, u1, u2, u3) & từ mã phát đi tương ứng t = (t0, t1, t2, t3, t4, t5, t6) Cho G(4,7) dạng không chính tắc ta đi tìm G(4,7) dạng chính tắc: Ví dụ G(4,7)= 1 1 0 1 0 0 0 0 1 1 0 1 0 0 0 0 1 1 0 1 0 0 0 0 1 1 0 1 (1) (2) (3) = (4) 1 1 0 1 0 0 0 0 1 1 0 1 0 0 1 1 1 0 0 1 0 1 0 1 0 0 0 1 1’=1 2’=2 3’=1+3 4’=1+2+4 )7,4( ~ G 21 Cho tin cần phát đi: u = (u0, u1, u2, u3) = (1 0 1 1) ta tìm từ mã phát đi theo 2 công thức 5 & 8 từ đó rút ra nhận xét Ví dụ (u0, u1, u2, u3) 1 1 0 1 0 0 0 0 1 1 0 1 0 0 1 1 1 0 0 1 0 1 0 1 0 0 0 1  ~~ .Gut t0 = u0.1 + u1.0 + u2.0 + u3.0 = u0 = 1 t1 = u0.1 + u1.1 + u2.0 + u3.0 = u0 + u1= 1+0 = 1 t2 = u0.0 + u1.1 + u2.1 + u3.0 = u1 + u2= 0+1 = 1 t3 = u0.1 + u1.0 + u2.1 + u3.1 = u0 + u2 + u3= 1+1 + 1 = 1 t4 = u0.0 + u1.1 + u2.0 + u3.1 = u1 + u3= 0+1 = 1 t5 = u0.0 + u1.0 + u2.1 + u3.0 = u2= 1 t6 = u0.0 + u1.0 + u2.0 + u3.1 = u3= 1 Vậy ta có từ mã phát đi t = (1 1 1 1 1 1 1) không có dạng mã khối tuyến tính 22 (u0, u1, u2, u3) 1 1 0 1 0 0 0 0 1 1 0 1 0 0 1 1 1 0 0 1 0 1 0 1 0 0 0 1  ~~ .Gut t0 = u0.1 + u1.0 + u2.1 + u3.1 = u0+ u2 + u3 = 1 + 1 +1 = 1 t1 = u0.1 + u1.1 + u2.1 + u3.0 = u0 + u1 + u2 = 1+ 0 + 1 = 0 t2 = u0.0 + u1.1 + u2.1 + u3.1 = u1 + u2 + u3 = 0+1+ 1 = 0 t3 = u0.1 + u1.0 + u2.0 + u3.0 = u0 = 1 t4 = u0.0 + u1.1 + u2.0 + u3.0 = u1 = 0 t5 = u0.0 + u1.0 + u2.1 + u3.0 = u2= 1 t6 = u0.0 + u1.0 + u2.0 + u3.1 = u3= 1 Vậy ta có từ mã phát đi: ( 1 0 0 1 0 1 1) có dạng mã khối tuyến tính 23 Ví dụ 24 • Dùng các phép biến đổi sơ cấp biển đổi các ma trận sinh sau thành ma trận sinh hệ thống. • Không phải mọi ma trận sinh đều có thể biến đổi thành ma trận sinh hệ thống.              1 0 1 1 1 0 0 0 0 1 1 0 1 1 0 1 0 0 1 0 0 0 0 1 1 1 1 1 74G              1 1 1 1 1 0 0 0 0 0 1 0 1 1 0 1 0 1 1 0 0 0 1 1 1 0 0 1 74G Phát hiện sai và sửa sai 25 • Nguyên lý phát hiện sai: Kiểm tra xem tổ hợp nhận có phải là từ mã hay không, nếu không thì tổ hợp nhận là sai. • Nguyên lý sửa sai: Kiểm tra xem tổ hợp nhận có khoảng cách Hamming gần với từ mã nào nhất, thì đó chính là từ mã đúng đã phát đi. • → Nguyên lý khoảng cách Hamming tối thiểu.  Không gian bù trực giao: • Cho S là một không gian k chiều của không gian V n chiều. Gọi Sd là tập tất cả các vectơ v trong V sao cho: • Sd được chứng minh là một không gian con của V và có số chiều là n-k. • Sd được gọi là không gian bù trừ trực giao của S và ngược lại. 0,  vuSu Cách phát hiện sai 26 • Hệ quả: • Mỗi ma trận G bất kỳ kích thước (k x n) với k hàng độc lập tuyến tính luôn tồn tại ma trận H kích thước (n-k)n với (n-k) hàng độc lập tuyến tính sao cho G x HT = 0, trong đó HT là ma trận chuyển vị của ma trận H. • Hay: các vectơ hàng của H đều trực giao với các vectơ hàng của G. • Cách phát hiện sai: • Nếu v là một từ mã được sinh ra từ ma trận G có ma trận trực giao tương ứng là H thì: V x HT = 0 • Ngược lại nếu V x HT = 0 thì v là một từ mã. Ma trận kiểm tra 27 • Ma trận kiểm tra H của một bộ mã có ma trận sinh Gkxn là ma trận có kích thước (n-k)n sao cho : G x HT = 0 • Ma trận sinh hệ thống có dạng Gkxn = [Ikk|Pk(n-k)] thì ma trận H(n-k)n = [Pk(n-k) T | I(n-k)(n-k)] Trong đó: I(n-k)(n-k) là ma trận đơn vị kích thước (n-k)(n-k), còn Pk(n-k) T là ma trận chuyển vị của ma trận Pk(n-k). Cho G không hệ thống, tính H? • VD: trên Z3, cho ma trận sinh của một mã như sau • Ta chuyển thành ma trận sinh của mã hệ thống tương đương bằng một phép hoán vị p=(1,4,6,2,5,3) các cột về dạng [I | B]. • Ta tính được H* tươngứng với G* là p-1.• • Tính H bằng hoán vị ngược Thử lại: GHT = 0. 17 28 Ma trận kiểm tra 29 • Ví dụ: Tìm ma trận kiểm tra của ma trận sinh hệ thống sau:              1 1 1 0 0 1 1 1 1 1 0 1 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 )74(htG            1 0 0 0 1 0 0 0 1 1 0 1 1 1 1 1 1 0 0 1 1 )73(htH Cách sửa sai 30 Syndrome – vectơ sửa sai (corrector)  S= v x HT được gọi là Syndrome hay vectơ sửa sai của v và được kí hiệu là s(v). v là từ mã khi và chỉ khi s(v)=0.  Từ ma trận H(n-k)n thành phần của Syndrome như sau: S0 = v0p00 + v1p10 + . . . + vk-1pk-1,0 + vk S1 = v0p01 + v1p11 + . . . + vk-1pk-1,1 + vk+1 ……………. Sn-k-1 = v0p0,n-k-1 + v1p1,n-k-1 + ...+ vk-1pk-1,n-k-1 + vn-1 – Gọi từ mã phát đi : t = (t0 t1 . . . . tn-1) (1) – Gọi từ mã thu được: r = (r0 r1 . . . . rn-1) (2) – Vector sai : e = (e0 e1 . . . en-1) (3) – Trong đó ei = 1 nếu ti  ri và ei = 0 nếu ti = ri Để phát hiện sai ta dùng thuật toán thử Syndrome: – S = r.HT = (s0 s1 . . . . sn-k-1) (4) gồm n-k thành phần – S=0 nếu và chỉ nếu r là từ mã phát (r  t) hoặc là tổ hợp tuyến tính của các từ mã (gọi là vector sai không phát hiện được). – S  0 thì r không phải là từ mã phát đi (r  t) và do đó có sai (e  0) Phương pháp giải mã mã khối tuyến tính: 31 Từ ma trận kiểm tra thành phần của Syndrome như sau: S0 = r0 + rn-kp00 + rn-k-1p10 + . . . + rn-ipk-1,0 S1 = r1 + rn-kp01 + rn-k-1p11 + . . . + rn-ipk-1,1  ……………. (5) Sn-k-1 = rn-k-1 + rn-kp0,n-k-1 + rn-k+ip11 + .+ rn-ipk-1,n-k-1 Từ (5) tương tự như mạch mã hóa, ta có mạch tính Syndrome như sau: Phương pháp giải mã mã khối tuyến tính 32 Mạch tính Syndrome r0 r1 rn-k p00 + p01 + + .... pk-1,0 Pk-1,1 Pk-1,n-k-1 P0,n-k-1 rn-1 so s1 sn-k-1 ... 33  Tính Syndrome của mã khối tuyến tính C(7,4) với ma trận H đã cho với vector thu: r = (r0 r1 r2 r3 r4 r5 r6) Ví dụ: S=r.HT= (r0 r1 r2 r3 r4 r5 r6) 1 0 0 0 1 0 0 0 1 1 1 0 0 1 1 1 1 1 1 0 1 = (S0 S1 S2) 34  S0 = r0.1 + r1.0 + r2.0 + r3.1 + r4.0 + r5.1 + r6.1 = r0+ r3 + r5 + r6  S1 = r0.0 + r1.1 + r2.0 + r3.1 + r4.1 + r5.1 + r6.0 = r1+ r3 + r4 + r5  S2 = r0.0 + r1.0 + r2.1 + r3.0 + r4.1 + r5.1 + r6.1 = r2+ r4 + r5 + r6 Mạch tính Syndrome của mã hệ thống tuyến tính C(7,4) 35 Khi xác định được một giá trị Syndrome S = (S0, S1. . . . Sn-k-1) ta có đến 2k vector sai tương ứng, nhưng ta chỉ chọn các vector sai nào có trọng số nhỏ nhất là vector sai có nhiều khả năng nhất. Trong thực tế khi tìm được Syndrome ta thấy S trùng với cột nào của ma trận kiểm tra H thì có sai ở vị trí tương ứng. Ví dụ: “ 1 1 1” trùng với cột thứ sáu tính từ trái sang của ma trận H, ta kết luận vector nhận được r sai ở vị trí r5. Ta chỉ việc đổi trị số của r5 từ 0 sang 1 hoặc ngược lại là được vector nhận được đúng (r=t) r = 1 0 0 1 0 0 1  e = 0 0 0 0 0 1 0 t = 1 0 0 1 0 1 1 -> đảo bit tại r5 Cách sửa sai 36 Ví dụ tính Syndrome 37 • Tính Syndrome của mã khối tuyến tính C(7,4) với ma trận sinh hệ thống sau: giả sử gửi tin: u=1001. Nhận được v = 1011011. Nhận xét gì về mẫu tin nhận được.              1 1 1 0 0 1 1 1 1 1 0 1 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 )74(htG Ví dụ tính Syndrome 38 S(v) = v.HT = (111)              1 1 1 0 0 1 1 1 1 1 0 1 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 )74(htG            1 0 0 0 1 0 0 0 1 1 0 1 1 1 1 1 1 0 0 1 1 )73(htH                        100 010 001 101 111 110 011 )73( T htH Cách sửa sai 39 • Qua ví dụ trên, ta thấy: • S(v) = (111) trùng với cột thứ 3 của H, nên ta sửa giá trị ở vị trí thứ 3. v  r = t 10110110010000 = 1001011 Vậy tin gửi đi là: 1001. Mã Hamming 40 •Với mọi số nguyên dương m  3, tồn tại mã Hamming với các thông số sau: Chiều dài từ mã: n = 2m – 1. Chiều dài phần tin: k = 2m – m – 1. Chiều dài phần kiểm tra: m = n –k Khả năng sửa sai: t = 1 •Cấu trúc ma trận kiểm tra H với các cột là một vector m chiều khác không. • H = [Imxm | P(n-k)k] •Mỗi cột của ma trận P là vector m chiều, có trọng số là 2 hoặc lớn hơn. Ví dụ: với m = 3, ma trận kiểm tra của mã (7,4) được viết dưới dạng (1) Trong thực tế để việc tạo và giải mã Hamming một cách đơn giản người ta đổi vị trí các cột trong ma trận H. Khi đó các bit kiểm tra xen kẽ với các bit mang tin chứ không còn tính chất khối, từ (1) ta có: (2) H(3,7) = 1 0 0 1 0 1 1 0 1 0 1 1 1 0 0 0 1 0 1 1 1 H = 0 0 0 1 1 1 1 0 1 1 0 0 1 1 1 0 1 0 1 0 1 41 Để việc tạo mã đơn giản ta chọn các bit kiểm tra x, y, z ở các vị trí tương ứng 2i với i = 0, 1, 2, . . ., nghĩa là các vị trí thứ nhất, thứ hai & thứ tư của các ký hiệu từ mã: t = (x, y, u0, z, u1, u2, u3) (3) Tạo mã: t.HT= (x, y, u0, z, u1, u2, u3) x 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 = 0 42 t = (x, y, u0, z, u1, u2, u3) (2) x.0 +y.0 +u0.0 +z.1 + u1.1 + u2.1 + u3.1 =0  z = u1 + u2 + u3 x.0 +y.1 +u0.1 +z.1 + u1.0 + u2.1 + u3.1 =0  y = u0 + u2 + u3 x.1 +y.0 +u0.1 +z.1 + u1.1 + u2.0 + u3.1 =0  x = u0 + u1 + u3 43 Tin cần phát đi: U = (u0, u1, u2, u3) = (1 0 1 1) x = u0 + u1 + u3 = 1+ 0+1= 0 y = u0 + u2 + u3 = 1+1+1 = 1 z = u1 + u2 + u3 = 0+1+1 = 0  Vậy từ mã phát đi sẽ là: t = ( 0 1 1 0 0 1 1) không có dạng mã khối. Giải mã Haming cũng giống như giải mã khối tuyến tính nhưng đơn giản hơn nhờ sử dụng ma trận kiểm tra H có dạng 2. Khi đó việc xác định vị trí ký hiệu sai tương đối thuận tiện. Ví dụ: 44 Mã Hamming (tt) 45 •Ví dụ: Với m = 3, ta có ma trận kiểm tra của bộ mã C(7,4) như sau:            1 0 1 1 1 1 1 1 0 0 1 1 1 0 0 0 1 0 0 0 1 73H Mã Hamming (tt) 46 • Trong thực tế để việc tạo và giải mã Hamming một cách đơn giản người ta đổi vị trí các cột trong ma trận H. Khi đó các bit kiểm tra xen kẽ với các bit mang tin chứ không còn tính chất khối. Và giá trị của cột hi khi này bằng i (i = 1,2,…) • Vị trí các bit kiểm tra ở các vị trí tương ứng 2i, với i = 0,1,2,… Ứng với các vị trí tương ứng của từ mã. c = (x,y,u0,z,u1,u2,u3)            1 1 1 0 1 1 1 0 1 0 0 1 1 1 0 0 1 0 1 0 0 73H Tạo mã 47 • Theo tính chất mã khối tuyến tính ta có: c.HT = 0 (x,y,u0,z,u1,u2,u3) x = 0. x = u0 + u1 + u3 y = u0 + u2 + u3 z = u1 + u2 + u3                       111 011 101 001 110 010 100 Tạo mã 48 • Với tin cần phát: u = 1011 • x = u0 + u1 + u3 = 1 + 0 + 1 = 0 • y = u0 + u2 + u3= 1 + 1 + 1 = 1 • z = u1 + u2 + u3= 0 + 1 + 1 = 0 • Vậy từ mã phát đi: c = 0110011 Giải mã 49 • Cách giải mã giống với giải mã, phát hiện lỗi sai và sửa lỗi của mã khối tuyến tính. • Tính Syndrome – vectơ sửa sai • S(v) = v.HT • Nếu S(v) khác 0, ta xem giá trị s(v) trùng với cột thứ mấy của ma trận H, thì có sai ở vị trí đó, và sửa lỗi. Giải mã 50 • Với từ mã thu được v = 0 0 1 1 0 1 1 • S(v) = v x HT = 110. Trùng với cột thứ 6 của ma trận H. Có nghĩa ký hiệu sai là ký hiệu thứ 6. 