K-map দিয়ে সরলীকরণ — ২ থেকে ৪ চলক, don't care

১ · কেন সরলীকরণ — কম literal মানে কম gate, কম খরচ

পর্ব ০৭-এ দেখেছেন, যেকোনো truth table থেকে সরাসরি একটি রাশি লেখা যায়: যে সারিতে আউটপুট 1, সেই সারির minterm লিখে সবগুলো OR করে দিলেই হলো। এই রূপকে বলে canonical SOP (sum of products). রাশিটি সবসময় সঠিক — কিন্তু প্রায়ই অনেক বড়।

একটি উদাহরণ নিন। চার চলকের (A, B, C, D; A হলো সবচেয়ে বাঁয়ের বিট) একটি Boolean function F = Σm(0, 1, 2, 5, 8, 9, 10) — অর্থাৎ সারি ০, ১, ২, ৫, ৮, ৯ আর ১০-এ আউটপুট 1. Canonical রূপে এখানে ৭টি minterm, প্রতিটিতে ৪টি করে literal (চলক বা তার উল্টো রূপ): মোট ২৮টি literal, ৭টি চার-ইনপুটের AND gate আর একটি সাত-ইনপুটের OR gate. এই পর্বের শেষে একই function দাঁড়াবে B′D′ + B′C′ + A′C′D — মাত্র ৭টি literal, তিনটি ছোট AND আর একটি তিন-ইনপুটের OR.

খরচ মাপার একক

বাস্তব chip-এ “ছোট রাশি” মানে কী? দুই স্তরের (two-level) AND-OR circuit-এ মোটামুটি এই হিসাব চলে:

এই পর্বে “minimal” বলতে প্রচলিত পাঠ্যবইয়ের সংজ্ঞা নেব: প্রথমে term সবচেয়ে কম, তারপর literal সবচেয়ে কম — দুই স্তরের SOP বা POS-এর মধ্যে। ওপরের উদাহরণে canonical রূপ ৭ term ২৮ literal, minimal রূপ ৩ term ৭ literal. NAND দিয়ে বানালে (পর্ব ০৮), complement করা ইনপুট আগে থেকেই আছে ধরে নিয়ে মোটামুটি হিসাব: canonical রূপে ৭টি চার-ইনপুটের NAND (৫৬ transistor) আর একটি সাত-ইনপুটের NAND (১৪ transistor) — প্রায় ৭০টি; minimal রূপে (২ + ২ + ৩) × ২ = ১৪ আর তিন-ইনপুটের NAND-এ ৬ — প্রায় ২০টি। একটি ছোট function-এই সাড়ে তিন গুণ পার্থক্য।

পর্ব ০৭-এর Boolean algebra-র সূত্র দিয়েও একই কাজ করা যায়। কিন্তু algebra-য় দুটি সমস্যা: কোন সূত্র কোন ক্রমে লাগাবেন তার কোনো নির্দিষ্ট নিয়ম নেই, আর শেষে পৌঁছে জানা যায় না যে আরও ছোট করা সম্ভব কি না। K-map চার চলক পর্যন্ত দুটি সমস্যাই মিটিয়ে দেয় — চোখের সামনে সব সম্ভাব্য দল দেখা যায়, আর একটি পদ্ধতি মানলে minimal উত্তর নিশ্চিত।

২ · K-map-এর মূল ধারণা — পাশাপাশি ঘর, Gray ক্রম আর torus

সরলীকরণের প্রায় পুরোটাই দাঁড়িয়ে আছে একটি ছোট সূত্রের ওপর, যাকে বলে combining theorem:

অর্থাৎ দুটি product term যদি ঠিক একটি চলকে আলাদা হয় — একটিতে Y, অন্যটিতে Y′, বাকি সব হুবহু এক — তাহলে দুটি মিলে একটি term হয়, আর সেই চলকটি বাদ পড়ে। যেমন A′B′C′D′ (m₀) + A′B′C′D (m₁) = A′B′C′. এমন দুটি minterm-কে বলে logically adjacent (যৌক্তিকভাবে পাশাপাশি)। Binary নকশায় এর মানে তাদের Hamming distance ১।

সমস্যা হলো, truth table-এ এই “পাশাপাশি” সারিগুলো পাশাপাশি থাকে না। ৪ চলকে m₀ (0000)-এর পাশাপাশি minterm চারটি: m₁, m₂, m₄ আর m₈ — truth table-এ ছড়িয়ে আছে সারি ১, ২, ৪ আর ৮-এ। Karnaugh map (K-map)-এর বুদ্ধি হলো truth table-এর ঘরগুলোকে একটি ছকে এমনভাবে সাজানো যাতে যৌক্তিক পাশাপাশি = কাগজে পাশাপাশি।

কেন 00, 01, 11, 10 — সাধারণ ক্রম কেন নয়

দুটি চলক (ধরুন C আর D) দিয়ে কলাম বানাতে হলে চারটি কলাম লাগে। সাধারণ গণনার ক্রমে লিখলে 00, 01, 10, 11 — কিন্তু 01 থেকে 10-এ যেতে দুটি বিটই বদলায়। তখন কাগজে পাশাপাশি দুটি ঘর যৌক্তিকভাবে পাশাপাশি নয়, আর উল্টোভাবে 01 আর 11 যৌক্তিকভাবে পাশাপাশি হলেও কাগজে দূরে। সমাধান হলো Gray code-এর ক্রম: 00, 01, 11, 10 — প্রতি ধাপে ঠিক একটি বিট বদলায় (পর্ব ০৪-এর Gray code অংশে এর নিয়ম দেখেছেন)। আর এই ক্রমের একটি বিশেষ গুণ আছে: শেষ 10 থেকে আবার প্রথম 00-তে ফিরতেও মাত্র একটি বিট বদলায়। Gray code চক্রাকার।

ফলাফল: সবচেয়ে ডানের কলাম সবচেয়ে বাঁয়ের কলামের পাশাপাশি, আর সবচেয়ে নিচের সারি সবচেয়ে ওপরের সারির পাশাপাশি। কাগজটিকে প্রথমে নল বানিয়ে ডান-বাঁ কিনারা জুড়ে দিন, তারপর নলটিকে বাঁকিয়ে ওপর-নিচ জুড়ে দিন — পাবেন একটি ডোনাট, গণিতের ভাষায় torus. চার চলকের K-map আসলে একটি torus, যাকে কেটে সমান করে কাগজে বিছানো হয়েছে। এ কারণেই চারটি কোণের ঘর একে অপরের পাশাপাশি — যা প্রথমবার দেখলে অদ্ভুত লাগে।

