Hỏi đáp môn LÝ THUYẾT THÔNG TIN

[09520411]

Chào các bạn. Mình lập ra topic này mục đích là bạn nào có thắc mắc về các câu hỏi ôn tập Lý thuyết thông tin thì mình gửi thắc mắc lên. Mong là sẽ có nhiều bạn vào forum và đóng góp ý kiến cho topic này.
Cảm ơn các bạn

[09520549]

Kí hiệu: n là chiều dài từ mã, k là số bit thông báo, d là khoảng cách Hamming của bộ mã.
Câu 8. Một mã tuyến tính có n = 8 và có d = 2 có tối đa bao nhiêu từ mã
(A). 32 (B). 48 (C). 64 (D). 128 (E). Cả bốn câu trên đều sai
Câu 10. Một mã tuyến tính có k = 8 và có d = 3 có chiều dài tối thiểu là bao nhiêu
(A). 11 (B). 12 (C). 13 (D). 14 (E). Cả bốn câu trên đều sai
Có công thức nào để giải mấy câu tương tự thế này không?

[09520411]

Trước khi mình trả lời cho bạn, bạn có thể xem phần Một số giới hạn của bài 12: Mã khối tuyến tính nhé
Có công thức chặn trên và chặn dưới đó

[09520411]

Kí hiệu: n là chiều dài từ mã, k là số bit thông báo, d là khoảng cách Hamming của bộ mã.
Câu 8. Một mã tuyến tính có n = 8 và có d = 2 có tối đa bao nhiêu từ mã
(A). 32 (B). 48 (C). 64 (D). 128 (E). Cả bốn câu trên đều sai
Câu 10. Một mã tuyến tính có k = 8 và có d = 3 có chiều dài tối thiểu là bao nhiêu
(A). 11 (B). 12 (C). 13 (D). 14 (E). Cả bốn câu trên đều sai
Có công thức nào để giải mấy câu tương tự thế này không?

Bài 12 trang 154 nói về giới hạn trên và giới hạn dưới của k/c Hamming
Định lý 10.2: Một bộ mã nhị phân có khoảng cách Hamming d thì có thể
- Phát hiện sai được t bit nếu d ≥ t + 1.
- Sửa sai được t bit nếu d ≥ 2t + 1.
Giới hạn trên: M <= 2 mũ n / (tổng xích ma của tổ hợp chập i của n) trong đó i
chạy từ 0 đến t.
Với M là số từ mã tối đa,n là chiều dài từ mã,t là số lượng bit có thể sửa sai
Giới hạn dưới: 2 mũ r >= tổng xích ma tổ hợp chập i của n ,i chạy từ 0 đến n.
r là số bit kiểm tra với chiều dài từ mã n và k bit thông báo thì r=n-k.

--------------
Câu 8 với d = 2 thì phát hiện được 1 bit sai và sửa sai được 0 bít -> Dựa vào đinh lí 10.2 ta suy ra ta t=0.
Áp dụng công thức Giới hạn trên, ta tính được số lượng từ mã tối đa là 2^8/8C0 = 2^8 =256 từ mã
Câu 10 d=3 suy ra t=1. Từ đó áp dụng công thức tính giới hạn dưới
r = n-k= n-8
2^(n-8)>=(1 + n)
Xét từ n nhỏ nhất (tức n=11) tới lớn nhất. Xem thử n nào ok rồi chọn
Ví dụ chọn n=11 -> loại
Chọn n=12-> chọn vì thoả
-----
Bonus thêm 1 bài
Câu 11. Một mã tuyến tính có k = 40 và có d = 3 có chiều dài từ mã tối thiểu là bao nhiêu
(A). 43 (B). 45 (C). 47 (D). 49 (E). Cả bốn câu trên đều sai
câu này nếu áp dụng cái tính thay số thì bạn sẽ chọn phương án C vì Nó nhỏ nhất và thoả mãn điều kiện
Tuy nhiên đáp án đúng là câu E vì 46 mới là chiều dài từ mã tối thiểu (Không tin thì check nhé)
Ta thấy n=12 thoả mãn yêu cầu bài toán

[09520411]

Dành cho từ Câu 30 đến Câu 33. Xét một thí nghiệm nhị phân có không gian mẫu S = {0, 1} và xác suất p(0) = 0,4, p(1)
= 0,6. Thực hiện thí nghiệm này n lần. Gọi z là biến ngẫu nhiên gắn với số kết quả 0 trong n lần thí nghiệm. Với n = 10.

