Hướng dẫn giải một số bài tập truyền tin

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] Tính entropi của nguồn. 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 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; y0, y1 là 2 giá trị 0,1 trên đầu ra của kênh. Tính P(X,Y); P(Y) ? Tính H(X,Y); H(Y|X); H(Y); thông lượng kênh ? Để 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] Tính entropi của nguồn Lập mã Shannon và mã Huffman với m=2 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 ni Q(xi)(10) Q(xi)(2) Từ mã a 1 0 0.0 0 b 2 0.5 0.10 10 c 3 0.75 0.110 110 d 4 0.875 0.1110 1110 e 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 b 10 c 110 d 1110 e 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 b 0010 c 0100 d 1010 e 0011 f 010 g 011 h 1101 i 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)