พูดคุย:เครื่องสถานะจำกัด

บทความนี้เคยมีเนื้อหาเหล่านี้ แต่เนื่องจากเนื้อหาทับซ้อนกับขั้นต้น และบางส่วนไม่เป็นสารานุกรม จึงยกยอดไว้ในนี้

ข้อความหัวเรื่อง Mealy FSM มีลักษณะดังนี้

1. สามารถนำมาอธิบายฟังก์ชันการทำงานของวงจรเดียวกันได้และยังสามารถที่นำ Mealy FSM มาวิเคราะห์ได้จาก Moore FSM
2. Mealy FSM ใช้อธิบายการทำงานของวงจรได้ดีกว่า Moore FSM และ Mealy FSM ใช้พื้นที่สำหรับการสร้างวงจรน้อยกว่าMoore FSM
3. Mealy FSM จะให้ Output ทันทีที่มีการเปลี่ยนแปลงที่ Input กล่าวคือ Mealy FSM จะให้ Output ที่ตอบสนองต่อสัญญาณนาฬิกาได้เร็วกว่า Moore FSM ที่มวงจรขนาดเท่ากัน
4. Moore FSM ไม่มีวงจร Combinational Logic ต่ออยู่ระหว่าง Inputs และ Outputs

การออกแบบ FSMs ประกอบไปด้วย 3 ขั้นตอน 1. การกำหนด State เพื่อกำหนด Output ของระบบ 2. การกำหนดการเปลี่ยนแปลงจาก State หนึ่งไปยังอีก State หนึ่ง เมื่อมี Inputมากระตุ้นระบบ 3. การทำ Optimization และ Minimization หมายถึงการนำ FSMs ไปสร้างให้ได้ประสิทธิภาพสูงสุดและวงจรที่ได้มีขนาดเล็กที่สุด FSMs ที่นิยมนำมาออกแบบวงจรดิจิตอล คือ Moore Machine และ Mealy Machine การออกแบบระบบโดย Mealy FSMs ที่มีการทำงานดังรูป การออกแบบวงจร FSM

 ขั้ั้นทีี่ 1. กำาหนดขอบเขตของงานออกมาในรูปของตาราง PS / NS,State diagram, ASM Chart, Flow map หรือ TimingDiagram
 ขั้ั้นทีี่ 2. กำาหนดจำานวนฟลิปฟลอปและตัวแปรสถานะ (ฟลิปฟลอปหนึึ่งตัวใช้ต้ตัวแปรหนึึ่งตัว) ใช้ร้รหัสหนึึ่งต่อ่อหนึึ่งสถานะ
   ขั้ั้นทีี่ 3. เลือกชนิดของฟลิปฟลอป กำาหนดอินพุท และสมการเอาท์พ์พุทแบบมัวร์แ์และ/หรือเมียลี
   ขั้ั้นทีี่ 4. เขียนแผนผังโลจิก

