kênh truyền rời rạc không nhớ

KÊNH TRUYỀN

Mục tiêu:

Trình bày mô hình truyền tin rời rạc từng ký tự mã độc lập lẫn nhau (phù hợp với đặc điểm của kênh). Mô hình này còn gọi là (Memoryless Discret Channel). Từ mô hình này người ta có thể xây dựng cách tính dung lượng kênh truyền và phương pháp phân loại đầu nhận để có thể giải mã tốt nhất.

KÊNH TRUYỀN RỜI RẠC KHÔNG NHỚ

Mục tiêu

Sau khi hoàn tất bài học này bạn có thể:

• Biết mô hình kênh truyền tin rời rạc không nhớ ở 2 khía cạnh vật lý và toán học.
• Khái niệm về lượng tin trên kênh truyền
• Định nghĩa dung lượng kênh truyền

Giới thiệu

Trước hết, ta có thể hiểu khái niệm kênh truyền rời rạc và không nhớ ở bài học này như sau: khái niệm truyền rời rạc ở đây là truyền tuần tự các ký tự độc lập nhau (hay truyền từng ký tự một), còn khái niệm không nhớ ở đây là chỉ xét mối quan hệ giữa ký tự truyền và ký tự nhận được tương ứng, không xét đến mối quan hệ giữa ký tự nhận được với ký tự nhận được trước đó.

Khái niệm về một kênh truyền rời rạc dựa vào phân bố xác suất của tín hiệu ra phụ thuộc vào tín hiệu vào và trạng thái của kênh truyền đã được chuẩn hóa bởi Feinstein (1958) và Wolfowitz (1961). Dung lượng kênh (Channel Capacity) được xác định chính xác nhờ Muroya (1953) và Fano (1961). Giải thuật và chương trình tính dung lượng kênh đã được viết bởi Eisenberg (1963).

Định lý cơ bản về truyền tin đã chỉ ra rằng “với dung lượng kênh cho trước luôn có thể tìm ra một phương pháp truyền tin với lượng tin nhỏ hơn dung lượng kênh và đạt sai số nhỏ hơn sai số cho phép bất kỳ”. Định lý cơ bản về truyền tin đã được Feinstein (1954, 1958) khảo sát. Các nhà khoa học Blackwell, Breinan (1958, 1959) và Thomasian (1961) đã lần lượt chỉnh lý để đạt chuẩn tốt hơn. Trong các nội dung tiếp theo của bài học, các bạn sẽ tìm hiểu về mô hình kênh truyền tin rời rạc không nhớ ở khia cạnh vật lý và toán học. Đặc biệt ở mô hình toán học sẽ chỉ ra cách xác định phân phối ở đầu ra dựa vào phân phối ở đầu vào.

Mô hình vật lý

Một thông báo được cấu tạo từ các ký hiệu của một bảng chữ cái ở đầu truyền (input) và được truyền trên kênh. Thông báo được nhận ở cuối kênh (hay đầu nhận-output) và được giải mã theo bảng chữ cái ở đầu truyền. Mặt khác, từng ký tự ở đầu nhận có thể quan hệ với các ký tự ở đầu nhận trước đó, các ký tự ở đầu truyền và trạng thái của kênh truyền. Để đơn giản, ở đây chúng ta chỉ xét mô hình vật lý như sau:

Xét từng ký tự ở đầu nhận chỉ phụ thuộc vào ký tự ở đầu truyền tương ứng với nó, nếu kênh truyền có nhiễu thì một ký tự ở đầu truyền có thể được diễn giải (nhiễu) ra nhiều ký tự khác nhau ở đầu nhận và do đó tạo ra một phân phối xác suất có điều kiện cho ký tự ở đầu nhận. Mô hình truyền tin rời rạc không nhớ là mô hình truyền tin chỉ xét mối quan hệ giữa ký tự truyền và ký tự nhận được tương ứng, không xét mối quan hệ giữa ký tự nhận được và ký tự nhận được trước đó.

Mô hình:

Mô hình toán học

Ta gọi:

