Giáo trình: Lý thuyết thông tin
• Liên quan đến Độ đo lượng tin, giáo trình sẽtrình bày các khái niệm cơbản vềthông tin, entropy, một sốcông thức, tính chất, các định lý quan trọng của entropy và cách tính lượng tin. • Về Sinh mã tách được,giáo trìnhsẽgiới thiệu đến người học các vấn đềvềyêu cầu của bài toán sinh mã, giải mãduy nhất, cũng nhưmãtức thời và giải thuật kiểmtra mã tách được. Các định lý quan trọng được đềcập trong nội dung này là: Định lý Kraft (1949), Định lý Shannon (1948) và Định lý sinh mãHuffman. • Về kênh truyền tin rời rạc không nhớ, giáo trình sẽgiới thiệu môhình kênh truyền theo 2 khía cạnh vật lý và toánhọc. Các khái niệm vềdung lượng kênh truyền, phân lớp kênh truyền, định lý về dung lượng kênh truyền, cũng nhưcác khái niệmtrong kỹthuật truyền tin và phương pháp xây dựng lược đồgiải mãtối ưu cũng được trình bày trong môn học này. • Vấn đề Sửa lỗi(hay xửlý mã sai) trên kênh truyền là một vấn đề rất quan trọng và được quan tâmnhiều trong môn học này. Các nội dung được giới thiệu đến các bạn sẽlà Nguyên lý Khoảng cách Hamming, các định lý về Cận Hamming, phương pháp kiểm tra chẵn lẻ, các lược đồ sửa lỗi, Bảng mã Hamming và Bảng mãxoay vòng.
Bạn đang xem trước 20 trang tài liệu Giáo trình: Lý thuyết thông tin, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
Giáo trình: Lý thuyết thông tin
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...........................................................
