ফাইনাইট স্টেট মেশিন (FSM) — Moore ও Mealy

Finite state machines — Moore & Mealy

৯ মিনিট পড়া মধ্যম · Intermediate Python কোডসহ সম্পূর্ণ বাংলায়

এক নজরে · TL;DR

ফাইনাইট স্টেট মেশিনFinite State Machine (FSM)একটি ফিক্সড, সসীম সংখ্যক অবস্থা (state), সেই অবস্থাগুলোর মধ্যে ইনপুট দ্বারা চালিত ট্রানজিশন, এবং আউটপুট — যেকোনো সিকোয়েনশিয়াল সার্কিটের সাধারণ গাণিতিক মডেল। হলো M3-এর ল্যাচ, ফ্লিপ-ফ্লপ, রেজিস্টার ও কাউন্টার — এই সবগুলোকেই যে একটি সাধারণ কাঠামোর নির্দিষ্ট উদাহরণ হিসেবে বর্ণনা করা যায়, তার সেই কাঠামো।
Moore মেশিনে আউটপুট শুধু বর্তমান স্টেটের উপর নির্ভর করে; Mealy মেশিনে আউটপুট বর্তমান স্টেট ও বর্তমান ইনপুট — দুটোর উপর নির্ভর করে।
একটি ধ্রুপদী উদাহরণ — বিট-স্ট্রিমে ঠিক "101" প্যাটার্ন খুঁজে বের করা একটি Moore FSM দিয়ে — এই পাঠে ডিজাইন করা হবে ও কোডে চালিয়ে যাচাই করা হবে।
CPU-এর কন্ট্রোল ইউনিট (M6/L29) মূলত একটি FSM — fetch → decode → execute স্টেটের মধ্য দিয়ে চলে — এই পাঠের কাঠামোই সেখানে সরাসরি প্রয়োগ হবে।

এই পাঠে যা শিখবেন

FSM-এর তিনটি মূল উপাদান — স্টেট, ট্রানজিশন, আউটপুট — এবং কীভাবে M3-এর প্রতিটি সার্কিট আসলে একটি FSM
Moore মেশিন বনাম Mealy মেশিন — আউটপুট কীসের উপর নির্ভর করে, তার পার্থক্য ও প্রতিটির trade-off
একটি "101" সিকোয়েন্স ডিটেক্টর Moore FSM ধাপে ধাপে ডিজাইন করা — স্টেট, ট্রানজিশন টেবিল, আউটপুট টেবিল
Python দিয়ে সেই FSM বাস্তবায়ন করে একটি real বিট-স্ট্রিমের উপর চালিয়ে ফলাফল হাতে-যাচাই করা

১ · FSM কী — M3-এর সবকিছুর অভিন্ন কাঠামো

এখন পর্যন্ত M3-এ আমরা দেখেছি ল্যাচL13 — সবচেয়ে সরল মেমরি এলিমেন্ট, লেভেল-ট্রিগারড।, ফ্লিপ-ফ্লপL14 — এজ-ট্রিগারড মেমরি এলিমেন্ট।, রেজিস্টারL15 — একাধিক ফ্লিপ-ফ্লপ মিলিয়ে একটি N-বিট মান সংরক্ষণ। ও কাউন্টারL16 — একটি নির্দিষ্ট সিকোয়েন্সে স্টেট পরিবর্তনকারী সার্কিট। — প্রতিটিই আলাদা সার্কিট মনে হলেও, তাদের সবার পেছনে একটিই সাধারণ গাণিতিক মডেল কাজ করে — ফাইনাইট স্টেট মেশিনFinite State Machine (FSM)একটি ফিক্সড, সসীম সংখ্যক স্টেট, ইনপুট দ্বারা চালিত ট্রানজিশন, এবং প্রতিটি স্টেট/ট্রানজিশনের সাথে যুক্ত আউটপুট — নিয়ে গঠিত আনুষ্ঠানিক মডেল।।

একটি FSM-এর তিনটি অংশ থাকে —

স্টেট (State): একটি ফিক্সড, সসীম সংখ্যক সম্ভাব্য "অবস্থা" — সিস্টেম যেকোনো মুহূর্তে ঠিক একটি স্টেটে থাকে।
ট্রানজিশন (Transition): কোন ইনপুট পেলে বর্তমান স্টেট থেকে কোন নতুন স্টেটে যাওয়া হবে, তার নিয়ম।
আউটপুট (Output): স্টেট এবং/অথবা ইনপুট থেকে উৎপন্ন ফলাফল সিগন্যাল।

উদাহরণস্বরূপ, L16-এর একটি ৩-বিট বাইনারি কাউন্টার আসলে একটি FSM যার ৮টি সম্ভাব্য স্টেট (0 থেকে 7), আর ট্রানজিশন নিয়ম হলো "প্রতি ক্লক টিকে স্টেট নাম্বার ১ বাড়াও, 7 থেকে 0-এ wrap করো" — এই একটিমাত্র বাক্যেই পুরো কাউন্টারের আচরণ বর্ণনা করা যায়। FSM-এর ভাষায় ভাবাটাই এই পাঠের মূল লক্ষ্য, কারণ M6-এর CPU কন্ট্রোল ইউনিট (L29) ঠিক এই একই কাঠামোতে ডিজাইন হবে।

মূল অন্তর্দৃষ্টি

SR ল্যাচ, D ফ্লিপ-ফ্লপ, শিফট রেজিস্টার, বাইনারি কাউন্টার — এরা "আলাদা আলাদা জিনিস" নয়, বরং সবাই একই তত্ত্বের (FSM) ভিন্ন ভিন্ন, ছোট-পরিসরের বাস্তবায়ন। FSM হলো সেই তত্ত্ব যা তাদের সবাইকে একটি অভিন্ন ভাষায় বর্ণনা করার ক্ষমতা দেয়।

২ · Moore মেশিন বনাম Mealy মেশিন

FSM-এর দুটি প্রধান ভ্যারিয়েন্ট আছে — পার্থক্য শুধু আউটপুট ঠিক কীসের উপর নির্ভর করে, তাতে।

Moore মেশিন
আউটপুট শুধুমাত্র বর্তমান স্টেটের উপর নির্ভর করে — ইনপুটের উপর সরাসরি নির্ভর করে না। আউটপুট যেন স্টেটের সাথে "সেঁটে" আছে।

Mealy মেশিন
আউটপুট বর্তমান স্টেট ও বর্তমান ইনপুট — দুটোর উপরেই নির্ভর করে। আউটপুট যেন ট্রানজিশনের সাথে "সেঁটে" আছে।

Mealy মেশিন একই ক্লক সাইকেলের মধ্যেই ইনপুট পরিবর্তনে দ্রুত সাড়া দিতে পারে (স্টেট পরিবর্তনের জন্য অপেক্ষা না করেই), কিন্তু এই দ্রুততার একটি বাস্তব মূল্য আছে — Mealy আউটপুট টাইমিং হ্যাজার্ডের প্রতি বেশি সংবেদনশীল, কারণ ইনপুটে সামান্য পরিবর্তনেও আউটপুট মুহূর্তেই বদলে যেতে পারে, যা সিঙ্ক্রোনাইজেশন জটিল করে তোলে। এই পাঠের বাকি অংশে আমরা তুলনামূলক সরল Moore মেশিন দিয়ে একটি বাস্তব উদাহরণ তৈরি করব।

৩ · উদাহরণ — "101" সিকোয়েন্স ডিটেক্টর (Moore FSM)

লক্ষ্য: একটি বিট-স্ট্রিম একবারে একটি বিট করে আসছে — যেই মুহূর্তে সাম্প্রতিক তিনটি বিট ঠিক "101" হয়ে যায়, আউটপুট ১ হয়ে যাবে (বাকি সময় ০)। এর জন্য ৪টি স্টেট যথেষ্ট —

