lược đồ giải mã

LƯỢC ĐỒ GIẢI MÃ

Mục tiêu

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

• Biết đặt vấn đề bài toán giải mã,
• Hiểu các khái niệm cơ bản của kỹ thuật truyền tin,
• Biết và hiểu các dạng sai số cơ bản của kỹ thuật truyền tin,
• Hiểu phương pháp xây dựng lược đồ giải mã tối ưu,
• Vận dụng xây dựng lược đồ giải mã tối ưu và tính các dạng xác suất truyền sai.

Đặt vấn đề bài toán giải mã

Phân tích yêu cầu giải mã:

Khi truyền giá trị x_i, ta sẽ nhận được y_j.

Đối với kênh truyền không nhiễu thì y_j chính là x_i. Đối với kênh truyền có nhiễu thì y_j có thể khác x_i. Do đó ta cần tìm cách giải mã y_j về giá trị x_i khi kênh truyền có nhiễu.

Phép phân hoạch các giá trị ở đầu nhận:

Phép phân hoạch tập các giá trị ở đầu nhập y_j thuộc Y là phép phân chia tập Y thành các tập con B_i sao cho:

1.

(mọi i ≠ j)

2. Khi nhận y_j thuộc B_i thì giải mã về x_i.

Ví dụ bài toán giải mã

Cho tập các từ mã truyền X và tập các dãy n bit nhận được Y như sau:

X={0000, 0101, 1110, 1011}

Y={0000, 0001, 0010, 0011, 0100, 0101, 0110, 0111,

1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111}

Giả sử ta có thể phân hoạch tập Y thành các tập con B_i như sau:

B₁={0000, 1000, 0001, 0010}

B₂={0101, 1101, 0100, 0111}

B₃={1110, 0110, 1111, 1100}

B₄={1011, 0011, 1010, 1001}

Giả sử nhận y_j = 0011 thì giải mã về x₄ = 1011 vì y_j thuộc B₄.

Các khái niệm cơ bản của kỹ thuật truyền tin

Xét sơ đồ truyền tin như sau:

Diễn giải:

• Nguồn phát tín hiệu (hay thông báo) với vận tốc R (tín hiệu/giây).
• Tín hiệu được mã hóa từ bộ ký tự mã.
• Tín hiệu mã hóa được truyền trên kênh với vận tốc C (ký tự/giây), C đồng thời là dung lượng của kênh truyền.
• Tín hiệu truyền trên kênh có thể bị nhiễu với xác suất P(e).
• Trước khi nhận, tín hiệu mã hóa được giải mã theo một phương thức tối ưu và độ chính xác cao nhất có thể có.

Bài toán đặt ra ở đây: tìm giải pháp tạo mã sao cho sai số đầu nhận có xác suất nhỏ hơn ε bất kỳ (ε < P(e)) đồng thời với đồng bộ hóa: vận tốc phát thông báo ở nguồn R và vận tốc truyền tải ≤ C (C là dung lượng kênh).

Các khái niệm cơ bản:

Từ mã: là dãy n ký tự truyền hay dãy n ký tự nhận đúng.

Bộ mã (S,n): là tập hợp gồm S từ mã với độ dài mỗi từ mã đều bằng n và được ký hiệu là x⁽¹⁾, …, x^(s).

Lược đồ giải mã: là một hàm gán cho một dãy n ký tự nhận được y_j một từ mã của bộ mã W = {w₁, w₂, …, w_s}. Ký hiệu: g(y_j) = w_i

Lược đồ giải mã tối ưu: là lược đồ giải mã sao cho tổng xác suất truyền sai là nhỏ nhất hay tổng xác suất truyền đúng là lớn nhất.

Nghĩa là: khi nhận y_j thì ta giải mã về w_i^* sao cho:

P(w_i^*/y_j) = Max{P(w_k/y_j)}

mọi w_k thuộc W

Ví dụ minh họa các khái niệm cơ bản

Giả sử kênh truyền từng bit với C=1, nguồn phát thông báo với tốc độ R=2/5 bit/giây (R<C). Để thuận lợi cho mã hóa và giảm nhiễu, ta xét từng khoảng thời gian n = 5 giây. Như vậy trong khoảng thời gian n = 5 giây, ta có:

• Tập hợp các tín hiệu khác nhau là 2^nR = 4. Giả sử 4 tín hiệu là m₁, m₂, m₃, m₄.
• Số bit được phát ra là nR=2 bit và một tín hiệu dạng m_i được kết cấu bởi một dãy các bit.
• Quá trình mã hóa các tín hiệu m₁, m₂, m₃, m₄ cần_{chú ý là: mỗi mi cần được mã hóa với số bit tối đa là nC=5 bit. Vậy, ta có thể mã hóa các tín hiệu mi theo 2 cách sau:}

Cách 1:

m₁=00000

m₂=01101

m₃=11010

m₄=10111

Cách 2:

m₁=00

m₂=01

m₃=10

m₄=11

Nếu sử dụng cách 1 với độ dài 5 bit, trong đó 5 bit có thể hiểu là có 2 bit thông tin cần truyền và 3 bit con lại là 3 bit được bổ sung để phát hiện nhiễu theo một phương pháp nào đó sẽ được đề cập ở các nội dung tiếp theo sau. Với cách mã hóa này, ta có nhiều khả năng phát hiện và sửa sai do nhiễu.

Nếu sử dụng cách 2 thì trường hợp có 1 bit truyền sai sẽ dẫn đến trùng lặp sang một trong các tín hiệu khác. Ví dụ truyền m₁=00 và nhận 2 bit là 01 (do nhiễu), trong trường hợp này 01 chính là m₂, đây là một tín hiệu đúng nên ta không thể phát hiện có nhiễu hay không nhiễu.

