thanh ghi lùi tưng bước

THANH GHI LÙI TỪNG BƯỚC

Mục tiêu

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

• Đặt vấn đề về thanh ghi lùi từng bước,
• Cách biểu diễn vật lý của thanh ghi,
• Cách biểu diễn toán học của thanh ghi,
• Tìm chu kỳ của thanh ghi.

Đặt vấn đề

Như chúng ta đã biết, phương pháp sinh bộ mã kiểm tra chẵn lẻ dựa trên lý thuyết nhóm cho phép chúng ta sinh mã nhanh bằng cách chỉ sinh ra k từ mã độc lập tuyến tính trong tổng số s=2^k từ mã, từ k từ mã này ta có thể xác định các từ mã còn lại (bằng cách cộng tổ hợp các từ mã). Vấn đề đặt ra ở đây là làm sao để tìm ra một phương pháp sinh mã khác sao cho số từ mã sinh ban đầu nhỏ hơn k (k là số từ mã độc lập tuyến tính của bộ mã kiểm tra chẵn lẻ) và từ đây ta có thể xác định nhanh các từ mã còn. Cụ thể dựa trên mô hình của thanh ghi lùi từng bước có thể giải quyết được vấn đề này.

Biểu diễn vật lý của thanh ghi

Để gọi một cách ngắn gọn, ta qui ước gọi thanh ghi thay vì goi thanh ghi lùi từng bước. Biểu diễn vật lý của thanh ghi có thể thấy như hình vẽ dưới đây:

• F_m-1, F_m-2, …, F₁, F₀ : các bit lưu trữ dữ liệu nhị phân.
• a_m-1, a_m-2, …, a₁, a₀ : các công tắc (switch) dùng để đóng (=1) hay mở ( =0

• : là bộ làm tính cộng trong phép toán mudulo 2 sau mỗi xung đồng hồ với dữ liệu do các bit của thanh ghi gửi về.

Quá trình dịch chuyển lùi từng bước: sau mỗi xung đồng hồ thì dữ liệu trong bit F­_i sẽ được chuyển về lưu trữ ở bit F_i-1 (F₁-> F₀; F₂->F₁; …; F_m-2->F_m-3; F_m-1->F_m-2). Tất cả các giá trị trên các F_i (trước khi có xung điện) sẽ được chuyển về bộ cộng (tùy theo các công tắc đóng hay mở), tổng của các giá trị này sẽ được đưa vào lưu trữ ở bit F_m-1.

Ta sẽ nghiên cứu thanh ghi này cụ thể hơn trong các nội dung tiếp theo nhằm tìm ra một phương pháp sinh mã mà ta có thể gọi là mã xoay vòng. Đây cũng là một dạng mã kiểm tra chẵn lẻ.

Biểu diễn toán học của thanh ghi

Mục tiêu của việc biểu diễn toán học là để tìm ra các mô hình tính toán phục vụ cho việc nghiên cứu sinh mã xoay vong chẵn lẻ từ thanh ghi.

Gọi x = (x₀, x₁, …, x_m-2, x_m-1) là giá trị các bit của thanh ghi tại thời điểm trước khi có nhịp xung đồng hồ.

x’ = (x’₀, x’₁, …, x’_m-2, x’_m-1) là giá trị các bit của thanh ghi sau khi có nhịp xung đồng hồ.

Khi đó ta có:

x’₀=x₁

x’₁=x₂

x’₂=x₃

----------

x’_m-2=x_m-1

x’_m-1=a₀x₀ + a₁x₁ + …+ a_m-1x_m-1.

Hay viết theo dạng ma trận ta có x’ = T.x

Trong đó:

T được gọi là ma trận đặc trưng của thanh ghi lùi từng bước.

Quá trình dịch chuyển lùi từng bước của thanh ghi:

Gọi

là véc tơ chỉ giá trị của thanh ghi tại thời điểm đang xét.

Giá trị của thanh ghi sau 1 xung đồng hồ là x⁽¹⁾=T.x⁽⁰⁾

Giá trị của thanh ghi sau 2 xung đồng hồ là x⁽²⁾=T.x⁽¹⁾=T².x⁽⁰⁾

Giá trị của thanh ghi sau 3 xung đồng hồ là x⁽³⁾=T.x⁽²⁾=T³.x⁽⁰⁾

-----------

Ví dụ thanh ghi lui từng bước

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

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

Ma trận đặc trưng của thanh ghi

Chu kỳ của thanh ghi

Như đã trình bày ở trên về quá trình dịch chuyển lùi từng bước của thanh ghi:

Giá trị của thanh ghi sau 1 xung đồng hồ là x⁽¹⁾=T.x⁽⁰⁾

Giá trị của thanh ghi sau 2 xung đồng hồ là x⁽²⁾=T.x⁽¹⁾=T².x⁽⁰⁾

Giá trị của thanh ghi sau 3 xung đồng hồ là x⁽³⁾=T.x⁽²⁾=T³.x⁽⁰⁾

----------------

Giá trị của thanh ghi sau n xung đồng hồ là x⁽ⁿ⁾=T.x^(n-1)=Tⁿ.x⁽⁰⁾ (bởi vì số trạng thái thông tin khác nhau có thể có là 2^m)

Vậy chu kỳ của thanh ghi là số xung nhịp đồng hồ để thanh ghi lặp lại trạng thái ban đầu. Nghĩa là nếu x⁽⁰⁾khác0 và tồn tại n>0 sao cho x⁽ⁿ⁾ = x⁽⁰⁾ thì ta nói n là chu kỳ của thanh ghi.

Lưu ý:

Cách viết biểu diễn nhị phân cho giá trị của x⁽ⁱ⁾ theo thứ tự từ trên xuống (theo cột), tương ứng với viết từ trái sang phải (theo dòng). Ví dụ: biểu diễn nhị phân của x⁽ⁱ⁾ = 3 có m = 3 bit như sau:

Viết theo dòng: x⁽ⁱ⁾ = 011 (viết từ trái sang phải)

Viết theo cột: (viết từ trên xuống)

Ví dụ tìm chu kỳ của thanh ghi

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

Tìm chu kỳ:

Bài tập

Tìm các chu kỳ của thanh ghi lui từng bước như hình sau:

Tìm các chu kỳ của thanh ghi lui từng bước như hình sau: