Tổng quan về lý thuyết thông tin - Tailieu123.org - Chia sẻ và tải tài liệu miễn phí

Luận văn - báo cáo

Thạc sĩ cao học

Kinh tế quản lý

Khoa học tự nhiên

Kinh tế - Thương mại

Lý luận chính trị

Kỹ thuật

Báo cáo, luận văn khác

Kỹ năng mềm

Mẫu slide

Mẫu slide cho thuyết trình

Mẫu slide cho giáo án điện tử

Mẫu slide khác

Mẫu slide - Template

Kinh doanh - tiếp thị

Marketing, bán hàng

PR truyền thông

Kế hoạch kinh doanh

Tài liệu kinh doanh, tiếp thị khác

Thương mại điện tử

Kinh tế - Quản lý

Bài giảng, giáo trình

Tài liệu kinh tế khác

Tài chính - Ngân hàng

Tài chính doanh nghiệp

Kế toán, kiểm toán

Ngân hàng - tín dụng

Tài liệu tài chính - ngân hàng khác

Biểu mẫu - Văn bản

Mẫu hợp đồng

Mẫu đơn từ

Biểu mẫu, văn bản khác

Thủ tục hành chính

Giáo dục đào tạo

Tài liệu, đề thi môn Toán

Tài liệu, đề thi môn Ngữ Văn

Tài liệu, đề thi THPT các trường

Tài liệu, đề thi Vật Lý

Tài liệu, đề thi Sinh Học

Tài liệu, đề thi Hóa Học

Tài liệu, đề thi Lịch Sử

Tài liệu, đề thi học sinh giỏi

Tài liệu, đề thi khác

Giải bài tập các môn

Giáo án bài giảng

Giáo án, bài giảng lớp 6

Giáo án, bài giảng lớp 7

Giáo án, bài giảng lớp 8

Giáo án, bài giảng lớp 9

Giáo án, bài giảng lớp 10

Giáo án, bài giảng lớp 11

Giáo án, bài giảng lớp 12

Giáo án, bài giảng tiểu học

Giáo án, bài giảng khác

Công nghệ thông tin

Văn bản pháp luật

Thuế - Lệ phí - Kinh phí

Văn bản pháp luật khác

Học tiếng Anh

Tài liệu học tiếng Anh khác

Y học- sức khỏe

Tài liệu y học - sức khỏe khác

Các bài văn khấn nôm

Lĩnh vực khác

Kinh doanh - tiếp thị

Kinh tế - Quản lý

Tài chính - Ngân hàng

Tổng quan về lý thuyết thông tin

748

261

Định dạng

Báo cáo tài liệu vi phạm

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

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

GIỚI THIỆU TỔNG QUAN

GIÁO TRÌNH LÝ THUYẾT THÔNG TIN

MỤC ĐÍCH

 Giáo trình này sẽ cung cấp cho người đọc những khối kiến thức cơ bản của lý thuyết thông tin

như: Độ do lượng tin (Measure of Information), Sinh mã tách được (Decypherable Coding),

Kênh truyền tin rời rạc không nhớ (Discrete Memoryless Channel) và Sửa lỗi trên kênh truyền

(Error Correcting Codings).

• 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ình sẽ 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ểm tra 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án họ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ệm trong 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âm nhiề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.

 Hơn nữa, hầu hết các vấn đề nêu trên đều được đưa vào nội dung giảng dạy ở các bậc Đại học

của một số ngành trong đó có ngành Công nghệ thông tin. Do đó, để có một tài liệu phục vụ

công tác giảng dạy của giáo viên cũng như việc học tập và nghiên cứu của sinh viên, chúng tôi

mạnh dạn biên soạn giáo trình này nhằm giúp cho sinh viên có một tài liệu tự học và nghiên

cứu một cách hiệu quả.

YÊU CẦU

 Sau khi học xong môn này, sinh viên phải có được những khả năng sau:

• Hiểu các khái niệm về về thông tin, Entropy, Entropy của một phân phối, Entropy của

nhiều phân phối, Entropy có điều kiện, Độ đo lượng tin. Vận dụng giải quyết các bài toán

về xác định lượng tin.

• Biết khái niệm về mã tách được, mã không tách được, bảng mã tối ưu. Hiểu Định lý Kraft

(1949), Định lý Shannon (1948), Định lý sinh mã Huffman và phương pháp sinh mã

Huffman. Vận dụng để sinh bảng mã tách được tối ưu, nhận biết được bảng mã như thế

nào là bảng mã tối ưu và có thể vận dụng để viết các chương trình sinh mã, giải mã (hay

viết chương trình nén và giải nén). Từ đây, các sinh viên có thể tự nghiên cứu các loại

bảng mã khác để vận dụng cho việc mã hóa và bảo mật thông tin một cách hiệu quả.

Biên soạn: TS. L ê Quy ết Thắng, ThS. Phan Tấn Tài & Ks. Dương Văn Hiếu. 6

lý thuyết thông tin

LÝ THUYẾT TOÁN

Kinh doanh - tiếp thị

Quản trị, internet, marketing

Giáo dục đào tạo

Các tài liệu, đề thi liên quan đến các môn học của học sinh và bài giảng của giáo viên

Công nghệ thông tin

Tài liệu lĩnh vực công nghệ thông tin

Học tiếng Anh

Các tài liệu liên quan đến học tiếng Anh