Finite State Machine — Sequential Logic-এর আনুষ্ঠানিক কাঠামো
Finite State Machines
প্রতিটা sequential circuit আসলে একটা FSM — বর্তমান state (register-এ রাখা) আর input মিলে next state ও output গণনা করে, ঠিক clock-এর নিয়ম মেনে; এই একই কাঠামো একটা সাধারণ counter থেকে CPU-র control unit পর্যন্ত সবখানে ফিরে আসে।
আগে এটা বুঝি
আগের দুই লেসনে আমরা দুইটা টুকরো পেয়েছি: register (clock-এ সিঙ্ক্রোনাইজড, একটা মান ধরে রাখতে পারে) আর clock timing-এর বাস্তবতা (propagation delay, setup/hold, আর সেই বাস্তবতা থেকে বেরিয়ে আসা max frequency-র সীমা)।
এই দুইটা টুকরো একসাথে বসালেই একটা সাধারণ, শক্তিশালী কাঠামো বেরিয়ে আসে — state (register-এ রাখা) + input → next state (combinational logic দিয়ে গণনা করা), ঠিক clock-এর নিয়ম মেনে। এটাই finite state machine (FSM) — প্রতিটা sequential circuit-এর আনুষ্ঠানিক কাঠামো, একটা সাধারণ counter থেকে শুরু করে পুরো CPU-র control unit পর্যন্ত সবকিছুর ভিত্তি।
মূল ধারণা
FSM-এর তিনটা অংশ
┌─────────────────────┐
input ────►│ │
│ Next-State Logic ├──► next state
│ (combinational) │ │
current ──►│ │ │
state └─────────────────────┘ │
▲ │
│ ┌──────────────┐ │
└─────────┤State Register│◄──────────────┘
│ (flip-flops) │
└───────┬──────┘
│
┌──────────┴──────────┐
current ──►│ Output Logic ├──► output
state │ (combinational) │
└─────────────────────┘তিনটা অংশ: State register (flip-flop-এর গুচ্ছ, বর্তমান state ধরে রাখে), next-state logic (বর্তমান state + input থেকে পরের state গণনা করে — pure combinational, যা লেসন ১-১১-এর সবকিছু দিয়ে বানানো যায়), আর output logic (state থেকে output গণনা করে)।
Moore বনাম Mealy — output কোথা থেকে আসে
Moore machine: output = f(state) — শুধু বর্তমান state-এর উপর নির্ভর করে, input-এর উপর না।
Mealy machine: output = f(state, input) — বর্তমান state এবং বর্তমান input দুটোর উপর নির্ভর করে।
| Moore | Mealy | |
|---|---|---|
| Output নির্ভর করে | শুধু state | state + input |
| প্রতিক্রিয়া | এক clock cycle দেরি (input বদলে output সাথে সাথে বদলায় না) | তাৎক্ষণিক (input বদলে output সাথে সাথে বদলাতে পারে) |
| Glitch-প্রবণতা | কম (output শুধু clock edge-এ বদলায়) | বেশি (output combinational input পরিবর্তনে সরাসরি সাড়া দেয়, মাঝপথে glitch হতে পারে) |
| State সংখ্যা | প্রায়ই বেশি লাগে | প্রায়ই কম লাগে |
এটা একটা বাস্তব প্রকৌশল trade-off — দ্রুত প্রতিক্রিয়া চাইলে Mealy, স্থিতিশীল/glitch-মুক্ত output চাইলে Moore।
উদাহরণ
সম্পূর্ণ ডিজাইন — “101” Sequence Detector
লক্ষ্য: একটা serial bit stream-এ প্রতিবার বিট প্যাটার্ন 101
(overlapping match সহ) দেখা গেলে output 1 দিতে হবে। Moore মডেল
বেছে নিচ্ছি (স্থিতিশীল output-এর জন্য)।
ধাপ ১ — State diagram। চারটা state: S0 (শুরু/কোনো progress
নেই), S1 (1 দেখেছি), S2 (10 দেখেছি), S3 (101 সম্পূর্ণ
— output=1, কিন্তু overlapping match-এর জন্য পরের বিট 01
হিসেবে গণ্য করা continues)।
0 1 0
┌─┐ ┌─┐ ┌─┐
▼ │ ▼ │ ▼ │
┌──►S0 ├──1──►S1 ├──0──►S2 ├──1──►S3
│ │ │
└──────────────0───────────────┘ │
1
S2◄──────────────┘ধাপ ২ — State transition table।
| বর্তমান state | Input=0 | Input=1 | Output |
|---|---|---|---|
| S0 | S0 | S1 | 0 |
| S1 | S2 | S1 | 0 |
| S2 | S0 | S3 | 0 |
| S3 | S2 | S1 | 1 |
(S3-তে input=1 এলে S1-এ যাওয়া কেন? কারণ সদ্য দেখা bit stream
...101|1 — শেষ bit 1 একটা নতুন সম্ভাব্য match-এর শুরু হতে পারে,
তাই S1-এ যাওয়া সঠিক, S0-এ না — এটাই “overlapping match” সঠিকভাবে
ধরার কৌশল।)
ধাপ ৩ — State encoding। 4টা state, তাই 2-bit binary encoding
যথেষ্ট: S0=00, S1=01, S2=10, S3=11।
ধাপ ৪ — Next-state logic ডেরাইভ (K-map, লেসন ৪-এর সরাসরি প্রয়োগ)।
State bit Q1Q0, input X, next state D1D0 — প্রতিটা bit-এর
জন্য আলাদা K-map বানিয়ে (৩ variable: Q1, Q0, X) minimized
expression বের করা হয়। এই ধাপটাই পুরো ডিজাইনকে “হাতে-আঁকা diagram”
থেকে “প্রকৃত গেট-লেভেল circuit”-এ রূপান্তর করে — ঠিক লেসন ৪-এর
পদ্ধতি, শুধু এবার ৩ variable-এর টেবিলে।
ধাপ ৫ — Output logic। Moore মডেলে output শুধু state-এর ফাংশন:
Output = 1 যদি এবং শুধু যদি Q1Q0 = 11 (state S3) — একটা সরল
2-input AND gate (Q1 AND Q0)।
পুরো circuit: 2টা D flip-flop (state register) + next-state combinational logic (K-map থেকে derived) + output combinational logic (একটা AND gate) — এটাই সম্পূর্ণ FSM, উপরের canonical block diagram-এর ঠিক বাস্তবায়ন।
ভেতরে কী ঘটছে
State Encoding — Binary বনাম One-Hot
উপরের উদাহরণে আমরা binary encoding ব্যবহার করেছি (4 state, 2
bit)। বিকল্প: one-hot encoding — প্রতিটা state-এর জন্য একটা
আলাদা flip-flop, ঠিক একটা সবসময় 1 (বাকিগুলো 0)।
4 state-এ one-hot লাগবে 4টা flip-flop (binary-তে মাত্র 2টা)
— বেশি flip-flop। কিন্তু next-state logic সরল হয়: প্রতিটা
state-এর “সক্রিয়” bit সরাসরি সেই state-এ পৌঁছানোর শর্ত বহন করে,
জটিল multi-bit K-map লাগে না।
| Binary encoding | One-hot encoding | |
|---|---|---|
| Flip-flop সংখ্যা | ⌈log₂ N⌉ | N |
| Next-state logic | জটিল (K-map, একাধিক variable) | সরল (প্রতি state একটা সরল term) |
| গতি | তুলনামূলক ধীর (জটিল combinational path) | দ্রুত (সরল, ছোট combinational path) |
| সাধারণ ব্যবহার | Area-সীমিত ASIC | FPGA (যেখানে flip-flop প্রচুর, কিন্তু routing/logic সীমিত সম্পদ) |
এটা lesson 8 (ALU)-তে দেখা “ripple বনাম parallel” আর lesson 5-এর “ripple-carry বনাম carry-lookahead”-এর একই পরিচিত প্যাটার্নের আরেকটা রূপ: বেশি hardware খরচ করে দ্রুত/সরল logic কেনা, একটা বারবার ফিরে আসা hardware ডিজাইন নীতি।
নিজে চালিয়ে দেখুন
Logisim-এ Sequence Detector চালান
১. দুইটা D flip-flop দিয়ে state register বানান (Q1Q0)
২. K-map থেকে derived next-state logic gate দিয়ে বানান (input:
Q1, Q0, X; output: D1, D0)
৩. Output logic: AND(Q1, Q0)
৪. Test sequence চালান: 1 0 1 1 0 1 — প্রত্যাশিত output প্রতিটা
bit-এর পর: 0 0 1 0 0 1 (প্রথম 101 bit ৩-এ ধরা পড়ে, দ্বিতীয়
overlapping match 101 (positions ৪-৬, 1 1 0 1-এর শেষ তিনটা
অবস্থানে না — নিজে হাতে ট্রেস করে verify করুন)
৫. প্রতিটা clock edge-এ state আর output রেকর্ড করুন, উপরের transition
table-এর সাথে মেলান
উপরের K-map-derived next-state logic সত্যিই একটা overlapping '101' pattern সঠিকভাবে ধরে — একটা দীর্ঘ test sequence চালিয়ে verify করা যায়।
নিজে বানান
নিজের FSM — Traffic Light Controller
- একটা সরল traffic light FSM ডিজাইন করুন: Red → Green → Yellow → Red, প্রতিটা state একটা নির্দিষ্ট সংখ্যক clock cycle স্থায়ী হয়
- State diagram আঁকুন — timer count state-এর অংশ হিসেবে অন্তর্ভুক্ত করুন (যেমন Green_1, Green_2, Green_3 যদি Green ৩ cycle স্থায়ী হয়)
- State transition table বানান
- Moore মডেল ব্যবহার করুন (ন্যায্য কারণ দিন কেন — ইঙ্গিত: physical light-এর output glitch-free হওয়া কতটা গুরুত্বপূর্ণ)
- Logisim-এ বাস্তবায়ন করে verify করুন output ঠিক প্রত্যাশিত cycle-এ বদলাচ্ছে
Traffic light FSM একটা চমৎকার উদাহরণ কারণ এটা দেখায় “state” সবসময় শুধু ইতিহাসের সারাংশ না — এখানে state সময় (কতক্ষণ একটা phase-এ আছি) এনকোড করছে, যা counter (পরের লেসনের বিষয়) আর FSM-এর মধ্যে সরাসরি সংযোগ তৈরি করে।
বাস্তব সিস্টেমে
FSM যেখানে সর্বত্র
-
CPU control unit — লেসন ১৫-এ দেখবেন একটা multi-cycle CPU-র control unit ঠিক এই কাঠামোর একটা FSM — state = “কোন instruction cycle-এ আছি” (fetch, decode, execute…), output = control signal।
-
Communication protocol — TCP-র connection state (LISTEN, SYN_SENT, ESTABLISHED, FIN_WAIT…) একটা classic FSM, Level 7-এ (Networking) বিস্তারিত দেখবেন।
-
Regex engine — Level 13-এ (CS Theory) দেখবেন একটা regular expression একটা DFA (deterministic finite automaton)-এ compile হয় — গাণিতিকভাবে এই লেসনের FSM-এর সাথে হুবহু সমতুল্য কাঠামো, ভিন্ন প্রসঙ্গে।
-
Elevator controller, vending machine — এই মডিউলের নিজস্ব “FSM Vending Machine” প্রজেক্ট ঠিক এই লেসনের পদ্ধতি অনুসরণ করে।
-
USB/HDMI protocol negotiation — hardware-স্তরের protocol handshake প্রায়ই একটা ছোট FSM দিয়ে বাস্তবায়িত হয় চিপে সরাসরি।
-
Video game character state — (Idle, Walking, Jumping, Attacking) — সফটওয়্যার-স্তরের FSM, একই ধারণা, হার্ডওয়্যার ছাড়াই।
যে ভুলগুলো সবাই করে
“Mealy machine সবসময় Moore-এর চেয়ে ভালো, কারণ কম state লাগে ও দ্রুত সাড়া দেয়।”
Mealy-র output input-এর সাথে সরাসরি combinational পথে যুক্ত — মানে input-এ যেকোনো glitch (transient, ভুল মান যা propagation delay-এর কারণে সাময়িকভাবে দেখা দেয়) সরাসরি output-এ প্রতিফলিত হতে পারে, এমনকি সেই glitch “আসল” মান না হলেও। Moore-এ output শুধু registered state থেকে আসে (flip-flop-এর মাধ্যমে filtered), তাই স্বভাবতই glitch-মুক্ত। Physical output (যেমন traffic light, motor control) নিয়ন্ত্রণে এই স্থিতিশীলতা প্রায়ই দ্রুত প্রতিক্রিয়ার চেয়ে বেশি গুরুত্বপূর্ণ — তাই choice প্রসঙ্গ-নির্ভর, “সবসময় ভালো” বলে কিছু নেই।
“একটা FSM-এর state সংখ্যা যত কম, ডিজাইন তত ভালো।”
কম state মানে কম flip-flop, কিন্তু প্রায়ই জটিলতর next-state logic (hood section-এর binary বনাম one-hot আলোচনার সরাসরি প্রতিফলন)। “ভালো” ডিজাইনের সংজ্ঞা প্রসঙ্গ-নির্ভর — একটা এলাকা-সীমিত ASIC-এ কম state/flip-flop অগ্রাধিকার পেতে পারে, একটা speed-সীমিত FPGA ডিজাইনে বেশি state (one-hot) কিন্তু সরল, দ্রুত logic অগ্রাধিকার পেতে পারে।
বুঝেছেন কি না দেখুন
1101 sequence detector-এ, বর্তমান state S2, input আসে 1।
Transition table অনুযায়ী পরের state কী, আর output কী হবে?
প্রয়োগ
101 sequence detector-এ, বর্তমান state S2, input আসে 1।
Transition table অনুযায়ী পরের state কী, আর output কী হবে?Transition table থেকে: state S2, input 1 → next state S3।
Output (Moore, শুধু state-এর ফাংশন): S3-তে output 1।
তবে গুরুত্বপূর্ণ সতর্কতা: এই output 1 তখনই প্রকাশ পাবে যখন
FSM পৌঁছাবে S3-এ, অর্থাৎ পরের clock edge-এর পরে — ঠিক এই
মুহূর্তে (input দেওয়ার সময়) output এখনও বর্তমান state (S2)-এর
ফাংশন, যা 0। এটাই Moore machine-এর “এক cycle দেরি” বৈশিষ্ট্য
যা concept section-এর তুলনা টেবিলে উল্লেখ করা হয়েছিল।
2কেন 101 sequence detector-এর state diagram-এ S3 (match found)
থেকে input=1-এ S1-এ যায়, S0-তে না? আপনার নিজের ভাষায় ব্যাখ্যা
করুন কেন এটাই “সঠিক” আচরণ।
যুক্তি
101 sequence detector-এর state diagram-এ S3 (match found)
থেকে input=1-এ S1-এ যায়, S0-তে না? আপনার নিজের ভাষায় ব্যাখ্যা
করুন কেন এটাই “সঠিক” আচরণ।সমস্যার সংজ্ঞা অনুযায়ী matches overlap করতে পারে — যেমন bit
stream 10101-এ 101 দুইবার ম্যাচ করে (position ১-৩, আর position
৩-৫, শেষ 1 দুইবার ব্যবহৃত হচ্ছে)।
S3-এ পৌঁছানো মানে সদ্য 101 দেখেছি। এরপর যদি input 1 আসে,
সাম্প্রতিকতম bit history হলো ...1 (শুধু শেষ bit-টাই এখন প্রাসঙ্গিক,
কারণ পরের match-এর জন্য নতুন করে “progress” গোনা শুরু হচ্ছে)। যেহেতু
1 দেখেছি, এটা একটা নতুন সম্ভাব্য match-এর প্রথম bit — ঠিক S1-এর
সংজ্ঞা (“1 দেখেছি, progress আছে”)।
যদি ভুলবশত S0-তে (কোনো progress নেই) যেতাম, তাহলে overlapping
match miss হয়ে যেত — যেমন 10101-এ দ্বিতীয় 101 (position ৩-৫)
ধরা পড়ত না, কারণ আমরা ভুলভাবে “progress ভুলে গিয়ে” শুরু থেকে শুরু
করতাম। এই সূক্ষ্মতাই FSM ডিজাইনে সবচেয়ে সাধারণ ভুলের একটা উৎস —
state transition ডিজাইন করার সময় সবসময় “সদ্য দেখা suffix”-টা
পরের সম্ভাব্য match-এর জন্য কতটা প্রাসঙ্গিক তা সাবধানে ভাবতে হয়।
3আপনি একটা FSM ডিজাইন করছেন ৭টা state নিয়ে একটা high-speed FPGA
ডিজাইনে, যেখানে timing (clock frequency) সবচেয়ে গুরুত্বপূর্ণ
বিবেচ্য বিষয়, flip-flop সংখ্যা না। Binary না one-hot এনকোডিং
বাছবেন, আর কেন?
ডিজাইন
One-hot এনকোডিং বেছে নেওয়া উচিত।
৭টা state binary-তে মাত্র 3 bit লাগবে (⌈log₂7⌉=3), one-hot-এ
7টা flip-flop — চার গুণেরও বেশি flip-flop। কিন্তু প্রশ্নে স্পষ্ট
বলা আছে flip-flop সংখ্যা এখানে সীমাবদ্ধতা না — FPGA-তে সাধারণত
প্রচুর flip-flop উপলব্ধ থাকে (প্রতিটা logic cell-এর সাথেই একটা করে
আসে), কিন্তু combinational logic path length সরাসরি max clock
frequency নির্ধারণ করে (clock ও timing লেসনের সূত্র:
T_clock ≥ T_prop + T_setup)।
One-hot-এ next-state logic প্রতিটা bit-এর জন্য সরল (প্রায়ই একটা মাত্র AND-এর সমতুল্য শর্ত), তাই combinational path ছোট, propagation delay কম, max frequency বেশি। Binary encoding-এ 3-bit-এর জটিল K-map-derived logic দীর্ঘতর combinational path তৈরি করতে পারে।
সংক্ষেপে: যখন flip-flop “সস্তা” (FPGA-তে প্রচুর) কিন্তু speed মূল্যবান, one-hot জেতে — hardware resource trade-off-টা platform-এর প্রকৃতির উপর নির্ভরশীল, একটা universal “সঠিক উত্তর” নেই।
4Traffic light FSM (BuildIt-এর উদাহরণ)-এ, যদি একটা “pedestrian
button” input যোগ করা হয় যা Green phase-কে সময়ের আগেই শেষ করে
দিতে পারে, এটা কি এখনও একটা বিশুদ্ধ Moore machine থাকবে?
যুক্তি
Machine নিজে এখনও Moore থাকতে পারে, যদি ডিজাইন করা হয় সঠিকভাবে — কিন্তু এটা সতর্কতার সাথে ভাবতে হবে।
Pedestrian button একটা input, আর output (traffic light color) যদি এখনও শুধুমাত্র state-এর ফাংশন থাকে (button নিজে সরাসরি output প্রভাবিত না করে, শুধু next-state নির্ধারণে ভূমিকা রাখে — অর্থাৎ button চাপলে FSM একটা ভিন্ন state-এ যায়, আর সেই নতুন state-এর output color স্বাভাবিক নিয়মে নির্ধারিত হয়), তাহলে এটা এখনও বিশুদ্ধ Moore।
কিন্তু যদি ভুলভাবে ডিজাইন করা হয় (button সরাসরি output logic-এ ঢুকিয়ে দেওয়া, “state Green-এ থেকেও button চাপলে সরাসরি output yellow দেখাও” ধরনের logic), তাহলে সেটা Mealy হয়ে যাবে (output input-নির্ভর হয়ে পড়েছে)।
সাধারণ নীতি: input যতই জটিল/অনেক থাক না কেন, machine Moore থাকে যতক্ষণ input-এর প্রভাব শুধু next-state transition-এর মধ্য দিয়ে output-এ পৌঁছায়, output logic-এ input সরাসরি প্রবেশ না করে। এই পার্থক্যটাই একটা FSM-কে Moore বা Mealy হিসেবে classify করার প্রকৃত, precise মানদণ্ড — input কতটা “জটিল” তার উপর না।
এরপর কী
FSM-এর আনুষ্ঠানিক কাঠামো এখন আমাদের হাতে — state register + next-state logic + output logic। পরের লেসনে আমরা দেখব এই কাঠামোর সবচেয়ে সরল, সবচেয়ে ব্যবহারিক প্রয়োগ: counter — যেখানে state নিজেই একটা সংখ্যা, আর transition সবসময় “+1 mod N” (সরাসরি Level 0-এর modular arithmetic-এর হার্ডওয়্যার রূপ)। সেখান থেকে shift register পর্যন্ত — যেখানে state bit-গুলো একে অপরের মধ্যে “সরে” যায়, serial আর parallel ডেটার মধ্যে রূপান্তরের ভিত্তি।
আরও পড়ুন
- Digital Design and Computer Architecture, Ch. 3.4 — Finite State Machines — Sarah Harris, David Harris · Moore/Mealy design flow-এর প্রামাণ্য উপস্থাপনা
- Introduction to the Theory of Computation, Ch. 1 — Finite Automata — Michael Sipser · FSM-এর তাত্ত্বিক ভিত্তি — Level 13-তে (CS Theory) এই একই ধারণা আরও গভীরভাবে ফিরে আসবে