Bài giảng Thiết kế số - Các khối mạch tổ hợp: 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ái Người trình bày: TS. Hoàng Mạnh Thắng TexPoint fonts used in EMF: A A A A A A Tối thiểu hóa trạng thái Vớ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óa Vớ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ầu Tối thiểu hóa các trạng thái được quan tâm để tối thiểu hóa mạch Thay 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 ưu Trạng thái tương đương Hai trạng thái S i và S j 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 S i hay S j là trạng thái đầu Nếu đầu vào w=0 đưa vào FSM khi đang ở S i và FSM dịch sang S u , thì S u được đặt là 0-successor của S i Tương tự, nếu w=1 va FSM chuyển sang S y thì S y được gọi là 1-successor của S i Các successor của S i 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 đương Nó đượ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ác Ví dụ tối thiểu hóa partition Xem bảng trạng thái sau Partition ban đầu gồm tấ cả các trạng thái Ví dụ tối thiểu hóa partition, cont Partition tiếp theo tách các trạng thái có các đầu ra khác nhau Bâ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ỗ block Vớ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 đương 1-successors của (ABD) là (CFG)  xem xét A,B và D vẫn còn tương đương Tiếp theo xét đên (CEFG) Ví dụ tối thiểu hóa partition, cont P_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 đương 1-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 kia F phải khác C, E, G bởi 1-successor, D, thuộc khối khác E, C và G Do đó, P_3=(ABD)(CEG)(F) Ở đây, ta biết rằng trạng thái F là duy nhất Ví dụ tối thiểu hóa partition, cont P_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ậy Bả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à G Kết quả Bài tập Xét các trạng thái tương đương trong sơ đồ trạng thái sau