Verilog Programming Style: Finite State Machine

บล็อกนี้เป็นบล็อกที่ต่อมาจากบล็อก Verilog Programming Style: Declaration

ในบล็อกนี้เรามาดูส่วนสำคัญนั่นคือ Finite State Machine ซึ่งเป็นส่วนควบคุมหลัก Finite State Machine ใน module ATM จะเขียนแบบ two-block ดังนี้

 //state
 reg[2:0] ps=0,ns=0;
 always@(posedge clock)begin
 if(command==RESET) ps<=0;
 else ps<=ns;
 end

 always@*begin

enT=0;enFh=0;enH=0;nT=memT;nFh=memFh;nH=memH;nBalance=balance;nDraw=draw;ready=0;

ns=0;
 case(ps)
 0:begin ns=1;  ready=1; nDraw=0; nT=0; nFh=0; nH=0; end
 1:begin
 ready=1;
 case(command)
 DEPOS: ns=2;
 WDRAW:ns=3;
 default:ns=0;
 endcase
 end
 2:begin
 nBalance=balance+(t<<3)+(t<<1)+(fh<<2)+fh+h;
 ns=0;
 end
 3:begin
 if(balance<need_money) ns=0;
 else begin nBalance=balance-need_money; nDraw=need_money; ns=4; end
 end
 4:begin
 if(draw>10) begin nDraw=draw-10; nT=memT+1; ns=4; end
 else begin ns=5; end
 end
 5:begin
 if(draw>5) begin nDraw=draw-5; nFh=memFh+1; ns=5; end
 else begin nH=draw; ns=6; end
 end
 6:begin enT=1; enFh=1; enH=1; ns=0; end
 default: begin ns=0; end
 endcase
 end

คราวนี้เราก็มาดูเป็นส่วนๆ เหมือนเช่นเคย

Block ที่ 1 ของ Finite State Machine

 //state
 reg[2:0] ps=0,ns=0;
 always@(posedge clock)begin
 if(command==RESET) ps<=0;
 else ps<=ns;
 end

Block ที่ 1 นั้นก็เหมือนการประกาศ register ปกตินั่นคือ register ps และ ns เป็น next signal ใน ISE Design คำว่า ps มักถูก hilight เป็นสีน้ำเงิน ไม่ต้องตกใจ ps ไม่ได้เป็นคำสงวนที่ห้ามใช้ประกาศเป็นชื่อแต่อย่างใด เพียงแต่โดน hilight ให้มันดูเด่นขึ้นเฉยๆ น่าจะเกิดจากการที่ ps ไปตรงกับตัวย่อคำว่า “picosecond” พอดี

Default Value

always@*begin

enT=0;enFh=0;enH=0;nT=memT;nFh=memFh;nH=memH;nBalance=balance;nDraw=draw;ready=0;

ns=0;

Block ที่ 2 เป็นบล็อกที่ผมมักเรียกว่า star block บล็อกนี้มักเป็นบล็อกเดียวใน module ที่มี always@* ถ้าในวงจรนี้ไม่มี combinational logic ส่วนอื่นๆ เช่น encoder หรือ decoder อีก หลัง always@* มักมีการประกาศกำหนดค่าปริยาย (Default Value) ของ signal ต่างๆ signal ที่จะถูกควบคุมจะใน star block นี้แบ่งได้ออกเป็น 4 ประเภท คือ enable signal ของ inout, next signal ของ register, control signal ของ register พิเศษเช่น counter และ flag signal เช่น ready ของ module เอง ทั้งนี้ควรระบุค่า default ทั้งหมดของ signal ที่จะถูก Finite State Machine ควบคุม เพื่อกันไม่ให้วงจร synthesis signal ดังกล่าวเป็น Latch ได้ (ซึ่ง Latch นี่เองมักจะนำไปสู่ “บั๊ก”)

ทั้งนี้พึงสังเกตว่า เราไม่ควรจะไปควบคุม register ต้นแบบโดยตรง แต่ควรควบคุมผ่าน next signal ของ register และเพื่อให้ปรับเป็นค่าใหม่นั้นใน clock ถัดไป

State Label และ Reset State

 case(ps)
 0:begin ns=1;  ready=1; nDraw=0; nT=0; nFh=0; nH=0; end

การสร้าง state transition table นั้นเรามักใช้ switch-case เพื่อทำให้โค้ดดูดีขึ้น (Clean Code) เราอาจตั้งชื่อ state ผ่าน parameter ได้ แต่ไม่แนะนำเวลาทำ Lab เพราะเวลาแก้ไขจะต้องแก้ไขซ้ำซ้อน คือต้องไปเพิ่มตรงที่ประกาศ parameter และก็ต้องมาเพิ่มชื่อ state ดังกล่าวใน star block อีก ทางที่ดีหากไม่อยากสับสนให้ comment ไว้เหนือ state จะดีกว่า

