Giáo trình Lý thuyết thông tin

Giáo trình gồm 5 chương được trình bày trong 45 tiết giảng cho sinh viên chuyên ngành Công nghệ thông tin, trong đó có khoảng 30 tiết lý thuyết và 15 tiết bài tập mà giáo viên sẽ hướng dẫn cho sinh viên trên lớp. Chương 1: Giới thiệu. Chương này trình bày các nội dung có tính tổng quan về môn học bao gồm: các đối tượng nghiên cứu, mô hình lý thuyết thông tin theo quan điểm của nhà toán học Shannon, khái niệm về lượng tin biết và chưa biết, định lý cơ bản của kỹ thuật truyền tin. Chương 2: Độ đo lượng tin. Chương này trình bày các vấn đề cơ bản về entropy, các tính chất của entropy, entropy của nhiều biến, entropy có điều kiện, các định lý về quan hệ giữa các entropy và lượng tin của một sự kiện. Chương 3: Sinh mã tách được. Nội dung chính của chương này bao gồm các khái niệm về mã tách được, quan hệ giữa mã tách được và độ dài mã, tính tối ưu của độ dài mã. Chương 4: Kênh truyền. Các nội dung được trình bày trong chương này bao gồm khái niệm về kênh truyền tin rời rạc không nhớ, các mô hình truyền tin ở khía cạnh vật lý và toán học, dung lượng trên kênh truyền, phân lớp các kênh truyền. Phương pháp xây dựng lược đồ giải mã tối ưu và cách tính xác suất truyền sai cũng được giới thiệu trong chương này. Chương 5: Sửa lỗi. Chương này trình bày các nội dung cốt lõi sau: khái niệm về khoảng cách Hamming, nguyên lý khoảng cách nhỏ nhất Hamming, bổ đề về tự sửa lỗi và định lý Cận Hamming. Chương này cũng giới thiệu về bộ mã kiểm tra chẵn lẻ, phương pháp kiểm tra chẵn lẻ, lược đồ sửa lỗi tối ưu, mã Hamming và mã xoay vòng.

pdf95 trang | Chia sẻ: diunt88 | Ngày: 24/08/2012 | Lượt xem: 2004 | Lượt tải: 23download
Bạn đang xem nội dung tài liệu Giáo trình Lý thuyết thông tin, để tải tài liệu về máy bạn click vào nút DOWNLOAD ở trên
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