৩ · ২, ৩ আর ৪ চলকের map — ঘরের নম্বর, দলের নিয়ম আর দল পড়া

K-map-এ প্রতিটি ঘর truth table-এর একটি সারি। নিচের ছকগুলোতে প্রতিটি ঘরে লেখা আছে সেটি কোন minterm. সারির চলকগুলো বাঁয়ে, কলামের চলকগুলো ওপরে, আর দুটোই Gray ক্রমে। Minterm-এর নম্বর = (সারির বিট)(কলামের বিট) একসাথে binary হিসেবে পড়লে যা হয়।

২ চলক (A, B) — ৪টি ঘর

৩ চলক (A | BC) — ৮টি ঘর

৪ চলক (AB | CD) — ১৬টি ঘর

মনে রাখার কৌশল: প্রতিটি সারিতে সংখ্যাগুলো “০ ১ ৩ ২” ছাঁচে চলে — শেষ দুটি অদলবদল। আর সারিগুলোও একই ছাঁচে: ওপরে ০–৩, তারপর ৪–৭, তারপর ১২–১৫, শেষে ৮–১১. পরীক্ষার খাতায় সবচেয়ে বেশি ভুল হয় এখানেই — m₂ আর m₃, বা ৮–১১ আর ১২–১৫-এর সারি অদলবদল হয়ে যায়। Map ভরার আগে প্রতিবার ছোট করে ঘরের নম্বর লিখে নিন।

দল বানানোর নিয়ম

1. আকার ২-এর ঘাত: ১, ২, ৪, ৮ বা ১৬টি ঘর (অংশ ২-এর প্রমাণ)। ৩, ৫, ৬ চলে না।
2. আয়তাকার: ১×২, ২×২, ১×৪, ২×৪, ৪×৪ — সারি বা কলাম ধরে, কোনাকুনি কখনো নয়। কোনাকুনি দুটি ঘর দুটি চলকে আলাদা।
3. কিনারা পেরোনো চলে: বাঁ আর ডান কিনারা পাশাপাশি, ওপর আর নিচ পাশাপাশি; চারটি কোণ মিলে একটি ৪-এর দল হতে পারে।
4. শুধু 1 (আর দরকার হলে X): দলে কোনো 0 থাকবে না।
5. প্রতিটি 1 অন্তত একবার ঢাকা: একটি 1 একাধিক দলে থাকতে পারে — overlap করা সম্পূর্ণ বৈধ, কারণ X + X = X.
6. দল যত বড় সম্ভব: প্রতিবার দল দ্বিগুণ হলে একটি literal কমে।
7. দলের সংখ্যা যত কম সম্ভব: যে দলের সব 1 অন্য দলে ঢাকা পড়ে গেছে, সেটি বাদ।

দলকে product term হিসেবে পড়া

একটি দলের ভেতরে ঘুরে দেখুন কোন চলকের মান বদলায়। যে চলক বদলায় (কোথাও 0, কোথাও 1), সেটি বাদ। যে চলক পুরো দলে 1 থাকে, সেটি সরাসরি লিখুন; যে চলক পুরো দলে 0 থাকে, সেটি complement করে লিখুন। ৪ চলকে:

চার কোণের দলটি একবার মিলিয়ে নিন: m₀ = 0000, m₂ = 0010, m₈ = 1000, m₁₀ = 1010. A বদলায় (0 ও 1), C বদলায়; B সবসময় 0, D সবসময় 0. তাই term = B′D′. Map-এ চারটি ঘর অনেক দূরে মনে হলেও torus-এ তারা একটি ২×২ বর্গ।

৪ · সমাধান করা উদাহরণ — ৩ চলক থেকে কোণ-কিনারার ৪ চলক

উদাহরণ ১: F(A, B, C) = Σm(0, 2, 5, 7)

প্রথমে map ভরুন। m₀ আর m₂ ওপরের সারিতে (A = 0), কলাম 00 আর 10-এ; m₅ আর m₇ নিচের সারিতে (A = 1), কলাম 01 আর 11-এ।

A \ BC   00   01   11   10
  0       1    0    0    1      <- m0, m2 : two edges of the same row
  1       0    1    1    0      <- m5, m7 : neighbours in the middle

ওপরের সারিতে m₀ আর m₂ দেখতে দূরে, কিন্তু ডান-বাঁ কিনারা পেরিয়ে পাশাপাশি: 000 আর 010 — শুধু B আলাদা। দল (0, 2): A = 0, C = 0 স্থির → A′C′. নিচের সারিতে m₅ = 101 আর m₇ = 111 — শুধু B আলাদা। দল (5, 7): A = 1, C = 1 → AC. কোনো ৪-এর দল সম্ভব নয়, কারণ যেকোনো ২×২-এ অন্তত একটি 0 পড়ে।

লক্ষ্য করুন, B একেবারে উধাও — আউটপুট B-এর ওপর নির্ভরই করে না। Truth table-এ এটি চোখে পড়া কঠিন, K-map-এ এক নজরে ধরা পড়ে। আর A′C′ + AC মানে “A আর C সমান হলে 1” — ⊕ (XOR)-এর উল্টো, XNOR. তিন বা তার বেশি চলকের XOR (যেমন A ⊕ B ⊕ C) K-map-এ দাবার ছকের মতো দেখায় — কোনো দুটি 1 পাশাপাশি নেই, তাই K-map একটি literal-ও কমাতে পারে না। তখন XOR gate সরাসরি ব্যবহার করাই সস্তা (পর্ব ১১-এর adder-এ দেখবেন)।

উদাহরণ ২: F(A, B, C, D) = Σm(0, 1, 2, 5, 8, 9, 10) — কোণ আর কিনারার ক্লাসিক

