Giải đề thi (đề số 1)

Câu 1 : Cho nguồn tin [X] = [x0, x1, x2, x3, x4, x5, x6, x7, x8]

Px = [1/8, 1/2, 1/16, 1/4, 1/32, 1/128, 1/256, 1/64,1/256]

a)     Tính entropi của nguồn.

b)     Lập mã nhị phân Huffman, tính độ dài trung bình từ mã và hiệu suất của mã lập được

c)      Tính lượng tin trung bình chứa trong mỗi ký hiệu mã

Bài giải

* Entropi của nguồn :

H(X) =  = 1/8*3 + 1/2 + 1/16*4 + 1/4*2 + 1/32*5 + 1/128*7 + 1/256*8 + 1/64*6 + 1/256*8 = 1.992187

* Lập mã nhị phân Huffman   (tiến hành qua 7 bước như trong vở)

Chọn n0 = 2, chúng ta dựng cây mã như sau :

từ đó bảng mã nhị phân Huffman là :

Tin

Từ mã tương ứng

x0

110

x1

0

x2

1110

x3

10

x4

11110

x5

1111110

x6

11111110

x7

111110

x8

11111111

 Chú ý : Để đọc từ mã thực hiện đọc ngược từ dưới lên, tin nào có xác suất càng lớn thì phải có độ dài từ mã càng nhỏ

Độ dài trung bình của từ mã : = 3*1/8 + 1*1/2 + 4*1/16 + 2*1/4 + 5*1/32 + 7*1/128 + 8*1/256 + 6*1/64 + 8*1/256 = 1.992187

Hiệu suất lập mã = H(X)/ = 1.992187 / 1.992187 = 1 (hơi vô lý ….)

Câu 2 : Giả sử kênh nhị phân được sử dụng để truyền nguồn tin nhị phân đẳng xác suất có ma trận kênh là :

                  y0        y1

P(Y/X) =  

x0, x1 là 2 giá trị 0 và 1 trên đầu vào kênh; y­0, y1 là 2 giá trị 0,1 trên đầu ra của kênh.

a)     Tính P(X,Y); P(Y) ?

b)     Tính H(X,Y); H(Y|X); H(Y); thông lượng kênh ?

c)      Để thông lượng kênh tăng thì các phân bố phải thay đổi như thế nào ?

Bài giải

* Vì nguốn tin là đẳng xác suất nên ta có p(x0)=p(x1)=1/2. Từ xác suất có điều kiện P(Y/X) và P(X) chúng ta tính xác suất đồng thời P(XY) theo công thức p(xy)=p(y/x)*p(x), do đó ta có bảng giá trị sau cho P(XY) và P(Y) :

                     X

Y

0

1

P(Y)

0

3/8

1/8

1/2

1

1/8

3/8

1/2

* Entropi đồng thời :      H(X,Y) = 2* (3/8*log8/3 + 1/8*log8) = 1.811278

Entropi có điều kiện :    H(Y|X) = 2* (3/8*log4/3 + 1/8*log4) = 0.811277

Entropi đầu ra là :          H(Y) = 1/2*log2 + 1/2*log2 = 1

Thông lượng kênh :      C = n0 * log m = n0 * 1 = n0 (bps)

* Để thông lượng kênh tăng ????????????? . Thông thường thông lượng kênh là cố định, chúng ta chỉ thay đổi các thông số để cải thiện tốc độ lập tin của nguồn (vì tốc độ lập tin này luôn < thông lượng).

Câu 3 : Vẽ biểu đồ hình cây mã và mặt phẳng toạ độ mã cho bộ mã ở câu 1

Bài giải

* Đồ hình cây mã

Mặt phẳng toạ độ mã :

( Chú ý : đây chỉ là hình vẽ mô phỏng, trong bài thi cần phải chia tỉ lệ các đoạn thẳng một cách chính xác)

Đề số 2

Câu 1 : Cho nguồn tin [X] = [a, b, c, d, e, f]

Px = [1/2, 1/4, 1/8, 1/16, 1/32, 1/32]

a)     Tính entropi của nguồn

b)     Lập mã Shannon và mã Huffman với m=2

c)      Tính độ dài trung bình của từ mã và hiệu suất của 2 bộ mã lập được

Bài giải

* Entropi của nguồn H(X) = 1.937500

* Lập mã Shannon

Chọn độ dài từ mã ni là số nguyên bé nhất >= -log p(xi).

Thiết lập Q(xi) =

Chuyển Q(xi) từ cơ số 10 sang cơ số 2

Chỉ giữ lại ni ký hiệu mã

xi

Q(xi)(10)

Q(xi)(2)

Từ mã

a

1

0

0.0

0

2

0.5

0.10

10

c

3

0.75

0.110

110

d

4

0.875

0.1110

1110

5

0.9375

0.11110

11110

f

5

0.96875

0.111110

111110

* Lập mã huffman

Làm tương tự câu 1b đề 1. Kết quả cuối cùng như sau :

Tin

Từ mã tương ứng

a

0

10

c

110

d

1110

11110

f

11111

* Độ dài trung bình của từ mã

Theo mã shannon  = 1/2 + 2/4 + 3/8 + 4/16 + 5/32 + 6/32 = 63/32 = 1.96875

Theo mã huffman   = 1/2 + 2/4 + 3/8 + 4/16 + 5/32 + 5/32 = 31/16 = 1.9375

* Hiệu suất của hai bộ mã lập được

Theo mã shannon  H(X) /  = 1.937500 / 1.96875 = 0.98

Theo mã huffman   H(X) /  = 1.937500 / 1.93750 = 1

Câu 2 : Cho mã nhị phân

                       y0   y1

P(Y/X) =

Gọi xác suất truyền đúng là q, xác suất truyền sai là p, xác suất xuất hiện tin vào là p(x0)=p(x1)=1/2. Xác định lượng tin tương hỗ trong trường hợp p=0 và p=1/2 ?

Bài giải

(xem trong vở của thầy có một bài hoàn toàn tương tự)

Câu 3 : Lập cây mã cho bộ mã sau, nhận xét các đặc tính của bộ mã trên cây

Tin

Từ mã

a

10

0010

c

0100

d

1010

0011

f

010

011

h

1101

1111

Bài giải

* Đồ hình cây mã của bộ mã trên như sau :

* Nhận xét các đặc tính của bộ mã trên cây :

Ø      Tính đầy : cây mã biểu diễn bộ mã chưa đầy (vì còn tồn tại nhánh trên cây chưa được sử dụng)

Ø      Tính phân tách : bộ mã này không phân tách được (vì có tồn tại nút vừa là nút trung gian vừa là nút cuối ví dụ : nút a, nút f ….)

Ø      Tính đều : bộ mã này không đều (vì các nút kết thúc không đồng mức)