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ểmShannon.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ảmnhiễu.12 9. Chi phí phải trảcho kỹthuật giảmnhiễ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ệmentropy.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ìmkiếm nhịphân-Đặt vấn đề.17 10. Bài toán vềcây tìmkiế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 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ủabà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ểmtra 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 CHƯƠNG 4:KÊNH TRUYỀN.45 BÀI 4.1: KÊNH TRUYỀN RỜI RẠCKHÔ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ềnxá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 3. Phương pháp kiểmtra chẵn lẻ.65 4. Phương pháp sinh mãkiểmtra chẵn lẻ.66 5. Ví dụsinh mãkiểmtra chẵn lẻ.66 6. Định lý quan hệgiữa độdài mãn, sốbit kiểmtra m và sốlỗi tựsửa e.67 7. Ví dụtìmmnhỏnhất từn và e.68 8. Ví dụtìme 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ệmnhómcộ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ểmtra chẵn lẻnhanh.71 6. Ví dụsinh mãkiểmtra 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ìmchu 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.82 2. Ma trận kiểm tra chẵn lẻmãxoay vòng.83 3. Định nghĩa mãxoay vòng.83 4. Phương pháp sinh nhanh bộmãxoay vòng.83 5. Ví dụsinh nhanh bộmãxoay vòng.84 6. Bài tập.85 BÀI 5.9: ĐA THỨC ĐẶC TRƯNG CỦA THANH GHI.86 1. Mục tiêu.86 2. Định nghĩa đa thức đặc trưng của thanh ghi.86 3. Quan hệgiữa chu kỳn, đa thức đăc trưng và đa thức (xn+ 1).86 4. Thủtục sinh thanh ghi lùi từng bước.87 5. Ví dụminh họa.87 6. Bài tập.87 Bài 5.10: PHƯƠNG PHÁP SINH MÃ XOAY VÒNG.88 1. Mục tiêu.88 2. Đặt vấn đề.88 3. Phương pháp sinh bảng mãxoay vòng.88 4. Ví dụminh họa 1.89 5. Ví dụminh họa 2.89 6. Ví dụminh họa 3.90 7. Bảng liệtkêmột số đa thức đặc trưng.90 8. Bài tập.90 BÀI TẬP TỔNG HỢP.91 1. Mục tiêu.91 2. Bài 1.91 3. Bài 2.91 4. Bài 3.92 5. Bài 4.93 TÀI LIỆU THAM KHẢO.95
Các file đính kèm theo tài liệu này:
- GT_LTTT.pdf