এটি সম্ভবত সবচেয়ে বেশি পরীক্ষায় আসা ধরনের map, কারণ এতে তিন রকম ফাঁদ একসাথে আছে: চার কোণ, ওপর-নিচ কিনারা পেরোনো দল, আর একটি একা পড়ে থাকা 1. নিচের stepper-এ ধাপে ধাপে দেখুন — চিহ্নিত ঘরগুলো এই ধাপের দল, আর P, Q, R লেখা দেখায় কোন 1 কোন দলে পড়েছে।

AB\CD   00    01    11    10
 00     1     1     0     1
 01     0     1     0     0
 11     0     0     0     0
 10     1     1     0     1
ones: m0 m1 m2 m5 m8 m9 m10  (7 ones)

AB\CD   00    01    11    10
 00     1P    1     0     1P
 01     0     1     0     0
 11     0     0     0     0
 10     1P    1     0     1P
P = m0 m2 m8 m10 : B=0, D=0 fixed  -> B'D'

AB\CD   00    01    11    10
 00     1PQ   1Q    0     1P
 01     0     1     0     0
 11     0     0     0     0
 10     1PQ   1Q    0     1P
Q = m0 m1 m8 m9 : B=0, C=0 fixed  -> B'C'

AB\CD   00    01    11    10
 00     1PQ   1QR   0     1P
 01     0     1R    0     0
 11     0     0     0     0
 10     1PQ   1Q    0     1P
R = m1 m5 : A=0, C=0, D=1 fixed  -> A'C'D

F = B'D' + B'C' + A'C'D
P = B'D'  -> m0 m2 m8 m10
Q = B'C'  -> m0 m1 m8 m9
R = A'C'D -> m1 m5
union     -> m0 m1 m2 m5 m8 m9 m10   = all 7 ones, no 0
cost: 3 terms, 7 literals   (canonical: 7 terms, 28 literals)

একটি অভ্যাস তৈরি করুন: সবচেয়ে “একা” 1 থেকে শুরু করুন। যে 1-এর মাত্র একটি দিকে বড় হওয়ার পথ আছে (যেমন এখানে m5), তার দল নিয়ে কোনো সিদ্ধান্তের সুযোগ নেই — সেটি আগে বসালে পরে ভুল হয় না। আর কোণ ও কিনারা সবসময় আলাদা করে যাচাই করুন — এগুলো চোখ এড়িয়ে যাওয়াই সবচেয়ে সাধারণ ভুল।

উদাহরণ ৩: একটি ৮-এর দল আর একটি জোড়া — F(A, B, C, D) = Σm(0–9), অর্থাৎ “BCD অঙ্কটি বৈধ কি না”

৪ বিটে ০ থেকে ১৫ লেখা যায়, কিন্তু BCD-তে শুধু ০–৯ বৈধ। V = 1 যখন ইনপুট ০–৯. ওপরের দুই সারি (m0–m7) পুরো 1 — একটি ৮-এর দল, যেখানে শুধু A = 0 স্থির → A′. নিচের সারিতে m8 আর m9 বাকি; এদের সবচেয়ে বড় দল ওপরের সারির m0, m1-এর সাথে ওপর-নিচ কিনারা পেরিয়ে (0, 1, 8, 9) → B′C′. উত্তর V = A′ + B′C′ — মাত্র ৩ literal. লক্ষ্য করুন, m0 আর m1 দুই দলেই আছে: m8, m9-কে বড় দলে নেওয়ার জন্য এই overlap দরকার। শুধু (8, 9) নিলে term হতো AB′C′ — একটি বাড়তি literal.

৫ · Implicant, prime implicant, essential prime implicant — পদ্ধতিগত উপায়

ছোট map-এ চোখে দেখে দল বানানো যায়। কিন্তু কোনো কোনো map-এ চোখ প্রতারণা করে — সবচেয়ে বড় দলটি নিয়েও minimal উত্তর পাওয়া যায় না। তাই পাঠ্যবই আর পরীক্ষা একটি পদ্ধতিগত উপায় চায়, যার জন্য তিনটি সংজ্ঞা লাগে:

এখানে implicant, prime implicant আর essential prime implicant — এই তিন স্তর মনে রাখুন। একটি গুরুত্বপূর্ণ উপপাদ্য (theorem) আছে: প্রতিটি minimal SOP-এর প্রতিটি term একটি prime implicant. কারণ কোনো term prime না হলে তাকে বড় করা যায় — একটি literal কমে, আর ঢাকা ঘর শুধু বাড়ে, তাই খরচ কমে অথচ function একই থাকে। ফলে minimal উত্তর খুঁজতে শুধু PI-দের মধ্যে খুঁজলেই চলে।

তৃতীয় ধাপটি আসলে একটি set cover সমস্যা — বড় function-এ কঠিন, কিন্তু ৪ চলকের map-এ প্রায় সবসময় হাতেই হয়ে যায়। নিচের map-টি দেখুন — এখানে সবচেয়ে বড়, সবচেয়ে চোখে পড়া দলটিই অপ্রয়োজনীয়।

AB\CD   00    01    11    10
 00     0     1     0     0
 01     0     1     1     1
 11     1     1     1     0
 10     0     0     1     0
ones: m1 m5 m6 m7 m11 m12 m13 m15

BD    (m5 m7 m13 m15)   centre 2x2 square
A'C'D (m1 m5)           column 01, rows 00-01
A'BC  (m6 m7)           row 01, columns 11-10
ABC'  (m12 m13)         row 11, columns 00-01
ACD   (m11 m15)         column 11, rows 11-10
5 prime implicants; none can grow without a 0

m1  : A'C'D            -> only one  => A'C'D essential
m6  : A'BC             -> only one  => A'BC essential
m12 : ABC'             -> only one  => ABC' essential
m11 : ACD              -> only one  => ACD essential
m5  : BD, A'C'D        -> two
m7  : BD, A'BC         -> two
m13 : BD, ABC'         -> two
m15 : BD, ACD          -> two

covered by the 4 EPIs:
  A'C'D -> m1 m5     A'BC -> m6 m7
  ABC'  -> m12 m13   ACD  -> m11 m15
BD = m5 m7 m13 m15  -> all already covered: redundant
F = A'C'D + A'BC + ABC' + ACD     4 terms, 12 literals
(with BD added: 5 terms, 14 literals - not minimal)

যখন একাধিক minimal উত্তর থাকে — essential PI একটিও নেই

