Boolean Simplification বাস্তব Circuit-এ — Gate গোনার হিসাব

আগে এটা বুঝি

আগের তিনটা লেসনে আপনি transistor থেকে CMOS gate বানিয়েছেন, আর দেখেছেন NAND একা দিয়ে যেকোনো function বানানো যায়। এখন হাতে আছে AND, OR, NOT, NAND, NOR, XOR — এই বাক্সগুলো দিয়ে circuit বানানোর স্বাধীনতা।

কিন্তু একটা প্রশ্ন এখনো বাকি: truth table থেকে সরাসরি gate-এ গেলে কী হয়?

Level 0-এর mathematics/boolean-algebra লেসনে আপনি ইতিমধ্যে [[karnaugh-map]] শিখেছেন — [[minterm]] থেকে canonical [[boolean-algebra|SOP]] বানানো, K-map দিয়ে সেটা minimize করা, [[de-morgans-law]] দিয়ে rewrite করা। সেই লেসনের মূল বার্তা ছিল: canonical form সবসময় সঠিক, প্রায় সবসময় অপচয়ী।

এই লেসন সেই গণিতটা পুনরায় শেখাবে না। এখানে আমরা সরাসরি circuit বানাব — একটা truth table থেকে শুরু করে, K-map চালিয়ে, তারপর গুনে দেখাব ঠিক কয়টা gate আর কয়টা transistor বাঁচল। এটাই আগের লেসনের “কম gate = কম সিলিকন, কম বিদ্যুৎ, কম সময়” দাবিটার প্রথম সংখ্যাভিত্তিক প্রমাণ।

দুইটা বাস্তব উদাহরণ নেব:

একটা ৪-input voting circuit — সরাসরি gate-count হিসাব
একটা 7-segment decoder-এর একটা অংশ — don’t-care কীভাবে আরো বাঁচায়

আর শেষে দেখব — সবকিছু কি সরল হয়? না। কিছু function (parity, XOR) সরলই হয় না, আর সেটাও একটা গুরুত্বপূর্ণ পাঠ।

মূল ধারণা

এক লাইনে recap

K-map-এর নিয়ম মনে করিয়ে দিই সংক্ষেপে: truth table-কে Gray-code ক্রমে সাজান যাতে পাশের ঘর ঠিক এক bit আলাদা হয়, 1-গুলোকে দুইয়ের ঘাত আকারের (১,২,৪,৮…) দলে বাঁধুন, দল যত বড় তত ভালো (প্রতি দ্বিগুণে একটা variable বাদ যায়), আর সবচেয়ে কম সংখ্যক বড় দলে সব 1 ঢাকুন। বিস্তারিত পুরোটা [[karnaugh-map]]-এ আছে — এখানে আমরা সরাসরি প্রয়োগে যাচ্ছি।

উদাহরণ ১ — ৪-input voting circuit

ধরুন আপনি একটা রকেটের navigation system ডিজাইন করছেন। চারটা স্বাধীন sensor (radiation-এ ভুল করতে পারে এমন পরিবেশে) একই জিনিস মাপছে, বাইনারিতে রিপোর্ট করছে (A, B, C, D)। আপনি চান একটা conservative decision circuit — output 1 হবে শুধু তখনই যখন চারটার মধ্যে অন্তত তিনটা sensor একমত (1 বলছে)। এটা একটা threshold function — নাম TH(3,4)।

Truth table

১৬টা row, সবকটা হাতে লিখি — F = 1 শুধু যেখানে অন্তত তিনটা input 1:

#	A B C D	ওজন	F	#	A B C D	ওজন	F
0	0000	0	0	8	1000	1	0
1	0001	1	0	9	1001	2	0
2	0010	1	0	10	1010	2	0
3	0011	2	0	11	1011	3	1
4	0100	1	0	12	1100	2	0
5	0101	2	0	13	1101	3	1
6	0110	2	0	14	1110	3	1
7	0111	3	1	15	1111	4	1

(“ওজন” মানে কয়টা input 1 — Hamming weight।) মাত্র পাঁচটা row-তে F=1: 7, 11, 13, 14, 15 — ঠিক সেই পাঁচটা row যাদের ওজন ≥3।

তাই F = Σm(7, 11, 13, 14, 15) — মাত্র পাঁচটা minterm ষোলোটার মধ্যে।

K-map

        CD
      00   01   11   10
    ┌────┬────┬────┬────┐
AB00│ 0  │ 0  │ 0  │ 0  │
    ├────┼────┼────┼────┤
  01│ 0  │ 0  │ 1  │ 0  │   ← m7
    ├────┼────┼────┼────┤
  11│ 0  │ 1  │ 1  │ 1  │   ← m13, m15, m14
    ├────┼────┼────┼────┤
  10│ 0  │ 0  │ 1  │ 0  │   ← m11
    └────┴────┴────┴────┘

m15 (কেন্দ্রের AB=11, CD=11 ঘর) চারদিকেই একটা করে প্রতিবেশী 1-এর সাথে জোড়া বাঁধে — চারটা আলাদা pair:

জোড়া	সাধারণ	Term
`m15, m14` (row `AB=11`, col `11`↔`10`)	`A=1,B=1,C=1`	`ABC`
`m15, m13` (row `AB=11`, col `11`↔`01`)	`A=1,B=1,D=1`	`ABD`
`m15, m7` (col `CD=11`, row `01`↔`11`)	`B=1,C=1,D=1`	`BCD`
`m15, m11` (col `CD=11`, row `11`↔`10`)	`A=1,C=1,D=1`	`ACD`

$F = ABC + ABD + BCD + ACD$

Gate count — সংখ্যা দিয়ে দেখুন

Canonical (naive) circuit — পাঁচটা minterm সরাসরি বসালে:

F = A'BCD + AB'CD + ABC'D + ABCD' + ABCD

পাঁচটা 4-input AND gate + একটা 5-input OR gate = ৬টা gate, মোট 5×4 + 5 = 25 টা তার-সংযোগ (input connection)।

Minimized circuit — চারটা term:

F = ABC + ABD + BCD + ACD

চারটা 3-input AND gate + একটা 4-input OR gate = ৫টা gate, মোট 4×3 + 4 = 16 টা তার-সংযোগ।

A,B,C ──► [AND3] ──┐
A,B,D ──► [AND3] ──┤
                    ├──► [OR4] ──► F
B,C,D ──► [AND3] ──┤
A,C,D ──► [AND3] ──┘

Minimized circuit-এর block diagram — চারটা 3-input AND, একটা 4-input OR।

Transistor count — [[logic-gate]]-এর টেবিল প্রয়োগ করে

আগের লেসনের CMOS transistor টেবিল মনে করুন: k-input NAND লাগে 2k transistor, তার উপর একটা inverter (+2) বসালে k-input AND হয় — মোট 2k + 2। একই সূত্র OR-এও (k-input NOR + inverter)। ২-input-এ এই সূত্র দেয় AND = 6, OR = 6 — ঠিক টেবিলের সাথে মেলে।

	Gate গঠন	Transistor হিসাব	মোট
Canonical	5× AND4	`5 × (2×4+2) = 5×10`	50
	1× OR5	`2×5+2`	12
		সর্বমোট	62
