Finite state machine — Moore, Mealy আর state diagram থেকে circuit

১ · State machine কী — যে circuit অতীত মনে রাখে

মডিউল ২-এর circuit-গুলোর output শুধু এই মুহূর্তের input দেখত — একে বলে combinational circuit. কিন্তু বহু কাজে আগে কী ঘটেছে তা মনে রাখতে হয়। মোবাইল ব্যাংকিং অ্যাপে ভুল PIN দিলে অ্যাপ বলে “আর ২ বার সুযোগ আছে” — অর্থাৎ সে গুনে রেখেছে আগে কতবার ভুল হয়েছে। এই গোনা একটি স্মৃতি। স্মৃতির প্রতিটি সম্ভাব্য অবস্থাকে বলে state, আর যে যন্ত্র নির্দিষ্টসংখ্যক state-এর একটিতে থাকে আর input অনুযায়ী state বদলায়, তাকে বলে finite state machine (FSM).

প্রতিটি FSM চারটি জিনিস দিয়ে পুরো বর্ণনা করা যায়:

• State-এর তালিকা — সসীম (finite), তাই নাম “finite”. যেমন: ভুল ০ বার, ১ বার, ২ বার, খোলা, বন্ধ (locked).
• Input — বাইরে থেকে যা আসে: সঠিক PIN, ভুল PIN, logout.
• Output — যন্ত্র যা জানায় বা করে: “২ বার সুযোগ আছে”, “স্বাগতম”, “অ্যাকাউন্ট বন্ধ”।
• Transition-এর নিয়ম — কোন state-এ কোন input এলে কোন state-এ যাবে। একটি transition মানে এক state থেকে আরেক state-এ যাওয়া।

সবচেয়ে ছোট উদাহরণ মেট্রোরেলের প্রবেশ-গেট বা টোকেন গেট (turnstile). দুটি state: বন্ধ আর খোলা. টোকেন বা কার্ড ছোঁয়ালে বন্ধ থেকে খোলা; কেউ ঢুকে গেলে (ধাক্কা) খোলা থেকে আবার বন্ধ। টোকেন ছাড়া ধাক্কা দিলে বন্ধই থাকে। এই তথ্য ছবিতে আঁকলে হয় state diagram — প্রতিটি state একটি বৃত্ত, প্রতিটি transition একটি তীর:

একই তথ্য টেবিলেও লেখা যায় — একে বলে state table. ছবি মানুষের বোঝার জন্য, টেবিল হিসাবের জন্য:

PIN-এর উদাহরণে state পাঁচটি: WRONG0, WRONG1, WRONG2 (কতবার ভুল হয়েছে), UNLOCKED আর LOCKED. WRONG2-তে আরেকবার ভুল এলে LOCKED, আর LOCKED থেকে সঠিক PIN দিলেও আর খোলে না — শুধু গ্রাহকসেবা বা নির্দিষ্ট নিয়মে reset হলে ফেরে। এই নকশাটি অংশ ৯-এ একটি C প্রোগ্রামে চালিয়ে দেখবেন। খেয়াল করুন, FSM-এর state-এ পুরো ইতিহাস থাকে না — শুধু ভবিষ্যতের সিদ্ধান্তের জন্য যতটুকু দরকার ততটুকু। কোন ভুল PIN দেওয়া হয়েছিল তা মনে রাখার দরকার নেই, শুধু কতবার।

২ · Hardware-এ FSM-এর গঠন — register আর দুই টুকরো logic

Digital circuit-এ FSM প্রায় সবসময় synchronous: state বদলায় শুধু clock-এর সক্রিয় ধারে। গঠন তিন টুকরো:

• State register: কয়েকটি D flip-flop, যা বর্তমান state-এর বিট-নকশা ধরে রাখে। n বিটে সর্বোচ্চ ২ⁿটি state. Flip-flop-এর ভেতরের গঠন পর্ব ১৫-এ (Latch আর flip-flop), আর register-এর বিস্তারিত পর্ব ১৬-এ।
• Next-state logic: বর্তমান state Q আর input x থেকে পরের state হিসাব করে — সাধারণ combinational circuit. এর output যায় flip-flop-এর D-তে; পরের clock ধারে সেটিই নতুন state.
• Output logic: output z হিসাব করে। এখানেই দুই মডেলের পার্থক্য।

গাণিতিকভাবে: state-এর সেট S, input-এর সেট I, output-এর সেট O, শুরুর state s₀, আর transition function δ : S × I → S. Output function দুই রকম:

৩ · নকশার ধাপ ১–২ · কথা থেকে state diagram — “1011” detector

FSM নকশার পূর্ণ পদ্ধতি সাত ধাপের — এই পর্বের বাকিটা এই ক্রমেই চলবে:

1. কথার সমস্যা → state diagram (প্রতিটি state-এর অর্থ এক লাইনে লিখে রাখা)
2. State table
3. State minimisation — সমতুল্য state একত্র করা (অংশ ৫)
4. State assignment — প্রতিটি state-কে বিট দেওয়া (অংশ ৬)
5. Next-state আর output সমীকরণ — K-map দিয়ে (অংশ ৬)
6. Circuit — flip-flop আর gate জোড়া
7. Simulation দিয়ে যাচাই

উদাহরণ হিসেবে নিন পরীক্ষার সবচেয়ে প্রচলিত প্রশ্নটি: একটি serial তারে প্রতি clock-এ একটি বিট x আসে। যখনই শেষ চারটি বিট 1011 হয়, output z = 1. এই ধরনের নকশাকে বলে sequence detector. প্রথমে একটি প্রশ্নের উত্তর ঠিক করতে হয়: একটি মিলের শেষ অংশ কি পরের মিলের শুরু হতে পারবে? যেমন 1011011-এ দুটি মিল, মাঝের 1টি দুজনেরই। এটি গুনলে overlapping, না গুনলে non-overlapping. প্রশ্নে স্পষ্ট না থাকলে নিজের ধারণাটি লিখে দেওয়া ভালো অভ্যাস।

