Bài 9 Kênh rời rạc không nhớ Lượng tin tương hỗ
9.1 Kênh rời rạc không nhớ và ma trận kênh 9.2 Entropy điều kiện và lượng tin tương hỗ 9.3 Một số loại kênh 9.4 Sự nhập nhằng (equivocation) và tốc độ truyền tin 9.5 Dung lượng kênh
Trang 142 Lý thuyết Thông tin - Khoa Công Nghệ Thông Tin
Kênh rời rạc không nhớ và ma trận kênh
(cid:132) Định nghĩa
(cid:132) Một kênh rời rạc không nhớ (DMC) được định nghĩa bằng một bảng kí hiệu đầu vào (nguồn phát) X = {x1, ..., xK}, một bảng kí hiệu đầu ra (nguồn nhận) Y = {y1, ..., yJ}, và một sự phân bố xác suất có điều kiện p(yj | xk), với 1 ≤ k ≤ K, 1 ≤ j ≤ J.
p(yj | xk) X Y
(cid:132) Bảng kí hiệu đầu ra không nhất thiết giống bảng kí hiệu đầu
xk yj
Trang 143 Lý thuyết Thông tin - Khoa Công Nghệ Thông Tin
vào. Điều này có nghĩa là bên nhận có thể nhận những kí hiệu mà không giống với những kí hiệu mà bên phát phát đi.
Nhận xét
(cid:132) Thuật ngữ không nhớ (memoryless) suy ra rằng
{ yp
y
|
x
x
}
( yp
|
x
)
=
1
jN
k
kN
kn
jn
L
K 1 j với N bất kỳ.
N ∏ 1 n =
(cid:132) Một kênh rời rạc không nhớ thường được biểu diễn dưới dạng
một ma trận kênh [p(yj | xk)] có kích thước K × J.
Trang 144 Lý thuyết Thông tin - Khoa Công Nghệ Thông Tin
... ... ... ... y1 p(y1 | x1) p(y1 | x2) ... p(y1 | xK) y2 p(y2 | x1) p(y2 | x2) ... p(y2 | xK) yJ p(yJ | x1) p(yJ | x2) ... p(yJ | xK) x1 x2 ... xK
Nhận xét (tt)
(cid:132) Chúng ta thấy, ma trận kênh chính là cái mà biểu diễn tính chất
(cid:132) Chú ý, nếu chúng ta biết sự phân bố xác suất trên X thì sự phân
tạp nhiễu của kênh truyền.
( yp
)
( xp
)
( yp
|
x
)
=
j
k
k
j
K ∑ 1 k =
Trang 145 Lý thuyết Thông tin - Khoa Công Nghệ Thông Tin
bố xác suất của Y sẽ được xác định như sau
Entropy điều kiện và lượng tin tương hỗ
(cid:132) Xét bài toán truyền tin sau
(cid:132) Ví dụ
(cid:132) Cho nguồn X = {x1, x2} với các xác suất lần lượt là p(x1) = 1/4,
Cho biết cấu trúc thống kê của nguồn X và ma trận kênh. Hãy xác định kí hiệu xk nào đã được phát phát đi khi nhận được ở đầu nhận một kí hiệu yj nào đó?
p(x2) = 3/4, nguồn Y = {y1, y2} và ma trận kênh là
y2 1/5 3/5 x1 x2
Trang 146 Lý thuyết Thông tin - Khoa Công Nghệ Thông Tin
y1 4/5 2/5 (cid:132) Nếu nhận được y1 thì xk nào có khả năng đã được phát đi?
Ví dụ
( xp
,
y
)
)
( xp
( yp
|
x
)
( xp
)
( yp
|
x
)
×
×
k
j
k
k
j
( xp
|
y
)
=
=
=
k
j
k ( yp
j )
j
(
,
)
( xp
)
( yp
|
x
)
×
yxp i
j
i
i
j
k K ∑ 1 i =
K ∑ 1 i =
|
( xp
|
)
=
xp ( 1
y 1
2
) =y 1
x
( |
(
(
|
)
( +
3 5
x ) 1 yp ( ) 1
2
=
=
)5/4( )4/3(
ypxp ) 1 1 )4/1( )5/4(
)4/1(
)5/2(
2 2 5
ypxp | ) 1 1 x xp ) ( 1 × +
×
×
(cid:132) p(x1 | y1) < p(x2 | y1), như vậy chúng ta có thể khẳng định được
Trang 147 Lý thuyết Thông tin - Khoa Công Nghệ Thông Tin
kí hiệu x2 có khả năng được phát đi hơn x1?
Ví dụ (tt)
(cid:132) Để ý, trong công thức của p(xi | yj) có chứa thừa số p(xi), nên
(cid:132) Vì vậy để công bằng trong việc so sánh chúng ta phải dựa trên tỉ số p(xi | yj)/p(xi) cái mà không bị ảnh hưởng nhiều bởi p(xi).
)
=
=
y 1 )
5/2 4/1
8 5
)
=
=
xp ( | 1 xp ( 1 xp | ( 2 xp (
y 1 )
5/3 4/3
4 5
2
(cid:132) Như vậy thực sự kí hiệu x1 mới có khả năng được phát đi hơn kí
p(xi | yj) đã bị ảnh hưởng bởi xác suất lề p(xi).
(cid:132) Từ xác suất điều kiện chúng ta giới thiệu khái niệm lượng tin có
hiệu x2.
Trang 148 Lý thuyết Thông tin - Khoa Công Nghệ Thông Tin
điều kiện.
Lượng tin có điều kiện I(xk | yj)
(cid:132) Định nghĩa
I(yj | xk) = –log p(yj | xk) I(xk | yj) = –log p(xk | yj) (cid:132) p(yj | xk) → 1 thì I(yj | xk) → 0 và ngược lại. (cid:132) Nếu khi phát đi xk và biết chắc yj sẽ nhận được thì ở phía nhận
(cid:132) Nếu p(yj | xk) = 1/2 (I(yj | xk) = 1 bit) thì khi phát đi xk bên nhận sẽ có hai khả năng và yj chỉ là một trong hai khả năng đó, có nghĩa là bên nhận cần thêm thông tin (cần thêm 1 bit) để biết chính xác đó là khả năng nào.
(cid:132) Xác suất p(yj | xk) = 1/2 chỉ xảy ra khi kênh truyền có nhiễu.
Trang 149 Lý thuyết Thông tin - Khoa Công Nghệ Thông Tin
chúng ta không cần tốn thêm thông tin gì để giải thích.
Lượng tin có điều kiện I(xk | yj)
(cid:132) Vì vậy lượng tin có điều kiện còn được gọi là lượng tin bị mất
(cid:132) Khi phát đi xk bên nhận sẽ có một tập các yj có khả năng được
đi do nhiễu.
(cid:132) Ngược lại khi nhận được yj bên phát sẽ có một tập các xk có khả
nhận.
(cid:132) Để đo mức độ “quan hệ” giữa xk với yj chúng ta giới thiệu khái
năng được phát.
Trang 150 Lý thuyết Thông tin - Khoa Công Nghệ Thông Tin
niệm lượng tin tương hỗ.
Lượng tin tương hỗ
(cid:132) Định nghĩa
(cid:132) Lượng tin tương hỗ giữa hai tin là lượng tin của của tin này
)
(
)
(
log
log
=
=
|yxp k xp (
j )
|xyp j yp (
k )
k
j
(cid:132) Nếu p(xk | yj) = 1 có nghĩa là nếu yj đã nhận được thì chắc chắn xk đã được phát đi, điều này có nghĩa là lượng tin của xk đã được truyền nguyên vẹn thông qua kênh, do đó I(xk, yj) = I(xk).
Trang 151 Lý thuyết Thông tin - Khoa Công Nghệ Thông Tin
được chứa trong tin kia và ngược lại. Bằng công thức Lượng tin tương hỗ = Lượng tin riêng – Lượng tin bị mất đi I(xk, yj) = I(xk) – I(xk | yj) = I(yj) – I(xk | yj)
log)
y
y
y
)
)
|
|
|
|
( yXI |
)
=
( xp k
( xp k
j
j
() xIy k
( xp k
j
j
j
Lượng tin có điều kiện trung bình K ∑ −= 1 k =
K ∑ 1 k =
( xYI |
)
( yp
|
x
() yI
|
x
)
( yp
|
x
log)
( yp
|
x
)
=
−=
k
k
j
k
j
k
j
k
j
J ∑ j 1 =
J ∑ j 1 =
( YXI
|
)
() yXI
|
)
( yp
)
|
y
log)
|
y
)
( yp
=
−=
j
j
( xp k
j
( xp k
j
j
J ∑ j 1 =
K ∑ k 1 =
( xp
,
y
log)
( xp
|
y
)
−=
k
j
j
k
( XYI |
)
,
y
log)
( yp
|
)
−=
( xp k
j
x k
j
J ∑ j 1 = J K ∑ ∑ j k 1 1 = = J K ∑ ∑ j k 1 1 = =
Trang 152 Lý thuyết Thông tin - Khoa Công Nghệ Thông Tin
Entropy điều kiện
(cid:132) Định nghĩa
(cid:132) Xét hai biến ngẫu nhiên x và y với phân bố xác suất đồng thời p(xk, yj), k = 1, ..., K , j = 1, ..., J. Entropy điều kiện của x đã cho y được định nghĩa là
H
(
yx |
)
( xp
,
y
log)
( xp
|
y
)
−=
k
j
j
k
J K ∑ ∑ j k 1 1 = =
(cid:132) H(x | y) có thể được diễn dịch như là độ bất ngờ trung bình về x
(cid:132) Định lý 9.1
(cid:132) H(x | y) ≤ H(x), dấu “=” xảy ra ⇔ x và y là độc lập.
Trang 153 Lý thuyết Thông tin - Khoa Công Nghệ Thông Tin
sau khi đã biết y.
Chứng minh
H
H
,
y
ln)
|
y
)
ln)
)
−
+
)|( yx
)( x
( xp k
j
( xp k
j
( xp k
( xp k
K ∑ 1 k =
,
ln)
( yxp k
j
)
( ) xp k xp y ( | k
j
J K ∑∑ −= 1 1 j k = = J K ∑∑ −= 1 1 j k = =
(cid:132) Lấy tổng trên những cặp (k, j) mà p(xk, yj) ≠ 0. Vì vậy
H
H
y
,
)
−
−
=
)|( yx
)( x
xp ( k
j
)
xp ( ) k xp y ( | k
j
⎡ ⎢ ⎢ ⎣ ( yp
⎤ 1 ⎥ ⎥ ⎦ , y
( xp
)
)
( xp
)
−
=
k
k
j
j
xp (
)
yp (
01
)
≤−
]
k
j
∑∑ k j ∑ ∑ k j [ = ∑∑ j k
Trang 154 Lý thuyết Thông tin - Khoa Công Nghệ Thông Tin
Chứng minh (tt)
(cid:132) Dấu “=” xảy ra ⇔ p(xk) = p(xk | yj) đối với tất cả các cặp (k, j) mà p(xk, yj) ≠ 0 đồng thời tổng p(xk)p(yj) trên tất cả những cặp này bằng 1.
(cid:132) Điều kiện thứ hai tương đương với điều kiện p(xk)p(yj) = 0 bất
(cid:132) Cả hai điều kiện này cuối cùng tương đương với điều kiện là x
kỳ khi nào mà p(xk, yj) = 0.
(cid:132) Định lý 9.2
(cid:132) H(x, y) = H(x) + H(y | x) = H(y) + H(x | y)
Trang 155 Lý thuyết Thông tin - Khoa Công Nghệ Thông Tin
và y độc lập.
Chứng minh
H
( xp
,
y
log)
( xp
,
y
)
),( yx
k
j
j
k
( xp
,
y
( xp
)
log
( yp
|
x
)
−=
+
[ ) log
]
k
j
k
k
j
( xp
log
( xp
( yp
,
y
log)
( yp
|
x
)
−=
[ )
k
k
k
j
k
j
] ∑∑ ) −
k
j
H
(
)
=
∑∑−= k j ∑∑ k j ∑ k x H )( +
| xy
(cid:132) Phần thứ hai chứng minh hoàn toàn tương tự. (cid:132) Kết hợp hai định lý trên chúng ta suy ra rằng
(cid:132) dấu “=” xảy ra ⇔ x, y là độc lập.
Trang 156 Lý thuyết Thông tin - Khoa Công Nghệ Thông Tin
H(x, y) ≤ H(x) + H(y)
Lượng tin tương hỗ trung bình
( YXI
,
)
( xp
,
y
() xI
)
,
y
k
k
j
|
)
j ( xp
y
j
,
log)
( xp
y
j
k
)
k ( xp
∑∑= k j ∑∑= j k
x
k |
)
( yp
( xp
,
y
log)
k
j
j yp ( ( xp
k ) y
j ,
)
( xp
,
y
log)
k
j
k )
j yp (
)
xp (
j
k
∑∑= k j ∑∑= j k
(cid:132) Nếu biểu diễn theo entropy thì chúng ta có
Trang 157 Lý thuyết Thông tin - Khoa Công Nghệ Thông Tin
I(x, y) = H(x) – H(x | y) = H(y) – H(y | x)
Một số loại kênh rời rạc không nhớ
(cid:132) Kênh đối xứng (Symmetric channel)
(cid:132) Là kênh mà mỗi dòng của ma trận kênh chứa cùng tập các số
4
j = 1
2
3
(cid:132) Ví dụ
0,3
k = 1
0,2
0,2
0,3
[p(yj | xk)] =
0,2
k = 2
0,3
0,3
0,2
0,2
0,3
0,5
0,3
0,5
0,2
[p(yj | xk)] =
p1’, ..., pJ’ và mỗi cột chứa cùng tập các số q1’, ..., qK’.
0,5
0,2
0,3
1 – ε
ε
0 ≤ ε ≤ 1
[p(yj | xk)] =
ε
1 – ε
Trang 158 Lý thuyết Thông tin - Khoa Công Nghệ Thông Tin
Các ma trận biểu diễn các kênh đối xứng
Kênh đối xứng nhị phân (binary symmetric channel – BSC).
Nhận xét
(cid:132) Kênh đối xứng thì H(y | x) độc lập với sự phân bố xác suất của
(cid:132) Chứng minh
H
(
)
( xp
,
y
log)
( yp
|
x
)
−=
| xy
k
j
k
j
( xp
)
( yp
|
x
log)
( yp
|
x
)
−=
k
k
j
k
j
( xp
)
p
p
−=
k
' log j
' j
J ∑ j 1 = J ∑ j 1 =
p
p
−=
' log j
' j
J K ∑ ∑ j k 1 1 = = K ∑ k 1 = K ∑ k 1 = J ∑ j 1 =
Trang 159 Lý thuyết Thông tin - Khoa Công Nghệ Thông Tin
nguồn phát và được xác định duy nhất bằng ma trận kênh.
Kênh không mất (Lossless channel)
(cid:132) Cạnh nối giữa xk và yj nghĩa là p(yj | xk) ≠ 0. Trong kênh không
xK x1 mất đầu ra xác định duy nhất đầu vào, vì vậy H(x | y) = 0. x1
(cid:132) Kênh đơn định (Deterministic channel)
y1 y2 ym ym+1 yJ
x1 x2 xm xm+1 xK
y1 yJ
y2 (cid:132) Trong kênh này đầu vào xác định duy nhất đầu ra, vì vậy
Trang 160 Lý thuyết Thông tin - Khoa Công Nghệ Thông Tin
H(y | x) = 0
Kênh vô dụng (Useless channel)
(cid:132) Một kênh là vô dụng nếu và chỉ nếu x và y là độc lập với mọi
(cid:132) Đối với một kênh vô dụng thì H(x | y) = H(x), tức là kiến thức về đầu ra không làm giảm độ bất ngờ về đầu vào. Vì vậy, đối với mục đích xác định đơn định đầu vào, chúng ta có thể phớt lờ đầu ra hoàn toàn. Bây giờ chúng ta sẽ chứng minh rằng. (cid:132) Một kênh rời rạc không nhớ là vô dụng nếu và chỉ nếu ma trận
sự phân bố xác suất của đầu vào (nguồn phát).
(cid:132) Chứng minh
(cid:132) Điều kiện đủ
kênh của nó có các dòng giống nhau.
Trang 161 Lý thuyết Thông tin - Khoa Công Nghệ Thông Tin
Giả sử ma trận có các dòng giống nhau p1’, ..., pJ’. Thì đối với mọi đầu ra yj
Kênh vô dụng (tt)
( yp
)
( xp
,
y
)
( xp
)
( yp
|
x
)
p
( xp
)
p
=
=
=
=
j
k
j
k
k
j
' j
k
' j
K ∑ 1 k =
K ∑ 1 k =
K ∑ 1 k =
Đối với mọi cặp đầu vào– ra (xk, yj), chúng ta có
(cid:132) Điều kiện cần
p(xk, yj) = p(xk) p(yj | xk) = p(xk) pj’ = p(xk) p(yj) Vì vậy đầu vào và đầu ra độc lập nhau bất chấp sự phân bố xác suất của đầu vào.
Trang 162 Lý thuyết Thông tin - Khoa Công Nghệ Thông Tin
Giả sử các dòng của ma trận không giống nhau ⇒ ∃ một cột chẳng hạn j0 mà có các phần tử không giống nhau. Giả sử p(yj0 | xk0) là phần tử lớn nhất trong cột này. Xét sự phân bố đồng nhất (đẳng xác suất) ở đầu vào (đầu phát), chúng ta có
Kênh vô dụng (tt)
( yp
)
( xp
)
( yp
|
x
)
( yp
|
x
)
( yp
|
x
)
=
=
<
0
0
0
0
0
j
k
k
j
k
j
k
j
1 K
K ∑ 1 k =
K ∑ 1 k =
(cid:132) Tức là p(yj0) ≠ p(yj0 | xk0). Vì vậy p(xk0, yj0) = p(xk0) p(yj0 | xk0) ≠ p(xk0) p(yj0). Mâu thuẫn với giả thiết là x, y độc lập với mọi sự phân bố xác suất của đầu vào.
Trang 163 Lý thuyết Thông tin - Khoa Công Nghệ Thông Tin
Sự nhập nhằng (equivocation) và tốc độ truyền tin
(cid:132) Xét một kênh nhị phân đối xứng với xác suất chéo ε. Giả sử
(cid:132) Một thiết bị được gọi là bộ quan sát, nhận mỗi cặp kí hiệu
rằng tại đầu vào P(0) = P(1) = 1/2, tốc độ sinh thông tin ở đầu phát là H(x) = 1 bit/kí hiệu.
(cid:132) z = 0 nếu x = y, z = 1 nếu x ≠ y
vào/ra (x, y) và sinh ra một kí hiệu z
…z(2)z(1) Bộ quan sát
Kênh
Trang 164 Lý thuyết Thông tin - Khoa Công Nghệ Thông Tin
…x(2)x(1) …y(2)y(1)
Sự nhập nhằng (equivocation) và tốc độ truyền tin (tt)
(cid:132) Sự phân bố của z được tìm thấy như sau:
P(z = 1) = P(x = 0) P(y = 1 | x = 0) + P(x = 1) P(y = 0 | x = 1)
= ε/2 + ε/2 = ε
(cid:132) Tốc độ sinh thông tin bởi bộ quan sát vì vậy bằng
P(z = 0) = 1 – P(z = 0) = 1 – ε
(cid:132) Đối với một dãy đầu ra đã cho y(1)y(2)..., nơi nhận (receiver) có thể xây dựng lại chính xác dãy đầu vào x(1)x(2)... chỉ khi đầu ra của bộ quan sát z(1)z(2)... đã được tạo sẵn.
(cid:132) Tốc độ truyền thông tin trên kênh, thường kí hiệu là R, là bằng tốc độ sinh thông tin H(x) trừ tốc độ sinh thông tin bổ sung H(z).
H(z) = –ε log ε – (1 – ε) log(1 – ε) bits/kí hiệu
R = H(x) – H(z) Trang 165 Lý thuyết Thông tin - Khoa Công Nghệ Thông Tin
Ví dụ
(cid:132) Chẳng hạn, nếu dữ liệu đầu vào được sinh ở tốc độ 1000 kí
→ tốc độ dữ liệu đầu vào = 1000 bits/giây
(cid:132) Một người có thể lý luận rằng trong một dãy dài, vì ε = 0,01, nghĩa là chỉ 1% số bit được truyền bị lỗi, và vì vậy tốc độ truyền thông tin phải là 990 bits/giây.
(cid:132) Câu trả lời là rằng kiến thức về số bit bị lỗi không đủ để xây dựng lại dữ liệu, mà chúng ta cần phải biết thêm về vị trí lỗi nữa, và vì lý do này nên tốc độ truyền thông tin là thực sự bằng một giá trị thấp hơn là 919 bits/giây.
Trang 166 Lý thuyết Thông tin - Khoa Công Nghệ Thông Tin
hiệu/giây và ε = 0,01, chúng ta có H(x) = 1 H(z) = 0,081 → tốc độ dữ liệu bổ sung = 81 bits/giây R = 0,919 → tốc độ truyền thông tin = 919 bits/giây
Nhận xét
(cid:132) Trong trường hợp tốt nhất ε = 0, chúng ta có H(z) = 0 và vì vậy
(cid:132) Trong một trường hợp khác nếu ε = 1/2, thì H(z) = 1, kết quả là
R = 1000 bits/giây.
(cid:132) Cả hai kết luận là nhất quán với sự mong đợi của chúng ta. (cid:132) Đối với kênh nhị phân đối xứng với đầu vào đẳng xác suất,
R = 0 bits/giây.
(cid:132) Tổng quát chúng ta chứng minh được rằng (cid:132) Sự tái xây dựng chính xác dãy đầu vào từ dãy đầu ra là có thể nếu bộ quan sát có thể sinh ra thông tin bổ sung ở tốc độ lớn hơn hay bằng H(x | y).
Trang 167 Lý thuyết Thông tin - Khoa Công Nghệ Thông Tin
chúng ta chứng minh được rằng H(z) = H(x | y).
Nhận xét (tt)
(cid:132) Để thấy điều này một cách trực quan, quan sát rằng đối với các dãy dài có chiều dài N có khoảng 2NH(x | y) dãy đầu vào có thể sinh ra một dãy đầu ra cụ thể.
(cid:132) Chỉ khi thông tin bổ sung được sinh ra tại tốc độ H(x | y) hay nhanh hơn mới cho phép phân biệt giữa các khả năng này. (cid:132) Đối với lý do này, H(x | y) thường được coi như là sự nhập
nhằng (equivocation) của kênh. Và chúng ta định nghĩa lại tốc độ truyền thông tin trên kênh là
Trang 168 Lý thuyết Thông tin - Khoa Công Nghệ Thông Tin
R = H(x) – H(x | y) = I(x, y)
Dung lượng kênh
(cid:132) Theo phần trên tốc độ truyền tin trên kênh được định nghĩa là
(cid:132) I(x, y) tổng quát là một hàm của sự phân bố xác suất đầu vào
R = H(x) – H(x | y) = I(x, y)
{p1, …, pK}. Vì vậy, có thể tìm thấy một sự phân bố mà cực đại I(x, y). Giá trị cực đại của I(x, y) được định nghĩa là dung lượng kênh C và là một hàm của ma trận kênh. C = Cực đại (trên các sự phân bố xác suất đầu vào) của I(x, y). (cid:132) Tổng quát, việc tính dung lượng kênh là một bài toán khó và là
(cid:132) Tuy nhiên đối với các kênh đã được giới thiệu ở trên C có thể
một bài toán chưa được giải một cách triệt để.
Trang 169 Lý thuyết Thông tin - Khoa Công Nghệ Thông Tin
tính toán được như phần sau đây trình bày.
Kênh đối xứng
C
log
p
p
J
=
+
' log j
' j
J ∑ 1 j = trong đó p1’, …, pJ’ là các phần tử của các hàng của ma trận. (cid:132) Trong trường hợp kênh nhị phân đối xứng với xác suất chéo là
p chúng ta có
(cid:132) Kênh không mất
(cid:132) H(x | y) = 0, vì vậy
C = 1 – H(p) với H(p) = –plogp – (1–p)log(1–p)
Trang 170 Lý thuyết Thông tin - Khoa Công Nghệ Thông Tin
C = Max {H(x) – H(x | y)} = Max{H(x)} = log K trong đó K là kích thước của bảng kí hiệu đầu vào. Dung lượng đạt được trong trường hợp đầu vào có sự phân bố đẳng xác suất.
Kênh đơn định
(cid:132) Ở đây H(y | x) = 0, vì vậy
C = Max {H(y) – H(y | x)} = Max{H(y)} = log J
(cid:132) Kênh vô dụng
(cid:132) Ở đây H(x | y) = H(x), vì vậy
trong đó J là kích thước của bảng kí hiệu đầu ra.
(cid:132) Một kênh vô dụng thì có dung lượng kênh bằng 0.
Trang 171 Lý thuyết Thông tin - Khoa Công Nghệ Thông Tin
C = Max {H(x) – H(x | y)} = Max{H(x) – H(x)} = 0
Bài 10 Mã hóa chống nhiễu, định lý kênh
10.1 Giới thiệu bài toán chống nhiễu 10.2 Định lý kênh có nhiễu cho kênh nhị phân đối xứng rời
rạc (BSC)
10.3 Định lý ngược của kênh truyền có nhiễu
Trang 172 Lý thuyết Thông tin - Khoa Công Nghệ Thông Tin
Giới thiệu bài toán chống nhiễu
(cid:132) Mục tiêu chống nhiễu là bên nhận có thể đoán (giải mã) được
(cid:132) Chẳng hạn xét nguồn nhị phân đối xứng với xác suất chéo ε, đồng thời giả sử nguồn phát đẳng xác suất, tức P(0) = P(1) = 1/2.
(cid:132) Với ε < 1/2, xét cơ chế giải mã ở bên nhận như sau: Nếu y = 0
càng chính xác càng tốt dãy kí hiệu đã được phát.
thì đoán x = 0 và nếu y = 1 thì đoán x = 1. (cid:132) Xác suất giải mã bị lỗi của cơ chế này là
(cid:132) Chú ý trong trường hợp ở đây chúng ta tính được
P(lỗi) = P(y = 0) P(x = 1 | y = 0) + P(y = 1) P(x = 0 | y = 1) = ε/2 + ε/2 = ε.
(cid:132) Vấn đề quan trọng là có thể giảm được xác suất giải mã bị lỗi
P(y = 0) = P(y = 1) = 1/2 và P(x ≠ y | y) = ε.
Trang 173 Lý thuyết Thông tin - Khoa Công Nghệ Thông Tin
hay không?
Giới thiệu bài toán chống nhiễu (tt)
(cid:132) Một hướng giải quyết như sau: để gởi 0 chúng ta gởi chuỗi 3 kí
(cid:132) Cơ chế giải mã của bên nhận như sau: Nếu chuỗi nhận có nhiều
hiệu 0 và tương tự để gởi 1 chúng ta gởi 3 kí hiệu 1.
(cid:132) Chẳng hạn bên nhận nếu nhận được 010 thì giải mã thành 0 còn
kí hiệu 0 hơn 1 thì giải mã thành 0 và ngược lại.
nếu nhận được 110 thì giải mã thành 1. (cid:132) Cơ chế này có xác suất giải mã bị lỗi là
(cid:132) Xác suất này nhỏ hơn ε. Tuy nhiên hiệu suất truyền thông tin bị
P(lỗi) = 3(1 – ε)ε2 + ε3 < ε
(cid:132) Tương tự nếu muốn xác suất giải mã tiến đến 0 chúng ta sẽ mã hoá 0 thành dãy 2n + 1 kí hiệu 0 và mã hoá 1 thành 2n + 1 kí hiệu 1, nhưng tương ứng lúc này hiệu suất truyền thông tin giảm xuống 2n + 1 lần so với ban đầu.
Trang 174 Lý thuyết Thông tin - Khoa Công Nghệ Thông Tin
giảm xuống 3 lần.
Giới thiệu bài toán chống nhiễu (tt)
(cid:132) Có một cách có thể giảm xác suất giải mã lỗi xuống gần bằng 0 nhưng không giảm hiệu suất truyền thông tin xuống gần bằng 0 mà chỉ cần nhỏ hơn một ngưỡng nào đó là đủ.
(cid:132) Ngưỡng đó chính là dung lượng kênh. (cid:132) Cách này cũng khai thác ý tưởng trên ở chỗ thay vì để gởi đi 0 và 1, cái mà có “khoảng cách Hamming” giữa chúng là 1 thì chúng ta sẽ mã hoá lần lượt thành 000 và 111, cái mà có “khoảng cách Hamming” giữa chúng là 3 và vì vậy giảm xác suất giải mã bị lỗi.
Trang 175 Lý thuyết Thông tin - Khoa Công Nghệ Thông Tin
Định lý kênh có nhiễu cho kênh nhị phân đối xứng rời rạc (BSC)
(cid:132) Xét kênh nhị phân đối xứng với xác suất chéo p. (cid:132) Dung lượng kênh trong đơn vị bits/kí hiệu là
(cid:132) Giả sử thời gian truyền 1 kí hiệu là T, số kí hiệu được truyền trong 1 giây là 1/T, thì dung lượng theo đơn vị bits/giây là
C = 1 – H(p) với H(p) = –plogp – (1–p)log(1–p)
C = [1 – H(p)]/T (cid:132) Xét nguồn X có entropy H(X) bits/ký hiệu, tức là nguồn này tạo
ra thông tin ở tốc độ theo đơn vị bits/giây.
(cid:132) Định lý 10.1.
(cid:132) Chừng nào mà R (bits/giây) còn nhỏ hơn C (bits/giây), thì việc truyền trên kênh với tỉ lệ lỗi nhỏ tuỳ ý là có thể thực hiện được.
(cid:132) Để chứng minh định lý này cần một số khái niệm sau.
Trang 176 Lý thuyết Thông tin - Khoa Công Nghệ Thông Tin
R = H(X)/T
Các khái niệm
(cid:132) Trọng số Hamming
(cid:132) Trọng số Hamming của một dãy kí hiệu v = a1a2...an , trong đó
(cid:132) Khoảng cách Hamming
(cid:132) Khoảng cách Hamming của hai dãy kí hiệu v1, v2 với chiều dài bằng nhau là số vị trí khác nhau của hai dãy, và thường được kí hiệu là d(v1, v2). (cid:132) Phép cộng cơ số m, ⊕
(cid:132) Xét a, b ∈ {0, 1, ..., m–1} thì a ⊕ b = (a + b) mod m. (cid:132) Nếu v1 = a1a2...an, v2 = b1b2...bn thì v1 ⊕ v2 = c1c2...cn trong đó ci
mỗi ai ∈ {0, 1, ..., m–1}, là số kí hiệu khác 0 của dãy, và thường được kí hiệu là w(v).
Trang 177 Lý thuyết Thông tin - Khoa Công Nghệ Thông Tin
= ai ⊕ bi với i = 1, 2, ..., n.
Các khái niệm (tt)
(cid:132) Ví dụ
(cid:132) w(10100) = 2, w(01120) = 3. (cid:132) d(10100, 10001) = 2, d(011010, 101101) = 5. (cid:132) Với m = 2 thì 1011 ⊕ 1101 = 0110. Với m = 3 thì 1021 ⊕ 2120
(cid:132) Bổ đề
= 0111.
(cid:132) Nhận xét
(cid:132) Bất đẳng thức thứ hai có dạng của bất đẳng thức tam giác: tổng
d(v1, v2) = w(v1 ⊕ v2 ) d(v1, v2) + d(v2, v3) ≥ d(v1, v3)
hai cạnh của một tam giác lớn hơn hoặc bằng cạnh còn lại. (cid:132) Định lý 10.1 đúng cho kênh rời rạc không nhớ bất kỳ. Tuy
Trang 178 Lý thuyết Thông tin - Khoa Công Nghệ Thông Tin
nhiên ở đây chúng ta chỉ chứng minh cho kênh nhị phân đối xứng rời rạc.
Chứng minh định lý
(cid:132) Ý tưởng chứng minh là mã hoá các dãy dữ liệu thành các từ mã, trong đó các kí hiệu mã lấy từ bảng kí hiệu đầu vào của kênh và xử lý các từ mã này như các đầu vào cơ bản của kênh.
(cid:132) Xác suất lỗi nhỏ tuỳ ý có thể đạt được dựa trên sự mã hoá như
sau: (1) chọn chiều dài N của dãy dữ liệu đủ dài (2) mã hoá các dãy này thành các từ mã có khoảng cách
(cid:132) Nguyên tắc giải mã ở đầu ra được thiết kế như sau: dãy kí hiệu nhận được ở đầu ra vj sẽ được giải mã thành từ mã wi mà có khoảng cách Hamming nhỏ nhất đối với vj.
(cid:132) Với cách chọn này xác suất giải mã lỗi là nhỏ nhất. Thật vậy
Hamming xa nhau.
Trang 179 Lý thuyết Thông tin - Khoa Công Nghệ Thông Tin
p(wi | vj) = p(wi)p(vj | wi)/p(vj)
Chứng minh định lý (tt)
(cid:132) Do đó khi chúng ta không rõ về p(wi) và dĩ nhiên sẽ kéo theo
p(vj) thì p(wi | vj) lớn nhất khi p(vj | wi) là lớn nhất. Mà
(cid:132) Nếu xác suất chéo p < 0,5 thì p(vj | wi) sẽ lớn nhất khi D là nhỏ
p(vj | wi) = pD(1–p)N–D trong đó D là khoảng cách Hamming giữa vj và wi, N là chiều dài của chúng, p là xác suất chéo.
(cid:132) Chứng minh rằng ∀ θ > 0 nhỏ tuỳ ý, với N đủ lớn tồn tại cách
nhất.
mã hoá các dãy dữ liệu thành các từ mã sao cho với nguyên tắc giải mã trên có xác suất giải mã lỗi là nhỏ hơn θ. (cid:132) Thật vậy số dãy dữ liệu có chiều dài N là vào khoảng
M = 2NH(X) = 2NRT
Trang 180 Lý thuyết Thông tin - Khoa Công Nghệ Thông Tin
trong khi đó tổng số dãy có chiều dài N là 2N.
Chứng minh định lý (tt)
(cid:132) Gọi {w1, w2, …, wM} là một tập từ mã bất kỳ, Pe là xác suất giải
(cid:132) Nếu chúng ta chứng minh được rằng ∀ θ > 0 nhỏ tuỳ ý, với N
mã lỗi đối với tập này.
(cid:132) Với xác suất lỗi trên đường truyền là p, một dãy có chiều dài N
đủ lớn giá trị trung bình của Pe, , nhỏ hơn θ thì sẽ tồn tại một eP tập từ mã mà có xác suất giải mã lỗi Pe nhỏ hơn θ.
(cid:132) Với hai số dương ε, δ nhỏ tuỳ ý, theo luật yếu của số lớn với N đủ lớn thì xác suất để số vị trí của chuỗi nhận vj khác với chuỗi phát wi lớn hơn N(p + ε) là nhỏ hơn δ. Hay nói theo ngữ cảnh của khoảng cách Hamming là
sẽ có trung bình Np vị trí lỗi.
(cid:132) Vì vậy bộ mã mà chúng ta mong muốn sẽ như sau: Khoảng cách Hamming giữa hai từ mã bất kỳ là ≥ 2N(p + ε) + 1
Trang 181 Lý thuyết Thông tin - Khoa Công Nghệ Thông Tin
P[d(wi, vj) > N(p + ε)] < δ
Chứng minh định lý (tt)
(cid:132) Như vậy với mỗi vj nhận được theo bất đẳng thức tam giác tồn
tại một từ mã wi mà có
d(wi, vj) ≤ N(p + ε)
còn các từ mã wk khác có
(cid:132) Vì vậy chúng ta sẽ giải mã được duy nhất vj thành wi. (cid:132) Với ý tưởng này, chúng ta sẽ đưa ra cơ chế giải mã lỏng hơn
d(wk, vj) ≥ N(p + ε) + 1
(cid:132) Với mỗi dãy vj nhận được, định nghĩa một tập kiểm tra Aj bao
cho một tập từ mã bất kỳ {w1, w2, …, wM}, nhưng cũng sẽ đảm bảo xác suất giải mã lỗi là nhỏ hơn θ.
(cid:132) Nếu từ mã được truyền wi là từ mã duy nhất thuộc tập Aj thì giải
gồm tất cả những dãy có chiều dài N và có khoảng cách Hamming so với vj nhỏ hơn hay bằng N(p + ε).
Trang 182 Lý thuyết Thông tin - Khoa Công Nghệ Thông Tin
mã vj thành wi. Ngược lại thông báo một lỗi đã xảy ra.
Chứng minh định lý (tt)
(cid:132) Một lỗi xảy ra thuộc vào một trong hai trường hợp sau đây
(1) Từ mã được truyền wi không thuộc Aj, tức là
d(wi, vj) > N(p + ε) Lỗi này xảy ra với xác suất nhỏ hơn δ.
(2) Tồn tại một từ mã wk khác cũng thuộc Aj. Lúc này chúng ta
(cid:132) Chúng ta chứng minh rằng theo cách này xác suất giải mã lỗi
không biết nên giải mã vj thành wi hay wk.
(cid:132) Chúng ta có
A
)
trung bình sẽ nhỏ hơn θ với θ nhỏ tuỳ ý cho trước.
δ +≤
∈
P e
( wP i
j
M ∑ i 1 = j i ≠
Trang 183 Lý thuyết Thông tin - Khoa Công Nghệ Thông Tin
Chứng minh định lý (tt)
eP
)
N
k
⎛ ⎜⎜ ⎝
⎞ ⎟⎟ ⎠
(
)
∈
=
AWP i
j
N
(cid:132) Suy ra
số dãy
ε
)
N k
⎛ ⎜⎜ ⎝
⎞ ⎟⎟ ⎠
M
)1
(
δ +<
−
P e
N
(cid:132) Để tính chúng ta sẽ tính giá trị trung bình của P(wi ∈ Aj). (cid:132) Giá trị trung bình này sẽ bằng số dãy thuộc tập Aj chia cho tổng pN ( ε+ ∑ k 0 = 2 ( pN + ∑ 0 k = 2
Trang 184 Lý thuyết Thông tin - Khoa Công Nghệ Thông Tin
Chứng minh định lý (tt)
NH
(
)
α
2
k
(cid:132) Mà chúng ta có một bất đẳng thức nổi tiếng sau N ⎛ ⎜⎜ ⎝
⎞ ≤⎟⎟ ⎠
N α ∑ k 0 =
(cid:132) Áp dụng vào bất đẳng thức trên chúng ta có
với H(α) = –α logα – (1–α)log(1–α). eP
eP (cid:132) Vì ε và δ có thể nhỏ tuỳ ý, nên chừng nào R < [1 – H(p)]/T = C (bits/giây) thì có thể làm cho nhỏ tuỳ ý bằng cách tăng N.
(cid:132) Chứng minh được hoàn tất.
Trang 185 Lý thuyết Thông tin - Khoa Công Nghệ Thông Tin
≤ δ + M×2–N [1 – H(p + ε)] = δ + 2NRT 2–N [1 – H(p + ε)] = δ + 2–N [1 – H(p + ε) – RT]
Ví dụ
(cid:132) Xét ví dụ trước đây, một kênh đối xứng nhị phân có xác suất
(cid:132) Định lý kênh cho phép chúng ta kết luận, với xác suất đúng tiến tới 1, rằng với N khá lớn chẳng hạn N = 1000, thì trong 21000 dãy có chiều dài 1000 chúng ta có thể chọn được 2K dãy với K < 919 sao cho khoảng cách Hamming giữa các dãy là ≥ 2Nε + 1 = 21.
(cid:132) Khoảng cách Hamming của bộ mã
(cid:132) Khoảng cách Hamming của một bộ mã A, với điều kiện A là mã đều, kí hiệu là d(A), là khoảng cách Hamming nhỏ nhất trong tất cả các khoảng cách giữa hai từ mã bất kỳ của A.
Trang 186 Lý thuyết Thông tin - Khoa Công Nghệ Thông Tin
chéo ε = 0,01. Tốc độ truyền kí hiệu f = 1000 kí hiệu/giây (tức T = 0,001 giây). Chúng ta có C = 0,919 bits/kí hiệu hay C = 919 bits/giây.
Định lý
(cid:132) Định lý 10.2
(cid:132) Một bộ mã nhị phân có khoảng cách Hamming d thì có thể
(cid:132) Phát hiện sai được t bit nếu d ≥ t + 1. (cid:132) Sửa sai được t bit nếu d ≥ 2t + 1.
(cid:132) Chứng minh
(cid:132) Gọi wi là từ mã phát, vi là dãy nhận tương ứng. Nếu sai tối đa t > 0 bit thì d(wi, vi) ≤ t. Do đó tổ hợp nhận sẽ không thể trùng với bất kỳ từ mã nào vì khoảng cách Hamming giữa hai từ mã bất kỳ là ≥ t + 1. Vì vậy bên nhận có thể phát hiện được sai. (cid:132) Tương tự nếu d(wi, wj) ≥ 2t + 1, theo bất đẳng thức tam giác ⇒ d(wj, vi) ≥ t + 1 ∀ từ mã wj ≠ wi. Vì vậy bên nhận có thể giải mã đúng vi thành wi dựa trên sự khác biệt này.
Trang 187 Lý thuyết Thông tin - Khoa Công Nghệ Thông Tin
Định lý ngược của kênh truyền có nhiễu
(cid:132) Định lý 10.2
(cid:132) Nếu tốc độ truyền tin R (bits/giây) lớn hơn dung lượng kênh C (bits/giây), thì sự truyền thông trên kênh với tỉ lệ lỗi nhỏ tuỳ ý là không thể thực hiện được. Hay nói cách khác xác suất giải mã lỗi tiến đến 1 khi chiều dài của dãy cần truyền gia tăng. (cid:132) Định lý này nói cách khác nếu tốc độ truyền tin lớn hơn dung lượng kênh thì việc truyền không được đảm bảo có nghĩa là chúng ta không thể giải mã đúng được.
Trang 188 Lý thuyết Thông tin - Khoa Công Nghệ Thông Tin
![Trắc nghiệm Mạch điện: Tổng hợp câu hỏi và bài tập [năm hiện tại]](https://cdn.tailieu.vn/images/document/thumbnail/2025/20251118/trungkiendt9/135x160/61371763448593.jpg)