S0: এখনো কিছুই মেলেনি (বা মিল ভেঙে গেছে)।
S1: সর্বশেষ একটি "1" দেখা গেছে — সম্ভাব্য মিলের শুরু।
S2: সর্বশেষ "10" দেখা গেছে।
S3 (Match): সর্বশেষ "101" দেখা গেছে — আউটপুট = ১।

ট্রানজিশন ডিজাইন করার সময় সবচেয়ে সূক্ষ্ম অংশ হলো "ভুল" বিট এলে ঠিক কোথায় ফিরে যেতে হবে তা নির্ধারণ করা — একদম S0-এ ফেরত না গিয়ে, নতুন সম্ভাব্য মিলের শুরু কিনা তা পরীক্ষা করতে হয় (overlapping match সম্ভব)। যেমন S2 (দেখেছে "10") থেকে যদি আরেকটি "1" আসে, ফলাফল "101" — তাই S3-এ যাওয়া ঠিক; কিন্তু S3 (দেখেছে "101") থেকে যদি আরেকটি "1" আসে, সর্বশেষ তিন বিট হয়ে যায় "011" — যা কোনো মিল না হলেও তার শেষ বিট "1" একটি নতুন সম্ভাব্য মিলের শুরু, তাই S0 নয়, S1-এ যেতে হবে।

সবুজ তীর মূল "মিলের দিকে এগোনো" পথ দেখায়; ধূসর তীরগুলো "ভুল বিট" এলে কোথায় ফিরতে হয় তা দেখায় — খেয়াল করুন S3 থেকে সরাসরি S0-এ ফেরা হয় না।

সম্পূর্ণ ট্রানজিশন টেবিল —

S0
ইনপুট ০ → S0 (থাকে)
ইনপুট ১ → S1

S1
ইনপুট ০ → S2
ইনপুট ১ → S1 (থাকে)

S2
ইনপুট ০ → S0
ইনপুট ১ → S3 (match)

S3
ইনপুট ০ → S2
ইনপুট ১ → S1

যেহেতু এটি একটি Moore মেশিন, আউটপুট টেবিল আলাদা এবং শুধু স্টেটের উপর নির্ভরশীল — S0, S1, S2 → আউটপুট ০; S3 → আউটপুট ১। এখন নিচের কোড সেলে এই একই ট্রানজিশন ও আউটপুট টেবিল সরাসরি ডেটা স্ট্রাকচার হিসেবে বসিয়ে, একটি প্রকৃত বিট-স্ট্রিমের উপর চালিয়ে দেখা যাক।

Python

# Moore FSM -- "101" সিকোয়েন্স ডিটেক্টর -- শুধুমাত্র সিমুলেটেড স্টেট ট্রানজিশন, কোনো বাস্তব হার্ডওয়্যার অ্যাক্সেস নয়

# ট্রানজিশন টেবিল: {(বর্তমান স্টেট, ইনপুট বিট): পরবর্তী স্টেট}
transitions = {
    ("S0", 0): "S0", ("S0", 1): "S1",
    ("S1", 0): "S2", ("S1", 1): "S1",
    ("S2", 0): "S0", ("S2", 1): "S3",
    ("S3", 0): "S2", ("S3", 1): "S1",
}

# আউটপুট টেবিল (Moore -- শুধু স্টেটের ফাংশন): {স্টেট: আউটপুট}
outputs = {"S0": 0, "S1": 0, "S2": 0, "S3": 1}

def run_fsm(bitstream, start_state="S0"):
    """বিট-স্ট্রিমের উপর FSM চালিয়ে প্রতিটি বিটের পরের স্টেট ও আউটপুট রিটার্ন করে"""
    state = start_state
    state_path = [state]
    output_seq = []
    for bit in bitstream:
        state = transitions[(state, bit)]
        state_path.append(state)
        output_seq.append(outputs[state])
    return state_path, output_seq

