สเตตแมชีน

จากวิกิพีเดีย สารานุกรมเสรี

บทความนี้ต้องการเก็บกวาด ตรวจสอบ ปรับปรุง แก้ไขรูปแบบ เพิ่มแหล่งอ้างอิง ใส่หมวดหมู่ หรือภาษาที่ใช้
ส่วนใดส่วนหนึ่งหรือในหลายส่วนด้วยกัน
คุณสามารถช่วยตรวจสอบ และแก้ไขบทความนี้ได้ด้วยการกดที่ปุ่ม แก้ไข ด้านบน
กรุณาเปลี่ยนไปใช้ป้ายข้อความอื่น เพื่อระบุสิ่งที่ต้องการตรวจสอบ หรือแก้ไข
ดูรายละเอียดเพิ่มเติมที่ วิธีแก้ไขหน้าพื้นฐาน คู่มือการเขียน และ นโยบายวิกิพีเดีย ซึ่งสามารถดูตัวอย่างบทความได้ที่ บทความคุณภาพ และเมื่อแก้ไขตามนโยบายแล้ว สามารถนำป้ายนี้ออกได้

สเตตแมชชีน (State machine) คือวงจรที่เป็น Sequential (มีสัญญาณนาฬิกาเข้ามาควบคุมการทำงาน) ซึ่ง ออกแบบเป็นสถานะการทำงาน(State) ของวงจรออกเป็นหลายๆ สถานะ แต่ละสเตทมีลอจิกการทำงานที่ต่างกัน เพื่อ กำเนิดค่าเอาต์พุตและค่าสเตทถัดไป มีสัญญาณสเตทที่กำหนดว่าสเตทปัจจุบันเป็นสเตทไหน สัญญาณของสเตทจะถูกเก็บ ไว้ในรีจีสเตอร์ ดังนั้นสเตทจะสามารถเปลี่ยนแปลงได้ที่ขอบขาของ Clock เท่านั้น

State Machine มี 2 ประเภท คือ

1. Moore Machine มีเอาต์พุตเปลี่ยนแปลงตามจังหวะของ Clock เท่านั้น คือ แต่ละสเตทมีค่าของเอาต์พุตที่กำหนดแน่นอน เอาต์พุตจะเปลี่ยนก็ต่อเมื่อสเตทเปลี่ยน

2. Mealy Mchine เอาต์พุตไม่จำเป็นต้องเปลี่ยนแปลงตามจังหวะของ Clock เท่านั้น คือ ภายในสเตทหนึ่งๆ เอาต์พุตสามารถเปลี่ยนแปลงได้ ถ้าอินพุตเปลี่ยน

(บทความนี้จะเน้นที่ Mealy เท่านั้น)

การวิเคราะห์วงจรเปลี่ยนสถานะตรงตามจังหวะเวลา( Clocked Synchronous State-Machine Analysis) Mealy machine เป็น state machine ที่ มีเอาท์พุทขณะใดๆ ขึ้นอยู่กับทั้ง อินพุท และ สถานะ ของวงจรในขณะนั้นๆ • โครงสร้างทั่วไปของ state machine ประกอบด้วย 3 ส่วนหลัก คือ ภาพ:state00.jpg

1. หน่วยความจำสถานะ ( State Memory) : เป็น flip-flop สำหรับจดจำสถานะการทำงานของวงจร โดย flip-flop n ตัว ใช้เป็นตัวแปรสถานะได้ n ตัว ใช้เก็บสถานะที่แตกต่างกันได้ 2n สถานะ

2. วงจรตรรกะกำหนดสถานะถัดไป ( Next State Logic Circuit) : เป็นวงจร combinationalสำหรับสร้างสัญญาexcitation ป้อนเข้าหน่วยความจำสถานะ เพื่อใช้กำหนดค่าของสถานะถัดไปโดย รับสัญญาณอินพุท จากตัวแปรอินพุทของ state machine และจากตัวแปรสถานะที่ป้อนกลับมาจากเอาท์พุทของ flip-flop ที่ใช้เป็นหน่วยความจำNext State F = F(current state, input)

3. วงจรตรรกะเอาท์พุท ( Output Logic Circuit) : เป็นวงจร combinational สำหรับสร้างสัญญาณเอาท์พุทของ state machine โดยอาจมีสัญญาณอินพุทเป็นตัวแปรสถานะเพียงอย่างเดียว หรือ ใช้ตัวแปรอินพุทของ state machine ด้วย ขึ้นอยู่กับประเภทของ state machine

