1. Lý thuyết thông tin



tải về 39.61 Kb.
Chuyển đổi dữ liệu24.07.2016
Kích39.61 Kb.
#3958
ĐỀ 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
Каталог: 2007
2007 -> Mẫu 01/hc-sn-dn (Ban hành kèm theo Thông tư số 83/2007/tt-btc ngày 16/7/2007 của Bộ Tài chính) TỜ khai hiện trạng sử DỤng nhà, ĐẤt thuộc sở HỮu nhà NƯỚc và ĐỀ xuất phưƠng án xử LÝ
2007 -> BỘ NÔng nghiệP & phát triển nông thôn cục trồng trọt giới Thiệu
2007 -> 10tcn tiêu chuẩn ngành 10tcn 1011 : 2006 giống cà RỐt-quy phạm khảo nghiệm tính khác biệT, TÍnh đỒng nhấT
2007 -> TIÊu chuẩn ngành 10tcn 683 : 2006 giống dưa chuột-quy phạm khảo nghiệM
2007 -> PHÁt triển nông thôN
2007 -> ĐOÀn tncs hồ chí minh
2007 -> List of the countries of the world sorted by total area
2007 -> Số: 962/QĐ-ubnd vĩnh Long, ngày 16 tháng 5 năm 2007
2007 -> Hồ sơ ngành hàng rau quả
2007 -> BẢn cáo bạch domesco vcbs

tải về 39.61 Kb.

Chia sẻ với bạn bè của bạn:




Cơ sở dữ liệu được bảo vệ bởi bản quyền ©hocday.com 2024
được sử dụng cho việc quản lý

    Quê hương