Bài tập lý thuyết thông tin

Bài 1: Giải sử có 3 thành phố A, B, C. Biết rằng dân thành phố A luôn nói thật,dân thành phố B luôn nói dối, còn dân thành phố C thì cứ một lần nói thật lạimột lần nói dối xen kẽ nhau. Du khách D muốn xác minh đồng thời xem anh tađang ở thành phố nào và người anh ta gặp là dân thành phố nào. D cần phải đặtít nhất bao nhiêu câu hỏi, nếu người nói chuyện với D chỉ có thể trả lời là“Phải” hoặc “Không”....
Nội dung trích xuất từ tài liệu:
Bài tập lý thuyết thông tin CHƯƠNG 3Bài 1: Giải sử có 3 thành phố A, B, C. Biết rằng dân thành ph ố A luôn nói th ật,dân thành phố B luôn nói dối, còn dân thành phố C thì cứ một l ần nói th ật l ạimột lần nói dối xen kẽ nhau. Du khách D muốn xác minh đồng thời xem anh tađang ở thành phố nào và người anh ta gặp là dân thành ph ố nào. D c ần ph ải đ ặtít nhất bao nhiêu câu hỏi, nếu người nói chuyện với D chỉ có th ể trả lời là“Phải” hoặc “Không”.Bài 2: Có 25 đồng tiền (đúc bằng kim loại) cùng một giá trị, trong đó có 24 đồngcó khối lượng như nhau, cũn một đồng là tiền giả, có khối lượng nhẹ hơn cácđồng khác. Hỏi phải cân ít nhất bao nhiêu lần thì có thể tìm ra được đồng ti ềngiả này?Bài 3: Khảo sát về tình hình thi tuyển sinh vào đại h ọc, cao đ ẳng cho bi ết t ỷ l ệthí sinh đạt điểm trên điểm sàn là , số thí sinh dưới điểm sàn là . Trong s ố thísinh đạt điểm trên điểm sàn có 30% là học sinh thuộc vùng nông thôn, 70%thuộc khu vực thành phố. Trong số thí sinh đạt điểm dưới đi ểm sàn có 60% h ọcsinh thuộc khu vực thành phố. Tìm lượng tin về năng lực học tập của thí sinhkhi biết khu vực cư trú?Bài 4: Nêu ý nghĩa và chứng minh các công thức sau: 1. 2. 3.Bài 5: Cho cấu trúc thống kê của nguồn X={x1, x2, x3}. xi x1 x2 x3 P(xi) 0.2 0.2 0.5 5 5Cho ma trận nhiễu trên kênh: P(yj|xi) y1 y2 y3 x1 0.2 0.5 0.25 5 x2 0.5 0.2 0.25 5 x3 0.2 0.2 0.5 5 5 - Tại đầu ra kênh nhận được tin yj do nguồn X phát. Hãy cho biết tin nào thuộc nguồn X có khả năng nhiều nhất chuyển thành tin yj . (i=1,2,3).Bài 6: Cho hệ thống truyền tin.Trong đó X={x1, x2, x3} là nguồn tin tại đầu vào kênh thông qua sự truy ền lantrong kênh trở thành nguồn Y={y1, y2, y3}. Cho biết phân bố sau: P(xi,yj) y1 y2 y3 x1 0 1/8 1/8 x2 1/8 1/1 1/16 6 x3 1/4 1/8 1/8 - Hãy cho biết cấu trúc thống kê của nguồn X, Y. Entopi của nguồn X, nguồn Y, Ma trận nhiễu trên kênh, H(X,Y), I(X,Y).Bài 7: Cho cấu trúc thống kê của nguồn X={x1, x2, x3, x4}. xi x1 x2 x3 x4 P(xi) 3/8 2/ 1/8 2/8 8Ma trận nhiễu trên kênh. P(yj|xi) y1 y2 y3 y4 x1 3/8 2/8 1/ 2/8 8 x2 2/8 2/8 3/ 1/8 8 x3 1/8 3/8 2/ 2/8 8 x4 2/8 1/8 2/ 3/8 8 - Tính entropi đầu vào kênh tin H(X); Entropi đầu ra kênh H(Y); I(X|Y), I(Y| X), H(X,Y).Bài 8: Cho cấu trúc thống kê của đích Y={y1, y2, y3}. yi y1 y2 y3 P(yi) 1/2 1/ 1/4 4Ma trận nhiễu trên kênh. P(xi|yj) y1 y2 y3 x1 1/4 1/2 1/4 x2 1/2 1/4 1/4 x3 1/4 1/4 1/2 - Tính tốc độ lập tin tại đầu ra kênh tin, đầu vào kênh tin, thông lượng kênh, độ dư tương đối của nguồn. Biết rằng số ký hiệu lập được trong một đơn vị thời gian là n0. CHƯƠNG 4Bài 1: Cho các từ mã x = ‘101010’, y = ‘110101’, z = ‘000110101’. Hãy biểu diễncác từ mã trên bằng phương pháp tọa độ mã và đồ hình mã.Bài 2: Cho bộ mã có các từ mã sau: 10 110 1110 01 001 0001. Hãy xác định tínhphân tách được và độ chậm phân giải của bộ mã bằng phương pháp dùng bảngt hử .Bài 3: Hãy giải thích tại sao 3 bộ mã Fano, Huffman, Shannon phân tách được.Bài 4. Để làm giảm sai lầm khi nhận tin bằng cách truy ền lặp l ại một bit 5 l ần.khi nhận 5 bit liền nhau ở cuối kênh được xem như là 1 bit. Giá trị bit này là 0nếu số bit 0 trong dãy lớn hơn số bit 1, ngược l ại n ếu s ố bit 1 nhi ều h ơn thì giátrị bit là 1. Biết xác suất nhiễu 1 bit là p=0.2; tổng số bit nh ận sai sau 5 l ần l ặptuân theo luật phân phối nhị thức B(p,5). Hãy tính xác suất truyền sai.Bài 5: Cho xâu x = ‘KHOA_CONG_NGHE_THONG_TIN’. - Để thỏa mãn điều kiện của bộ mã thống kê tối ưu thì độ dài trung bình từ mã phải thỏa mãn giới hạn nào? (Tính giới hạn trên, giới hạn dưới của bộ mã). - Sử dụng thuật toán ...