আরও সরলীকরণ — Quine-McCluskey, multi-level logic আর hazard

১ · K-map-এর সীমা — ৫ আর ৬ চলকের map

পর্ব ০৯-এ আপনি K-map দিয়ে সরলীকরণ শিখেছেন। এর গোপন কৌশল একটিই: ঘরগুলো Gray code-এর ক্রমে সাজানো, তাই পাশাপাশি দুটি ঘর ঠিক একটি বিটে আলাদা (Hamming distance ১)। আর এমন দুটি 1-কে একসাথে নিলে Boolean algebra-র একটি সূত্র (পর্ব ০৭-এর Boolean algebra) কাজ করে:

অর্থাৎ যে চলকটি দলের ভেতরে বদলায়, সেটি পদ থেকে বাদ পড়ে। K-map আসলে এই সূত্রকে চোখে দেখার একটি ছবি। এই পর্বে প্রশ্ন — ছবিটি কত বড় হলে আর চোখে ধরা যায় না, আর তখন কী করবেন? প্রতীকের নিয়ম মনে রাখুন: লেখায় উল্টো রূপ (complement) A′ (prime চিহ্ন) দিয়ে লেখা হবে, আর কোডে ' বা ~ দিয়ে।

৫ চলক: দুটি ৪ চলকের map, একটির ওপর আরেকটি

৫ চলকে (A, B, C, D, E) ঘর ৩২টি। সবচেয়ে প্রচলিত আঁকা হলো দুটি ৪ চলকের map: একটিতে A = 0 (minterm ০–১৫), আরেকটিতে A = 1 (minterm ১৬–৩১)। প্রতিটি map-এর ভেতরে আগের মতোই সারিতে BC আর কলামে DE, Gray ক্রমে। নতুন নিয়মটি শুধু একটি: দুই map-এর ঠিক একই জায়গার দুটি ঘর পরস্পরের প্রতিবেশী, কারণ তারা কেবল A-তে আলাদা। দুটি map স্বচ্ছ কাগজে এঁকে একটির ওপর আরেকটি রাখলে যে ঘর দুটি মিলে যায়, তারাই প্রতিবেশী।

আরেক রকম আঁকাও বইয়ে দেখবেন: একটি ৪ × ৮ map, যার কলামে তিনটি চলক (যেমন CDE) প্রতিফলিত Gray ক্রমে: 000, 001, 011, 010 │ 110, 111, 101, 100. এখানে মাঝখানে একটি কল্পিত আয়না থাকে — আয়নার দুই পাশে সমান দূরত্বের কলাম (যেমন 010 আর 110, বা 000 আর 100) প্রতিবেশী। একে বলে mirror adjacency. দুটি আঁকাই একই সত্য বলে; এই পর্বে আমরা “দুটি map ওপর-নিচে” রূপটি ব্যবহার করব, কারণ সেটি ভুল কম করায়।

উদাহরণ: F(A, B, C, D, E) = Σm(0,2,4,6,9,13,21,23,25,29,31). ঘরে লেখা সংখ্যাটি minterm নম্বর, আর ■ মানে সেখানে F = 1:

তিনটি দল চোখে পড়ে:

• ০, ২, ৪, ৬ — A = 0 map-এর ওপরের দুই সারির চার কোণের মতো (DE = 00 আর 10 কলাম পাশাপাশি, কারণ map-এর ডান-বাঁ কিনারা জোড়া)। এখানে A = 0, B = 0, E = 0 স্থির, C আর D বদলায় → A′B′E′.
• ৯, ১৩, ২৫, ২৯ — দুই map-এর একই জায়গা (BC = 11 আর 10, DE = 01). ওপর-নিচে মেলানো দল: A বদলায়, C বদলায়; স্থির B = 1, D = 0, E = 1 → BD′E.
• ২১, ২৩, ২৯, ৩১ — শুধু A = 1 map-এ, BC = 01, 11 আর DE = 01, 11 → ACE.

ফল: F = A′B′E′ + BD′E + ACE. মিনটার্ম ২৯ দুটি দলেই আছে — তাতে ক্ষতি নেই। তিনটি দলই essential (প্রতিটির নিজস্ব একটি ঘর আছে, যেমন ০, ৯, ২১), তাই এটিই ন্যূনতম। এই ফল আমরা Quine-McCluskey-র একটি script দিয়েও যাচাই করেছি; অংশ ৩-এর simulator-এ আপনি নিজেও একই পদ্ধতি দেখবেন।

৬ চলক আর তার পরে — চোখ কেন হার মানে

৬ চলকে ৬৪টি ঘর: চারটি ৪ চলকের map, AB = 00, 01, 11, 10 অনুযায়ী ২ × ২ ছকে বসানো। এখন একটি ঘরের প্রতিবেশী ৬টি — নিজের map-এ ৪টি, আর পাশের ও নিচের map-এ একই জায়গার দুটি। ১৬ বা ৩২ ঘরের দল চার map জুড়ে ছড়িয়ে থাকতে পারে। গবেষণাগারে কেউ কেউ এভাবে কাজ করেন, কিন্তু ভুলের সম্ভাবনা লাফিয়ে বাড়ে। ৭ চলকে ১২৮টি ঘর আর ৮টি map — কার্যত অসম্ভব।

আসল সমস্যা দুটি। (১) দেখা: n চলকে প্রতিটি ঘরের n-টি প্রতিবেশী; কাগজ দুই মাত্রার, তাই n > ৪ হলেই কিছু প্রতিবেশী কাগজে দূরে চলে যায়। (২) বাছা: সব বড় দল দেখতে পেলেও কোন কয়টি নিলে সবচেয়ে কম খরচে সব 1 ঢাকা পড়ে — এই সিদ্ধান্ত চোখে ভুল হয় সবচেয়ে বেশি। বাস্তব chip-এ একটি control logic-এর ২০–৩০টি input থাকা সাধারণ ব্যাপার। তাই দরকার এমন পদ্ধতি, যা কম্পিউটার চালাতে পারে — একটি algorithm.

২ · Quine-McCluskey — টেবিলে টেবিলে prime implicant

কয়েকটি সংজ্ঞা