Câu 32. Xác suất trong 10 lần thí nghiệm có 6 lần kết quả thí nghiệm là 0 bằng (làm tròn đến 2 số lẽ):
(A). 0,11 (B). 0,12 (C). 0,13 (D). 0,14 (E). 0,15
Câu 33. Xác suất trong 10 lần thí nghiệm có 4 lần kết quả thí nghiệm là 0 bằng (làm tròn đến 2 số lẽ):
(A). 0,21 (B). 0,24 (C). 0,25 (D). 0,27 (E). 0,28

Bạn nào có thể giải đáp được câu này nè

[09520204]

Dành cho từ Câu 30 đến Câu 33. Xét một thí nghiệm nhị phân có không gian mẫu S = {0, 1} và xác suất p(0) = 0,4, p(1)
= 0,6. Thực hiện thí nghiệm này n lần. Gọi z là biến ngẫu nhiên gắn với số kết quả 0 trong n lần thí nghiệm. Với n = 10.

Câu 32. Xác suất trong 10 lần thí nghiệm có 6 lần kết quả thí nghiệm là 0 bằng (làm tròn đến 2 số lẽ):
(A). 0,11 (B). 0,12 (C). 0,13 (D). 0,14 (E). 0,15
Câu 33. Xác suất trong 10 lần thí nghiệm có 4 lần kết quả thí nghiệm là 0 bằng (làm tròn đến 2 số lẽ):
(A). 0,21 (B). 0,24 (C). 0,25 (D). 0,27 (E). 0,28

Bạn nào có thể giải đáp được câu này nè

câu 32: p = C(10,6)*(0,4^6)*(0,6^4)
câu 33 tương tự
==> công thức: C(n,k)*p^k*((1-p)^(n-k))
trong đó: n là số lần, k số lần thực hiện thí nghiệm, p là xác suất của kết quả thực hiện thí nghiệm

[08520127]

mấy câu hỏi trắc nghiệm đó ở đâu vậy các bạn,mấy bữa cuối không đi học nên không biết

[09520204]

mấy câu này có ai giải được không?

Cho trường GF(2m) với m = 4 có các phần tử được liệt kê trong bảng sau đây
theo ba dạng: luỹ thừa, đa thức, vectơ. Ngoài ra cho biết đa thức tối
thiểu của a là đa thức căn bản f(x) = 1 + x3 + x4.
Dựa trên trường này, chúng ta xây dựng mã vòng có thể sửa sai 2 bit.
*Câu 43:* Đa thức nào sau đây là đa thức tối thiểu của phần tử a7
*A. *1 + x + x2 *B. *1 + x + x4 *C. *1
+ x3 + x4 *D. *1 + x + x2 + x3 + x4
*Câu 44:* Đa thức sinh của mã vòng cần xây là
*A. *1+x + x2 + x4 + x8 *B. *1 + x3 + x4 *C. *1 + x
+ x2 + x3 + x8 *D. *1 + x + x4
*Câu 45:** * Phần tử nào sau đây là phần tử liên hợp của phần tử a7
*A. *a11 *B. *a9
*C. *a8 *D. *a10

[09520411]

Thật may là thầy Quang lớp mình nói mấy câu trên trường GF(2m) không có thi hihi

[09520204]

thế thầy nhiệm thì sao nhỉ

[09520020]

Bài 12 trang 154 nói về giới hạn trên và giới hạn dưới của k/c Hamming
Định lý 10.2: Một bộ mã nhị phân có khoảng cách Hamming d thì có thể
- Phát hiện sai được t bit nếu d ≥ t + 1.
- Sửa sai được t bit nếu d ≥ 2t + 1.
Giới hạn trên: M <= 2 mũ n / (tổng xích ma của tổ hợp chập i của n) trong đó i
chạy từ 0 đến t.
Với M là số từ mã tối đa,n là chiều dài từ mã,t là số lượng bit có thể sửa sai
Giới hạn dưới: 2 mũ r >= tổng xích ma tổ hợp chập i của n ,i chạy từ 0 đến n.
r là số bit kiểm tra với chiều dài từ mã n và k bit thông báo thì r=n-k.

