nhóm cộng tính và bộ từ mã chẵn lẻ

NHÓM CỘNG TÍNH VÀ BỘ TỪ MÃ 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 Khái niệm nhóm cộng tính,

Biết các tính chất của bộ mã chẵn lẻ,

Vận dụng sinh ma trận kiểm tra chắn lẻ từ bộ mã kiểm tra chẵn lẻ.

Vận dụng tốt phương pháp sinh bộ mã kiểm tra chẵn lẻ từ các từ mã độc lập tuyến tính của bộ mã.

Khái niệm nhóm cộng tính.

Đặt vấn đề:

Như chúng ta đã biết, phương pháp sinh mã kiểm tra chẵn lẻ giúp ta sinh bộ mã kiểm tra chẵn lẻ với số từ mã tương ứng là s=2^k. Với phương pháp này, ta phải xác định từng từ mã một (bằng cách giải hệ phương trình tuyến tính nhị phân). Giả sử: k=5 ta phải xác định s=2⁵ =32 từ mã hay k=10 ta phải xác định s=2¹⁰=1024 từ mã,…Điều này sẽ mất nhiều thời gian nếu k càng lớn. Vấn đề đặt ra ở đây là tìm ra một phương pháp sinh bộ mã kiểm tra chẵn lẻ nhanh hơn về mặt thời gian. Phương pháp sinh mã kiểm tra chẵn lẻ dựa theo lý thuyết nhóm sẽ giải quyết vấn đề này.

Khái niệm nhóm cộng tính:

Nhóm G được gọi là một nhóm cộng tính nếu G có các tính chất:

Nhóm G là nhóm hoán vị (nhóm Aben) nếu ∀a,b thuộc G=> a + b = b + a.

Ví dụ:

- Tập hợp các số nguyên với phép + thông thường là nhóm Aben.

- Tập hợp các số nhị phân có độ dài n bit cùng với phép + trong Modulo 2 tạo thành nhóm Aben.

Tính chất của bộ mã chẵn lẻ

Tính tương đương của bộ mã nhóm cộng tính và bộ từ mã kiểm tra chẵn lẻ được thể hiện qua 2 định lý sau:

Định lý 1: tập hợp các từ mã trong bộ mã kiểm tra chẵn lẻ là một nhóm cộng tính.

(Đề nghị sinh viên chứng minh định lý này dựa vào các tính chất của nhóm cộng tính)

Định lý 2: Nếu tập hợp W là tập các dãy nhị phân với độ dài các dãy cùng bằng n và W là một nhóm Aben với phép cộng Modulo 2 thì W có thể xem như một bộ mã kiểm tra chẵn lẻ được sinh ra từ ma trận A có dạng như sau:

Trong đó:

- Ma trận A có m dòng và n cột.

- I_m : là ma trận đơn vị cấp m.

- k: là số dãy nhị phân (hay từ mã) độc lập tuyến tính lớn nhất.

- n: là độ dài của từ mã và m = n-k:

- bij: được xác định bằng cách dựa vào hệ phương trình tuyến tính (*) và k từ mã độc lập tuyến tính như sau:

Đoạn kiểm tra Đoạn thông tin

Thế k từ mã độc lập tuyến tính vào hệ pt (*) để tìm các b_ij => ma trận A.

Ví dụ minh họa

Xét tập hợp M gồm có 8 dãy nhị phân dài 6 bits như sau:

r₁ r₂ r₃ r₄ r₅ r₆

w’₀ = 0 0 0 0 0 0

w’₁ = 1 0 1 0 0 1

w’₂ = 1 1 0 0 1 0

w’₃ = 0 1 0 1 0 1

w’₄ = 0 1 1 0 1 1 (w’₁+w’₂)

w’₅ = 1 1 1 1 0 0 (w’₁+w’₃)

w’₆ = 1 0 0 1 1 1 (w’₂+w’₃)

w’₇ = 0 0 1 1 1 0 (w’₁+w’₂+w’₃)

Ta thấy {w₁, w₂, w₃} là tập hợp lớn nhất các từ mã độc lập tuyến tính từ tập hợp M:

w’₁ = 1 0 1 0 0 1

w’₂ = 1 1 0 0 1 0

w’₃ = 0 1 0 1 0 1

=> n=6 và k=3. => m = n – k = 3.

Như vậy: ma trận kiểm tra chẵn lẻ có dạng như sau:

Vậy ta có thể sử dụng nhóm M như là một bộ mã kiểm tra chẵn lẻ.

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

Bước khởi tạo:xác định các giá trị n, m, k, s.

Bước 1: sinh k từ mã độc lập tuyến tính (đltt).

Bước 2: cộng tổ hợp các từ mã:

+ Cộng các tổ hợp của 2 từ mã từ k mã đltt => có tổ hợp chập 2 của k từ mã.

----

+ Cộng các tổ hợp của k từ mã từ k từ mã đltt => có tổ hợp chập k của k từ mã.

Bước 3:Cộng s-1 từ mã đã tìm được để tìm từ mã cuối cùng => tổ hợp chập 0 của k= 1 từ mã.

Ví dụ sinh mã kiểm tra chẵn lẻ nhanh

Tìm bộ mã nhóm khi biết trước ma trận kiểm tra

Bước khởi tạo: n = 6, m = 3, k = 3, s = 2^k = 8.

Bước 1: Sinh k = 3 từ độc lập truyến tính: w’₁=001001, w’₂=111010, w’₃=110100

Bước 2: Cộng tổ hợp các từ mã.

+ Cộng các tổ hợp 2 từ mã đltt:

w’₄=w’₁+w’₂=110011

w’₅=w’₁+w’₃=111101

w’₆=w’₂+w’₃=001110

+ Cộng các tổ hợp 3 từ mã đltt:

w’₇=w’₁+w’₂+w’₃=001111

Bước 3: xác định từ mã cuối cùng:

w’₀=w’₁+w’₂+w’₃+w’₄+w’₅+w’₆+w’₇=000000

Bài tập

Sử dụng phương pháp sinh mã nhanh cho bộ mã từ ma trận kiểm tra A như sau:

Sử dụng phương pháp sinh mã nhanh cho bộ mã từ ma trận kiểm tra A trong các trường hợp sau: