แนะนำการออกแบบ Finite State Machine

คำจำกัดความอย่างง่ายของ Finite State Machine (FSM) แบบซิงโครนัสคือระบบดิจิทัลที่สามารถจำสถานะ และถูกขับเคลื่อนโดยสัญญาณคล็อกทำให้สถานะเปลี่ยนไปโดยขึ้นกับอินพุตและสถานะก่อนหน้า พื้นฐานการทำงานนี้ครอบคลุมระบบอย่างง่ายที่มี DFF ตัวเดียวไปจนถึงระบบคอมพิวเตอร์ที่มีความซับซ้อน ในบทความนี้จะแนะนำขั้นตอนการออกแบบและอิมพลิเมนต์ FSM ลงบน CPLD โดยอาศัยตัวอย่างง่ายๆ แนวทางหลักที่นยมใช้คือ อาศัยแผนภาพสถานะ (state diagram) และ ASM (Algorithmic State Machine)

โจทย์ปัญหา

รูปที่ 1 แสดงสวิทซ์ 3 ทางที่ใช้เปิด/ปิดหลอดไฟบริเวณบันได ปกติที่ใช้ในบ้านทั่วไปจะเป็นสวิทซ์แบบค้างสถานะ แต่ในที่นี้จะใช้สวิทซ์แบบกดติดปล่อยดับ และใช้ FSM เป็นตัวจำสถานะของระบบ การทำงานที่ต้องการคือ เมื่อกดสวิทซ์ที่ชั้นบนหรือชั้นล่างก็ตาม หลอดไฟจะเปลี่ยนสถานะจากเดิม คือหากหลอดดับอยู่ก็จะติดสว่าง ถ้าสว่างอยู่ก็จะดับ

รูปที่ 1 ระบบไฟสามทางโดยใช้สวิทซ์กดติดปล่อยดับ

เพื่อให้ปัญหาง่ายขึ้นจะสมมุติว่าบ้านนี้มีผู้อาศัยคนเดียว (และไม่มีผี) ดังนั้นไม่มีทางที่สวิทซ์ทั้งสองจะถูกกดพร้อมกัน เราจะอิมพลิเมนต์วงจรลงบน CPLD ของ Xilinx โดยอาศัยบอร์ด CPLD Explorer XC9572 (ผลิตภัณฑ์ของบริษัท www.ailogictechnology.com)ซึ่งมีอุปกรณ์ที่ต้องการติดตั้งอยู่แล้ว คือใช้สวิทซ์กด PB1 และ PB2 แทนสวิทซ์ A,B ในรูปที่ 1 และใช้ LED1 แทนหลอดไฟ สวิทซ์กดบนบอร์ดนี้จะให้ลอจิก 0 เมื่อกด (active low)

การออกแบบอย่างง่าย

วิธีการหนึ่งในการแก้ปัญหาทั่วไปคือเริ่มต้นจากความคิดง่ายๆ ก่อนแล้วจึงต่อยอดภายหลัง ลองพิจารณาว่าระบบนี้ควรจะมีจำนวนสถานะเท่าใด การทำงานของหลอดคือไม่ติดสว่างก็ดับ ดังนั้นโดยพื้นฐานแล้วสองสถานะน่าจะเพียงพอ หรือไม่อย่างใด? ทดลองเขียนแผนภาพสถานะสำหรับ Moore machine (คือระบบที่เอาต์พุตขึ้นกับสถานะเท่านั้น) ตามรูปที่ 2

รูปที่ 2 แผนภาพที่ประกอบด้วย 2 สถานะ

