Học liệu

Thực hiện MÃ HÓA NGUỒN - MÃ HUFFMAN trên Matlab

  • 16/10/2018
  • Học liệu

Yêu cầu:

Thực hiện mã hóa thông điệp sau đây ‘information theory is interesting’ bằng hai phương pháp:

-  Mã ASCII

-  Mã Huffman

So sánh, đánh giá hai phương pháp mã hóa trên

Trình tự các bước thực hiện:

Phần 1: Mã hóa bằng Mã Ascii

Bước 1: Click vào biểu tượng   trên Desktop để mở chương trình Matlab

Bước 2: Tạo ra một file mới trong của sổ Editor bằng cách vào File à New à Blank M-file

Bước 3: Trong cửa sổ Editor, nhấn vào File / Save as và  đặt tên file là Bai3Ascii1.m à Nhấn vào nút Save để lưu file

Bước 4: Để xoá màn hình và xóa các biến đã lưu trước đó, gõ vào cửa sổ Editor hai dòng lệnh sau, xem hình dưới:

          clc;

          clear all;

Bước 5: Để tra Mã Ascii cho chuỗi ‘information theory is interesting’, sinh viên gõ vào cửa sổ Editor các dòng lệnh sau:

i = dec2bin('i',7)

n = dec2bin('n',7)

f = dec2bin('f',7)

o = dec2bin('o',7)

r = dec2bin('r',7)

m = dec2bin('m',7)

a = dec2bin('a',7)

t = dec2bin('t',7)

i = dec2bin('i',7)

o = dec2bin('o',7)

n = dec2bin('n',7)

space = dec2bin(' ',7)

t = dec2bin('t',7)

h = dec2bin('h',7)

e = dec2bin('e',7)

o = dec2bin('o',7)

r = dec2bin('r',7)

y = dec2bin('r',7)

space = dec2bin(' ',7)

i = dec2bin('i',7)

s = dec2bin('s',7)

space = dec2bin(' ',7)

i = dec2bin('i',7)

n = dec2bin('n',7)

t = dec2bin('t',7)

e = dec2bin('e',7)

r = dec2bin('r',7)

e = dec2bin('e',7)

s = dec2bin('s',7)

t = dec2bin('t',7)

i = dec2bin('i',7)

n = dec2bin('i',7)

g = dec2bin('g',7)

Bước 6: Nhấn vào nút Run như hình dưới đây để chạy chương trình

Bước 7: Mở kết quả trong của sổ Command (xem hình), sau đó ghi kết quả chương trình vào bảng dưới đây:

 

Ký tự

Mã ASCII nhị phân

Ký tự

Mã ASCII nhị phân

i

 

y

 

n

 

space

 

f

 

i

 

o

 

s

 

r

 

space

 

m

 

i

 

a

 

n

 

t

 

t

 

i

 

e

 

o

 

r

 

n

 

e

 

space

 

s

 

t

 

t

 

h

 

i

 

e

 

n

 

o

 

g

 

r

 

 

 

 

Phần 2: Mã hóa bằng mã Huffman

Bước 1: Thực hiện lại các bước từ bước 1 đến bước 4 của phần 1 để tạo ra một file mới Bai3Huffman1.m

Bước 2: Tạo ra chuỗi tin chứa đoạn text information theory is interesting’. Đoạn tin này lưu trong một biến gọi là msg. Chuỗi tin này gồm 33 ký tự, bao gồm cả ký tự trống. Sinh viên gõ vào cửa sổ Editor vừa tạo dòng lệnh sau:

msg = 'information theory is interesting';

Bước 3: Ước lượng nguồn tin: Trước khi thực hiện mã hóa, chúng ta cần có thông tin về các ký tự nguồn tin và tính thống kê (xác suất) của nguồn được lưu trong hai biến symbp. Việc này được thực hiện bằng hai lệnh sau:

symb = {'i''n''f''o''r''m''a''t'' ''h''e''y''s''g'};

p = [5/33 4/33 1/33 3/33 3/33 1/33 1/33 4/33 1/33 3/33 1/33 2/33 1/33 3/33];

Bước 4: Xây dựng bộ mã Huffman sử dụng hàm Huffmancode, hàm này có hai thông số đầu vào là symp, hàm này có hai thông số đầu ra là dict là bộ mã Huffman, avglen là chiều dài trung bình của từ mã.

dict = huffmandict(symb, p);

Bước 5: Cho hiển thị bộ mã Huffman sử dụng vòng lặp tương tự như phần Cơ sở lý thuyết

temp = dict;

for i = 1:length(temp)

temp{i,2} = num2str(temp{i,2});

end

temp

Bước 6: Thực hiện giải mã hóa Huffman dùng hàm huffmandeco, hàm này có hai thông số đầu vào là dict msg, kết quả chuỗi bit đã mã hóa lưu vào biến binstream

binstream = huffmanenco(msg, dict);

Bước 7: Thực hiện giải mã Huffman dùng hàm huffmandeco

msgdeco = huffmandeco(binstream, dict)

Bước 8: Nhấn vào nút Run như hình dưới đây để chạy chương trình

Bước 9: Mở kết quả trong của sổ Command (xem hình), sau đó ghi kết quả chương trình vào bảng dưới đây:

 

Ký tự

Mã Huffman

Ký tự

Mã Huffman

i

 

y

 

n

 

space

 

f

 

i

 

o

 

s

 

r

 

space

 

m

 

i

 

a

 

n

 

t

 

t

 

i

 

e

 

o

 

r

 

n

 

e

 

space

 

s

 

t

 

t

 

h

 

i

 

e

 

n

 

o

 

g

 

r

 

 

 

 

Bước 10:  Từ các bước thí nghiệm ở phần 1 về mã Ascii, sinh viên rút ra kết quả và điền vào chổ trống sau:

  • Với bản tin trên, trong trường hợp sử dụng bảng mã Ascii thì cần tổng cộng …............ bits (tính tổng số bit trong bảng ở bước 7 – phần 1)
  • Chiều dài trung bình của từ mã này là bao nhiêu (Tổng số bit/ Tổng số ký tự):..................bits/ký tự
  • Có đánh giá gì về chiều dài của từng từ mã trong bộ mã này ? (Giống nhau hay khác nhau) ...............................................................................................

Bước 12: Từ các bước thí nghiệm ở phần 2 về mã Huffman, sinh viên rút ra kết quả và điền vào chổ trống sau:

  • Với bản tin trên, trong trường hợp sử dụng bảng mã Huffman thì cần tổng cộng …............ bits (tính tổng số bit trong bảng ở bước 9 – phần 2)
  • Chiều dài trung bình của từ mã này là bao nhiêu (Tổng số bit/ Tổng số ký tự):..................bits/ký tự
  • Có đánh giá gì về độ dài của từng từ mã trong bộ mã này ? (Giống nhau hay khác nhau)................................................................................................
  • Đánh giá về mối quan hệ giữa xác suất của ký tự với độ dài từ mã của ký tự ..........................................................................................................................

Bước 13: So sánh kết quả ở bước 11 và bước 12, sinh viên rút ra nhận xét và điền vào chổ trống sau:

  • So sánh tổng số bit sử dụng mã Huffman so với Mã Ascii để mã hóa cho cùng chuỗi tin ở trên (Lớn hơn, nhỏ hơn hay bằng): .........................................................................................................................
  • Tính toán hiệu suất nén của mã Huffman so với mã Ascii theo công thức sau:

 (Tổng số bit với Ascii – Tổng số bit với mã Huffman) * 100%

                              Tổng số bit với Ascii

.........................................................................................................................................................................................................................................................................................................................................................................................

Các tin khác