7/2/2010
1
Chương 3:
Kênh rời rạc không phụ
thuộc thời gian
3.2 Phương án giải mã tối ưu. Định
lý căn bản của LTTT
Giải mã
•Gọi x1, x2, …, xMvà y1, y2, …, yLlần lượt là các ký
tựinput và output.
•Một phương án giải mã là một phép tương ứng
mỗi ký tựoutput yjvới một ký tựinput xj*. Khi
nhận được yjta sẽgiải mã thành xj*
•Giải mã là phân hoạch tập ký tựoutput thành các
tập B1, …, BMsao cho mỗi ytrong Bisẽgiải mã
thành xi
•Một phương án giải mã có thểxem nhưmột kênh
deterministic với tập ký tựinput là y1, y2, …, yL
và tập ký tựoutput là x1, x2, …, xM
7/2/2010
2
Huỳnh Văn Kha
7/2/2010
2
Ví dụ
Xác
suất
X
1/2 x1
1/4 x2
1/4 x3
7/2/2010Huỳnh Văn Kha
3
Y
y1
y2
y3
Z
x1
x2
x3
1
1
1/2
1/2
Bài toán giải mã
•Cho trước input, xây dựng phương án giải mã sao
cho xác suất sai là nhỏnhất
•Giảsửyjtương ứng với xj*
•Gọi xác suất đúng là p(e’), ta có:
•Kênh và input cho trước nên các p(yj)không đổi
•Với mỗi yjcho trước chỉcần chọn xj*sao cho
p(xj*|yj)là lớn nhất
7/2/2010Huỳnh Văn Kha
4
7/2/2010
3
Trường hợp input ñồng xác suất
•Nếu input là đồng xác suất thì
•Với ycốđịnh thì việc cực đại p(xi|y) tương đương
với việc cực đại p(y|xi)
•Nhưvậy với phân phối đều của input thì phương
án giải mã tối ưu là với mỗi ycho trước chọn xi
sao cho p(y|xi)là cực đại
•Ta sẽxét kỹhơn vấn đềnày trong chương 4
7/2/2010Huỳnh Văn Kha
5
Ví dụ
•Xét ma trận kênh
•Gải sửp(x1) = ½, p(x2) = p(x3) = ¼
•Tìm phương án giải mã tối ưu và tính xác suất sai
7/2/2010Huỳnh Văn Kha
6
1/2 1/3 1/6
1/6 1/2 1/3
1/3 1/6 1/2
y1y2y3
x1
x2
x3
7/2/2010
4
ðịnh lý căn bản của LTTT
•Giảsửnguồn sinh ra dãy các ký tựnhịphân với
định lượng không đổi Rbit/giây, và định lượng
truyền của nguồn không quá 1 bit/giây
•Trong ngiây, nguồn sinh nR ký tự
•Tổng sốmẫu tin có thểcó trong ngiây là 2nR
•Chú ý 2nR có thểkhông nguyên, trong trường hợp
đó, ta lấy [2nR] (phần nguyên của 2nR)
•Ta cũng không quan tâm trường hợp sốký tựcủa
nguồn không phải là 2. Vì nếu sốký tựmã là Dvà
nguồn sinh Ský tự/giây, thì trong ngiây, nguồn
sinh DnS = 2nSlog D. Và có thểxem nó nhưnguồn
nhịphân với định lượng R = S log D
7/2/2010Huỳnh Văn Kha
7
ðịnh lý căn bản của LTTT
•Thay vì truyền từng ký tựqua kênh, ta sẽmã hóa
mỗi block nký tự
•Do định lượng truyền không quá 1 bit/giây nên
sốký tựmã mã hóa mỗi block không quá nký tự
•Đểgiữđịnh lượng sinh của nguồn là R, ta cần 2nR
từmã chiều dài ≤ n
•Ý tưởng cơbản của định lý là cho trước ε> 0, nếu
chọn nđủlớn, ta có thểtìm được 2nR từmã và
một cách giải mã sao cho sai sốđều < ε, nghĩa là
< εbất chấp từmã nào được truyền qua kênh
7/2/2010Huỳnh Văn Kha
8
7/2/2010
5
ðịnh lý căn bản của LTTT
•Cái giá phải trảlà ta cần phải chờngiây trước khi
mã hóa nguồn tin, cũng có thểphải tốn thêm thời
gian chờdo việc mã hóa và giải mã
•Thêm vào đó, phương án mã hóa và giải mã
trong định lý này rất phức tạp và khó thực hiện
trong thực tế
7/2/2010Huỳnh Văn Kha
9
ðịnh lý căn bản của LTTT
•Ví dụ, xét R = 2/5 và n = 5. Trong 5giây, sốmẫu
tin có thểcó do nguồn sinh ra là 2nR = 4. Gọi
chúng là m1, m2, m3, m4
•Ta gán cho mỗi mimột dãy nhịphân độdài ≤ 5
7/2/2010Huỳnh Văn Kha
10
m100000
m201101
m311010
m410111
m100
m201
m310
m411