Bài giảng Cơ sở lí thuyết thông tin - Chương 3: Mã hóa kênh. Mã Khối tuyến tính - Phạm Hải Đăng

Cơ sở lí thuyết thông tin Chương 3: Mã hóa kênh Mã Khối tuyến tính TS. Phạm Hải Đăng 02/12/2013 Slice 1 Trường ĐH Bách Khoa Hà Nội Phần 1: Khái niệm cơ bản  Mã kênh/Mã sửa lỗi  Mã hóa kênh (channel Coding) hay còn gọi là mã sửa lỗi (Error Correction coding) là kỹ thuật khống chế, phát hiện và sửa lỗi trong quá trình truyền dữ liệu qua kênh có nhiễu.  Mã sữa lỗi sử dụng thông tin dư thừa (redundancy) được mã hóa thêm vào dữ liệu phía bên phát. Thông tin dư thừa sẽ được phía thu sử dụng để sửa lỗi - mà không cần yêu cầu phát lại tin. 02/12/2013 Slice 2 Trường ĐH Bách Khoa Hà Nội Phần 1: Khái niệm cơ bản  Phân loại lỗi  Lỗi độc lập thống kê: Lỗi xuất hiện trong quá trình truyền tin trên kênh truyền, xuất hiện độc lập không liên quan tới nhau. Ví dụ: nhiễu Gaussian.  Lỗi chùm: Lỗi có phân bố liên hệ với nhau. 02/12/2013 Slice 3 Trường ĐH Bách Khoa Hà Nội Phần 1: Khái niệm cơ bản Ví dụ: Kênh truyền tin không nhớ (Binary Symmetric Memoryless Channel).  Lỗi xảy ra với bit “0” và “1” với cùng xác suất p (symmetric)  Lỗi xảy ra ngẫu nhiên và độc lập giữa các bit (memoryless) 02/12/2013 Slice 4 Trường ĐH Bách Khoa Hà Nội 1-p IN OUT 0 0 1 1 1-p p p p là xác suất lỗi – BER Bit Error Rate (BER) Phần 1: Khái niệm cơ bản Ví dụ: Kênh truyền tin đa đường 02/12/2013 Slice 5 Trường ĐH Bách Khoa Hà Nội receiving signal time strength 0 sending signal Phần 1: Khái niệm cơ bản Ví dụ: Kênh truyền tin đa đường 02/12/2013 Slice 6 Trường ĐH Bách Khoa Hà Nội RX power TX power Channel Fading Phần 1: Khái niệm cơ bản Phân loại mã sửa lỗi:  Mã khối (block codes): thông tin được mã hóa và chèn thêm phần dư thừa theo từng khối.  Mã khối  Mã khối tuyến tính  Mã vòng CRC  Mã BCH, Reed-Solomon, LDPC  Mã chập (Convolutional codes): thông tin được biến đổi theo các hàm truyền đạt (phép tích chập). Không có giới hạn rõ ràng giữa thông tin và phần dư thừa.  Mã chập (covolutional codes)  Mã Turbo 02/12/2013 Slice 7 Trường ĐH Bách Khoa Hà Nội Phần 2: Các khái niệm cơ bản của mã hóa sửa lỗi  Tốc độ mã  Khoảng cách Hamming (Hamming distance)  Khoảng cách tối thiểu (minimum distance)  Ma trận sinh, mã trận kiểm tra chẵn lẻ. 02/12/2013 Slice 8 Trường ĐH Bách Khoa Hà Nội Phần 2: Các khái niệm cơ bản của mã hóa sửa lỗi Tốc độ mã Giả thiết là tập hợp 2 phần tử ‘0’ và ‘1’. biểu diễn vector n phần tử của Số binary là tập hợp điểm trong không gian Mã là mã chấp nhận bit đầu vào và tạo ra bit đầu ra. Định nghĩa: tốc độ mã của mã là Ví dụ: Mã lặp (repetition code) nhận 1 bit đầu vào và tạo ra n bit lặp lại ở đầu ra. Tốc độ mã là 02/12/2013 Slice 9 Trường ĐH Bách Khoa Hà Nội 2 2 n 2 ( , )n k 2k 2 n ( , )n k k n ( , )n k k R n  ( ,1)n 1 R n  Phần 2: Các khái niệm cơ bản của mã hóa sửa lỗi Ma trận sinh Với biểu diễn thông tin (message). là từ mã (codeword) của mã lặp Quá trình mã hóa được biểu diễn dưới dạng ma trận. Ma trận sinh của mã lặp là 02/12/2013 Slice 10 Trường ĐH Bách Khoa Hà Nội m C ( ,1)n  , , ,...C m m m m C mG  1,1,1,...,1G  G Phần 2: Các khái niệm cơ bản của mã hóa sửa lỗi  Biểu diễn mã lặp (3,1) trong không gian  Khoảng cách Hamming trong mã binary được tính bằng số các điểm khác biệt trong 2 từ mã. 02/12/2013 Slice 11 Trường ĐH Bách Khoa Hà Nội  1 1,1,1C   0 0,0,0C      1 2 12 1,0,1,1,1,0 1,1,0,1,1,1 3 C C d    Phần 2: Các khái niệm cơ bản của mã hóa sửa lỗi  Định nghĩa : Khoảng cách tối thiểu (min distance) là khoảng cách Hamming nhỏ nhất giữa 2 từ mã bất kì.  Phương pháp giải mã ML: tìm kiếm từ mã có khoảng cách gần nhất với từ mã thu được. 02/12/2013 Slice 12 Trường ĐH Bách Khoa Hà Nội Phần 2: Các khái niệm cơ bản của mã hóa sửa lỗi  Liên hệ giữa khoảng cách Hamming tối thiểu và khả năng phát hiện và sửa lỗi. Với mã binary Khả năng phát hiện lỗi Khả năng sửa lỗi 02/12/2013 Slice 13 Trường ĐH Bách Khoa Hà Nội ( , )n k min 1d  min 1 2 d t        Phần 2: Các khái niệm cơ bản của mã hóa sửa lỗi  Tỷ lệ lỗi bit (BER – Bit Error Rate) của mã lặp trong môi trường kênh AWGN (Additive White Gaussian Noise) 02/12/2013 Slice 14 Trường ĐH Bách Khoa Hà Nội Phần 2: Các khái niệm cơ bản của mã hóa sửa lỗi 02/12/2013 Slice 15 Trường ĐH Bách Khoa Hà Nội  Ví dụ mã kiểm tra chẵn  Trong trường hợp n = k+1, bản tin được bổ sung thêm 1 bit kiểm tra chẵn lẻ  Trong trường hợp số chẵn các bit ‘1’, Bit kiểm tra chẵn lẽ có giá trị  Trong trường hợp số lẻ các bit ‘1’, bit kiểm tra có giá trị  Bit kiểm tra chẵn lẽ được thêm vào đảm bảo số chẵn các bit ‘1’ trong từ mã.  Mã kiểm tra chẵn lẻ chỉ phát hiện được (tối đa) 1 lỗi, không có khả năng sửa lỗi. 1 (mod 2) k ii q m   1 q Phần 2: Các khái niệm cơ bản của mã hóa sửa lỗi 02/12/2013 Slice 16 Trường ĐH Bách Khoa Hà Nội  Ví dụ 1: Mã kiểm tra chẵn lẽ (6,5)  Bản tin m = (10110) => từ mã c=(101101)  Bản tin m = (11011) => từ mã c=(110110) Phần 2: Các khái niệm cơ bản của mã hóa sửa lỗi 02/12/2013 Slice 17 Trường ĐH Bách Khoa Hà Nội  Ví dụ 2: Bảng mã kiểm tra chẵn lẽ (4,3) Dataword Codeword 111 011 101 001 110 010 100 000 1111 0011 0101 1001 0110 1010 1100 0000  Mã khối (n,k) được biểu diễn dạng vector Bản tin d=(d1 d2.dk) Từ mã c=(c1 c2..cn)  Mã khối được xây dựng c=dG Với G là ma trận sinh                           k 2 1 21 22221 11211 a . a a ... ...... ... ... G knkk n n aaa aaa aaa Phần 3: Mã khối tuyến tính Phần 3: Mã khối tuyến tính  Để đảm bảo 2 bản tin không có chung 1 từ mã (không thể giải mã/sửa lỗi), các hệ số phải độc lập tuyến tính.  Nếu là 2 từ mã bất kì cũng là 1 từ mã  Hệ quả: khối gồm toàn bit ‘0’ cũng là 1 từ mã 1 c a k i i i d   a i ic kc i kc c c  Khả năng sửa lỗi của mã khối tuyến tính  Khoảng cách Hamming của mã khối tuyến tính là khoảng cách Hamming nhỏ nhất của các từ mã khác ‘0’  Để tìm khoảng cách Hamming nhỏ nhất, cần tìm kiểm tra 2k từ mã để tìm khoảng cách Hamming nhỏ nhất. Phần 3: Mã khối tuyến tính Phần 3: Mã khối tuyến tính  Với mã (4,2), có ma trận sinh  Với d=[1,1]        1010 1101 G 0111 ____ 1010 1101 c    a1 = [1011] a2 = [0101] Ví dụ 1: mã khối tuyến tính Error Syndrome  Để sửa lỗi mã khối tuyến tính, sử dụng phương pháp Error Syndrome  Nếu cr là từ mã thu được ở phía thu, vector phát hiện lỗi (error syndrome) s của cr s = crH T  Nếu cr bị lỗi, gọi e là vector lỗi cr = c + e do đó s = (c + e) HT = cHT + eHT s = 0 + eHT Vector syndrome có giá trị chỉ phụ thuộc vào vector lỗi e. Phần 3: Mã khối tuyến tính – Giải mã sửa lỗi Error Syndrome  Nhận xét: nếu cộng vector e với các từ mã khác thì vẫn thu được 1 vector syndrome.  Tổng cộng có 2(n - k) syndromes, 2n vector lỗi.  Ví dụ: với mã (3,2), có 2 syndromes và 8 vector lỗi e. Rõ ràng không thể sửa tất cả các lỗi trong trường hợp này.  Ví dụ: với mã (7,4) có 8 syndromes và 128 vector lỗi e.  Vì vậy, với 8 syndromes, ta cần bố trí các giá trị khác nhau để sửa được 7 lỗi (lỗi 1 bit) và 1 trường hợp không lỗi s=0. Phần 3: Mã khối tuyến tính – Giải mã sửa lỗi Bảng liệt kê lỗi  Bảng liệt kê lỗi được xây dựng như sau: c1 (all zero) e1 e2 e3 eN c2+e1 c2+e2 c2+e3 c2+eN c2 cM+e1 cM+e2 cM+e3 cM+eN cM s0 s1 s2 s3 sN Các hàng đều có chung giá trị syndrome Các hàng khác nhau có vector syndrome khác nhau Bảng có 2k cột (tương ứng với các từ mã hợp lệ) và 2n-k hàng (số lượng các syndrome) Phần 3: Mã khối tuyến tính – Giải mã sửa lỗi  Bảng liệt kê lỗi được xây dựng theo cách  Liệt kê tất cả các lỗi 1 bit  Liệt kê tất cả các lỗi 2 bit   Kiểm tra đảm bác các lỗi được bổ sung vào bảng có vector syndrome khác nhau. Việc xây dựng bảng kết thúc khi sử dụng hết các vector syndrome.  Để giải mã:  Tính vector syndrome theo công thức s = 0 + eHT  Tra bảng tương ứng, tìm vector lỗi e tương ứng.  Cộng modulo vector e và từ mã thu được để giải mã c = cr + e Phần 3: Mã khối tuyến tính – Giải mã sửa lỗi Phần 3: Mã khối tuyến tính – Mã hệ thống  Mã hệ thống có phần thông tin và phần kiểm tra được phân tách trong từ mã, phần thông tin là không thay đổi so với ban đầu  Ma trận sinh của mã hệ thống có dạng  P|I ..1..00 ................ ..0..10 ..0..01 G 21 22221 11211               kRkk R R ppp ppp ppp k R R = n - k  Với mã hệ thống, ma trận kiểm tra được xây dựng G = [ I | P] and so H = [-PT | I]  Ví dụ: mã (7,4) với khoảng cách Hamming dmin= 3                1111000 0110100 1010010 1100001 P|I G              1001011 0101101 0011110 I|P- H T Phần 3: Mã khối tuyến tính – Mã hệ thống Tìm vector syndrome trong ví dụ  Từ mã thu được cr = [1101001]    000 100 010 001 111 011 101 110 1001011Hc s Tr                         Phần 3: Mã khối tuyến tính – Mã hệ thống  Mã Hamming là dạng đặc biệt của mã khối tuyến tính  Với mỗi  Từ mã có độ dài  Bản tin có độ dài  Tốc độ mã  Khoảng cách Hamming , khả năng sửa 1 lỗi  Mã Hamming là mã có tốc độ mã R lớn nhất với cùng khoảng cách Hamming Phần 4: Mã Hamming 2r  2 1rn   2 1rk r   1 2 1r k r R n     min 3d  min 3d   Mã Hamming (7,4) dạng hệ thống                1111000 0110100 1010010 1100001 P|I G              1001011 0101101 0011110 I|P- H T              1001011 0101010 0011001 0000111 G            1010101 1100110 1111000 H Phần 4: Mã Hamming (7,4)  Mã Hamming (7,4) dạng không hệ thống  Ví dụ: mã Hamming (7,4) không hệ thống d = 1011 c = 1110000 + 0101010 + 1101001 = 0110011 e = 0010000 cr= 0100011 s = crH T = eHT = 011  Chú ý: giá trị vector syndrome là vị trí lỗi. Phần 4: Mã Hamming (7,4) Phần 4: Mã Hamming (7,4) – BER  For a given channel bit error rate (BER), what is the BER after correction (assuming a memoryless channel, i.e., no burst errors)?  To do this we will compute the probability of receiving 0, 1, 2, 3, . errors  And then compute their effect Bit Error Rates after Decoding  Example – A (7,4) Hamming code with a channel BER of 1%, i.e., p = 0.01 P(0 errors received) = (1 – p)7 = 0.9321 P(1 error received) = 7p(1 – p)6 = 0.0659 P(3 or more errors) = 1 – P(0) – P(1) – P(2) = 0.000034 002.0)1( 2 67 received) errors P(2 52    pp Bit Error Rates after Decoding  Single errors are corrected, so, 0.9321+ 0.0659 = 0.998 codewords are correctly detected  Double errors cause 3 bit errors in a 7 bit codeword, i.e., (3/7)*4 bit errors per 4 bit dataword, that is 3/7 bit errors per bit. Therefore the double error contribution is 0.002*3/7 = 0.000856 Bit Error Rates after Decoding  The contribution of triple or more errors will be less than 0.000034 (since the worst that can happen is that every databit becomes corrupted)  So the BER after decoding is approximately 0.000856 + 0.000034 = 0.0009 = 0.09%  This is an improvement over the channel BER by a factor of about 11 Perfect Codes So, errors 3 toupcorrect to 6 2)-1)(n-n(n 2 1)-n(n n1 errors 2 toupcorrect to 2 1)-n(n n1 error 1 toupcorrect to 12    nR If equality then code is Perfect Only known perfect codes are SEC Hamming codes and TEC Golay (23,12) code (dmin=7). Using previous equation yields )1223(11 222048 6 2)-1)(23-23(23 2 1)-23(23 231 