Bài giảng Thiết kế số: Tối thiểu hóa trạng thái - TS. Hoàng Mạnh Thắng

Chia sẻ: _ _ | Ngày: | Loại File: PPT | Số trang:10

Thêm vào BST

Báo xấu

11
lượt xem 5
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng "Thiết kế số: Tối thiểu hóa trạng thái - TS. Hoàng Mạnh Thắng" được biên soạn với các nội dung chính sau: Tối thiểu hóa trạng thái; Trạng thái tương đương; Tối thiểu hóa phân tách nhỏ; Ví dụ tối thiểu hóa partition; Ví dụ tối thiểu hóa partition, cont. Mời quý thầy cô và các em sinh viên cùng tham khảo bài giảng!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Thiết kế số: Tối thiểu hóa trạng thái - TS. Hoàng Mạnh Thắng

Người trình bày: ̣ TS. Hoàng Manh Thă ́ng
Tối thiểu hóa trạng thái Với FSM đơn gian thi ̉ ̉ ̃ thấy qua sơ đồ ̀ có thê dê ̣ trang tha ̣ ́i mà số trang tha ́i được dùng có thê tô ̉ ́i ̉ thiêu ho ́a Với FSM phức tap, s ̣ ơ đồ trang tha ̣ ̉ ́ ́i có thê co ̣ nhiều trang tha ̉ ực hiên ch ́i cần đê th ̣ ức năng yêu cầu ̉ Tối thiêu ho ̣ ́a các trang tha ́i được quan tâm đê tô ̉ ́i ̉ thiêu ho ́a macḥ Thay vì cố đưa ra các trang thạ ́i nào tương đương, thường dễ hơn đưa ra các trang tha ̣ ́i không tương đương  đinh nghi ̣ ̉ ̣ ́i ưu ̃a thu tuc tô
Trạng thái tương đương ̣ Hai trang tha ́i Si và Sj là tương nếu đối với moi ̣ ̉ chuỗi vào có thê, chu ̣ ́ng cho ra cùng môt gia ́ tri ̣ ̣ đầu ra không quan tâm đến Si hay Sj là trang tha ́i đầu Nếu đầu vào w=0 đưa vào FSM khi đang ở Si và ̣ FSM dich sang S ̣ ̀ 0successor cua u, thì Su được đăt la ̉ Si Tương tự, nếu w=1 va FSM chuyên sang S ̉ y thì Sy được goi la ̣ ̀ 1successor cua S ̉ i ̉ i là ksuccessor cua no Các successor cua S ̉ ́, với nhiều biến vào
Tối thiểu hóa phân tách nhỏ Từ đinh nghi ̣ ̃a về tương đương, nếu S_i và S_j là tương đương thì tương ứng có ksuccessor tương đương Nó được dùng tao ra thu tuc tô ̣ ̉ ̣ ́i thiêu ho ̉ ́a liên quan ̣ đến các trang tha ́i như là các tâp va ̣ ̀ sau đó phá vỡ ̣ các tâp đo ́ thành các partitions gồm các tâp con không ̣ tương đương ̣ Đinh nghi ̣ ̃a: môt partition gô ̣ ̀m môt hay nhiê ̀u bloc, mỗ ̣ ̣ block gồm môt tâp con ca ̣ ́c trang tha ́i có thê la ̉ ̀ tương đương, nhưng các trang tha ̣ ̣ ́i trong môt block không tương đương với các trang tha ̣ ́i trong block khác
Ví dụ tối thiểu hóa partition ̉ ̣ Xem bang trang tha ́i sau ̉ ́c trang tha Partition ban đầu gồm tấ ca ca ̣ ́i
Ví dụ tối thiểu hóa partition, cont ̣ Partition tiếp theo tách các trang tha ́i có các đầu ra khác nhau Bây giờ xem xét tất ca 0 va ̉ ̉ ́t ca ̉ ̀ 1 successor cua tâ ̣ các trang tha ́i trong mỗ block  Với (ABD), 0successors là (BDB): vẫn cùng môt block ̣  xem xét A,B và D vẫn còn tương đương ̉  1successors cua (ABD) la ̀ (CFG)  xem xét A,B và D vẫn còn tương đương Tiếp theo xét đên (CEFG)
Ví dụ tối thiểu hóa partition, cont P_2=(ABD)(CEFG) Đối với (CEFG), 0successors là (FEFF), tất ca ̉ trong cùng block trong P_2C,E,F và G vẫn còn tương đương 1successors là (ECDG), chúng ko cùng trong môt ̣ ̣ ̣ block ít nhất có môt trang tha ́i trong (CEFG) không tương đương với các trang tha ̣ ́i kia ̉  F phai khác C, E, G bởi 1successor, D, thuôc khô ̣ ́i khác E, C và G Do đó, P_3=(ABD)(CEG)(F) Ở đây, ta biết rằng trang tha ̣ ́i F là duy nhất
Ví dụ tối thiểu hóa partition, cont P_3=(ABD)(CEG)(F) Qúa trình được lăp lai va ̣ ̣ ̀ cuối cùng nhân đ ̣ ược P_5=(AD)(B)(CEG)(F) A và D tương đương nhau, ̣ C,E và G cũng vây ̉ ̣ Bang trang tha ̉ ược viết lai bă ́i có thê đ ̣ ̀ng cách xóa ̉ ́c hàng D, E và G bo ca
Kết quả
Bài tập ̣ Xét các trang tha ́i tương đương trong sơ đồ trang ̣ thái sau