Tài liệu Bai tap thao luan ly thiet thong tint (1)

  • Số trang: 13 |
  • Loại file: PDF |
  • Lượt xem: 716 |
  • Lượt tải: 0
euroviet

Đã đăng 38 tài liệu

Mô tả:

Bài tập trong thảo luận nhóm môn môn học lý thuyết thông tin
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN & TRUYỀN THÔNG BÀI TẬP THẢO LUẬN MÔN HỌC TOÁN HỌC LÝ THUYẾT THÔNG TIN Số tín chỉ : 02 Hệ: Đại học chính qui Ngành: Nhóm ngành Công nghệ thông tin Khoa : Công nghệ thông tin Nhóm giảng viên biên soạn : 1. TS Trần Thị Ngân 2. ThS Dương Thị Mai Thương 3. ThS Đào Thị Thu 4. KS Phạm Thế Anh Đơn vị : Bộ môn Khoa học máy tính Năm : 2014 1 MỤC LỤC BÀI THẢO LUẬN 1: LƯỢNG TIN NGUỒN RỜI RẠC ........................................................3 BÀI THẢO LUẬN 2: ENTROPY NGUỒN RỜI RẠC VÀ MỐI LIÊN HỆ GIỮA LƯỢNG TIN VÀ ENTROPY ..................................................................................................................6 BÀI THẢO LUẬN 3: MÃ THỐNG KÊ TỐI ƯU ....................................................................8 BÀI THẢO LUẬN 4: MÃ CHỐNG NHIỄU VÀ MÃ TUYẾN TÍNH ................................. 11 2 BÀI THẢO LUẬN 1: LƯỢNG TIN NGUỒN RỜI RẠC 1.1 Tổng hợp kiến thức về xác suất 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ại mộ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: 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 8 điểm trên điểm sàn là , số thí sinh dưới điểm sàn là 10 2 . Trong số thí sinh đạt điểm trên 10 đ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ọc sinh 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í sinh khi biết khu vực cư trú? Bài giải: - P(năng lực)={ 8 ; 10 2 } 10 Thành thị Trên sàn 30% 8 Nông thôn 70% 10 Dưới sàn 60% 2 10 8 10 40% 2 10 - Lượng tin về năng lực khi biết khu vực cư trú: I(năng lực/cư trú) = -log p(năng lực/cư trú) 1.2 Bài tập về lượng tin Câu 3: A chọn ngẫu nhiên 1 số từ khoảng từ 0 tới 7. Cho biết số câu hỏi trung bình tối thiểu mà B cần đặt cho A để xác định được số mà A đã chọn? Giả sử A đã chọn là 5, hãy đặt ra các câu hỏi cần thiết để B có thể xác định được số mà A đã chọn. Bài giải: A chọn ngẫu nhiên 1 số từ khoảng từ 0 tới 7. Cho biết số câu hỏi trung bình tối thiểu mà B cần đặt cho A để xác định được số mà A đã chọn? Giả sử A đã chọn là 5, hãy đặt ra các câu hỏi cần thiết để B có thể xác định được số mà A đã chọn. 3 Bài giải: - Độ bất định của số được chọn ngẫu nhiêu: I(ai) = - log p(ai) = -log1/8 = 3 (bit) (Vì xác suất chọn các số 0-7 là như nhau nên lượng tin trung bình của cả nguồn tin I(A)=3 bit). - Để tìm được số A đã chọn thì B phải đặt các câu hỏi cho A để thu được lượng thông tin tối thiểu 3 bit. - Mỗi câu hỏi của B ở dạng lựa chọn (trả lời đúng/sai) vì thế có thể coi như là nguồn rời rạc nhị phân, vậy độ bất định trung bình nhận được sau mỗi câu trả lời là: H B   p lo g p –  1  p  lo g  1  p  Với: p và (1- p) là xác suất nhận được câu trả lời là “đúng” và “sai”. - Số câu hỏi cần thiết đặt ra là n  I ( A) ( I ( A)  nH (B ) Lượng tin trung bình của nguồn H (B) thu được bằng số câu hỏi đặt ra nhân với độ bất định của từng câu trả lời) - Số câu hỏi là trung bình tối thiểu khi H(B) = max. - H(B)max khi p 1 p  1/ 2 vậy n m in  3 b it  3 n m in  I ( A) H ( B ) m ax lần hỏi. 1b it Giả sử A chọn số 5, các câu hỏi B có thể dặt cho A là: - Câu 1: Số A chọn lớn hơn 4 (chia đôi khoảng) Trả lời: Đúng - Câu 2: Sô A chọn nhỏ hơn 7 (lớn hơn 4 thì sẽ là 5,6,7) Trả lời: Đúng - Câu 3: Số A chọn là 6 (nhỏ hơn 7 và lớn hơn 4 thì là 5,6) Trả lời: Sai - Vậy số A chọn là 5. Tương tự áp dụng bài này nếu A chọn số trong khoảng 0-15, giả sử A chọn số 9 B hãy đặt câu hỏi để xác định số A đã chọn. Câu 4: Trong bộ bài 52 cây (không tính phăng teo). A rút ra 1 cây bất kỳ. Tính số câu hỏi trung bình tối thiểu để xác định được cây bài A rút. Giả sử A rút cây 9 bích, hãy nêu phương thức hỏi cần thiết để xác định. Câu 5: Một thiết bị diện tử gồm 16 khối có độ tin cậy như nhau và được mắc nối tiếp. Sử dụng thiết bị đo ở đầu ra mỗi khối, giả sử có 1 khối bị hỏng. Tính số lần đo trung bình tối thiểu để xác định được khối bị hỏng. Giả sử khối bị hỏng là khối thứ 7, tìm vị trí các điểm đo cần thiết. 4 Bài 6: Có 27 đồng tiền (đúc bằng kim loại) cùng một giá trị, trong đó có 26 đồng có khối lượng như nhau, 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ền giả này? Nêu phương thức cân. Bài giải: Trong 27 đồng xu có 1 đồng xu giả nhẹ hơn. Để tìm được đồng xu giả người ta sử dụng một đĩa cân thăng bằng. Hãy tính số lần câu trung bình tối thiểu để xác định được đồng xua giả. Nêu phương thức cân? Bài giải: - Độ bất định trung bình I(A)=log27 - Khi cân có 3 khả năng xảy ra: o Cân thăng bằng với xác suất p o Cân lệch trái với xác suất q o Cân lệch phải với xác suất 1-(p+q) - Độ bất định TB mỗi lần cân - Số lần cân cần thiết n   p lo g p  q lo g q  (1  p  q ) lo g (1  p  q ) I ( A) H (B) - Số lần cân tối thiểu n m in  I ( A) H ( B ) m ax  lo g 2 7  3 lo g 3 lần cân. Phương thức cân: (đảm bảo p = q = q – p – q) - Lần 1: Chia 27 đồng xu thành 3 phần, mỗi phần lấy 9 đồng xu. Lấy 2 phần bất kỳ đặt lên mỗi bàn cân 1 phần. Nếu cân thăng bằng thì đồng xu giả ở phần con lại. Ngược lại, tùy theo cân lệch trái hay phải ta xác định được đồng xu giả ở phần nào. - Lần 2: Chia 9 đồng xu có chưa đồng xu giả thành 3 phần như nhau, mỗi phần có 3 đồng xu. Đặt 2 phần bất kỳ lên cân, kêt quả sẽ thu được phần chưa đồng xu giả. - Lần 3: Lấy 2 đồng xu bất kỳ lên cân và xác định được đồng xu giả 5 BÀI THẢO LUẬN 2: ENTROPY NGUỒN RỜI RẠC VÀ MỐI LIÊN HỆ GIỮA LƯỢNG TIN VÀ ENTROPY 2.1Entropy nguồn rời rạc Bài 1: Cho cấu trúc thống kê của nguồn X={x1, x2, x3}. xi x1 x2 x3 P(xi) 0.25 0.25 0.5 Cho ma trận nhiễu trên kênh: P(yj|xi) y1 y2 y3 x1 0.25 0.5 0.25 x2 0.5 0.25 0.25 x3 0.25 0.25 0.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 2: Cho hệ thống truyền tin. Kênh tin X Y Trong đó X={x1, x2, x3} là nguồn tin tại đầu vào kênh thông qua sự truyền lan trong 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/16 1/16 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 3: 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/8 1/8 2/8 Ma trận nhiễu trên kênh. 6 P(yj|xi) y1 y2 y3 y4 x1 3/8 2/8 1/8 2/8 x2 2/8 2/8 3/8 1/8 x3 1/8 3/8 2/8 2/8 x4 2/8 1/8 2/8 3/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 4: Cho cấu trúc thống kê của đích Y={y1, y2, y3}. yi y1 y2 y3 P(yi) 1/2 1/4 1/4 Ma 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à n 0. 2.2Bài tập về mối liên hệ giữa entropy và lượng tin Bài 5: Nêu ý nghĩa và chứng minh các công thức sau: 1. I ( X ,Y )  I ( X )  I ( X | Y ) 2. I ( X , Y )  H ( X )  H (Y )  H ( X , Y ) 3. H ( X , Y )  H ( X )  H (Y | X ) 7 BÀI THẢO LUẬN 3: MÃ THỐNG KÊ TỐI ƯU 3.1 Tổng hợp kiến thức về khái niệm mã thống kê tối ưu, các phương pháp mã hóa. 3.2 Bài tập về mã thống kê tối ưu Bài 1: Cho các từ mã x = „101010‟, y = „110101‟, z = „000110101‟. Hãy biểu diễn cá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ính phân tách được và độ chậm phân giải của bộ mã bằng phương pháp dùng bảng thử. 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à 0 nế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ặp tuâ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 mã hóa Fano, Shanon, Huffman để mã hóa xâu x với cơ số mã m = 2. - Tính trị số kinh tế, vẽ cây mã của từng bộ mã. Có nhận xét gì về 3 phương pháp mã hóa? - Mở rộng cho cơ số mã m = 3 cho ba phương pháp. o Viết lại thuật toán mã hóa o Áp dụng mã hóa xâu x o Tính trị số kinh tế của mỗi bộ mã. Bài 6: Cho nguồn U = {u1, u2, u3, u4} với xác suất xuất hiện tương ứng 0,25; 0,2; 0,15}. Xét nguồn mới U2 = { uiuj , với 1  i , j  4 P(ui) = {0,4; } có tập phân bố xác suất là U2 = {0,16; 0,1; 0,08; 0,06; 0,1; 0,0625; 0,05; 0,0375; 0,08; 0,05; 0,04; 0,03; 0,06; 0,0375; 0,03; 0,0225} . - Hãy mã hóa nguồn U và U2 bằng phương pháp mã hóa Huffman. - Đưa ra nhận xét về hiệu suất mã hóa của hai nguồn U và U2 . 8 Bài 8: Sử dụng các ngôn ngữ đã học, viết chương trình minh họa 3 thuật toán Fano, Shanon, Huffman Thuật toán mã hóa Shanon Thuật toán mã hóa Fano 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. TgA:=A[i]; A[i]:=A[j]; A[j]:=TgA; TgP:=P[i]; P[i]:=P[j]; P[j]:=TgP; End; end; Procedure Mahoa_Shanon; Var k:integer; s:real; nn:array[1..255] of integer; Begin for i:=1 to n do ma[i]:=''; for i:=1 to n do begin nn[i]:=0;S:=1; repeat nn[i]:=nn[i]+1;S:=S*0.5;until S1 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. Bài 9: Cho xâu x = „abcbabcbabcbabbbc‟. Sử dụng thuật toán mã hóa Lempel – Ziv để lập mã và giải mã cho xâu x. 10 BÀI THẢO LUẬN 4: MÃ CHỐNG NHIỄU VÀ MÃ TUYẾN TÍNH 4.1 Mã chống nhiễu Bài 1: Cho bộ mã: a1 = 0101001, a2 = 1111101, a1 = 0101001, a3 = 1100011, a4 = 1010001. - Sử dụng phương pháp phát hiện sai bằng quãng cách Hamming, bộ mã này có thể sửa sai được mấy ký hiệu? - Nếu tại đầu ra kênh tin nhận được tin b1 = 0011010 và b2 = 1101101 có thể sửa sai được cho 2 tin b1 , b2 được không? Nếu được sửa lại về tin chính xác. Bài 2: Cho các bộ mã: a1 0 1 0 1 1 0 0 a2 1 1 0 1 0 0 0 a3 1 0 0 1 1 1 0 a4 0 1 1 0 1 0 1 - Xây dựng bộ mã phát hiện sai bằng phương pháp parity chẵn/ lẻ và phương pháp dùng mã khối. - Xây dựng bộ mã phát hiện sai bằng phương pháp mã thuận nghịch. - Bộ mã trên có hệ số tỷ lệ là bao nhiêu? Gợi ý giải: Với một từ mã có 4 ký hiệu véc tơ sai cũng có 4 ký hiệu, có các phương án sai 1 ký hiệu, 2 ký hiệu, 3 ký hiệu .. Ta có bảng sau: Vec tơ mã a1 a2 a3 a4 Số k. h sai 0001 0101 1110 1111 Vec tơ sai 0001 0000 0100 0010 0011 0111 1100 1101 1 0100 1010 1011 1000 1001 1101 0110 0111 0011 0010 0110 1101 1100 0101 0100 0000 1011 1010 1001 1000 1100 0111 0110 2 1010 1011 0100 1100 1101 1001 0010 0011 0111 0110 0010 1001 1000 1011 1010 0100 3 1101 1100 1000 0011 0010 1110 1011 0000 11 1111 - 1010 - 0000 4 - Với nhận xét trên ta có các tổ hợp cấm được phân thành nhóm, các từ mã cấm trong nhóm Bi tương ứng với từ mã đúng ai. Ta dược bảng sau: B1 B2 B3 B4 0000 0100 1100 1101 0011 0111 1010 1011 1001 1101 0110 0111 - Ta thấy nhận được tổ hợp „0111‟ hoặc „1101‟ do sai 1 ký hiệu ta có thể giải mã và sửa thành „0101‟ ( a ), như vậy theo nguyên tắc trên ta có thể sửa sai cho bộ mã. Tuy 2 nhiên như bộ mã trên cũng cho thấy có thể sửa không chính xác vì tổ hợp „1101‟ có thể sửa thành a2 cũng có thể sửa thành a4 . Để giải quyết người ta khắc phục bằng cách dùng bảng chọn hoặc tính khoảng cách mã của bộ mã. 4.2 Mã tuyến tính Bài 3: Xác định mã V(6,4) từ ma trận sinh Bài 4: Cho biết ma trận sinh 1 0 1 1  G    0100 1 1 1 0 0 0    101010  G    0 0 0 1 1 1    0 1 0 1 0 1 , các vec tơ nhiễu: 0010, 1000, 1001. Bằng phương pháp tính Syndrom hãy sửa sai cho dãy mã sau: 10100101. Bộ mã trên sửa sai được tối đa bao nhiêu bit? Gợi ý giải: Bước 1: Xếp lớp kề: v 00000 00101 01010 01111 10011 10110 11001 11100 e V1 00001 00100 01011 01110 10010 10111 11000 11101 V2 00010 00111 01000 01101 10001 10100 11011 11110 V3 10000 10101 11010 11111 00011 00110 01001 01100 12 Tính Syndrom của các lớp 1, 2, 3 lần lượt bằng : 01, 10, 11. Các vec tơ tạo lớp kề : 00001, 00010, 10000 là những vec tơ sai. Mã này không sửa được hết tất cả các từ mã sai một bit, vì khoảng cách mã tối thiểu D  2 . Muốn sửa được thì D  3. Bước 2: Giả thiết nhận được v '  1 0 1 1 1 , Syndrom S  v ' H  0 1 ứng với vec tơ tạo lớp kề 00001. Bước 3: Từ mã gốc: v  1 0 1 1 1  0 0 0 0 1  1 0 1 1 0 T 13
- Xem thêm -