Bài tập và góp ý giải môn lý thuyết thông tin

1 đáp án Ngành đào tạo: Điện tử – viễn thông Hệ đào tạo : Đại học Môn học : Lý thuyết thông tin Mã số 411 LTT 340A Số ĐVHT: 4 Phần 1: lý thuyết thông tin Câu 1: (1 điểm): Định nghĩa l−ợng thông tin riêng (độ bất định) của một biến ngẫu nhiên. Xác định các đơn vị đo - Định nghĩa l−ợng thông tin riêng (độ bất định) L−ợng thông tin riêng là độ bất định tiềm năng chứa trong một biến cố ngẫu nhiên kx . Ký hiệu ( )kI x ( ) ( )k kI k ln px x= - Các đơn vị đo k 1= − ( ) ( )k kI ln px x= − (nat) 1k ln 2 = − ( ) ( )k 2 kI log px x= − (bít) 1k ln10 = − ( ) ( )k kI lg px x= − (hart) 1 nat = 1,443 bít 1 hart = 3,322 bít Câu 2: (1 điểm) Định nghĩa entropy của nguồn rời rạc Entropy của nguồn tin rời rạc A là trung bình thống kê của l−ợng thông tin riêng của các tin thuộc A Ký hiệu: ( )1H A ( ) ( )1 iH A M I aΔ= ⎡ ⎤⎣ ⎦ ( ) ( ) ( ) 1 2 s 1 2 s a a ... a A p a p a ... p a ⎛ ⎞= ⎜ ⎟⎝ ⎠ ( )i0 p a 1≤ ≤ ( )s i i 1 p a 1 = =∑ ( ) ( ) ( )s '1 i i i 1 H A p a log p a = = −∑ (bít) 2 Câu 3: (1 điểm) Nêu các tính chất của entropy của nguồn rời rạc Các tính chất của ( )1H A - Khi ( )kp a 1= , ( )ip a 0= với i k∀ ≠ thì ( ) ( )1 1 minH A H A 0= = - Một nguồn tin rời rạc gồm s dấu đồng xác suất cho entropy cực đại. Ta có ( )1 maxH A logs= - Entropy của nguồn rời rạc là một đại l−ợng giới nội ( )10 H a logs≤ ≤ Câu 4: (1 điểm) Định nghĩa khả năng thông qua kênh rời rạc, nêu các tính chất? - Định nghĩa: Khả năng thông qua của kênh rời rạc là giá trị cực đại của l−ợng thông tin chéo trung bình truyền qua kênh trong một đơn vị thời gian lấy theo mọi khả năng có thể có của nguồn tin A. ( ) ( )' ' kA AC max I A,B v max I A,B Δ= = (bps) - Các tính chất: + 'C 0≥ 'C 0= khi A và B là độc lập (kênh bị đứt) + ' kC v logs≤ ' kC v logs= khi kênh không nhiễu Câu 5: (2 điểm) Entropy của nguồn rời rạc nhị phân. ý nghĩa của dơn vị đo bít? - Entropy của nguồn rời rạc nhị phân. 1 2a aA p 1 p ⎛ ⎞= ⎜ ⎟−⎝ ⎠ ( ) ( ) ( )1 maxH A plog p 1 p log 1 p= − − − − Khi 1p 1 p 2 = − = ( ) ( )1 1 maxH A H A 1bit= = - ý nghĩa: 1 bít là l−ợng thông tin riêng trung bình chứa trong một biến cố của một nguồn rời rạc 2 phân đồng xác suất. ( )1H A (bits) p 0,5 1 1 3 Câu 6: (2 điểm) Xác định hai trạng thái cực đoan của kênh rời rạc. - Kênh bị đứt: Các nguồn tin A và B ở hai đầu thu và phát là độc lập. ( ) ( )i j ip a b p a= ( ) ( )j i ip b a p a= ( ) ( ) ( )i j i jp a b p a p b= Ta có: ( ) ( )jH A b H A= ( ) ( )H A B H A= Nhận xét: L−ợng thông tin tổn hao trung bình đúng bằng entropy của nguồn. Kênh không thể truyền tin đ−ợc - Kênh không nhiễu: A B≡ ( )k kp a b 1= ( )kH A b 0= ( )H A B 0= Nhận xét: L−ợng thông tin tổn hao trên kênh bằng 0 Câu 7: (2 điểm) Entropy có điều kiện ( )H A B : định nghĩa và nêu các tính chất - Định nghĩa: Entropy có điều kiện về 1 tr−ờng tin A khi đã rõ tr−ờng tin B đ−ợc xác định theo công thức sau: ( ) ( ) ( )s t i j i j i 1 j 1 H A B p a b log p a b = = = −∑∑ - Các tính chất: + ( ) ( ) ( ) ( ) ( )H AB H A H B A H B H A B= + = + + ( ) ( )0 H A B H A≤ ≤ + ( ) ( ) ( )H AB H A H B= + Câu 8: (2 điểm) L−ợng thông tin chéo trung bình truyền qua kênh rời rạc: định nghĩa và tính chất - Định nghĩa: ( ) ( )i jI A,B M I a ,bΔ ⎡ ⎤= ⎣ ⎦ với ( ) ( )( )i ji j i p a b I a ,b log p a = 4 ( ) ( ) ( )( ) s t i j i j i 1 j 1 i p a b I A,B p a b log p a= = =∑∑ ( ) ( ) ( ) ( ) ( )I A,B H A H A B H B H B A= − = − - Tính chất: + ( )I A,B 0≥ + ( ) ( )I A,B H A≤ Câu 9: (3 điểm) Cho kênh đối xứng nhị phân sau ( )1p a p= ( )2 1p a p= − ( ) ( )1 2 2 1 1s dp b a p b a p p= − = − Cho tốc độ truyền tin của kênh 1kv T= Tính khả năng thông qua 'C của kênh này. Giải: Ta có ( ) ( ) ( )' A A 1 1C max I A,B max H B H B A T T = = −⎡ ⎤⎣ ⎦ Trong đó: ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) 2 t i j i j i i 1 j 1 1 1 1 1 1 2 1 2 1 2 1 2 1 2 2 2 2 2 s s s s s s s s s s s s H B A p a p b a log p b a p a p b a log p b a p b a log p b a p a p b a log p b a p b a log p b a p 1 p log 1 p p log p 1 p p log p 1 p log 1 p p log p 1 p log 1 p = = = − = − + −⎡ ⎤⎣ ⎦ − +⎡ ⎤⎣ ⎦ = − − − + − − + − −⎡ ⎤ ⎡ ⎤⎣ ⎦ ⎣ ⎦ = − + − −⎡ ⎤⎣ ⎦ ∑∑ Ta thấy ( )H B A không phụ thuộc vào xác suất tiên nghiệm của các tin thuộc nguồn A. Do đó: ( ) ( )' A 1 1C max H B H B A T T = − Ta có ( ) ( )maxAmax H B H B log 2 1bit= = = ' max 1C T = khi sp 0= (kênh không nhiễu) ( ) ( )' s s s s' max C 1 p log p 1 p log 1 p C = + + − − 2b 1b 2a 1a sp sp ( )2 1 dp b a p= ( )1 2 dp b a p= A B ' ' maxC C sp 0,5 1 1 5 Câu 10: (3 điểm) A chọn ngẫu nhiên một trong các số từ 0 đến 7. Tính 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. Nêu thuật toán hỏi? Giả sử A đã chọn số 3, hãy đặt các câu hỏi cần thiết? Độ bất định của số đ−ợc chọn ngẫu nhiên: ( ) ( )i i 1I a log p a log 3bit8= − = − = Để tìm đ−ợc số đã chọn của A, B phải đặt các câu hỏi cho A để thu đ−ợc đủ một l−ợng thông tin cần thiết là 3 bít. Mỗi câu hỏi của B (dạng lựa chọn) có thể xem là nguồn rời rạc nhị phân, bởi vậy l−ợng thông tin nhận đ−ợc sau mỗi câu trả lời t−ơng ứng là: ( ) ( ) ( )H B plog p 1 p log 1 p= − − − − Với p : xác suất nhận câu trả lời ″đúng ″ 1 p− : xác suất nhận câu trả lời ″sai″ Vậy số câu hỏi cần thiết n là : ( ) ( )i I a n H B = Số câu hỏi trung bình tối thiểu là: ( ) ( )imin max I a n H B = ( )maxH B khi 1p 1 p 2= − = min 3bitn 3 1bit = = lần hỏi Giả sử A chọn số B. Các câu hỏi b có thể đặt cho A là: - Câu 1 - Số A chọn lớn hơn 3? Trả lời: Sai - Câu 2 - Số A chọn lớn hơn 1? Trả lời: Đúng - Câu 3 - Số A chọn lớn hơn 2? Trả lời: Sai Vậy số A chọn là 3 Câu 11: (4 điểm) Một thiết bị vô tuyến điện gồm 16 khối có độ tin cậy nh− nhau và đ−ợc mắc nối tiếp. Ta sử dụng một thiết bị đo để đo tín hiệu ra của các khối. Giả sử có một khối nào đó bị hỏng. Hãy tính số lần đo trung bình tối thiểu để tìm đ−ợc khối bị hỏng. Nêu thuật toán đo? Giả sử khối hỏng là khối thứ 6, tìm vị trí các điểm đo cần thiết? Theo giả thiết độ bất định của khối hỏng là: ( ) ( )i i 1I a log p a log 4bit16= − = − = L−ợng thông tin nhận đ−ợc sau mỗi phép đo: ( ) ( ) ( )H B plog p 1 p log 1 p= − − − − 6 Với p : xác suất có tín hiệu 1 p− : xác suất không có tín hiệu Để xác định đ−ợc khối hỏng (khử hết độ bất định) số phép đo cần thiết n là: ( ) ( )imin max I a n H B = ( )H B max→ khi 1p 1 p 2 = − = ( )maxH B 1bit= min 4bitn 4 1bit = = lần đo Để nmin thuật toán đo phải đảm bảo ( )H B max→ ⇒ Mỗi lần đo phải đo ở điểm giữa của các khối cần xác định nhằm đảm bảo 1p 1 p 2 = − = . Giả sử khối hỏng là khối 6. Các phép đo cần thiết là: - Lần 1: Đo ở đầu ra khối 8: Không có tín hiệu, khối hỏng nằm trong các khối từ 1 → 8. - Lần 2: Đo ở đầu ra khối 4: Không có tín hiệu, khối hỏng nằm trong các khối từ 5 → 8. - Lần 3: Đo ở đầu ra khối 6: Không có tín hiệu, khối hỏng nằm trong khối 5 hoặc 6. - Lần 4: Đo ở đầu ra khối 5: Có tín hiệu. Vậy khối hỏng là khối 6 Câu 12: (4 điểm) Trong bộ tú lơ khơ 52 quân (không kể făng teo), A rút ra một quân bài bất kỳ. Tính số câu hỏi trung bình tối tiểu mà B cần đặt cho A để xác định đ−ợc quân bài mà A đã rút. Nêu thuật toán hỏi? Giả sử A rút ra 7 quân rô, hãy nêu các câu hỏi cần thiết? Độ bất định về quân bài mà A đã rút: ( ) ( )i i 1I a log p a log 6bit52= − = − < Giả sử B đặt cho A câu hỏi dạng lựa chọn, khi đó l−ợng thông tin nhận đ−ợc sau mỗi câu trả lời của A là: ( ) ( ) ( )H B plog p 1 p log 1 p= − − − − Với p : xác suất nhận câu trả lời là ″đúng ″ 1 p− : xác suất nhận câu trả lời là ″sai″ Số câu hỏi cần thiết để xác định đ−ợc quân bài A đã rút là: ( ) ( )i I a n H B = 7 Ta thấy n min→ khi ( )H B max→ ( ) ( )maxH B H B 1bit= = khi 1p 1 p 2= − = Số câu hỏi trung bình tối thiểu là: min log52 bitn 6 1bit = < lần Thuật toán phải đảm bảo 1p 1 p 2 = − = . Giả sử A rút ra 7 rô. Các câu hỏi cần thiết có thể nh− sau: - Câu 1: Quân A rút là quân đỏ? Đúng - Câu 2: Quân A rút là quân cơ? Sai - Câu 3: Quân A rút có giá trị ≤ 7? Đúng (giả sử J = 11, Q = 12, K = 13, At=1) - Câu 4: Quân A rút có giá trị ≤ 3? Sai - Câu 5: Quân A rút có giá trị ≤ 5? Sai - Câu 6: Quân A rút là 6 rô? Sai Vậy quân A rút là 7 rô Câu 13 :(4 điểm) 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 cân đĩa thăng bằng. Hãy tính số lần cân trung bình tối thiểu để xác định đ−ợc đồng xu giả. Nêu thuật toán cân ? Theo giả thiết độ bất định chứa trong sự kiện đồng xu giả là : I(xi) = - log p(xi) = - log 1/27 = log 27 bit Khi sử dụng cân đĩa thăng bằng, sau mỗi lần cân các sự kiện có thể có là : - Cân thăng bằng với xác suất p - Cân lệch trái với xác suất q - Cân lệch phải với xác suất 1-p-q L−ợng thông tin nhận đ−ợc sau mỗi lần cân : H(B) = -plog p – qlog q – (1-p-q)log (1-p-q) Để xác định đ−ợc đồng xu giả tổng l−ợng thông tin nhận đ−ợc sau các lần cân phải không nhỏ hơn độ bất định của đông xu giả. Nh− vậy số lần cân cần thiết là : n = I(xi)/H(B) Để n có giá trị nhỏ nhất thì H(B) phải đạt giá trị cực đại. Ta có H(B) = H(B)max= log 3 khi p = q = 1-p-q = 1/3. Khi đó nmin= I(xi)/H(B)max = log27/log 3 = 3 lần cân. Thuật toán cân nh− sau( đảm bảo p = q = 1-p-q ) - Lần 1 : Chia 27 đồng xu thành 3 phần, mỗi phần có 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ả 8 nằm trong 9 đồng xu ch−a cân. Ng−ợc lại, tuỳ theo cân lệch trái hay lệch phải ta cũng xác định đ−ợc phần có chứa đồng xu giả. - Lần 2 : Chia 9 đồng 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 2 bàn cân. Kết quả của phép cân sẽ giúp ta xác định đ−ợc 3 đồng xu có chứa đông xu giả. - Lần 3 : Lấy 2 đồng xu bất kỳ trong 3 đồng xu có chứa đồng xu giả đặt lên 2 đĩa cân. Sau lần cân này ta sẽ xác định đ−ợc đồng xu giả. Câu 14 : (2 điểm) Tính entropie của tr−ờng sự kiện đồng thời ? Xét 2 tr−ờng sự kiện A và B sau : ( ) ( )ji i j ba A i 1,0 B j 1, t p a p b ⎧ ⎫⎧ ⎫ ⎪ ⎪= = = =⎨ ⎬ ⎨ ⎬⎩ ⎭ ⎪ ⎪⎩ ⎭ Khi đó, tr−ờng sự kiện đồng thời C A.B= là : ( ) ( )i ji j a b C i, j, i 1,0, j 1, t p a p b ⎧ ⎫⎪ ⎪= ∀ = =⎨ ⎬⎪ ⎪⎩ ⎭ Theo định nghĩa, entropie của tr−ờng sự kiện đồng thời đ−ợc xác định nh− sau : ( ) ( ) ( )s t i j i j i 1 j 1 H C p a b log p a b = = = −∑∑ Câu 15: (2 điểm) Cho kênh nhị phân đối xứng không nhớ sau (hình vẽ). Hãy tính phân bố xác suất của các tin ở đầu ra? Biết rằng p(a1)=p ; p(a2)=1-p. Theo công thức xác suất đầy đủ ta có: ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) 1 1 1 1 2 1 2 2 1 2 1 2 2 2 1 p b p a .p b a p a .p b a p b p a .p b a p a .p b a 1 p b = + = + = − Phần 2: lý thuyết m∙ hoá Câu 1: (1 điểm): Định nghĩa độ dài trung bình của từ mã ? Phát biểu định lý mã hoá thứ nhất của Shannon? Xét phép mã hoá các tin rời rạc sau: ini ia →α A 1a 2b 1b Sp Sp 2a ( )2 1 dp b a p= ( )1 2 dp b a p= B 9 ( ) ( ) in i i i i a A V p a p a ⎛ ⎞⎛ ⎞ α= → = ⎜ ⎟⎜ ⎟ ⎜ ⎟⎝ ⎠ ⎝ ⎠ - Định nghĩa: Độ dài trung bình của từ mã là kỳ vọng của đại l−ợng ngẫu nhiên in ( )s i i i 1 n p a n = =∑ - Định lý mã hoá thứ nhất của Shannon (đối với mã nhị phân) Luôn luôn có thể xây dựng đ−ợc một phép mã hoá các tin rời rạc có hiệu quả mà độ dài trung bình của từ mã có thể nhỏ tuỳ ý, nh−ng không nhỏ hơn entropie xác định bởi các đặc tính thống kê của nguồn ( )1n H A≥ Câu 2: (1 điểm) Nêu nguyên tắc lập mã tiết kiệm? Từ định lý mã hoá thứ 1 của Shannon: ( ) ( ) ( ) ( )s si i 1 i i i 1 i 1 n p a n H A p a log p a = = = ≥ = −∑ ∑ ta có: ( )i i 1n log p a ≥ Nguyên tắc: Các tin có xác suất xuất hiện lớn đ−ợc mã hoá bằng các từ mã có độ dài nhỏ và ng−ợc lại các tin có xác suất xuất hiện nhỏ đ−ợc mã hoá bằng các từ mã có độ dài lớn. Câu3: (1 điểm) Trọng số của từ mã: định nghĩa và tính chất? - Định nghĩa trọng số của từ mã: ( )iniW α Trọng số của 1 từ mã là số các dấu mã khác không chứa trong từ mã - Tính chất: + ( )ini0 W 1≤ α ≤ + ( ) ( )n n n ni j i jW d ,α + α = α α Câu 4: (1 điểm) Nêu các định lý quy định khả năng phát hiện sai và khả năng sửa sai của một bộ mã? - Định lý về khả năng phát hiện sai: Mã đều nhị phân có độ thừa với khoảng cách Hamming 0d 1> có khả năng phát hiện t sai thoả mãn điều kiện 0t d 1≤ − . - Định lý về khả năng sửa sai: 10 Mã đều nhị phân có độ thừa với khoảng cách Hamming 0d 3≥ có khả năng sửa đ−ợc t sai thoả mãn điều kiện: 0 d 1t 2 −⎡ ⎤≤ ⎢ ⎥⎣ ⎦ . Trong đó [ ]x ký hiệu phần nguyên của số x. Câu 5: (2 điểm) Khoảng cách mã: định nghĩa, tính chất? Định nghĩa khoảng cách mã tối thiểu? - Định nghĩa: Khoảng cách giữa hai từ mã niα và njα là số các dấu mã khác nhau về giá trị tính theo cùng một thứ tự giữa 2 từ mã này. Ví dụ: 7i 0 1 1 0 1 0 0α = 7 j 1 0 1 0 0 1 1 * * * * * α = ( )7 7i jd , 5α α = - Tính chất: + ( )n ni jd , 0α α ≥ ( )n ni jd , 0α α = khi n ni jα ≡ α + ( )n ni jd , nα α ≤ + Tính chất tam giác: ( ) ( ) ( )n n n n n ni j j k i kd , d , d ,α α + α α ≥ α α Định nghĩa khoảng cách mã tối thiểu: d0= min d( ai n, aj n) với mọi i,j Câu 6: (2 điểm) Cho mã xyclic ( )V - n - k có đa thức sinh ( ) 3g x =1+ x + x ( )n =7, k = 4 . Hãy thiết lập ma trận sinh và ma trận kiểm tra của mã này? Cho ma trận sinh G. 3 2 4 2 3 5 3 4 6 1 1 0 1 0 0 0x x 0 1 1 0 1 0 0x x x 0 0 1 1 0 1 0x x x 0 0 0 1 1 0 1x x x ⎛ ⎞+ + ⎛ ⎞⎜ ⎟ ⎜ ⎟+ +⎜ ⎟ ⎜ ⎟=⎜ ⎟ ⎜ ⎟+ +⎜ ⎟ ⎜ ⎟⎜ ⎟+ + ⎝ ⎠⎝ ⎠ 1 G = Ma trận kiểm tra H : Ta có : ( ) ( ) 7 4 2x 1 x x x 1 g x += = + + +h x 11 3 7 5 4 4 2 5 4 5 3 2 4 3 2 4 2 3 3 1 x x 1 x x x x x x 1 x x 1 x x x x x x 1 x x x x x 1 x x 1 0 + + + + + + + + + + + + + + + + + + + + + 7 x ( ) ( ) ( ) ( ) ( ) ( ) deg h x* 1 4 3 2 * * r 1 * 2 3 4 3 4 5 2 4 5 6 h X X h X x x x 1 h x x.h x H ........ x .h x 1 x x x 1 011100 H x x x x 01 0111 0 x x x x 001 0111 − − = = + + + ⎛ ⎞⎜ ⎟⎜ ⎟= ⎜ ⎟⎜ ⎟⎜ ⎟⎝ ⎠⎛ ⎞+ + + ⎛ ⎞⎜ ⎟ ⎜ ⎟= + + + =⎜ ⎟ ⎜ ⎟⎜ ⎟⎜ ⎟+ + + ⎝ ⎠⎝ ⎠ Ta có TG.H 0= Câu 7: (2 điểm) hãy thiết lập từ mã hệ thống của bộ mã xyclic (7,4) có đa thức sinh ( ) 3g x =1+ x + x t−ơng ứng với đa thức thông tin ( ) 3a x = x + x . (Sử dụng thuật toán 4 b−ớc). - B−ớc 1: ( ) 3a x = x + x - B−ớc 2: Nâng bậc ( ) ( )3 7 4 6 4x x x x x−= + = +n-ka x x - B−ớc 3: Chia tính d−: ( ) 4 3 6 4 3 3 3 3 x x x 1 x x x x 1 x x x 1 r x x 1 + + + + + + + + = + 6 x - B−ớc 4: Thiết lập từ mã f(x) ( ) ( ) ( ) ( ) n k 6 4 6 6 a x x r x x x x 1 1 1 0 0 1 0 1 x . . . . . . x −= + = + + + ↔ f f x x 12 Câu 8: (2 điểm) Cho phân tích 7x +1 nh− sau ( )( )( )3 2 31 x x 1 x x+ + + +7x +1= 1+ x Hãy nêu tất cả các mã xyclic có thể có trên vành [ ]x 72Z x +1 . TT Đa thức sinh g(x) Mã (n, k) 0d 1 1+ x ( )7,6 2 2 31+ x + x ( )7,4 3 3 2 31+ x + x ( )7,4 3 4 2 41+ x + x + x ( )7,3 4 5 2 3 41+ x + x + x ( )7,3 4 6 ∑6 i i=0 x ( )7,1 7 7 1 ( )7,7 1 Câu 9: (4 điểm) Hãy thực hiện mã hoá Shannon – Fano cho nguồn rời rạc A sau: ⎛ ⎞⎜ ⎟⎜ ⎟⎜ ⎟⎝ ⎠ 1 2 3 4 5 6 7 8 9 10a a a a a a a a a a A = 1 1 1 1 1 1 1 1 1 1 4 4 8 8 8 32 32 32 64 64 Đánh giá hiệu quả của phép mã hoá này? Hãy giải mã cho dãy bít nhận đ−ợc có dạng: 101100111010101… TT ia ( )p ia Từ mã α ini in 1 1a 1 4 0 0 2 2 2a 1 4 0 1 2 3 3a 1 8 1 0 0 3 4 4a 1 8 1 0 1 3 5 5a 1 8 1 1 0 3 6 6a 1 32 1 1 1 0 0 5 7 7a 1 32 1 1 1 0 1 5 8 8a 1 32 1 1 1 1 0 5 9 9a 1 64 1 1 1 1 1 0 6 10 10a 1 64 1 1 1 1 1 1 6 13 - Đánh giá hiệu quả: ( )10 i i i 1 1 1 1 1n p a n 2.2. 3.3. 3.5. 2.6. 4 8 32 64 9 15 6 251 2. 8 32 32 32 = = = + + + = + + + = ∑ dấu ( ) ( ) ( ) 10 1 i i 1 i 1 1 1 1 1H A p a log 2. .log 4 3. log8 3. log32 2. log64 p a 4 8 32 64 252. 32 = = = + + + = ∑ bit ( )1n H A= ⇒ phép mã hoá là tối −u - Giải mã cho dãy bít nhận sau: 4 3 8 4 2 1 0 1 1 0 0 1 1 1 0 1 0 1 0 1 ... a a a a a ↓ ↓ ↓ ↓ ↓ Câu 10: (4 điểm) Giả sử từ mã nhận đ−ợc của mã xyclic (7,3) với đa thức sinh ( ) 2 4g x =1+ x + x + x có dạng sau ( ) 6 5 4 3 2v x = x + x + x + x + x . Hãy sử dụng thuật toán chia dịch vòng để tìm đ−ợc từ mã đã phát, biết rằng mã (7, 3) này có 0d = 4 . - B−ớc 1: Chia v(x) cho g(x) ( ) 5 4 3 2 3 6 4 3 2 2 5 5 3 2 3 2 0 x x x x x x 1 x x x x x x x x x x x r x x x x + + + + + + + + + + + + + = + + 6x - B−ớc 2: ( )( )0 d 1 4 1W r x 3 t 1,52 2− −⎡ ⎤ ⎡ ⎤= > = = =⎢ ⎥ ⎢ ⎥⎣ ⎦ ⎣ ⎦ - B−ớc 3: (lần 1) ( ) 6 5 4 3x.v x x x x x 1= + + + + ( ) 5 4 3 3 6 4 3 2 2 5 2 5 3 2 3 1 x x x 1 x x 1 x x x x x x x x 1 x x x x r x x x 1 + + + + + + + + + + + + + + + = + + 6x ( )( )1W r x 3 t 1= > = ⇒ B−ớc 3 14 - B−ớc 3: (lần 2): ( )2 6 5 4x .v x x x x x 1= + + + + ( ) 5 4 3 6 4 3 2 2 5 3 2 5 3 2 2 x x x 1 x x 1 x x x x x x x x x x 1 x x x x r x 1 + + + + + + + + + + + + + + + + + = 6x ( )( )2W r x 1 t= = - B−ớc 4: ( ) ( ) ( ) ( ) 2 6 5 4^ 2 2 2 ^ 6 4 3 2 * x v x r x x x x xx x x x x x x x 0011101 + + + += = = + + + ↔ f f Sai ở 5x đã đ−ợc sửa Câu 11: (3 điểm) Hãy xác định tập tất cả các từ mã của bộ mã xyclic (7, 3) có đa thức sinh ( ) 2 3 4g x =1+ x + x + x . Cho mã xyclic (7, 3) có ( ) 2 3 4g x = 1+ x + x + x ma trận sinh: 2 3 4 3 4 5 2 4 5 6 1 x x x 1 011100 G x x x x 01 0111 0 x x x x 001 0111 ⎛ ⎞+ + + ⎛ ⎞⎜ ⎟ ⎜ ⎟= + + + =⎜ ⎟ ⎜ ⎟⎜ ⎟⎜ ⎟+ + + ⎝ ⎠⎝ ⎠ Tập 32 8= =k2 từ mã, trong đó 7 từ mã khác không là tập các tổ hợp tuyến tính các hàng của ma trận G ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) 3 4 5 2 2 4 5 6 2 5 2 3 5 6 2 2 3 6 2 4 6 1 0 1 1 1 0 0 xg x x x x x 0 1 0 1 1 1 0 x g x x x x x 0 0 1 0 1 1 1 1 x g x 1 x x x 1 1 1 0 0 1 0 1 x g x 1 x x x 1 0 0 1 0 1 1 x x g x x x x x 0 1 1 1 0 0 1 1 x x g x 1 x x x 1 1 0 0 1 0 1 ↔ = + + + ↔ = + + + ↔ + = + + + ↔ + = + + + ↔ + = + + + ↔ + + = + + + ↔ 2 3 4g x = 1+ x + x + x 15 Câu 12: (3 điểm) Phát biểu và chứng minh giới hạn Hamming? Định nghĩa mã hoàn thiện? - Giới hạn Hamming. Với mã tuyến tính (n, k), điều kiện cần để sử đ−ợc t sai là: t i n k n i 0 C 2 − = ≤∑ Chứng minh: Số các kiểu sai có trọng số i là inC Số các kiểu sai có trọng số ≤ t là: t0 1 t in n n n i 0 C C ... C C = + + + =∑ Số các trạng thái khác nhau của các dấu kiểm tra là: r n k2 2 −= Để sửa đ−ợc sai, mỗi trạng thái của các dấu kiểm tra chỉ đ−ợc gán tối đa cho 1 kiểu sai. Vậy để sửa đ−ợc tất cả các kiểu sai có trọng số ≤ t ta có: t i n kn i 0 C 2 − = ≤∑ - Định nghĩa mã hoàn thiện. Mã hoàn thiện là mã (n, k, d) đạt đ−ợc giới hạn Hamming Ví dụ: Mã (7, 4) có d = 3 Ta có : d 1t 1 2 −⎡ ⎤= =⎢ ⎥⎣ ⎦ 0 1 7 4 3 7 7C C 2 2 8 1 7 8 −+ ≤ = = + = Vậy mã (7, 4) là 1 mã hoàn thiện. Câu 13: (4 điểm) Cho phân tích của x15+1 nh− sau : X15+1=(1+x)(1+x+x2)(1+x+x4)(1+x3+x4)(1+x+x2+x3+x4) Hãy nêu tất cả các mã xyclic có độ dài 15 trên vành Z2[x]/x 15+1? Đặt ( ) ( ) ( ) ( ) 2 1 2 4 3 4 3 4 g X 1 X g X 1 X X g X 1 X X g X 1 X X = + = + + = + + = + + 16 TT Đa thức sinh Mã (n,k) 1 ( )1g X (15,14) 2 ( )2g X (15,13) 3 ( )3g X (15,11) 4 ( )4g X (15,11) 5 ( )5g X (15,11) 6 1 2g .g (15,12) 7 1 3g .g (15,10) 8 1 4g .g (15,10) 9 1 5g .g (15,10) 10 2 3g .g (15,9) 11 ( )2 4g . g (15,9) 12 2 5g .g (15,9) 13 3 4g .g (15,7) 14 3 5g .g (15,7) 15 4 5g .g (15,7) 16 1 2 3g .g .g (15,8) 17 1 2 4g .g .g (15,8) 18 1 2 5g .g .g (15,8) 19 2 3 4g .g .g (15,5) 20 2 3 5g .g .g (15,5) 21 1 3 4g .g .g (15,6) 22 1 3 5g .g .g (15,6) 23 1 4 5g .g .g (15,6) 24 2 4 5g .g .g (15,5) 25 3 4 5g .g .g (15,3) 26 1 2 3 4g .g .g .g (15,4) 27 1 2 3 5g .g .g .g (15,4) 28 1 2 4 5g .g .g .g (15,4) 29 2 3 4 5g .g .g .g (15,1) 30 1 3 4 5g .g .g .g (15,2) 31 1 (15,15) 17 Câu 14:(