Minimized	4× AND3	`4 × (2×3+2) = 4×8`	32
	1× OR4	`2×4+2`	10
		সর্বমোট	42

৬২ থেকে ৪২ — প্রায় ৩২% transistor সাশ্রয়, শুধু বীজগণিত আর K-map দিয়ে, কোনো নতুন hardware trick ছাড়াই। এই একই circuit যদি একটা চিপে দশ লক্ষবার বসে (যেমন একটা বড় ECC memory controller-এ), তাহলে দশ লক্ষ গুণ ২০টা transistor — একটা বাস্তব সংখ্যা, তাত্ত্বিক নয়।

Majority function-এর সাথে পরিচিত হয়ে রাখুন

লক্ষ্য করুন — যদি input শুধু তিনটা হতো (A, B, C, কমপক্ষে দুইটা 1), মিনিমাইজড ফলাফল হতো F = AB + BC + AC — Level 0-এর boolean-algebra লেসনের Q1-এ ঠিক এই function derive করা হয়েছিল, আর সেখানে বলা হয়েছিল এটা full adder-এর carry-out। পরের লেসনেই (adder) আমরা ঠিক এই function আবার দেখব — এবার gate থেকে নয়, arithmetic থেকে derive করে, আর দুইটা derivation একই জায়গায় মিলবে।

ভেতরে কী ঘটছে

Don’t-care — কতটা আরো বাঁচানো যায়

Voting circuit-এ প্রতিটা input combination বৈধ ছিল (সব ১৬টা pattern ঘটতে পারে)। কিন্তু বাস্তবে অনেক circuit-এর input space-এর একটা অংশ কখনো ঘটে না — আর সেই “কখনো না ঘটা” জায়গাটাই বিনামূল্যে আরো minimization এনে দেয়। উদাহরণ: BCD digit (৪ bit, 0–9) থেকে 7-segment display চালানো।

Level 0-এর boolean-algebra লেসনে আমরা 7-segment-এর a segment (উপরের আনুভূমিক দাগ) ডিজাইন করেছিলাম। এখানে করব g segment (মাঝখানের আনুভূমিক দাগ) — এটা প্রায়ই সবচেয়ে জটিল, কারণ এটা কম regular pattern-এ জ্বলে।

     ─a─
    │   │
    f   b
    │   │
     ─g─      ← এইটা
    │   │
    e   c
    │   │
     ─d─

Truth table

ABCD = BCD digit (A = 8-এর ঘর, …, D = 1-এর ঘর)। কোন digit-এ g জ্বলে তা প্রতিটা অঙ্কের চেনা 7-segment আকৃতি থেকে সরাসরি:

Digit	ABCD	g
0	0000	0
1	0001	0
2	0010	1
3	0011	1
4	0100	1
5	0101	1
6	0110	1
7	0111	0
8	1000	1
9	1001	1
10–15		`X`

0, 1, 7 — এই তিনটা অঙ্কে সোজা দাগ থাকে, মাঝের দাগ লাগে না। বাকি সাতটা অঙ্কে লাগে। ১০–১৫ BCD-তে কখনো ঘটে না — don’t-care।

$g = \sum m(2,3,4,5,6,8,9) + \sum d(10,11,12,13,14,15)$

K-map

        CD
      00   01   11   10
    ┌────┬────┬────┬────┐
AB00│ 0  │ 0  │ 1  │ 1  │   ← m3, m2
    ├────┼────┼────┼────┤
  01│ 1  │ 1  │ 0  │ 1  │   ← m4, m5, m7=0!, m6
    ├────┼────┼────┼────┤
  11│ X  │ X  │ X  │ X  │   ← কখনো ঘটে না
    ├────┼────┼────┼────┤
  10│ 1  │ 1  │ X  │ X  │   ← m8, m9
    └────┴────┴────┴────┘

m7 (row AB=01, col CD=11) একটা firm 0 — কোনো দলে সেটা ঢোকানো যাবে না, don’t-care নয়।

তিন ধাপে minimization — পার্থক্যটা দেখতে

ধাপ ১ — Canonical, কোনো minimization নেই:

সাতটা minterm সরাসরি: 7 টা 4-input AND + 1 টা 7-input OR = ৮টা gate, 7×4 + 7 = 35 তার-সংযোগ।

ধাপ ২ — Minimize করা, কিন্তু don’t-care অগ্রাহ্য করে (১০–১৫-কে জোরপূর্বক 0 ধরে):

তখন প্রতিটা দল শুধু real 1-দের মধ্যেই বাঁধতে হয়, X-এর সুবিধা ছাড়াই:

$g = A'B'C + A'BC' + A'BD' + AB'C'$

চারটা 3-input AND + একটা 4-input OR = ৫টা gate, 4×3 + 4 = 16 তার-সংযোগ।

ধাপ ৩ — Don’t-care পুরোপুরি কাজে লাগিয়ে:

নিচের সারি (AB=1x, অর্থাৎ A=1) পুরোটাই — real 1 (m8, m9) আর don’t-care (m10–m15 সবই এই region-এ পড়ে) মিলে একটা পুরো ৮-ঘরের দল বানানো যায় → শুধু A, কোনো gate-ই লাগে না, একটা সরাসরি তার!

$g = A + BC' + CD' + B'CD$

A → কোনো gate না, সরাসরি wire
BC' → 2-input AND
CD' → 2-input AND
B'CD → 3-input AND
সব মিলিয়ে একটা 4-input OR

৩টা AND gate + ১টা OR gate = ৪টা gate, 2+2+3+4 = 11 তার-সংযোগ।

ধাপ	Gate সংখ্যা	তার-সংযোগ
Canonical	8	35
Minimized (don’t-care ছাড়া)	5	16
Minimized (don’t-care সহ)	4	11

তিন ধাপের তুলনা — একই function, একই output, ক্রমশ কম gate।

যাচাই — কয়েকটা digit হাতে বসিয়ে:

Digit 1 (0001, A=0,B=0,C=0,D=1): A=0, BC'=0, CD'=0, B'CD = 1·0·1 = 0 → g=0 ✓ (১ লিখতে মাঝের দাগ লাগে না)

Digit 3 (0011, A=0,B=0,C=1,D=1): A=0, BC'=0, CD'=1·0=0, B'CD=1·1·1=1 → g=1 ✓

Digit 7 (0111, A=0,B=1,C=1,D=1): A=0, BC'=1·0=0, CD'=1·0=0, B'CD=0·1·1=0 → g=0 ✓ (৭-এ মাঝের দাগ লাগে না, আর এটাই সেই firm-0 minterm — কোনো দলে ভুলবশত ঢোকেনি সেটা এই হিসাবই প্রমাণ করছে)

Don't-care ঘোষণা করার আগে প্রমাণ চাই

