FSM Vending Machine

কেন এই প্রজেক্ট

Finite State Machines লেসনে আমরা দেখেছি একটা সিস্টেম কীভাবে তার ইতিহাস একটা সসীম সংখ্যক “state”-এ সংক্ষিপ্ত করে রাখে, আর নতুন ইনপুট এলে সেই state বদলায়। ভেন্ডিং মেশিন এই ধারণার জন্য প্রায় নিখুঁত একটা উদাহরণ — মেশিনটার পুরো ইতিহাস মনে রাখার দরকার নেই, শুধু এইটুকু মনে রাখলেই চলে: “এখন পর্যন্ত মোট কত টাকা ঢোকানো হয়েছে?” সেই একটা সংখ্যাই একটা state।

এই প্রজেক্টে পুরো ডিজাইন-প্রক্রিয়াটা হাতে-কলমে করব — states এনুমারেট করা থেকে শুরু করে শেষে দুইটা ভিন্ন মাধ্যমে (গেট-লেভেল সার্কিট, আর Verilog) বাস্তবায়ন পর্যন্ত। আর এই ছোট্ট প্রজেক্টটাই আসলে এই মডিউলের সবচেয়ে বড় প্রজেক্ট — Single-cycle CPU-এর — একটা রিহার্সাল। CPU-এর PC (program counter) রেজিস্টার আর তার state-machine-চালিত control logic ঠিক এই একই প্যাটার্নে বানানো হবে, শুধু states-এর সংখ্যা অনেক বড়।

Moore নাকি Mealy?

দুইটা বিকল্প ছিল:

• Mealy machine: আউটপুট নির্ভর করে state এবং বর্তমান ইনপুটের উপর — কয়েন ঢোকার সাথে সাথে সেই একই clock cycle-এ dispense সিগন্যাল আসতে পারে, এক cycle কম সময় লাগে।
• Moore machine: আউটপুট নির্ভর করে শুধু state-এর উপর — dispense সিগন্যাল আসবে state বদলে যাওয়ার পরের cycle-এ, কিন্তু পুরো cycle জুড়ে স্থির থাকে, input মাঝপথে বদলে গেলেও glitch করে না।

এই প্রজেক্টে Moore বেছে নিচ্ছি। কারণ: dispense সিগন্যাল একটা physical actuator (মোটর, সোলেনয়েড) চালায়, আর মানুষ কয়েন ঢোকানোর গতি একটা ক্লক সাইকেলের তুলনায় অসীম ধীর — এক cycle এক্সট্রা লেটেন্সি কোনো ব্যাপারই না। বিপরীতে, Mealy machine-এ আউটপুট সরাসরি ইনপুটের সাথে কম্বিনেশনালি জোড়া থাকায়, ইনপুট লাইনে সামান্য নয়েজ বা bounce (একটা যান্ত্রিক কয়েন-সুইচে যা খুবই বাস্তব একটা সমস্যা) সরাসরি dispense আউটপুটে glitch তৈরি করতে পারে — একটা মোটর সংক্ষিপ্ত সময়ের জন্য ভুলভাবে চালু হয়ে যেতে পারে। মানুষ-গতির সিস্টেমে glitch-প্রতিরোধ, extra latency-র চেয়ে অনেক বেশি গুরুত্বপূর্ণ — তাই Moore।

State ডিজাইন

কয়েন মাত্র দুই মূল্যের — ৫ আর ১০ টাকা — আর টার্গেট মূল্য ১৫ টাকা। তাই “এখন পর্যন্ত কত টাকা” হিসেবে সম্ভাব্য অবস্থা মাত্র কয়েকটা:

State	অর্থ	3-bit encoding
S0	০ টাকা জমা হয়েছে	000
S5	৫ টাকা জমা হয়েছে	001
S10	১০ টাকা জমা হয়েছে	010
DISP	১৫ টাকা পূর্ণ — item dispense, change নেই	011
DISPCH5	২০ টাকা জমা হয়েছিল — item dispense + ৫ টাকা change	100

S10-এ থাকা অবস্থায় সর্বোচ্চ একটা ১০-টাকার কয়েন এলে মোট হয় ২০ টাকা — তার বেশি ওভারপে কখনো সম্ভব না, কারণ ১৫ টাকা পার হওয়া মাত্রই মেশিন dispense state-এ চলে যায়, আর কয়েন নেওয়া বন্ধ করে দেয়। তাই মাত্র ৫টা state-ই যথেষ্ট — ৩-বিট এনকোডিং-এ (৮টা সম্ভাব্য কোড) ৩টা কোড (101, 110, 111) অব্যবহৃত থেকে যায়, যেগুলো নিরাপদে হ্যান্ডল করতে হবে।