Như vậy, trong khoảng thời gian truyền và dung lượng kênh cho phép, ta cần mã hóa mỗi tín hiệu càng dài càng tốt nhưng không được vượt quá độ dài mã cho phép. Trường hợp với thời gian n=5 và c= 1 bit thì nC=5 là số bit tối đa có thể truyền nên ta chỉ mã hóa tín hiệu với độ dài mã tối đa là 5 bit.

Các dạng sai số cơ bản

Xác suất truyền sai từ mã x_i:

Xác suất truyền sai trung bình:

Xác suất truyền sai lớn nhất:

Phương pháp xây dựng lượt đồ giải mã tối ưu

Theo công thức Bayes:

Ta có: P(w_k/y_j) = [p(w_k).p(y_j/w_k)] / p(y_j) với (mọi w_k thuộc W)

Từ định nghĩa lược đồ giải mã tối ưu:

⇒ tìm w_k sao cho P(w_k/y_j) → Max <=> p(w_k).p(y_j/w_k) → Max.

Như vậy, ta có thể xây dựng lược đồ giải mã tối ưu theo các bước sau:

Bước 0: Khởi tạo các B_i = ϕ (mọi i)

Bước lặp: xét với mọi y_j thuộc Y

+ Tính:

p(w₁).p(y_j/w₁)

p(w₂).p(y_j/w₂)

…

p(w_M).p(y_j/w_M)

+ So sánh các giá trị tính trên và chọn giá trị w*_i sao cho p(w*_i).p(y_j/w*_i)= Max {p(w_k).p(y_j/w_k)} (mọi w_k thuộc W)

+ B_i = B_i + {y_j} và g(y_j) = w*_i.

Minh họa xây dựng lược đồ giải mã tối ưu

Bài toán:

Cho ma trận truyền tin A và xác suất ở đầu truyền như sau:

Với p(x₁)=1/2; p(x₂)=p(x₃)=1/4. Hãy xây dựng lược đồ giải mã tối ưu.

Áp dụng phương pháp xây dựng lược đồ giải mã tối ưu:

Bước 0: B₁={}; B₂={}; B₃={};

Bước 1: Nhận giá trị y₁, ta tính:

+ p(x₁).p(y₁/x₁)= 1/2.1/2 = 1/4 (Max)

+ p(x₂).p(y₁/x₂)= 1/4.1/3 = 1/12

+ p(x₃).p(y₁/x₃)= 1/4.1/6 = 1/24

Do p(x₁).p(y₁/x₁) lớn nhất nên liệt kê y₁ vào tập hợp B₁ tương ứng với x₁.

=> B₁={y₁}.

Bước 2: Nhận giá trị y₂, ta tính:

+ p(x₁).p(y₂/x₁)= 1/2 . 1/3 = 1/6 (Max)

+ p(x₂).p(y₂/x₂)= 1/4 . 1/6 = 1/24

+ p(x₃).p(y₂/x₃)= 1/4 . 1/2 = 1/8

Do p(x₁).p(y₁/x₁) lớn nhất nên liệt kê y₂ vào tập hợp B₁ tương ứng với x₁.

=> B₁={y₁, y₂}.

Bước 3: Nhận giá trị y₃, ta tính:

+ p(x₁).p(y₃/x₁)= 1/2 . 1/6 = 1/12

+ p(x₂).p(y₃/x₂)= 1/4 . 1/2 = 1/8 (Max)

+ p(x₃).p(y₃/x₃)= 1/4 . 1/3 = 1/12

Do p(x₁).p(y₂/x₁) lớn nhất nên liệt kê y₃ vào tập hợp B₂ tương ứng với x₂.

=> B₂={y₃}.

Kết quả:

Phân hoạch: B₁={y₁, y₂}, B₂=

{y₃} và B₃={}.

Lược đồ giải mã tối ưu:

Minh họa cách tính các sai số

Xét lại ví dụ minh họa xây dựng lược đồ giải mã tối ưu trên, ta có:

- Ma trận truyền tin A:

- Xác suất ở đầu truyền: p(x₁)=1/2; p(x₂)=p(x₃)=1/4.

• Lược đồ giải mã tối ưu:

- Phân hoạch: B₁={y₁, y₂}, B₂={y₃} và B₃={}.

Tính các xác suất truyền sai:

Xác suất truyền sai một từ mã:

Bài tập 1

Cho ma trận truyền tin sau:

Biết xác suất ở đầu truyền: p(x₁)=5/10, p(x₂)=3/10, p(x₃)=2/10.

• Tính dung lượng kênh truyền.
• Xây dựng lược đồ giải mã tối ưu.
• Tính các sai số p(e) và p_m(e).

Cho ma trận truyền tin sau:

Biết xác suất ở đầu truyền: p(x₁)=1/3, p(x₂)=1/3, p(x₃)=1/3.

• Tính dung lượng kênh truyền.
• Xây dựng lược đồ giải mã tối ưu
• Tìm các sai số p(e) và p_m(e).

Bài Tập 2

Cho ma trận truyền tin sau:

Biết p(x₁)=1/2, p(x₂)=1/4, p(x₃)=1/4.

• Tính dung lượng kênh truyền.
• Xây dựng lược đồ giải mã tối ưu.
• Tính các sai số p(e) và p_m(e).

Cho ma trận truyền tin sau:

Biết xác suất truyền p(x₁)=0.4, p(x₂)=0.4, p(x₃)=0.2.

• Tính dung lượng kênh truyền.
• Xây dựng lược đồ giải mã tối ưu.
• Tính các sai số p(e) và p_m(e).