การวิเคราะห์วงจรเปลี่ยนสถานะตรงตามจังหวะเวลา • Mealy machine เป็น state machine ที่ มีเอาท์พุทขณะใดๆ ขึ้นอยู่กับทั้ง อินพุท และ สถานะ ของวงจรในขณะนั้นๆ ภาพ:input1.jpg - นั่นคือ เอาท์พุทปัจจุบัน ของวงจร จะขึ้นอยู่กับ หรือเป็นฟังก์ชันของ ตัวแปรอินพุท และ สถานะปัจจุบัน - นั่นคือ ถ้าหากมีการเปลี่ยนแปลงค่าของตัวแปรอินพุท หรือ ค่าของตัวแปรสถานะเพียงอย่างใดอย่างหนึ่ง ก็จะส่งผลให้ เกิดการเปลี่ยนแปลงค่าของเอาท์พุทด้วย (มี propagation delay ขึ้นกับความซับซ้อนของวงจร G) - โดย การเปลี่ยนแปลงสถานะจะเป็นจังหวะตามการ tick ของสัญญาณนาฬิกา - ส่วนสัญญาณอินพุทเปลี่ยนแปลงค่าได้โดยอิสระ ไม่ขึ้นกับสัญญาณนาฬิกาของ state machine

  หมายเหตุ : หากต้องการให้ เอาท์พุทขึ้นอยู่กับ สัญญาณอินพุทด้วย และ เปลี่ยนค่าตามจังหวะสัญญาณนาฬิกาด้วย

สามารถทำได้โดยเพิ่มหน่วยความจำไปที่ output อีกชุดหนึ่ง (output pipeline memory) ซึ่งค่าของ pipelined outputs ขณะใดๆ จะขึ้นอยู่กับ สถานะและอินพุทในช่วงคาบของclock ก่อนการ tick ครั้งล่าสุด

- ตัวอย่างที่ 1 : Mealy Machine ที่ใช้ positive-edge-triggered D flip-flop

ภาพ:output.jpg

- จากแผนภาพวงจร จะเห็นว่าเป็น clocked synchronous state machine ชนิด Mealy Machine เปลี่ยนสถานะที่ขอบขาขึ้นของ CLK (ดูจากชนิดของ flip-flop) มีตัวแปรอินพุท 1 ตัว คือ EN มีตัวแปรสถานะ 2 ตัว คือ Q0, Q1 (ดูจากจำนวน flip-flop) มีตัวแปรเอาท์พุท 1 ตัว คือ MAX


สารบัญ

[แก้] Mealy Machines

เป็น FSMs มีสถานะเปลี่ยนแปลงตามสัญญาณนาฬิกา แต่เอาต์พุต ที่ได้จะเปลี่ยนตามอินพุตที่เข้ามาในแต่ละสถานะ คือ ภายในสถานะหนึ่งๆ จะมีลักษณะของเอาต์พุตที่สามารถเปลี่ยนแปลงได้ ตามอินพุตที่เปลี่ยน หรืออาจกล่าวได้ว่า "Output ของระบบจะขึ้นอยู่กับสถานะปัจจุบัน (Present State)" และอินพุตที่เข้ามากระตุ้นระบบในขณะนั้น


Mealy Machine เป็น State Machine ที่อนุญาตให้เอาต์พุตมีการเปลี่ยนแปลงได้โดยไม่จำเป็นต้องเข้าจังหวะกับการเปลี่ยนสเตท ที่สำคัญก็คือสเตทยังเปลี่ยนตามจังหวะ clock แต่เอาต์พุตสามารถเปลี่ยนตามอินพุตได้ทันทีโดยไม่สนใจ clock และงานบางอย่างสามารถลดจำนวนสเตทลงได้ถ้าใช้ Mealy Machine งานบางอย่างจำเป็นต้องใช้ Mealy Machine เท่านั้น ข้อเสียของ Mealy Machine คือ เข้าใจยากกว่า Moore Machine จึงออกแบบยากกว่าและเสียงต่อการเกิด glitch ที่ เอาต์พุตมากกว่า

[แก้] Mealy Model

คือแบบจำลองของวงจร ซีเควนเชียล จาก 1 ใน 2 ประเภท อีกประเภทหนึ่ง คือ Moore model

ภาพด้านล่างนี้คือ แบบจำลอง  Mealy จะเห็นได้ว่า มี output รวมอยู่กับการเปลี่ยน State จากStateหนึ่ง ไปอีก State หนึ่ง 

เช่น จากState A ไป B จะมีลูกศรเป็นตัวชี้ และที่ลูกศรมีตัวเลขกำกับ 0/1 หมายถึงเมื่อinput เป็น 0 จะให้ output 1 และ Stateเปลี่ยนจาก A ไป B

ภาพ:exam01.jpg

ซึ่งเราสามารถที่จะนำ Mealy Model มาทำการวิเคราะห์วงจรซีเควนเชียลได้ โดยการวิเคราะห์วงจร ซีเควนเชียล แยกออกเป็น 4 ประเภทด้วยกัน คือ