পদ্ধতি: প্রতিটি state-এর অর্থ হবে “লক্ষ্যের শুরুর কতটুকু এই মুহূর্তে মিলে আছে”। তাই A = কিছুই মেলেনি, B = 1, C = 10, D = 101. নতুন বিট এলে প্রশ্ন একটাই: এখন পর্যন্ত দেখা লেখার শেষ অংশের সবচেয়ে লম্বা কোন টুকরো 1011-এর শুরুর সাথে মেলে? নিচের stepper-এ Mealy নকশাটি state ধরে ধরে বানানো হলো:

এই “শেষ অংশের সবচেয়ে লম্বা টুকরো যা লক্ষ্যের শুরুর সাথে মেলে” — নিয়মটি string matching-এর KMP অ্যালগরিদমের failure function-এর সাথে হুবহু এক; আগ্রহী হলে DSA কোর্সের string matching পর্ব দেখতে পারেন। নিচে একই Mealy নকশার ছবি:

একই detector, Moore মডেলে

Moore-এ output state-এর গায়ে থাকে, তাই “1011 পূর্ণ হয়েছে” — এই খবরের জন্য একটি আলাদা state লাগে। S0 = কিছু মেলেনি, S1 = 1, S2 = 10, S3 = 101, আর নতুন S4 = 1011 এইমাত্র এসেছে (output 1). S4 থেকে পরের transition-গুলো ঠিক Mealy-র B-এর মতো, কারণ overlapping নিয়মে “1011”-এর শেষ “1” নতুন শুরু:

S4-এ 0 এলে “10110”-এর শেষ “10” মেলে, তাই S2; 1 এলে “10111”-এর শেষ “1”, তাই S1. Non-overlapping Moore-এ S4-এর সারি হবে S0 আর S1 (মিলের পর নতুন করে শুরু; তবু নতুন 1টি প্রথম বিট হিসেবে গোনা যায়)।

৪ · Moore বনাম Mealy — output কখন আসে, state কত লাগে

দুই নকশাকে একই input দিয়ে চালালে আসল পার্থক্য চোখে পড়ে। আগে Moore detector-কে 1101011 দিয়ে cycle ধরে ধরে দেখুন। প্রতি cycle-এ output হলো বর্তমান state-এর output; clock ধারে state বদলায়:

এবার একটি ছোট simulator দিয়ে তিনটি নকশা — Moore, Mealy আর non-overlapping Mealy — একই input 10110110-এ পাশাপাশি চালানো যাক। Simulator-টি সাধারণ: যেকোনো state table আর বিট-স্ট্রিং দিলে প্রতিটি cycle ছাপে:

// Generic synchronous FSM simulator: give it a state table, it prints every clock cycle.
// Moore: out[state]. Mealy: out[state][x]. One input bit x is sampled per clock edge.
const moore = { kind: "Moore", start: "S0",
  next: { S0: ["S0", "S1"], S1: ["S2", "S1"], S2: ["S0", "S3"], S3: ["S2", "S4"], S4: ["S2", "S1"] },
  out:  { S0: 0, S1: 0, S2: 0, S3: 0, S4: 1 } };              // only S4 ("1011 seen") says 1
const mealy = { kind: "Mealy", start: "A",
  next: { A: ["A", "B"], B: ["C", "B"], C: ["A", "D"], D: ["C", "B"] },
  out:  { A: [0, 0], B: [0, 0], C: [0, 0], D: [0, 1] } };       // output on the D --1--> B arc
const noOv = { ...mealy, kind: "Mealy-nonoverlap",
  next: { ...mealy.next, D: ["C", "A"] } };                     // after a hit, start again from A
function step(m, s, x) {                                        // one clock cycle
  const z = m.kind === "Moore" ? m.out[s] : m.out[s][x];        // output during this cycle
  return { z, next: m.next[s][x] };                             // state after the clock edge
}
function simulate(machines, bits) {
  const st = machines.map(m => m.start), zs = machines.map(() => "");
  console.log(("cyc x | " + machines.map(m => m.kind.padEnd(17)).join("| ")).trimEnd());
  [...bits].forEach((ch, t) => {
    const x = +ch, cells = machines.map((m, i) => {
      const r = step(m, st[i], x), cell = `${st[i]}->${r.next} z=${r.z}`;
      st[i] = r.next; zs[i] += r.z; return cell.padEnd(17);
    });
    console.log((` ${t}  ${x} | ` + cells.join("| ")).trimEnd());
  });
  machines.forEach((m, i) => console.log(`${m.kind.padEnd(16)} z = ${zs[i]}`));
}
simulate([moore, mealy, noOv], "10110110");

cyc x | Moore            | Mealy            | Mealy-nonoverlap
 0  1 | S0->S1 z=0       | A->B z=0         | A->B z=0
 1  0 | S1->S2 z=0       | B->C z=0         | B->C z=0
 2  1 | S2->S3 z=0       | C->D z=0         | C->D z=0
 3  1 | S3->S4 z=0       | D->B z=1         | D->A z=1
 4  0 | S4->S2 z=1       | B->C z=0         | A->A z=0
 5  1 | S2->S3 z=0       | C->D z=0         | A->B z=0
 6  1 | S3->S4 z=0       | D->B z=1         | B->B z=0
 7  0 | S4->S2 z=1       | B->C z=0         | B->C z=0
Moore            z = 00001001
Mealy            z = 00010010
Mealy-nonoverlap z = 00010000

কেন Moore-এ state বেশি লাগে — একটি ছোট প্রমাণ

দাবি: একই input-output আচরণের জন্য (Moore-এর এক cycle দেরি মেনে নিয়ে) সবচেয়ে ছোট Mealy machine-এর state-সংখ্যা সবচেয়ে ছোট Moore machine-এর চেয়ে বেশি নয়।