• Literal: একটি চলক বা তার উল্টো রূপ — A বা A′.
• Product term: কয়েকটি literal-এর AND, যেমন B′C′; SOP হলো এমন পদের OR.
• Implicant: যে পদ 1 হলে F-ও 1 (বা don't care). K-map-এ শুধু 1 আর d ঘর নিয়ে বানানো যেকোনো বৈধ দল।
• Prime implicant (PI): যে implicant থেকে আর একটি literal-ও বাদ দেওয়া যায় না — বাদ দিলে কোনো 0 ঘর ঢুকে পড়ে। K-map-এ “আর বড় করা যায় না” এমন দল।

Binary রূপ আর dash চিহ্ন

QM-এ প্রতিটি পদকে লেখা হয় চলকের ক্রমে (A B C D) একটি সারি দিয়ে: 1 মানে চলকটি সরল রূপে আছে, 0 মানে উল্টো রূপে, আর – (dash) মানে চলকটি পদে নেই। যেমন -00- = B′C′ (A আর D নেই), আর 0--1 = A′D. দুটি সারি জোড়া লাগে কেবল যদি ঠিক একটি অবস্থানে একটির 0 আর অন্যটির 1 থাকে, আর বাকি সব অবস্থান হুবহু এক (dash-সহ) — তখন সেই অবস্থানে dash বসে। এটিই XY + XY′ = X, শুধু সংখ্যার ভাষায়।

পদ্ধতির ধাপ

1. সব minterm আর সব don't care binary-তে লিখুন, 1-এর সংখ্যা অনুযায়ী দলে (g0, g1, g2 …) সাজান।
2. শুধু পাশাপাশি দুই দল (gk আর gk+1) তুলনা করুন; এক বিটে আলাদা প্রতিটি জোড়া পরের টেবিলে লিখুন, আর দুটি সারিতেই ✓ দিন।
3. নতুন টেবিলেও একই কাজ (dash-এর অবস্থান মিলতে হবে)। একই পদ দুবার এলে একবার রাখুন।
4. যখন আর কিছু জোড়া লাগে না, তখন যে সারিতে ✓ পড়েনি, সেগুলোই prime implicant.
5. এরপর chart দিয়ে বাছাই (অংশ ৩) — সেখানে don't care-কে আর কলাম হিসেবে ধরা হয় না।

কেন এটি কাজ করে — ছোট প্রমাণ

কেন শুধু পাশের দল? দুটি সারি ঠিক একটি বিটে আলাদা হলে একটিতে 1-এর সংখ্যা অন্যটির চেয়ে ঠিক ১ বেশি। তাই g1-এর সাথে g3 মেলানোর চেষ্টা বৃথা — এতে কাজ অনেক কমে।

কেন সব PI পাওয়া যায়? k-টি dash-ওয়ালা যেকোনো implicant P নিন (K-map-এ ২^k ঘরের দল)। এর যেকোনো একটি dash-এর জায়গায় 0 আর 1 বসালে দুটি implicant পাওয়া যায়, যাদের প্রতিটিতে k − 1 dash, আর তারা ঠিক সেই এক বিটে আলাদা। Induction ধরে: k − 1 dash-ওয়ালা সব implicant ধাপ k − 1-এ টেবিলে আছে (ধাপ ০-এ সব minterm আর don't care তো আছেই), তাই ধাপ k-এ P নিশ্চয়ই তৈরি হয়। আর P-এ ✓ পড়ে না মানে কোনো বড় implicant P-কে ধারণ করে না — অর্থাৎ P prime.

কেন শুধু PI দিয়েই ন্যূনতম SOP? (Quine-এর একটি পরিচিত ফল) ধরুন কোনো ন্যূনতম SOP-এ একটি পদ Q prime নয়। তাহলে এমন একটি PI P আছে যা Q-কে ধারণ করে আর যার literal কম। Q-এর জায়গায় P বসালে F একই থাকে (P-ও implicant, তাই কোনো 0 ঘর 1 হয় না), সব ঘর ঢাকাও থাকে, কিন্তু literal কমে — অর্থাৎ আগেরটি ন্যূনতম ছিল না। তাই খোঁজার জায়গা শুধু PI-এর তালিকা।

পূর্ণ উদাহরণ: F(A, B, C, D) = Σm(0,1,2,5,6,7,8,9,10,14) + d(3,13)

Don't care ৩ আর ১৩ মানে — ধরুন একটি যন্ত্রে input 0011 আর 1101 কখনো আসে না; তাই সেখানে F কী হবে, তাতে কিছু যায় আসে না। টেবিলে তাদের রাখা হয়, যাতে বড় দল বানাতে সাহায্য করে।

টেবিল ১ (ধাপ ০): ১২টি সারি (১০টি minterm + ২টি don't care), 1-এর সংখ্যা ধরে দলে। প্রতিটিই পরে কোনো জোড়ায় গেছে, তাই সবগুলোতে ✓.

কীভাবে প্রথম টেবিল থেকে দ্বিতীয়টি আসে, ধাপে ধাপে দেখুন — “পরে” চাপুন:

g0: 0000(0)
g1: 0001(1)  0010(2)  1000(8)
g2: 0011(3d) 0101(5)  0110(6)  1001(9)  1010(10)
g3: 0111(7)  1101(13d) 1110(14)
compare only g0-g1, g1-g2, g2-g3

0000 + 0001 -> 000-  (0,1)
0000 + 0010 -> 00-0  (0,2)
0000 + 1000 -> -000  (0,8)
tick: 0, 1, 2, 8

1: 0001+0011 -> 00-1   0001+0101 -> 0-01
   0001+1001 -> -001   (0001 vs 0110: 3 bits, no)
2: 0010+0011 -> 001-   0010+0110 -> 0-10
   0010+1010 -> -010
8: 1000+1001 -> 100-   1000+1010 -> 10-0

0011+0111 -> 0-11   0101+0111 -> 01-1
0101+1101 -> -101   0110+0111 -> 011-
0110+1110 -> -110   1001+1101 -> 1-01
1010+1110 -> 1-10
(0011+1101: 3 bits differ, no)

000- (0,1) + 100- (8,9)   -> -00- (0,1,8,9)
-000 (0,8) + -001 (1,9)   -> -00-  (same, keep once)
00-0 (0,2) + 10-0 (8,10)  -> -0-0 (0,2,8,10)
0-10 (2,6) + 1-10 (10,14) -> --10 (2,6,10,14)
000- + 00-0 ?  dashes in different places -> no

stage 2: 00-- -00- -0-0 0--1 --01 0-1- --10
no two of them combine -> 7 prime implicants
00-- = A'B'   -00- = B'C'   -0-0 = B'D'
0--1 = A'D    --01 = C'D    0-1- = A'C
--10 = CD'

টেবিল ২ (ধাপ ১): ১৮টি সারি, প্রতিটিতে ✓ (সবাই ধাপ ২-এ গেছে)।

টেবিল ৩ (ধাপ ২): ৭টি আলাদা পদ, কোনোটিতে ✓ নেই — এরাই prime implicant.

৩ · Prime implicant chart — essential PI, dominance আর Petrick

এবার বাছাই। Prime implicant chart-এ সারিতে PI, কলামে শুধু আসল minterm (don't care ৩ আর ১৩ এখানে নেই — তাদের ঢাকতেই হবে এমন কোনো বাধ্যবাধকতা নেই)। কোনো PI কোনো minterm ঢাকলে সেখানে ×:

তিনটি নিয়ম

1. Essential PI: কোনো কলামে একটিমাত্র × থাকলে সেই PI ছাড়া ওই minterm ঢাকার আর উপায় নেই — যেকোনো সমাধানে এটি থাকবেই। এখানে কলাম ১৪-তে শুধু P7 (⊗)। তাই CD′ essential.
2. Column dominance: কলাম i-এর সব × যদি কলাম j-এরও থাকে (i-এর সেট ⊆ j-এর সেট), তবে i ঢাকলে j আপনিই ঢাকা পড়ে — j মুছে দিন।
3. Row dominance: সারি P যদি সারি Q-এর সব বাকি কলাম ঢাকে, আর P-এর খরচ Q-এর চেয়ে বেশি না হয়, তবে Q মুছে দিন — P নিলে কখনো খারাপ হয় না।

এই দুই dominance নিয়ম বারবার খাটালে নতুন করে “একটিমাত্র ×” কলাম তৈরি হয় — তাদের বলে secondary essential. পুরো প্রক্রিয়াটি দেখুন:

        0 1 2 5 6 7 8 9 10 14
P1 A'B' x x x
P2 B'C' x x       x x
P3 B'D' x   x     x   x
P4 A'D    x   x x
P5 C'D    x   x     x
P6 A'C      x   x x
P7 CD'      x   x     x  x   <- only x in 14

take P7 = CD'  -> covers 2, 6, 10, 14
remove those columns
left columns: 0 1 5 7 8 9
P1 A'B' : 0 1        P4 A'D : 1 5 7
P2 B'C' : 0 1 8 9    P5 C'D : 1 5 9
P3 B'D' : 0 8        P6 A'C : 7

col 8 = {P2, P3}  ⊆  col 0 = {P1, P2, P3}  -> drop col 0
col 5 = {P4, P5}  ⊆  col 1 = {P1, P2, P4, P5} -> drop col 1
left columns: 5 7 8 9

P1 A'B' : (none)        -> drop
P3 B'D' : 8    ⊆ P2 : 8 9  (same cost) -> drop
P6 A'C  : 7    ⊆ P4 : 5 7  (same cost) -> drop
left rows: P2 {8,9}  P4 {5,7}  P5 {5,9}

col 7 : only P4 -> take A'D  (covers 5, 7)
col 8 : only P2 -> take B'C' (covers 8, 9)
all columns covered; P5 not needed

F = CD' + B'C' + A'D
without don't cares the best was
F = CD' + B'C' + A'BD   (7 literals)
don't care 3 let A'BD grow into A'D

যখন সহজ নিয়ম থেমে যায় — cyclic chart আর Petrick

কিছু function-এ কোনো essential PI নেই, dominance-ও কিছু মোছে না — প্রতিটি কলামে দুটি ×, প্রতিটি সারিতে দুটি ×, একটি বৃত্তের মতো। একে বলে cyclic chart. পরিচিত উদাহরণ: F(A, B, C) = Σm(0,1,2,5,6,7), যার ৬টি PI: P1 = A′B′ (০, ১), P2 = A′C′ (০, ২), P3 = B′C (১, ৫), P4 = BC′ (২, ৬), P5 = AC (৫, ৭), P6 = AB (৬, ৭)।

১৯৫০-এর দশকে Stanley Petrick-এর নামে পরিচিত Petrick-এর পদ্ধতি এখানে বাছাইকেই একটি Boolean সমস্যা বানিয়ে ফেলে: Pi = 1 মানে “PI নম্বর i নেওয়া হলো”। প্রতিটি কলামের জন্য লিখুন “এদের অন্তত একটি নিতে হবে” (একটি OR), আর সব কলাম একসাথে সত্য হতে হবে (সবগুলোর AND). গুণ করে SOP বানালে প্রতিটি পদ একটি বৈধ cover; তার মধ্যে সবচেয়ে ছোটটি বেছে নিন।

          0 1 2 5 6 7
P1 A'B'   x x
P2 A'C'   x   x
P3 B'C      x   x
P4 BC'        x   x
P5 AC           x   x
P6 AB             x x
every column: exactly 2 x

col 0   1   2   5   6   7
P = (P1+P2)(P1+P3)(P2+P4)(P3+P5)(P4+P6)(P5+P6)
P = 1  <=>  every minterm is covered

(P1+P2)(P1+P3) = P1 + P2P3
(P4+P2)(P4+P6) = P4 + P2P6
(P5+P3)(P5+P6) = P5 + P3P6
P = (P1 + P2P3)(P4 + P2P6)(P5 + P3P6)

(P1 + P2P3)(P4 + P2P6)
= P1P4 + P1P2P6 + P2P3P4 + P2P3P6
                (P2P3 · P2P6 = P2P3P6)

x (P5 + P3P6):
P1P4P5 + P1P3P4P6 + P1P2P5P6 + P1P2P3P6
+ P2P3P4P5 + P2P3P4P6 + P2P3P5P6 + P2P3P6
P2P3P6 absorbs the three terms that contain it:
P = P1P4P5 + P2P3P6 + P1P2P5P6 + P1P3P4P6 + P2P3P4P5

P1P4P5 : F = A'B' + BC' + AC   (3 terms, 6 literals)
P2P3P6 : F = A'C' + B'C + AB   (3 terms, 6 literals)
the other three need 4 PIs
two different minimal answers - both correct

এবার পুরো পদ্ধতিটি যন্ত্রে চালিয়ে দেখুন। নিচের simulator প্রতিটি ধাপের টেবিল (g0, g1 … দলে), PI-এর তালিকা (* = essential), essential নেওয়ার পর বাকি minterm, Petrick-এর সব absorbed cover আর চূড়ান্ত F ছাপে। শেষে দুটি স্বাধীন যাচাই: পুরো truth table মিলিয়ে দেখা, আর সব সম্ভাব্য implicant (প্রতিটি চলক 0, 1 বা অনুপস্থিত — ৩ⁿটি পদ) থেকে brute force-এ সবচেয়ে কম কয়টি পদে F ঢাকা যায় তা বের করা। তিনটি function: মূল উদাহরণ, cyclic উদাহরণ, আর একই minterm কিন্তু ভিন্ন don't care d(13,15). Run চাপুন:

const bits = (m, n) => m.toString(2).padStart(n, "0"), range = k => [...Array(k).keys()];
const name = t => [...t].map((c, i) => c === "-" ? "" : "ABCD"[i] + (c === "0" ? "'" : "")).join("");
const hit = (t, m) => [...bits(m, t.length)].every((b, i) => t[i] === "-" || t[i] === b);
const cost = s => s.length * 100 + s.join("").replace(/-/g, "").length;   // terms first, then literals
function qm(n, ones, dc) {
  let cur = new Map([...ones, ...dc].sort((a, b) => a - b).map(m => [bits(m, n), [m]])), primes = [];
  for (let st = 0; cur.size; st++) {
    console.log(`stage ${st}`); for (const g of range(n + 1)) {
      const row = [...cur].filter(([t]) => t.split("1").length - 1 === g);
      if (row.length) console.log(`  g${g}: ` + row.map(([t, ms]) => ms + "=" + t).join("  ")); }
    const next = new Map(), used = new Set();
    for (const [a, ma] of cur) for (const [b, mb] of cur) {
      const d = range(n).filter(i => a[i] !== b[i]);                 // dashes must line up
      if (d.length !== 1 || a[d[0]] !== "0" || b[d[0]] !== "1") continue;
      next.set(a.slice(0, d[0]) + "-" + a.slice(d[0] + 1), [...ma, ...mb].sort((x, y) => x - y)); used.add(a).add(b);
    }
    primes.push(...[...cur.keys()].filter(t => !used.has(t))); cur = next;
  }
  const ess = primes.filter(p => ones.some(m => hit(p, m) && primes.filter(q => hit(q, m)).length === 1));
  for (const p of primes) console.log(`${ess.includes(p) ? "*" : " "} ${name(p).padEnd(6)} covers ${ones.filter(m => hit(p, m))}`);
  const left = ones.filter(m => !ess.some(p => hit(p, m))); let sums = [[]];   // Petrick: multiply out + absorb
  for (const m of left) sums = sums.flatMap(s => primes.filter(p => hit(p, m)).map(p => [...new Set([...s, p])]))
    .filter((s, i, all) => !all.some((o, j) => (o.length < s.length || j < i) && o.every(x => s.includes(x))));
  const cover = [...ess, ...sums.sort((a, b) => cost(a) - cost(b))[0]];
  console.log(`left [${left}]  Petrick: ${sums.map(s => s.map(name).join("+")).join(" | ") || "nothing left"}`);
  const ok = range(1 << n).every(m => dc.includes(m) || ones.includes(m) === cover.some(p => hit(p, m)));
  const imps = range(3 ** n).map(k => range(n).map(i => "01-"[Math.floor(k / 3 ** i) % 3]).join(""))
    .filter(t => range(1 << n).every(m => !hit(t, m) || ones.includes(m) || dc.includes(m)));
  const fits = (k, s = [], from = 0) => s.length === k ? ones.every(m => s.some(t => hit(t, m)))
    : imps.slice(from).some((t, i) => fits(k, [...s, t], from + i + 1));
  let k = 1; while (!fits(k)) k++;   // brute force: fewest product terms over ALL implicants
  console.log(`F = ${cover.map(name).join(" + ")}  truth table ${ok ? "OK" : "WRONG"}, brute-force minimum = ${k} terms\n`);
}
const F = [0, 1, 2, 5, 6, 7, 8, 9, 10, 14];
qm(4, F, [3, 13]);  qm(3, [0, 1, 2, 5, 6, 7], []);  qm(4, F, [13, 15]);

stage 0
  g0: 0=0000
  g1: 1=0001  2=0010  8=1000
  g2: 3=0011  5=0101  6=0110  9=1001  10=1010
  g3: 7=0111  13=1101  14=1110
stage 1
  g0: 0,1=000-  0,2=00-0  0,8=-000
  g1: 1,3=00-1  1,5=0-01  1,9=-001  2,3=001-  2,6=0-10  2,10=-010  8,9=100-  8,10=10-0
  g2: 3,7=0-11  5,7=01-1  5,13=-101  6,7=011-  6,14=-110  9,13=1-01  10,14=1-10
stage 2
  g0: 0,1,2,3=00--  0,1,8,9=-00-  0,2,8,10=-0-0
  g1: 1,3,5,7=0--1  1,5,9,13=--01  2,3,6,7=0-1-  2,6,10,14=--10
  A'B'   covers 0,1,2
  B'C'   covers 0,1,8,9
  B'D'   covers 0,2,8,10
  A'D    covers 1,5,7
  C'D    covers 1,5,9
  A'C    covers 2,6,7
* CD'    covers 2,6,10,14
left [0,1,5,7,8,9]  Petrick: B'C'+A'D | B'C'+C'D+A'C | B'D'+A'D+C'D | B'D'+C'D+A'C
F = CD' + B'C' + A'D  truth table OK, brute-force minimum = 3 terms

left [0,1,2,5,6,7]  Petrick: A'B'+BC'+AC | A'C'+B'C+AB | A'B'+A'C'+AC+AB | A'B'+BC'+B'C+AB | A'C'+B'C+BC'+AC
F = A'B' + BC' + AC  truth table OK, brute-force minimum = 3 terms

৪ · জটিলতা — কেন নিখুঁত উত্তর খোঁজা কঠিন

ছোট উদাহরণে QM ঝটপট চলে, কিন্তু চলক বাড়লে দুটি জায়গায় বিস্ফোরণ ঘটে।

(১) PI-এর সংখ্যা। n চলকে সম্ভাব্য product term ৩ⁿটি (প্রতিটি চলক 0, 1 বা –)। ধাপ k-এর টেবিলে সর্বোচ্চ C(n, k) · ২^n−kটি সারি থাকতে পারে, আর এমন function জানা আছে যাদের PI-এর সংখ্যা প্রায় ৩ⁿ/n-এর মাপে — অর্থাৎ চলকের সাথে exponential হারে বাড়ে। ২০ চলকে ৩^২০ প্রায় ৩৫০ কোটি। শুধু তালিকা বানাতেই কম্পিউটার হাঁপিয়ে ওঠে।

(২) বাছাই। PI chart-এর প্রশ্নটি আসলে একটি বিখ্যাত সমস্যা: কয়েকটি উপসেট (প্রতিটি PI = সে যে minterm-গুলো ঢাকে) থেকে সবচেয়ে কম খরচের কয়টি নিলে পুরো সেট (সব minterm) ঢাকা পড়ে — set cover. ১৯৭২ সালে Richard Karp-এর বিখ্যাত ২১টি NP-complete সমস্যার তালিকায় set cover ছিল, আর এর অনুকূলতম রূপটি NP-hard. উল্টো দিকেও সত্য: যেকোনো set cover সমস্যাকে একটি PI chart হিসেবে সাজানো যায় বলে দেখানো হয়েছে, তাই চার্টের সমস্যাটি সাধারণভাবেই কঠিন। Petrick-এর গুণফল নিজেই exponential বড় হতে পারে। এই তত্ত্ব বিস্তারিত আছে DSA কোর্সের P বনাম NP আর NP-hard সমস্যা বাস্তবে পর্বে।

বাস্তবের উত্তর: heuristic, আর চতুর data structure

• Greedy: বারবার সেই PI নেওয়া, যেটি সবচেয়ে বেশি না-ঢাকা minterm ঢাকে। Set cover-এ greedy কখনো সেরা উত্তরের প্রায় ln(m) গুণের বেশি খারাপ হয় না (m = minterm-এর সংখ্যা) — একটি প্রমাণিত সীমা। Greedy-র যুক্তি দেখতে পারেন DSA-র greedy পর্বে।
• Espresso: ১৯৮০-এর দশকের শুরুতে IBM আর UC Berkeley-র গবেষকদের (Robert Brayton প্রমুখ) কাজ বলে পরিচিত। এটি সব PI কখনো বানায় না। একটি cover নিয়ে শুরু করে তিনটি কাজ ঘুরে ঘুরে করে: EXPAND (প্রতিটি পদকে যতটা পারা যায় বড় করা, অর্থাৎ prime বানানো), IRREDUNDANT (অপ্রয়োজনীয় পদ ফেলে দেওয়া), আর REDUCE (পদ আবার ছোট করে নতুন দিকে বাড়ার সুযোগ তৈরি)। ফল প্রায় সবসময় ন্যূনতমের খুব কাছে, সময় অনেক কম। Berkeley-র এই প্রোগ্রাম বহু বছর শিক্ষা ও শিল্পে মানদণ্ড ছিল।
• BDD আর SAT: ১৯৮৬ সালে Randal Bryant-এর ordered BDD একটি function-কে সংকুচিত সিদ্ধান্ত-graph-এ রাখে — চলকের ক্রম ঠিক থাকলে একই function-এর রূপ অনন্য, তাই দুটি circuit সমান কি না প্রায় সঙ্গে সঙ্গে বলা যায়। ১৯৯০-এর দশকে লাখ লাখ PI-কে তালিকা না বানিয়ে BDD-র ভেতরে “implicitly” রেখে নিখুঁত minimizer বানানো হয়। আর আধুনিক SAT solver আজ synthesis আর equivalence checking-এর প্রধান হাতিয়ার।

৫ · Multiple-output minimisation — product term ভাগাভাগি

বাস্তব circuit-এ একই input থেকে প্রায়ই কয়েকটি output বের হয় — যেমন একটি decoder বা ALU-এর control. প্রতিটি output আলাদাভাবে সরল করলে প্রতিটির জন্য ন্যূনতম SOP আসে, কিন্তু মোট circuit ন্যূনতম না-ও হতে পারে। কারণ একটি AND gate (একটি product term) একবার বানিয়ে একাধিক OR gate-এ জুড়ে দেওয়া যায়। একে বলে multiple-output minimisation.

উদাহরণ: f1(A, B, C) = Σm(2,3,7) আর f2(A, B, C) = Σm(4,5,7).

• আলাদাভাবে: f1 = A′B + BC, f2 = AB′ + AC. মোট ৪টি আলাদা product term, AND gate-এর মোট input ৮টি।
• একসাথে: minterm ৭ (ABC) দুটি function-এই আছে। f1 = A′B + ABC, f2 = AB′ + ABC — ABC একবার বানিয়ে দুই জায়গায় ব্যবহার। মোট ৩টি product term, AND input ৭টি।

মজার ব্যাপার, ABC কোনো function-এরই prime implicant নয় (f1-এ এটি BC-র ভেতরে, f2-এ AC-র ভেতরে)। তাই multiple-output-এর তত্ত্বে খোঁজার জায়গা বড়: প্রতিটি function-এর PI-এর সাথে function-গুলোর AND-এর (এখানে f1 · f2 = m₇ = ABC) PI-ও প্রার্থী — এদের বলে multiple-output prime implicant. QM-এর টেবিলে প্রতিটি সারির সাথে “কোন কোন output-এ আছে” একটি tag রেখে এটি করা যায়।

এই ভাগাভাগির প্রাকৃতিক ঘর হলো PLA (Programmable Logic Array): একটি AND-তল (প্রতিটি সারি একটি product term) আর একটি OR-তল (প্রতিটি output কোন কোন সারি নেবে)। PLA-র আকার মোটামুটি সারির সংখ্যার সমানুপাতিক, তাই এখানে লক্ষ্য হলো মোট আলাদা product term কমানো — প্রতিটি output-এর literal নয়। ১৯৭০-৮০-এর দশকে chip-এর control logic আর পরে PAL/CPLD নামের প্রোগ্রামযোগ্য chip এই কাঠামো ব্যবহার করত, আর Espresso মূলত এমন PLA-র জন্যই বানানো হয়েছিল। নিচের simulator দুই ভাবেই brute force-এ সেরা উত্তর খোঁজে:

// Two outputs of A,B,C: minimise separately vs jointly (shared product terms), by brute force
const f1 = [2, 3, 7], f2 = [4, 5, 7], n = 3, range = k => [...Array(k).keys()];
const terms = range(3 ** n).map(k => range(n).map(i => "01-"[Math.floor(k / 3 ** i) % 3]).join(""));
const hit = (t, m) => [...m.toString(2).padStart(n, "0")].every((b, i) => t[i] === "-" || t[i] === b);
const name = t => [...t].map((c, i) => c === "-" ? "" : "ABC"[i] + (c === "0" ? "'" : "")).join("");
const lits = s => s.join("").replace(/-/g, "").length;
const isImp = (t, f) => range(1 << n).every(m => !hit(t, m) || f.includes(m));
const covers = (s, f) => f.every(m => s.some(t => isImp(t, f) && hit(t, m)));
function best(ok) {                      // smallest set of terms (then fewest literals) with ok(set)
  for (let k = 1; k <= 4; k++) {
    let found = null;
    const go = (s, from) => {
      if (s.length === k) { if (ok(s) && (!found || lits(s) < lits(found))) found = s; return; }
      for (let i = from; i < terms.length; i++) go([...s, terms[i]], i + 1);
    };
    go([], 0);
    if (found) return found;
  }
}
const s1 = best(s => covers(s, f1) && s.every(t => isImp(t, f1)));
const s2 = best(s => covers(s, f2) && s.every(t => isImp(t, f2)));
const sep = [...new Set([...s1, ...s2])];
console.log(`separate: f1 = ${s1.map(name).join(" + ")}   f2 = ${s2.map(name).join(" + ")}`);
console.log(`          distinct product terms = ${sep.length}, AND-gate inputs = ${lits(sep)}`);
const joint = best(s => covers(s, f1) && covers(s, f2));
const use = f => joint.filter(t => isImp(t, f));
console.log(`joint:    f1 = ${use(f1).map(name).join(" + ")}   f2 = ${use(f2).map(name).join(" + ")}`);
console.log(`          distinct product terms = ${joint.length}, AND-gate inputs = ${lits(joint)}\n`);
console.log("PLA table (joint)   A B C | f1 f2");
for (const t of joint)
  console.log(`  ${name(t).padEnd(16)}  ${[...t].join(" ")} |  ${isImp(t, f1) ? 1 : "."}  ${isImp(t, f2) ? 1 : "."}`);

separate: f1 = BC + A'B   f2 = AC + AB'
          distinct product terms = 4, AND-gate inputs = 8
joint:    f1 = ABC + A'B   f2 = ABC + AB'
          distinct product terms = 3, AND-gate inputs = 7

PLA table (joint)   A B C | f1 f2
  ABC               1 1 1 |  1  1
  AB'               1 0 - |  .  1
  A'B               0 1 - |  1  .

৬ · Multi-level logic — factoring, area বনাম delay

এখন পর্যন্ত লক্ষ্য ছিল দুই স্তরের (AND তারপর OR) ন্যূনতম SOP. কিন্তু আসল chip-এ দুই স্তরে থাকার কোনো বাধ্যবাধকতা নেই। সাধারণ অংশ বের করে আনলে — factoring — অনেক কম gate লাগে:

বাঁ দিকে দুটি AND আর একটি OR (৬টি gate-input), ডান দিকে একটি OR আর একটি AND (৪টি)। এভাবে বহু-স্তরের circuit-কে বলে multi-level logic. দুটি উদাহরণ মিলিয়ে দেখুন (gate-input = সব gate-এর input-এর যোগফল, area-র একটি মোটা মাপ; স্তর = input থেকে output পর্যন্ত সবচেয়ে বেশি কয়টি gate, inverter বাদে):

প্রথম জোড়ায় area কমল (১১ → ৮), কিন্তু signal-কে এখন ২-এর বদলে ৪টি gate পার হতে হয় — delay বাড়ল। এটিই area–delay trade-off: কম gate মানে কম জায়গা ও কম power, কিন্তু বেশি স্তর মানে ধীর। দ্বিতীয় জোড়ায় factoring ছাড়া আর কোনো দাম দিতে হয়নি — ৩২ থেকে ৯, স্তর একই। তাই synthesis tool সাধারণত আগে area কমাতে factoring করে, তারপর যে path সবচেয়ে ধীর (critical path, পর্ব ১৮) শুধু সেখানে আবার স্তর কমায়।

আরেকটি বাস্তব কথা: CMOS-এ (পর্ব ০৮-এর logic gate আর transistor) ৮-input-এর OR একটি gate নয়। বেশি input-এর gate-এ transistor সিরিজে জুড়তে হয়, যা ধীর; সাধারণত ৩–৪ input-এর বেশি হলে gate ভেঙে গাছের মতো সাজাতে হয়। তাই “দুই স্তরের” SOP-ও আসলে chip-এ প্রায়ই বহু স্তরের।

Technology mapping — আসল gate দিয়ে ঢাকা

Factoring-এর পরে circuit থাকে একটি আদর্শ AND/OR/NOT-এর জালে। কিন্তু কারখানা দেয় একটি নির্দিষ্ট standard cell library: INV, NAND2, NOR2, NAND3, AOI21 (AND-OR-Invert: (AB + C)′ একটি cell-এ), OAI21, XOR2, flip-flop — প্রতিটির মাপা area আর delay সহ। Technology mapping হলো সেই জালকে এই cell-গুলো দিয়ে এমনভাবে ঢাকা, যাতে মোট area বা delay সবচেয়ে কম হয় — অনেকটা জিগস পাজলের মতো, আর জাল গাছের মতো হলে dynamic programming দিয়ে নিখুঁত করা যায়। CMOS-এ NAND আর NOR স্বাভাবিক (পর্ব ০৮), তাই SOP প্রায়ই NAND–NAND রূপে বসে।

FPGA-তে খেলা আলাদা। সেখানে মূল ব্লক একটি k-input LUT (সাধারণত ৪ থেকে ৬ input), যা যেকোনো k-input function-কে সমান খরচে বানায় — XOR হোক বা AND. ফলে literal গোনার অর্থ থাকে না; লক্ষ্য হয় LUT-এর সংখ্যা আর LUT-এর স্তর কমানো।

৭ · Hazard — যুক্তিতে ঠিক, সময়ে ভুল

Boolean algebra সময় জানে না। কিন্তু প্রতিটি আসল gate-এর output বদলাতে একটু সময় লাগে — propagation delay (পর্ব ০৮-এ পরিচয়, পর্ব ১৮-এ বিস্তারিত)। একটি input বদলালে তার খবর বিভিন্ন পথে বিভিন্ন সময়ে output-এ পৌঁছায়। ফলে যে output স্থির থাকার কথা, সেটিও মুহূর্তের জন্য উল্টে যেতে পারে — একটি glitch. এমন সম্ভাবনাকে বলে hazard.

Static-1 hazard: F = AB′ + BC

ধরুন A = 1, C = 1 স্থির, আর B বদলায়। B = 1 হলে BC = 1, তাই F = 1; B = 0 হলে AB′ = 1, তাই F = 1. যুক্তিতে F সবসময় 1. কিন্তু B′ বানাতে একটি inverter লাগে, তাই AB′ পথটি BC পথের চেয়ে এক gate লম্বা। B যখন 1 থেকে 0 হয়, BC আগে বন্ধ হয়, AB′ পরে চালু হয় — মাঝের ফাঁকে F এক মুহূর্ত 0. একে বলে static-1 hazard: output 1-এ থাকার কথা, তবু 1 → 0 → 1 লাফ। প্রতিটি gate (inverter-সহ) ১ একক সময় নেয় ধরে ঘটনাগুলো দেখুন:

A=1 C=1 B=1
B'  = 0
AB' = 0
BC  = 1
F   = AB' + BC = 1

B   = 0   (input changes now)
B'  = 0   (inverter has not reacted yet)
AB' = 0
BC  = 1   (AND has not reacted yet)
F   = 1

B'  = 1   (inverter saw B=0 at t=1)
BC  = 0   (AND saw B=0 at t=1)
AB' = 0   (its input B' was still 0 at t=1)
F   = 1   (OR saw AB'=0, BC=1 at t=1)

AB' = 1   (saw B'=1 at t=2)
F   = AB'(t=2) + BC(t=2) = 0 + 0 = 0
F : ‾‾‾‾‾‾__‾‾
t : 0 1 2 3 4

F = AB'(t=3) + BC(t=3) = 1 + 0 = 1
glitch width = 1 time unit
             = the extra inverter delay on the AB' path

K-map (A,B,C):      BC=00 01 11 10
               A=0     0  0  1  0
               A=1     1 [1  1] 0
                         m5 m7  <- AC joins them
F = AB' + BC + AC ; A=C=1 -> AC = 1 all the time
F stays 1 through the whole change

কেন consensus পদ “বিনা খরচে” যুক্তি বদলায় না

Consensus theorem বলে: XY + X′Z + YZ = XY + X′Z. প্রমাণ: YZ = YZ(X + X′) = XYZ + X′YZ. প্রথম অংশ XY-এর ভেতরে (XY + XYZ = XY), দ্বিতীয়টি X′Z-এর ভেতরে — তাই YZ যুক্তির দিক থেকে বাড়তি। এখানে X = B, Y = C, Z = A ধরলে BC + B′A + CA = BC + AB′. অর্থাৎ AC যোগ করলে F-এর truth table একটুও বদলায় না, শুধু সময়ের আচরণ বদলায়। K-map ন্যূনতম করার সময় আমরা এই পদটিই “অপ্রয়োজনীয়” বলে বাদ দিয়েছিলাম!

সাধারণ নিয়ম (দুই স্তরের SOP, এক সময়ে একটি input বদলায়): static-1 hazard থাকে যদি এবং কেবল যদি K-map-এ এমন দুটি পাশাপাশি 1 থাকে, যাদের কোনো একটি পদ একসাথে ঢাকে না। যুক্তি: দুটি ঘর একই পদ P-এর ভেতরে থাকলে P বদলানো চলকের ওপর নির্ভর করে না, তাই পুরো পরিবর্তনে P = 1 থাকে আর OR-ও 1 থাকে। আর না থাকলে প্রথম ঘরের পদগুলোতে বদলানো চলকটি এক রূপে, দ্বিতীয়টির পদগুলোতে অন্য রূপে আছে — delay অসমান হলে প্রথমটি বন্ধ হয়ে দ্বিতীয়টি চালু হওয়ার আগে ফাঁক তৈরি হতে পারে। সমাধান: প্রতিটি এমন জোড়ার জন্য একটি বাড়তি দল। সবচেয়ে নিরাপদ পথ — সব prime implicant রেখে দেওয়া; সেই SOP-এ এমন কোনো ফাঁক থাকে না।

নিচের simulator একই circuit-কে সময়-ধাপে চালায়: প্রতিটি signal-এর পরের মান = তার gate-এর function, আগের মুহূর্তের input দিয়ে (প্রতি gate ১ একক delay). তিনটি পরীক্ষা: B পড়ে যাওয়া, B ওঠা, আর consensus পদ যোগ করে আবার B পড়া। Run চাপুন:

// Unit-delay simulation of F = AB' + BC (+ AC): every gate, the inverter too, takes 1 time unit
function simulate(withConsensus, bBefore, bAfter, T = 8) {
  const A = 1, C = 1, B = t => (t < 1 ? bBefore : bAfter);         // B switches at t = 1
  // steady state before the change: each signal settled for the old B
  let s = { nB: 1 - bBefore, AnB: A & (1 - bBefore), BC: bBefore & C, AC: A & C };
  s.F = s.AnB | s.BC | (withConsensus ? s.AC : 0);
  const wave = { "B": [], "B'": [], "AB'": [], "BC": [], "AC": [], "F": [] };
  for (let t = 0; t < T; t++) {
    const b = B(t);
    wave["B"].push(b); wave["B'"].push(s.nB); wave["AB'"].push(s.AnB);
    wave["BC"].push(s.BC); wave["AC"].push(s.AC); wave["F"].push(s.F);
    s = {                                    // value at t+1 = gate function of values at t
      nB: 1 - b,
      AnB: A & s.nB,
      BC: b & C,
      AC: A & C,
      F: s.AnB | s.BC | (withConsensus ? s.AC : 0),
    };
  }
  return wave;
}
const draw = v => v.map(x => (x ? "‾‾" : "__")).join("");
for (const [title, cons, b0, b1] of [
  ["F = AB' + BC,  B falls 1->0", false, 1, 0],
  ["F = AB' + BC,  B rises 0->1", false, 0, 1],
  ["F = AB' + BC + AC,  B falls 1->0", true, 1, 0]]) {
  const w = simulate(cons, b0, b1);
  console.log(`${title}   (A = 1, C = 1)\nt     ${[...Array(8).keys()].map(t => String(t).padEnd(2)).join("")}`);
  for (const [sig, v] of Object.entries(w)) if (cons || sig !== "AC") console.log(`${sig.padEnd(5)} ${draw(v)}   ${v.join("")}`);
  const glitch = w.F.some((x, t) => t > 0 && t < 7 && !x && w.F[t - 1] && w.F.slice(t).includes(1));
  console.log(`=> F ${glitch ? "GLITCHES (static-1 hazard)" : "stays 1, no glitch"}\n`);
}

F = AB' + BC,  B falls 1->0   (A = 1, C = 1)
t     0 1 2 3 4 5 6 7 
B     ‾‾______________   10000000
B'    ____‾‾‾‾‾‾‾‾‾‾‾‾   00111111
AB'   ______‾‾‾‾‾‾‾‾‾‾   00011111
BC    ‾‾‾‾____________   11000000
F     ‾‾‾‾‾‾__‾‾‾‾‾‾‾‾   11101111
=> F GLITCHES (static-1 hazard)

F = AB' + BC,  B rises 0->1   (A = 1, C = 1)
t     0 1 2 3 4 5 6 7 
B     __‾‾‾‾‾‾‾‾‾‾‾‾‾‾   01111111
B'    ‾‾‾‾____________   11000000
AB'   ‾‾‾‾‾‾__________   11100000
BC    ____‾‾‾‾‾‾‾‾‾‾‾‾   00111111
F     ‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾   11111111
=> F stays 1, no glitch

F = AB' + BC + AC,  B falls 1->0   (A = 1, C = 1)
t     0 1 2 3 4 5 6 7 
B     ‾‾______________   10000000
B'    ____‾‾‾‾‾‾‾‾‾‾‾‾   00111111
AB'   ______‾‾‾‾‾‾‾‾‾‾   00011111
BC    ‾‾‾‾____________   11000000
AC    ‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾   11111111
F     ‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾   11111111
=> F stays 1, no glitch

Static-0 আর dynamic hazard

Static-0 hazard হলো উল্টো ছবি: output 0-তে থাকার কথা, কিন্তু 0 → 1 → 0. এটি স্বাভাবিকভাবে POS (OR-AND) circuit-এ দেখা যায়। যেমন F = (A + B)(B′ + C), A = 0, C = 0 স্থির, আর B বদলালে দুই বন্ধনীর একটি দেরিতে 0 হয়ে মুহূর্তের জন্য দুটিই 1 থাকতে পারে। সমাধানও দ্বৈত: consensus বন্ধনী (A + C) গুণ করা। আর যে SOP-এ কোনো পদে একই চলকের দুই রূপ (যেমন BB′) নেই, তাতে এক input-এর পরিবর্তনে static-0 hazard হয় না — কারণ F = 0 থাকা অবস্থায় কোনো AND পদ এক মুহূর্তের জন্যও 1 হতে পারে না।

Dynamic hazard: output একবার বদলানোর কথা (0 → 1), কিন্তু কয়েকবার লাফায় (0 → 1 → 0 → 1). এর জন্য একই input থেকে output পর্যন্ত অন্তত তিনটি আলাদা দৈর্ঘ্যের পথ লাগে, তাই এটি সাধারণত বহু-স্তরের circuit-এ ঘটে। পাঠ্যবইয়ের একটি পরিচিত ফল: দুই স্তরের SOP থেকে সব static-1 hazard সরালে এক input-এর পরিবর্তনে static-0 বা dynamic hazard-ও থাকে না। তবে একাধিক input একসাথে বদলালে (function hazard) কোনো বাড়তি পদই নিশ্চয়তা দিতে পারে না।

কখন hazard সত্যিই বিপদ

আজকের প্রায় সব processor synchronous: combinational logic-এর output ধরে রাখে flip-flop (পর্ব ১৫), আর সে মান নেয় শুধু clock-এর edge-এ। Clock-এর সময়কাল এমনভাবে ঠিক করা হয়, যাতে সবচেয়ে ধীর পথও তার আগে স্থির হয়ে যায় (পর্ব ১৮-এর timing আর clock). মাঝখানের glitch তাই কেউ দেখে না — রেলস্টেশনের সিগন্যাল-ঘরে কর্মী যেমন শুধু ট্রেন ছাড়ার নির্দিষ্ট মুহূর্তে সিগন্যাল দেখেন, মাঝের ঝিলিক নয়।

কিন্তু কয়েকটি জায়গায় glitch সরাসরি ভুল ঘটায়:

• Asynchronous circuit আর asynchronous FSM — এখানে প্রতিটি পরিবর্তনই “ঘটনা”, তাই একটি glitch ভুল state-এ পাঠাতে পারে।
• flip-flop-এর asynchronous reset বা set লাইনে combinational logic — একটি glitch-ই পুরো register মুছে দিতে পারে।
• clock নিজে যদি logic দিয়ে বানানো হয় (যেমন হাতে বানানো clock gating) — glitch মানে বাড়তি clock edge.
• chip-এর বাইরের pin, যা অন্য সিস্টেমের interrupt বা strobe হিসেবে ব্যবহৃত।

আর synchronous circuit-এও glitch-এর একটি নীরব দাম আছে: প্রতিটি অপ্রয়োজনীয় 0 → 1 → 0 লাফ capacitor চার্জ-ডিসচার্জ করে, অর্থাৎ dynamic power খরচ (পর্ব ০২-এ দেখা power wall-এর একটি ছোট উৎস)।

৮ · আজকের বাস্তবতা — synthesis tool সব করে, তবু বুঝতে হয়

আজ কোনো chip-প্রকৌশলী হাতে QM চালিয়ে circuit বানান না। নকশা লেখা হয় Verilog-এর মতো hardware description language-এ (পর্ব ১৪-এর HDL আর Verilog), আর logic synthesis tool বাকিটা করে: নকশাকে Boolean জালে রূপান্তর, two-level আর multi-level সরলীকরণ, don't care কাজে লাগানো, technology mapping, তারপর timing দেখে আবার উন্নতি। উন্মুক্ত দুনিয়ায় পরিচিত জুটি Yosys (২০১০-এর দশকে Claire Wolf-এর শুরু করা open-source synthesis suite) আর ABC (UC Berkeley-র logic synthesis ও verification system, Alan Mishchenko-র নেতৃত্বে বলে পরিচিত)। শিল্পে Synopsys, Cadence-এর মতো কোম্পানির বাণিজ্যিক tool প্রচলিত। ABC ভেতরে circuit-কে AND-Inverter Graph (শুধু ২-input AND আর inverter-এর জাল) হিসেবে রেখে হাজার হাজার ছোট ছোট rewrite চালায়।

তাহলে এই পর্ব কেন শিখলেন? কারণ tool-এর ফল বুঝতে, বিশ্বাস করতে আর দরকারে আটকাতে হয়। একটি উদাহরণ — hazard-মুক্ত করার জন্য আপনি consensus পদ লিখলেন:

module f_hazard_free (
    input  wire a, b, c,
    output wire f
);
    // a&c is logically redundant (consensus of a&~b and b&c)
    assign f = (a & ~b) | (b & c) | (a & c);
endmodule

// Yosys script (example):  read_verilog f.v
//                          synth -top f_hazard_free
//                          stat

Synthesis tool-এর লক্ষ্য area আর delay, hazard নয়। a & c যুক্তিতে বাড়তি, তাই optimizer সাধারণত সেটি মুছে দিতে পারে — আপনার hazard-সমাধান নিঃশব্দে উধাও। asynchronous নকশায় তাই প্রকৌশলীরা বিশেষ নিয়ম মানেন: tool-কে নির্দিষ্ট অংশ ছুঁতে না দেওয়ার attribute বা constraint (tool-ভেদে নাম আলাদা), হাতে বসানো library cell, আর synthesis-এর পরে netlist আবার পরীক্ষা। আবার উল্টো দিকে, Verilog-এ কোনো output-কে 'x দিলে অনেক synthesis tool সেটিকে don't care হিসেবে ব্যবহার করে ছোট circuit বানায় — কিন্তু simulation-এ সেই x অন্যভাবে ছড়ায়; দুটির পার্থক্য না বুঝলে simulation আর chip আলাদা আচরণ করতে পারে।

প্রকৌশলীর রোজকার কাজগুলো তাই এমন: synthesis report-এ area, cell-এর সংখ্যা আর logic depth পড়া; কেন একটি path এত গভীর হলো বোঝা; tool-এর ফল মূল নকশার সমান কি না equivalence checking (BDD/SAT দিয়ে) চালিয়ে নিশ্চিত হওয়া; আর timing ভাঙলে নকশা নতুন করে সাজানো।

৯ · AI-এর যুগে — সরলীকরণের উত্তর যাচাই

Logic minimization-এ AI chatbot-এর উত্তর প্রায়ই প্রথম দেখায় বিশ্বাসযোগ্য, কিন্তু এখানে ভুল ধরা খুব সহজ — কারণ প্রতিটি দাবি একটি truth table-এ যাচাই করা যায়। ১৬ বা ৩২টি সারি মিলিয়ে দেখতে একটি script-এর কয়েক মিলিসেকেন্ড লাগে।

AI-এর উত্তর হাতে পেলে — যাচাইয়ের চেকলিস্ট

• চূড়ান্ত SOP প্রতিটি care-input-এ মূল function-এর সাথে মিলেছে (script বা হাতে truth table)
• প্রতিটি পদ সত্যিই implicant — কোনো 0 ঘর ঢাকে না — আর প্রতিটি PI আর বড় করা যায় না
• PI chart-এ don't care কলাম নেই, আর essential PI নিজে গুনে মিলিয়েছি
• “ন্যূনতম” দাবিটি brute force বা Petrick দিয়ে নিশ্চিত করেছি, আর বিকল্প ন্যূনতম উত্তর আছে কি না দেখেছি
• hazard-এর দাবি সময়-ধাপের simulation-এ (বা waveform viewer-এ) দেখে নিয়েছি; HDL কোড synthesizable কি না আর synthesis-এর পর consensus পদ টিকে আছে কি না যাচাই করেছি