Giáo trình Lý thuyết thông tin - Lê Quyết Thắng

Giáo trình: Lý thuyết thông tin. MỤC LỤC GIỚI THIỆU TỔNG QUAN.............................................................................................................6 1. MỤC ĐÍCH ...........................................................................................................................6 2. YÊU CẦU .............................................................................................................................6 3. NỘI DUNG CỐT LÕI...........................................................................................................7 4. KẾT THỨC TIÊN QUYẾT ..................................................................................................7 5. TÀI LIỆU THAM KHẢO.....................................................................................................8 6. PHƯƠNG PHÁP HỌC TẬP.................................................................................................8 CHƯƠNG 1: GIỚI THIỆU ...............................................................................................................9 1. Mục tiêu.................................................................................................................................9 2. Đối tượng nghiên cứu............................................................................................................9 3. Mô hình lý thuyết thông tin theo quan điểm Shannon ........................................................10 4. Lượng tin biết và chưa biết .................................................................................................10 5. Ví dụ về lượng tin biết và chưa biết ....................................................................................10 6. Định lý cơ sở của kỹ thuật truyền tin ..................................................................................11 7. Mô tả trạng thái truyền tin có nhiễu ....................................................................................11 8. Minh họa kỹ thuật giảm nhiễu.............................................................................................12 9. Chi phí phải trả cho kỹ thuật giảm nhiễu ............................................................................13 10. Khái niệm về dung lượng kênh truyền ............................................................................13 11. Vấn đề sinh mã................................................................................................................13 12. Vấn đề giải mã.................................................................................................................13 CHƯƠNG 2: ĐỘ ĐO LƯỢNG TIN ...............................................................................................15 BÀI 2.1: ENTROPY .......................................................................................................................15 1. Mục tiêu...............................................................................................................................15 2. Ví dụ về entropy..................................................................................................................15 3. Nhận xét về độ đo lượng tin ................................................................................................15 4. Khái niệm entropy...............................................................................................................16 5. Entropy của một sự kiện......................................................................................................16 6. Entropy của một phân phối .................................................................................................16 7. Định lý dạng giải tích của Entropy......................................................................................16 8. Ví dụ minh họa....................................................................................................................17 9. Bài toán về cây tìm kiếm nhị phân-Đặt vấn đề ...................................................................17 10. Bài toán về cây tìm kiếm nhị phân - Diễn giải................................................................17 11. Bài tập .............................................................................................................................18 BÀI 2.2: CÁC TÍNH CHẤT CỦA ENTROPY .............................................................................19 1. Mục tiêu: .............................................................................................................................19 2. Các tính chất cơ bản của Entropy........................................................................................19 3. Minh họa tính chất 1 và 2....................................................................................................19 4. Minh họa tính chất 3 và 4....................................................................................................19 5. Định lý cực đại của entropy ................................................................................................20 6. Chứng minh định lý cực đại của Entropy............................................................................20 7. Bài tập .................................................................................................................................21 BÀI 2.3: ENTROPY CỦA NHIỀU BIẾN .....................................................................................22 1. Mục tiêu...............................................................................................................................22 2. Định nghĩa Entropy của nhiều biến.....................................................................................22 3. Ví dụ Entropy của nhiều biến..............................................................................................22 4. Định nghĩa Entropy có điều kiện.........................................................................................22 Biên soạn: TS. L ê Quy ết Thắng, ThS. Phan Tấn Tài & Ks. Dương Văn Hiếu. 1 Giáo trình: Lý thuyết thông tin. 5. Ví dụ Entropy có điều kiện .................................................................................................23 6. Quan hệ giữa H(X,Y) với H(X) và H(Y) khi X, Y độc lập.................................................23 7. Quan hệ giữa H(X,Y) với H(X) và H(Y) khi X, Y tương quan ..........................................24 8. Bài tập .................................................................................................................................25 BÀI 2.4: MINH HỌA CÁC ENTROPY........................................................................................26 1. Mục tiêu...............................................................................................................................26 2. Yêu cầu của bài toán ...........................................................................................................26 3. Xác định các phân phối ngẫu nhiên của bài toán ................................................................26 4. Minh họa Entropy H(X), H(Y) và H(X,Y)..........................................................................27 5. Minh họa Entropy H(X/Y) và H(Y/X) ................................................................................27 6. Minh họa quan hệ giữa các Entropy....................................................................................27 BAI 2.5: ĐO LƯỢNG TIN (MESURE OF INFORMATION) ......................................................28 1. Mục tiêu...............................................................................................................................28 2. Đặt vấn đề bài toán..............................................................................................................28 3. Xác định các phân phối của bài toán...................................................................................28 4. Nhận xét dựa theo entropy ..................................................................................................28 5. Định nghĩa lượng tin ...........................................................................................................29 6. Bài tập .................................................................................................................................29 CHƯƠNG 3: SINH MÃ TÁCH ĐƯỢC (Decypherable Coding)...................................................31 BÀI 3.1: KHÁI NIỆM VỀ MÃ TÁCH ĐƯỢC..............................................................................31 1. Mục tiêu...............................................................................................................................31 2. Đặt vấn đề bài toán sinh mã ................................................................................................31 3. Khái niệm về bảng mã không tách được .............................................................................32 4. Bảng mã tách được..............................................................................................................32 5. Khái niệm bảng mã tức thời ................................................................................................33 6. Giải thuật kiểm tra tính tách được của bảng mã..................................................................33 7. Bài toán 1- yêu cầu..............................................................................................................33 8. Bài toán 1 - Áp dụng giải thuật ...........................................................................................34 9. Bài toán 2 ............................................................................................................................34 10. Bài tập .............................................................................................................................35 BÀI 3.2: QUAN HỆ GIỮA MÃ TÁCH ĐƯỢC VÀ ĐỘ DÀI MÃ................................................36 1. Mục tiêu...............................................................................................................................36 2. Định lý Kraftn(1949)...........................................................................................................36 3. Định nghĩa cây bậc D cỡ k. .................................................................................................36 4. Vấn đề sinh mã cho cây bậc D cỡ k ....................................................................................37 5. Chứng minh định lý Kraft (Điều kiện cần) .........................................................................37 6. Chứng minh định lý Kraft (Điều kiện đủ)...........................................................................38 7. Ví dụ minh họa định lý Kraft ..............................................................................................38 8. Bài tập .................................................................................................................................39 BÀI 3.3: TÍNH TỐI ƯU CỦA ĐỘ DÀI MÃ..................................................................................40 1. Mục tiêu...............................................................................................................................40 2. Định lý Shannon (1948) ......................................................................................................40 3. Bảng mã tối ưu tuyệt đối .....................................................................................................40 4. Bảng mã tối ưu tương đối....................................................................................................41 5. Điều kiện nhận biết một bảng mã tối ưu .............................................................................41 6. Định lý Huffman .................................................................................................................41 7. Phương pháp sinh mã Huffman...........................................................................................42 8. Minh họa phương pháp sinh mã Huffman ..........................................................................42 9. Nhận xét tính tối ưu của bảng mã Huffman ........................................................................43 10. Bài tập .............................................................................................................................43 Biên soạn: TS. L ê Quy ết Thắng, ThS. Phan Tấn Tài & Ks. Dương Văn Hiếu. 2 Giáo trình: Lý thuyết thông tin. CHƯƠNG 4: KÊNH TRUYỀN ......................................................................................................45 BÀI 4.1: KÊNH TRUYỀN RỜI RẠC KHÔNG NHỚ ...................................................................45 1. Mục tiêu...............................................................................................................................45 2. Giới thiệu.............................................................................................................................45 3. Mô hình vật lý .....................................................................................................................45 4. Mô hình toán học.................................................................................................................46 5. Ví dụ xác định phân phối đầu nhận.....................................................................................47 6. Lượng tin trên kênh truyền..................................................................................................47 7. Định nghĩa dung lượng kênh truyền....................................................................................48 BAI 4.2: CÁC DẠNG KÊNH TRUYỀN........................................................................................49 1. Mục tiêu...............................................................................................................................49 2. Hiểu định lý về dung lượng kênh truyền,Kênh truyền không mất tin.................................49 3. Kênh truyền xác định ..........................................................................................................49 4. Kênh truyền không nhiễu ....................................................................................................50 5. Kênh truyền không sử dụng được. ......................................................................................50 6. Kênh truyền đối xứng..........................................................................................................50 7. Xây dựng công thức tính dung lượng kênh truyền đối xứng ..............................................51 8. Định lý về dung lượng kênh truyền.....................................................................................52 9. Bài tập .................................................................................................................................52 BÀI 4.3: LƯỢC ĐỒ GIẢI MÃ .......................................................................................................53 1. Mục tiêu...............................................................................................................................53 2. Đặt vấn đề bài toán giải mã .................................................................................................53 3. Ví dụ bài toán giải mã .........................................................................................................53 4. Các khái niệm cơ bản của kỹ thuật truyền tin .....................................................................54 5. Ví dụ minh họa các khái niệm cơ bản .................................................................................54 6. Các dạng sai số cơ bản ........................................................................................................55 7. Phương pháp xây dựng lượt đồ giải mã tối ưu....................................................................55 8. Minh họa xây dựng lược đồ giải mã tối ưu .........................................................................56 9. Minh họa cách tính các sai số..............................................................................................57 10. Bài tập 1 ..........................................................................................................................58 11. Bài Tập 2 .........................................................................................................................58 CHƯƠNG 5: SỬA LỖI...................................................................................................................59 BÀI 5.1: NGUYÊN LÝ KHOẢNG CÁCH NHỎ NHẤT HAMMING .........................................59 1. Mục tiêu: .............................................................................................................................59 2. Khoảng cách Hamming.......................................................................................................59 3. Kênh truyền đối xứng nhị phân và lược đồ giải mã tối ưu..................................................59 4. Ví dụ kênh truyền đối xứng nhị phân..................................................................................60 5. Quan hệ giữa xác suất giải mã và khoảng cách Hamming..................................................60 6. Nguyên lý Hamming ...........................................................................................................60 7. Bài tập .................................................................................................................................61 BÀI 5.2: BỔ ĐỀ VỀ TỰ SỬA LỖI VÀ CẬN HAMMING ...........................................................62 1. Mục tiêu...............................................................................................................................62 2. Bổ đề về tự sửa lỗi...............................................................................................................62 3. Chứng minh và minh họa bổ đề ..........................................................................................62 4. Cận Hamming. ....................................................................................................................63 5. Phân các dạng lỗi.................................................................................................................64 6. Bài tập .................................................................................................................................64 BÀI 5.3: MÃ KIỂM TRA CHẴN LẺ .............................................................................................64 1. Mục tiêu: .............................................................................................................................64 2. Bộ mã kiểm tra chẵn lẻ........................................................................................................65 Biên soạn: TS. L ê Quy ết Thắng, ThS. Phan Tấn Tài & Ks. Dương Văn Hiếu. 3 Giáo trình: Lý thuyết thông tin. 3. Phương pháp kiểm tra chẵn lẻ .............................................................................................65 4. Phương pháp sinh mã kiểm tra chẵn lẻ ...............................................................................66 5. Ví dụ sinh mã kiểm tra chẵn lẻ............................................................................................66 6. Định lý quan hệ giữa độ dài mã n, số bit kiểm tra m và số lỗi tự sửa e ..............................67 7. Ví dụ tìm m nhỏ nhất từ n và e...........................................................................................68 8. Ví dụ tìm e lớn nhất từ m và n.............................................................................................68 9. Bài tập .................................................................................................................................68 BÀI 5.4: NHÓM CỘNG TÍNH VÀ BỘ TỪ MÃ CHẴN LẺ .........................................................69 1. Mục tiêu...............................................................................................................................69 2. Khái niệm nhóm cộng tính. .................................................................................................69 3. Tính chất của bộ mã chẵn lẻ................................................................................................69 4. Ví dụ minh họa....................................................................................................................70 5. Phương pháp sinh mã kiểm tra chẵn lẻ nhanh.....................................................................71 6. Ví dụ sinh mã kiểm tra chẵn lẻ nhanh.................................................................................71 7. Bài tập .................................................................................................................................72 BÀI 5.5: LƯỢC ĐỒ SỬA LỖI TỐI ƯU.........................................................................................73 1. Mục tiêu...............................................................................................................................73 2. Đặt vấn đề............................................................................................................................73 3. Định nghĩa Hiệp hợp ...........................................................................................................73 4. Lược đồ sửa lỗi theo các hiệp hợp ......................................................................................74 5. Lược đồ sửa lỗi thong qua bộ lỗi.........................................................................................74 6. Ví dụ minh họa lược đồ sửa lỗi 1 bit...................................................................................74 7. Ví dụ minh họa lược đồ sửa lỗi 2 bit...................................................................................75 8. Ví dụ minh họa lược đồ sửa lỗi 3 bit...................................................................................76 9. Xác suất truyền đúng...........................................................................................................76 10. Bài tập .............................................................................................................................76 BÀI 5.6: MÃ HAMMING ..............................................................................................................76 1. Mục tiêu...............................................................................................................................76 2. Mã Hammin.........................................................................................................................77 3. Tính chất..............................................................................................................................77 4. Ví dụ minh họa....................................................................................................................77 5. Bài tập .................................................................................................................................78 BÀI 5.7: THANH GHI LÙI TỪNG BƯỚC ...................................................................................79 1. Mục tiêu...............................................................................................................................79 2. Đặt vấn đề............................................................................................................................79 3. Biểu diễn vật lý của thanh ghi .............................................................................................79 4. Biểu diễn toán học của thanh ghi ........................................................................................80 5. Ví dụ thanh ghi lui từng bước .............................................................................................80 6. Chu kỳ của thanh ghi...........................................................................................................81 7. Ví dụ tìm chu kỳ của thanh ghi ...........................................................................................81 8. Bài tập .................................................................................................................................82 BÀI 5.8: MÃ XOAY VÒNG ..........................................................................................................82 1. Mục tiêu.............................