Bài tập lý thuyết thông tin và lời giải năm 2024
|
Chương III: MÃ THỐNG KÊ TỐI ƯU Bài tập: Lập một bộ mã cho nguồn tin u có sơ đồ thống kê như sau. Ui U1 U2 U3 U4 U5 U6 U7 U8 U9 P(u) 0.34 0.2 0.19 0.1 0.07 0.04 0.03 0.02 0.01 Bằng mã nhị phân (m=2)theo phương pháp shannon. Tính độ dài trung bình của từ mã ntb và tính kinh tế của từ mã: p=H(U)/Ntb. Giải Sơ đồ mã hóa theo phương pháp mã hóa shannon: Ui U1 U2 U3 U4 U5 U6 U7 U8 U9 P(ui) 0.34 0.2 0.19 0.1 0.07 0.04 0.03 0.02 0.01 Pi 0 0.34 0.54 0.73 0.83 0.9 0.94 0.97 0.99 ni 2 3 3 4 4 5 6 6 7 Dạng mã nhị phân của pi 0 0.01010111 0.10001010 0.10111010 0.11010100 0.11100110 0.11110000 0.11111000 0.11111101 Từ mã 00 010 100 1011 1101 11100 111100 111110 1111110 Độ dài trung bình từ mã: NTB= Entropy của tập tin: H(u)= Chỉ số kinh tế của bộ mã: p= \=0,8279 1 11/13/2011 ĐẶNG QUANG HUY - D09VTH2 GVHD: NGUYỄN THỊ LAN ANH __________________________________________________________________ Chương IV: MÃ CHỐNG NHIỄU: MÃ KHỐI Bài tập: Ma trận sinh của bộ mã tuyến tính (6,3) trên trường GF(2) là: G= a. Biểu diễn G dưới dạng chuẩn Gch. b. Liệt kê các từ mã có được từ G và Gch. c. Có bao nhiêu từ mã có trọng số hamming là 1,2,3,4,5,6,7. Giải a. Biểu diễn G dưới dạng chuẩn Gch. Gch= b. Liệt kê các từ mã của G và Gch. Vector mang tin a 000 001 010 011 100 101 110 111 v= a.G w(v) v’=a.Gch w(v’) 000000 110110 110001 000111 011010 101100 101011 011101 0 4 3 3 3 3 4 4 000000 001111 010110 011001 100011 101100 110101 111010 0 4 3 3 3 3 4 4 2 11/13/2011 ĐẶNG QUANG HUY - D09VTH2 GVHD: NGUYỄN THỊ LAN ANH
__________________________________________________________________ Chương V: MÃ VÒNG a. Bài tập: Cho mã vòng (n,k)=(7,4)có ma trận sinh là g(x)=x3+x+1. Liệt kê tất cả các từ mã của bộ mã và cho biết bộ mã có khả năng sửa sai bao nhiêu bit? Giải Cho d= (0001) ta tính được: V1=0001000+dư số V1=0001000+011=0001011 Quay vòng từ mã v1 ta sẽ được thêm 6 từ mã nữa: V2=1000101 V3=1100010 V4=0110001 V5=1011000 3 11/13/2011 ĐẶNG QUANG HUY - D09VTH2 GVHD: NGUYỄN THỊ LAN ANH V6=0101100 V7=0010110 Cho d=(0011) ta tính được: Vδ=0011000+dư số Vδ=0011000+101=00111101 Quay vòng từ mã vδ ta sẽ được thêm 6 từ mã nữa: V9 =1001110 V10 =0100111 V11=1010011 V13 =1110100 V14=0111010 Cho d=(1111000) ta tinh được: V15=1111000+dư số V15=1111000+111=1111111 Cho d=(0000) ta tính được: V0=0000000 + dư số b. Ta có thể tính dễ dàng trọng số Hamming của bộ mã là trọng số nhỏ nhất của từ mã khác không : H(V)=3 nên bộ mã có khả năng sửa được tất các mẫu sai 1bít. BÀI TẬP LÝ THUYẾT THÔNG TIN Chương 2: Lượng Tin Trong một trò sổ số vui người ta sổ 10 chữ số từ 0 đến 9. 4 11/13/2011 ĐẶNG QUANG HUY - D09VTH2 GVHD: NGUYỄN THỊ LAN ANH Xác suất trúng của mỗi nhóm lá như nhau. a. Tính lượng tin riêng của tin: “số trúng giải là số 9” b. Tính lượng tin tương hỗ giữa tin: “số trúng giải là số 9” so với tin: “số trúng giải là số chia hết cho 3”. c. Trong 10 tin trên gọi U={u1, u2, u3, u4, u5, u6} với ui là tin “số i trung giải” (i=0,1,.....,6). Tìm lượng tin trung bình của tập tin U. Giải a. Gọi p(9) là xác suất số 9 trúng giải ta có: p(9) = \= 0.1 Vậy I(9) = b. Gọi p(0-3-6-9) là xác suất trúng giải chia hết cho 3. Ta có p(0-3-6-9) = Mặc khác I(9/0-3-6-9) = \= \= Vậy: I(9;0-3-6-9) = I(9)-I(9/0-3-6-9) = = 1.322 c. Lượng tin trung bình của tập tin U: I(U) = \=- \= \= 2.325 5 11/13/2011 ĐẶNG QUANG HUY - D09VTH2 GVHD: NGUYỄN THỊ LAN ANH Chương 3: Mã Thống Kê Tối Ưu Cho nguồn tin U có sơ đồ thống kê như sau: ui p(ui) u1 0.338 u2 0.32 u3 0.13 u4 0.1 u5-6 0.018 u7-9 0.01 u10-18 0.005 u19 0.01 Dùng mã Huffman kết hợp mã đều để mã hóa nguồn tin trên với cơ số mã m=3. Tính ntb và tính kinh tế của từ mã: Giải Sơ đồ mã hóa theo phương pháp mã hóa Huffman: ui u1 u2 u3 u4 u5 u6 u7 u8 u9 u10 u11 u12 u13 u14 u15 u16 u17 u18 u19 p(ui) 0.338 0.32 0.13 0.1 0.018 0.018 0.01 0.01 0.01 0.005 0.005 0.005 0.005 0.005 0.005 0.005 0.005 0.005 0.001 ni 1 1 2 2 4 4 4 4 4 5 5 5 5 5 5 5 5 5 4 Từ mã 0 1 20 21 2210 2211 2200 2201 2202 22200 22201 22202 22210 22211 22212 22220 22221 22222 2212 Phương pháp mã hóa như sau: • Bước 1: sắp xếp các tin có xác suất theo thứ tự giảm dần. • Bước 2: ghép 3 tin có xác suất nhỏ nhất, trở thành tin phụ mới • Bước 3: lặp lại giống bước 1( sắp xếp các tin theo xác suất giảm dần • Bước 4: ghép 3 tin có xác suất nhỏ nhất trở thành tin phụ mới (cách trình bày này lập đi lập lại cho đến khi còn 1 tin cuối cùng). 6 11/13/2011 ĐẶNG QUANG HUY - D09VTH2 Độ dài trung bình tư mã: ntb = Entropy của tập tin: H(U) = - GVHD: NGUYỄN THỊ LAN ANH \= Chỉ số kinh tế của bộ mã: p = \= 0.9913 Chương 4: Mã Khối Mã Chống Nhiễu Ma trận sinh của bộ mã tuyến tính (7,3) trên trường GF(2) là: G =
Giải
Hch = [-PT.In-k]
1 0 1 1 0 0 0 7 11/13/2011 ĐẶNG QUANG HUY - D09VTH2 Hch = GVHD: NGUYỄN THỊ LAN ANH 0 1 1 0 1 0 0 1 1 1 0 0 1 0 1 1 0 0 0 0 1
Vector mang v= a.G tin a 000 0000000 001 1011100 010 0101110 011 1110010 100 0010111 101 1001011 110 0111001 111 1100101 w(v) v’=a.Gch w(v’) 0 4 4 4 4 4 4 4 0000000 0011110 0100111 0111001 1001011 1010101 1101100 1110010 0 4 4 4 4 4 4 4
Chương 5: Mã Vòng Đa thức sinh của bộ mã vòng hamming là: g(x)=1+x3+x4 a. Tìm đa thức thử h(x) của bộ mã này. b. Thiết kế mạch mã hóa thực hiện qua h(x). c. Xác định các bit thử và từ mã nhận được tương ứng với chuỗi bit mang tin d=(10000001011). Giải 8 11/13/2011 ĐẶNG QUANG HUY - D09VTH2 GVHD: NGUYỄN THỊ LAN ANH
n = 2n-k-1 = 24-1 = 15. h(x) = (xn+1)/g(x) Từ công thức: Ta tính được: h(x) =
thì: v(x) = d(x).xn-k + dư số của = + số dư của \=( ) Trong đó x3+1 tương ứng với chuỗi bit 1001 là các bit thử và từ mã nhận được tương ứng với v(x) = ( ) là v = (100000101110010). BÀI TẬP MÔN LÝ THUYẾT THÔNG TIN. CHƯƠNG 1: LƯỢNG TIN ĐỀ BÀI: Xác định entropy khi đổ súc sắc. Giả sử súc sắc được chế tạo sao cho xác xuất suất hiện của bất kỳ mặt nào cũng tỉ lệ với số chấm trên mặt súc sắc. GIẢI: Gọi P(xi) là xác suất của các mặt súc sắc. Với i=(1,2,3,4,5,6) Entropy khi đổ súc sắc: 6 H(x) = ∑ P(xi). I(xi) 1 \=− 1 1 2 2 3 3 4 4 5 5 6 6 .log 2 ( ) - log 2 ( ) - log 2 ( ) - log 2 ( ) - log 2 ( ) - log 2 ( ) 21 21 21 21 21 21 21 21 21 21 21 21 \= 0.209 + 0.323 + 0.401 + 0.455 + 0.492 + 0.516 9 11/13/2011 ĐẶNG QUANG HUY - D09VTH2 GVHD: NGUYỄN THỊ LAN ANH \= 2.396 (bit) CHƯƠNG 2: MÃ THỐNG KÊ TỐI ƯU ĐỀ BÀI: Lập một bộ mã cho nguồn tin U có sơ đồ thống kê như sau: Ui P(ui) U1 .34 U2 .2 U3 .19 U4 .1 U5 .07 U6 .04 U7 .03 U8 .02 U9 .01 Bằng mã nhị phân (m = 2) theo phương pháp Shannon. Tính độ dài trung bình của từ mã và tính kinh tế của bộ mã. GIẢI: Sơ đồ mã hóa theo phương pháp Shannon: ui U1 U2 U3 U4 U5 U6 U7 U8 U9 P(ui) .34 .2 .19 .1 .07 .04 .03 .02 .01 Pi 0 .34 .54 .73 .83 .9 .94 .97 .99 ni 2 3 3 4 4 5 6 6 7 Dạng nhị phân của Pi 0 0.010 0.100 0.1011 0.1101 0.11100 0.111100 0.111110 0.1111110 Từ mã 00 010 100 1011 1101 11100 111100 111110 1111110 Độ dài trung bình của từ mã: 9 ntb = ∑ ni p (ui ) = 3.1 i =1 Entropy của tập tin: 9 H (U ) = − ∑ p (u i ) log 2 p (u i) = 2.5644 i =1 Tính kinh tế của bộ mã: 10 11/13/2011 ĐẶNG QUANG HUY - D09VTH2 ρ= GVHD: NGUYỄN THỊ LAN ANH H (U ) 2.5644 = = 0.8279 ntb 3.1 BÀI TẬP LÝ THUYẾT THÔNG TIN Chương 2: Lượng Tin Xem các con bài của bộ bài 52 lá tạo thành 1 nguồn tin rời rạc. Tính entropy của một lá bài rút ngẫu nhiên. Giả sử bỏ qua nước của con bài để bây giờ U={ Ace, 2, 3, 4, 5, 6, 7, 8, 9, 10, Jack, Qeen, King}. Tính entropy của một lá bài rút ngẫu nhiên trong trường hộp này, trong trường hợp U=(bài có hình, bài không hình). Giải d. H(U)= với p(ui)= =- (i=1, 2, 3,.......,52) \=-52
với p(ui)= =- \=5.700 (i=1, 2, 3,.......,13) \=-13 \=3.700
Gọi uoh là tin con bài không hình thì p(uoh)= Vậy H(U)= p(uh)I(uh)+p(uoh)I(uoh) =- p(uh) )-p( ) 11 11/13/2011 ĐẶNG QUANG HUY - D09VTH2 =- - GVHD: NGUYỄN THỊ LAN ANH = 0.779 Chương 5: Mã Vons Đa thức sinh của bộ am vòng hamming là: g(x)=1+x3+x4 d. Tìm đa thức thử h(x) của bộ am này. e. Thiết kế mạch am hóa thực hiện qua h(x). f. Xác định các bit thử và từ am nhận được tương ứng với chuỗi bit mang tin d=(10000001011). Giải
n=2n-k-1=24-1=15. Từ công thức: h(x)=(xn+1)/g(x) Ta tính được: h(x)= d. Khi d=(10000001011) hay d(x)= thì: v(x)=d(x).xn-k+ dư số của 12 11/13/2011 ĐẶNG QUANG HUY - D09VTH2 = GVHD: NGUYỄN THỊ LAN ANH + số dư của \=( ) Trong đó x3+1 tương ứng với chuỗi bit 1001 là các bit thử và từ am nhận được tương ứng với v(x)= ( ) là v=(100000101110010). BÀI TẬP LÝ THUYẾT THÔNG TIN Chương 2: Lượng Tin. = Chương 3: Mã Thống Kế Tối Ưu. Bài tập: Lập một bộ mã cho nguồn tin u có sơ đồ thống kê như sau. Ui U1 U2 U3 U4 U5 U6 U7 U8 U9 P(u) 0.34 0.2 0.19 0.1 0.07 0.04 0.03 0.02 0.01 Bằng mã nhị phân (m=2)theo phương pháp shannon. Tính độ dài trung bình của từ mã ntbvà tính kinh tế của từ mã:p=H(U)/Ntb Giải Sơ đồ mã hóa theo phương pháp mã hóa shannon: Ui U1 U2 U3 U4 U5 U6 U7 U8 U9 P(ui) 0.34 0.2 0.19 0.1 0.07 0.04 0.03 0.02 0.01 Pi 0 0.34 0.54 0.73 0.83 0.9 0.94 0.97 0.99 ni 2 3 3 4 4 5 6 6 7 Dạng mạ nhị phân của pi 0 0.01010111 0.10001010 0.10111010 0.11010100 0.11100110 0.11110000 0.11111000 0.11111101 Từ mã 00 010 100 1011 1101 11100 111100 111110 1111110 Độ dài trung bình tư mã: NTB= 13 11/13/2011 ĐẶNG QUANG HUY - D09VTH2 Entropy của tập tin: GVHD: NGUYỄN THỊ LAN ANH H(u)= Chỉ số kinh tế của bộ mã: p= \=0,8279 Chương 4: Mã Chống Nhiếu : Mã Khối Chương 5: Mã Vòng. Bài tập: cho mã vòng (n,k)=(7,4) có ma trận sinh là g(x)=x3+x+1. Liệt kê tất cả các từ mã của bộ mã và cho biết bộ mã có khả năng sửa sai bao nhiêu bít. Giải A.cho d= (0001) ta tính được: V1=0001000+dư số V1=0001000+011=0001011 Quay vòng từ mãv1 ta sẽ đượcthêm 6 từ mã nữa: V2=1000101 V3=1100010 V4=0110001 V5=1011000 V6=0101100 V7=0010110 Cho d=(0011)ta tính được: Vδ=0011000+dư số Vδ=0011000+101=00111101 Quay vòng từ mã vδ ta sẽ đượcthêm 6 từ mã nữa: 14 11/13/2011 ĐẶNG QUANG HUY - D09VTH2 GVHD: NGUYỄN THỊ LAN ANH V9 =1001110 V10 =0100111 V11=1010011 V13 =1110100 V14=0111010 Cho d=(1111000) ta tinh được: V15=1111000+dư sô V15=1111000+111=1111111 Cho d=(0000) ta tính được: V0=0000000+dư số B. ta có thể tính rễ ràng trọng số hamming của bộ mã là trọng số nhở nhất của từ mã khác không : H(V)=3 nên bộ mã có khả năng sửa được tất các mẫu sai 1bít. __________________________________________________________________ Chương III: MÃ THỐNG KÊ TỐI ƯU Bài tập: Lập một bộ mã cho nguồn tin u có sơ đồ thống kê như sau. Ui U1 U2 U3 U4 U5 U6 U7 U8 U9 P(u) 0.34 0.2 0.19 0.1 0.07 0.04 0.03 0.02 0.01 Bằng mã nhị phân (m=2)theo phương pháp shannon. Tính độ dài trung bình của từ mã ntb và tính kinh tế của từ mã: p=H(U)/Ntb. Giải Sơ đồ mã hóa theo phương pháp mã hóa shannon: Ui U1 U2 U3 P(ui) 0.34 0.2 0.19 Pi 0 0.34 0.54 ni 2 3 3 Dạng mã nhị phân của pi 0 0.01010111 0.10001010 Từ mã 00 010 100 15 11/13/2011 ĐẶNG QUANG HUY - D09VTH2 U4 U5 U6 U7 U8 U9 0.1 0.07 0.04 0.03 0.02 0.01 0.73 0.83 0.9 0.94 0.97 0.99 4 4 5 6 6 7 GVHD: NGUYỄN THỊ LAN ANH 0.10111010 0.11010100 0.11100110 0.11110000 0.11111000 0.11111101 1011 1101 11100 111100 111110 1111110 Độ dài trung bình từ mã: NTB= Entropy của tập tin: H(u)= Chỉ số kinh tế của bộ mã: p= \=0,8279 __________________________________________________________________ Chương IV: MÃ CHỐNG NHIỄU: MÃ KHỐI Bài tập: Ma trận sinh của bộ mã tuyến tính (6,3) trên trường GF(2) là: G= h. Biểu diễn G dưới dạng chuẩn Gch. i. Liệt kê các từ mã có được từ G và Gch. j. Có bao nhiêu từ mã có trọng số hamming là 1,2,3,4,5,6,7. Giải h. Biểu diễn G dưới dạng chuẩn Gch. Gch= i. Liệt kê các từ mã của G và Gch. 16 11/13/2011 ĐẶNG QUANG HUY - D09VTH2 Vector mang tin a 000 001 010 011 100 101 110 111 GVHD: NGUYỄN THỊ LAN ANH v= a.G w(v) v’=a.Gch w(v’) 000000 110110 110001 000111 011010 101100 101011 011101 0 4 3 3 3 3 4 4 000000 001111 010110 011001 100011 101100 110101 111010 0 4 3 3 3 3 4 4
Chương V: MÃ VÒNG BÀI TẬP MÔN LÝ THUYẾT THÔNG TIN. CHƯƠNG 1: LƯỢNG TIN. 1. Trong một trò chơi xổ số vui người ta xổ 10 chữ số từ 0 đến 9. Xác xuất trúng của mỗi số là như nhau. a. Tính lượng tin riêng của tin : “ số trúng giải là số 9”. b. Tính lượng tin tương hỗ giữa tin : “số trúng giải là 9” so 17 11/13/2011 ĐẶNG QUANG HUY - D09VTH2 GVHD: NGUYỄN THỊ LAN ANH với tin :”số trúng giải là số chia hết cho 3”. c. Trong 10 tin trên gọi U=(u1,u2,u3,u4,u4,u5,u6) với ui là tin “số i trúng giải” (i=0,1,…,6). Tìm lượng tin trung bình của tập tin U. Bài làm a. Gọi p(9) là xác suất số 9 trúng giải ta có p(9) = 1/10= 0.1 vậy I(9)= -log p(9)= log 10= 3.322 b. Gọi p(0-3-6-9) là xác suất để số trúng giải chia hết cho 3, ta có: p(0-3-6-9) = 4/10= 0.4 Mặt khác : I (9/0-3-6-9) = - log p(9/0-3-6-9) Vậy \= − log p (9 / 0 − 3 − 6 − 9) p (0 − 3 − 6 − 9) \= − log 1/ 10 = l og4 4 / 10 I(9; 0-3-6-9) = I(9) – I(9/0-3-6-9) 10 = log10− log4= log = 1.322 4 c. Lượng tin trung bình của tập tin U : 6 6 I (U) =p (u )I (u )i ∑ i =0 CHƯƠNG 2: MÃ THỐNG KÊ TỐI i 1 1 =− ∑ log 10 i=0 10 1 = .7.log10 10 18 11/13/2011 ĐẶNG QUANG HUY - D09VTH2 GVHD: NGUYỄN THỊ LAN ANH Trong kênh truyền tin nhị phân có nhiễu nguồn X = {x0,x1} có p(x0) = 0.4 và p(x1) = 0.6. Xác suất truyền tin sai nhầm p(y0/x1) = p(y1/x0) = 0.1, xác suất truyền tin đúng p(y0/x0) = p(y1/x1) = 0.9, với Y = {y0,y1} a/ Tính H(Y) b/ Tính H(Y/X) c/ Tính I(X;Y) Bài làm: a/ H(Y) = p(y0)I(y0) + p(y1)I(y1) p ( x, y i ) Áp dụng công thức p( x) = ∑ ∀i Ta có: P(y0) = p(y0,x0) + p(y0,x1) = p(y0) p(y0/x0) + p(x1) p(y0/x1) = 0,4.0,9 + 0,6.0,1 = 0,42 P(y1) = p(y1,x0) + p(y1,x1) = p(x0) p(y1/x0) + p(x1) p(y1/x1) = 0,4.0,1 + 0,6.0,9 = 0,58 H(Y) = -0,42log0,42 – 0,58log0,58 =0,8915 P ( x, y ) I ( y , x ) b/ H (Y / X ) = ∑ XY \= p(x 0,y0) I(y0/x0) + p(x0,y1) I(y1/x0) + p(x1,y0) I(y0/x1) + p(x1,y1) I(y1/x1) Mà: p(x0,y0) = p(x0) p(y0/x0) = 0,4.0,9 = 0,36 p(x0,y1) = p(x0) p(y1/x0) = 0,4.0,1 = 0,04 19 11/13/2011 ĐẶNG QUANG HUY - D09VTH2 GVHD: NGUYỄN THỊ LAN ANH p(x1,y0) = p(x1) p(y0/x1) = 0,6.0,1 = 0,06 p(x1,y1) = p(x1) p(y1/x1) = 0,6.0,9 = 0,54 I(y0/x0) = -log p(y0/x0) = -log0,9 = log10/9 I(y1/x0) = -log p(y1/x0) = -log0,1 = log10 I(y0/x1) = -log p(y0/x1) = -log0,1 = log10 I(y1/x1) = -log p(y1/x1) = -log0,9 = log10/9 Nên: H(Y/X) = 0,36log10/9 + 0,04log10 + 0,06log10 + 0,54log10/9 = 0.469 p ( x, y ) I ( x; y ) c/ I ( X ; Y ) = ∑ XY \= p(x 0,y0) I(x0;y0) + p(x0,y1) I(x0;y1) + p(x1,y0) I(x1;y0) + p(x1,y1)I(x1;y1) Mà: I(x0;y0) = I(y0;x0) = I(y0) - I(y0/x0) = log p(y0/x0)/p(y0) = log0,9/0,42 I(x 0;y1) = I(y1;x0) = I(y1) - I(y1/x0) = log p(y1/x0)/ p(y1) = log0,1/0,58 I(x 1;y0) = I(y0;x1) = I(y0) - I(y0/x1) = log p(y0/x1)/ p(y0) = log0,1/0,42 I(x 1;y1) = I(y1;x1) = I(y1) - I(y1/x1) = log p(y1/x1)/ p(y1) = log0,9/0,58 Vậy I(X;Y) = 0,36log0,9/0,42 + 0.04log0,1/0,58 + 0,06log0,1/0,42 + 0,54log0,9/0,58 = 0,512 BÀI TẬP LÝ THUYẾT THÔNG TIN __________________________________________________________________ Chương III: MÃ THỐNG KÊ TỐI ƯU 20 11/13/2011 ĐẶNG QUANG HUY - D09VTH2 GVHD: NGUYỄN THỊ LAN ANH Bài tập: Lập một bộ mã cho nguồn tin u có sơ đồ thống kê như sau. Ui U1 U2 U3 U4 U5 U6 U7 U8 U9 P(u) 0.34 0.2 0.19 0.1 0.07 0.04 0.03 0.02 0.01 Bằng mã nhị phân (m=2)theo phương pháp shannon. Tính độ dài trung bình của từ mã ntb và tính kinh tế của từ mã: p=H(U)/Ntb. Giải Sơ đồ mã hóa theo phương pháp mã hóa shannon: Ui U1 U2 U3 U4 U5 U6 U7 U8 U9 P(ui) 0.34 0.2 0.19 0.1 0.07 0.04 0.03 0.02 0.01 Pi 0 0.34 0.54 0.73 0.83 0.9 0.94 0.97 0.99 ni 2 3 3 4 4 5 6 6 7 Dạng mã nhị phân của pi 0 0.01010111 0.10001010 0.10111010 0.11010100 0.11100110 0.11110000 0.11111000 0.11111101 Từ mã 00 010 100 1011 1101 11100 111100 111110 1111110 Độ dài trung bình từ mã: NTB= Entropy của tập tin: H(u)= Chỉ số kinh tế của bộ mã: p= \=0,8279 __________________________________________________________________ Chương IV: MÃ CHỐNG NHIỄU: MÃ KHỐI __________________________________________________________________ Chương V: MÃ VÒNG BÀI TẬP LÝ THUYẾT THÔNG TIN Chương II 21 11/13/2011 ĐẶNG QUANG HUY - D09VTH2 GVHD: NGUYỄN THỊ LAN ANH Xem các con bài của bộ bài 52 lá tạo thành 1 nguồn tin rời rạc, Tính Entropy của 1 lá bài rút ngẫu nhiên. Giả sử bỏ qua nước của con bài để bây giờ U={ Ace, 2,3,4,5,6,7,8,9,10,Jack, Queen, King}. Tính Entropy của 1 lá bài rút ngẫu nhiên trong trường hợp này, trong trường hợp U={ bài có hình, bài ko hình} Giải: H(U)=i=152puiIui với p(ui)=1/52 ( i= 1,2,3,….52) =-i=152p(ui)log pui =-52.1/52 log (1/52)= log52 = 5700 b) H(U)=i=113puiIui với p(ui)=1/13 ( i= 1,2,3,….13) =-i=113p(ui)Iui =-13.1/13 log (1/13)= log13 = 3700 c) Gọi uh là tin bài có hình thì p(uh)=3/13 Gọi uoh là tin bài có hình thì p(uoh)=10/13 Vậy H(U)= p(uh)I (uh)+ p(uoh)I (uoh) =- p(uh)log p(uh)- )- p(uoh)log (uoh) \= 313log 313- 1013log1013 =0,779 Chương III Lập 1 bộ mã cho nguồn tin U có sơ đồ thống kê như sau: Ui u1 u2 u3 u4 u5 u6 u7 u8 u9 P(ui) .34 .2 .19 .1 .07 .04 .03 .02 .01 Bằng mã nhị phân the phương pháp shannon. Tính độ dài trung bình của từ mã ntb và tính kinh tế của từ mã p=H(U)/ ntb Giải: Sơ đồ mã hóa theo phương pháp mã hóa shannon: Ui P(ui) Pi ni Dạng nhị phân của Pi Từ Mã 22 11/13/2011 ĐẶNG QUANG HUY - D09VTH2 GVHD: NGUYỄN THỊ LAN ANH U1 .34 0 2 0 00 U2 .2 .34 3 0,01010111 010 U3 .19 .54 3 0,10001010 100 U4 .1 .73 4 0,10111010 1011 U5 .07 .83 4 0,11010100 1101 U6 .04 .9 5 0,11100110 11100 U7 .03 .94 6 0,11110000 111100 U8 .02 .97 6 0,11111000 111110 U9 .01 .99 7 0,11111101 1111110 Độ dài trung bình từ mã : ntb= i=19ni pui=3.1 Entropy của tập tin : H(U)=-i=19puilogui=2,5664 Chỉ số kinh tế của bộ mã: ρ= H(U)/ ntb=2.5664/3.1=0,8279 Chương V Chứng minh rằng trong 1 bộ mã vòng khi sai E(x) có thể dò được thì mẫu sai Ei(x) chuyển dịch vòng I bit so với E(x) cũng có thể dò được Giải: Nếu Ei(x) là 1 mẫu sai ko phát hiện được thì Ei(x) là 1 từ mã. Từ đây theo đn của mã vòng thì E(x) cũng là 1 từ mã.Khi đó vì mã vòng là mã tuyến tính nên 1 từ mã v(x) bất kỳ sau khi chịu tác động sai của E(x) sẽ biến thành 1 từ mã v’(x) và không phát hiện sai được. Điều này mâu thuẫn với giả thiết là E(x) là mẫu sai phát hiện được. BÀI TẬP LÝ THUYẾT THÔNG TIN 23 11/13/2011 ĐẶNG QUANG HUY - D09VTH2 GVHD: NGUYỄN THỊ LAN ANH Bài 8 : chứng minh rằng Bài giải : \= H(X) + H(Y/X) (đpcm) Bài 9 : Giả sử có một nguồn tin rời rạc xuất hiện p(u) khi u
độ dài l(u) thỏa : Chứng minh rằng độ dài trung bình Thỏa Bài giải: 24 11/13/2011 ĐẶNG QUANG HUY - D09VTH2 GVHD: NGUYỄN THỊ LAN ANH Theo đề bài với mọi u ta có: Vì p(u)>0 nên bất đẳng thức trên tương đương với: Cộng tất cả các bất đẳng thức của từng tin u theo vế: Hay Chương III :MÃ THỐNG KÊ TỐI ƯU BÀI 1: cho bộ mã có cơ số mã m = 4 như sau: U={3,23,11,123,10} a. Vẽ cây mã và đồ hình kết cấu của bộ mã U b. Vẽ mặt tọa độ mã c. Lập 1 bộ mã hệ thống 6 từ mã có các tổ hợp sơ đẳng. Vẽ đồ hình kết cấu của bộ mã vừa lặp Bài giải: a. Cây mã : ------------Mức 0 2 1 -----------Mức 1 3 1 2 0 --------------Mức 2 3 25 11/13/2011 ĐẶNG QUANG HUY - D09VTH2 GVHD: NGUYỄN THỊ LAN ANH -----------Mức 3 Đồ hình kết cấu : 0 0 3 1 0 b. Mặt tọa độ mã: ui ni pi 3 1 3 23 2 14 11 2 5 123 3 57 10 2 1
Bài 5 : lập 1 bộ mã cho nguồn tin U có sơ đồ thống kê như sau: ui u1 u2 u3 u4 u5 u6 u7 P(ui) .34 .2 .19 .1 .07 .04 .03 u8 u9 .02 .01 Bằng mã nhị phân m=2, theo phương pháp Shannon,tính đọ dài trung bình của từ mã ntb và tính theo kinh tế của từ mã : 26 11/13/2011 ĐẶNG QUANG HUY - D09VTH2 GVHD: NGUYỄN THỊ LAN ANH Bài giải : Sơ đồ mã hóa theo phương pháp Shannon: ui P(ui) Pi ni Dạng nhị phân của Pi Từ Mã u1 .34 0 2 0 00 u2 .2 .34 3 0.01010111 010 u3 .19 .54 3 0.10001010 100 u4 .1 .73 4 0.1011010 1011 u5 .07 .83 4 0.11010100 11 01 u6 .04 .9 5 0.11100110 11100 u7 .03 .94 6 0.11110000 111100 u8 .02 .97 6 0.11111000 111110 u9 .01 .99 1 0.11111101 1111110 Đọ dài trung bình từ mã : Etropy của tập tin: Chỉ số kinh tế của bộ mã : Bài 7 : cho nguồn tin U có sơ đồ thống kê như sau: ui u1 u2 u3 P(ui) .5 .25 .315 u14 .31 . 0157 .0156 Dung mã Huffman kết hợp mã đều để mã hóa nguồn tin trên với cơ số mã m=2 Bài giải: P(ui) .5 Sơ đồ mã hóa Từ mã 0 27 11/13/2011 ĐẶNG QUANG HUY - D09VTH2 GVHD: NGUYỄN THỊ LAN ANH .25 10 .315 11000 .31 11001 .31 11010 .31 11011 . 0157 111000 . 0157 111001 . 0157 111010 . 0157 111011 . 0157 111100 . 0157 111101 . 0157 111110 .0156 111111 Chương IV : MÃ CHỒNG NHIỄU: MÃ KHỐI Bài 3 : ma trận Sinh của bộ mã tuyến tính (7,3) trên đường GF (2) là : a.Biểu diễn G dưới dạng chuẩn Gch b.Xác định ma trận thử Hch c. Liệt kê các từ mã có được từ G và Gch d. Xác định khoảng cách Hamming của bộ mã này 28 11/13/2011 ĐẶNG QUANG HUY - D09VTH2 GVHD: NGUYỄN THỊ LAN ANH bài giải: a.Lấy cột 7 làm cột 1,cột 1 làm cột 3 ta có ma trận Sinh Gch: b.Ta có :Hch [-PTIn-k] = c.Liệt kê các từ mã của G và Gch: Vector mang tin a V=a.G w(v) v’=a.Gch W(v’) 000 0000000 0 0000000 0 001 1011100 4 0011110 4 010 0101110 4 0100111 4 011 1110010 4 0111001 4 100 0010111 4 1001011 4 101 1001011 4 1010101 4 110 0111001 4 1101100 4 29 11/13/2011 ĐẶNG QUANG HUY - D09VTH2 111 1100101 GVHD: NGUYỄN THỊ LAN ANH 4 1110010 4
Chương 5 : MÃ VÒNG Bài 1: chứng minh rằng đa thức sinh g(x) của 1 bộ mã vòng là ước số của xn+1 Bài giải: Giả sử cũng là 1 đa thức mã.Khi đó: Và Từ đây : Hay Tức là (đpcm) Bài 5 : chứng minh rằng trong 1 bộ mã vòng khi mẫu sai E(x) có thể dò được thì mẫu sai E(i)(x) chuyển dịch vòng i bit so với E(x) cũng có thể dò được Bài giải: Ta chứng minh bằng phản chứng. Nếu E(i)(x) là 1 mẫu sai không phát hiện được thì E(i)(x) là 1 từ mã. Từ đây theo định nghĩa của mã vòng thì E(x) cũng là 1 từ mã. Khi đó vì mã vòng là mã tuyến tính nên 1 từ mã v(x) bất kỳ sau khi chịu tác động sai của E(x) sẽ biến thành 1 từ mã v’(x) và không phát hiện sai được. Điều nay mẫu thuẫn với giả thiết là E(x) là mẫu sai phát hiện được. BÀI TẬP LÝ THUYẾT THÔNG TIN 30 11/13/2011 ĐẶNG QUANG HUY - D09VTH2 GVHD: NGUYỄN THỊ LAN ANH Bài tập: Xem các con bài của bộ bài 52 lá tạo thành một nguồn tin rời rạc. Tính entropy của một lá bài rút ngẫu nhiên. Giả sử bỏ qua nước của con bài để bây giờ U={Ace,2,3,4,5,6,7,8,9,10, Jack, Queen, King}. Tính entropy của một lá bài rút ngẫu nhiên trong trường hợp này, trong trường hợp U={bài có hình, bài không có hình} Giải: Câu a: H(U)= với \= (i= 1,2,…,52) với \= (i= 1,2,…,13) \= =-52 = 52 \=5.7 Câu b: H(U)= = =-13 31 11/13/2011 ĐẶNG QUANG HUY - D09VTH2 \= GVHD: NGUYỄN THỊ LAN ANH 13 \=3.7 Câu c: Gọi Gọi Vậy: \= là tin bài không có hình H(U) = \= + \= = = 0.779 CHƯƠNG III: MÃ THỐNG KÊ TỐI ƯU Bài tập: Lập một bộ mã cho nguồn tin U có sơ đồ thống kê: 0.34 0.2 0.19 0.1 0.07 0.04 0.03 0.02 0.01 32 11/13/2011 ĐẶNG QUANG HUY - D09VTH2 GVHD: NGUYỄN THỊ LAN ANH Bằng mã nhị phân (m=2)theo phương pháp Fano. Tính độ dài trung bình của từ mã ntbvà tính kinh tế của từ mã: =H(U) Giải: Sơ đồ mã hóa theo phương pháp mã hóa shannon: 0.34 0.2 0.19 0.1 0.07 0.04 0.03 0.02 0.01 0 0 1 1 1 1 1 1 1 0 1 0 0 1 1 1 1 1 0 1 0 1 1 1 1 0 1 1 1 0 1 1 Độ dài trung bình tư mã: Entropy của tập tin: Chỉ số kinh tế của bộ mã: 0 1 Từ mã 00 01 100 101 110 1110 11110 111110 111111 2 2 3 3 3 4 5 6 6 \= H(U)= \= \=2.5664 \= 0.9685 33 11/13/2011 ĐẶNG QUANG HUY - D09VTH2 GVHD: NGUYỄN THỊ LAN ANH CHƯƠNG IV: MÃ CHỐNG NHIỄU – MÃ KHỐI Bài tập: Một không gian vector được tạo bởi mọi tổ hợp tuyến tính của tập hợp các vector: = 1101000 = 0110100 = 0100011 = 1110010 = 1010001 a. Các vector b có độc lập tuyến tính không? b. Tìm số chiều và cơ hệ của không gian vector này Giải: Câu a: Các vector phụ thuộc tuyến tính vì: =0 34 11/13/2011 ĐẶNG QUANG HUY - D09VTH2 GVHD: NGUYỄN THỊ LAN ANH Câu b: Gọi là hệ số Giả sử tồn tại sao cho: =0 1101000)+ (0110100)+
(1110010) = (0000000) \=0 =0 =0 =0 =0 =0 =0 = \= Vậy \= \=0 độc lập tuyến tính, có thể biểu diễn tuyến tính theo nên không gian vector có 4 chiều và một cơ hệ của nó là 35 11/13/2011 ĐẶNG QUANG HUY - D09VTH2 . CHƯƠNG V: MÃ VÒNG Bài tập:Xét bộ mã vọng (7,3) có đa thức sinh g(x)= 1+ + + . Cho v = (0011101) là một từ mã của bộ mã (7,3). Tìm tất cả các từ mã bằng cách dùng đẳng thức sau: [v(i)T]=S[v(i-1)]T, i= 1,n-1 Với v(k) là từ mã thứ k và: S= Giải: 36 11/13/2011 ĐẶNG QUANG HUY - D09VTH2 GVHD: NGUYỄN THỊ LAN ANH Trước hết đặt : v(1)= (0011101) [v(2)]T= [v(1)]T \= \= Vậy v(2)= (1001110). Tương tự ta xác định được: v(3)= (0100111) 37 11/13/2011 ĐẶNG QUANG HUY - D09VTH2 GVHD: NGUYỄN THỊ LAN ANH v(4)= (1010011) v(5)= (1101001) v(7)= (1110100) v(8)= (0111010) Cuối cùng bộ mã có từ mã tầm thường: v(0)= (0000000) 38 11/13/2011 ĐẶNG QUANG HUY - D09VTH2 GVHD: NGUYỄN THỊ LAN ANH 39 11/13/2011 ĐẶNG QUANG HUY - D09VTH2 GVHD: NGUYỄN THỊ LAN ANH BÀI TẬP LÝ THUYẾT THÔNG TIN Chương II: LƯỢNG TIN Chương III: MÃ THỐNG KÊ TỐI ƯU Bài tập: Lập một bộ mã cho nguồn tin u có sơ đồ thống kê như sau. Ui U1 U2 U3 U4 U5 U6 U7 U8 U9 P(u) 0.34 0.2 0.19 0.1 0.07 0.04 0.03 0.02 0.01 Bằng mã nhị phân (m=2)theo phương pháp shannon. Tính độ dài trung bình của từ mã ntb và tính kinh tế của từ mã: p=H(U)/Ntb. Giải Sơ đồ mã hóa theo phương pháp mã hóa shannon: Ui U1 U2 U3 U4 U5 U6 U7 U8 U9 P(ui) 0.34 0.2 0.19 0.1 0.07 0.04 0.03 0.02 0.01 Pi 0 0.34 0.54 0.73 0.83 0.9 0.94 0.97 0.99 ni 2 3 3 4 4 5 6 6 7 Dạng mã nhị phân của pi 0 0.01010111 0.10001010 0.10111010 0.11010100 0.11100110 0.11110000 0.11111000 0.11111101 Từ mã 00 010 100 1011 1101 11100 111100 111110 1111110 Độ dài trung bình từ mã: NTB= Entropy của tập tin: H(u)= Chỉ số kinh tế của bộ mã: p= \=0,8279 __________________________________________________________________ Chương IV: MÃ CHỐNG NHIỄU: MÃ KHỐI __________________________________________________________________ 40 11/13/2011 ĐẶNG QUANG HUY - D09VTH2 GVHD: NGUYỄN THỊ LAN ANH Chương V: MÃ VÒNG BÀI TẬP LÝ THUYẾT THÔNG TIN Chương 2 lượng tin Chương 3:Mã thống kê tối ưu: Bài tập: Lập một bộ mã cho nguồn tin u có sơ đồ thống kê như sau. Ui U1 U2 U3 U4 U5 U6 U7 U8 U9 P(u) 0.34 0.2 0.19 0.1 0.07 0.04 0.03 0.02 0.01 Bằng mã nhị phân (m=2)theo phương pháp shannon. Tính độ dài trung bình của từ mã ntbvà tính kinh tế của từ mã:p=H(U)/Ntb Giải Sơ đồ mã hóa theo phương pháp mã hóa shannon: Ui U1 U2 U3 U4 U5 U6 U7 U8 U9 P(ui) 0.34 0.2 0.19 0.1 0.07 0.04 0.03 0.02 0.01 Pi 0 0.34 0.54 0.73 0.83 0.9 0.94 0.97 0.99 ni 2 3 3 4 4 5 6 6 7 Dạng mạ nhị phân của pi 0 0.01010111 0.10001010 0.10111010 0.11010100 0.11100110 0.11110000 0.11111000 0.11111101 Từ mã 00 010 100 1011 1101 11100 111100 111110 1111110 Độ dài trung bình tư mã:NTB= Entropy của tập tin:H(u)= Chỉ số kinh tế của bộ mã:p= \=0,8279 41 11/13/2011 ĐẶNG QUANG HUY - D09VTH2 GVHD: NGUYỄN THỊ LAN ANH Chương 4:mã chống nhiếu:mã khối Bài tập ma trận sinh của bộ mã tuyến tính (6,3)có dạng chuẩ1n là a.tìm ma trận thử hch của bộ mã. b.liệt kê tất cả các từ mã của bộ mã trên và xác định khoảng cách hamming của bộ mã. c.xác định hàm cấu trúc trọng số mã A(z) và xác định hàm số cấu trủ trọng số mã của bộ mã trực giao sinh ra từ ma trận HCH làB (z) bằng hai phương pháp:trực tiếp và gian tiếp qua A(z). d.lập bảng sắp chuẩncủa bộ mã này với chú ý rằng bảng có chứa mấu sai 2 bít và tính syndrome của tất cả các mẫu sai có thể sửa sai được. e,thiết lập mạch mã hõa,mạch tinhsyndrome và mạch sửa sai của bộ mã. GIẢI a Hch=(-pT,IN-K)= HTch= b liệt kê các từ mã: Vector mang tin a V= aGch W(v) 000 000 000 0 001 001 010 2 010 010 111 4 011 011 101 4 100 100 100 2 101 101 110 4 110 110 011 4 111 111 001 4 Vậy khoảng cách hamming của bộ mã D=2 là trọng số hamming nhở nhất của các từ mã khác không. C: Dựa vào bảng liệt kê ta có: A(z)=1+2z2=5z4 Xác định trực tiếp b(z): Ta liẹt kê các tu8ừ mã của5 bộ mã sinh ra bởi hch Vector mang tin a 000 001 010 011 V= aGch 000 000 010 001 011 010 001 011 W(v) 0 2 3 3 42 11/13/2011 ĐẶNG QUANG HUY - D09VTH2 100 101 110 111 GVHD: NGUYỄN THỊ LAN ANH 110 100 101 111 100 101 110 111 3 3 4 6 Vậy B(z)=1+z2+4z3+z4+z6 Chương 5:mã vòng: Bài tập:cho mã vòng (n,k)=(7,4)có ma trận sinh là g(x)=x3+x+1. Liệt kê tất cả các từ mã của bộ mã và cho biết bộ mã có khả năng sửa sai bao nhiêu bít. GIẢI A.cho d= (0001) tatính được: V1=0001000+dư số V1=0001000+011=0001011 Quay vòng từ mãv1 ta sẽ đượcthêm 6 từ mã nữa: V2=1000101 V3=1100010 V4=0110001 V5=1011000 V6=0101100 V7=0010110 Cho d=(0011)ta tính được: Vδ=0011000+dư số Vδ=0011000+101=00111101 Quay vòng từ mã vδ ta sẽ đượcthêm 6 từ mã nữa: V9 =1001110 V10 =0100111 V11=1010011 V13 =1110100 V14=0111010 Cho d=(1111000) ta tinh được: V15=1111000+dư sô V15=1111000+111=1111111 Cho d=(0000) ta tính được: 43 11/13/2011 ĐẶNG QUANG HUY - D09VTH2 GVHD: NGUYỄN THỊ LAN ANH V0=0000000+dư số b,ta có thể tính rễ ràng trọng số hamming của bộ mã là trọng số nhở nhất của từ mã khác không : H(V)=3 nên bộ mã có khả năng sửa được tất các mẫu sai 1bít BÀI TẬP LÝ THUYẾT THÔNG TIN BÀI TẬP LÝ THUYẾT THÔNG TIN Chương 5: Mã Vons Đa thức sinh của bộ am vòng hamming là: g(x)=1+x3+x4 g. Tìm đa thức thử h(x) của bộ am này. h. Thiết kế mạch am hóa thực hiện qua h(x). i. Xác định các bit thử và từ am nhận được tương ứng với chuỗi bit mang tin d=(10000001011). Giải
44 11/13/2011 ĐẶNG QUANG HUY - D09VTH2 GVHD: NGUYỄN THỊ LAN ANH n=2n-k-1=24-1=15. h(x)=(xn+1)/g(x) Từ công thức: Ta tính được: h(x)=
thì: v(x)=d(x).xn-k+ dư số của = + số dư của \=( ) Trong đó x3+1 tương ứng với chuỗi bit 1001 là các bit thử và từ am nhận được tương ứng với v(x)= ( ) là v=(100000101110010). BÀI TẬP MÔN LÝ THUYẾT THÔNG TIN CHƯƠNG 1: LƯỢNG TIN BÀI TẬP LÝ THUYẾT THÔNG TIN Chương 3: Mã Thống Kê Tối Ưu Lập một bộ mã cho nguồn tin U có sơ đồ thống kê như sau: ui u1 u2 u3 u4 u5 u6 u7 u8 u9 P(ui) 0.34 0.2 0.19 0.1 0.07 0.04 0.03 0.02 0.01 Bằng mã nhị phân (m=2) theo phương pháp shannon. Tính độ dài trung bình của từ mã ntbvà tính kinh tế của từ mã: p=H(U)/ntb Giải 45 11/13/2011 ĐẶNG QUANG HUY - D09VTH2 GVHD: NGUYỄN THỊ LAN ANH Sơ đồ mã hóa theo phương pháp mã hóa shannon: ui p(ui) Pi ni Dạng mạ nhị phân của Pi u1 0.34 0 2 0 u2 0.2 0.34 3 0.01010111 u3 0.19 0.54 3 0.10001010 u4 0.1 0.73 4 0.10111010 u5 0.07 0.83 4 0.11010100 u6 0.04 0.9 5 0.11100110 u7 0.03 0.94 6 0.11110000 u8 0.02 0.97 6 0.11111000 u9 0.01 0.99 7 0.11111101 Từ mã 00 010 100 1011 1101 11100 111100 111110 1111110 Chọn ni thỏa điều kiện 2-ni I(a) = - log(0.125)/log(2) 46 11/13/2011 ĐẶNG QUANG HUY - D09VTH2 GVHD: NGUYỄN THỊ LAN ANH \=3 I(a;b) = I (a) – I(a/b) = -log p(u3) + log p( u3/ u3,u4,u5,u6) = 3 + log 2 0.125/0.125*4 >> I= 3+log(0.125/4/0.125)/log(2) =1 I(a;c) = I (a) – I(a/c) = -log p(u3) + log p( u3/ u3,u4) = 3 + log 2 0.125/0.125*2 >> I= 3+log(0.125/2/0.125)/log(2) =2 Chương 2 : Mã hóa nguồn tin Bài 5 / tr Lập một bộ mã cho nguồn tin U có sơ đồ thống kê như sau: ui U1 U2 U3 U4 U5 U6 U7 U8 U9 P(ui) 0.34 0.2 0.19 0.1 0.07 0.04 0.03 0.02 0.01 Bằng mã nhị phân (m=2) theo phương pháp Fano . Tính độ dài trung bình của từ mã ntb và tính kinh tế của từ mã p=H(u)/ ntb Giải 47 11/13/2011 ĐẶNG QUANG HUY - D09VTH2 Ui P(ui) Lần 1 Lần 2 U1 0.34 0 U2 0.2 U3 GVHD: NGUYỄN THỊ LAN ANH Lần 3 Lần 4 Lần 5 Lần 6 ni Từ mã 0 2 00 0 1 2 01 0.19 1 0 0 3 100 U4 0.1 1 0 1 3 101 U5 0.07 1 1 0 3 110 U6 0.04 1 1 1 0 4 1110 U7 0.03 1 1 1 1 0 5 11110 U8 0.02 1 1 1 1 1 0 6 111110 U9 0.01 1 1 1 1 1 1 6 111111 Độ dài trung bình của từ mã ntb là: ntb = ∑ ni pi = (0.34*2) + (0.2*2) + (0.19*3) + (0.1*3) + (0.07*3) +(0.04*4) +(0.03*5) +(0.02*6) + (0.01*6) = 2.65 H(u) = - ∑ pi log2 pi = - [ (0.34*log2 0.34)+(0.2*log2 0.2)+(0.19*log2 0.19)+(0.1*log2 0.1)+(0.07*log2 0.07)+(0.04*log2 0.04)+(0.03*log2 0.03)+(0.02*log2 0.03)+(0.01*log2 0.01) ] H(u) = 2.5664 Chỉ số kinh tế của bộ mã : p = H(u) / ntb = 2.5664 / 2.65 = 0.9684 Chương 3 : Mã hóa kênh truyền ( mã khối Hamming) Bài 2 / tr Cho ma trân sinh của bộ mã tuyến tính C (6,3) trên trường Galois G=0 1 1 0 1 0 48 11/13/2011 ĐẶNG QUANG HUY - D09VTH2 1 1 0 0 0 1 1 1 0 1 1 0 GVHD: NGUYỄN THỊ LAN ANH Tính Gch Có bao nhiêu từ mã có trọng số Hamming 0,1,2,3,4,5,6,7 Giải Lấy cột 3 làm cột 1, cột 6 làm cột 2 và cột 4 làm cột 3 ta có ma trận sinh Gch như sau : Gch = 1 0 0 0 1 1 0 1 0 1 1 0 0 0 1 1 1 1 Liệt kê các từ mã có được từ ma trận sinh G và ma trận sinh chuẩn tắc Gch Vector mang tin a V=aG W(v) V’ = a Gch W(v’) 000 000000 0 000000 0 001 110110 4 001111 4 010 110001 3 010110 3 011 000111 3 011001 3 100 011010 3 100011 3 101 101100 3 101100 3 110 101011 4 110101 4 111 011101 4 111010 4 Vậy bộ mã có 1 từ mã có trọng số là 0 0 từ mã có trọng số là 1 0 từ mã có trọng số là 2 4 từ mã có trọng số là 3 49 11/13/2011 ĐẶNG QUANG HUY - D09VTH2 GVHD: NGUYỄN THỊ LAN ANH 3 từ mã có trọng số là 4 0 từ mã có trọng số là 5 0 từ mã có trọng số là 6 0 từ mã có trọng số là 7 Chương 3 : Mã vòng Bài 2 / tr Cho bộ mã vòng (7,4) có đa thức sinh là : G(x) = x3+x2+1 a. Tìm đa thức thử h(x) của bộ mã này b. Giả sử nhận được tổ hợp u(x) = x6+x5+x2+1 . Xác định đa thức syndrome của u(x) Giải a.Ta có công thức h(x) = xn+1 / g(x) và ta tính được h(x) = x7+1 / x3+x2+1 = x4+ x3+x2+1 vậy h(x) = x4+ x3+x2+1 b.Già sử nhận được đa thức u(x) = x6+x5+x2+1 , khi đó đa thức syndrome của nó : Su(x) = số dư của ( u(x) / g(x) ) = số dư của (x6+x5+x2+1 / x3+x2+1) = 0 Vậy đa thức syndrome của u(x) là su(x) = 0 50 11/13/2011 ĐẶNG QUANG HUY - D09VTH2 GVHD: NGUYỄN THỊ LAN ANH BÀI TẬP LÝ THUYẾT THÔNG TIN Chương 1 : Tin và lượng tin Bài 2.9 / tr 36 Cho tập tin U={ ui } với ui=xiyizi ( i = 1,2,3,4,5) i Ui P(ui) 1 010 0.25 2 011 0.25 3 100 0.125 4 101 0.125 5 110 0.125 6 111 0.125 Gọi tin a là tin ui= u3 = 100, gọi tin b là tin xi=1 ,gọi tin c là tin yi=0 . Tính I(a) , I(a;b) , I(a;c) Giải I(a) = - log 2 0.125 >> I(a) = - log(0.125)/log(2) =3 I(a;b) = I (a) – I(a/b) 51 11/13/2011 ĐẶNG QUANG HUY - D09VTH2 GVHD: NGUYỄN THỊ LAN ANH \= -log p(u3) + log p( u3/ u3,u4,u5,u6) = 3 + log 2 0.125/0.125*4 >> I= 3+log(0.125/4/0.125)/log(2) =1 I(a;c) = I (a) – I(a/c) = -log p(u3) + log p( u3/ u3,u4) = 3 + log 2 0.125/0.125*2 >> I= 3+log(0.125/2/0.125)/log(2) =2 Chương 2 : Mã hóa nguồn tin Bài 5 / tr Lập một bộ mã cho nguồn tin U có sơ đồ thống kê như sau: ui U1 U2 U3 U4 U5 U6 U7 U8 U9 P(ui) 0.34 0.2 0.19 0.1 0.07 0.04 0.03 0.02 0.01 Bằng mã nhị phân (m=2) theo phương pháp Fano . Tính độ dài trung bình của từ mã ntb và tính kinh tế của từ mã p=H(u)/ ntb Giải 52 11/13/2011 ĐẶNG QUANG HUY - D09VTH2 Ui P(ui) Lần 1 Lần 2 U1 0.34 0 U2 0.2 U3 GVHD: NGUYỄN THỊ LAN ANH Lần 3 Lần 4 Lần 5 Lần 6 ni Từ mã 0 2 00 0 1 2 01 0.19 1 0 0 3 100 U4 0.1 1 0 1 3 101 U5 0.07 1 1 0 3 110 U6 0.04 1 1 1 0 4 1110 U7 0.03 1 1 1 1 0 5 11110 U8 0.02 1 1 1 1 1 0 6 111110 U9 0.01 1 1 1 1 1 1 6 111111 Độ dài trung bình của từ mã ntb là: ntb = ∑ ni pi = (0.34*2) + (0.2*2) + (0.19*3) + (0.1*3) + (0.07*3) +(0.04*4) +(0.03*5) +(0.02*6) + (0.01*6) = 2.65 H(u) = - ∑ pi log2 pi = - [ (0.34*log2 0.34)+(0.2*log2 0.2)+(0.19*log2 0.19)+(0.1*log2 0.1)+(0.07*log2 0.07)+(0.04*log2 0.04)+(0.03*log2 0.03)+(0.02*log2 0.03)+(0.01*log2 0.01) ] H(u) = 2.5664 Chỉ số kinh tế của bộ mã : p = H(u) / ntb = 2.5664 / 2.65 = 0.9684 Chương 3 : Mã hóa kênh truyền ( mã khối Hamming) Bài 2 / tr Cho ma trân sinh của bộ mã tuyến tính C (6,3) trên trường Galois G=0 1 1 0 1 0 53 11/13/2011 ĐẶNG QUANG HUY - D09VTH2 1 1 0 0 0 1 1 1 0 1 1 0 GVHD: NGUYỄN THỊ LAN ANH Tính Gch Có bao nhiêu từ mã có trọng số Hamming 0,1,2,3,4,5,6,7 Giải Lấy cột 3 làm cột 1, cột 6 làm cột 2 và cột 4 làm cột 3 ta có ma trận sinh Gch như sau : Gch = 1 0 0 0 1 1 0 1 0 1 1 0 0 0 1 1 1 1 Liệt kê các từ mã có được từ ma trận sinh G và ma trận sinh chuẩn tắc Gch Vector mang tin a V=aG W(v) V’ = a Gch W(v’) 000 000000 0 000000 0 001 110110 4 001111 4 010 110001 3 010110 3 011 000111 3 011001 3 100 011010 3 100011 3 101 101100 3 101100 3 110 101011 4 110101 4 111 011101 4 111010 4 Vậy bộ mã có 1 từ mã có trọng số là 0 0 từ mã có trọng số là 1 0 từ mã có trọng số là 2 4 từ mã có trọng số là 3 54 11/13/2011 ĐẶNG QUANG HUY - D09VTH2 GVHD: NGUYỄN THỊ LAN ANH 3 từ mã có trọng số là 4 0 từ mã có trọng số là 5 0 từ mã có trọng số là 6 0 từ mã có trọng số là 7 Chương 3 : Mã vòng Bài 2 / tr Cho bộ mã vòng (7,4) có đa thức sinh là : G(x) = x3+x2+1 c. Tìm đa thức thử h(x) của bộ mã này d. Giả sử nhận được tổ hợp u(x) = x6+x5+x2+1 . Xác định đa thức syndrome của u(x) Giải a.Ta có công thức h(x) = xn+1 / g(x) và ta tính được h(x) = x7+1 / x3+x2+1 = x4+ x3+x2+1 vậy h(x) = x4+ x3+x2+1 b.Già sử nhận được đa thức u(x) = x6+x5+x2+1 , khi đó đa thức syndrome của nó : Su(x) = số dư của ( u(x) / g(x) ) = số dư của (x6+x5+x2+1 / x3+x2+1) = 0 Vậy đa thức syndrome của u(x) là su(x) = 0 55 11/13/2011 ĐẶNG QUANG HUY - D09VTH2 GVHD: NGUYỄN THỊ LAN ANH BÀI TẬP LÝ THUYẾT THÔNG TIN Chương II: LƯỢNG TIN Bài tập: Giả sử có một nguồn tin rời rạc với xác suất xuất hiện p khi u thuộc U, với mỗi tin u, chọn một từ mã có dộ dài 1(u) thỏa: Log(1/p(u)) j và dĩ nhiên n > i > j.Vậy: vi(x)= vixn-i + vjxn-j = xn-i + xn-j : g(x) xn-i (xi-j + 1) : g(x) Hay: Từ đây: xi-j + 1 : g(x) trong khi i-j < n mâu thuẫn với giả thiết ban đầu n là số nhỏ nhất sao cho xn + 1 : g(x). Vậy trọng số Hamming của bộ mã phải luôn lớn hơn hoặc bằng 3. |
