Tài liệu

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

Science and Technology

Đ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 đa thức đặc trưng của thanh ghi,
  • Hiểu Quan hệ giữa chu kỳ n, đa thức đặc trưng và đa thức (xn + 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 đa thức đặc trưng của thanh ghi

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

gm(x)=a0 + a1x+ a2 x2+ …+am-1xm-1 + xm.

với a0, a1, a2,…, am-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:

a0 = 1, a1= 0, a2 = 1, a3 = 0

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

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

Đa thức đặc trưng của thanh ghi gm(x)=a0 + a1x+ a2 x2+ …+am-1xm-1 + xm luôn chia hết đa thức (xn + 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:

  • a0 = 1, a1= 0, a2 = 1, a3 = 0
  • Đa thức đặc trưng của thanh ghi có dạng: g4(x)=1 + x2 + x4.
  • Thanh ghi này có chu kỳ n = 6.

Thực hiện phép chia đa thức (x6 + 1) : (1 + x2 + x4)= (x2 + 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:

a0 = 1, a1= 0, a2 = 1, a3 = 0

đa thức đặc trưng của thanh ghi có dạng: g4(x)=1 + x2 + x4.

thanh ghi này có chu kỳ n = 6 và (x6 + 1) : 1 + x2 + x4 = x2 + 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 đa thức đặc trưng của thanh ghi

  • Tìm 2 đa thức gm(x)=a0 + a1x+ a2 x2+ …+am-1xm-1 + xm

và hk(x)=h0 + h1x+ h2x2 + …+hk-1xk-1 + xk sao cho (xn + 1) = gm(x)* hk(x).

  • Nếu tồn tại (xn + 1) = gm(x)* hk(x) thì ta chọn gm(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ừ gm(x)=a0 + a1x+ a2 x2+ …+am-1xm-1 + xm => a0, a1, a2,…, am-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 đa thức đặc trưng của thanh ghi

Ta có (x7 + 1) : (1 + x2 + x3) = (1 + x2 + x3 + x4)

Do m=3 nên chọn g3(x) = (1 + x2 + x3) làm đa thức đặc trưng của thanh ghi.

Bước 2: Vẽ thanh ghi

Từ g3(x) = (1 + x2 + x3) ta có, a0=1, a1=0, a2=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.

Đánh giá:
0 dựa trên 0 đánh giá

Tuyển tập sử dụng module này

Nội dung cùng tác giả
 
Nội dung tương tự