bitstream = [1, 0, 1, 0, 1]
state_path, output_seq = run_fsm(bitstream)

print("ইনপুট বিট-স্ট্রিম:  ", bitstream)
print("স্টেট পাথ:         ", state_path)
print("আউটপুট সিকোয়েন্স:  ", output_seq)
print()
match_positions = [i + 1 for i, o in enumerate(output_seq) if o == 1]
print(f"'101' ম্যাচ পাওয়া গেছে {len(match_positions)} বার, বিট-পজিশন {match_positions}-এ (১-ইনডেক্সড)")

হাতে-যাচাই: ইনপুট [1,0,1,0,1]-এ S0→S1(bit1=1)→S2(bit2=0)→S3(bit3=1, প্রথম ম্যাচ, পজিশন ৩)→S2(bit4=0)→S3(bit5=1, দ্বিতীয় ম্যাচ, পজিশন ৫)। দুটো ম্যাচ ওভারল্যাপ করে — বিট ৩ উভয় ম্যাচেই ব্যবহৃত হয়েছে (পজিশন ১-৩ এবং পজিশন ৩-৫ উভয়ই "101") — এটাই প্রমাণ করে কেন S3 থেকে S0-এ সরাসরি না ফিরে S1/S2-তে ফেরা জরুরি ছিল।

বাস্তব প্রাসঙ্গিকতা · CPU কন্ট্রোল ইউনিট

একটি CPU-এর কন্ট্রোল ইউনিট (M6/L29-এ বিস্তারিত) মূলত একটি FSM — যার স্টেটগুলো হলো fetch, decode, execute (এবং প্রয়োজনে memory-access, write-back) — প্রতিটি ক্লক সাইকেলে এক স্টেট থেকে পরের স্টেটে যায়, ঠিক যেমন এই সিকোয়েন্স ডিটেক্টর প্রতিটি বিটে এক স্টেট থেকে পরের স্টেটে গিয়েছিল। এই পাঠের ট্রানজিশন-টেবিল কাঠামোটাই সেখানে সরাসরি প্রয়োগ হবে, শুধু "ইনপুট বিট"-এর জায়গায় "ইনস্ট্রাকশনের অপকোড" বসবে।

ভাবনার প্রশ্ন

প্রতিটি প্রশ্ন নিজে কিছুক্ষণ ভাবুন — তারপর "→ উত্তর" চাপুন।

প্র ০১ L16-এর বাইনারি কাউন্টার কীভাবে একটি FSM-এর নির্দিষ্ট উদাহরণ, তা নিজের ভাষায় ব্যাখ্যা করুন — এর স্টেট, ট্রানজিশন ও আউটপুট কী কী?

একটি N-বিট বাইনারি কাউন্টারের স্টেটগুলো হলো ০ থেকে 2^N - 1 পর্যন্ত সম্ভাব্য গণনার মান (মোট 2^N টি স্টেট)। ট্রানজিশন নিয়ম অত্যন্ত সরল ও প্রতিটি স্টেটে একইরকম — "ইনপুট" ধরা হয় ক্লক-টিক নিজেই, এবং প্রতি টিকে বর্তমান স্টেট থেকে (মান+1) mod 2^N স্টেটে যাওয়া হয়। আউটপুট সাধারণত স্টেট মানটাই সরাসরি — অর্থাৎ এটি একটি Moore মেশিন, কারণ আউটপুট (গণনার মান) শুধু বর্তমান স্টেটের উপর নির্ভরশীল, কোনো আলাদা ইনপুটের উপর নয়।

প্র ০২ একই "101" সিকোয়েন্স ডিটেক্টর যদি Mealy স্টাইলে ডিজাইন করা হতো, তাহলে ঠিক কী পরিবর্তন হতো?