state 0 มักถูกเก็บไว้เป็น reset state คือยังไม่ใช่ส่วนที่เริ่มต้นจริงๆ แต่เป็นส่วนที่ clear ค่าต่างๆ เพื่อพร้อมที่จะเริ่มทำงานต่อไป เป็น state ที่จะกระโดดมาเวลา reset ตอนเริ่มต้นออกแบบมักจะเขียนกันไว้ว่า

 case(ps)
 0:begin ns=1; end

อย่างนี้ก่อนเป็น passing state เปล่าๆ หนึ่งอัน แล้วค่อยมาวิเคราะห์ต่อว่าค่าใดเป็นค่าที่ต้อง clear ก่อนเพื่อให้ module พร้อมที่จะทำงานในรอบใหม่ต่อไป

Command Choice

 1:begin
    ready=1;
    case(command)
       DEPOS: ns=2;
       WDRAW:ns=3;
       default:ns=0;
    endcase
    end

state หนึ่งที่น่าสนใจคือ state ที่เลือก command; state นี้มักจะอยู่เป็น state ที่ 1 ต่อจาก reset state; state นี้ไว้พิจารณาดูว่าขณะนี้มี command อะไรเข้ามาบ้าง; command choice มักอยู่ในรูปแบบ switch-case และที่สำคัญเช่นกันคืออย่าลืม default case (เดี๋ยวจะถูกเข้าใจเป็น latch อีก) และที่ต่างจากภาษาโปรแกรมส่วนใหญ่คือ switch-case ใน Verilog จะไม่ต้อง break; และใช้ keywork case แทน keyword switch ทั้งนี้เตือนเพราะจะสับสนเวลาเขียนโปรแกรมในภาษาอื่น

Arithmetic Logic Transition

2:begin
   nBalance=balance+(t<<3)+(t<<1)+(fh<<2)+fh+h;
   ns=0;
   end

หลายครั้งที่ในวงจรต้องมีการคำนวณที่ซับซ้อนเช่น คูณหรือหาร แต่ทว่านี่ไม่ใช่ภาษาโปรแกรมเชิงซอฟต์แวร์ ดังนั้นเราจึงต้องคิดว่าการคำนวณเหล่านั้นจะ synthesis ออกมาเป็นวงจรอย่างไร สำหรับการคูณหรือหารด้วยค่าคงที่บางจำนวน เช่น 2n อาจลดรูปเป็นวงจรได้ง่ายด้วยการ shift คูณ 2 ก็ shift left 1 ที คูณ 4 ก็ shift left 2 ที เป็นต้น

การหารก็ในทางกลับกัน หาร 2 ก็ shift right 1 ที หาร 4 ก็ shift right 2 ที หากคูณค่าคงที่ที่ไม่ใช่ 2n ก็อาจใช้กฎการแจกแจงเข้าช่วยเช่น t*10 ก็กระจายเป็น (t*8)+(t*2) ก็กลายเป็น (t<<3)+(t<<1) จะใช้เลขอะไรช่วยแจกแจงนั้นก็สามารถดูได้ด้วยการเปลี่ยนเลขนั้นเป็นไบนารีดูเช่น t*15 15 มีเลขไบนารีเป็น 1111 หรือกล่าวอีกนัยหนึ่งว่า 15=8+4+2+1 ได้นั่น เอง ก็จะได้ว่า t*15= (t*8)+(t*4)+(t*2)+(t*1) = (t<<3)+(t<<2)+(t<<1)+t นั่นเอง

สำหรับการหารเลขที่ไม่ใช่ 2n อาจมีปัญหาสักหน่อย เพราะไม่มีกฎการแจกแจงการหาร เราเปลี่ยนการหารเป็นการคูณไมได้เพราะจะสร้างเป็นทศนิยมซ้ำ เช่น t/3=t*1/3 1/3 ในไบนารีก็จะเป็น 0.01010101… อาจทำให้เสียความแม่นยำลงไปได้ ทางที่ดีเราอาจใช้วน loop แล้วค่อยๆ ลบเอา ระหว่างนั้นก็เพิ่มตัวหาร หรือที่เรากันว่า childish algorithm จะดีกว่า

สำหรับการคูณหารค่าใน register 2 ตัวก็อาจทำโดยใช้ loop ด้วยการบวกไปเรื่อยๆ สำหรับการคูณ หรือลบไปเรื่อยๆ สำหรับการหาร หรืออาจจะใช้ algorithm การ shift หรือเลือกใช้การ represent ตัวเลขด้วยระบบ floating point เพราะหากมีการคำนวณจำนวนมาก floating point จะใช้ logarithm เข้าช่วยเพื่อเปลี่ยนการคูณ-หารเป็นการบวก-ลบได้ สำหรับ balance ในที่นี้เราสามารถมองได้เป็น nBalance=balance+(t*10)+(fh*5)+h จะสังเกตเห็นได้ว่า แบงค์พัน แบงค์ห้าร้อย และแบงค์ร้อยจะถูกคูณแค่ 10 5 และ 1 ตามลำดับเท่านั้น นั่นเพราะเราเก็บ balance ในหน่วยร้อยบาทนั่นเอง การออกแบบวิธีการ represent ข้อมูลอย่างเหมาะสมสามารถช่วยลดความซับซ้อนในการคำนวณได้

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

