Bài giảng Lý thuyết thông tin: Chương 5 - Bùi Văn Thành

Chia sẻ: Nguyễn Hà | Ngày: | Loại File: PDF | Số trang:50

Thêm vào BST

Báo xấu

913
lượt xem 66
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Chương 5 Mã hóa kênh truyền thuộc bài giảng lý thuyết thông tin, cùng nắm kiến thức trong chương này thông qua việc tìm hiểu các nội dung chính sau: khái niệm về mã phát hiện sai và sửa sai, mã khối tuyến tính.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Lý thuyết thông tin: Chương 5 - Bùi Văn Thành

CHƯƠNG 5 Mã hóa kênh truyền 1
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
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 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. 3
Nguyên lý mã hóa kiểm soá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 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. k bit k+n-k = n bit Phát Bộ mã KSL Thu + (n-k) bit Thông tin Với n-k: bit kiểm tra 4
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ỳ: p(n,t) = Cntpst(1-ps)n-t 5
Cơ chế phát hiện sai của mã hiệu.  Số từ mã có thể có: N0 = 2n  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  n 1 6
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)
Đ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
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: p’ = C21pqC31 pq2 + C22p2C32p2q 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
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
Vector sai – cô cheá söûa loã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
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
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 g 0  a1 g1  ...  ak 1 g k 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 g11 ... g1( n 1)   1   10 Gk n      ...        g k 1   g ( k 1) 0  g ( k 1)1 ... g ( k 1)( n 1)   Với: gi = (gi0, gi1… gi(n-1)) với i = 0, 1, …, k-1 13
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. • 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 14
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 4 7  g1    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
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
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=uxG ↔ 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 4 7   1     b3 = a0 + a1g 3   0 1 0 0 0 1 1   (4)     b4 = a1  g 4  (5) 1 0 1 0 0 0 1 b5 = a2 (6) b6 = a2 + a3 (7) 17
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 + b4 0  g 1 1 0 1 0 0 0  g   a1 G b4   1    = 1 0 1 1 1 0 0  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
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
Ma trận sinh hệ thống    1 0  0 P00 P01  P0 ( n  k 1)     0 1  0 P10 P11  P1( n  k 1 )   G k  n  I kk | Pk ( n  k )           0 0  1 P( k 1) 0 P( k 1)1  P( k 1)( n  k 1)    k  k    k         (nk )   • Ví dụ: Mã hóa 1 0 0 0 1 1 0 0 u = 1101 → w = u x Ght = 1101000 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