F(A, B, C) = Σm(0, 1, 2, 5, 6, 7) নিন। Map-এ ছয়টি 1 একটি চক্র বানায়:

A \ BC   00   01   11   10
  0       1    1    0    1
  1       0    1    1    1
PIs: A'B'(0,1)  A'C'(0,2)  B'C(1,5)  BC'(2,6)  AC(5,7)  AB(6,7)

ছয়টি PI, প্রত্যেকটি ২ ঘরের জোড়া, আর প্রতিটি 1-কে ঠিক দুটি PI ঢাকে — তাই কোনো essential PI নেই। এমন অবস্থাকে বলে cyclic (চক্রাকার) map. পদ্ধতি: যেকোনো একটি PI ধরে নিন, তারপর বাকিটুকু সবচেয়ে কম খরচে ঢাকুন। A′B′ নিলে বাকি থাকে 2, 5, 6, 7 — BC′ (2, 6) আর AC (5, 7) দিয়ে শেষ: F = A′B′ + BC′ + AC. আবার A′C′ দিয়ে শুরু করলে বাকি 1, 5, 6, 7 — B′C (1, 5) আর AB (6, 7): F = A′C′ + B′C + AB. দুটিই ৩ term, ৬ literal — দুটিই সঠিক minimal উত্তর। পরীক্ষায় যেকোনো একটি লিখলেই পূর্ণ নম্বর পাওয়ার কথা; খাতায় দ্বিতীয়টির কথা উল্লেখ করলে বোঝা যায় আপনি পদ্ধতিটি জানেন।

এবার পুরো পদ্ধতিটি যন্ত্রে চালিয়ে দেখুন। নিচের ছোট minimiser map আঁকে (সারি-কলাম Gray ক্রমে, 1, X আর 0-এর জায়গায় .), সব prime implicant আর essential PI ছাপে, তারপর সব PI-এর প্রতিটি সম্ভাব্য সমষ্টি পরীক্ষা করে (exhaustive search — ৪ চলকে PI খুব বেশি হয় না, তাই এক মুহূর্তে শেষ) সবচেয়ে কম খরচের উত্তর বের করে। শেষে truth table-এর ১৬টি সারি মিলিয়ে দেখে। Run চাপুন, তারপর শেষের লাইনগুলোতে নিজের function বসিয়ে দেখুন:

// K-map minimiser for 2-4 variables: draw the map, find every prime implicant,
// pick a minimal SOP cover by exhaustive search, then verify with the truth table.
const V = "ABCD", G = { 1: ["0", "1"], 2: ["00", "01", "11", "10"] };   // Gray order
const cubes = n => n ? cubes(n - 1).flatMap(s => ["0" + s, "1" + s, "-" + s]) : [""];
const cells = c => c.includes("-") ? [...cells(c.replace("-", "0")), ...cells(c.replace("-", "1"))] : [parseInt(c, 2)];
const term = c => [...c].map((b, i) => b === "-" ? "" : V[i] + (b === "0" ? "'" : "")).join("") || "1";
const lits = S => S.reduce((s, c) => s + c.replace(/-/g, "").length, 0);
function kmap(n, on, dc = []) {
  const rb = n >> 1, cb = n - rb, val = m => on.includes(m) ? "1" : dc.includes(m) ? "X" : ".";
  console.log(`${V.slice(0, rb)}\\${V.slice(rb, n)}`.padEnd(6) + G[cb].join("  "));
  for (const r of G[rb]) console.log(r.padEnd(6) + G[cb].map(c => val(parseInt(r + c, 2)).padEnd(cb)).join("  "));
  const imp = cubes(n).filter(c => cells(c).every(m => on.includes(m) || dc.includes(m)) && cells(c).some(m => on.includes(m)));
  const pis = imp.filter(a => !imp.some(b => b !== a && cells(a).every(m => cells(b).includes(m))));
  const epi = pis.filter(p => on.some(m => pis.filter(q => cells(q).includes(m)).length === 1 && cells(p).includes(m)));
  console.log("prime implicants:", pis.map(p => `${term(p)}(${cells(p).join(",")})`).join("  "));
  console.log("essential:", epi.map(term).join(", ") || "none");
  let best = [];
  for (let mask = 1; mask < 1 << pis.length; mask++) {
    const S = pis.filter((_, i) => mask >> i & 1);
    if (!on.every(m => S.some(p => cells(p).includes(m)))) continue;
    const cost = S.length * 100 + lits(S), b = best[0] ? best[0].length * 100 + lits(best[0]) : 1e9;
    if (cost < b) best = [S]; else if (cost === b) best.push(S);
  }
  best.forEach(S => {
    const ok = [...Array(1 << n).keys()].every(m => dc.includes(m) || S.some(p => cells(p).includes(m)) === on.includes(m));
    console.log(`F = ${S.map(term).join(" + ")}   [${S.length} terms, ${lits(S)} literals, truth table ${ok ? "OK" : "FAIL"}]`);
  });
  console.log("-".repeat(44));
}
kmap(3, [0, 2, 5, 7]);
kmap(4, [0, 1, 2, 5, 8, 9, 10]);
kmap(3, [0, 1, 2, 5, 6, 7]);                 // two equally good answers
kmap(4, [1, 5, 6, 7, 11, 12, 13, 15]);       // BD is prime but not needed
kmap(4, [1, 3, 7, 11, 15], [0, 2, 5]);       // with don't cares