จากแผนภาพอธิบายได้ว่าถ้าไม่มีการกดสวิทซ์ AB = 11 สถานะจะคงเดิม แต่ถ้าหากกดสวิทซ์ตัวหนึ่งตัวใด (AB = 01 หรือ AB = 10) หลอดจะเปลี่ยนเป็นสถานะตรงข้าม จากแผนภาพจะสามารถเขียนเป็นตารางการเปลี่ยนสถานะได้ดังนี้ (โดยให้ AB = 00 เป็น X (don't care) เนื่องจากไม่สามารถเกิดขึ้นได้)

มาถึงตรงนี้ผู้มีประสบการณ์ออกแบบมาก่อนคงจับได้ว่าการออกแบบนี้ไม่ถูกต้องและทำงานไม่ได้ตามวัตถุประสงค์ อย่างไรก็ตามเพื่อแสดงขั้นตอนทั้งหมดของการออกแบบและอิมพลิเมนต์ จะลองทำต่อไปก่อนเพื่อดูว่าได้ผลเป็นอย่างไร ใส่ข้อมูลจากตารางลงใน คาร์นอฟ แมพ (Karnaugh map)

และทำการลดทอน จะได้สมการบูลีนสำหรับการอัพเดทสถานะดังนี้

q_new = A'q' + B'q' + ABq ซึ่งเป็นลอจิกสำหรับอินพุตของ DFF ดังนั้นวงจรทั้งหมดสามารถเขียนได้ดังรูปที่ 3 รูปที่ 3 วงจรที่ได้จากการออกแบบอย่างง่าย ในการอิมพลิเมนต์บน CPLD อาจเขียนโดยใช้ภาษาฮาร์ดแวร์ เช่น Verilog ดังนี้

module sw_3way(
    input A,
    input B,
            input Clk,
    output Y
    );
  reg q,Qp;
    always @ (A,B,q)
  begin
  // next states
  Qp = (~A&~q)|(~B&~q)|(A&B&q);
  end
  always @ (posedge Clk)
  begin
     q <= Qp;
  end
 assign Y = q;
endmodule

สร้างโปรเจ็คบนซอฟต์แวร์ Xilinx ISE และกำหนดขาสำหรับสัญญาณ A,B,Y,Clk เป็นขา 39,40,38,5 ของ XC9572 ตามลำดับ ผลการทำงานดูได้จากคลิปนี้

จะเห็นว่าเอาต์พุตของวงจรไม่เป็นไปตามที่ต้องการ ปัญหาทีเกิดขึ้นคือสัญญาณคล็อกบนบอร์ดมีความถี่สูงกว่าความเร็วในการกดสวิทซ์ของมนุษย์ ดังนั้นเมื่อสวิทซ์ใดถูกกด (AB=01 หรือ AB=10) จากรูปที่ 1 จะเห็นว่าสถานะจะสลับเปลี่ยนระหว่าง S0 กับ S1 หลายครั้ง (อาจเป็นหลายร้อยหลายพันครั้ง) ดังนั้นสถานะสุดท้ายเมื่อปล่อยสวิทซ์จึงไม่สามารถคาดเดาได้

วิธีแก้อย่างง่ายๆ หากต้องการใช้วงจรนี้คือ ใช้ความถี่คล็อกต่ำมากๆ และเหมาะสมกับช่วงเวลาในการกดสวิทซ์ของผู้ใช้ กล่าวคือต้องการให้วงจรเปลี่ยนสถานะเพียงครั้งเดียวต่อการกดสวิทซ์แต่ละครั้ง ตัวอย่างเช่นใช้คล็อกประมาณ 1-2 Hz ในการทดลองบนบอร์ดจะใช้วิธีเพิ่มโมดูลหารความถี่คล็อกลงจนเหลือประมาณ 1 Hz (ถ้าต้องการนำไปใช้งานจริงแนะนำให้สร้างคล็อกจากไอซีตั้งเวลา เช่น 555 หรือวงจรออสซิเลเตอร์แบบ RC ดีกว่าการหารคล็อกความถี่สูงซึ่งต้องใช้ฟลิปฟล็อปจำนวนมาก)

คลิปที่สองด้านล่างแสดงผลการทำงาน พบว่าพอใช้งานได้หากผู้ใช้กดอย่างฉลาด คือเมื่อเห็นหลอดไฟเปลี่ยนสถานะเมื่อใดก็ปล่อยมือทันที แต่ถ้ากดแล้วปล่อยเร็วเกินไปสถานะก็ไม่เปลี่ยน หรือหากกดแช่ไว้นานก็จะเห็นหลอดไฟเปลี่ยนสถานะกลับไปกลับมาด้วยความถี่เท่ากับสัญญาณคล็อก

การออกแบบที่ดีกว่า

จากปัญหาที่เกิดขึ้นในแผนภาพสถานะอย่างง่ายรูปที่ 1 ทำให้เกิดความคิดในการพัฒนาให้ดีขึ้น คือเพิ่มสถานะคั่นระหว่างสถานะติด/ดับ เดิม เพื่อป้องกันการเปลี่ยนไปมาอย่างไม่สิ้นสุด กล่าวได้ว่าสถานะที่เพิ่มเข้ามาจะเป็นตัวดักการเปลี่ยนแปลงในขณะที่สวิทซ์กดค้างอยู่นั่นเอง การออกแบบใหม่นี้แสดงได้ในรูปที่ 4 สมมุติว่าเริ่มต้นจาก S0 (หลอดดับ) เมื่อมีการกดสวิทซ์ใดๆ เช่น AB = 01 สถานะจะเปลี่ยนเป็น S1 ทำให้หลอดติด แต่สถานะจะยังติดอยู่ที่ S1 ตราบเท่าที่สวิทซ์นั้นยังถูกกด (AB = 01) เมื่อปล่อยสวิทซ์ AB = 11 สถานะจะเปลี่ยนไปที่ S2 คือหลอดยังติดอยู่ แต่พร้อมรับการกดสวิทซ์ครั้งต่อไป เมื่อมีการกดสวิทซ์ สถานะจะวิ่งจาก S2 ติดอยู่ที่ S3 และไปยัง S0 เมือปล่อยสวิทซ์

รูปที่ 4 แผนภาพสถานะใหม่ที่ประกอบด้วย 4 สถานะ

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

รูปที่ 5 แผนภาพ ASM สำหรับการออกแบบใหม่

หลังจากนั้นแปลง ASM เป็นภาษา HDL กระทำได้โดยง่าย ตัวอย่างสำหรับ Verilog ดาวน์โหลดได้จากลิงค์ด้านล่างนี้ sw3_asm4.v สร้างโปรเจ็คและโปรแกรมลงบนบอร์ด ผลการทำงานของการออกแบบใหม่นี้แสดงได้ดังคลิปนี้

จะเห็นว่าวงจรยังมีข้อผิดพลาดอยู่ เกิดอะไรขึ้น?

ปัญหาใหม่ที่ทำให้ระบบ FSM นี้ทำงานผิดพลาดคือสิ่งที่เกิดขึ้นปกติในวงจรที่รับอินพุตจากสวิทซ์ ดังแสดงในรูปที่ 6 ขณะที่มีการกดหรือปล่อยสวิทซ์ จะเกิดปรากฏการณ์ที่เรียกว่าการเด้งของหน้าสัมผัส (contact bounce) ทำให้สัญญาณมีความไม่แน่นอนอยู่ในช่วงสั้นๆ และสามารถทำให้วงจรดิจิทัลทำงานผิดพลาดหากอ่านสัญญาณในช่วงนี้ ช่วงเวลาของการเด้งนี้ขึ้นอยู่กับสวิทซ์ ซึ่งผู้ผลิตมักจะให้ค่ากรณ๊เลวร้ายสุด โดยทั่วไปมีค่าไม่ควรกิน 20 มิลลิวินาที

รูปที่ 6 การเด้งของหน้าสัมผัสในสวิทซ์

การแก้ปัญหาการเด้งนี้ทำได้หลายวิธี เช่นหน่วงเวลาการอ่านให้พ้นช่วงการเด้งไปก่อน สามารถค้นหาจากอินเตอร์เน็ตและเลือกวิธีที่ชอบได้ ในกรณีที่เราเขียนโปรแกรมโดยภาษา Verilog อยู่แล้ว จึงต้องการโมดูล debounce ที่เป็นภาษาเดียวกันจะได้เชื่อมต่อกันได้ง่าย เมื่อค้นหาจากอากู๋โดยคีย์เวิร์ด "switch debounce Verilog" จะได้ URL มากมาย ในที่นี้เลือกอันดับแรกคือเว็บ Debounce Logic Circuit (with Verilog example) และเพิ่มโมดูล DeBounce_v.v ที่มีให้ในเว็บนั้นเข้ากับโปรเจ็คเดิม (สำหรับคำอธิบายการทำงานสามารถอ่านได้จากข้อมูลในเว็บ ซึ่งมีประโยชน์มาก) ไฟล์ใหม่ที่เพิ่มเติมส่วน debounce เข้าไป สามารถดาวน์โหลดได้จากลิงค์นี้ sw3_asm4db.v

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

บทสรุป

บทความนี้นำเสนอตัวอย่างการออกแบบระบบ FSM แบบซิงโครนัส จุดมุ่งหมายคือการอธิบายการออกแบบสมัยใหม่ คือใช้โปรแกรมลงชิพประเภท CPLD/FPGA แทนการนำเอาไอซีเกทและฟลิปฟลอปแบบ TTL หรือ CMOS มาต่อกันบนบอร์ด และใช้ภาษา HDL แทนการใช้ schematics ข้อดีของแนวทางสมัยใหม่คือมีความยืดหยุ่น เหมาะกับวงจรที่ซับซ้อนเพราะจะลดขนาดวงจร การใช้พลังงาน และเวลา อย่างไรก็ตามการนำเสนอในบทความได้เลือกตัวอย่างที่ง่าย เพื่อหวังว่าผู้อ่านจะได้เข้าใจหลักการและขั้นตอนในออกแบบจนถึงอิมพลิเมนต์ได้ชัดเจนขึ้น