Công thức truyền tin

thông tin: I ( xi ; y i ) = I ( xi ) + I ( y i ) − I ( xi, y i )  1  I ( xi ) = f   p( x )    i  9. Lượng tin tương hỗ trung bình • Nguồn rời rạc 1 I ( xi ) = log = − log p ( xi ) p( xi / y j ) p ( xi ) I ( X ; Y ) = ∑ p ( xi, y j ) log i, j p ( xi ) 2. Lượng tin riêng p ( xi, y j ) = ∑ p ( xi, y j ) log I ( xi ) = − log p ( xi ) (dvtt) i, j p ( xi ). p ( y j ) p ( y j / xi ) 3. Lượng tin riêng của nguồn = ∑ p ( xi, y j ) log I ( X ) = ∑ p ( xi ).I ( xi ) i, j p( y j ) i I ( X ;Y ) = H ( X ) − H ( X / Y ) = −∑p ( xi ). log p ( xi ) (dvtt/tin) = H ( X ) + H (Y ) − H ( X, Y ) = H (Y ) − H (Y / X ) 4. Entropi của nguồn • Rời rạc 10. Tốc độ lập tin của nguồn H ( xi ) = I ( xi ) = − log p ( xi ) R( X ) = n0 .H ( X ) H ( X ) = I ( X ) = −∑p ( xi ). log p ( xi ) • Nguồn rời rạc • Liên tục n0 – Tần số tạo tin của nguồn H ( X ) = ∫ w( x )dx R ( X ) = F .H ( X ) x Nếu p(xi) = p ∀i R = F. log( N ) 5. Lượng tin đồng thời • Nguồn liên tục • Rời rạc R = 2 Fmax H ( X ) I ( xi, y i ) = −log P ( xi, y i ) • Nguồn có giá trị đỉnh hữu hạn I ( xi, y i ) = I ( xi ) + I ( y i ) − I ( xi ; y i ) I ( X, Y ) = H ( X, Y ) = −∑P ( xi, y i ) log P ( xi, y i )  X = { x} xmin ≤ x ≤ xmax i, j  1 • Liên tục  d( ) I ( X, Y ) = H ( X, Y ) = − ∫ w( x, y ) log w( x, y ) dxdy  w( x) = w = N = 0 x, y  dx R = 2 Fmax log( x max − x min ) 6. Độ bất định có điều kiện • Nguồn có công suất trung bình hữu hạn • Rời rạc I ( xi / yi ) = −log P ( xi / yi )  X = {x} − ∞ < x < +∞  I ( X / Y ) = H ( X / Y ) = −∑P ( xi, y i ) log P ( xi / y i )  w( x) Ptb < ∞ i, j R = 2 Fmax. log 2Π tb eP I (Y / X ) = H (Y / X ) = −∑P ( xi, y i ) log P ( y i / xi ) i, j 11. Thông lượng của kênh • Liên tục C = n 0 .I ( X, Y ) H ( X / Y ) = I ( X / Y ) = − ∫ w( x, y ) log w( x / y ) dxdy • Kênh rời rạc x, y C = ∆f .H ( X ) max H (Y / X ) = I (Y / X ) = − ∫ w( x, y ) log w( y / x ) dxdy • Kênh liên tục C = 2∆f [ H (Y ) − H ( N )] x, y 7. Quan hệ giữa các Entropi Thường là nhiễu chuẩn • H(X,Y) = H(X)+H(Y/X) H ( N ) = log 2ΠeN = H(X)+H(X/Y) C = 2∆ (log f 2Π y − log eP 2Π ) eN Px S • H(Y/X) = H(Y) = ∆f log(1 + ) = ∆f log(1 + ) N N H(Y/X) = H(X) Nếu X,Y độc lập thống kê 1. Các công thức xác suất P(B | A) = P(A, B).P(B) 8. Lượng tin tương hỗ P ( Ai | B ) = P ( Ai, B ) / P ( B ) p ( xi / y i ) I ( xi ; y i ) = H ( xi ) − H ( xi / y i ) = log p ( xi )

P ( B,

Ai ).P ( Ai )  2 ≤ n0 ≤ m
= n 
∑P( B, A ).P ( A j )   L − n0  ∈ Z
 m − 1 
j
j =1
 
2. Mã hóa nguồn rời rạc
n0-Số kí hiệu được nhóm
Mô hình (A, p(xi))
X = { x1 …x L } 4. Giới hạn Hamming về độ dài từ mã chống nhiễu
• Mã phát hiện sai
P ( X ) = ( p ( x1 )… p ( x L ))
Điều kiện: N 1E ≤ R
H ( X ) = −∑ p ( x i ) log 2 p ( x i ) ≤ log 2 L
 t
1  N1E = ∑ C n .( m − 1)
i i
H ( X ) max ⇔ p ( x1 ) = p ( x 2 ) = … = p( x L ) =
L mà  i =1
H ( X ) max = log 2 L 
 R = mn − mk
• Mã hóa với từ mã có độ dài cố định t
⇒ m n − m k ≥ ∑ C n .(m − 1) i
i

• Độ dài từ mã tối thiểu i =1

R =  log 2 L  + 1 • Mã sửa sai
Điều kiện R ≥ N .N 1E
t
• Hiệu suất mã hóa
⇔ m n − m k ≥ m k .∑ C n ( m − 1) i
i
H(X ) H(X )
= +1 i =1
R  log 2 L  t
⇔ n − k ≥ log m ∑ C n (m − 1) i
i
H ( X ) max
Hiệu suất bằng 1 ⇔ 
i =0

 L =2
k

5. Giới hạn Hamming về quãng cách mã
• Định lý mã hóa nguồn 1:
• Phát hiện sai kênh có số sai t
X: Nguồn rời rạc không nhớ, H(X) hữu hạn.
Với ε > 0 :
d ≥ t +1
• Sửa sai hoàn toàn kênh có có số sai t
 N d ≥ 2t + 1
R = ≥ H ( X ) + ε
Pe→ 0 ⇔  J

 J →∞
R ≤ H ( X ) + ε
P e →1 ⇔ 
 J →∞

• Mã hóa với từ mã có độ dài thay đổi
• Xây dựng bộ mã R min
L
R = ∑ ni. p ( x i ) → min
i =1
• Bất đẳng thức Kraft:
Nếu bộ mã có các từ mã có độ dài tương
ứng là n1