A\BC  00  01  11  10
0     1   .   .   1
1     .   1   1   .
prime implicants: A'C'(0,2)  AC(5,7)
essential: A'C', AC
F = A'C' + AC   [2 terms, 4 literals, truth table OK]
--------------------------------------------
AB\CD 00  01  11  10
00    1   1   .   1
01    .   1   .   .
11    .   .   .   .
10    1   1   .   1
prime implicants: B'D'(0,2,8,10)  A'C'D(1,5)  B'C'(0,1,8,9)
essential: B'D', A'C'D, B'C'
F = B'D' + A'C'D + B'C'   [3 terms, 7 literals, truth table OK]
--------------------------------------------
A\BC  00  01  11  10
0     1   1   .   1
1     .   1   1   1
prime implicants: BC'(2,6)  A'C'(0,2)  B'C(1,5)  AC(5,7)  A'B'(0,1)  AB(6,7)
essential: none
F = BC' + AC + A'B'   [3 terms, 6 literals, truth table OK]
F = A'C' + B'C + AB   [3 terms, 6 literals, truth table OK]
--------------------------------------------
AB\CD 00  01  11  10
00    .   1   .   .
01    .   1   1   1
11    1   1   1   .
10    .   .   1   .
prime implicants: A'C'D(1,5)  ACD(11,15)  BD(5,7,13,15)  ABC'(12,13)  A'BC(6,7)
essential: A'C'D, ACD, ABC', A'BC
F = A'C'D + ACD + ABC' + A'BC   [4 terms, 12 literals, truth table OK]
--------------------------------------------
AB\CD 00  01  11  10
00    X   1   1   X
01    .   X   1   .
11    .   .   1   .
10    .   .   1   .
prime implicants: CD(3,7,11,15)  A'D(1,3,5,7)  A'B'(0,1,2,3)
essential: CD
F = CD + A'D   [2 terms, 4 literals, truth table OK]
F = CD + A'B'   [2 terms, 4 literals, truth table OK]
--------------------------------------------

৬ · Don't care — যে ইনপুট কখনো আসে না, তাকে কাজে লাগানো

অনেক বাস্তব circuit-এ কিছু ইনপুট-সমন্বয় কখনো আসেই না। BCD-তে ৪ বিটে ১৬টি নকশা সম্ভব, কিন্তু বৈধ মাত্র ০–৯; 1010 থেকে 1111 পর্যন্ত ছয়টি নকশা কোনো সঠিক উৎস থেকে আসার কথা নয়। এমন সারির আউটপুট নিয়ে আমাদের মাথাব্যথা নেই — তাই সেখানে লেখা হয় X (বা d), নাম don't care. লেখার রীতি: F = Σm(…) + d(…)।

নিয়মটি সহজ: X-কে প্রয়োজনমতো 1 বা 0 ধরুন। কোনো দল বড় করতে X কাজে লাগলে সেটিকে 1 ধরে দলে নিন; না লাগলে ছেড়ে দিন (0 ধরা হলো)। কিন্তু শুধু X দিয়ে কোনো দল বানাবেন না — সেটি কোনো 1-কে ঢাকে না, শুধু খরচ বাড়ায়। আর X ঢাকতে হবে, এমন কোনো বাধ্যবাধকতাও নেই।

7-segment display — segment e

ক্যালকুলেটর আর ডিজিটাল ঘড়ির অঙ্ক দেখায় seven-segment display: সাতটি দাগ, নাম a (ওপরে), b (ওপরের ডানে), c (নিচের ডানে), d (নিচে), e (নিচের বাঁয়ে), f (ওপরের বাঁয়ে) আর g (মাঝে)। একটি BCD-to-7-segment decoder চার বিটের BCD (ABCD) নিয়ে সাতটি আউটপুট দেয় — প্রতিটি segment-এর জন্য একটি করে Boolean function. Segment e (নিচের বাঁয়ের দাগ) জ্বলে শুধু ০, ২, ৬ আর ৮-এ:

AB\CD   00    01    11    10
 00     1     0     0     1
 01     0     0     0     1
 11     X     X     X     X
 10     1     0     X     X
ones: m0 m2 m6 m8   don't care: m10..m15

AB\CD   00    01    11    10
 00     1P    0     0     1Q
 01     0     0     0     1Q
 11     0     0     0     0
 10     1P    0     0     0
P = m0 m8 -> B'C'D'    Q = m2 m6 -> A'CD'    6 literals

AB\CD   00    01    11    10
 00     1P    0     0     1P
 01     0     0     0     1
 11     X     X     X     X
 10     1P    0     X     XP
P = m0 m2 m8 (+X m10) -> B'D'

AB\CD   00    01    11    10
 00     1P    0     0     1PQ
 01     0     0     0     1Q
 11     X     X     X     XQ
 10     1P    0     X     XPQ
Q = m2 m6 (+X m14 m10) : C=1, D=0 -> CD'

e = B'D' + CD'           4 literals   (was 6)
used as 1 : m10 m14
left as 0 : m11 m12 m13 m15
if a bad code arrives anyway:
  input 10 11 12 13 14 15
  e  =   1  0  0  0  1  0

Segment a — এক বড় সাশ্রয়

Segment a (ওপরের দাগ) জ্বলে ০, ২, ৩, ৫, ৬, ৭, ৮, ৯-এ — বাকি থাকে শুধু ১ আর ৪. (অঙ্ক ৬-এর ওপরে আর ৯-এর নিচে দাগ থাকবে কি না, তা display-ভেদে আলাদা হয়; কিছু decoder chip ৬ আর ৯-কে এই “লেজ” ছাড়া দেখায়। এখানে আমরা লেজসহ রূপ ধরছি, যা পাঠ্যবইয়ে বেশি প্রচলিত — অন্য রূপ ধরলে উত্তর বদলাবে।)

a = Σm(0,2,3,5,6,7,8,9) + d(10..15)

AB\CD   00   01   11   10
 00      1    0    1    1
 01      0    1    1    1
 11      X    X    X    X
 10      1    1    X    X

X-গুলো ধরে চারটি বড় দল: নিচের দুই সারি (m8–m15, X-সহ) একটি ৮-এর দল → A; শেষ দুই কলাম (C = 1, m2, m3, m6, m7 আর X m10, m11, m14, m15) আরেকটি ৮-এর দল → C; মাঝের ২×২ বর্গ (m5, m7, m13, m15) → BD; আর চার কোণ (m0, m2, m8, m10) → B′D′. ফল a = A + C + BD + B′D′ — মাত্র ৬ literal. X ছাড়া একই segment লাগে ১১ literal. নিচের কোডটি দুই segment-এর হিসাবই চালিয়ে মিলিয়ে দেয়, আর বলে দেয় অবৈধ ইনপুটে circuit আসলে কী দেখাবে:

// BCD to 7-segment decoder: minimise segments a and e with and without don't cares.
// Inputs ABCD = BCD digit 0-9 (A = MSB). Codes 1010-1111 never arrive -> don't care.
const V = "ABCD";
const SEG = { a: [0, 2, 3, 5, 6, 7, 8, 9], e: [0, 2, 6, 8] };     // digits that light the segment
const DC = [10, 11, 12, 13, 14, 15];
const cubes = n => n ? cubes(n - 1).flatMap(s => ["0" + s, "1" + s, "-" + s]) : [""];
const cells = c => c.includes("-") ? [...cells(c.replace("-", "0")), ...cells(c.replace("-", "1"))] : [parseInt(c, 2)];
const lits = S => S.reduce((s, c) => s + c.replace(/-/g, "").length, 0);
const term = c => [...c].map((b, i) => b === "-" ? "" : V[i] + (b === "0" ? "'" : "")).join("") || "1";
function minCover(on, dc) {
  const imp = cubes(4).filter(c => cells(c).every(m => on.includes(m) || dc.includes(m)) && cells(c).some(m => on.includes(m)));
  const pis = imp.filter(a => !imp.some(b => b !== a && cells(a).every(m => cells(b).includes(m))));
  let best = null;
  for (let mask = 1; mask < 1 << pis.length; mask++) {
    const S = pis.filter((_, i) => mask >> i & 1);
    if (on.every(m => S.some(p => cells(p).includes(m))) && (!best || S.length * 100 + lits(S) < best.length * 100 + lits(best))) best = S;
  }
  return best;
}
const f = (S, m) => S.some(p => cells(p).includes(m)) ? 1 : 0;
for (const s of ["a", "e"]) {
  const plain = minCover(SEG[s], []), withX = minCover(SEG[s], DC);
  console.log(`segment ${s}: on for digits ${SEG[s].join(",")}`);
  console.log(`  without don't care: ${plain.map(term).join(" + ")}  (${lits(plain)} literals)`);
  console.log(`  with    don't care: ${withX.map(term).join(" + ")}  (${lits(withX)} literals)`);
  const ok = [...Array(10).keys()].every(d => f(withX, d) === (SEG[s].includes(d) ? 1 : 0));
  console.log(`  digits 0-9 ${ok ? "all correct" : "MISMATCH"}; inputs 10-15 give ` + DC.map(m => f(withX, m)).join(""));
}
const tot = x => ["a", "e"].reduce((t, s) => t + lits(minCover(SEG[s], x)), 0);
console.log(`segments a + e together: ${tot([])} literals -> ${tot(DC)} literals with don't cares`);

segment a: on for digits 0,2,3,5,6,7,8,9
  without don't care: B'C'D' + A'BD + AB'C' + A'C  (11 literals)
  with    don't care: B'D' + BD + C + A  (6 literals)
  digits 0-9 all correct; inputs 10-15 give 111111
segment e: on for digits 0,2,6,8
  without don't care: B'C'D' + A'CD'  (6 literals)
  with    don't care: CD' + B'D'  (4 literals)
  digits 0-9 all correct; inputs 10-15 give 100010
segments a + e together: 17 literals -> 10 literals with don't cares

৭ · POS — 0-এর দল বানিয়ে, তারপর NAND–NAND আর NOR–NOR

এতক্ষণ 1-এর দল বানিয়ে SOP পেয়েছি। একই map থেকে POS (product of sums) রূপও পাওয়া যায় — এবার 0-গুলোর দল বানিয়ে। যুক্তিটি দুই লাইনের:

1. 0-গুলোর দল বানালে যে SOP আসে, সেটি F নয়, F′-এর minimal SOP — কারণ F′ ঠিক সেখানেই 1, যেখানে F হলো 0.
2. F = (F′)′. এবার De Morgan লাগান: (P + Q + R)′ = P′Q′R′, আর প্রতিটি product term-এর complement একটি sum term — (B D′)′ = B′ + D. অর্থাৎ F′-এর প্রতিটি term থেকে প্রতিটি literal উল্টে, AND-এর জায়গায় OR বসিয়ে একটি বন্ধনী।

সরাসরি পড়ার নিয়ম: 0-এর দলে যে চলক স্থির 0, সেটি বন্ধনীতে সরাসরি; যে চলক স্থির 1, সেটি complement করে। (SOP-এর ঠিক উল্টো — কারণ একটি maxterm সেই সারিতেই 0 হয়।)

সমাধান: F = Σm(0, 1, 2, 5, 8, 9, 10)-এর POS

AB\CD   00   01   11   10
 00      1    1    0    1
 01      0    1    0    0
 11      0    0    0    0
 10      1    1    0    1
zeros: m3 m4 m6 m7 m11 m12 m13 m14 m15

তিনটি ৪-এর দলে নয়টি 0 ঢাকা যায়: পুরো তৃতীয় সারি (m12–m15) → A = 1, B = 1 স্থির → F′-এর term AB; কলাম CD = 11 (m3, m7, m15, m11) → CD; আর দ্বিতীয়-তৃতীয় সারির প্রথম ও শেষ কলাম (m4, m6, m12, m14 — ডান-বাঁ কিনারা পেরিয়ে) → B = 1, D = 0 → BD′. তাই F′ = AB + CD + BD′, আর De Morgan:

লক্ষ্য করুন: একই function-এর minimal SOP ছিল ৭ literal, minimal POS ৬ literal. কোনটি সস্তা তা আগে থেকে বলা যায় না — দুটিই বের করে তুলনা করাই নিয়ম। নিচের কোড দুটি রূপ পাশাপাশি বের করে, আর POS-টিকে সরাসরি truth table-এ মিলিয়ে দেখে:

// POS minimisation: group the 0s (and X) to get a minimal SOP for F', then apply
// De Morgan: every product term of F' becomes one sum term (clause) of F.
const V = "ABCD";
const cubes = n => n ? cubes(n - 1).flatMap(s => ["0" + s, "1" + s, "-" + s]) : [""];
const cells = c => c.includes("-") ? [...cells(c.replace("-", "0")), ...cells(c.replace("-", "1"))] : [parseInt(c, 2)];
const lits = S => S.reduce((s, c) => s + c.replace(/-/g, "").length, 0);
const prod = c => [...c].map((b, i) => b === "-" ? "" : V[i] + (b === "0" ? "'" : "")).join("");
const sum = c => "(" + [...c].map((b, i) => b === "-" ? "" : V[i] + (b === "1" ? "'" : "")).filter(Boolean).join(" + ") + ")";
function minCover(n, on, dc) {                 // same exhaustive search as before
  const imp = cubes(n).filter(c => cells(c).every(m => on.includes(m) || dc.includes(m)) && cells(c).some(m => on.includes(m)));
  const pis = imp.filter(a => !imp.some(b => b !== a && cells(a).every(m => cells(b).includes(m))));
  let best = null;
  for (let mask = 1; mask < 1 << pis.length; mask++) {
    const S = pis.filter((_, i) => mask >> i & 1);
    if (on.every(m => S.some(p => cells(p).includes(m))) && (!best || S.length * 100 + lits(S) < best.length * 100 + lits(best))) best = S;
  }
  return best;
}
function pos(n, on, dc = []) {
  const zeros = [...Array(1 << n).keys()].filter(m => !on.includes(m) && !dc.includes(m));
  const sop = minCover(n, on, dc), neg = minCover(n, zeros, dc);
  console.log(`F  = Σm(${on})` + (dc.length ? ` + d(${dc})` : "") + `   zeros: ${zeros}`);
  console.log(`F' = ${neg.map(prod).join(" + ")}`);
  console.log(`F  = ${neg.map(sum).join("")}   [POS: ${neg.length} clauses, ${lits(neg)} literals]`);
  console.log(`F  = ${sop.map(prod).join(" + ")}   [SOP: ${sop.length} terms, ${lits(sop)} literals]`);
  const evalPOS = m => neg.every(c => [...c].some((b, i) => b !== "-" && ((m >> (n - 1 - i)) & 1) !== +b));
  const ok = [...Array(1 << n).keys()].every(m => dc.includes(m) || evalPOS(m) === on.includes(m));
  console.log(`truth table check of POS: ${ok ? "OK" : "FAIL"}\n`);
}
pos(4, [0, 1, 2, 5, 8, 9, 10]);
pos(3, [0, 2, 5, 7]);
pos(4, [1, 3, 7, 11, 15], [0, 2, 5]);
pos(3, [3, 5, 6, 7]);                         // 3-input majority