ระบบจะสามารถรับ input ได้ อาจจะให้ output tและมีmemory ที่สามารถเก็บ input ได้ ในเวลาหนึ่ง ๆ จะมีสถานะ (state) ต่าง ๆ สถานะนี้สามารถบอกได้ถึง Input ที่เข้ามาแล้ว และสถานะ ที่จะเกิดขึ้น เมื่อมี input ใหม่เข้ามาแล้วสถานะ ขึ้นอยู่กับสถานะปัจจุบันและ input ถ้าจำนวนของสถานะมีจำกัด/ นับได้หรือกำหนดได้ Finite-state machine สามารถทำการคำนวณภายในเนื้อที่ในหน่วยความจำที่จำกัดได้ ทำให้มันไม่สามารถที่จะทำงานหลายอย่างภายใต้ข้อจำกัดของคอมไพเลอร์ได้ ดังนั้นจึงต้องมีการสร้างเครื่องมือที่สามารถรองรับการทำงานที่มีลักษณะที่ซับซ้อนมากขึ้น การสร้างเครื่องมือนี้ต้องอาศัยกลไกการเพิ่มเนื้อที่การทำงาน มีวิธีหนึ่งที่ใช้บ่อยในคอมไพเลอร์ เรียกว่า "Stacking" Push คือ การเพิ่มข้อมูลเข้าไปใน stack Pop คือ การย้ายข้อมูลออกจาก stack Top of stack คือ ข้อมูลที่อยู่บนสุดของ stack เรียกว่า bottom marker ซึ่งเป็นตัวที่ใช้บอกถึง bottom of stack และไม่สามารถ pop ออกมาได้ ตัวอย่าง 1 ไฟล์:Finite50.jpg จากรูป (a) top symbol คือ C จากลำดับของ symbol ทำให้เราทราบว่า 1. A คือ symbol ที่ถูก PUSH ลงไปเป็นตัวแรก 2. B คือ symbol ที่ถูก PUSH ลงไปเป็นตัวที่ 2 3. A คือ symbol ที่ถูก PUSH ลงไปเป็นตัวที่ 3 4. C คือ symbol ที่ถูก PUSH ลงไปเป็นตัวสุดท้าย ไฟล์:Finite60.jpg จากรูป (c) แสดงการ POP symbol C ทำให้ A กลายเป็น top of symbol ซึ่งจะสังเกตเห็นว่าการกระทำกับข้อมูลบน stack นั้น จะทำได้กับข้อมูลที่อยู่บนสุดเท่านั้น ประโยชน์ของ Finite State Machine 1.ใช้เขียน Model ง่าย ๆ จนถึงการทำที่ยากและซับซ้อน 2.ใช้ในการศึกษา “ Formal Language“ 3.ใช้ในการศึกษา Compiler, Programming Language เป็นต้น Finite and Pushdown Finite state machine ได้แบ่งการทำงานออกเป็น step ย่อย ในแต่ละ step อาจเปลี่ยนลักษณะใน memory ได้โดยที่เปลี่ยน state และเปลี่ยนการ POP หรือ PUSH STACK Pushdown machine จะมีขั้นตอนหลายขั้นตอนในการ process แต่ละ symbol ของ input sequence แต่ละขั้นตอนจะถูกควบคุมโดยตัว control ซึ่งเครื่องสามารถที่จะรู้ได้ว่าการ process ของ input sequence นั้นเสร็จสิ้นเมื่อใด Transition ประกอบด้วย 3 ส่วนมีดังนี้ 1. Stack operation PUSH ข้อมูลที่ต้องการจัดเก็บลง stack POP ข้อมูลออกจาก top ของ stack (การ POP stack สามารถทำได้กับข้อมูลตัวบนสุด หรือตัวล่าสุดได้เท่านั้น) คงสภาพของ stack ไว้เหมือนเดิม ไม่มีการเปลี่ยนแปลง 2. State operation คือ เปลี่ยนจากสถานะหนึ่งไปอีกสถานะหนึ่ง 3. Input operation รับ input ตัวถัดไปเข้ามาเป็นตัวปัจจุบัน (current) นั่นหมายความว่า "Advance" ไม่เปลี่ยนแปลง Input นั่นหมายความว่า "Retain" Pushdown Machine จะถูกระบุโดยสิ่งต่างๆ ดังนี้ 1) เชตจำกัดของ Input Symbol ซึ่งจะรวมถึง End Marker ด้วย 2) เชตจำกัดของ Stack Symbol ซึ่งจะรวมถึง Bottom Marker ด้วย 3) เชตจำกัดของ State ซึ่งจะรวมถึงสถานะเริ่มต้น (Starting State) ด้วย 4) สิ่งควบคุม (A Control) ซึ่งจะสั่งให้ทำการ Exit หรือ Transition โดยตัวกระทำจะถูกดึงไปใช้กับ Input จนกระทั่งพบ End Marker หรือทำการ Pop , Push จนพบ End Marker 5) Stack เริ่มต้น ซึ่งจะอยู่ในลักษณะ "Top Symbol On the Right" คือ Bottom Marker จะอยู่ทางซ้ายมือเรียงมาก่อน ตามด้วย Stack Symbol Pushdown Recognizer Pushdown Machine จะถูกเรียกว่า Pushdown Recognizer ก็ต่อเมื่อมีการหยุดการทำงาน --Iamion | พูดคุย - 21:01, 27 ตุลาคม 2007 (ICT)