Type of State and Looping State

3:begin
 if(balance<need_money) ns=0;
 else begin nBalance=balance-need_money; nDraw=need_money; ns=4; end
 end
 4:begin
 if(draw>10) begin nDraw=draw-10; nT=memT+1; ns=4; end
 else begin ns=5; end
 end
 5:begin
 if(draw>5) begin nDraw=draw-5; nFh=memFh+1; ns=5; end
 else begin nH=draw; ns=6; end
 end
 6:begin enT=1; enFh=1; enH=1; ns=0; end
 default: begin ns=0; end
 endcase
 end
//โค้ดส่วนนี้แสดงอัลกอริทึมการทอนเงินใน Lab 2 ให้ดูด้วย

ถ้าหากลองพิจารณาดูจะพบว่าลักษณะการเขียน state แบ่งได้เป็น 3 แบบใหญ่ๆ คือ

  1. Passing State คือ state ที่จะไป state ถัดไปแน่นอน แต่มาแวะผ่านเพื่อ set ค่า, clear ค่า, รอการทำงาน และ อื่นๆ เช่น Reset State ดังกล่าวขั้นต้น
  2. Choice State คือ state ที่พิจารณาว่าสถาการณ์ในปัจจุบันนี้ควรจัดการด้วยการไปที่ state ไหน ส่วนมากจะใช้พิจารณา command
  3. Looping State คือ state ที่จะดักทำการเปลี่ยนค่าให้สอดคล้องกับเงื่อนไขก่อน แล้วจึงปล่อยให้ระบบไปยัง state อื่นต่อไป ลักษณะสำคัญของ state แบบนี้คือจะมีการทำงานหลัง if เพื่อดักให้ค่าที่ไม่เหมาะสมเข้ามา เปลี่ยนค่าต่างๆ และกำหนดให้ nextstate เป็น state เดิม จนกว่าจะผ่านเงื่อนไขจึงจะผ่านไปได้ ดังนั้นจึงทำให้ Looping State มักถูกออกแบบแบบ Mealy เพราะมีการเปลี่ยนแปลงหลังจากที่ผ่านการเช็คเงื่อนไขแล้ว หรือเขียนใน ASM Chart เป็นรูปวงรี

การเขียนวิธีการควบคุม control signal ในแต่ละ state มีหลายแบบ บ้างเขียนไล่ control signal ที่จะควบคุมใน state นั้นๆ การไล่ก็มี 2 แบบ บ้างก็เขียนไล่ในบรรทัด ซึ่งมีข้อดีคือจะทำให้โค้ดดูสั้นเป็นพิเศษ แต่โค้ดจะดูยากหรือจะเขียนไล่สัญญาณละบรรทัดก็ได้ แต่ if else หรือ case ส่วนมากจะเขียน case ละบรรทัด บางคนอาจแยก control signal บางอันออกมา เขียนนอก Finite State Machine เป็น Mealy Assignment เช่น

assign flag= (ps==2)||(ps==8);

ข้อดีของวิธีนี้คือสามารถลด control signal ที่ Finite State Machine ควบคุมแต่ข้อเสียคือถ้าจะเปลี่ยน state จะต้องแก้หลายที่ แต่ก็สามารถทำได้ แต่โค้ดที่ไม่ควรทำเลยคือการไป hack state คือไปเก็บ state ไปเปลี่ยน state นอก Finite State Machine กล่าวโดยง่ายคือพยายามทำอะไรที่พยายามไปควบคุม Finite State Machine ซึ่งไม่ควร เพราะ Finite State Machine ควรจะเป็นตัวที่ควบคุมทั้งหมด ทั้งนี้การพยายามควบคุม Finite State Machine จะทำให้ synthesis ได้วงจรที่ซับซ้อนและมักจะตามมาด้วยปัญหาเสมอ

โดยภาพรวมแล้วโค้ด Verilog จะมีความยาวหลายบรรทัด แต่มี pattern ซ้ำๆ กันจนดูเหมือน copy paste ไปๆมาๆ ทั้งนี้ก็เพื่อเหตุผลเดียวอันเป็นหัวใจสำคัญของการเขียน Verilog นั่นคือ ให้วงจรสามารถ synthesis ได้ง่ายและตรงประเด็นที่สุด

This entry was posted in เทคนิควิธีการ, Lab Verilog and tagged , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s