F  = Σm(0,1,2,5,8,9,10)   zeros: 3,4,6,7,11,12,13,14,15
F' = BD' + CD + AB
F  = (B' + D)(C' + D')(A' + B')   [POS: 3 clauses, 6 literals]
F  = B'D' + A'C'D + B'C'   [SOP: 3 terms, 7 literals]
truth table check of POS: OK

F  = Σm(0,2,5,7)   zeros: 1,3,4,6
F' = AC' + A'C
F  = (A' + C)(A + C')   [POS: 2 clauses, 4 literals]
F  = A'C' + AC   [SOP: 2 terms, 4 literals]
truth table check of POS: OK

F  = Σm(1,3,7,11,15) + d(0,2,5)   zeros: 4,6,8,9,10,12,13,14
F' = D' + AC'
F  = (D)(A' + C)   [POS: 2 clauses, 3 literals]
F  = CD + A'D   [SOP: 2 terms, 4 literals]
truth table check of POS: OK

F  = Σm(3,5,6,7)   zeros: 0,1,2,4
F' = B'C' + A'C' + A'B'
F  = (B + C)(A + C)(A + B)   [POS: 3 clauses, 6 literals]
F  = BC + AC + AB   [SOP: 3 terms, 6 literals]
truth table check of POS: OK

NAND–NAND আর NOR–NOR — K-map-এর উত্তর থেকে সরাসরি circuit

পর্ব ০৮-এ দেখেছেন, CMOS-এ AND আর OR আসলে NAND/NOR-এর পরে একটি inverter — তাই সরাসরি NAND বা NOR দিয়ে বানানো সস্তা আর দ্রুত। দুটিই universal gate. সুখবর হলো, দুই স্তরের SOP হুবহু NAND–NAND হয়ে যায়, আর POS হুবহু NOR–NOR:

অর্থাৎ প্রথম স্তরে প্রতিটি product term-এর জন্য একটি NAND (২, ২ আর ৩ ইনপুটের), দ্বিতীয় স্তরে তিনটির আউটপুট নিয়ে একটি তিন-ইনপুটের NAND. প্রমাণ De Morgan দিয়ে: (X′Y′Z′)′ = X + Y + Z, যেখানে X, Y, Z হলো তিনটি product. ছবিটা হুবহু AND-OR circuit-এর মতো, শুধু সব gate NAND — মাঝের দুটি “বুদবুদ” (inversion) একে অপরকে কেটে দেয়।

B' D'   --[NAND]--\
B' C'   --[NAND]---[NAND 3-input]--- F
A' C' D --[NAND]--/
(level 1)          (level 2)

POS থেকে একইভাবে NOR–NOR: F = (A′ + B′)(C′ + D′)(B′ + D) = ( (A′ + B′)′ + (C′ + D′)′ + (B′ + D)′ )′ — প্রথম স্তরে তিনটি দুই-ইনপুটের NOR, দ্বিতীয় স্তরে একটি তিন-ইনপুটের NOR. Complement করা ইনপুট (B′, C′, D′) চলকের পাশেই পাওয়া যায় ধরে নেওয়া হয়েছে; না থাকলে প্রতিটির জন্য একটি inverter (বা ইনপুট জোড়া দেওয়া একটি NAND) লাগবে।

৮ · সাধারণ ভুল, ৪-এর বেশি চলক, আর K-map-এর সীমা

নিজের দল ঠিক হলো কি না, যন্ত্রে মিলিয়ে নেওয়া যায়। নিচের checker-কে আপনার দলগুলো ঘরের নম্বরের তালিকা হিসেবে দিন; এটি প্রতিটি দলে এই ভুলগুলো খোঁজে — আকার, আয়তাকার কি না, 0 আছে কি না, আরও বড় করা যায় কি না (prime কি না), অপ্রয়োজনীয় কি না, আর কোনো 1 বাদ পড়ল কি না:

// Grouping checker: give your groups as lists of cell numbers; it reports the
// classic mistakes (bad size, not a rectangle, covers a 0, not prime, redundant, 1 left out).
const V = "ABCD";
function cubeOf(g, n) {                    // the product term if g is a valid group, else null
  if (g.length & (g.length - 1)) return null;          // size must be a power of two
  let c = "";
  for (let i = n - 1; i >= 0; i--) {
    const bits = new Set(g.map(m => (m >> i) & 1));
    c += bits.size === 2 ? "-" : [...bits][0];
  }
  return 2 ** (c.split("-").length - 1) === g.length ? c : null;  // all cells of that rectangle?
}
const term = c => [...c].map((b, i) => b === "-" ? "" : V[i] + (b === "0" ? "'" : "")).join("") || "1";
function check(name, n, on, dc, groups) {
  console.log(`${name}: groups ${JSON.stringify(groups)}`);
  const ok = m => on.includes(m) || dc.includes(m);
  groups.forEach((g, k) => {
    const c = cubeOf(g, n), msg = [];
    if (!c) msg.push(g.length & (g.length - 1) ? `size ${g.length} is not a power of 2` : "not a rectangle (cells differ in too many variables)");
    if (g.some(m => !ok(m))) msg.push("covers a 0");
    if (c && !msg.length) {
      const bigger = [...c].some((b, i) => b !== "-" && g.every(m => ok(m ^ (1 << (n - 1 - i)))));
      if (bigger) msg.push("can be doubled (not prime)");
      const others = groups.filter((_, j) => j !== k).flat();
      if (g.filter(m => on.includes(m)).every(m => others.includes(m))) msg.push("redundant");
    }
    console.log(`  group ${k + 1} ${c ? term(c) : "?"}: ${msg.join("; ") || "fine"}`);
  });
  const left = on.filter(m => !groups.flat().includes(m));
  console.log(left.length ? `  1s not covered: ${left}` : "  every 1 is covered");
}
check("try 1", 4, [0, 1, 2, 5, 8, 9, 10], [], [[0, 1], [8, 9], [0, 2, 8, 10], [5]]);
check("try 2", 4, [0, 1, 2, 5, 8, 9, 10], [], [[0, 1, 8, 9], [0, 2, 8, 10], [1, 5]]);
check("try 3", 3, [0, 2, 5, 7], [], [[0, 2, 5], [2, 7]]);
check("try 4", 4, [1, 5, 6, 7, 11, 12, 13, 15], [], [[5, 7, 13, 15], [1, 5], [6, 7], [12, 13], [11, 15]]);

try 1: groups [[0,1],[8,9],[0,2,8,10],[5]]
  group 1 A'B'C': can be doubled (not prime)
  group 2 AB'C': can be doubled (not prime)
  group 3 B'D': fine
  group 4 A'BC'D: can be doubled (not prime)
  every 1 is covered
try 2: groups [[0,1,8,9],[0,2,8,10],[1,5]]
  group 1 B'C': fine
  group 2 B'D': fine
  group 3 A'C'D: fine
  every 1 is covered
try 3: groups [[0,2,5],[2,7]]
  group 1 ?: size 3 is not a power of 2
  group 2 ?: not a rectangle (cells differ in too many variables)
  every 1 is covered
try 4: groups [[5,7,13,15],[1,5],[6,7],[12,13],[11,15]]
  group 1 BD: redundant
  group 2 A'C'D: fine
  group 3 A'BC: fine
  group 4 ABC': fine
  group 5 ACD: fine
  every 1 is covered

৫ আর ৬ চলক — যেখানে K-map হাঁপিয়ে ওঠে

৫ চলকের map সাধারণত দুটি ৪×৪ ছক পাশাপাশি এঁকে বানানো হয় — একটি E = 0, আরেকটি E = 1 (যেখানে E পঞ্চম চলক)। দুই ছকের একই অবস্থানের ঘর পাশাপাশি ধরা হয়, যেন একটির ওপর আরেকটি রাখা। ৬ চলকে চারটি ছক লাগে। নিয়ম একই, কিন্তু চোখ আর কাজ করে না: একটি ঘরের প্রতিবেশী এখন ৫ বা ৬টি, যার কিছু অন্য ছকে, আর ত্রিমাত্রিক দল মনে মনে কল্পনা করতে হয়। ভুলের সম্ভাবনা লাফিয়ে বাড়ে।

আরও বড় সমস্যা মাপের। n চলকে ঘর ২ⁿটি, আর prime implicant-এর সংখ্যা সবচেয়ে খারাপ ক্ষেত্রে ঘরের সংখ্যার চেয়েও দ্রুত বাড়তে পারে। তখন দরকার এমন পদ্ধতি যা কাগজের ছবির ওপর নির্ভর করে না, যন্ত্রে চালানো যায় — যেমন Quine–McCluskey পদ্ধতি, যা minterm-গুলো টেবিলে সাজিয়ে ধাপে ধাপে জোড়া মেলায় আর সব PI বের করে। পর্ব ১০-এ এটি, ৫–৬ চলকের map, একাধিক আউটপুট একসাথে সরল করা, আর hazard বিস্তারিত দেখবেন। আজকের chip-নকশায় এই কাজ করে logic synthesis software, যা হাজার হাজার চলক সামলায় — তবে ভেতরের ধারণা (implicant, cover) একই।

৯ · AI-এর যুগে — K-map-এর উত্তর নিজে যাচাই করুন

K-map-এর প্রশ্ন দিলে AI প্রায়ই আত্মবিশ্বাসী, সুন্দর ব্যাখ্যাসহ উত্তর দেয় — আর বেশ প্রায়ই সেটি ভুল। কারণ AI আসলে ছক দেখে না; লেখা থেকে অনুমান করে। কোণ আর কিনারার দল, ৮–১১ বনাম ১২–১৫ সারির ক্রম, আর don't care-এর ব্যবহার — এগুলোতেই ভুল বেশি। সুখবর হলো, K-map-এর উত্তর যাচাই করা খুব সহজ: truth table-এর ১৬টি সারি মিলিয়ে দেখলেই হয়।

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

• map-এর প্রতিটি ঘরের নম্বর নিজে মিলিয়েছি — বিশেষ করে শেষ দুই সারি আর শেষ দুই কলাম
• প্রতিটি দলের আকার ২-এর ঘাত, আয়তাকার, আর তাতে কোনো 0 নেই
• প্রতিটি term prime — কোনো literal বাদ দিলে অন্তত একটি 0 ঢোকে
• truth table-এর সব সারি (don't care বাদে) এই পর্বের minimiser বা নিজের script-এ মিলিয়েছি
• SOP আর POS দুটিই বের করে literal তুলনা করেছি, আর don't care-এ circuit কী দেবে তা লিখে রেখেছি