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...............................................................................................................................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
Biên soạn: TS. L ê Quy ết Thắng, ThS. Phan Tấn Tài & Ks. Dương Văn Hiếu. 4
Giáo trình: Lý thuyết thông tin.
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ệt kê 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
Biên soạn: TS. L ê Quy ết Thắng, ThS. Phan Tấn Tài & Ks. Dương Văn Hiếu. 5