State transition diagram

        c5              c5              c10
   ┌───────────►  S5  ───────────►  S10 ───────────►  DISPCH5
   │               │                  │                   │
  S0               │ c10              │ c5                 │ (input যাই হোক)
   │               ▼                  ▼                   ▼
   │             DISP  ◄──────────────┘                   S0
   │               │                                        ▲
   │  (কোনো input না থাকলে প্রতিটা state নিজের মধ্যেই থাকে) │
   └────────────────────────────────────────────────────────┘
                DISP → (input যাই হোক) → S0

State transition table

বর্তমান state	c5=1	c10=1	কোনো input না	Moore আউটপুট (dispense, change5)
S0	→ S5	→ S10	→ S0	(0, 0)
S5	→ S10	→ DISP	→ S5	(0, 0)
S10	→ DISP	→ DISPCH5	→ S10	(0, 0)
DISP	→ S0	→ S0	→ S0	(1, 0)
DISPCH5	→ S0	→ S0	→ S0	(1, 1)

একসাথে দুইটা কয়েন এলে (c5=1 আর c10=1 একই সাইকেলে) — বাস্তবে এটা এড়ানো উচিত (input debounce/serialize করে), কিন্তু ডিজাইনে একটা সুনির্দিষ্ট আচরণ থাকা দরকার। এখানে c10-কে অগ্রাধিকার দিচ্ছি — নিচের Verilog কোডে এই সিদ্ধান্তটা স্পষ্টভাবে দেখা যাবে।

DISP আর DISPCH5 — দুইটা state-ই পরের সাইকেলে, input যাই হোক না কেন, S0-এ ফিরে যায়। দুইটার Moore আউটপুট আলাদা: DISP-এ শুধু dispense=1, DISPCH5-এ dispense=1 আর change5=1 — এই যে output রেখাগুলো state-এর সাথে সরাসরি বাঁধা, input-এর সাথে নয়, এটাই Moore machine-এর সংজ্ঞা বাস্তবে প্রয়োগ হতে দেখা।

ধাপে ধাপে — Logisim / Digital

১. State register

তিনটা D flip-flop পাশাপাশি — বর্তমান state-এর ৩ বিট ধরে রাখে। প্রতিটার clock input একই সিস্টেম clock-এ যুক্ত।

২. Next-state combinational logic

উপরের transition table থেকে প্রতিটা next-state বিটের জন্য একটা Boolean expression বের করুন (চাইলে Karnaugh map ব্যবহার করে সরলীকরণ করুন — এই মডিউলেই সেই টপিক আছে)। ইনপুট: বর্তমান state (৩ বিট) + c5, c10। আউটপুট: পরবর্তী state (৩ বিট), যেটা D flip-flop-গুলোর D ইনপুটে যাবে।

অব্যবহৃত state কোড (101, 110, 111) কোনো সংজ্ঞায়িত ইনপুটে পৌঁছানোর কথা না — কিন্তু power-on-এর সময় flip-flop যেকোনো এলোমেলো মানে শুরু হতে পারে। তাই এই তিনটা কোডের জন্যও next-state লজিকে একটা “safe default” রাখুন: S0-এ ফিরে যাওয়া। এটা নিশ্চিত করে যে মেশিন কখনো একটা অনির্ধারিত অবস্থায় আটকে থাকবে না।

৩. আউটপুট লজিক

dispense = (state == DISP) OR (state == DISPCH5) — দুইটা ৩-ইনপুট AND গেট (state-এর প্রতিটা বিট নির্দিষ্ট মানে আছে কি না চেক করে) আর একটা OR দিয়ে ডিকোড করুন। change5 = (state == DISPCH5) — একইভাবে, শুধু একটা AND গেট।

ধাপে ধাপে — Verilog

৪. case সহ clocked FSM

module vending_fsm (
    input  clk,
    input  rst,
    input  c5,       // ৫ টাকার কয়েন পালস
    input  c10,       // ১০ টাকার কয়েন পালস
    output dispense,
    output change5
);
    localparam S0      = 3'b000;
    localparam S5      = 3'b001;
    localparam S10     = 3'b010;
    localparam DISP    = 3'b011;
    localparam DISPCH5 = 3'b100;

    reg [2:0] state, next_state;

    always @(*) begin
        case (state)
            S0:      next_state = c10 ? S10  : (c5 ? S5  : S0);
            S5:      next_state = c10 ? DISP : (c5 ? S10 : S5);
            S10:     next_state = c10 ? DISPCH5 : (c5 ? DISP : S10);
            DISP:    next_state = S0;
            DISPCH5: next_state = S0;
            default: next_state = S0;   // ১০১/১১০/১১১ — অব্যবহৃত কোড থেকে নিরাপদ প্রত্যাবর্তন
        endcase
    end

    always @(posedge clk or posedge rst) begin
        if (rst)
            state <= S0;
        else
            state <= next_state;
    end

    assign dispense = (state == DISP) || (state == DISPCH5);
    assign change5  = (state == DISPCH5);
