เครื่องจักรแบบเมลลี่

เครื่องจักรเมลลี่ (อังกฤษ: Mealy Machine) เป็นเครื่องสถานะจำกัดชนิดหนึ่งซึ่งเอาต์พุตของสถานะนั้น ๆ เป็นฟังก์ชันของสถานะปัจจุบันและอินพุต ด้วย

การวิเคราะห์วงจรเปลี่ยนสถานะตรงตามจังหวะเวลา

การวิเคราะห์วงจรเปลี่ยนสถานะตรงตามจังหวะเวลา (Clocked Synchronous State-Machine Analysis)

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

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

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

จากแผนภาพวงจร จะเห็นว่าเป็น clocked synchronous เครื่องสถานะ ชนิด 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

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

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

ซึ่งเราสามารถที่จะนำ 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 ตัวอย่างแผนผังเวลาการทำงานของวงจรแต่ละวงจร

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

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

วิธีทำ พิจารณาจากตารางสภาวะที่ให้มา จะพบว่า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 ค่า)

1. เขียน state diagram ได้ดังนี้

   

2. ASM. Chart เขียนได้ดังนี้
3. หาลำดับของ output Z เมื่อ input x = 011011 และ สภาวะเริ่มต้นที่สภาวะ A

ดังนั้น เราสามารถแสดงการทำงานได้ดังนี้

1. เวลา : 1 2 3 4 5 6
2. Input x : 0 1 1 0 1 1 (6 bit)
3. สภาวะเริ่มต้น y : A B A C A C
4. สภาวะต่อไป Y : B A C A C C
5. Output Z : 1 1 0 0 0 0

Mealy Finite State Machine

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

อ้างอิง

• Mealy, George H. (1955). A Method for Synthesizing Sequential Circuits. Bell System Technical Journal. pp. 1045–1079.

• Holcombe, W.M.L. (1982). Algebraic automata theory. Cambridge Studies in Advanced Mathematics. Vol. 1. Cambridge University Press. ISBN 0-521-60492-3. Zbl 0489.68046.
• Roth, Charles H. Jr. (2004). Fundamentals of Logic Design. Thomson-Engineering. pp. 364–367. ISBN 0-534-37804-8.
• Akhavi, Ali; Klimann, Ines; Lombardy, Sylvain; Mairesse, Jean; Picantin, Matthieu (2012). "On the finiteness problem for automaton (semi)groups". International Journal of Algebra and Computation. 22 (6). arXiv:1105.4725. Bibcode:2011arXiv1105.4725A. doi:10.1142/S021819671250052X. S2CID 47518684. Zbl 1280.20038.