mã kiểm tra chẵn lẻ

MÃ KIỂM TRA CHẴN LẺ

Mục tiêu:

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

• Hiểu bộ ,
• Hiểu phương pháp kiểm tra chẵn lẻ,
• Biết tính chất cơ bản của phương pháp kiểm tra chẵn lẻ,
• Hiểu và vận dụng tốt phương pháp sinh ,
• Hiểu và vận dụng tốt Định lý quan hệ giữa độ dài mã n, số bit kiểm tra m và số lỗi tự sửa e,
• Vận dụng cho các bài học tiếp theo.

Bộ

Bộ là bộ mã gồm s từ mã, trong đó mỗi từ mã có dạng sau:

Ghi chú: trong một số trường hợp sinh mã theo phương pháp kiểm tra chẵn lẻ, thứ tự các bit kiểm tra và các bit thông tin có thể xen kẻ nhau (theo một thứ tự nào đó, chẳng hạn như mã Hamming,…) hay cũng có thể theo một thứ tự khác (theo quy ước khác). Ở đây, ta chọn thứ tự các bit kiểm tra chẵn lẻ và các bit thông tin như trên để dễ tính toán nhưng vẫn mất tính tổng quát hóa.

Trong đó: w’ viết theo dong là chuyển vị của w (w được viết theo cột)

+ r_i: là bit thứ i của từ mã ( 1<_ i <_ n).

+ n: độ dài của từ mã hay số bit của từ mã chẵn lẻ.

+ m: số bit kiểm tra.

+ k = n-m: số bit thông tin => s=2^k (vì với k bit thông tin thì ta chỉ có thể biểu diên tối đa 2^k trạng thái thông tin k bit).

+ Đoạn kiểm tra: gồm m bit dùng để kiểm tra mã sai.

+ Đoạn thông tin: gồm k bit thông tin.

Mỗi đoạn mã thông tin có duy nhất một đoạn mã kiểm tra và được xác định bởi hệ phương trình tuyến tính nhị phân sau:

Gọi

Ma trận A được gọi là ma trận kiểm tra chẵn lẻ có hạng là m (hay Rank(A) = m).

Các phép toán trong Modulo 2 (+,-):

0 + 1 = 1 + 0 = 1; 0 – 1 = 1 – 0 = 1;

1 + 1 = 1 – 1 = 0;

Phương pháp kiểm tra chẵn lẻ

Gọi w’=r₁r₂…r_n là từ mã truyền (hay dãy n bit truyền) và v’=r₁r₂…r_n là dãy n bit nhận được.

Qui ước:v’, w’ (lần lượt là chuyển vị của v và w) được viết theo dòng. Còn v, w được viết theo cột.

Nếu A.v = 0 thì v = w, ta gọi v là chẵn (trường hợp nhận đúng)

Nếu A.v khác 0 thì v khác w, ta gọi v là lẻ (trường hợp nhận sai).

Ta gọi z = v-w là bộ lỗi giữa v và w. Nghĩa là tại các vị trí z = {0} thì bit nhận được tương ứng là bit đúng và tại các vị trí z = {1} thì bit nhận được tương ứng là bit sai (hay bit lỗi).

Ta gọi C = A.v là bộ sửa lỗi (hay bộ điều chỉnh lỗi).

Ta có C = A.z = A.(v-w) = A.v-A.w = A.v => C = A.v = A.z

Tính chất của bộ sửa lỗi: dãy n bit nhận được v và bộ lỗi tương ứng có cùng bộ điều chỉnh.

Phương pháp sinh

Giả sử: cho trước ma trận kiểm tra chẵn lẻ A với Rank(A) = m.

Tìm bộ mã chẵn lẻ W={w₁, w₂, w₃,…,w_s}

Bước 0: Xác định các giá trị n, m, k, s

Độ dài của từ mã n= số cột của ma trận A.

Số bit kiểm tra m= số dòng của ma trận A.

Số bit thông tin: k = n-m.

Số từ mã s=2^k của bộ mã.

Bước i: Tìm các từ mã thứ i (1<_ i <_ s):