• Tx={x₁, x₂, …, x_M} là bộ ký tự sinh mã ở đầu truyền (input).
• Ty={y₁, y₂,…,y_L} là bộ ký tự giải mã ở đầu nhận (output).
• Biến ngẫu nhiên X lấy giá trị (đã mã hóa) trên Tx và có phân phối p(X=x_i)=p(x_i) với i=1,..,M.
• Biến ngẫu nhiên Y lấy giá trị (giải mã) trên Ty và có phân phối xác suất có điều kiện: P(Y=y_j/X=x_i)=p(y_j/x_i)=p_ij với j=1,..,L.

Gọi A=||p_ij|| là ma trận truyền tin hay mô hình truyền tin của .

Với và p_ij = p(Y=y_j/X=x_i) = p(y_j/x_i) là xác suất nhận được giá trị y_j khi đã truyền giá trị x_i.

Tính phân phối đầu nhận:

Ta có:

Vậy p(yj)= PX’ .Aj(1)

Một các tổng quát: P’Y = P’X.A (2)

Trong đó:

• A_jlà cột thứ j của A
• P’_X = [p(x₁), p(x₂),…., p(x_M)].
• P’_Y = [p(y₁), p(y₂),…., p(y_M)].

Ví dụ xác định phân phối đầu nhận

Cho ma trận truyền tin như sau:

Xác suất truyền: p(x₁)=0.5 và p(x₂)=p(x₃)= 0.25.

Ta tìm phân phối của Y :

Ta có: P_X^’ =(0.5, 0.25, 0.25)

Áp dụng công thức (1) ở trên ta được:

p(y₁) = P_x^’ .A₁ = 0.375

p(y₂) = P_x^’ .A₂ = 0.3

p(y₃) = P_x^’ .A₃ = 0.325

=> PY’ =(0.375, 0.3, 0.325)

Lượng tin trên kênh truyền

Ví dụ: cho ma trận truyền tin như sau:

Xác suất truyền: p(x₁)=0.5 và p(x₂)=p(x₃)= 0.25.

X = {x₁,x₂,x₃} được xem như tập các ký tự truyền và Y ={y₁, y₂, y₃} là tập các ký tự nhận.

Tính lượng tin trên kênh truyền:

Ta tìm phân phối của Y :

Ta có: P_X^’ =(0.5, 0.25, 0.25)

Áp dụng công thức (1) ở trên ta được:

p(y₁) = P_x^’ .A₁ = 0.375

p(y₂) = P_x^’ .A₂ = 0.3

p(y₃) = P_x^’ .A₃ = 0.325

=> P_Y^’ =(0.375, 0.3, 0.325)

Tính các Entropy:

H(Y) = H(0.375, 0.3, 0.325) = 1.58 (bit)

H(Y/X=x₁) = H(0.5, 0.2, 0.3)= 1.49 (bit)

H(Y/X=x₂) = H(0.3, 0.5, 0.2)= 1.49 (bit)

H(Y/X=x₁) = H(0.2, 0.3, 0.5)= 1.49 (bit)

H(Y/X)= p(x₁).H(Y/X=x₁) + p(x₂).H(Y/X=x₂) + p(x₃).H(Y/X=x₃) = 1.49 (bit)

Lượng thông tin truyền trên kênh: I (X/Y)= I (Y/X)= H(Y) - H(Y/X) = 0,09 (bit)

Định nghĩa dung lượng kênh truyền

Dựa vào ma trận truyền tin A, ta có thể dễ dàng tính lượng tin trên kênh truyền.

I(X/Y)= H(X)-H(Y/X)

= H(Y)-H(X/Y)

= I(Y/X)

Ta có I(X/Y)= H(Y)-H(Y/X), trong đó:

H(Y)= H(P_X^’ .A) phụ thuộc vào P_X.

H(Y/X) phụ thuộc vào P_X

Vậy: I(Y/X) phụ thuộc hoàn toàn vào P_X và do đó I(Y/X) có thể đạt Max với P_X xác định nào đó.

Ta định nghĩa: là dung lượng của kênh truyền (ĐVT: bit).