đa thức đặc trưng của thanh ghi

ĐA THỨC ĐẶC TRƯNG CỦA THANH GHI

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 ,
• Hiểu Quan hệ giữa chu kỳ n, đa thức đặc trưng và đa thức (xⁿ + 1),
• Vận dụng sinh thanh ghi lùi từng bước,
• Làm cơ sở để vận dụng sinh bộ mã vòng.

Định nghĩa

Định nghĩa: có ma trận đặc trưng là T là đa thức có dạng

g_m(x)=a₀ + a₁x+ a₂ x²+ …+a_m-1x^m-1 + x^m.

với a₀, a₁, a₂,…, a_m-1 là các công tắc của thanh ghi và m là số bit của thanh ghi

Ví dụ: xét lại thanh ghi như hình sau:

a₀ = 1, a₁= 0, a₂ = 1, a₃ = 0

Đa thức đặc trưng của thanh ghi có dạng: g_m(x)=1 + x² + x⁴.

Quan hệ giữa chu kỳ n, đa thức đăc trưng và đa thức (xⁿ + 1)

Đa thức đặc trưng của thanh ghi g_m(x)=a₀ + a₁x+ a₂ x²+ …+a_m-1x^m-1 + x^m luôn chia hết đa thức (xⁿ + 1).

Ví dụ: xét lại thanh ghi lui từng bước như hình sau:

Từ thanh ghi ta có thể xác định các kết quả sau:

• a₀ = 1, a₁= 0, a₂ = 1, a₃ = 0
• Đa thức đặc trưng của thanh ghi có dạng: g₄(x)=1 + x² + x⁴.
• Thanh ghi này có chu kỳ n = 6.

Thực hiện phép chia đa thức (x⁶ + 1) : (1 + x² + x⁴)= (x² + 1) => chia hết.

Ghi chú: phép toán trên đa thức nhị phân vẫn là phép toán Modulo 2.

Ví dụ: xét lại thanh ghi lui từng bước như hình sau:

a₀ = 1, a₁= 0, a₂ = 1, a₃ = 0

có dạng: g₄(x)=1 + x² + x⁴.

thanh ghi này có chu kỳ n = 6 và (x⁶ + 1) : 1 + x² + x⁴ = x² + 1.

Thủ tục sinh thanh ghi lùi từng bước

Để sinh thanh ghi lùi từng bước với số bit là m và có chu kỳ n, ta có thể thực hiện theo các bước sau:

Bước 1: xác định

• 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ì ta chọn g_m(x) làm đa thức đặc trưng cho thanh ghi (vì số bit kiểm tra của bộ mã là m) và thực hiện bước 2.
• Ngược lại: không tồn tại thanh ghi theo yêu cầu.

Bước 2: vẽ thanh ghi

Từ g_m(x)=a₀ + a₁x+ a₂ x²+ …+a_m-1x^m-1 + x^m => a₀, a₁, a₂,…, a_m-1 => thanh ghi có dạng:

Ví dụ minh họa

Thiết kế thanh ghi có m=3 bit và chu kỳ n=7, ta thực hiện theo 2 bước sau:

Bước 1: Xác định

Ta có (x⁷ + 1) : (1 + x² + x³) = (1 + x² + x³ + x⁴)

Do m=3 nên chọn g₃(x) = (1 + x² + x³) làm .

Bước 2: Vẽ thanh ghi

Từ g₃(x) = (1 + x² + x³) ta có, a₀=1, a₁=0, a₂=1

Bài tập

1. Trong các thanh ghi sau đây, thanh ghi nào sinh ra bộ mã vòng có độ dài n=15 bit?

Nêu các bước cần thiết để thiết kế bộ mã xoay vòng độ dài 15 bit với số bit kiểm tra là Vẽ sơ đồ thanh ghi dạng tổng quát.