Bài giảng Thiết kế số - Tối thiểu hóa trạng thái - Hoàng Mạnh Thắng

Thiết kế số Tối thiểu hóa trạng tháiNgười trình bày: TS. Hoàng Mạnh ThắngTexPoint fonts used in EMF: AAAAAATối thiểu hóa trạng tháiVới FSM đơn giản thì có thể dễ thấy qua sơ đồ trạng thái mà số trạng thái được dùng có thể tối thiểu hóaVới FSM phức tạp, sơ đồ trạng thái có thể có nhiều trạng thái cần để thực hiện chức năng yêu cầuTối thiểu hóa các trạng thái được quan tâm để tối thiểu hóa mạchThay vì cố đưa ra các trạng thái nào tương đương, thường dễ hơn đưa ra các trạng thái không tương đương  định nghĩa thủ tục tối ưuTrạng thái tương đươngHai trạng thái Si và Sj là tương nếu đối với mọi chuỗi vào có thể, chúng cho ra cùng một giá trị đầu ra không quan tâm đến Si hay Sj là trạng thái đầuNếu đầu vào w=0 đưa vào FSM khi đang ở Si và FSM dịch sang Su, thì Su được đặt là 0-successor của SiTương tự, nếu w=1 va FSM chuyển sang Sy thì Sy được gọi là 1-successor của SiCác successor của Si là k-successor của nó, với nhiều biến vào Tối thiểu hóa phân tách nhỏTừ định nghĩa về tương đương, nếu S_i và S_j là tương đương thì tương ứng có k-successor tương đươngNó được dùng tạo ra thủ tục tối thiểu hóa liên quan đến các trạng thái như là các tập và sau đó phá vỡ các tập đó thành các partitions gồm các tập con không tương đươngĐịnh nghĩa: một partition gồm một hay nhiều bloc, mỗ block gồm một tập con các trạng thái có thể là tương đương, nhưng các trạng thái trong một block không tương đương với các trạng thái trong block khácVí dụ tối thiểu hóa partitionXem bảng trạng thái sauPartition ban đầu gồm tấ cả các trạng tháiVí dụ tối thiểu hóa partition, contPartition tiếp theo tách các trạng thái có các đầu ra khác nhauBây giờ xem xét tất cả 0- và 1- successor của tất cả các trạng thái trong mỗ blockVới (ABD), 0-successors là (BDB): vẫn cùng một block  xem xét A,B và D vẫn còn tương đương1-successors của (ABD) là (CFG)  xem xét A,B và D vẫn còn tương đươngTiếp theo xét đên (CEFG)Ví dụ tối thiểu hóa partition, contP_2=(ABD)(CEFG)Đối với (CEFG), 0-successors là (FEFF), tất cả trong cùng block trong P_2C,E,F và G vẫn còn tương đương1-successors là (ECDG), chúng ko cùng trong một block ít nhất có một trạng thái trong (CEFG) không tương đương với các trạng thái kiaF phải khác C, E, G bởi 1-successor, D, thuộc khối khác E, C và GDo đó, P_3=(ABD)(CEG)(F)Ở đây, ta biết rằng trạng thái F là duy nhấtVí dụ tối thiểu hóa partition, contP_3=(ABD)(CEG)(F)Qúa trình được lặp lại và cuối cùng nhận được P_5=(AD)(B)(CEG)(F)A và D tương đương nhau,C,E và G cũng vậyBảng trạng thái có thể được viết lại bằng cách xóa bỏ các hàng D, E và GKết quả Bài tậpXét các trạng thái tương đương trong sơ đồ trạng thái sau