mã xoay vòng

MÃ XOAY VÒNG

Mục tiêu

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

• Biết cách xác định ma trận kiểm tra chẵn lẻ cho (hay còn gọi là mã vòng),
• Hiểu định nghĩa ,
• Vận dụng xây dựng bộ ,
• Vận dụng phương pháp sinh nhanh bộ để sinh bộ mã kiểm tra chẵn lẻ.

Ma trận kiểm tra chẵn lẻ

Định nghĩa: ma trận kiểm tra chẵn lẻ được thiết kế từ thanh ghi lùi từng bước là ma trận có dạng sau:

A=[x⁽⁰⁾| T x⁽⁰⁾|T² x⁽⁰⁾ |…|T^n-1 x⁽⁰⁾] với n là chu kỳ của thanh ghi (n > m)

Trong đó:

• T là ma trận đặc trưng của thanh ghi.
• x⁽⁰⁾ ≠ 0: là giá trị khởi tạo của thanh ghi.
• n : là chiều dài của từ mã và cũng là chu kỳ của thanh ghi.
• m: là số bit kiểm tra hay số bit của thanh ghi.

Ví dụ: xét lại ví dụ tìm chu kỳ thanh ghi, nếu chọn giá trị khởi tạo của thanh ghi là x⁽⁰⁾ = 1 thì ta có ma trận kiểm tra với chu kỳ n=6 như sau:

Định nghĩa

Mã xoay vòng là mã kiểm tra chẵn lẻ được sinh ra từ ma trận kiểm tra chẵn lẻ ứng với chu kỳ n của thanh ghi lùi từng bước có dạng như:

A=[x⁽⁰⁾| Tx⁽⁰⁾|T²x⁽⁰⁾ |…|T^n-1x⁽⁰⁾ ]

Ví dụ: xét lại ma trận kiểm tra chẵn lẻ ở trên

Ta có n = 6, m = 3, k = 2 => s = 2^k = 2² = 4 từ mã.

Áp dụng Phương pháp sinh mã nhanh bộ mã kiểm tra chẵn lẻ ta có bộ mã kiểm tra chẵn lẻ gồm 4 từ mã sau : w₀ = 000000, w­₁ = 101010, w­₂ = 010101, w­₄ = 111111, đây chính là một trong các bộ sinh từ thanh ghi lùi từng bước nêu trên (Các bước sinh mã nhanh đề nghị các bạn tự làm)

Phương pháp sinh nhanh bộ

Cách sinh nhanh k từ mã độc lập tuyến tính của bộ mã vòng từ a₀,a₁, a₂, …, a_m-1:

Bước 3: xác định các từ mã còn lại của bộ mã

Các từ mã còn lại gồm (2^k – k từ mã) được xác định bằng cách cộng tổ hợp của 2, 3, …, k từ mã từ k từ mã độc lập tuyến tính ở trên.

Ví dụ sinh nhanh bộ

Cho thanh ghi lui từng bước như hình sau:

Từ thanh ghi, ta có: m=4, n=6, a₀=1, a₁=0, a₂=1, a₃=0.

Bước 1: Sinh đầu tiên

w₁=101010

Bước 2: Sinh k -1 từ mã độc lập tuyến tính còn lại

w₂=010101

Bước 3: Xác định các từ mã còn lại của bộ mã

w₃ =111111 (w₁+w₂), w₀ =000000 (w₁+w₂ + w₃)

Bộ mã vòng vừa sinh là W={000000, 101010, 010101, 111111)

Bài tập

Cho thanh ghi lùi từng bước sau:

• Tìm ma trận kiểm tra chẵn lẻ có số cột n > 4
• Từ kết quả câu a, xác định bộ tương ứng.
• Tìm bộ theo phương pháp sinh nhanh bộ

Cho thanh ghi lùi từng bước sau:

• Tìm ma trận kiểm tra chẵn lẻ có số cột n > 4
• Từ kết quả câu a, xác định bộ tương ứng.
• Tìm bộ theo phương pháp sinh nhanh bộ .