chunghoanggiang
New Member
Download miễn phí Giáo trình Lý thuyết thông tin
MỤC LỤC
GIỚI THIỆU TỔNG QUAN.6
1. MỤC ĐÍCH.6
2. YÊU CẦU.6
3. NỘI DUNG CỐT LÕI.7
4. KẾT THỨC TIÊN QUYẾT.7
5. TÀI LIỆU THAM KHẢO.8
6. PHƯƠNG PHÁP HỌC TẬP.8
CHƯƠNG 1:GIỚI THIỆU.9
1. Mục tiêu.9
2. Đối tượng nghiên cứu.9
3. Mô hình lý thuyết thông tin theo quan điểmShannon.10
4. Lượng tin biết và chưa biết.10
5. Ví dụvềlượng tin biết vàchưa biết.10
6. Định lý cơsởcủa kỹthuật truyền tin.11
7. Mô tảtrạng thái truyền tin có nhiễu.11
8. Minh họa kỹthuật giảmnhiễu.12
9. Chi phí phải trảcho kỹthuật giảmnhiễu.13
10. Khái niệm vềdung lượng kênh truyền.13
11. Vấn đềsinh mã.13
12. Vấn đềgiải mã.13
CHƯƠNG 2: ĐỘ ĐO LƯỢNG TIN.15
BÀI 2.1: ENTROPY.15
1. Mục tiêu.15
2. Ví dụvềentropy.15
3. Nhận xét về độ đo lượng tin.15
4. Khái niệmentropy.16
5. Entropy của một sựkiện.16
6. Entropy của một phân phối.16
7. Định lý dạng giải tích của Entropy.16
8. Ví dụminh họa.17
9. Bài toán vềcây tìmkiếm nhịphân-Đặt vấn đề.17
10. Bài toán vềcây tìmkiếm nhịphân - Diễn giải.17
11. Bài tập.18
BÀI 2.2: CÁC TÍNH CHẤT CỦA ENTROPY.19
1. Mục tiêu:.19
2. Các tính chất cơbản của Entropy.19
3. Minh họa tính chất 1 và 2.19
4. Minh họa tính chất 3 và 4.19
5. Định lý cực đại của entropy.20
6. Chứng minh định lý cực đại của Entropy.20
7. Bài tập.21
BÀI 2.3: ENTROPY CỦA NHIỀU BIẾN.22
1. Mục tiêu.22
2. Định nghĩa Entropy của nhiều biến.22
3. Ví dụEntropy của nhiều biến.22
4. Định nghĩa Entropy có điều kiện.22
5. Ví dụEntropy có điều kiện.23
6. Quan hệgiữa H(X,Y) với H(X) và H(Y) khi X, Y độc lập.23
7. Quan hệgiữa H(X,Y) với H(X) và H(Y) khi X, Y tương quan.24
8. Bài tập.25
BÀI 2.4: MINH HỌA CÁC ENTROPY.26
1. Mục tiêu.26
2. Yêu cầu củabài toán.26
3. Xác định các phân phối ngẫu nhiên của bài toán.26
4. Minh họa Entropy H(X), H(Y) và H(X,Y).27
5. Minh họa Entropy H(X/Y) và H(Y/X).27
6. Minh họa quan hệgiữa các Entropy.27
BAI 2.5: ĐO LƯỢNG TIN (MESURE OF INFORMATION).28
1. Mục tiêu.28
2. Đặt vấn đềbài toán.28
3. Xác định các phân phối của bài toán.28
4. Nhận xét dựa theo entropy.28
5. Định nghĩa lượng tin.29
6. Bài tập.29
CHƯƠNG 3:SINH MÃ TÁCH ĐƯỢC (Decypherable Coding).31
BÀI 3.1: KHÁI NIỆM VỀMÃ TÁCH ĐƯỢC.31
1. Mục tiêu.31
2. Đặt vấn đềbài toán sinh mã.31
3. Khái niệm vềbảng mãkhông tách được.32
4. Bảng mãtách được.32
5. Khái niệm bảng mãtức thời.33
6. Giải thuật kiểmtra tính tách được của bảng mã.33
7. Bài toán 1- yêu cầu.33
8. Bài toán 1 - Áp dụng giải thuật.34
9. Bài toán 2.34
10. Bài tập.35
BÀI 3.2: QUAN HỆGIỮA MÃ TÁCH ĐƯỢC VÀ ĐỘDÀI MÃ.36
1. Mục tiêu.36
2. Định lý Kraftn(1949).36
3. Định nghĩa cây bậc D cỡk.36
4. Vấn đềsinh mãcho cây bậc D cỡk.37
5. Chứng minh định lý Kraft (Điều kiện cần).37
6. Chứng minh định lý Kraft (Điều kiện đủ).38
7. Ví dụminh họa định lý Kraft.38
8. Bài tập.39
BÀI 3.3: TÍNH TỐI ƯU CỦA ĐỘDÀI MÃ.40
1. Mục tiêu.40
2. Định lý Shannon (1948).40
3. Bảng mãtối ưu tuyệt đối.40
4. Bảng mãtối ưu tương đối.41
5. Điều kiện nhận biết một bảng mãtối ưu.41
6. Định lý Huffman.41
7. Phương pháp sinh mãHuffman.42
8. Minh họa phương pháp sinh mãHuffman.42
9. Nhận xét tính tối ưu của bảng mãHuffman.43
10. Bài tập.43
CHƯƠNG 4:KÊNH TRUYỀN.45
BÀI 4.1: KÊNH TRUYỀN RỜI RẠCKHÔNG NHỚ.45
1. Mục tiêu.45
2. Giới thiệu.45
3. Mô hình vật lý.45
4. Mô hình toán học.46
5. Ví dụxác định phân phối đầu nhận.47
6. Lượng tin trên kênh truyền.47
7. Định nghĩa dung lượng kênh truyền.48
BAI 4.2: CÁC DẠNG KÊNH TRUYỀN.49
1. Mục tiêu.49
2. Hiểu định lý vềdung lượng kênh truyền,Kênh truyền không mất tin.49
3. Kênh truyềnxác định.49
4. Kênh truyền không nhiễu.50
5. Kênh truyền không sửdụng được.50
6. Kênh truyền đối xứng.50
7. Xây dựng công thức tính dung lượng kênh truyền đối xứng.51
8. Định lý vềdung lượng kênh truyền.52
9. Bài tập.52
BÀI 4.3: LƯỢC ĐỒGIẢI MÃ.53
1. Mục tiêu.53
2. Đặt vấn đềbài toán giải mã.53
3. Ví dụbài toán giải mã.53
4. Các khái niệm cơbản của kỹthuật truyền tin.54
5. Ví dụminh họa các khái niệm cơbản.54
6. Các dạng sai sốcơbản.55
7. Phương pháp xây dựng lượt đồgiải mãtối ưu.55
8. Minh họa xây dựng lược đồgiải mãtối ưu.56
9. Minh họa cách tính các sai số.57
10. Bài tập 1.58
11. Bài Tập 2.58
CHƯƠNG 5:SỬA LỖI.59
BÀI 5.1: NGUYÊN LÝ KHOẢNG CÁCH NHỎNHẤT HAMMING.59
1. Mục tiêu:.59
2. Khoảng cách Hamming.59
3. Kênh truyền đối xứng nhịphân và lược đồgiải mã tối ưu.59
4. Ví dụkênh truyền đối xứng nhịphân.60
5. Quan hệgiữa xác suất giải mãvà khoảng cách Hamming.60
6. Nguyên lý Hamming.60
7. Bài tập.61
BÀI 5.2: BỔ ĐỀVỀTỰSỬA LỖI VÀ CẬN HAMMING.62
1. Mục tiêu.62
2. Bổ đềvềtựsửa lỗi.62
3. Chứng minh và minh họa bổ đề.62
4. Cận Hamming.63
5. Phân các dạng lỗi.64
6. Bài tập.64
BÀI 5.3: MÃ KIỂM TRA CHẴN LẺ.64
1. Mục tiêu:.64
2. Bộmãkiểm tra chẵn lẻ.65
3. Phương pháp kiểmtra chẵn lẻ.65
4. Phương pháp sinh mãkiểmtra chẵn lẻ.66
5. Ví dụsinh mãkiểmtra chẵn lẻ.66
6. Định lý quan hệgiữa độdài mãn, sốbit kiểmtra m và sốlỗi tựsửa e.67
7. Ví dụtìmmnhỏnhất từn và e.68
8. Ví dụtìme lớn nhất từm và n.68
9. Bài tập.68
BÀI 5.4: NHÓM CỘNG TÍNH VÀ BỘTỪMÃCHẴN LẺ.69
1. Mục tiêu.69
2. Khái niệmnhómcộng tính.69
3. Tính chất của bộmãchẵn lẻ.69
4. Ví dụminh họa.70
5. Phương pháp sinh mãkiểmtra chẵn lẻnhanh.71
6. Ví dụsinh mãkiểmtra chẵn lẻnhanh.71
7. Bài tập.72
BÀI 5.5: LƯỢC ĐỒSỬA LỖI TỐI ƯU.73
1. Mục tiêu.73
2. Đặt vấn đề.73
3. Định nghĩa Hiệp hợp.73
4. Lược đồsửa lỗi theo các hiệp hợp.74
5. Lược đồsửa lỗi thong qua bộlỗi.74
6. Ví dụminh họa lược đồsửa lỗi 1 bit.74
7. Ví dụminh họa lược đồsửa lỗi 2 bit.75
8. Ví dụminh họa lược đồsửa lỗi 3 bit.76
9. Xác suất truyền đúng.76
10. Bài tập.76
BÀI 5.6: MÃ HAMMING.76
1. Mục tiêu.76
2. Mã Hammin.77
3. Tính chất.77
4. Ví dụminh họa.77
5. Bài tập.78
BÀI 5.7: THANH GHI LÙI TỪNG BƯỚC.79
1. Mục tiêu.79
2. Đặt vấn đề.79
3. Biểu diễn vật lý của thanh ghi.79
4. Biểu diễn toán học của thanh ghi.80
5. Ví dụthanh ghi lui từng bước.80
6. Chu kỳcủa thanh ghi.81
7. Ví dụtìmchu kỳcủa thanh ghi.81
8. Bài tập.82
BÀI 5.8: MÃ XOAY VÒNG.82
1. Mục tiêu.82
2. Ma trận kiểm tra chẵn lẻmãxoay vòng.83
3. Định nghĩa mãxoay vòng.83
4. Phương pháp sinh nhanh bộmãxoay vòng.83
5. Ví dụsinh nhanh bộmãxoay vòng.84
6. Bài tập.85
BÀI 5.9: ĐA THỨC ĐẶC TRƯNG CỦA THANH GHI.86
1. Mục tiêu.86
2. Định nghĩa đa thức đặc trưng của thanh ghi.86
3. Quan hệgiữa chu kỳn, đa thức đăc trưng và đa thức (xn+ 1).86
4. Thủtục sinh thanh ghi lùi từng bước.87
5. Ví dụminh họa.87
6. Bài tập.87
Bài 5.10: PHƯƠNG PHÁP SINH MÃ XOAY VÒNG.88
1. Mục tiêu.88
2. Đặt vấn đề.88
3. Phương pháp sinh bảng mãxoay vòng.88
4. Ví dụminh họa 1.89
5. Ví dụminh họa 2.89
6. Ví dụminh họa 3.90
7. Bảng liệtkêmột số đa thức đặc trưng.90
8. Bài tập.90
BÀI TẬP TỔNG HỢP.91
1. Mục tiêu.91
2. Bài 1.91
3. Bài 2.91
4. Bài 3.92
5. Bài 4.93
TÀI LIỆU THAM KHẢO.95
Để tải bản Đầy Đủ của tài liệu, xin Trả lời bài viết này, Mods sẽ gửi Link download cho bạn sớm nhất qua hòm tin nhắn.
Ai cần download tài liệu gì mà không tìm thấy ở đây, thì đăng yêu cầu down tại đây nhé:
Nhận download tài liệu miễn phí
Tóm tắt nội dung tài liệu:
.CHƯƠNG 3: SINH MÃ TÁCH ĐƯỢC
(Decypherable Coding)
Mục tiêu:
Phân này đề cập đến bài toán mã hóa (coding) các giá trị của một biến X. Khi mã các giá trị
của X người ta phải sử dụng bảng ký tự mã (Coding Character Table) hay bảng chữ cái (Code
Alphabet). Như vậy, một giá trị x của X sẽ được mã thành một từ mã (Code Word) w dưới dạng
một dãy các ký tự mã với độ dài là n ký tự. Trong truyền tin, một dãy các giá trị của X được phát
sinh và được mã thành một dãy liên tục các từ mã hay một dãy các ký tự mã lấy từ bảng ký tự
mã. Vấn đề cần giải quyết là:
1. Khi nhận một dãy ký tự mã liên tục đó thì ta có thể giải mã thành một dãy các giá trị duy
nhất của X hay không ? Nói cách khác, dãy ký tự mã này có tách được thành các từ mã
một cách duy nhất hay không ?
2. Chỉ ra phương pháp xây dựng mã tách được tối ưu.
BÀI 3.1: KHÁI NIỆM VỀ MÃ TÁCH ĐƯỢC
Mục tiêu
Sau khi hoàn tất bài học này bạn có thể:
- Biết yêu cầu của bài toán sinh mã,
- Hiểu khái niệm về bảng mã tách được và bảng mã không tách được,
- Hiểu khái niệm về bảng mã tức thời,
- Hiểu giải thuật kiểm tra tính tách được của một bảng mã,
- Vận dụng giải thuật kiểm tra tính tách được của một bảng mã để kiểm tra xem một bảng
mã có phải là bảng mã tách được hay không.
Đặt vấn đề bài toán sinh mã
Giả sử nguồn tin X xuất hiện và được ghi lại thông qua một thiết bị đặc biệt. Chẳng hạn như ảnh
được ghi lại bằng máy ảnh, âm thanh được ghi lại bằng máy ghi âm, … Qua kênh truyền, những
thông tin này cần được mã hóa cho phù hợp. Để có thể mã hóa người ta cần một bảng chữ cái
gồm các chữ cái quy định trước (chẳng hạn bảng chữ cái la tinh, bảng mã nhị phân, … ). Mỗi giá
trị của X sau đó được mã dưới dạng một dãy hữu hạn các chữ cái và ta gọi dãy hữu hạn các chữ
cái gán cho một giá trị của x là một từ mã.
Ta xét BNN X={x1, x2, …,xn} có phân phối {p1, p2, …, pn} được quan sát liên tục và độc lập. Dãy
các giá trị nhận được gọi là thông báo (Message) có dạng xi1xi2…xin. Tập hợp A={a1, a2, …, an} là
tập hợp ký tự mã (Code Characters) hay là bảng chữ cái (Code Alphabet) dùng để sinh mã. Một
giá trị xi ∈ X được gán bởi một dãy hữu hạn các ký tự mã được gọi là từ mã (Code word). Tập
hợp gồm tất cả các từ mã gán cho tất cả các giá trị của X được gọi là bộ mã hay bảng mã (Code).
Các từ mã phải khác nhau từng đôi một.
Biên soạn: TS. L ê Quy ết Thắng, ThS. Phan Tấn Tài & Ks. Dương Văn Hiếu. 31
Giáo trình: Lý thuyết thông tin.
Bộ mã được gọi là tách được nếu như từ một dãy các ký tự mã nhận được liên tục (được mã hóa
từ bộ mã này), ta luôn luôn giải mã được với kết quả duy nhất là dãy các giá trị gốc của X.
Shannon (1948) lần đầu tiên đã đưa ra định lý cơ sở về sinh mã tách được. Mc Millan (1956) đã
chứng minh định lý về điều kiện cần và đủ của bảng mã tách được. Nhưng vấn đề sinh mã tách
được chỉ được xét một cách chuẩn mực bởi Feinstein (1958), Abramson (1963) và Fano (1961).
Sardinas(1960) và Patterson (1963) đã đưa ra định lý về giải thuật kiểm tra tính tách được của một
bảng mã. Abramson (1963) đã đưa ra khái niệm bảng mã tức thời.
Trong phạm vi bài giảng này, bài toán sinh mã tối ưu được đặt ra ở đây là tìm ra một phương pháp
sinh mã sao cho độ dài trung bình của các từ mã trong bộ mã là nhỏ nhất. Nghĩa là, nếu giá trị xi
được gán bởi từ mã có độ dài ni thì bài toán sinh mã phải thỏa:
Minnp
n
i
ii →∑
=1
Huffman (1950) đã đưa ra qui trình xây dựng một bảng mã tối ưu thỏa yêu cầu này.
Khái niệm về bảng mã không tách được
Bảng mã không tách được là bảng mã mà khi mã hóa thông báo Msg ta sẽ nhận được một dãy các
từ mã ws, và khi giải mã dãy các từ mã ws thì ta có thể nhận được nhiều thông báo Msg khác
nhau.
Ví dụ: Xét biến ngẫu nhiên X={x1, x2, x3, x4} có bảng mã W={w1=0, w2=1, w3=01, w4=10}.
Giả sử thông báo nguồn có nội dung: x1x2x3x4x3x2x1. Khi đó dãy mã tương ứng viết từ W có
dạng: 0101100110.
Nếu giải mã tuần tự từ trái qua phải ta nhận kết quả: x1x2x1x2x2x1x1x2x2x1. Nhưng nếu bằng
phương pháp khác ta có thể nhận được kết quả: x3x3x4x3x4 và nhiều thông báo khác nữa.
Nhận xét: Bảng mã giải mã không tách được là bảng mã mà trong đó tồn tại ít nhất một từ mã
này là mã khóa của một hay nhiều từ mã khác trong bộ mã (ví dụ từ mã w1=0 hay w2=1 là mã
khóa của w3).
Bảng mã tách được
Bảng mã tách được là bảng mã mà khi mã hóa thông báo Msg ta sẽ nhận được dãy các từ mã ws,
và khi giải mã dãy các từ mã ws thì ta chỉ nhận được một thông báo duy nhất là Msg ban đầu.
Ví dụ: Xét biến ngẫu nhiên X={x1, x2} có bảng mã tương ứng W={w1=0, w2=01}.
Phương pháp giải mã được sử dụng như sau: chỉ giải mã khi nào đã nhận được đoạn mã với độ
dài bằng độ dài của từ mã dài nhất.
Giả sử dãy mã nhận được (cần giải mã) là: 0010000101001.
Sử dụng phương pháp giải mã trên ta nhận được duy nhất dãy thông báo gốc:
x1x2x1x1x1x2x2x1x2.
Có thể chi tiết hóa các bước giải mã dãy từ mã trên như sau:
Nhận được đoạn 00 -> Giải ra x1 , còn lại 0.
Nhận tiếp 1 ->01 -> Giải ra x2.
Nhận tiếp 00 -> Giải ra x1, còn lại 0.
Biên soạn: TS. L ê Quy ết Thắng, ThS. Phan Tấn Tài & Ks. Dương Văn Hiếu. 32
Giáo trình: Lý thuyết thông tin.
Nhận tiếp 0 -> 00 -> Giải ra x1, còn lại 0.
Nhận tiếp 0 -> 00 -> Giải ra x1, còn lại 0.
Nhận tiếp 1 -> 01 -> Giải ra x2.
Nhận tiếp 01 -> Giải ra x2.
Nhận tiếp 00 -> Giải ra x1, còn lại 0.
Nhận tiếp 1 -> 01 -> Giải ra x2.
Kết quả dãy thông báo là: x1x2x1x1x1x2x2x1x2.
Kết luận: Bảng mã tách được là bảng mã mà trong đó không tồn lại từ mã này là mã khóa từ mã
khác, tuy nhiên vẫn có thể tồn tại từ mã này là tiền tố (phần đầu) của từ mã kia.
Khái niệm bảng mã tức thời
Bảng mã tức thời là bảng mã mà khi mã hóa thông báo Msg ta sẽ nhận được dãy các từ mã ws, và
khi giải mã dãy các từ mã ws thì ta chỉ nhận được một thông báo duy nhất là Msg ban đầu.
Abramson đã chứng minh được kết quả sau: Bảng mã tức thời là bảng mã không tồn tại từ
mã này là tiền tố của từ mã khác.
Ví dụ 1: Bảng mã W={w1=10; w2=101; w3=100} không phải bảng mã tức thời vì w1 là tiền tố của
w2 và w3.
Ví dụ 2: Bảng mã W={w1=0, w2=100, w3=101, w4=11} là bảng mã tức thời vì không tồn tại từ
mã này là tiền tố của từ mã khác.
Giải thuật kiểm tra tính tách được của bảng mã
Thủ tục sau đây do Sardinas (1960), Patterson (1963) và Abramson (1963) đưa ra nhằm kiểm tra
xem một bảng mã nào đó có phải là bảng mã tách được (bảng mã cho phép giải mã duy nhất) hay
không.
Input: Bảng mã W
Output: Kết luận bảng mã tách được hay không tách được.
Giải thuật:
Bước khởi tạo: Gán tập hợp S0=W.
Bước 1: xác định tập hợp S1 từ S0:
- Khởi tạo S1={}
- Với ∀ wi, wj ∈ S0, ta xét: nếu wi=wjA (wj là tiền tố của wi) hay wj=wi A (wi là tiền tố
của wj) thì thêm A (phần hậu tố) vào S1.
Bước k: xác định tập hợp Sk (k≥2) từ tập hợp S0 và Sk-1:
- Khởi tạo: Sk={}
- Với ∀ wi∈ ...