ĐỀ CƯƠNG ÔN TẬP
LÝ THUYẾT THÔNG TIN
1. Lý thuyết thông tin:
Đoán số, đo
- B1: Tính độ bất định của đối tượng cần xác định (từ đề bài)
Dùng phép đặt câu hỏi hoặc đo lường
- B2: Xác định lượng thông tin nhận được sau 1 lần đo hoặc hỏi, phụ thuộc bản chất phép đo. VD: Bài toán tìm tiền giả
- B3:Tính số phép đo, số câu hỏi cần thiết
n= Iai/hb
nmin = Iai/max hb
Đối với nhị phân, max hb = 1bit
Tam phân, max hb = log3
- B4: Xác định thuật toán đo ( xác suất để các sự kiện xuất hiện là đồng xác suất)
Bài này em không hiểu nên thầy nói thế nào em viết thế
2. Cây Huffman:
Cho A = a1 a2 a3 a4 a5 a6 a7
1/2 1/4 1/8 1/16 1/32 1/64 1/64
- B1: Sắp xếp các tin theo thứ tự giảm dần của xác suất xuất hiện
- B2: Trong danh sách chọn 2 cây có trọng số nhỏ nhất ghép lại để tạo thành một cây có trọng số bằng tổng trọng số 2 cây con, rồi quay lại B1
- B3: Tính từ gốc G, đường đi đến a1 là 1, a2 là 01…
TT
|
ai
|
P(ai)
|
(mô tả đường đi của ai)
|
ni (độ dài của ai)
|
1
2
3
4
5
6
7
|
a1
a2
a3
a4
a5
a6
a7
|
1/2
1/4
1/8
1/16
1/32
1/64
1/64
|
1
01
001
0001
00001
000001
000000
|
1
2
3
4
5
6
6
|
- B4: Đánh giá hiệu quả của giải thuật
Tính độ dài trung bình
= = 1.1/2 + 2.1/4 + 3.1/8 + 4.1/16 + 5.1/32 + 6.1/64 + 6.1/64
= (dấu mã)
Tính H(A)
H(A) = = 1/2.log2 + 1/4.log4 + 1/8.log8 + 1/16.log16 + 1/32.log32 + 1/64.log64 + 1/64.log64
= (bit)
(chú ý: vì tính theo bit nên ta ngầm hiểu ở đây là log cơ số 2, vì vậy log2=1, log4=2…)
Vậy = H(A) nên mã hóa là tối ưu
- B5: Giải mã đoạn mã đã cho
1010011100110..
Ban đầu ta có con trỏ P trỏ vào gốc G
Khi gặp bit đầu tiên là 1, con trỏ P nhảy sang nhánh con trái của G, thấy đó là lá a1 nên in ra a1 và con trỏ P trở về G.
Bit tiếp theo là 0, con trỏ P nhảy sanh nhánh con phải của G, thấy chưa phải lá nên đọc bit tiếp theo là bit 1, P lại nhảy sanh nhánh con trái, thấy lá nên in ra a2 và con trỏ P trở về G.
Cứ như thế ta được đoạn giải mã
a1 a2 a3 a1 a1 a3 a1 …
3. Thuật toán 4 bước
Cho mã Xyclic (7,3) có đa thức sinh g(X) = 1 + X2 + X3 + X4 và đa thức thông tin a(X) = 1 + X2
Dùng thuật toán 4 bước để thiết lập từ mã hệ thống của bộ mã trên
Bài giải
Mã Xyclic (7,3,4) n = 7, k = 3
- B1: Mã hóa đối chứng tin ai bằng đa thức thông tin a(X). Ví dụ
A 0 B 1 C X D X2
E 1 + X F X + X2 G 1 + X2 H 1 + X + X2
nhưng vì người ta đã cho a(X) nên ko cần mã hóa nữa
- B2: Nâng bậc ai(X) bằng cách nhân với Xn-k
a(X) = a(X) . Xn-k với n =7, k = 3
a(X) = (1 + X2). X4 = X6 + X4
-
X6 + X4 X4 + X3 + X2 + 1
X6 + X5 + X4 + X2 X2 + X + 1
X5 + X2
X5 + X4 + X3 + X
X4 + X3 + X2 + X
X4 + X3 + X2 + 1
X + 1
B3: Chia a(X) ở bước 2 cho g(X) để tìm phần dư r(X)
Vậy r(X) = X + 1
- B4: Từ mã là
f(X) = a(X) + r(X)
= X6 + X4 + X+ 1
1010011
X6 …. X0
Tại vị trí tương ứng nếu trong f(X) có bit nào thì bit đó =1, không có thì = 0, X6 có nên bit đầu tiên bằng 1, X5 không có nên bit thứ 2 = 0, X4 có nên bit 3 = 1…. X có nên bit 6 =1, X0(=1) có nên bit 7 = 1
* Mô tả sơ đồ chức năng:
Từ đa thức sinh g(X) ta có bậc bằng 4 nên có 4 ô nhớ
g0 = g2 = g3 = g4 =1; g1 =0 ( vì trong g(X) có X0, X2, X3, X4 , không có X1)
TT
|
Vào
|
Trạng thái các ô nhớ
|
Ra
|
1
|
2
|
3
|
4
|
1
2
3
|
1
0
1
|
1
1
1
|
0
1
1
|
1
1
0
|
1
0
0
|
1
0
1
|
4
5
6
7
|
0
0
0
0
|
0
0
0
0
|
1
0
0
0
|
1
1
0
0
|
0
1
1
0
|
0
0
1
1
|
Ban đầu trạng thái các ô nhớ =0
-
Nhịp 1, 2, 3 đầu ra giống hệt đầu vào
-
Nhịp 4, 5,6 ,7 chỉ là phép dịch phải các trạng thái ô nhớ
4. Chia dịch vòng:
Cho mã Xyclic (7, 3, 4) có đa thức sinh g(X) = 1 + X2 + X3 + X4. Giả sử từ mã nhận được của bộ mã trên có dạng v(X) = 1 + X + X2. Sử dụng thuật toán chia dịch vòng để tìm lại từ mã đã phát
Bài giải
Từ đề bài cho (7, 3, 4) ta có n = 7, k = 3, d0 = 4
- B1: Chia v(X) cho g(X) ta thấy bậc của v(X) nhỏ hơn bậc của g(X) nên v(X) chính là phần dư của phép chia
r0(X) = X2 + X + 1
trọng số của phần dư w(r0(X)) = 3 > t
với t = phần nguyên của = phần nguyên của = 1
- B2: Dịch vòng phải bằng cách nhân v(X) với X rồi lại chia cho g(X) để tìm phần dư. So sánh trọng số của phần dư với t
X.v(X) = X + X2 + X3 chia cho g(X) dư r1(X) = X + X2 + X3
w(r1(X)) = 3 > t
Ta lại dịch vòng phải một lần nữa
X2.v(X) = X2 + X3 + X4 rồi chia cho g(X) được 1 dư 1
r2(X) =1
w(r2(X)) =1 = t
-
^
B3: Xác định từ mã (vì ta dịch phải 2 lần, tức là nhân X2 nên để tìm từ mã ta phải chia cho X2)
f(X) = = = X2 + X + 1 + X5
(vì ta coi 1 (= X0 ) = X7)
Ta được từ mã 1110010
So với v(X) = 1110000
Ta thấy sai ở vị trí X5 đã được sửa
Chú ý: Nếu không thực hiện dịch vòng phải, có thể thực hiện dịch vòng trái bằng cách chia v(X) cho X. Khi đó:
f(X) = X2 . = X2 . (X6 + X5 + 1 + X3) = X + 1 + X2 + X5 giống như dịch vòng trái
Chia sẻ với bạn bè của bạn: |