การลดรูปสถานะ
จากวิกิพีเดีย สารานุกรมเสรี
[แก้] State Reduction
State Reduction เป็นการลด state เพื่อให้ความซับซ้อนของวงจรลดน้อยลง เมื่อความซับซ้อนองวงจรลดลง จำนวนอุปกรณ์ที่ใช้ในการต่อวงจรก็ลดน้อยลง โอกาสที่ความผิดพลาดจะเกิดขึ้นก็ลดลง ซึ่ง state ที่จะลดได้นั้นจะต้องเป็น state ที่มีคุณสมบัติทัดเทียมกันหรือเหมือนกันเท่านั้น (Equivalent State) ซึ่งมีคุณสมบัติดังนี้
ถ้าให้ a และ b เป็นสเตทปัจจุบัน (Present State) A และ B เป็นสเตทถัดไป (Next State) ถ้าจะลดสเตท a และ b ได้ก็ต่อเมื่อ
1. ที่ Input เดียวกัน Output ของ a และ b เหมือนกัน
2. สเตทถัดไป (Next State ) A และ B ทัดเทียมกัน
ถ้าทั้ง 2 สเตทเป็นไปตามกฎทั้ง 2 ข้อก็สามารถยุบสเตทรวมกันได้ โดยเมื่อยุบรวมกันแล้วการทำงานของวงจรจะยังคงเหมือนเดิม เช่น
จาก State Tale ข้างบนจะเห็นว่า สเตท b และ d ที่ Input เดียวกันมี Output เหมือนกันและมี Next State เดียวกัน สามรถยุบรวมกันและนำมาเขียนใหม่ได้ดังนี้
แต่ถ้า State มีจำนวนมากหรือ Next State ไม่เหมือนกันแต่เท่าเทียมกันซึ่งไม่สามารถคิดได้ทันทีได้เลยเราจะใช้ Implication Table เข้าช่วยในการยุบ State
วิธีการดู
1. ให้เราดู Output โดยดูทีละ 2 State ว่าเหมือนกันหรือป่าวถ้าไม่เหมือนกันให้ใส่ กากบาทที่ช่องนั้นเลยนั้นคือยุบไม่ได้ แต่ถ้า Output เหมือนกันให้ดูข้อที่ 2
2. ให้เราดูว่า Next State เหมือนกันหรือป่าวถ้า Next State เหมือนกันก็ให้ใส่เครื่องหมายถูกที่ช่องนั้นเลยนั้นคือยุบได้ แต่ถ้าไม่เหมือนกันให้ติดไว้
3. ให้ทำตามข้อ 1 และ 2 จนครบทุกช่อง
4. กลับมาเช็คช่องที่ติดค่าไว้ทีละช่องว่า State ที่ติดไว้นั้น ยุบได้ช่องนั้นก็ยุบได้ด้วย แต่ถ้า State นั้นยุบไม่ได้ช่องนั้นก็ยุบไม่ได้ด้วย เช่น
หมายเหตุ ช่อง (b , c) ที่เป็น / ก็เพราะว่า (b , c) กับ (c , b) ทั้งสอง State วนหากันเองจึงยุบรวมได้
และช่อง (d , e) ที่ไม่ติด (d , e) ก็เพราะว่า State d และ State e ต่างก็วนเข้าหาตัวเองเหมือนกันจึงใช้ได้
เริ่มพิจารณาจาก
(a , b) ติดที่ (A , E) ซึ่ง (A , E) เป็น X ดังนั้น (a , b) จึงเป็น X ด้วย
(a , c) ติดที่ (B , C)(A , E) ซึ่ง (B , C) ผ่านแต่ (A , E) ไม่ผ่านดังนั้นช่องนี้จึงเป็น X
(d , e) ติดที่ (A , B) ซึ่งไม่ผ่านดังนั้นช่องนี้จึงเป็น X
เพราะฉะนั้นจึงยุบ State ได้ที่ State b และ State c นำ State มาเข้ากลุ่มและเรียงกันใหม่
(A) (BC) (D) (E)
แล้วนำมาเขียนในรู้ของ State Table ใหม่