• Moore → Mealy, state একই: যেকোনো Moore machine নিন। প্রতিটি তীর s --x--> t-এর গায়ে output হিসেবে λ(t) লিখুন — অর্থাৎ গন্তব্য state-এর output. ফল একটি Mealy machine, state-সংখ্যা একই, আর Moore যে output পরের cycle-এ দিত, এটি সেটিই এই cycle-এ দেয়। তাই Mealy-র ন্যূনতম state-সংখ্যা ≤ Moore-এর।
• Mealy → Moore, state বাড়তে পারে: একটি Mealy state-এ যদি ভিন্ন output-ওয়ালা তীর এসে পৌঁছায় (যেমন B-তে A --1/0--> B আর D --1/1--> B), Moore-এ সেই state-কে output অনুযায়ী ভাগ করতে হয় — B₀ আর B₁. সবচেয়ে খারাপ ক্ষেত্রে state-সংখ্যা |S| × |O| পর্যন্ত হয়। আমাদের detector-এ শুধু B ভাগ হয়েছে: B₁ = S4, তাই ৪ থেকে ৫।

বাস্তবে নকশাকারীরা প্রায়ই মাঝামাঝি পথ নেন: Mealy-তে হিসাব করে output-টিকে একটি flip-flop-এ ধরে রাখা (registered output). তখন আচরণ Moore-এর মতো এক cycle দেরিতে, কিন্তু state কম। Timing-এর এই হিসাব — setup, hold আর critical path — বিস্তারিত পর্ব ১৮-এ (Timing আর clock).

৫ · ধাপ ৩ · State minimisation — সমতুল্য state একত্র করা

