kieutrang_7294
New Member
Download miễn phí Giáo trình môn Lý thuyết thông tin
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ã
264.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
Để 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:
ư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=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 in S) then
Begin
n:=n+1;
A[n]:= St;
S:=S+[St];
end;
for i:=1 to n do P:=0;
for i:=1 to n do
begin
for k:=1 to length(St) do
if A=St[k] then P:= p+1;
P:=P/length(st);
end;
for i:=1 to n do Ma:= '';
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
TgA:=A; A:=A[j]; A[j]:=TgA;
TgP:=P; P:=P[j]; P[j]:=TgP;
End;
end;
Procedure Mahoa_Fano(l,r:integer);
Var k:integer;
s,Sum:integer;
Begin
if l
S:=0;
For i:=l to r do S:=S+P;
Sum:=0; k:=l-1;
Repeat
k:=k+1;
Sum:=Sum+P[k];
until Sum>=S/2;
For i:=l to K do Ma:=Ma+'0';
For i:=K+1 to r do Ma:=Ma+'1';
Mahoa_fano(l,k); Mahoa_fano(k+1,r);
End;
End;
BEGIN
Input;
create;
Sorting;
Mahoa_fano(1,n);
Output;
Readln;
END.
Phương pháp mã theo Shanon
Xét nguồn U với bảng phân phối xác suất:
...
...
Nhà toán học Shanon đề xuất thuật toán mã hóa như sau:
Bước 1: Sắp xếp các tin theo thứ tự giảm dần của xác suất.
Bước 2: Tính theo công thức:
nếu
nếu
Ở bước này ta đã giả thiết các tin được sắp xếp theo thứ tự giảm dần của xác suất:
Bước 3: Tính độ dài từ mã mã hoá tin theo công thức sau:
hay
Bước 4 : Chuyển đổi tính được ở Bước 2 từ hệ thập phân sang hệ nhị phân.
Bước 5 : Xác định từ mã bằng cách lấy ký hiệu nhị phân ngay sau dấu phẩy.
Để rõ hơn về thuật toán ta xét ví dụ sau :
Cho nguồn tin gồm 7 tin:
0,34
0,23
0,19
0,10
0,07
0,06
0,01
Thực hiện qua 5 bước theo thuật toán ta được kết quả sau:
hệ 2
Từ mã
0,34
2
0,0
0,00
00
0,23
3
0,34
0,010
010
0,19
3
0,57
0,100
100
0,10
4
0,76
0,1100
1100
0,07
4
0,86
0,1101
1101
0,06
5
0,93
0,11101
11101
0,01
7
0,99
0,1111110
1111110
Kiểm tra tính tối ưu:
= -(0,01 log 0,01 + 0,06log0,06 + 0,10log0,10 + 0,19log0,19 + 0,23log0,23 + 0,34log0,34) » 2,37
= = 0,01.7 + 0,06. 5 + 0,07. 4 + 0,10.4 + 0,19. 3 + 0,23. 3 + 0,34. 2 = 2,99
Trị số kinh tế r = H(U) / = 2,37/2,99 = 0,81
Nhận xét:
1. Việc sắp xếp nguồn theo xác suất giảm dần cũng nhằm mục đích 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 Shanon, ta có thể mở rộng cho việc tạo bộ mã với cơ số bất kỳ bằng cách xác định lại độ dài cũng như đổi các xác suất phụ sang dạng phân.
4. Trong trường hợp khi có nhiều tin với xác suất bằng nhau 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 shanon;
USES WINCRT;
var st:string;
A:array[1..255] of char;
Ma:array[1..255] of string[20];
P:array[1..255] of real;
PP: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=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 in S) then
Begin
n:=n+1;
A[n]:= St;
S:=S+[St];
end;
for i:=1 to n do P:=0;
for i:=1 to n do
begin
for k:=1 to length(St) do
if A=St[k] then P:= p+1;
p[k]:=p[k]/length(st);
end;
end;
Procedure Sorting;
var i,j:integer;tgp:real;
TgA: char;
Begin
For i:=1 to n-1 do
For j:=i+1 to n do
If P
TgA:=A; A:=A[j]; A[j]:=TgA;
TgP:=P; P:=P[j]; P[j]:=TgP;
End;
end;
Procedure Mahoa_Shanon;
Var k:integer;
s:real;
nn:array[1..255] of integer;
Begin
for i:=1 to n do ma:='';
for i:=1 to n do
begin
nn:=0;S:=1;
repeat nn:=nn+1;S:=S*0.5;until S
end;
for i:=1 to n do
begin
pp:=0;
for j:=1 to i-1 do pp:=pp+p[j];
end;
for i:=1 to n do
repeat
pp:=2*pp;
if pp>1 then
begin
ma:=ma+'1';pp:=pp-1;
end
else ma:=ma+'0';
until length(ma)=nn;
End;
BEGIN
Input;
create;
Sorting;
Mahoa_shanon;
Output;
Readln;
END.
Có thể chứng minh rằng những bộ mã được xây dựng theo hai phương pháp trên đều là mã prefix và hai phương pháp trên là tương đương nhau.
Mã Huffman
Huffman đã đưa ra nguyên tắc để xây dựng bộ mã thống kê tối ưu như sau: Để một mã prefix có độ dài tối thiểu điều kiện cần và đủ là thoả mãn 3 tính chất đó là:
Tính chất 1: Tính thứ tự của độ dài từ mã: Nếu sắp xếp các tin theo thứ tự giảm dần của xác suất với i < j thì độ dài của các từ mã tương ứng phải thỏa mãn điều kiện ni £ nj .
Tính chất 2: Tính chất những từ mã cuối: Với n0 thoả mãn điều kiện 2 £ n0 £ m (m là cơ số mã) thì n0 từ mã cuối luôn có độ dài n bằng nhau, về trọng số chỉ khác nhau ký hiệu bên phải
nN-n0 = .. = nN-1 = nN .
Tính chất 3: Tính liên hệ từ mã cuối và từ mã trước cuối: Một dãy gồm nN -1 ký hiệu phải là một từ mã hay là...