điện tử số phần 32

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: AAAAAA
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 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 đầu
Nế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 Si
Tương tự, nếu w=1 va FSM chuyển sang Sy thì Sy được gọi là 1-successor của Si
Cá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 đươ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