phương pháp sinh mã xoay vòng

PHƯƠNG PHÁP SINH MÃ XOAY VÒNG

Mục tiêu

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

• Hiểu các phương pháp sinh mã vòng,
• Biết bảng liệt kê một số đa thức đặc trưng,
• Vận dụng để sinh mã vòng theo nhiều cách khách nhau.

Đặt vấn đề

Để sinh bộ mã kiểm tra chẵn lẻ, ta có thể dựa theo nhiều phương pháp khác nhau như: sinh mã dựa theo lý thuyết nhóm, mã Hamming,... Vấn đề đặt ra ở đây là làm sao để sinh bộ mã xoay vòng với độ dài n bit và m bit kiểm tra chẵn lẻ. Phương pháp sinh mã xoay vòng dựa trên lý thuyết về đa thức đặc trưng nhị phân của thanh ghi giúp ta có cái nhìn tổng quát về vấn đề sinh bộ mã xoay vòng theo nhiều cách khác nhau.

Phương pháp sinh bảng mã xoay vòng

Để sinh mã xoay vòng độ dài n bit với m bit kiểm tra và k bit thông tin, ta có thể thực hiện theo các bước sau:

Bước 1: tìm 2 đa thức g_m(x)=a₀ + a₁x+ a₂ x²+ …+a_m-1x^m-1 + x^m

và h_k(x)=h₀ + h₁x+ h₂x² + …+h_k-1x^k-1 + x^k sao cho (xⁿ + 1) = g_m(x)* h_k(x).

Nếu tồn tại (xⁿ + 1) = g_m(x)* h_k(x) thì chuyển sang bước 2

Ngược lại không thể sinh bộ mã vòng theo yêu cầu.

Bước 2: ta có thể sinh bộ mã xoay vòng theo các cách như dưới đây:

Cách 1: Chọn đa thức g_m(x)=a₀ + a₁x+ a₂ x²+ …+a_m-1x^m-1 + x^m

=> a₀, a₁, a₂,…, a_m-1

=> thanh ghi => ma trận đặc trưng T

=> chu kỳ n => ma trận kiểm tra chẵn lẻ A.

=> Bộ mã xoay vòng.

Cách 2: chọn đa thức g_m(x)=a₀ + a₁x+ a₂ x²+ …+a_m-1x^m-1 + x^m

=> a₀, a₁, a₂,…, a_m-1

=> Sinh nhanh k từ mã độc lập tuyến tính với từ mã sinh độc lập tuyến tính đầu tiên có dạng: w₁=a₀a₁a₂…a_m-11000…00 => Bộ mã xoay vòng.

k-1 bit 0

Cách 3: chọn h_k(x)=h₀ + h₁x+ h₂x² + …+h_k-1x^k-1 + x^klàm đa thức sinh ma trận kiểm tra chẵn lẻ cho bộ mã vòng có dạng:

=> Sinh bộ mã xoay vòng theo Phương pháp sinh nhanh bộ mã xoay vòng.

Nhận xét: kết quả theo 3 cách sinh bộ mã xoay vòng nói trên la như nhau (cho cùng bộ mã).

Ví dụ minh họa 1

=> Bộ mã xoay vòng vớin=14, m=4, k=11.

Ví dụ minh họa 2

Chọn đa thức gm(x)= 1+x+x4 => a0 = 1, a1 = 1, a2 = 0, a3 = 0.

Bước 1: Sinh mã xoay vòng đầu tiên

w1 =110010000000000

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

w2 =011001000000000

w3 =001100100000000

w4 =000110010000000

w5 =000011001000000

w6 =000001100100000

w7 =000000110010000

w8 =000000011001000

w9 =000000001100100

w10=000000000110010

w11=000000000011001

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

(215 - 11) từ mã còn lại được xác định bằng cách cộng tổ hợp 2, 3, 4,.., k = 11 từ mã từ k=11 từ mã độc lập tuyến tính.

Ví dụ minh họa 3

Chọn h_k(x)= 1+ x + x² + x³ +x⁵ + x⁷ + x⁸ + x¹¹làm đa thức sinh ma trận kiểm tra chẵn lẻ cho bộ mã vòng => h₀ = 1, h₁ = 1, h₂ = 1, h₃ = 1, h₄ = 0, h₅ = 1, h₆ = 0, h₇ = 1, h₈ =1, h₉ = 0, h₁₀ = 0.

kê một số đa thức đặc trưng

Bài tập

Tìm bộ mã vòng có độ dài 7 bit.

Tìm thanh ghi sinh bộ mã vòng có độ dài 15 bit.

Tìm thanh ghi sinh bộ mã vòng có độ dài 31 bit.