nguyên lý khoảng cách nhỏ nhất hamming

SỬA LỖI

Mục tiêu: Xây dựng nguyên tắc sửa lỗi dựa vào khoảng cách Hamming. Trên nguyên tắc này, phương pháp sửa lỗi “kiểm tra chắn lẻ (parity check)” được xây dựng và tạo ra quy trình sửa lỗi tối ưu và phù hợp với công nghệ truyền tin hiện nay.

NGUYÊN LÝ KHOẢNG CÁCH NHỎ NHẤT HAMMING

Mục tiêu:

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

• Định nghĩa khoảng cách Hamming
• Kênh truyền đối xứng nhị phân và lược đồ giải mã tối ưu
• Quan hệ giữa xác suất giải mã và khoảng cách Hamming
• Nguyên lý khoảng cách nhỏ nhất của Hamming.

Khoảng cách Hamming

Định nghĩa:cho v₁ và v₂ là 2 dãy nhị phân dài n bit, ta gọi khoảng cách Hamming giữa 2 dãy v₁, v₂ là số bit tương ứng khác nhau. Ký hiệu: d(v₁, v₂).

Ví dụ:

v₁=10101010

v₂=10101111

Ta nhận thấy rằng bit thứ 6 và bit thứ 8 giữa giữa v₁ và v₂ là khác nhau nên số bit tương ứng khác nhau giữa v₁ và v₂ là 2. Do đó, ta nói khoảng cách Hamming giữa v₁ và v₂ là 2 hay d(v₁, v₂) = 2

Kênh truyền đối xứng nhị phân và lược đồ giải mã tối ưu

Xét kênh truyền đối xứng nhị phân. Giả sử ta truyền các dãy từ mã nhị phân có độ dài n bits với xác suất truyền sai 1 bit là beta.

1-beta

Gọi W = {w₁, w₂,…,w_s} là tập s từ mã truyền, độ dài mỗi từ mã đều bằng n bit.

V = {v₁, v₂,…., v₂ⁿ} là tập các dãy n bit nhận được ở cuối kênh với W có phân phối đều, xác suất để nhận v_j khi truyền w_i là p(v_j/w_i) = p_ij.

Theo lược đồ giải mã tối ưu ta có: khi nhận v_j thì giải mã về w_i^* sao cho:

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

(∀w_i ∈ W)

Ta có: P(w_k/y_j) = [p(w_k).p(y_j/w_k)] / p(y_j) với (∀w_k ∈ W)

=> P(w_k/y_j) → Max <=> p(w_k).p(y_j/w_k) → Max.

Do W có phân phối đều nên P(w_k/y_j) → Max <=> p(y_j/w_k) → Max

Vậy: để tìm w_i^* sao cho P(w_i^*/v_j) = Max{P(w_k/v_j)} ta chỉ cần tìm w_i^* sao cho

P(v_j/ w_i^*) = Max{P(v_j/ w_k)} (chỉ dựa vào ma trân truyền tin A)

Ví dụ kênh truyền đối xứng nhị phân

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

dựa vào lược đồ giải mã tối ưu ta có:

• Nhận v₁ giải mã về w₁
• Nhận v₂ giải mã về w₃
• Nhận v3 giải mã về w2.

Quan hệ giữa xác suất giải mã và khoảng cách Hamming

Giả sử nhận được v:

Xét 2 từ mã w₁ và w₂ cần chọn để giải mã cho v.

Nhận xét: xác suất giải mã càng lớn thì khoảng cách Hamming càng nhỏ.

Nguyên lý Hamming

Định lý: trên kênh truyền đối xứng nhị phân với s từ mã ở đầu truyền có độ dài n bit, lược đồ giải mã tối ưu có thể thay thế bằng lược đồ giải mã theo khoảng cách Hamming với nguyên lý: nếu nhận được v, ta sẽ giải ra w*_i

sao cho d(v,w*_i)=Min d(v,w_k) (với ∀w_k ∈ W).

Ví dụ: xét bộ mã W={w₁=00000, w₂=10011, w₃=11100, w₄=01111}

Giả sử nhận được dãy v=01011.

ta có: d(v,w₁)=3; d(v,w₂)=2; d(v,w₃)=4; d(v,w₄)=1.

vậy v được giải về w₄ vì khoảng cách Hamming giữa v và w₄ là nhỏ nhất.

Bài tập

1. Cho bộ mã W={w₁=000000, w₂=101010, w₃=111000, w₄=111111} và nhận được dãy v=010111, khi đó giải mã về từ mã nào? diễn giải?

2. Cho bộ mã W={w1=000000, w2=010101, w3=000111, w4=111111} và Nhận được dãy v=010111, khi đó giải mã về từ mã nào? diễn giải?