lược đồ sửa lỗi tối ưu

LƯỢC ĐỒ SỬA LỖI TỐI ƯU

Mục tiêu

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

• Biết được vấn đề của bài toán,
• Hiểu Định nghĩa Hiệp hợp,
• Vận dụng để xây dựng lược đồ sửa lỗi theo các hiệp hợp,
• Vận dụng để xây dựng lược đồ sửa lỗi thông qua bộ sửa lỗi,
• Vận dụng tính Xác suất truyền đúng cho lược đồ sửa lỗi,
• Kiến thức đạt được sẽ là cơ sở để các bạn có thể ứng dụng cho việc thiết kế một hệ, thống mã hóa, giải mã và bảo mật thông tin.

Đặt vấn đề

Trong một hệ thống liên lạc truyền tin, bên cạnh các yêu cầu thiết bị (như nguồn phát, bộ mã hóa, kênh truyền, bộ giải mã,…) đảm bảo tốt cho việc truyền và nhận dữ liệu thì còn có các khía cạnh khác như phương pháp mã hóa và giải mã sao cho tối ưu là phần rất quan trọng trong hệ thống. Vấn đề luôn được đặt ra ở đây là làm thế nào để chỉ ra một phương pháp giải mã tối ưu, có nghĩa là hệ thống phải có khả năng phát hiện và sửa lỗi một cách chính xác nhất có thể có khi nhiễu xảy ra. Đây chính là vấn đề chính được thảo luận trong suốt bài học này.

Định nghĩa Hiệp hợp

Gọi W={w₁, w₂, …,w_s} là bộ mã kiểm tra chẵn lẻ.

V ={v₁, v₂, …, v2n size 12{v rSub { size 8{2 rSup { size 6{n} } } } } {}} là tập hợp các dãy n bit có thể nhận được ở cuối kênh.

Ta gọi một hiệp hợp của W trong V là tập hợp có dạng z + W (z là bộ lỗi)

Ví dụ: Cho ma trận kiểm tra chẵn lẻ sau:

Từ A, ta có thể xây dựng được bộ mã tương ứng sau: W={w’₀=0000, w’₁=0101, w’₂=1110, w’₃=1011}.

Ta có thể thấy rằng, các bộ lỗi một bit khác nhau có thể có là z={1000, 0100, 0010, 0001}. Do đó các hiệp hợp ứng với các bộ lỗi 1 bit sẽ là:

Trong đó: hiệp hợp i = w_i + z_i, các bạn có thể xét thêm các bộ lỗi sai 2 bit, 3 bit, … để được các hiệp hợp ứng với các bộ lỗi sai 2 bit, 3bit,….

Lược đồ sửa lỗi theo các hiệp hợp

Bước 1: Lập bảng các hiệp hợp ứng với các bộ lỗi cần thiết

• Dòng đầu tiên viết các từ mã w_i thuộc W.
• Các dòng tiếp theo ứng với cột w₀ = 00…00 viết các bộ lỗi z (các bộ lỗi 1 bit, 2 bit,…).
• Các dòng ở cột thứ i được xác định bởi z + w_i

Bước 2: Quá trình giải mã

Giải mã: khi nhận v, ta xác định cột thứ i chứa v và giải mã về w_i tương ứng.

Ví dụ: xây dựng lược đồ sửa lỗi theo các hiệp hợp cho bộ mã được sinh từ ma trận kiểm tra chẵn lẻ sau:

Từ A, ta có thể xây dựng được bộ mã tương ứng sau: W={w’₀=0000, w’₁=0101, w’₂=1110, w’₃=1011}.

Bước 1: Lập bảng các hiệp hợp ứng với các bộ lỗi cần thiết:

Ta xây dựng các hiệp hợp ứng với các bộ lỗi sai 1 bit. Vậy z={1000, 0100, 0010, 0001}.

(Bảng các hiệp hợp)

Bước 2: Quá trình giải mã:

Giả sử nhận v = 0111. Tra tìm v trên bảng các Hiệp hợp ta có v ở cột 1. Do đó, v được giải mã về w₁ = 0101.

Giả sử nhận v = 1010. Tra tìm v trên bảng các Hiệp hợp ta có v ở cột 2 hay cột 3. Do đó, v được giải mã về w₂ hay w_3, trong trường hợp này giải mã không chính xác. Đề nghị các bạn lưu ý và cho ý kiến của bạn về các trường hợp giải mã không chính xác này.