এখানে 10–15 don’t-care ধরা নিরাপদ ছিল কারণ এটা প্রমাণযোগ্য — BCD সংজ্ঞা অনুযায়ীই ৪-bit representation 9-এর বেশি কখনো এনকোড করে না, সফটওয়্যার/হার্ডওয়্যার input validation যাই থাকুক। যদি কোনো upstream bug (বা EMI glitch) থেকে 1010 চলে আসে, g = A + ... circuit-টা A=1 দেখেই g=1 জ্বালিয়ে দেবে — একটা undefined ডিজিটের জন্য একটা অর্থহীন কিন্তু “নির্ধারিত না” প্যাটার্ন জ্বলবে ডিসপ্লেতে। Display-এর জন্য এটা নিরাপদ (ভুল দেখানো ছাড়া কিছু হবে না) — কিন্তু নিচের misconception অংশে দেখবেন একই কৌশল নিরাপত্তা-সংবেদনশীল সিস্টেমে বিপজ্জনক হতে পারে।

কেন কিছু function সরলই হয় না

এতক্ষণ দুইটা উদাহরণেই minimization বড় লাভ দিয়েছে। এটা ভুল ধারণা তৈরি করতে পারে যে “সব function-ই সরল হয়”। তা সত্য না।

তিন-input parity function নিন — F = 1 iff বিজোড় সংখ্যক input 1 (এটাই তিন-input XOR: F = A ⊕ B ⊕ C)।

F = Σm(1, 2, 4, 7)

        BC
      00   01   11   10
    ┌────┬────┬────┬────┐
A 0 │ 0  │ 1  │ 0  │ 1  │
    ├────┼────┼────┼────┤
  1 │ 1  │ 0  │ 1  │ 0  │
    └────┴────┴────┴────┘

কোনো দুইটা 1-ঘর পরস্পরের প্রতিবেশী না — চেকারবোর্ড প্যাটার্ন। K-map-এ কোনো দল বাঁধা যায় না, একটা ঘর ছাড়া। তাই minimal SOP canonical-এর সমানই থেকে যায়:

$F = A'B'C + A'BC' + AB'C' + ABC$

চারটা 3-input AND + একটা OR — minimize করার আগেও পরেও একই, কারণ কোনো valid grouping নেই।

কেন — গভীর কারণ

Parity function-এর সংজ্ঞাই “প্রতিটা bit flip করলে output flip হয়”। কিন্তু K-map-এর adjacency মানে “ঠিক এক bit flip করলে, বাকি output অপরিবর্তিত থাকা উচিত যাতে সেই variable বাদ দেওয়া যায়”। Parity function-এ এক bit flip করলে output-ও সবসময় flip করে — ঠিক উল্টো ধর্ম। তাই কোনো variable-ই কখনো “বাদ” দেওয়া যায় না; প্রতিটা literal সবসময় দরকার।

Practical পাঠ: parity/checksum/CRC-এর মতো circuit — যেগুলো XOR-ভারী — এদের gate count কমানোর কোনো K-map trick নেই। এই কারণেই বাস্তব parity generator (যেমন 74HC280, ৯-bit parity IC) সরাসরি একটা XOR-tree, কোনো SOP minimization চেষ্টা করে না। পরের লেসনেই আমরা এই একই ঘটনা আবার দেখব — half-adder-এর Sum = A ⊕ B কোনোভাবেই AND-OR SOP-এ ছোট হয় না, তাই সরাসরি XOR gate ব্যবহার করাই optimal।

কেন ৪–৫ variable-এর পরে হাতে করা বন্ধ

আমাদের দুইটা উদাহরণই ৪ variable-এ থামল। বাস্তব circuit-এ প্রায়ই ৬, ৮, এমনকি ১৬+ variable থাকে — একটা CPU-র opcode decoder হয়তো ৮-bit opcode field পড়ে, 2^8 = 256 টা সম্ভাব্য combination। হাতে সেই K-map আঁকা অসম্ভব (256-ঘরের গ্রিড কল্পনা করুন, ৮-মাত্রিক hypercube-এ)।

Level 0-এর [[karnaugh-map]] glossary entry-তে যা বলা হয়েছিল তা এখানে আবার প্রাসঙ্গিক: সঠিক minimal circuit খোঁজা NP-hard। তাই বাস্তব synthesis tool দুইটা পথ নেয়:

পদ্ধতি	কী করে	ব্যবহার
Quine–McCluskey	সব prime implicant খুঁজে, তারপর essential গুলো বাছে — প্রমাণিতভাবে minimal	ছোট function (~১৫-২০ variable পর্যন্ত ব্যবহারিক, exponential খরচে)
Espresso	heuristic — প্রমাণ ছাড়াই দ্রুত প্রায়-optimal সমাধান খোঁজে	বড় function, বাস্তব synthesis tool-এ সর্বত্র

Espresso ১৯৮০-এর দশকে UC Berkeley-তে তৈরি (Brayton et al.), আর আজও প্রায় প্রতিটা open-source আর commercial synthesis tool-এর ভেতরে চলে — যার মধ্যে Yosys-ও, যেটা আগের লেসনের experiment-এ ব্যবহার করেছিলেন (abc pass আসলে Berkeley-র ABC logic-synthesis system, যেটা Espresso-family algorithm-এর উত্তরসূরি)।

কেন Quine–McCluskey-ও একটা সীমায় গিয়ে থেমে যায়

সমস্যাটা শুধু “৪ variable-এর বেশি হাতে আঁকা কঠিন” না — এটা সংখ্যাগতভাবে গভীর। Quine–McCluskey-র প্রথম ধাপ (prime implicant তৈরি) worst-case-এ exponential সংখ্যক prime implicant তৈরি করতে পারে, variable সংখ্যার সাথে।

একটা ক্লাসিক উদাহরণ — n-variable multiplexer function (যেমন 2:1 MUX-এর generalization): এই ধরনের function-এ prime implicant সংখ্যা n-এর সাথে প্রায় 3^(n/2)-এর মতো বাড়তে পারে। n=20-এ এটা কয়েক মিলিয়ন prime implicant — মেমরি আর সময় দুটোই দ্রুত ফুরিয়ে যায়।

এই কারণেই এই লেসনের boolean-algebra glossary entry-র দাবিটা (“সঠিক minimal circuit খোঁজা NP-hard”) শুধু একটা তাত্ত্বিক সতর্কতা না — এটা প্রকৌশলে সত্যিকারের প্রাচীর। Espresso এই প্রাচীর এড়ায় প্রমাণ ছাড়াই ভালো সমাধান খুঁজে — সব prime implicant গণনা না করে, স্থানীয় (local) উন্নতি বারবার প্রয়োগ করে, যতক্ষণ না আর উন্নতি সম্ভব হয়। ফলাফল সাধারণত অপ্টিমালের কাছাকাছি (বেশিরভাগ বাস্তব function-এ ১-২%-এর মধ্যে), কিন্তু কোনো গ্যারান্টি নেই এটাই সেরা — শুধু “যথেষ্ট ভালো, যুক্তিসঙ্গত সময়ে”।

তুলনা করে দেখুন: এই লেসনের TH(3,4) উদাহরণে (৪ variable, ১৬ minterm) prime implicant সংখ্যা ছিল মাত্র ৪টা — QM নিজেই মুহূর্তে সমাধান করেছে (আগের experiment-এ)। কিন্তু বাস্তব industrial function-এ (যেমন একটা ৩২-input ALU control logic) এই একই algorithm ব্যবহারযোগ্য না, কারণ prime implicant সংখ্যা নিজেই গণনা করা অসম্ভব হয়ে যায় — ঠিক এখানেই heuristic (Espresso) বাধ্যতামূলক হয়ে ওঠে।

