Đánh giá tính kinh tế của bộ mã Huffman
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] =S/2; For i:=l to K do Ma[i]:=Ma[i]+'0'; For i:=K+1 to r do Ma[i]:=Ma[i]+'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: hoặc 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[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[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[i] 1 then begin ma[i]:=ma[i]+'1';pp[i]:=pp[i]-1; end else ma[i]:=ma[i]+'0'; until length(ma[i])=nn[i]; 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à prefix của từ mã thứ N là từ mã cuối cùng của bộ mã. Từ những nguyên tắc trên ta có thuật toán xây dựng cây mã Huffman như sau: Bước 1: Chọn n0 là số nguyờn lín nhất thoả mãn điều kiện: 2 £ n0 £ m và là một số nguyên. Bước 2: Khởi tạo danh sách cây cấp chứa các trọng số cho các tin . Bước 3: For i :=1 to +1 do Begin (3.1) Tìm cây có trọng số thấp nhất: tương ứng với trọng số là . Giả sử . (3.2) Thay thế cây này bằng cây có trọng số và có cây con là . (3.3) Gán các giá trị riêng cho các nhánh trên cây tương ứng các nhánh nối với các cây con . End; Cây cuối cùng thu được là cây mã gồm các nút lá là các từ mã tương ứng với các tin của nguồn. Mỗi từ mã là dãy các ký hiệu mã được đánh dấu trên đường đi từ gốc tới nút lá. Thuật toán mã hóa trên có thể mô tả một cách khác như sau: Bước 1: Sắp xếp nguồn X theo xác suất giảm dần Bước 2: Chọn n0 là số nguyên lớn nhất thoả mãn điều kiện: 2 £ n0 £ m và là một số nguyên. Bước 3: Lặp, thay thế tin cuối cùng có xác suất nhỏ nhất thành 1 tin phụ có xác suất bằng tổng xác suất trong nhóm sau đó sắp xếp các tin cũ lại cùng tin phụ theo xác suất giảm dần. Quá trình lặp lại cho đến khi tin phụ có xác suất bằng 1 (Số bước lặp là ). Bước 4: Lập mã: Xuất phát từ tin phụ có xác suất bằng 1, đánh các tin trong nhóm các trị từ , từ các tin phụ sau trở đi, mã của các tin trong nhóm chính bằng mã của tin phụ cộng với các trị từ . Quá trình sẽ dừng lại khi tất cả các tin đó được gán mã. Bước 5: Loại bỏ tất cả các tin phụ, ta thu được bộ mã cần tìm. Để rõ hơn về thuật toán ta xét ví dụ sau: Cho nguồn tin gồm 7 tin: với cấu trúc thống kê 0,34 0,23 0,19 0,10 0,07 0,06 0,01 Ta lấy cơ số mã m=2, nên chọn n0=2 Sau khi thực hiện thuật toán ta được kết quả sau: 0 0 0 0 0 0 1 1 1 1 1 0,24 0,58 0,34 0,42 0,23 0,19 0,14 0,10 0,07 0,07 0,06 0,01 Mức 2 Mức 1 Mức 3 Mức 4 Mức 5 T(2) T(1) T(3) T(4) T(5) T(6) 1 1 00 10 11 011 0100 01010 01011 Thuật toán trên được mô phỏng bởi chương trình sau Program huffman; uses wincrt; var st:string; A:array[1..255] of char; Ma:array[1..255] of string[20]; mma:array[1..255] of string[20]; P:array[1..255] of real; aa:array[1..255] of char; 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[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(n1:integer); var i,j,tgp:integer; TgA: char; Begin For i:=1 to n1-1 do For j:=i+1 to n1 do If Pp[i] Các file đính kèm theo tài liệu này:
|