›
›

Bài giảng Lý thuyết thông tin - Chương 5: Mã hóa kênh truyền

pdf 50 trang phuongnguyen 5030
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Lý thuyết thông tin - Chương 5: Mã hóa kênh truyền", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfbai_giang_ly_thuyet_thong_tin_chuong_5_ma_hoa_kenh_truyen.pdf

Nội dung text: Bài giảng Lý thuyết thông tin - Chương 5: Mã hóa kênh truyền

  1. CHƯƠNG 5 Mã hĩa kênh truyền 1
  2. Nội dung 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 2
  3. Vấn đề 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 ngồ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 sốt lỗi là một vấn đề hết sức quan trọng. 3
  4. Nguyên lý mã hĩa kiểm sốt lỗi • 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 số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. k bit k+n-k = n bit Bộ mã KSL Phát Thu + (n-k) bit Thơng tin Với n-k: bit kiểm tra 4
  5. Khái niệm về mã phát hiện sai và sửa sai. 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ỳ: t t n-t p(n,t) = Cn ps (1-ps) 5
  6. Cơ chế phát hiện sai của mã hiệu. n Số từ mã cĩ thể cĩ: N0 = 2 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: 2n 2k 1 E  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ĩ: 2n 2k n6 1
  7. Khả năng phát hiện và sửa sai 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)
  8. Điều kiện phát hiện 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
  9. Hệ số sai khơng phát hiện được 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: 1 1 2 2 2 2 2 p’ = C2 pqC3 pq + C2 p C3 p q 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
  10. Phương trình đường truyền • 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
  11. Vector sai – cơ chế sửa lỗi 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
  12. Mã khối tuyến tính • 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. 12
  13. Cách biểu diễn mã – Ma trận sinh • 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 : w a0 g0 a1g1 ak 1gk 1 (ai {0,1}i 0,1, ,k 1) • k từ mã này tạo thành một ma trận sinh cấp k x n như sau: g 0 g 00 g 01 g 0(n 1) g g g g G 1 10 11 1(n 1) k n     g g g g k 1 (k 1)0 (k 1)1 (k 1)(n 1) 13 Với: gi = (gi0, gi1 gi(n-1)) với i = 0, 1, , k-1
  14. Cách mã hĩa • 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. • Gọi t là từ mã phát đi: t = t0 t1 .tn-1 , Với tj = 0 hoặc 1 và 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ã. • Mã khối tuyến tính hệ thống có cấu trúc: n-k bits kiểm tra K bits mang tin  Độ dài từ mã : n 14
  15. Ví dụ • Cho ma trận sinh của một mã tuyến tính C(7,4) sau: 1 1 0 1 0 0 0 g 0 1 0 1 1 1 0 0 g 1 G 4 7 g 2 0 1 0 0 0 1 1 g 3 1 0 1 0 0 0 1 • Nếu u = (u0 u1 u2 u3) = (1101) là thơng tin cần mã hĩa thì từ mã tương ứng là: 1 1 0 1 0 0 0 t u.G (u0, u1, u2, u3) 0 1 1 0 1 0 0 ~ ~ 1 1 1 0 0 1 0 1 0 1 0 0 0 1 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) 15
  16. Ma trận sinh • 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
  17. Cách giải mã • 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) g 0 1 1 0 1 0 0 0 b2 = a1 + a3g (3) 1 0 1 1 1 0 0 G 1 b = 4a 7 + a (4) 3 0 1g 3 0 1 0 0 0 1 1 b4 = a1 g 4 (5) 1 0 1 0 0 0 1 b5 = a2 (6) b6 = a2 + a3 (7) 17
  18. Cách giải mã (tt) • 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 + b 4g 0 1 1 0 1 0 0 0 g 1 0 1 1 1 0 0 a1 = b4 1 G 4 7 g 3 0 1 0 0 0 1 1 a2 = b5 g 4 1 0 1 0 0 0 1 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. 18
  19. Mã tuyến tính hệ thống • 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) k bit thơng tin n - k bit 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. . n - k bit kiểm tra k bit thơng tin 19
  20. Ma trận sinh hệ thống 1 0 0 P P  P 00 01 0(n k 1) 0 1 0 P P  P 10 11 1( n k 1) G I | P  k n kk k ( n k )      0 0 1P P  P  ( k 1)0 ( k 1)1 (k 1)( n k 1)  k k k (n k ) • Ví dụ: Mã hĩa 1 0 0 0 1 1 0 u = 1101 → w = u x Ght = 1101000 0 1 0 0 0 1 1 G ht ( 4 7 ) Giãi mã 0 0 1 0 1 1 1 w = 0110100 → u = 0110 0 0 0 1 1 0 1 20
  21. Ví dụ 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: 1 1 0 1 0 0 0 (1) 1 1 0 1 0 0 0 1’=1 0 1 1 0 1 0 0 (2) 0 1 1 0 1 0 0 2’=2 G(4,7)= 0 0 1 1 0 1 0 (3) G(4,7) = 1 1 1 0 0 1 0 3’=1+3 ~ 0 0 0 1 1 0 1 (4) 1 0 1 0 0 0 1 4’=1+2+4 21
  22. Ví dụ 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 1 1 0 1 0 0 0 0 1 1 0 1 0 0 t u.G (u0, u1, u2, u3) 1 1 1 0 0 1 0 ~ ~ 1 0 1 0 0 0 1 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 221 1 1 1) khơng cĩ dạng mã khối tuyến tính
  23. 1 1 0 1 0 0 0 t u.G (u , u , u , u ) 0 1 1 0 1 0 0 ~ ~ 0 1 2 3 1 1 1 0 0 1 0 1 0 1 0 0 0 1 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
  24. Ví dụ • 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. 1 1 0 1 0 0 1 1 1 0 1 0 0 1 1 0 1 0 1 0 1 0 1 1 0 1 0 1 G G 4 7 1 0 0 1 1 0 0 4 7 0 0 1 1 0 0 1 1 0 0 1 0 1 1 1 0 0 1 0 1 1 • 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. 24
  25. Phát hiện sai và sửa sai • 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:  u S , u v 0 • 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. 25
  26. Cách phát hiện sai • 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ã. 26
  27. Ma trận kiểm tra • 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)] T thì ma trận H(n-k)n = [Pk(n-k) | 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 T Pk(n-k) là ma trận chuyển vị của ma trận Pk(n-k). 27
  28. 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 đương btươngằng một phép hố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à • Tính H bằng hốn vị ngược p-1. • Thử lại: GHT = 0. 17 28
  29. Ma trận kiểm tra • Ví dụ: Tìm ma trận kiểm tra của ma trận sinh hệ thống sau: 1 0 0 0 1 1 0 0 1 0 0 0 1 1 G ht ( 4 7 ) 0 0 1 0 1 1 1 0 0 0 1 1 0 1 1 0 1 1 1 0 0 H 1 1 1 0 0 1 0 ht ( 3 7 ) 0 1 1 1 0 0 1 29
  30. Cách sửa sai 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 30
  31. Phương pháp giải mã mã khối tuyến tính: – 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 tốn thử Syndrome: T – S = r.H = (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) 31
  32. Phương pháp giải mã mã khối tuyến tính 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: 32
  33. Mạch tính Syndrome r0 r1 rn-k rn-1 P0,n-k-1 p00 p01 Pk-1,1 pk-1,0 Pk-1,n-k-1 + + + sn-k-1 so s1 33
  34. Ví dụ: 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) 1 0 0 0 1 0 0 0 1 1 1 0 = (S0 S1 S2) T S=r.H = (r0 r1 r2 r3 r4 r5 r6) 0 1 1 1 1 1 1 0 1 34
  35. 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
  36. Cách sửa sai 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 36
  37. Ví dụ tính Syndrome • 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 0 0 0 1 1 0 0 1 0 0 0 1 1 G ht ( 4 7 ) 0 0 1 0 1 1 1 0 0 0 1 1 0 1 37
  38. Ví dụ tính Syndrome 1 0 0 0 1 1 0 0 1 0 0 0 1 1 G ht ( 4 7 ) 0 0 1 0 1 1 1 1 1 0 0 0 0 1 1 0 1 0 1 1 1 1 1 1 0 1 1 1 0 0 T H ht ( 3 7 ) 1 0 1 H 1 1 1 0 0 1 0 ht ( 3 7 ) 1 0 0 0 1 1 1 0 0 1 0 1 0 0 0 1 S(v) = v.HT = (111) 38
  39. Cách sửa sai • 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. 39
  40. Mã Hamming •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. 40
  41. 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 0 0 1 0 1 1 H(3,7) = 0 1 0 1 1 1 0 (1) 0 0 1 0 1 1 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ĩ: 0 0 0 1 1 1 1 H = 0 1 1 0 0 1 1 (2) 1 0 1 0 1 0 1 41
  42. Để 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ã: 0 0 1 0 1 0 0 1 1 T t.H = (x, y, u0, z, u1, u2, u3) x 1 0 0 = 0 1 0 1 1 1 0 42 1 1 1
  43. 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
  44. Ví dụ: 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. 44
  45. Mã Hamming (tt) •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 0 1 0 1 1 H 0 1 0 1 1 1 0 3 7 0 0 1 0 1 1 1 45
  46. Mã Hamming (tt) • 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ã. 0 0 0 1 1 1 1 .c = (x,y,u ,z,u ,u ,u ) H 0 1 20 13 1 0 0 1 1 3 7 1 0 1 0 1 0 1 46
  47. Tạo mã • Theo tính chất mã khối tuyến tính ta cĩ: 0 0 1 c.HT = 0 0 1 0 (x,y,u ,z,u ,u ,u ) x 0 1 1 = 0. 0 1 2 3 1 0 0 1 0 1 1 1 0 1 1 1 x = u0 + u1 + u3 y = u0 + u2 + u3 z = u1 + u2 + u3 47
  48. Tạo mã • 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 48
  49. Giải mã • 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. 49
  50. Giải mã • 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. v = 0 0 1 1 0 0 1 u = 1001. 50