Mealy সংস্করণে আউটপুট টেবিলটা আর আলাদাভাবে {স্টেট: আউটপুট} আকারে থাকত না — বরং প্রতিটি ট্রানজিশনের সাথেই একটি আউটপুট যুক্ত থাকত, অর্থাৎ {(স্টেট, ইনপুট): (পরবর্তী স্টেট, আউটপুট)}। কার্যকরীভাবে, S2 থেকে ইনপুট ১ পেলে "S3-এ যাওয়া" এবং "আউটপুট=১" — এই দুটো একসাথে সেই একই ট্রানজিশনেই ঘটত (একটি আলাদা S3 স্টেটে গিয়ে তারপর আউটপুট বের করার বদলে), ফলে ম্যাচ ডিটেকশন এক ক্লক সাইকেল আগে ঘটতে পারত — কিন্তু বিনিময়ে ৪টির বদলে হয়তো স্টেট সংখ্যা একই থাকলেও আউটপুট লজিক ট্রানজিশনের সাথে আরও জটিলভাবে জড়িয়ে যেত।

প্র ০৩ উপরের কোড সেলে S3 থেকে ইনপুট ১ এলে কেন সরাসরি S0-এ না গিয়ে S1-এ যাওয়া হয়?

S3-এ পৌঁছানো মানে সর্বশেষ তিন বিট ছিল "101"। এরপর যদি আরেকটি "1" আসে, সর্বশেষ তিন বিট হয়ে যায় "011" — এটি কোনো মিল নয় ঠিকই, কিন্তু এর একদম শেষ বিটটাই "1", যা একটি সম্পূর্ণ নতুন সম্ভাব্য "101" মিলের প্রথম বিট হতে পারে। তাই এই তথ্য (যে একটি "1" সদ্য দেখা গেছে) হারিয়ে ফেলে সরাসরি S0 (কিছুই মেলেনি)-এ ফেরত গেলে ভবিষ্যতের একটি বৈধ ওভারল্যাপিং ম্যাচ মিস হয়ে যেত — এই কোড সেলের আউটপুট সিকোয়েন্সে ঠিক এই কারণেই বিট-পজিশন ৩ ও ৫ দুটোতেই ম্যাচ পাওয়া গেছে।

অনুশীলন

হাতে-ট্রেস করুন: উপরের FSM-টিকে বিট-স্ট্রিম [1,1,0,1]-এর উপর হাতে-কলমে ট্রেস করুন (কোড চালানোর আগেই) — প্রতিটি বিটের পর স্টেট ও আউটপুট কী হবে?

শুরু S0। bit1=1 → S1 (out 0)। bit2=1 → S1 (out 0, S1-এ ইনপুট ১ এলে S1-এই থাকে)। bit3=0 → S2 (out 0)। bit4=1 → S3 (out 1, ম্যাচ — সর্বশেষ তিন বিট "101")। চূড়ান্ত স্টেট পাথ: S0→S1→S1→S2→S3, আউটপুট সিকোয়েন্স: [0,0,0,1] — বিট-পজিশন ৪-এ একটি ম্যাচ।
ডিজাইন করুন: একটি নতুন Moore FSM-এর স্টেট তালিকা ভাবুন যা "11" (পরপর দুটি ১) সনাক্ত করবে — কয়টি স্টেট লাগবে এবং কেন?

মাত্র ৩টি স্টেট যথেষ্ট — S0 (কিছুই মেলেনি বা সর্বশেষ বিট ০), S1 (সর্বশেষ বিট ১ কিন্তু তার আগেরটা নয়), S2/Match (পরপর দুটি ১ দেখা গেছে)। ট্রানজিশন: S0-তে ইনপুট ১→S1, ইনপুট ০→S0; S1-তে ইনপুট ১→S2 (ম্যাচ), ইনপুট ০→S0; S2-তে ইনপুট ১→S2 (থাকে, কারণ শেষ বিটও ১ — ওভারল্যাপিং মিলের সম্ভাবনা), ইনপুট ০→S0। "101" ডিটেক্টরের চেয়ে কম স্টেট লাগে কারণ প্যাটার্নটি ছোট (২ বিট বনাম ৩ বিট)।