--------------
Câu 8 với d = 2 thì phát hiện được 1 bit sai và sửa sai được 0 bít -> Dựa vào đinh lí 10.2 ta suy ra ta t=0.
Áp dụng công thức Giới hạn trên, ta tính được số lượng từ mã tối đa là 2^8/8C0 = 2^8 =256 từ mã
Câu 10 d=3 suy ra t=1. Từ đó áp dụng công thức tính giới hạn dưới
r = n-k= n-8
2^(n-8)>=(1 + n)
Xét từ n nhỏ nhất (tức n=11) tới lớn nhất. Xem thử n nào ok rồi chọn
Ví dụ chọn n=11 -> loại
Chọn n=12-> chọn vì thoả
-----
Bonus thêm 1 bài
Câu 11. Một mã tuyến tính có k = 40 và có d = 3 có chiều dài từ mã tối thiểu là bao nhiêu
(A). 43 (B). 45 (C). 47 (D). 49 (E). Cả bốn câu trên đều sai
câu này nếu áp dụng cái tính thay số thì bạn sẽ chọn phương án C vì Nó nhỏ nhất và thoả mãn điều kiện
Tuy nhiên đáp án đúng là câu E vì 46 mới là chiều dài từ mã tối thiểu (Không tin thì check nhé)
Ta thấy n=12 thoả mãn yêu cầu bài toán

C bổ sung một tí về cách lụi cho bài dạng câu 10 và 11

2^(n-k) >= 1 + n
--> n - k >= log (1 + n)

>> vì n bết lắm là = k (vì r = n - k đâu có âm) nên mình cứ lấy giá trị của k thế vào n và tính log(1+n)
Lấy kết quả đó mà tính cái n thực sự từ n-k
Vì sao ư?: Vì hàm log(n) tăng chậm hơn hàm f(n) = n nên n càng tăng thì bất đẳng thức chỉ có càng đúng thôi (ý mình là VT càng bỏ xa VP khi n tăng í mà )

Tóm lại:: Gặp bài kiủ đó thì tính a = log(1 + k) --> n = ]a + k[
Thế thôi

[09520020]

thế thầy nhiệm thì sao nhỉ

Thầy Nhiệm nói là "Không có phòng thực hành, các em về tự coi bài. Cần hỏi thì Skype với thầy"
(Sry đó là câu cuối cùng mình nghe trước khi thầy trò chào tạm biệt)

[09520509]

Cho mình hỏi bài nay làm sao?
ma trận sinh bên:
1 0 1 1 0 1 0
1 1 0 1 0 0 0
0 0 0 1 0 1 1
1 0 0 0 1 1 0
Thông báo u = 1010 sẽ được mã hóa thành từ mã
A.1010001 B.0100011 C.1100011 D.1011001
mình đã nhân u với ma trận sinh nhưng nó ra toàn là 1111111

[09520601]

Đáp án là A Hải ơi...nhân kiểu j thế =))
lấy cột đầu nhân với u --> ra dc bit đầu tien 1 ...(Loai đáp án B)
lấy cột 2 nhân với u --> ra được bít 2 là 0 (Loai đáp án C)
A va D khác nhau bit 4 ...Lấy cột 4 nhân với u ra 0 ( loai D)
...
phăng A ngay

[09520193]

Dành cho câu 11 đến câu 19: Cho nguồn X = { x1, x2, x3, x4, x5, x6, x7, x8} có các xác suất lần lượt như sau: 0.24; 0.20; 0.14; 0.12; 0.1; 0.08; 0.07; 0.05. Mã hoá nhị phân nguồn này bằng phương pháp Shannon.
11. Tin x3 được mã hoá thành:
a. 001 b. 011 c. 100 d. 010 e. Tất cả đều sai.
12. Tin x4 được mã hoá thành:
a. 011 b. 010 c. 0110 d. 1100 e. 1001
13. Tin x5 được mã hoá thành:
a. 1011 b. 1100 c. 1001 d. 011 e. 101
14. Tin x7 được mã hoá thành:
a. 0101 b. 1010 c. 1100 d. 1110 e. 11010
15. Tin x8 được mã hoá thành:
a. 11110 b. 11101 c. 1111 d. 11011 e. 1110
16. Entropy H(X) của nguồn bằng (làm tròn đến 2 số lẻ và lấy đơn vị bits):
a. 2.80 b. 2.79 c. 2.83 d. 2.84 e. 2.82
17. Chiều dài trung bình của bộ mã cho nguồn X trên theo phương pháp Shannon là:
a. 3.02 b. 3.15 c. 3.23 d. 3.47 e. 3.51
18. Mã hoá nguồn X3 bằng phương pháp Shannon thì từ mã ứng với dãy tin x1x3x5 sẽ có chiều dài bằng :
a. 10 b. 9 c. 8 d. 7 e. 6
19. Entropy của nguồn X5, H(X5) được làm tròn lấy 2 số thập phân theo đơn vị bit là:
a. 14.15 b. 14.18 c. 14.17 d. 14.19 e. 14.16

mình giải ra 11-> 17 : b e a d b c d
còn câu 18 , 19 chưa biết làm ai chỉ mình với
thanks