Gọi kp_i là triển khai nhị phân k bit của số i

Từ mã cần tìm là: w’_i=r₁r₂..r_mkp_i

Giải hệ phương trình A.w_i=0 để tìm m bit kiểm tra ứng với k bit thông tin (kp_i) đã biết

=> từ mã w_i

Ví dụ sinh

Xây dựng bộ được sinh từ ma trận kiểm tra A như sau:

Bước 0 :

n=6 (= số dòng của ma trận A)

m=3 (= số cột của ma trận A)

Số bit thông tin k = n – m = 3 => Số từ mã s=2^k=8 từ mã.

Bước i: Tìm từ mã thứ i (1<_ i <_ s):

w’₁=r₁r₂r₃000 (000 là triển khai nhị phân k=3 bits của số i=0)

w’₁=r₁r₂r₃001 (001 là triển khai nhị phân k=3 bits của số i=1)

w’₂=r₁r₂r₃010 (010 là triển khai nhị phân k=3 bits của số i=2)

w’₃=r₁r₂r₃011 (011 là triển khai nhị phân k=3 bits của số i=3)

w’₄=r₁r₂r₃100 (100 là triển khai nhị phân k=3 bits của số i=4)

w’₅=r₁r₂r₃101 (101 là triển khai nhị phân k=3 bits của số i=5)

w’₆=r₁r₂r₃110 (110 là triển khai nhị phân k=3 bits của số i=6)

w’₇=r₁r₂r₃111 (111 là triển khai nhị phân k=3 bits của số i=7)

Giải hệ phương trình A.w₁=0

Giải hệ phương trình A.w₂=0

Giải tương tự cho các trường hợp còn lại ta có:

w’₀=000000, w’₃=110011, w’₄=110100,

w’₅=111101, w’₆=001110, w’₇=000111.

=> W={000000, 001001, 111010, 110011, 110100, 111101, 001110, 000111}

Định lý quan hệ giữa độ dài mã n, số bit kiểm tra m và số lỗi tự sửa e

Điều kiện cần (Cận Hamming):

Điều kiện cần để bộ mã chẵn lẻ có độ dài n bit có thể tự sửa được e bit lỗi với k bit thông tin và m bit kiểm tra là:

Điều kiện đủ ( ĐK Vasharmov-Gilbert-Sacks):

Điều kiện đủ để bộ có độ dài n bit với m bit kiểm tra chẵn lẻ có thể tự sửa được e bit lỗi là:

c

Ghi chú:

Ví dụ tìm m nhỏ nhất từ n và e

Giả sử biết trước n=7 và e=1. Tìm số bit kiểm tra tối thiểu cần thiết của bộ mã chẵn lẻ.

Theo định lý điều kiện cần (Cận Hamming):

Vậy số bit kiểm tra tối thiểu cần thiết là m = 3.

Ví dụ tìm e lớn nhất từ m và n

Giả sử cho trước m=3, k=2. Tìm số bit lỗi lớn nhất có thể tự sửa e?

Theo định lý điều kiện đủ (ĐK Vassharmov-Gilbert-Sacks):

Vậy số bit lỗi lớn nhất có thể tự sửa là e = 1.

Bài tập

Xây dựng bộ được sinh từ ma trận kiểm tra A như sau:

Tìm bộ được sinh từ ma trận kiểm tra A như sau:

Gợi ý giải bài tập 1 & 2: dựa vào phương pháp sinh và tham khảo ví dụ sinh .

Xét bộ độ dài 15 bit có thể tự sửa được 1 bit lỗi trên đường truyền, hãy cho biết số bit kiểm tra chẵn lẻ tối thiểu?

Xét bộ độ dài 8 bit với 4 bit kiểm tra chẵn lẻ. Hãy cho biết số lỗi tự sửa tối đa của bộ mã?

Gợi ý giải bài tập 3 & 4: dựa vào đinh lý Điều kiện cần (Cận Hamming) và Điều kiện đủ (ĐK Varshamov-Gilbert-Sacks).