প্রথমবার state diagram আঁকলে প্রায়ই অপ্রয়োজনীয় state থেকে যায় — বিশেষ করে বড় সমস্যায়, বা কেউ “প্রতিটি ঘটনার জন্য একটি নতুন state” নিয়ম মেনে আঁকলে। কম state মানে কম flip-flop (বা একই flip-flop-এ বেশি don't care) আর প্রায়ই ছোট logic. তাই ধাপ ৩: state minimisation.

সংজ্ঞা: দুটি state p আর q equivalent (p ≡ q), যদি যেকোনো input-ধারা p থেকে চালালে যে output-ধারা আসে, q থেকে চালালেও ঠিক সেটিই আসে। বাইরে থেকে এদের আলাদা করার কোনো পরীক্ষা নেই, তাই একটিকে মুছে তার দিকের সব তীর অন্যটিতে ঘুরিয়ে দেওয়া যায়। সরাসরি “সব input-ধারা” পরীক্ষা অসম্ভব (অসীম), তাই ধাপে ধাপে ভাবা হয়:

• p আর q k-equivalent, যদি ১ থেকে k দৈর্ঘ্যের সব input-ধারায় output এক। ১-equivalent মানে প্রতিটি একক input-এ output এক — এটিই শুরুর ভাগ, যাকে এই পর্বে P0 বলা হয়েছে (কিছু বই একে P1 বলে)। Moore-এ শুরুর ভাগ হয় state-এর নিজের output দিয়ে।
• মূল সূত্র: p আর q (k+1)-equivalent ⇔ এদের output প্রতিটি input-এ এক, আর প্রতিটি input x-এ δ(p, x) আর δ(q, x) k-equivalent.
• প্রতিটি ধাপে দলগুলো শুধু ভাঙতে পারে, জোড়া লাগে না; আর n state-এর বেশি দল হতে পারে না। তাই সর্বোচ্চ n − ১ ধাপে এমন একটি ধাপ আসে যেখানে কিছু ভাঙে না। তখন থেকে আর কখনো ভাঙবে না (পরের ধাপ একই সূত্রে একই দল থেকে হিসাব হয়) — সেই দলগুলোই আসল equivalence-এর দল।

এই পদ্ধতির নাম partition refinement (বইভেদে partition method বা Moore-এর algorithm). একটি ৭-state Mealy machine নিন, যা কেউ বাড়তি state রেখে এঁকেছেন:

একই কাজ implication table দিয়ে

পরীক্ষায় অনেক সময় implication table চাওয়া হয়। প্রতিটি state-জোড়ার একটি ঘর (৭টি state-এ ৭ × ৬ / ২ = ২১টি)। ধাপ: (১) output ভিন্ন হলে ঘরে X. (২) নইলে ঘরে লিখুন, এই জোড়া equivalent হতে হলে কোন কোন জোড়াকে equivalent হতে হবে (পরের state-এর জোড়া)। (৩) বারবার পুরো টেবিল ঘুরে দেখুন: কোনো ঘরের শর্তে X-ওয়ালা জোড়া থাকলে সেই ঘরেও X. আমাদের machine-এ:

যে তিনটি ঘর X-মুক্ত রইল — AG, BE, CF — সেগুলোই equivalent জোড়া, partition-এর ফলের সাথে হুবহু এক। লক্ষ করুন, বাকি তিনটি শর্ত একে অন্যের ওপর চক্রাকারে নির্ভর করে (AG চায় BE, BE চায় CF, CF চায় AG) — কোনো বিরোধ নেই বলে তিনটিই টিকে যায়। নিচের প্রোগ্রাম partition refinement চালিয়ে প্রতিটি ধাপ ছাপে, তারপর মূল আর ছোট machine-কে ৮ বিট পর্যন্ত দৈর্ঘ্যের সব input-ধারায় চালিয়ে মেলায়:

// State minimisation by partition refinement on a 7-state Mealy machine.
// M[s][x] = [next state, output]. Start state A.
const M = { A: [["A", 0], ["B", 0]], B: [["C", 0], ["E", 0]], C: [["G", 0], ["D", 0]],
            D: [["F", 0], ["E", 1]], E: [["F", 0], ["B", 0]], F: [["A", 0], ["D", 0]],
            G: [["G", 0], ["E", 0]] };
const S = Object.keys(M), show = P => P.map(g => "{" + g.join(",") + "}").join(" ");
function split(keyOf) {                       // group states that have the same key
  const g = {}; S.forEach(s => (g[keyOf(s)] ??= []).push(s)); return Object.values(g);
}
let P = split(s => "out" + M[s].map(c => c[1]).join("")), k = 0;  // P0: same output row
for (;;) {
  console.log(`P${k}: ${show(P)}`);
  const id = {}; P.forEach((g, i) => g.forEach(s => (id[s] = i)));
  const Q = split(s => id[s] + ":" + M[s].map(c => id[c[0]]).join(","));  // same block AND same next-blocks
  if (Q.length === P.length) { console.log(`P${k + 1} = P${k}: stable`); break; }
  P = Q; k++;
}
const rep = {}; P.forEach(g => g.forEach(s => (rep[s] = g[0])));   // name each block by its first state
const R = {}; P.forEach(g => (R[g[0]] = M[g[0]].map(([n, z]) => [rep[n], z])));
console.log("reduced table (state: x=0 next/z, x=1 next/z):");
for (const s in R) console.log(`  ${s}: ${R[s][0].join("/")}  ${R[s][1].join("/")}`);
function outputs(T, bits) {                   // output string of a machine on an input string
  let s = "A", z = "";
  for (const ch of bits) { z += T[s][+ch][1]; s = T[s][+ch][0]; }
  return z;
}
let tested = 0, bad = 0;
for (let len = 1; len <= 8; len++)
  for (let v = 0; v < 1 << len; v++) {
    const bits = v.toString(2).padStart(len, "0"); tested++;
    if (outputs(M, bits) !== outputs(R, bits)) bad++;
  }
console.log(`${S.length} states -> ${P.length} states; ${tested} input strings checked, ${bad} differ`);

P0: {A,B,C,E,F,G} {D}
P1: {A,B,E,G} {C,F} {D}
P2: {A,G} {B,E} {C,F} {D}
P3 = P2: stable
reduced table (state: x=0 next/z, x=1 next/z):
  A: A/0  B/0
  B: C/0  B/0
  C: A/0  D/0
  D: C/0  B/1
7 states -> 4 states; 510 input strings checked, 0 differ

৬ · ধাপ ৪–৭ · State assignment, K-map থেকে সমীকরণ আর যাচাই

ধাপ ৪ · কোন state পাবে কোন বিট

A, B, C, D নামগুলো hardware বোঝে না; প্রতিটিকে একটি বিট-নকশা দিতে হয়। এই সিদ্ধান্তকে বলে state assignment বা state encoding. n-টি state-এর জন্য প্রধান তিনটি পথ:

One-hot-এর সমীকরণ লেখা প্রায় যান্ত্রিক: “এই state-এর flip-flop পরের ধারে 1 হবে, যদি এখন এমন কোনো state সক্রিয় থাকে যার তীর এখানে আসে, আর সেই তীরের input মেলে”। যেমন “1011” detector-এ C-তে আসে B --0--> আর D --0-->, তাই D_C = Q_Bx′ + Q_Dx′. FPGA-তে প্রতিটি LUT-এর পাশে flip-flop প্রায় বিনামূল্যে থাকে, আর এমন ছোট সমীকরণ একটি LUT-এই ধরে যায় — তাই FPGA-র synthesis tool প্রায়ই নিজে থেকে FSM-কে one-hot-এ বদলে নেয় (tool আর সেটিংসভেদে)। ASIC-এ flip-flop তুলনায় দামি, তাই ছোট-মাঝারি FSM-এ binary বা নকশাকারীর বাছা encoding বেশি দেখা যায়।

Binary-র ভেতরেও কোন state কোন কোড পাবে, তাতে logic বদলায়। ৪টি state-এ ৪! = ২৪ রকম assignment, আর বড় machine-এ সংখ্যাটি বিশাল — তাই পুরোনো পাঠ্যবইয়ে হাতে-খাটানো নিয়ম আছে: যে দুটি state-এর একই পরের state, বা যারা একই state-এর পরের state, তাদের পাশাপাশি (এক বিট ভিন্ন) কোড দিন — এতে K-map-এ 1-গুলো পাশাপাশি পড়ে বড় দল হয়। আধুনিক tool এই খোঁজ heuristic দিয়ে করে।

ধাপ ৫–৭ · K-map থেকে সমীকরণ, circuit আর যাচাই

Binary assignment নিন: A = 00, B = 01, C = 10, D = 11 (বিট Q₁Q₀). প্রতিটি সারিতে বর্তমান Q₁Q₀ আর x থেকে পরের Q₁⁺Q₀⁺ আর z লিখুন। D flip-flop-এ Q⁺ = D, তাই পরের state-এর বিটই সরাসরি D ইনপুট — একে বলে transition table:

এবার প্রতিটি কলাম আলাদা একটি ৩-চলকের Boolean function — পর্ব ০৯-এর K-map দিয়ে সরল করুন (এই পৃষ্ঠায় complement লেখা হয়েছে প্রাইম চিহ্নে: x′ মানে NOT x; কোডের আউটপুটে একই জিনিস ASCII ' দিয়ে):

• D₁ = Σm(2, 5, 6). ঘর ২ (010) আর ৬ (110) পাশাপাশি — দল Q₀x′. ঘর ৫ (101) একা — Q₁Q₀′x. তাই D₁ = Q₀x′ + Q₁Q₀′x.
• D₀ = Σm(1, 3, 5, 7) — x = 1-এর চারটি ঘরই। এক দলে: D₀ = x. অর্থ স্পষ্ট: শেষ বিট 1 হলেই পরের state B বা D (দুটিরই Q₀ = 1).
• z = Σm(7) = Q₁Q₀x — state D আর x = 1. Mealy বলে x আছে।

ধাপ ৬, circuit: দুটি D flip-flop (একই clock); D₀-এ সরাসরি x-এর তার; D₁-এ দুটি AND (২ আর ৩ ইনপুটের) আর একটি OR; z-এর জন্য একটি ৩-ইনপুট AND; আর x′ ও Q₀′-এর জন্য দুটি inverter. সব মিলিয়ে কয়েকটি gate — ৪টি product term, ৯টি literal. Encoding বদলালে এই হিসাব কেমন বদলায়, আর সমীকরণগুলো আসলেই state table মেনে চলে কি না (ধাপ ৭), নিচের প্রোগ্রাম দেখায়। এটি ছোট একটি brute-force minimiser চালিয়ে binary আর Gray-তে ন্যূনতম SOP খোঁজে, one-hot-এ তীর গুনে সমীকরণ লেখে, তারপর তিনটি circuit-কে ২৫৬ cycle চালিয়ে টেবিলের সাথে মেলায়:

// Minimised "1011" Mealy detector -> D flip-flop and output equations under three encodings.
const T = { A: [["A", 0], ["B", 0]], B: [["C", 0], ["B", 0]], C: [["A", 0], ["D", 0]], D: [["C", 0], ["B", 1]] };
const S = Object.keys(T), lits = c => [...c].filter(ch => ch !== "-").length;
const has = (c, m, n) => [...c].every((ch, i) => ch === "-" || +ch === ((m >> (n - 1 - i)) & 1));
function minSOP(n, f) {                       // f(m) = 1 or 0; brute-force smallest SOP (n <= 3)
  const all = [...Array(1 << n).keys()], on = all.filter(m => f(m)), cubes = [];
  for (let v = 0; v < 3 ** n; v++) { let c = ""; for (let i = 0, w = v; i < n; i++, w = (w - w % 3) / 3) c += "01-"[w % 3]; cubes.push(c); }
  const imp = cubes.filter(c => all.every(m => !has(c, m, n) || f(m)) && on.some(m => has(c, m, n)));
  let best = [], cost = Infinity;                   // try every subset of implicants
  for (let mask = 0; mask < 2 ** imp.length; mask++) {   // cost = literals, then number of terms
    const pick = imp.filter((_, i) => Math.floor(mask / 2 ** i) % 2), c = pick.reduce((a, p) => a + lits(p), 0) * 100 + pick.length;
    if (c < cost && on.every(m => pick.some(p => has(p, m, n)))) { best = pick; cost = c; }
  }
  return best; }
function design(label, code, names, oneHot) { // code[state] = bits; one-hot = OR of the arcs entering each state
  const k = code.A.length, n = k + 1, dec = {}; S.forEach(s => (dec[code[s]] = s));
  const row = m => T[dec[(m >> 1).toString(2).padStart(k, "0")]][m & 1];
  const arcs = want => S.flatMap(s => [0, 1].filter(x => want(T[s][x])).map(x => code[s].replace(/0/g, "-") + x));
  const eqs = [...Array(k).keys()].map(i => oneHot ? arcs(([nx]) => code[nx][i] === "1") : minSOP(n, m => +code[row(m)[0]][i]));
  const zq = oneHot ? arcs(([, z]) => z === 1) : minSOP(n, m => row(m)[1]);
  const sop = e => e.map(c => [...c].map((ch, i) => ch === "-" ? "" : names[i] + (ch === "0" ? "'" : "")).join("")).join(" + ") || "0";
  const total = [...eqs, zq].flat(); console.log(`${label}: ${k} flip-flops, ${total.length} product terms, ${total.reduce((a, c) => a + lits(c), 0)} literals`);
  eqs.forEach((e, i) => console.log(`  D${names[i]} = ${sop(e)}`)); console.log(`  z = ${sop(zq)}`);
  let s = "A", q = code.A, ok = 0, x = 1, seen = new Set();   // verify: equations vs table, 256 clocks
  for (let t = 0; t < 256; t++, x = (x * 13 + 7) % 32) {
    const b = x >> 4, m = parseInt(q + b, 2), z = +zq.some(c => has(c, m, n));
    const nq = eqs.map(e => +e.some(c => has(c, m, n))).join("");
    if (z === T[s][b][1] && nq === code[T[s][b][0]]) ok++;
    seen.add(s + b); s = T[s][b][0]; q = nq;
  }
  console.log(`  check: ${ok}/256 cycles match the table, ${seen.size}/8 transitions exercised`);
}
design("binary  A=00 B=01 C=10 D=11", { A: "00", B: "01", C: "10", D: "11" }, ["Q1", "Q0", "x"]);
design("gray    A=00 B=01 C=11 D=10", { A: "00", B: "01", C: "11", D: "10" }, ["Q1", "Q0", "x"]);
design("one-hot A=1000 B=0100 C=0010 D=0001", { A: "1000", B: "0100", C: "0010", D: "0001" }, ["QA", "QB", "QC", "QD", "x"], true);

binary  A=00 B=01 C=10 D=11: 2 flip-flops, 4 product terms, 9 literals
  DQ1 = Q0x' + Q1Q0'x
  DQ0 = x
  z = Q1Q0x
  check: 256/256 cycles match the table, 8/8 transitions exercised
gray    A=00 B=01 C=11 D=10: 2 flip-flops, 7 product terms, 18 literals
  DQ1 = Q1Q0'x' + Q1'Q0x' + Q1Q0x
  DQ0 = Q0'x + Q1Q0' + Q1'Q0
  z = Q1Q0'x
  check: 256/256 cycles match the table, 8/8 transitions exercised
one-hot A=1000 B=0100 C=0010 D=0001: 4 flip-flops, 9 product terms, 18 literals
  DQA = QAx' + QCx'
  DQB = QAx + QBx + QDx
  DQC = QBx' + QDx'
  DQD = QCx
  z = QDx
  check: 256/256 cycles match the table, 8/8 transitions exercised

একটি JK flip-flop উদাহরণ

পরীক্ষায় অনেক সময় JK বা T flip-flop দিয়ে নকশা চাওয়া হয়। তখন এক ধাপ বাড়ে: প্রতিটি সারিতে “Q থেকে Q⁺-এ যেতে J আর K-তে কী দিতে হবে” — এটি আসে excitation table থেকে (পর্ব ১৫-এ বিস্তারিত)। JK flip-flop-এর excitation: 0 → 0: J = 0, K = X; 0 → 1: J = 1, K = X; 1 → 0: J = X, K = 1; 1 → 1: J = X, K = 0. অনেক X (don't care) থাকায় K-map-এ দল বড় হয়। একই binary detector-এ:

K-map থেকে (X-কে দরকারমতো 1 ধরে): J₁ = Q₀x′, K₁ = Q₀′x′ + Q₀x (অর্থাৎ Q₀ ⊙ x, XNOR), J₀ = x, K₀ = x′. যাচাই: JK-র সূত্র Q⁺ = JQ′ + K′Q-তে বসালে Q₀⁺ = xQ₀′ + xQ₀ = x — D-নকশার D₀ = x-এর সাথে মেলে। (এই সমীকরণগুলো একটি আলাদা scratch script-এ brute-force minimiser দিয়েও মিলিয়ে নেওয়া হয়েছে।)

৭ · আরও দুটি উদাহরণ, অব্যবহৃত state আর reset

(ক) Serial even parity — একটি T flip-flop

একটি তারে বিট আসছে; এখন পর্যন্ত আসা 1-এর সংখ্যা জোড় হলে z = 1 (Moore). দুটি state যথেষ্ট — EVEN (z = 1) আর ODD (z = 0); 1 এলে state উল্টায়, 0 এলে থাকে। Q = 0 মানে EVEN ধরলে: D-তে D = Q ⊕ x, আর T flip-flop-এ আরও সহজ — T = x (1 এলে toggle), z = Q′. Network-এর parity বিট এভাবেই হিসাব হয় (Computer Networks কোর্সের error detection পর্ব)।

(খ) ৩ দিয়ে বিভাজ্য কি না — serial বিটে

একটি binary সংখ্যা MSB আগে করে একটি একটি বিট আসছে। প্রতি মুহূর্তে বলতে হবে, এখন পর্যন্ত আসা সংখ্যাটি ৩ দিয়ে বিভাজ্য কি না। পুরো সংখ্যা মনে রাখার দরকার নেই — শুধু ৩ দিয়ে ভাগশেষ r. যুক্তি: এখন পর্যন্ত সংখ্যা N হলে নতুন বিট x আসার পর সংখ্যা 2N + x; তাই নতুন ভাগশেষ r⁺ = (2r + x) mod 3, যা শুধু r আর x-এর ওপর নির্ভর করে। ৩টি state: R0, R1, R2; z = 1 শুধু R0-তে (Moore).

উদাহরণ: 110110 (= ৫৪)। ভাগশেষ ক্রমে 1, 0, 0, 1, 0, 0 (১, ৩, ৬, ১৩, ২৭, ৫৪-এর ভাগশেষ) — শেষে R0, অর্থাৎ ৫৪ ৩ দিয়ে বিভাজ্য। কোড 11-কে don't care ধরে K-map থেকে: D₁ = Q₀x′ + Q₁x, D₀ = Q₁x′ + Q₁′Q₀′x, z = Q₁′Q₀′ — মোট ৯টি literal.

অব্যবহৃত state — চুপচাপ ফাঁদ

৩টি state-এর জন্য ২টি flip-flop, তাই কোড 11 কোনো state পায়নি — এটি unused state. স্বাভাবিক চলায় সেখানে যাওয়া যায় না, কিন্তু চালু হওয়ার মুহূর্তে flip-flop-এর মান এলোমেলো থাকতে পারে, বা বিদ্যুতের ঝাঁকুনি, তড়িৎ-চৌম্বক শব্দ বা মহাজাগতিক কণার আঘাতে একটি বিট উল্টে যেতে পারে। তখন প্রশ্ন: 11 থেকে machine কোথায় যায়? ওপরের সমীকরণে বসিয়ে দেখুন: x = 0 হলে D₁ = 1·1 = 1, D₀ = 1·1 = 1 — আবার 11! আর z = 0. অর্থাৎ যতক্ষণ 0 আসতে থাকে, machine 11-এ আটকে থাকে, ভুল output দেয় — একে বলে lock-up. x = 1 এলে 10 (R2)-তে বেরিয়ে আসে, কিন্তু ততক্ষণে হিসাব নষ্ট।

সমাধান তিনটি, খরচ অনুযায়ী:

• স্পষ্ট নিয়ম দেওয়া: don't care না ধরে লিখুন 11 → R0 (দুই input-এই)। নতুন সমীকরণ D₁ = Q₁′Q₀x′ + Q₁Q₀′x, D₀ = Q₁Q₀′x′ + Q₁′Q₀′x — ১২টি literal (আগে ৯)। খরচ সামান্য বাড়ল, বদলে machine self-correcting: যেকোনো অবস্থা থেকে এক cycle-এ বৈধ state-এ ফেরে।
• অন্তত যাচাই করা: don't care রেখে সমীকরণ বের করার পর প্রতিটি অব্যবহৃত কোড বসিয়ে দেখুন — কয়েক cycle-এ বৈধ state-এ ফিরলে যথেষ্ট কি না, নকশার প্রয়োজন অনুযায়ী ঠিক করুন। (অংশ ৬-এর ৫-state Moore detector-এ 101, 110, 111 সবই এক cycle-এ বৈধ state-এ যায়।)
• Reset: চালু হওয়ার সময় একটি reset সংকেত সব flip-flop-কে শুরুর state-এ বসায়। এটি প্রায় প্রতিটি নকশায় লাগে — কিন্তু চলার মাঝে বিট উল্টালে reset সাহায্য করে না, তাই নিরাপত্তা-গুরুত্বপূর্ণ নকশায় প্রথম পথটিও লাগে।

Synchronous বনাম asynchronous reset

শিল্পে প্রচলিত সমাধান দুটির মিশ্রণ: reset ধরা হয় asynchronously, ছাড়া হয় synchronously — দুই flip-flop-এর একটি ছোট “reset synchronizer” দিয়ে। কোনটি ভালো, তা নিয়ে কোম্পানি আর FPGA-নির্মাতাদের পরামর্শ ভিন্ন; নকশার নিয়মপুস্তক মেনে চলাই নিয়ম। কেন ধারের কাছে বদলানো সংকেত বিপজ্জনক (setup-hold আর metastability), তা পর্ব ১৮-এ; reset ছাড়ার ক্ষেত্রে একই ধরনের সময়সীমার নাম recovery আর removal time.

৮ · Verilog-এ FSM — তিন block-এর রীতি আর পরীক্ষা

পর্ব ১৪-এ দেখেছেন, combinational block-এ কোনো পথে output মান না পেলে latch তৈরি হয়। FSM লেখার প্রচলিত রীতি এই ফাঁদ এড়ায় নকশাটিকে ছবি ১৭.২-এর তিন টুকরোয় আলাদা রেখে: একটি clock-চালিত block (শুধু state register), একটি combinational block (next-state logic) আর output-এর জন্য আরেকটি (বা একটি assign). State-এর নাম দেওয়া হয় localparam দিয়ে:

module det1011 (
    input  wire clk,
    input  wire rst_n,          // active-low asynchronous reset
    input  wire x,              // one serial bit per clock
    output reg  z
);
    localparam [1:0] A = 2'd0,  // nothing useful seen
                     B = 2'd1,  // "1"
                     C = 2'd2,  // "10"
                     D = 2'd3;  // "101"
    reg [1:0] state, next;

    // (1) state register: the only flip-flops in the design
    always @(posedge clk or negedge rst_n)
        if (!rst_n) state <= A;
        else        state <= next;

    // (2) next-state logic: combinational, blocking "="
    always @(*) begin
        next = state;                   // default first: every path assigns next, so no latch
        case (state)
            A: if (x)  next = B;
            B: if (!x) next = C;
            C: next = x ? D : A;
            D: next = x ? B : C;        // overlapping: "1011" ends in "1" -> B
            default: next = A;          // unreachable here (all 4 codes used) - safe habit
        endcase
    end

    // (3) output logic: Mealy = state AND input
    always @(*) begin
        z = 1'b0;
        if (state == D && x) z = 1'b1;
    end
endmodule

কয়েকটি নিয়ম, যা এই ছোট module-এ লুকিয়ে আছে:

• next = state; শুরুতেই: যে শাখায় next লেখা হয়নি (যেমন A-তে x = 0), সেখানে “একই state-এ থাকা” — latch নয়, কারণ register তো আছেই। এই এক লাইন বাদ দিলে A আর B শাখায় next কোনো মান পায় না, আর synthesis একটি latch বসায়।
• Register block-এ <=, combinational block-এ = (non-blocking বনাম blocking) — পর্ব ১৪-এর নিয়ম।
• Moore হলে output block শুধু state পড়বে: ৫-state নকশায় assign z = (state == S4);.
• Synchronous reset চাইলে sensitivity list থেকে negedge rst_n সরিয়ে দিন — বাকি সব একই।

SystemVerilog-এ আরও পরিষ্কার: typedef enum logic [1:0] {A, B, C, D} state_t; দিয়ে state-এর নিজস্ব type (enum), আর always_ff / always_comb, যাতে tool নিজে মিলিয়ে দেখে block-টি সত্যিই flip-flop বা combinational. Simulator-এর waveform-এ তখন 2'd3-এর বদলে নাম “D” দেখায়। দুই-block রীতিও প্রচলিত — next-state আর output একই combinational block-এ — তবে output-কে register-এ রাখতে চাইলে (registered output) সেটি clock-চালিত block-এ যায়।

FSM পরীক্ষা — state আর transition coverage

একটি testbench যত cycle-ই চালাক, যদি কোনো তীর একবারও না চলে, সেই তীরের ভুল ধরা পড়বে না — অংশ ৬-এর প্রোগ্রামের প্রথম খসড়ার অভিজ্ঞতাই এর প্রমাণ। তাই FSM-এর পরীক্ষায় দুটি সংখ্যা মাপা হয়:

• State coverage: মোট state-এর কয়টিতে অন্তত একবার পৌঁছানো গেছে। দুর্বল মাপ — “1011” detector-এর চারটি state ছোঁয়া যায় এমন input-এও D --0--> C তীর বাদ পড়তে পারে।
• Transition coverage: state × input-এর কয়টি তীর চলেছে — এখানে ৮টির ৮টি চাই। আরও কড়া মাপ হলো তীরের জোড়া বা ক্রম (যেমন “মিলের ঠিক পরে আবার মিল” — overlapping পরীক্ষা)।

এর সাথে থাকে reset-এর পরের state, প্রতিটি অব্যবহৃত কোড থেকে কী হয়, আর একটি “সোনালি মডেল” (যেমন অংশ ৪-এর JS simulator) — RTL-এর output প্রতি cycle-এ মডেলের সাথে মেলানো। শিল্পে SystemVerilog-এর coverage tool এই গোনা স্বয়ংক্রিয়ভাবে করে, আর formal tool গাণিতিকভাবে প্রমাণ করতে পারে যে কোনো state থেকে ফেরার পথ আছে।

৯ · FSM সবখানে — protocol থেকে CPU, cache আর regex

একবার FSM চিনলে চারপাশে সবখানে দেখবেন। Hardware-এ:

• Protocol controller: একটি UART receiver-এর state সাধারণত IDLE (তার উঁচু) → START (নিচু হলো — start বিট কি না, মাঝখানে আবার দেখা) → DATA (৮টি বিট, প্রতিটির মাঝখানে নমুনা; সময় মাপতে প্রায়ই baud rate-এর ১৬ গুণ গতির একটি counter) → STOP (তার উঁচু কি না; না হলে framing error). USB-এর specification-এ একটি device-এর অবস্থাগুলো (যেমন Default, Address, Configured, Suspended) state machine হিসেবেই বর্ণিত, আর TCP সংযোগের LISTEN, SYN-SENT, ESTABLISHED-এর মতো অবস্থাও একটি বিখ্যাত state diagram (Computer Networks কোর্সের TCP সংযোগ পর্ব)।
• CPU-র control unit: একটি multi-cycle প্রসেসরে প্রতিটি instruction কয়েকটি ধাপে চলে — fetch, decode, execute, memory, write-back — আর কোন ধাপের পর কোন ধাপ, তা ঠিক করে একটি FSM; প্রতিটি state-এ কোন control সংকেত চালু থাকবে, তা Moore-ধাঁচের output. এই নকশা পর্ব ৩৩ (Control unit) আর পর্ব ৩৪ (Multi-cycle datapath আর microprogrammed control)-এ। Counter-ও আসলে একটি সরল FSM — যার input নেই, বা বড়জোর একটি enable; পর্ব ১৬-এ।
• Cache controller: প্রতিটি cache line-এর অবস্থা (Modified, Exclusive, Shared, Invalid) আর অন্য core-এর অনুরোধে তার বদল — MESI protocol — একটি FSM; পর্ব ৫৩-এ।
• Regex engine: তত্ত্বে output-হীন FSM-কে বলে DFA: কিছু state “গ্রহণযোগ্য”, শেষে সেখানে থাকলে লেখাটি নকশার সাথে মেলে। প্রতিটি regular expression-এর সমান একটি DFA আছে, আর “1011” detector আসলে regex (0|1)*1011-এর DFA. Programming-এ regex ব্যবহার দেখতে পারেন Python কোর্সের regex পর্বে।

Software-এও FSM একটি প্রিয় নকশা-পদ্ধতি: firmware, game-এর চরিত্র, UI-এর পর্দা বদল, network parser. সবচেয়ে পরিষ্কার রূপ টেবিল-চালিত — state × event-এর একটি টেবিল, আর একটি ছোট loop. অংশ ১-এর PIN-লকের নকশা C-তে:

#include <stdio.h>
/* PIN entry that locks after 3 wrong tries, written as a table-driven FSM (Moore style). */
typedef enum { WRONG0, WRONG1, WRONG2, UNLOCKED, LOCKED, NSTATES } State;
typedef enum { OK, BAD, LOGOUT, RESET, NEVENTS } Event;
static const char *sname[NSTATES] = { "WRONG0", "WRONG1", "WRONG2", "UNLOCKED", "LOCKED" };
static const char *ename[NEVENTS] = { "correct PIN", "wrong PIN", "logout", "admin reset" };
static const char *say[NSTATES]   = { "enter PIN (3 tries left)", "enter PIN (2 tries left)",
                                      "enter PIN (1 try left)", "welcome", "account locked" };
static const State next[NSTATES][NEVENTS] = {
    /*             OK        BAD       LOGOUT    RESET  */
    /* WRONG0 */ { UNLOCKED, WRONG1,   WRONG0,   WRONG0 },
    /* WRONG1 */ { UNLOCKED, WRONG2,   WRONG1,   WRONG0 },
    /* WRONG2 */ { UNLOCKED, LOCKED,   WRONG2,   WRONG0 },
    /* UNLOCK */ { UNLOCKED, UNLOCKED, WRONG0,   WRONG0 },
    /* LOCKED */ { LOCKED,   LOCKED,   LOCKED,   WRONG0 },
};
static State step(State s, Event e) {
    if ((unsigned)s >= (unsigned)NSTATES || (unsigned)e >= (unsigned)NEVENTS)
        return LOCKED;                      /* corrupted value: fall into the safe state */
    return next[s][e];
}
int main(void) {
    const Event input[] = { BAD, OK, LOGOUT, BAD, BAD, BAD, OK, RESET, OK };
    State s = WRONG0;                       /* reset state */
    printf("start    %-8s : %s\n", sname[s], say[s]);
    for (unsigned i = 0; i < sizeof input / sizeof input[0]; i++) {
        State n = step(s, input[i]);
        printf("%-11s %-8s -> %-8s : %s\n", ename[input[i]], sname[s], sname[n], say[n]);
        s = n;
    }
    printf("unknown state 7 -> %s\n", sname[step((State)7, OK)]);
    return 0;
}

start    WRONG0   : enter PIN (3 tries left)
wrong PIN   WRONG0   -> WRONG1   : enter PIN (2 tries left)
correct PIN WRONG1   -> UNLOCKED : welcome
logout      UNLOCKED -> WRONG0   : enter PIN (3 tries left)
wrong PIN   WRONG0   -> WRONG1   : enter PIN (2 tries left)
wrong PIN   WRONG1   -> WRONG2   : enter PIN (1 try left)
wrong PIN   WRONG2   -> LOCKED   : account locked
correct PIN LOCKED   -> LOCKED   : account locked
admin reset LOCKED   -> WRONG0   : enter PIN (3 tries left)
correct PIN WRONG0   -> UNLOCKED : welcome
unknown state 7 -> LOCKED

১০ · AI-এর যুগে — state diagram AI দিয়ে, যাচাই simulation দিয়ে

“1011 detector-এর Verilog লিখে দিন” বললে AI কয়েক সেকেন্ডে উত্তর দেয়, আর দেখতে প্রায়ই নিখুঁত। কিন্তু FSM-এর ভুল সূক্ষ্ম — একটি ভুল তীর শুধু বিশেষ input-ক্রমেই ধরা পড়ে। এই বিষয়ে AI-এর প্রচলিত ভুল:

• ভুল তীর: B-তে 1 এলে A-তে ফেরানো, D-তে 0 এলে A-তে ফেরানো (C হওয়ার কথা) — overlapping আর non-overlapping গুলিয়ে ফেলা।
• Moore আর Mealy মিশিয়ে ফেলা: “Moore” বলে output-এ input ঢুকিয়ে দেওয়া, বা Moore-এর এক cycle দেরি ভুলে testbench-এ ভুল cycle-এ output খোঁজা।
• K-map আর minimisation-এ ভুল: ভুল দল, অব্যবহৃত কোডকে don't care ধরে lock-up তৈরি করা, বা equivalent নয় এমন state একত্র করা।
• Non-synthesizable বা latch-ওয়ালা Verilog: default ছাড়া combinational block, একই block-এ = আর <= মেশানো, নকশার ভেতরে initial দিয়ে state বসানো।
• বানানো তথ্য: কোনো chip বা protocol-এর state-এর নাম ও সংখ্যা, বা কোনো tool-এর encoding option ভুল বলা।

AI-এর দেওয়া FSM যাচাইয়ের চেকলিস্ট

• প্রতিটি state-এর অর্থ নিজে লিখে প্রতিটি তীর হাতে মিলিয়েছি — বিশেষ করে “ভুল বিট এলে কোথায় ফেরে” ঘরগুলো
• State table নিজের simulator-এ (যেমন অংশ ৪-এর JS) চালিয়ে overlapping-এর একটি input, যেমন 1011011, দিয়ে output-এর cycle মিলিয়েছি
• সমীকরণগুলো truth table-এ বসিয়ে বা script দিয়ে যাচাই করেছি; অব্যবহৃত কোডগুলো থেকে কী হয় দেখেছি
• Verilog-এ default আছে, latch নেই (lint বা synthesis-এর রিপোর্টে দেখা), reset-এর ধরন প্রয়োজনমতো
• Testbench-এ transition coverage পূর্ণ, আর protocol বা chip-এর তথ্য মূল specification বা datasheet-এ মিলিয়েছি