MỤC LỤC
CHƯƠNG 1: NHỮNG KHÁI NIỆM CƠ BẢN 1
1.1 Giới thiệu về lý thuyết thông tin 1
1.2 Hệ thống truyền tin 1
1.2.1 Các quan điểm để phân loại các hệ thống truyền tin 1
1.2.2 Sơ đồ truyền tin và một số khái niệm trong hệ thống truyền tin 2
1.3 Nguồn tin nguyên thuỷ 2
1.3.1 Khái niệm chung 2
1.3.2 Bản chất của thông tin theo quan điểm truyền tin 3
1.4 Hệ thống kênh tin 6
1.4.1 Khái niệm 6
1.4.2 Phân loại môi trường truyền tin 6
1.4.3 Mô tả sự truyền tin qua kênh: 7
1.5 Hệ thống nhận tin 8
1.6 Một số vấn đề cơ bản của hệ thống truyền tin 8
1.6.1 Hiệu suất [ tốc độ truyền tin] 8
1.6.2 Độ chính xác: [hay khả năng chống nhiễu của hệ thống] 8
1.7 Rời rạc hóa một nguồn tin liên tục 8
1.7.1 Khâu lấy mẫu 8
1.7.2 Khâu lượng tử hoá 10
1.8 Điều chế và giải điều chế 11
1.8.1 Điều chế 11
1.8.2 Giải điều chế 12
CHƯƠNG 2: TÍN HIỆU 13
2.1 Một số khái niệm cơ bản 13
2.1.1 Tín hiệu duy trì: 13
2.1.2 Tín hiệu xung [đột ngột] 13
2.1.3 Tín hiệu điều hoà 13
2.2 Phân tích phổ cho tín hiệu 13
2.2.1 Chuỗi Fourier và phổ rời rạc 14
2.2.2 Tích phân Fourier và phổ liên tục 19
2.2.3 Phổ các tín hiệu điều chế 19
2.2.4 Phân tích tín hiệu ngẫu nhiên 22
2.3 Nhiễu trắng 24
CHƯƠNG 3: LƯỢNG TIN, ENTROPI NGUỒN RỜI RẠC 26
3.1 Độ đo thông tin 26
3.1.1 Khái niệm độ đo: 26
3.1.2 Độ đo thông tin. 26
3.2 Lượng tin của nguồn rời rạc 26
3.2.1 Mối liên hệ của lượng tin và lý thuyết xác suất 26
3.2.2 Lượng tin riêng, lượng tin tương hỗ, lượng tin có điều kiện 26
3.2.3 Tính chất của lượng tin 26
3.2.4 Lượng tin trung bình 26
3.3 Entropi của nguồn rời rạc 26
3.3.1 Khái niệm entropi 26
3.3.2 Tính chất của entropi 26
3.3.3 Entropi đồng thời và Entropi có điều kiện 26
3.3.4 Entropi nguồn Markov 26
3.4 Mối quan hệ giữa lượng tin tương hỗ trung bình và Entropi 26
3.5 Tốc độ lập tin nguồn rời rạc và thông lượng kênh rời rạc 26
3.5.1 Tốc độ lập tin 26
3.5.2 Thông lượng kênh 26
CHƯƠNG 4: LÝ THUYẾT MÃ 26
4.1 Khái niệm và điều kiện thiết lập mã 26
4.1.1 Mã hiệu và các thông số cơ bản 26
4.1.2 Điều kiện thiết lập bộ mã 26
4.2 Các phương pháp biểu diễn mã 26
4.2.1 Biểu diễn bằng bảng liệt kê [Bảng đối chiếu mã] 26
4.2.2 Biểu diễn bằng toạ độ mã 26
4.2.3 Đồ hình mã 26
4.2.4 Phương pháp hàm cấu trúc mã 26
4.3 Mã có tính phân tách được, mã có tính prefix 26
4.3.1 Điều kiện để mã phân tách được 26
4.3.2 Mã có tính prefix 26
4.3.3 Bất đẳng thức Kraft 26
4.4 Mã thống kê tối ưu 26
4.4.1 Giới hạn độ dài trung bình của từ mã 26
4.4.2 Tiêu chuẩn mã kinh tế tối ưu 26
4.4.3 Mã thống kê Fano –Shanon 26
4.4.4 Thuật toán mã hoá Lempel-Ziv 26
4.5 Mã chống nhiễu 26
4.5.1 Khái niệm về mã phát hiện sai và sửa sai 26
4.5.2 Cơ chế phát hiện sai 26
4.5.3 Xây dựng bộ mã sửa sai bằng bảng chọn 26
4.5.4 Xây dựng bộ mã sửa sai bằng trọng số Hamming và khoảng cách Hamming 26
4.5.5 Một số biện pháp xây dựng bộ mã phát hiện sai và sửa sai 26
4.6 Mã tuyến tính 26
4.6.1 Phương pháp xây dựng mã tuyến tính 26
4.6.2 Nguyên lý giải mã 26
4.6.3 Một số giới hạn của mã tuyến tính 26
4.7 Mã vòng 26
4.7.1 Khái niệm: 26
4.7.2 Nguyên lý lập mã 26
4.7.3 Nguyên lý giải mã 26
CHƯƠNG 5: GIỚI THIỆU VỀ HỆ MẬT MÃ 26
5.1 Khái niệm hệ mật mã 26
5.2 Phân loại các hệ thống mật mã 26
5.3 Hệ mã cổ điển [Symmetric-key encryption] 26
5.3.1 Khái niệm 26
5.3.2 Một số hệ mã cổ điển 26
5.3.3 Hệ mã DES 26
5.4 Một số hệ mã hoá hiện đại 26
5.4.1 Khái niệm chung 26
5.4.2 Một số hệ mã công khai thông dụng 26
Bạn đang xem nội dung tài liệu Giáo trình môn Lý thuyết thông tin, để tải tài liệu về máy bạn click vào nút DOWNLOAD ở trên
ưu là dựa trên cơ sở độ dài từ mã , tỷ lệ nghịch với xác suất xuất hiện . Nghĩa là các từ mã dài sẽ dùng để mã hóa cho các tin có xác suất xuất hiện nhỏ và ngược lại. Mã thống kê Fano –Shanon Fano và Shanon đã độc lập nghiên cứu và đề xuất phương pháp xây dựng bộ mã thống kê tối ưu, bản chất của hai phương pháp là tương đương nhau. Để thuận tiện trong việc trình bày, các bộ mã xây dựng được từ các thuật toán này có cơ số mã m=2 Phương pháp mã theo Fano Giả sử có nguồn tin với các xác suất tương ứng ... ... Nhà toán học Fano đề xuất thuật toán mã hoá như sau: Bước 1: Sắp xếp các tin ui theo thứ tự giảm dần của xác suất. Bước 2: Chia các tin làm hai nhóm có xác suất xấp xỉ bằng nhau. Nhóm đầu lấy trị 0, nhóm sau lấy trị 1. Bước 3: Lặp lại bước 2 đối với các nhóm con cho tới khi tất cả các nhóm chỉ còn lại một tin thì kết thúc thuật toán. Để rõ hơn về thuật toán, ta xét ví dụ sau: Cho nguồn tin gồm 7 tin: Lần 1 Lần 2 Lần 3 Lần 4 Lần 5 Từ mã 0,34 0 0 00 0,23 0 1 01 0,19 1 0 10 0,10 1 1 0 110 0,07 1 1 1 0 1110 0,06 1 1 1 1 0 11110 0,01 1 1 1 1 1 11111 Độ dài trung bình của từ mã: = 0,01.5 + 0,06 .5 + 0,07.4 + 0,10. 3 + 0,19. 2 + 0,23. 2 + 0,34 .2 = 2,41 Trị số kinh tế = 2,37 /2,41 = 0,98 Nhận xét: 1. Việc sắp xếp nguồn theo xác suất giảm dần nhằm mục đích đẩy các tin có xác suất cao lên đầu bảng cùng với việc chia đôi nguồn dẫn tới các lớp trên sẽ kết thúc rất nhanh, vì vậy các tin có xác suất cao sẽ có độ dài từ mã ngắn dẫn tới độ dài trung bình của bộ mã là nhỏ. 2. Độ phức tạp của thuật toán phụ thuộc vào việc sử dụng thuật toán sắp xếp. Nếu sử dụng thuật toán sắp xếp đệ quy thì độ phức tạp sẽ là . 3. Xuất phát từ thuật toán Fano, ta có thể mở rộng cho việc tạo bộ mã với cơ số bất kỳ bằng cách trong bước 2 ta chia thành m lớp và lấy các trị từ 0 đến 4. Trong trường hợp khi có nhiều tin với xác suất bằng nhau cũng như có nhiều phương án phân lớp thì bộ mã thu được có thể không duy nhất. Thuật toán trên được mô phỏng bởi chương trình sau: Program Fano; uses wincrt; var st:string; A:array[1..255] of char; Ma:array[1..255] of string[20]; P:array[1..255] of real;; n,i,j,k:integer; Procedure Input; Begin write['cho xau can ma hoa:'];readln[St]; end; Procedure Output; var k:integer;xauma:string; Begin xauma:=''; for i:=1 to length[st] do for k:=1 to n do if st[i]=a[k] then xauma:=xauma+ma[k]+' '; writeln['Ket qua ma hoa']; writeln[xauma]; end; Procedure Create; var s:set of char; Begin n:=0;s:=[]; for i:=1 to length[st] do if not [St[i] in S] then Begin n:=n+1; A[n]:= St[i]; S:=S+[St[i]]; end; for i:=1 to n do P[i]:=0; for i:=1 to n do begin for k:=1 to length[St] do if A[i]=St[k] then P[i]:= p[i]+1; P[i]:=P[i]/length[st]; end; for i:=1 to n do Ma[i]:= ''; end; Procedure Sorting; var i,j,tgp:integer; TgA: char; Begin For i:=1 to n-1 do For j:=i+1 to n do If P[i]