(แบบที่ 1)วงจร Pulsed synchronous วงจรแบบนี้มี Input เป็น pulse และหน่วยความจำมีนาฬิกาดังที่ได้กล่าวมาแล้ว แต่ input pulse จะเข้าจังหวะ (Synchronous) กับนาฬิกา หรือ ไม่เข้าจังหวะ (Asynchronous) กับนาฬิกาก็ได้ซึ่งทั้งสองกรณี input pulse จะมีผลต่อการเปลี่ยนสถานะต่อไปของวงจร ในช่วงจังหวะที่มี pulseนาฬิกาเท่านั้น

(แบบที่ 2) วงจร Level synchronous วงจรแบบนี้จะรวมถึงวงจรทั้งหมดที่มีหน่วยความจำควบคุมโดยสัญญาณนาฬิกา และ สัญญาณ Input เป็น level ไม่ว่า level นั้นจะเข้าจังหวะกับสัญญาณนาฬิกาหรือไม่

(แบบที่ 3) วงจร Pulsed asynchronous ต้องใช้ความรอบคอบเป็นพิเศษ เนื่องจากไม่มี pulse นาฬิกาเป็นตัวกำหนดจังหวะที่จะเกิดการ เปลี่ยนแปลงของวงจร ดังนั้น State ของวงจรจะเปลี่ยนแปลงทันที เมื่อ input ที่เข้ามาเปลี่ยนแปลง

(แบบที่ 4) วงจร เลเวลอซิงโครนัสเป็นวงจรที่มี input เป็น level และไม่มี clock ควบคุมหน่วยความจำป็นแบบที่วิเคราะห์ได้ยากที่สุด ทำให้เราสามารถวิเคราะห์วงจรลอจิก ต่างๆ โดยหาState table และ Timing diagram ของมันได้


และภาพด้านล่างนี้คือ mealy machine timing diagramตัวอย่างแผนผังเวลาการทำงานของวงจรแต่ละวงจร ภาพ:timing.jpg

ตัวอย่าง :จากตารางสภาวะข้างล่างนี้เป็นรูปแบบของ มิลลี ให้หา

   ก) ผังสภาวะ (state diagram)
 ข) ASM. Chart
 ค) คุณลักษณะของ Z (ลำดับของ Z) เมื่อมี Input x เป็นดังนี้ x = 011011 และสภาวะเริ่มต้นอยู่ที่สภาวะ A

ภาพ:ex02.jpg

วิธีทำ พิจารณาจากตารางสภาวะที่ให้มา จะพบว่าOutput Z จะขึ้นกับทั้ง Input x และ PS (y) โดยที่ Input x = 0, 1 (มี 2 ค่า) ตัวแปรสภาวะ (state) = A, B, C (3 สภาวะ) มักแทนด้วย Code เช่น A = 00, B = 01, C = 10 Output Z = 0, 1 (2 ค่า)

ก) เขียน state diagram ได้ดังนี้

ภาพ:ex03.jpg

ข) ASM. Chart เขียนได้ดังนี้

ภาพ:ex04.jpg

ค) หาลำดับของ output Z เมื่อ input x = 011011 และ สภาวะเริ่มต้นที่สภาวะ A ∴ เราสามารถแสดงการทำงานได้ดังนี้

เวลา : 1 2 3 4 5 6

Input x : 0 1 1 0 1 1 (6 bit)

สภาวะเริ่มต้น y  : A B A C A C

สภาวะต่อไป Y  : B A C A C C

Output Z  : 1 1 0 0 0 0

[แก้] Mealy Finite State Machine

มาทำความรู้จักกับ Finite State Machines หรือ FSMs ซึ่งเป็นเครื่องมือที่ใช้สำหรับออกแบบวงจรที่มีสัญญาณนาฬิกาควบคุมการทำงาน (Sequential) มีการทำงานเป็นสถานะ (State) แต่ละสถานะจะมีการทำงานที่แตกต่างกัน ค่าเอาต์พุตและสถานะถัดไป จะถูกกำหนดโดยอินพุตที่เข้ามายังสถานะนั้นๆ ทำให้สามารถเปลี่ยนจากสถานะหนึ่งไปยังสถานะอื่นๆได้ ซึ่งเป็นเครื่องมือที่มีประโยชน์มากในการออกแบบระบบดิจิตอล เพื่อนำไปอธิบายการทำงานของวงจร โดยทั่วไปวงจรที่ประกอบไปด้วย หน่วยความจำ หรือรีจีสเตอร์ ถือว่าเป็น Finite State Machines (FSMs)


[แก้] ข้อความหัวเรื่อง 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 ที่มีการทำงานดังรูป

ภาพ:fsm1.jpg

การออกแบบวงจร FSM

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