Bài giảng Cơ sở lí thuyết thông tin - Chương 5: Mã tích chập. Thuật toán giải mã Viterbi - Phạm Hải Đăng

Cơ sở lí thuyết thông tin Chương 5: Mã tích chập Thuật toán giải mã Viterbi TS. Phạm Hải Đăng 16/12/2013 Slice 1 Trường ĐH Bách Khoa Hà Nội Phần 1: Khái niệm cơ bản  Định nghĩa Mã tích chập  Mã tích chập là 1 dạng mã tuyến tính.  Mã tích chập có cấu trúc giống 1 bộ lọc số - phép tích chập.  Bộ mã hóa tích chập có thể coi như 1 tập hợp các bộ lọc số - hệ thống tuyến tính, bất biến theo thời gian.  Đầu vào của bộ mã hóa tích chập là một dòng dữ liệu (data stream) biểu diễn dạng vector  Tốc độ mã R=k/n  Chiều dài ràng buộc K (constraint length) là kích thước của thanh ghi (số lượng D-FF). 16/12/2013 Slice 2 Trường ĐH Bách Khoa Hà Nội (1) (1) (1) (1) 2 0 1 2 (2) (2) (2) (2) 2 0 1 2 ( ) ... ( ) ... m x m m x m x m x m m x m x       (1) (2)( ) ( ) ( ) ...m x m x m x    Phần 1: Khái niệm cơ bản  Ví dụ: Mã tích chập có R=1/2  Với đầu vào  Đầu ra  Biểu diễn đầu ra dạng vector 16/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ụ: Mã tích chập có R=1/2  Với đầu vào Biểu diễn dạng đa thức  Đầu ra dạng đa thức Với đa thức sinh 16/12/2013 Slice 4 Trường ĐH Bách Khoa Hà Nội Phần 1: Khái niệm cơ bản  Ví dụ: Mã tích chập dạng hệ thống có ma trận đa thức sinh Biểu diễn dạng sơ đồ mạch 16/12/2013 Slice 5 Trường ĐH Bách Khoa Hà Nội Phần 1: Khái niệm cơ bản  Biểu diễn dạng tổng quan của đa thức bản tin và ma trận đa thức sinh  Từ mã của mã tích chập 16/12/2013 Slice 6 Trường ĐH Bách Khoa Hà Nội Bộ mã hóa tích chập R=1/2 Bộ mã hóa tích chập R=1/2 Phần 2: Biểu diễn sơ đồ trạng thái và sơ đồ lưới của mã tích chập  Mã tích chập là một máy trạng thái (state machine), có thể biểu diễn bằng sơ đồ chuyển trạng thái  Giá trị D-FF là trạng thái (state). Số lượng trạng thái  Đầu vào là kích thích chuyển trạng thái  Mũi tên mô tả quá trình chuyển trạng thái, với giá trị đầu vào/đầu ra. Ví dụ: 0/00 – Đầu vào m=0, đầu ra c=[00] 16/12/2013 Slice 7 Trường ĐH Bách Khoa Hà Nội 2K Phần 2: Biểu diễn sơ đồ trạng thái và sơ đồ lưới của mã tích chập  Từ sơ đồ chuyển trạng thái, có thể chuyển sang sơ đồ lưới 16/12/2013 Slice 8 Trường ĐH Bách Khoa Hà Nội Phần 3: Thuật toán giải mã Viterbi Sơ đồ lưới của mã tích chập Đầu vào m=[1,1,0,0,1,0,1,0] 16/12/2013 Slice 9 Trường ĐH Bách Khoa Hà Nội 2 2G( ) 1 1x x x x      Phần 3: Thuật toán giải mã Viterbi  Thuật toán giải mã Viterbi thuộc lớp thuật toán giải mã ML (Maximum Likelihood).  Thuật toán Viterbi là thuật toán tìm đường ngắn nhất, với quãng đường được tính toán là tổng khoảng cách Hamming của các nhánh trung gian.  P là trạng thái (state) đích, S trạng thái trung gian.  P0 là tổng khoảng cách quãng đường tới state P với bit đầu vào giá trị ‘0’, đi qua state S0. BR0 là khoảng cách Hamming (đầu ra) của nhánh S0-P  P1 là tổng khoảng cách quãng đường tới state P với bit đầu vào giá trị ‘1’, đi qua state S1. BR1 là khoảng cách Hamming (đầu ra) của nhánh S1-P 16/12/2013 Slice 10 Trường ĐH Bách Khoa Hà Nội Phần 3: Thuật toán giải mã Viterbi Ví dụ: mã tích chập Đầu vào m=[1,1,0,0,1,0,1,0] Từ mã thu được Xuất phát từ trạng thái 0 (giá trị các D-FF được reset về giá trị bit ‘0’). Tại t=1. Khoảng cách Hamming giữa đầu ra [11] và nhánh 0-0 và 0-1 lần lượt là 2 và 0 16/12/2013 Slice 11 Trường ĐH Bách Khoa Hà Nội 2 2G( ) 1 1x x x x      Phần 3: Thuật toán giải mã Viterbi Ví dụ: mã tích chập Đầu vào m=[1,1,0,0,1,0,1,0] Từ mã thu được Xuất phát từ trạng thái 0 (giá trị các D-FF được reset về giá trị bit ‘0’). Tại t=2, tính các khoảng cách Hamming tới các state 16/12/2013 Slice 12 Trường ĐH Bách Khoa Hà Nội 2 2G( ) 1 1x x x x      Phần 3: Thuật toán giải mã Viterbi Ví dụ: mã tích chập Đầu vào m=[1,1,0,0,1,0,1,0] Từ mã thu được Xuất phát từ trạng thái 0 (giá trị các D-FF được reset về giá trị bit ‘0’). Tại t=3, tính các khoảng cách Hamming tới các state 16/12/2013 Slice 13 Trường ĐH Bách Khoa Hà Nội 2 2G( ) 1 1x x x x      Phần 3: Thuật toán giải mã Viterbi Ví dụ: mã tích chập Đầu vào m=[1,1,0,0,1,0,1,0] Từ mã thu được Xuất phát từ trạng thái 0 (giá trị các D-FF được reset về giá trị bit ‘0’). Tại t=3: xuất hiện 2 tuyến đường cùng tới 1 trạng thái. So sánh là loại bỏ tuyến đường có khoảng cách Hamming lớn. Tuyến đường giữ lại được biểu diễn như hình vẽ 16/12/2013 Slice 14 Trường ĐH Bách Khoa Hà Nội 2 2G( ) 1 1x x x x      Phần 3: Thuật toán giải mã Viterbi Ví dụ: mã tích chập Đầu vào m=[1,1,0,0,1,0,1,0] Từ mã thu được Xuất phát từ trạng thái 0 (giá trị các D-FF được reset về giá trị bit ‘0’). Tại t=4: Mở rộng sơ đồ lưới, tính khoảng cách Hamming 16/12/2013 Slice 15 Trường ĐH Bách Khoa Hà Nội 2 2G( ) 1 1x x x x      Phần 3: Thuật toán giải mã Viterbi Ví dụ: mã tích chập Đầu vào m=[1,1,0,0,1,0,1,0] Từ mã thu được Xuất phát từ trạng thái 0 (giá trị các D-FF được reset về giá trị bit ‘0’). Tại t=4: Loại bỏ nhánh có khoảng cách Hamming lớn 16/12/2013 Slice 16 Trường ĐH Bách Khoa Hà Nội 2 2G( ) 1 1x x x x      Phần 3: Thuật toán giải mã Viterbi Ví dụ: mã tích chập Đầu vào m=[1,1,0,0,1,0,1,0] Từ mã thu được Xuất phát từ trạng thái 0 (giá trị các D-FF được reset về giá trị bit ‘0’). Tại t=5: Mở rộng sơ đồ lưới, tính khoảng cách Hamming 16/12/2013 Slice 17 Trường ĐH Bách Khoa Hà Nội 2 2G( ) 1 1x x x x      Phần 3: Thuật toán giải mã Viterbi Ví dụ: mã tích chập Đầu vào m=[1,1,0,0,1,0,1,0] Từ mã thu được Xuất phát từ trạng thái 0 (giá trị các D-FF được reset về giá trị bit ‘0’). Tại t=5: Loại bỏ nhánh có khoảng cách Hamming lớn 16/12/2013 Slice 18 Trường ĐH Bách Khoa Hà Nội 2 2G( ) 1 1x x x x      Phần 3: Thuật toán giải mã Viterbi Ví dụ: mã tích chập Đầu vào m=[1,1,0,0,1,0,1,0] Từ mã thu được Xuất phát từ trạng thái 0 (giá trị các D-FF được reset về giá trị bit ‘0’). Tại t=6: Mở rộng sơ đồ lưới, tính khoảng cách Hamming 16/12/2013 Slice 19 Trường ĐH Bách Khoa Hà Nội 2 2G( ) 1 1x x x x      Phần 3: Thuật toán giải mã Viterbi Ví dụ: mã tích chập Đầu vào m=[1,1,0,0,1,0,1,0] Từ mã thu được Xuất phát từ trạng thái 0 (giá trị các D-FF được reset về giá trị bit ‘0’). Tại t=6: Loại bỏ nhánh có khoảng cách Hamming lớn 16/12/2013 Slice 20 Trường ĐH Bách Khoa Hà Nội 2 2G( ) 1 1x x x x      Phần 3: Thuật toán giải mã Viterbi Ví dụ: mã tích chập Đầu vào m=[1,1,0,0,1,0,1,0] Từ mã thu được Xuất phát từ trạng thái 0 (giá trị các D-FF được reset về giá trị bit ‘0’). Tại t=7: Mở rộng sơ đồ lưới, tính khoảng cách Hamming 16/12/2013 Slice 21 Trường ĐH Bách Khoa Hà Nội 2 2G( ) 1 1x x x x      Phần 3: Thuật toán giải mã Viterbi Ví dụ: mã tích chập Đầu vào m=[1,1,0,0,1,0,1,0] Từ mã thu được Xuất phát từ trạng thái 0 (giá trị các D-FF được reset về giá trị bit ‘0’). Tại t=7: Loại bỏ nhánh có khoảng cách Hamming lớn 16/12/2013 Slice 22 Trường ĐH Bách Khoa Hà Nội 2 2G( ) 1 1x x x x      Phần 3: Thuật toán giải mã Viterbi Ví dụ: mã tích chập Đầu vào m=[1,1,0,0,1,0,1,0] Từ mã thu được Xuất phát từ trạng thái 0 (giá trị các D-FF được reset về giá trị bit ‘0’). Tại t=8: Mở rộng sơ đồ lưới, tính khoảng cách Hamming 16/12/2013 Slice 23 Trường ĐH Bách Khoa Hà Nội 2 2G( ) 1 1x x x x      Phần 3: Thuật toán giải mã Viterbi Ví dụ: mã tích chập Đầu vào m=[1,1,0,0,1,0,1,0] Từ mã thu được Xuất phát từ trạng thái 0 (giá trị các D-FF được reset về giá trị bit ‘0’). Tại t=8: Loại bỏ nhánh có khoảng cách Hamming lớn 16/12/2013 Slice 24 Trường ĐH Bách Khoa Hà Nội 2 2G( ) 1 1x x x x      Phần 3: Thuật toán giải mã Viterbi Ví dụ: mã tích chập Đầu vào m=[1,1,0,0,1,0,1,0] Từ mã thu được  Lựa chọn tuyến đường ngắn nhất – Survival Path  Đầu vào của tuyến đường ngắn nhất chính là thông tin cần giải mã-sửa lỗi. 16/12/2013 Slice 25 Trường ĐH Bách Khoa Hà Nội 2 2G( ) 1 1x x x x      Phần 3: Thuật toán giải mã Viterbi  So sánh khả năng sửa lỗi của mã tích chập với các độ dài ràng buộc khác nhau, và phương pháp giải mã 1-bit (Khoảng cách Hamming) và 3-bit (khoảng cách Euclid). 16/12/2013 Slice 26 Trường ĐH Bách Khoa Hà Nội