K-map শেখার আসল মূল্য তাই minimize করা নয় — সেটা মূল্য হলো tool কী করছে বোঝা, don’t-care-এর সিদ্ধান্ত নিজে নিতে পারা, আর কখন একটা function (parity-র মতো) আদৌ সরল হবে না সেটা আগেই চেনা।

উদাহরণ

সম্পূর্ণ পাশাপাশি তুলনা

তিনটা function-ই আমরা দেখেছি — একসাথে রাখলে প্যাটার্নটা স্পষ্ট হয়:

Function	Variable	Canonical gate	Minimal gate	সাশ্রয়
`TH(3,4)` ভোটিং	4	6	5	মাঝারি
7-seg `g` (don’t-care সহ)	4	8	4	বড়
৩-input parity	3	4	4	শূন্য

নিয়ম যা এখান থেকে বেরোয়:

যত বেশি “structure” (input-দের মধ্যে সম্পর্ক) থাকে, তত বেশি সাশ্রয়ের সুযোগ
যত বেশি don’t-care, তত বেশি সাশ্রয়ের সুযোগ (তবে ঝুঁকিও বাড়ে)
Parity-জাতীয় function-এ (“প্রতিটা bit সমান গুরুত্বপূর্ণ, কোনো bit-ই বাদ দেওয়া যায় না”) সাশ্রয় নেই — এই ধরনের function চেনাটাই একটা দক্ষতা, যাতে অকারণে minimization-এ সময় নষ্ট না হয়

নিজে চালিয়ে দেখুন

EXPERIMENT

নিজের হাতের হিসাব Python দিয়ে যাচাই করুন

Python 3· ১৫ মিনিট

# gate_cost.py
def and_or_transistors(fanins):
    """AND/OR gate = NAND/NOR + inverter, তাই k-input gate = 2k+2"""
    return sum(2 * k + 2 for k in fanins) 

def cost(and_fanins, or_fanin):
    """and_fanins: প্রতিটা AND gate-এর input সংখ্যার লিস্ট, or_fanin: OR gate-এর input সংখ্যা"""
    gates = len(and_fanins) + (1 if or_fanin > 0 else 0)
    wires = sum(and_fanins) + or_fanin
    transistors = and_or_transistors(and_fanins)
    transistors += (2 * or_fanin + 2) if or_fanin > 0 else 0
    return gates, wires, transistors


# ── TH(3,4) ভোটিং circuit ──────────────────────────────
canonical = [4, 4, 4, 4, 4]     # ৫টা minterm, প্রতিটা 4-input AND
minimal   = [3, 3, 3, 3]        # ABC, ABD, BCD, ACD

for name, ands, or_in in [
    ("canonical", canonical, len(canonical)),
    ("minimal",   minimal,   len(minimal)),
]:
    g, w, t = cost(ands, or_in)
    print(f"TH(3,4) {name:10s}: gate={g:2d}  wire={w:3d}  transistor={t:3d}")

# ── 7-seg 'g' (তিন ধাপ) ─────────────────────────────────
seg_g_canonical    = [4]*7
seg_g_min_no_dc    = [3, 3, 3, 3]
seg_g_min_with_dc  = [2, 2, 3]           # BC', CD', B'CD  (A হলো ফ্রি — wire)

for name, ands in [
    ("canonical",       seg_g_canonical),
    ("min, no dc",      seg_g_min_no_dc),
    ("min, with dc",    seg_g_min_with_dc),
]:
    or_in = len(ands) + (1 if name == "min, with dc" else 0)  # +1 জন্য A term
    g, w, t = cost(ands, or_in)
    print(f"seg_g {name:14s}: gate={g:2d}  wire={w:3d}  transistor={t:3d}")

প্রত্যাশিত output:

TH(3,4) canonical : gate= 6  wire= 25  transistor= 62
TH(3,4) minimal   : gate= 5  wire= 16  transistor= 42
seg_g canonical      : gate= 8  wire= 35  transistor= 86
seg_g min, no dc     : gate= 5  wire= 16  transistor= 42
seg_g min, with dc   : gate= 4  wire= 12  transistor= 32

হাতে করা হিসাবের সাথে সংখ্যাগুলো মিলিয়ে দেখুন — এই লেসনের প্রতিটা টেবিলই এই স্ক্রিপ্টের আউটপুট থেকে যাচাইযোগ্য।

নিজে বাড়ান: parity function-এর জন্য একই হিসাব চালান — canonical আর minimal gate সংখ্যা সমান আসবে (৪ = ৪), যা এই লেসনের “কিছু function সরলই হয় না” দাবিটার প্রোগ্রামেটিক প্রমাণ।

এটা কী প্রমাণ করে

Canonical বনাম minimized SOP-এর gate/transistor খরচের হাতে করা হিসাব একটা প্রোগ্রামেটিক গণনার সাথে হুবহু মেলে — আর নিজের যেকোনো নতুন function-এর জন্য এই একই হিসাব স্বয়ংক্রিয়ভাবে চালানো যায়।

EXPERIMENT

Yosys দিয়ে TH(3,4) synthesize করে সংখ্যা মেলান

Linux / macOS (Yosys দরকার)· ১৫ মিনিট

// vote.v
module vote_naive(input A, B, C, D, output F);
  assign F = (~A&B&C&D) | (A&~B&C&D) | (A&B&~C&D) |
             (A&B&C&~D) | (A&B&C&D);
endmodule

module vote_min(input A, B, C, D, output F);
  assign F = (A&B&C) | (A&B&D) | (B&C&D) | (A&C&D);
endmodule

for m in vote_naive vote_min; do
  echo "=== $m ==="
  yosys -q -p "read_verilog vote.v; hierarchy -top $m; \
               proc; opt; techmap; opt; abc -g AND,OR,NAND,NOR,NOT; \
               opt; stat" 2>&1 | grep -A 10 "Printing statistics"
done

দুইটা module-ই functionally identical — একই truth table। Yosys নিজেই আসলে vote_naive-কেও optimize করে vote_min-এর কাছাকাছি নিয়ে যাবে (Espresso-family minimization তার ভেতরেই চলছে), কিন্তু opt pass বাদ দিয়ে (proc; techmap; stat, abc ছাড়া) চালালে vote_naive-এর raw গঠন (৬টা gate, বেশি input) সরাসরি দেখা যায় — optimization pass-টা কতটা কাজ করছে সেটাই এখানে স্পষ্ট হয়।

এটা কী প্রমাণ করে

একটা real synthesis tool-ও একই minimal gate count-এ পৌঁছায় — হাতের K-map কল্পনা না, verifiable ইঞ্জিনিয়ারিং।

নিজে বানান

BUILD IT

Gate/Transistor Cost Estimator + Don't-Care Explorer

Python · ●●●○○