endmodule

লক্ষ্য করুন — next_state কম্বিনেশনাল (always @(*)), আর state clocked (always @(posedge clk ...), <= দিয়ে non-blocking assignment)। এই দুই-always-ব্লক প্যাটার্নই HDL Verilog Intro লেসনের FSM লেখার idiom — কম্বিনেশনাল “কী হওয়া উচিত” নির্ধারণ করে, clocked ব্লক শুধু সেটা প্রতি clock edge-এ latch করে।

যাচাই — দুইটা input sequence

সিকোয়েন্স ১ — এক্স্যাক্ট পেমেন্ট, change নেই (৫ + ১০ = ১৫):

cycle	input	state (আগে) → state (পরে)	dispense	change5
১	c5=1	S0 → S5	0	0
২	c10=1	S5 → DISP	0 → 1 (পরের cycle-এ)	0
৩	—	DISP → S0	1 (এই cycle জুড়ে)	0

সিকোয়েন্স ২ — ওভারপে, change সহ (১০ + ১০ = ২০):

cycle	input	state (আগে) → state (পরে)	dispense	change5
১	c10=1	S0 → S10	0	0
২	c10=1	S10 → DISPCH5	0 → 1 (পরের cycle-এ)	0 → 1
৩	—	DISPCH5 → S0	1 (এই cycle জুড়ে)	1

দুইটা সিকোয়েন্সেই লক্ষ্য করুন — dispense/change5 state বদলানোর ঠিক পরের cycle-এ ওঠে, একই cycle-এ নয় — এটাই Moore machine-এর এক-cycle লেটেন্সির বাস্তব প্রকাশ, যেটা আগে থেকেই justify করা হয়েছিল।

Logisim-এ প্রতিটা cycle ম্যানুয়ালি ক্লক পালস দিয়ে state আর আউটপুট মিলিয়ে দেখুন। Verilog-এ একটা ছোট টেস্টবেঞ্চে c5/c10 পালস পাঠিয়ে $monitor দিয়ে state/dispense/change5-এর মান প্রতি cycle-এ প্রিন্ট করান, তারপর উপরের টেবিলের সাথে মিলিয়ে নিন।

নিজেকে চ্যালেঞ্জ করুন

1. তৃতীয় কয়েন — ২ টাকার কয়েন যোগ করুন; এতে নতুন states লাগবে (২, ৪, ৬, ৭, ৮, ৯, ১১, ১২, ১৩, ১৪ টাকা পর্যন্ত পৌঁছানো সম্ভব সংমিশ্রণ) — state count কতটা বাড়ল হিসেব করুন
2. একাধিক আইটেম মূল্য — একটা select input দিয়ে দুইটা ভিন্ন দামের আইটেমের (১৫ আর ২৫ টাকা) মধ্যে বেছে নেওয়ার সুবিধা যোগ করুন
3. Cancel বাটন — যেকোনো state থেকে S0-এ ফিরে আসার আর জমা টাকা ফেরত দেওয়ার একটা transition যোগ করুন
4. Mealy সংস্করণ বানান — একই স্পেসিফিকেশন Mealy machine হিসেবে redesign করুন, state count কমে কিনা দেখুন, আর dispense সিগন্যালের timing diagram-এ latency পার্থক্যটা চোখে দেখুন
5. State encoding পরীক্ষা — one-hot encoding (৫টা state-এর জন্য ৫টা ফ্লিপ-ফ্লপ, প্রতিটাতে ঠিক একটা 1) দিয়ে আবার বানিয়ে binary encoding-এর সাথে গেট-সংখ্যা তুলনা করুন

এটা যেখানে গিয়ে মিশবে

এখানে যা শিখলেন	পরে কোথায় লাগবে
State register + next-state combinational logic প্যাটার্ন	এই মডিউলেরই পরের প্রজেক্ট — Single-cycle CPU-এর PC register ও control logic
Moore vs Mealy trade-off (glitch বনাম latency)	Level 3 — CPU-এর fetch-decode-execute cycle, multi-cycle control unit
Clocked always block-এর দুই-ব্লক idiom	Level 3 (Assembly module)-এ compiler-generated state machine পড়া
State transition table থেকে circuit design	Level 5 — Compiler-এর lexer (regex → NFA → DFA → token)
Saturating-counter state machine ধারণা	Level 11 — Advanced Architecture-এর branch predictor (2-bit FSM)
অব্যবহৃত-state safe-default হ্যান্ডলিং	Level 4 — OS process lifecycle (new/ready/running/blocked)-এর মতো state machine-এ ভ্যালিড transition guard