Lược đồ sửa lỗi thong qua bộ lỗi

Để xây dựng lược đồ sửa lỗi thông qua bộ sửa lỗi, ta dựa vào tính chất của bộ sửa lỗi. Như vậy ta có thể thấy lược đồ giải mã gồm 2 bước sau:

Bước 1: Lập bảng sửa lỗi: Bộ lỗi (Z) – Bộ sửa lỗi (C=A*Z).

Bước 2: Quá trình sửa lỗi

• Khi nhận được dãy n bit v thuộc V, ta xác định bộ điều lỗi C cho v với C=A.v

• Tra bảng sửa lỗi để tìm bộ lỗi z₀ ứng với C.
• Giải mã w=v+z₀.

Ví dụ minh họa lược đồ sửa lỗi 1 bit

Xét bộ mã được sinh từ ma trận

Bộ mã tương ứng được xác định là: w₁=000000, w₂=101101, w₃=111010, w₄=010111

(Đề nghị các bạn tham khảo phương pháp sinh mã chẵn lẻ và xây dựng lại bộ mã từ ma trận kiểm tra chẵn lẻ A).

Lược đồ sửa lỗi:

Bước 1: Lập bảng sửa lỗi: Bộ lỗi- Bộ điều chỉnh (e = 1)

Bộ lỗi (z’) Bộ điều chỉnh (C’=A.z)

Bước 2: Quá trình sửa lỗi

• Giả sử nhận v=001101, tính C = A.v = 1000
• Tra bảng sửa lỗi để tìm bộ lỗi z₀ ứng với C, ta có z₀ = 100000
• Giải mã w = v + z₀ = 001101 + 100000 = 101101 = w₂

Ví dụ minh họa lược đồ sửa lỗi 2 bit

Lược đồ sửa lỗi:

Bước 1: Lập bảng sửa lỗi: Bộ lỗi- Bộ điều chỉnh (e = 2)

010100 0101

(Tất cả các bộ 2 lỗi còn lại có trùng bộ điều chỉnh với các bộ ở trên)

Bước 2: Quy trình sửa lỗi

• Giả sử nhận v=100111, tính C = A.v = 1100
• Tra bảng sửa lỗi để tìm bộ lỗi z₀ ứng với C, ta có z₀ = 110000
• Giải mã w = v + z₀ = 100111 + 110000 = 010111 = w₄

Ví dụ minh họa lược đồ sửa lỗi 3 bit

Lược đồ sửa lỗi:

Bước 1: Lập bảng sửa lỗi: Bộ lỗi- Bộ điều chỉnh (e = 3)

(Tất cả các bộ 3 lỗi còn lại có trùng bộ điều chỉnh với các bộ ở trên)

Bước 2: Quy trình sửa lỗi

Giả sử nhận v=011001, tính C = A.v = 1101

Tra bảng sửa lỗi để tìm bộ lỗi z₀ ứng với C, ta có z₀ = 110100

Giải mã w=v + z₀ = 011001 + 110100 = 101101 = w₂

Chú ý:

Tổng số bộ điều chỉnh = 2^m. Trong một số trường hợp, bộ mã chẵn lẻ chỉ cho phép phát hiện lỗi trên đường truyền và không thể giải mã chính xác do tổng số bộ điều chỉnh = 2^m và số bộ lỗi có thể lớn hơn nhiều (so với tống số bộ điều chỉnh).

Xác suất truyền đúng

Gọi N_i là số bộ lỗi ứng với i lỗi có thể tự sửa, khi đó xác suất truyền đúng và tự điều chỉnh sẽ là:

Với n là độ dài từ mã

Ví dụ: xét trường hợp các ví dụ trên với n= 6 và tự sửa e = 3 bit lỗi. Áp dụng công thức trên ta có:

Bài tập

Cho ma trận kiểm tra chẵn lẻ sau:

• Xây dựng bộ mã kiểm tra chẵn lẻ.
• Minh họa quy trình sửa lỗi 1 bit.

Từ kết quả của bài tập 1, hãy minh họa lược đồ sửa lỗi thông qua bộ điều chỉnh trong các trường hợp lỗi 1 bit, 2 bit. Tính xác suất truyền đúng cho các trường hợp có thể tự sửa được.