একটা truth table (n variable, don't-care সহ) input হিসেবে নিন
পূর্বের লেসনের Quine–McCluskey minimizer পুনর্ব্যবহার করে minimal SOP বের করুন
প্রতিটা AND/OR gate-এর fan-in থেকে gate count, wire count, আর transistor count হিসাব করুন
don't-care ব্যবহার করে বনাম না করে — দুই ভার্সনের খরচ পাশাপাশি দেখান
নিজের ৩-৫টা পরিচিত function চালিয়ে (parity, majority, 7-seg segment) প্যাটার্ন যাচাই করুন

আগের (Level 0) লেসনের Quine–McCluskey minimizer-টাই এখানে দ্বিতীয় ব্যবহার পাবে — এবার output শুধু expression না, সরাসরি engineering cost।

from itertools import combinations

# ── Quine–McCluskey core (আগের লেসন থেকে, সামান্য পরিমার্জিত) ──

def combine(a, b):
    diff, out = 0, []
    for x, y in zip(a, b):
        if x != y:
            diff += 1
            out.append('-')
        else:
            out.append(x)
    return ''.join(out) if diff == 1 else None


def prime_implicants(minterms, dontcares, nbits):
    terms = {format(m, f'0{nbits}b') for m in set(minterms) | set(dontcares)}
    primes = set()
    while terms:
        used, nxt = set(), set()
        for a, b in combinations(sorted(terms), 2):
            c = combine(a, b)
            if c:
                nxt.add(c); used.add(a); used.add(b)
        primes |= (terms - used)
        terms = nxt
    return primes


def covers(implicant, minterm_bits):
    return all(i == '-' or i == m for i, m in zip(implicant, minterm_bits))


def minimize(minterms, dontcares=(), nbits=4):
    if not minterms:
        return []
    primes = prime_implicants(minterms, dontcares, nbits)
    targets = [format(m, f'0{nbits}b') for m in minterms]
    chart = {m: [p for p in primes if covers(p, m)] for m in targets}
    chosen, remaining = set(), set(targets)
    for m, ps in chart.items():
        if len(ps) == 1:
            chosen.add(ps[0])
    for p in chosen:
        remaining -= {m for m in targets if covers(p, m)}
    while remaining:
        best = max(primes - chosen,
                   key=lambda p: sum(1 for m in remaining if covers(p, m)))
        got = {m for m in remaining if covers(best, m)}
        if not got:
            break
        chosen.add(best)
        remaining -= got
    return sorted(chosen)


# ── নতুন: cost model ─────────────────────────────────────

def implicant_literal_count(imp):
    return sum(1 for b in imp if b != '-')


def circuit_cost(implicants):
    """AND-per-term + একটা OR — gate, wire, transistor গোনা"""
    and_fanins = [implicant_literal_count(imp) for imp in implicants
                  if implicant_literal_count(imp) > 0]      # ০-literal term = ফ্রি wire, gate লাগে না
    n_free_wires = sum(1 for imp in implicants if implicant_literal_count(imp) == 0)
    or_fanin = len(implicants)

    gates = len(and_fanins) + (1 if or_fanin > 1 else 0)
    wires = sum(and_fanins) + (or_fanin if or_fanin > 1 else 0)
    transistors = sum(2 * k + 2 for k in and_fanins)
    if or_fanin > 1:
        transistors += 2 * or_fanin + 2
    return dict(gates=gates, wires=wires, transistors=transistors,
                free_wires=n_free_wires)


def analyse(name, minterms, dontcares, nbits):
    canonical = [format(m, f'0{nbits}b') for m in minterms]   # প্রতিটা variable রাখা — canonical
    min_no_dc = minimize(minterms, (), nbits)                  # minimize, কিন্তু don't-care অগ্রাহ্য
    min_dc    = minimize(minterms, dontcares, nbits)           # সবটুকু ব্যবহার করে

    print(f"\n{'='*60}\n{name}\n{'='*60}")
    for label, imps in [("canonical", canonical),
                         ("minimized, no don't-care", min_no_dc),
                         ("minimized, with don't-care", min_dc)]:
        c = circuit_cost(imps)
        print(f"  {label:28s} term={len(imps):2d}  gate={c['gates']:2d}  "
              f"wire={c['wires']:3d}  transistor={c['transistors']:3d}")


# ── পরীক্ষার case ────────────────────────────────────────
analyse("TH(3,4) ভোটিং",      [7,11,13,14,15], [],              4)
analyse("7-seg 'g'",           [2,3,4,5,6,8,9], list(range(10,16)), 4)
analyse("৩-input parity",      [1,2,4,7],       [],              3)

প্রত্যাশিত: প্রথম দুইটা case-এ don’t-care সংস্করণ সবচেয়ে সস্তা; parity-তে তিনটা সংখ্যাই সমান — ঠিক এই লেসনের দাবিগুলোর সরাসরি প্রমাণ।

নিজে বাড়ান:

XOR-based realization যোগ করুন — parity function-এ SOP-এর বদলে A ⊕ B ⊕ C ব্যবহার করলে transistor cost কত (৮–১২ per XOR ধরে)? SOP-এর চেয়ে সস্তা না দামি?
একটা “cost budget” নিয়ে multi-output minimization যোগ করুন — ৭-segment-এর সাতটা segment একসাথে minimize করলে term share করা যায় কি না দেখুন
আপনার নিজের কোনো circuit ধারণা (যেমন একটা ৪-bit priority encoder) থেকে truth table বানিয়ে চালিয়ে দেখুন
Fan-in সীমা যোগ করুন (ধরুন hardware-এ সর্বোচ্চ 3-input gate পাওয়া যায়) — তখন বড় fan-in term-কে ছোট gate-এর tree-তে ভাঙার logic লিখুন (multi-level logic-এর শুরু)

বাস্তব সিস্টেমে

Gate-count minimization যেখানে সত্যিকারের টাকা বাঁচায়

Triple/quad modular redundancy (TMR/QMR)। এই লেসনের ভোটিং circuit কাল্পনিক না — Apollo Guidance Computer, Space Shuttle-এর flight computer, আর আজকের radiation-hardened satellite chip-এ হুবহু এই ধরনের majority/threshold voting circuit চলে, যাতে একটা sensor-এর radiation-induced bit flip পুরো সিস্টেম না ভাঙে।

RAID 5 parity। একাধিক disk-এর ডেটা থেকে একটা parity disk বানানো — সেটাও একটা XOR-tree, এই লেসনের parity উদাহরণের মতোই “minimize করা যায় না” ক্যাটাগরির circuit। হার্ডওয়্যার RAID controller-এ dedicated XOR ইঞ্জিন থাকে, generic SOP logic না।

7447/74247-এর মতো BCD-to-7-segment driver IC। ১৯৭০-এর দশক থেকে এই লেসনের মতোই don’t-care-ভিত্তিক minimization হাতে করে ডিজাইন হয়েছে — লক্ষ লক্ষ কপি বিক্রি হওয়া এই IC-র প্রতিটা gate বাঁচানো সরাসরি উৎপাদন খরচে প্রভাব ফেলেছে।

FPGA LUT packing। FPGA-তে logic একটা ৬-input lookup table (LUT) আকারে থাকে। Synthesis tool-এর কাজ হলো আপনার Boolean function-কে যতগুলো সম্ভব কম LUT-এ গুঁজে দেওয়া — সরাসরি এই লেসনের “কম gate” লক্ষ্যেরই একটা রূপ, শুধু gate-এর বদলে LUT count।

Instruction decoder। একটা CPU-র opcode decoder একটা বিশাল Boolean function (৮–১৬+ input bit)। হাতে minimize করা অসম্ভব — synthesis tool Espresso-family algorithm দিয়ে এটা করে, প্রতিটা নতুন চিপ generation-এ লক্ষ লক্ষবার।

ECC (error-correcting code) সার্কিট। Hamming code, Reed-Solomon decoder — এদের ভেতরের syndrome-calculation logic-ও Boolean minimization-এর মধ্য দিয়ে যায়, কারণ প্রতিটা memory access-এ এই circuit সক্রিয় থাকে, তাই gate delay সরাসরি memory latency-তে যোগ হয়।

Feature-flag/query predicate সরলীকরণ। যদিও এটা সিলিকন না, একই algebra একই কারণে কাজে লাগে — কম clause মানে কম CPU cycle প্রতিটা request-এ, যেমন আগের লেসনে দেখেছেন।

যে ভুলগুলো সবাই করে

“কম literal মানেই কম transistor — সবসময়।”

প্রায়ই সত্যি, কিন্তু gate type-এর উপর নির্ভর করে।

এই লেসনে AND-OR (SOP) form-এর জন্য cost model ব্যবহার করেছি: k-input AND/OR = 2k+2 transistor। কিন্তু XOR-এর transistor cost fan-in-এর সাথে রৈখিকভাবে বাড়ে না — একটা ২-input XOR-ই ৮–১২ transistor লাগে (AND/OR-এর ৬-এর চেয়ে বেশি), কারণ CMOS-এ XOR স্বাভাবিকভাবে “সস্তা” গঠন না।

তাই parity function-এ A ⊕ B ⊕ C (দুইটা ২-input XOR = ~১৬-২৪ transistor) বনাম SOP form (A'B'C + A'BC' + AB'C' + ABC, চারটা ৩-input AND + একটা OR = 4×8 + 8 = 40 transistor) — এখানে XOR form সস্তা, যদিও “literal count” হিসাবে compare করলে বিভ্রান্তিকর হতে পারে।

নিয়ম: literal count একটা proxy metric, চূড়ান্ত সত্য না। যে gate library আপনার হাতে আছে (শুধু NAND/NOR, নাকি XOR-ও পাওয়া যায়), সেটার উপর ভিত্তি করেই আসল cost হিসাব করতে হয়।

“একটা function-এর minimal SOP সবসময় একটাই, unique।”

প্রায়ই একাধিক সমান-খরচের minimal solution থাকে।

F = Σm(0,1,2,3,5,7) নিন। দুইটা বৈধ minimal cover:

F = A' + AC          (একই cost)
F = A' + BC          (ভুল! — যাচাই করে দেখুন, m5-এ মেলে না)

সঠিক দ্বিতীয় বিকল্প: এই নির্দিষ্ট function-এ আসলে A' + C-ই একমাত্র essential cover (Level 0-এর লেসনে দেখানো হয়েছিল)। কিন্তু general ক্ষেত্রে — যেখানে prime implicant chart-এ একটা minterm একাধিক prime implicant দিয়ে সমানভাবে ঢাকা পড়ে (non-essential choice) — সেখানে একাধিক সমান-cost minimal SOP থাকতে পারে। Quine–McCluskey-র “greedy” ধাপে তখন যেকোনো একটা বাছা যায়, দুইটাই সঠিক।

Practical পাঠ: আপনার হাতে করা K-map minimization যদি কোনো বইয়ের/tool-এর উত্তরের সাথে না মেলে, তার মানে এই না যে আপনি ভুল করেছেন — দুইটা সমতুল্য minimal সমাধান হতে পারে। Gate count মিললেই যথেষ্ট।

“Don't-care সবসময় নিরাপদ — যেহেতু সেই input তো ঘটবেই না।”

এই লেসনের 7-segment উদাহরণে don’t-care নিরাপদ ছিল, কারণ ভুল input এলে শুধু ভুল ডিজিট দেখাবে — কোনো বিপর্যয় না।

কিন্তু একই কৌশল একটা safety-critical state machine-এ প্রয়োগ করলে বিপজ্জনক। ধরুন একটা industrial controller-এর ৩ bit দিয়ে ৫টা state এনকোড করা (৩ bit-এ ৮টা pattern সম্ভব, ৩টা “অসম্ভব”)। যদি সেই ৩টা pattern-কে don’t-care ধরে minimize করা হয়, আর একটা power glitch বা cosmic ray সত্যিই register-কে সেই “অসম্ভব” state-এ ফেলে দেয় — circuit-এর আচরণ সম্পূর্ণ অনির্দিষ্ট। হয়তো একটা motor বন্ধ হওয়ার বদলে চলতেই থাকবে।

নিয়ম: don’t-care ব্যবহারের আগে প্রশ্ন করুন — “এই input সত্যিই গাণিতিকভাবে অসম্ভব (যেমন BCD-এর ১০–১৫), নাকি শুধু ‘স্বাভাবিক অবস্থায় ঘটে না’ (যেমন একটা faulty state)?” প্রথমটায় don’t-care নিরাপদ। দ্বিতীয়টায় safety-critical design-এ explicit default recovery state রাখা উচিত, don’t-care না — ঠিক [[karnaugh-map]] glossary entry-তে যেমন বলা হয়েছে।

বুঝেছেন কি না দেখুন

F(A,B,C,D) = Σm(1,3,5,7,9,11,13,15) — এই function-এর জন্য canonical আর minimal SOP-এর gate count বের করুন।

প্রয়োগ

প্রথমে লক্ষ্য করুন — সব আটটা minterm-ই বিজোড় (D=1 যেখানে)। আসলে F = D — শুধু একটা variable-এর মান, কোনো gate-ই লাগে না।

যাচাই: D=1 এমন সব minterm হলো xxx1 — অর্থাৎ A,B,C যেকোনো মান নিতে পারে, D=1 হলেই যথেষ্ট। 2^3 = 8 টা এমন combination আছে, আর ঠিক এই আটটাই দেওয়া হয়েছে (1,3,5,7,9,11,13,15 সবই বিজোড়)।

Canonical SOP: ৮টা minterm, প্রতিটা 4-input AND + 8-input OR = ৯টা gate।

Minimal: F = D — শূন্য gate, একটা সরাসরি wire।

এটা এই লেসনের সবচেয়ে চরম উদাহরণ: ৯টা gate থেকে শূন্যে। এটাই দেখায় কেন সবসময় প্রথমে minimize করা উচিত, circuit বানানোর আগে — একটা সরল pattern (এখানে “শুধু D-এর উপর নির্ভর করে”) হাতে truth table দেখে সহজেই মিস করা যায়, কিন্তু K-map/QM সেটা স্বয়ংক্রিয়ভাবে ধরে ফেলে।

এই লেসনের TH(3,4) ভোটিং সার্কিটে আমরা বলেছি চারটা term-ই essential prime implicant, তাই minimal SOP-এ কোনো term বাদ দেওয়া যায় না। কিন্তু m15 (সব input 1) চারটা term-েই আছে — তাহলে কি m15-এর জন্য একটা আলাদা, পঞ্চম term লাগবে না কেন?

যুক্তি

লাগবে না, কারণ একটা minterm একাধিক product term দিয়ে ঢাকা পড়তে পারে — SOP-এর OR gate যেকোনো একটা input 1 হলেই পুরো output 1 করে দেয়, “ঠিক একটা term মেলা উচিত” এমন কোনো নিয়ম নেই।

m15-এ (A=B=C=D=1) চারটা term-ই সত্য হয় একসাথে:

ABC = 1·1·1 = 1
ABD = 1·1·1 = 1
BCD = 1·1·1 = 1
ACD = 1·1·1 = 1

F = ABC + ABD + BCD + ACD = 1+1+1+1 = 1 (OR-এ, 1+1=1) — সঠিক।

গভীর পাঠ: K-map-এ দল overlap করতে পারে, আর এখানে m15-ই সেই ওভারল্যাপের কেন্দ্র — চারটা দলই তাকে স্পর্শ করে। এটা কোনো অপচয় না; এটাই কারণ চারটা মাত্র 3-literal term দিয়ে পাঁচটা minterm ঢাকা সম্ভব হয়েছে (m15 “বিনামূল্যে” চারবার কভার হয়ে গেছে, আলাদা কোনো term ছাড়াই)।

আপনাকে একটা ৫-input majority circuit ডিজাইন করতে বলা হয়েছে (F=1 iff অন্তত ৩টা input 1, ৫টার মধ্যে)। হাতে K-map করবেন, নাকি algorithmic tool ব্যবহার করবেন? কেন?

ডিজাইন

৫ variable মানে ৩২-ঘরের K-map — টেকনিক্যালি সম্ভব (দুইটা ৪-variable K-map পাশাপাশি রেখে, একটা “তৃতীয় dimension” হিসেবে), কিন্তু ভুল হওয়ার সম্ভাবনা অনেক বেড়ে যায়। এই লেসনের karnaugh-map glossary entry অনুযায়ী ৪ variable পর্যন্তই আরামদায়ক, ৫-৬-এ “কঠিন হয়ে যায়”।

ব্যবহারিক সিদ্ধান্ত:

প্রথমে Quine–McCluskey (এই লেসনের build অংশের কোড) চালিয়ে প্রমাণিতভাবে minimal SOP বের করুন — ৫ variable-এ এটা এখনো দ্রুত (2^5=32 minterm, exponential blowup শুরু হয় আরো বড় n-এ)
ফলাফলটা হাতে যাচাই করুন ছোট অংশে — যেমন symmetry ব্যবহার করে: TH(3,5) একটা symmetric function (input-দের ক্রম কোনো পার্থক্য করে না), তাই minimal SOP-ও symmetric হওয়া উচিত — প্রতিটা 3-variable combination-এর term থাকবে (C(5,3) = 10 টা term, প্রতিটা 3-literal)
Gate count হিসাব করুন এই লেসনের cost model দিয়ে, তারপর Yosys/Espresso দিয়ে দ্বিতীয়বার যাচাই করুন

সংক্ষেপে: ৫ variable “সীমানার কাছে” — একেবারে অসম্ভব না, কিন্তু হাতে করাটা এখন বেশি ঝুঁকিপূর্ণ, কম উপকারী। এই সিদ্ধান্তের মানদণ্ডই এই লেসনের মূল পাঠ: variable সংখ্যা বাড়লে হাত থেকে algorithm-এ কখন সরে যেতে হবে সেটা বোঝা, স্রেফ চোখ বন্ধ করে tool ব্যবহার করা না।

৩-input parity function-এ কোনো K-map grouping সম্ভব না, তাই minimize করা যায় না বলা হয়েছে। কিন্তু চারটা AND gate + একটা OR gate-এর বদলে কি দুইটা XOR gate (A ⊕ B ⊕ C) ব্যবহার করা “minimization” না?

যুক্তি

হ্যাঁ, এটা minimization — কিন্তু SOP framework-এর বাইরে।

এই লেসনের পুরো আলোচনা ছিল AND-OR (SOP) two-level logic-এর মধ্যে minimization — সেই framework-এ parity সত্যিই সরল হয় না, কারণ কোনো valid K-map grouping নেই।

কিন্তু circuit ডিজাইনে আপনি SOP-তে আটকে থাকতে বাধ্য নন। XOR gate ব্যবহার করলে:

A ⊕ B ⊕ C

দুইটা মাত্র gate (দুইটা 2-input XOR চেইন করে), প্রতিটা ৮–১২ transistor — মোট আনুমানিক ১৬–২৪ transistor। SOP form-এ (চারটা 3-input AND + একটা 4-input OR): 4×8 + 4×2+2 = 32+10 = 42 transistor-এর কাছাকাছি (আগের misconception-এ হিসাব করা)।

তাই XOR-based realization SOP-এর চেয়ে সস্তা — কিন্তু এটা “SOP minimization”-এর ফলাফল না, এটা different gate library বেছে নেওয়ার ফলাফল।

গভীর পাঠ: K-map/QM শুধু “AND, OR, NOT” primitive দিয়ে minimal two-level circuit খোঁজে। বাস্তব synthesis tool (Yosys-এর abc, commercial EDA tool) XOR, multiplexer সহ আরো বড় gate library থেকে বাছে, আর multi-level logic (কয়েক স্তর গভীর circuit) বিবেচনা করে — যেটা প্রায়ই SOP-এর চেয়ে ভালো ফল দেয়, বিশেষত parity-জাতীয় function-এ। এটাই কারণ বাস্তব chip-এ parity/checksum সার্কিট সবসময় XOR-tree হিসেবে ডিজাইন হয়, SOP হিসেবে না।

7-segment g উদাহরণে don’t-care ব্যবহার করে g = A + BC' + CD' + B'CD পেয়েছিলাম। যদি input 1010 (digit ১০, অবৈধ BCD) সত্যিই সার্কিটে চলে আসে, g-এর মান কী হবে? এটা কি সমস্যা?

প্রয়োগ

1010 মানে A=1, B=0, C=1, D=0।

A     = 1
BC'   = 0 · 0 = 0
CD'   = 1 · 1 = 1
B'CD  = 1 · 1 · 0 = 0

g = 1 + 0 + 1 + 0 = 1 (OR-এ)। তাই g জ্বলবে।

এটা “ভুল” কিন্তু “সমস্যা” কি না — নির্ভর করে context-এর উপর:

যদি এটা একটা সাধারণ 7-segment display হয় (calculator, microwave oven timer), তাহলে 1010 কখনো আসারই কথা না, কারণ উপরের সিস্টেম (যেমন BCD counter) কখনো 9-এর বেশি গোনে না। যদি hardware fault-এ আসেও, ফলাফল শুধু একটা arbitrary-দেখতে আকৃতি — bothersome কিন্তু বিপজ্জনক না।
কিন্তু যদি এই একই g-সদৃশ don’t-care-based minimization একটা নিয়ন্ত্রণ সংকেত (যেমন motor on/off, valve open/close) তৈরি করত, তাহলে একটা অপ্রত্যাশিত ইনপুট পুরো সিস্টেমকে অনির্দিষ্ট আচরণে ঠেলে দিতে পারত — misconception অংশে যেমন আলোচনা হয়েছে।

নিয়ম যা এখান থেকে বেরোয়: don’t-care ব্যবহারের decision নেওয়ার সময় শুধু “output সরল হবে কি না” না, “যদি এই ‘অসম্ভব’ input সত্যিই ঘটে, তার পরিণতি কতটা গুরুতর” — সেই প্রশ্নও করা উচিত। Display-এ নিরাপদ, actuator control-এ না।

F(A,B,C) = Σm(0,1,2,3,4,5,6,7) — অর্থাৎ সব আটটা minterm-ই 1। Canonical SOP আর minimal SOP-এর gate count কত? এটা কি এই লেসনের কোনো আগের উদাহরণের সাথে মেলে?

প্রয়োগ

সব minterm 1 মানে F আসলে ধ্রুবক 1 — input যাই হোক, output সবসময় 1। এটাই boolean-algebra লেসনের A + 1 = 1 identity-র সরাসরি প্রয়োগ (সব variable-এর সব combination মিলিয়ে পুরো space ঢেকে ফেলা)।

Canonical SOP: আটটা 3-input AND + একটা 8-input OR = ৯টা gate।

Minimal: F = 1 — একটা constant-1 উৎস (hardware-এ এটা সাধারণত Vdd-এর সাথে সরাসরি তার, কোনো gate না) — শূন্য gate।

এই লেসনের earlier উদাহরণের সাথে মিল: এটা ঠিক গঠনগতভাবে একই ঘটনা যা এই লেসনের প্রথম “check” প্রশ্নে (F=D, ৯ gate থেকে শূন্যে) দেখা গিয়েছিল — দুইটাই দেখায় যে একটা truth table “দেখতে জটিল” (অনেকগুলো 1-minterm) মনে হলেও, প্রকৃত function অনেক সরল হতে পারে, আর সেটা ধরার একমাত্র নির্ভরযোগ্য উপায় হলো minimization চালানো — চোখে “অনেক minterm” দেখে “জটিল circuit লাগবে” ধরে নেওয়াটা ভুল অনুমান।

সাধারণ নিয়ম: n-variable function-এ যদি সব 2ⁿ minterm-ই 1 হয়, ফলাফল সবসময় ধ্রুবক 1 (dual ভাবে, সব 0 হলে ধ্রুবক 0) — এই দুইটা extreme case-ই minimization-এর সবচেয়ে বড় সম্ভাব্য সাশ্রয় দেখায়, 2ⁿ-input worth-এর canonical circuit থেকে শূন্য gate-এ।

এরপর কী

এরপর — গণনা করা circuit

এই লেসনে আমরা shape (Boolean function) থেকে সস্তা circuit বানাতে শিখেছি। কিন্তু এখনো একটাও circuit বানাইনি যেটা সংখ্যা যোগ করে — যেটা এই পুরো মডিউলের driving question-এর কেন্দ্রে: “কয়েক কোটি on/off switch দিয়ে ‘যোগ করা’ কীভাবে সম্ভব হয়?”

পরের লেসনে আমরা ঠিক সেই প্রশ্নের উত্তর দেব। শুরু হবে সবচেয়ে ছোট adder (half-adder, মাত্র দুইটা gate) দিয়ে, তারপর full-adder — আর সেখানে আপনি দেখবেন এই লেসনের ভোটিং circuit-এর majority function হুবহু একই function যেটা carry-out গণনা করে। শেষে n-bit ripple-carry adder চেইন করে দেখব কেন সেটা ধীর, আর carry-lookahead কীভাবে সেই সমস্যার সমাধান করে — ঠিক যেভাবে এই লেসনে আমরা gate count কমিয়েছি, সেখানে আমরা delay কমাব।

Boolean Simplification বাস্তব Circuit-এ — Gate গোনার হিসাব

এই লেসন শেষে আপনি পারবেন

আগে যা বোঝা থাকা দরকার

আগে এটা বুঝি

মূল ধারণা

এক লাইনে recap

উদাহরণ ১ — ৪-input voting circuit

Truth table

K-map

Gate count — সংখ্যা দিয়ে দেখুন

Transistor count — [[logic-gate]]-এর টেবিল প্রয়োগ করে

ভেতরে কী ঘটছে

Don’t-care — কতটা আরো বাঁচানো যায়

Truth table

K-map

তিন ধাপে minimization — পার্থক্যটা দেখতে

কেন কিছু function সরলই হয় না

কেন ৪–৫ variable-এর পরে হাতে করা বন্ধ

কেন Quine–McCluskey-ও একটা সীমায় গিয়ে থেমে যায়

উদাহরণ

সম্পূর্ণ পাশাপাশি তুলনা

নিজে চালিয়ে দেখুন

নিজের হাতের হিসাব Python দিয়ে যাচাই করুন

Yosys দিয়ে TH(3,4) synthesize করে সংখ্যা মেলান

নিজে বানান

Gate/Transistor Cost Estimator + Don't-Care Explorer

বাস্তব সিস্টেমে

Gate-count minimization যেখানে সত্যিকারের টাকা বাঁচায়

যে ভুলগুলো সবাই করে

বুঝেছেন কি না দেখুন

এরপর কী

এরপর — গণনা করা circuit

আরও পড়ুন

এই লেসন শেষে আপনি পারবেন

আগে যা বোঝা থাকা দরকার

◔আগে এটা বুঝিWhy this matters

◆মূল ধারণাCore concept

এক লাইনে recap

উদাহরণ ১ — ৪-input voting circuit

Truth table

K-map

Gate count — সংখ্যা দিয়ে দেখুন

Transistor count — [[logic-gate]]-এর টেবিল প্রয়োগ করে

⚙ভেতরে কী ঘটছেUnder the hood

Don’t-care — কতটা আরো বাঁচানো যায়

Truth table

K-map

তিন ধাপে minimization — পার্থক্যটা দেখতে

কেন কিছু function সরলই হয় না

কেন ৪–৫ variable-এর পরে হাতে করা বন্ধ

কেন Quine–McCluskey-ও একটা সীমায় গিয়ে থেমে যায়

▶উদাহরণExample

সম্পূর্ণ পাশাপাশি তুলনা

⌘নিজে চালিয়ে দেখুনExperiment

নিজের হাতের হিসাব Python দিয়ে যাচাই করুন

Yosys দিয়ে TH(3,4) synthesize করে সংখ্যা মেলান

⚒নিজে বানানBuild it yourself

Gate/Transistor Cost Estimator + Don't-Care Explorer

◉বাস্তব সিস্টেমেReal-world usage

Gate-count minimization যেখানে সত্যিকারের টাকা বাঁচায়

⚠যে ভুলগুলো সবাই করেMisconceptions

?বুঝেছেন কি না দেখুনCheck understanding

→এরপর কীNext step

এরপর — গণনা করা circuit

আরও পড়ুন

আগে এটা বুঝি

মূল ধারণা

ভেতরে কী ঘটছে

উদাহরণ

নিজে চালিয়ে দেখুন

নিজে বানান

বাস্তব সিস্টেমে

যে ভুলগুলো সবাই করে

বুঝেছেন কি না দেখুন

এরপর কী