Foundationপ্রথম নীতি থেকে
LEVEL 0লেসন ১৩/১৬মাঝারি৫৫ মিনিট

Boolean Algebra — logic থেকে circuit-এ

Boolean Algebra and Minimization

একই logic, কিন্তু এবার circuit-এর ভাষায় — K-map, minimization, don't-care, আর কেন gate সংখ্যা কমানো মানে সিলিকন, বিদ্যুৎ আর সময় বাঁচানো।

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

  • Boolean algebra-র axiom ও duality principle প্রয়োগ করতে পারবেন
  • Truth table থেকে minimal SOP ও POS বের করতে পারবেন
  • Karnaugh map দিয়ে ৪-variable পর্যন্ত expression minimize করতে পারবেন
  • Don't-care condition কাজে লাগিয়ে আরো সরল circuit বানাতে পারবেন
  • Gate সংখ্যা, propagation delay আর খরচের সম্পর্ক ব্যাখ্যা করতে পারবেন

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

আগে এটা বুঝি

আমরা propositional logic শিখেছি। Boolean algebra সেই একই জিনিস — কিন্তু একটা ভিন্ন উদ্দেশ্যে।

Logic-এ প্রশ্ন ছিল: এই দাবিটা কি সত্য?

Boolean algebra-য় প্রশ্ন: এই function-টা সবচেয়ে কম gate দিয়ে কীভাবে বানাব?

পার্থক্যটা তুচ্ছ শোনায়, কিন্তু পরিণতি বিশাল। একটা CPU-তে কোটি কোটি gate। প্রতিটা gate মানে:

  • সিলিকনের জায়গা — chip যত বড়, উৎপাদন তত ব্যয়বহুল আর ত্রুটির সম্ভাবনা তত বেশি
  • বিদ্যুৎ — প্রতিটা switching-এ শক্তি খরচ, আর তাপ
  • সময় — প্রতিটা gate-এ propagation delay, আর সেটাই clock speed-এর সীমা টানে

একটা expression-এ তিনটার বদলে দুইটা gate ব্যবহার করা মানে, সেই circuit যদি চিপে ১০ লক্ষবার পুনরাবৃত্ত হয়, তাহলে ১০ লক্ষ gate সাশ্রয়।

এই লেসনটা Level 0-এর শেষ গাণিতিক ধাপ আর Level 2-এর প্রথম ধাপ — এখানেই গণিত সিলিকনে পরিণত হতে শুরু করে।

মূল ধারণা

একই বীজগণিত, নতুন সংকেত

Circuit ডিজাইনে সংকেত আলাদা, কারণ ঐতিহাসিকভাবে সেগুলো বীজগণিত থেকে এসেছে, logic থেকে নয়।

ধারণাLogicBoolean algebraCircuit
ANDp ∧ qA · B বা ABAND gate
ORp ∨ qA + BOR gate
NOT¬pA' বা Āinverter
সত্যT1high voltage
মিথ্যাF0low voltage

গুণ = AND, যোগ = OR — এই ধার করা সংকেত সুবিধাজনক, কারণ precedence স্বাভাবিকভাবেই ঠিক থাকে: AB + C মানে (A·B) + C, ঠিক যেমন 2×3 + 4।

কিন্তু সাবধান — সব সাদৃশ্য খাটে না। 1 + 1 = 1 এখানে (OR), সংখ্যার মতো 2 নয়।

Axiom

Boolean algebra-র সংজ্ঞা দেওয়া হয় কয়েকটা axiom দিয়ে (Huntington’s postulates):

A + 0 = A              A · 1 = A            identity
A + 1 = 1              A · 0 = 0            null
A + A = A              A · A = A            idempotent
A + A' = 1             A · A' = 0           complement
(A')' = A                                   involution

A + B = B + A          AB = BA              commutative
A + (B+C) = (A+B) + C  A(BC) = (AB)C        associative
A(B+C) = AB + AC       A + BC = (A+B)(A+C)  distributive

(A+B)' = A'B'          (AB)' = A' + B'      De Morgan
A + AB = A             A(A+B) = A           absorption

সবগুলোই আমরা logical equivalence-এর লেসনে দেখেছি — শুধু পোশাক বদলেছে।

Minterm, maxterm, canonical form

n variable-এর একটা minterm হলো এমন একটা product যেখানে প্রতিটা variable ঠিক একবার আছে (সরাসরি বা complement সহ)।

৩ variable-এ ৮টা minterm:

#A B CMinterm
00 0 0A'B'C'
10 0 1A'B'C
20 1 0A'BC'
30 1 1A'BC
41 0 0AB'C'
51 0 1AB'C
61 1 0ABC'
71 1 1ABC

প্রতিটা minterm ঠিক একটা row-তে ১, বাকি সব row-তে ০।

তাই একটা function-এর canonical SOP (sum of products) হলো যেসব row-তে output ১, তাদের minterm-গুলোর OR:

F=∑m(1,3,5,7)F = \sum m(1, 3, 5, 7)

Maxterm ঠিক উল্টো — প্রতিটা maxterm ঠিক একটা row-তে ০। Canonical POS (product of sums) হলো ০-row-গুলোর maxterm-এর AND:

F=∏M(0,2,4,6)F = \prod M(0, 2, 4, 6)

দুইটাই একই function, ভিন্ন রূপ। আমরা এটা logical-equivalence লেসনে DNF/CNF হিসেবে দেখেছি — এখানে শুধু নাম আর সংকেত ভিন্ন।

Minimization — কেন দরকার

Canonical form সবসময় সঠিক, কিন্তু প্রায় সবসময় অপচয়ী।

উদাহরণ: F = Σm(1, 3, 5, 7)

Canonical SOP:

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

চারটা 3-input AND gate + একটা 4-input OR gate = ৫টা gate, আর ১২টা input connection।

কিন্তু লক্ষ্য করুন: সব minterm-এ C আছে, আর A, B-এর সব combination আছে। তাই:

F=CF = C

একটা তারও লাগে না। পাঁচটা gate থেকে শূন্য।

বীজগণিত দিয়ে:

A'B'C + A'BC + AB'C + ABC
= A'C(B' + B) + AC(B' + B)      [C common করে বের করা]
= A'C·1 + AC·1                   [complement law]
= C(A' + A)                      [C common]
= C·1 = C                        [complement law]

এটাই minimization — আর এটা প্রতিটা chip design-এ, প্রতিটা FPGA synthesis-এ, প্রতিদিন লক্ষ লক্ষবার হয়।

Karnaugh map — চোখে দেখে minimize করা

বীজগণিত করা ক্লান্তিকর আর ভুল হওয়ার সম্ভাবনা বেশি। K-map একটা দৃশ্যমান পদ্ধতি, ২–৪ variable-এ চমৎকার কাজ করে।

মূল ধারণা: truth table-কে এমনভাবে সাজান যাতে পাশাপাশি ঘরগুলো ঠিক একটা bit-এ আলাদা হয়।

এই ক্রমটাকে বলে Gray code: 00, 01, 11, 10 — লক্ষ্য করুন 10 আর 00-ও এক bit আলাদা, তাই map-টা চারদিকে wrap করে (একটা torus)।

        BC
      00   01   11   10
    ┌────┬────┬────┬────┐
A 0 │ m0 │ m1 │ m3 │ m2 │
    ├────┼────┼────┼────┤
  1 │ m4 │ m5 │ m7 │ m6 │
    └────┴────┴────┴────┘
৩-variable K-map। কলামের ক্রম Gray code — পাশাপাশি ঘর ঠিক এক bit-এ আলাদা।

নিয়ম:

  1. যেসব ঘরে output 1, সেগুলো চিহ্নিত করুন
  2. 1-গুলোকে দুইয়ের ঘাত আকারের আয়তক্ষেত্রে দল বাঁধুন (১, ২, ৪, ৮…)
  3. দল যত বড় তত ভালো — প্রতিবার আকার দ্বিগুণ হলে একটা variable বাদ যায়
  4. দল overlap করতে পারে
  5. Map চারদিকে wrap করে (বাম-ডান, উপর-নিচ)
  6. সব 1 ঢাকা পড়া পর্যন্ত সবচেয়ে কম সংখ্যক বড় দল নিন

একটা উদাহরণ

F = Σm(0, 1, 2, 3, 5, 7)

        BC
      00   01   11   10
    ┌────┬────┬────┬────┐
A 0 │ 1  │ 1  │ 1  │ 1  │   ← পুরো row: A' 
    ├────┼────┼────┼────┤
  1 │ 0  │ 1  │ 1  │ 0  │   ← মাঝের দুইটা: AC
    └────┴────┴────┴────┘

দল ১: পুরো উপরের row (৪টা ঘর) → A' (B আর C দুটোই বাদ, কারণ দলের ভেতরে দুটোই সব মান নেয়)

দল ২: ডান দুইটা কলামের নিচের ঘর (m5, m7) → AC

F=A′+ACF = A' + AC

আরো সরল করা যায় absorption দিয়ে:

A′+AC=A′+CA' + AC = A' + C

(কারণ A' + AC = (A'+A)(A'+C) = 1·(A'+C) = A'+C)

চূড়ান্ত: F = A' + C — একটা inverter + একটা OR gate।

Canonical form-এ ছিল ছয়টা 3-input AND + একটা 6-input OR।

Don’t-care — অজানাকে সুবিধায় পরিণত করা

কিছু input combination কখনো ঘটবে না। তখন output কী হবে সেটা আপনার ইচ্ছা — আর সেই স্বাধীনতা কাজে লাগিয়ে আরো সরল circuit বানানো যায়।

চিহ্ন: X বা d।

উদাহরণ — BCD থেকে “৫-এর বেশি” detector:

BCD-তে ৪ bit দিয়ে ০–৯ প্রকাশ করা হয়। ১০–১৫ কখনো ঘটে না।

       CD
     00   01   11   10
   ┌────┬────┬────┬────┐
AB 00│ 0  │ 0  │ 0  │ 0  │   0,1,3,2
   ├────┼────┼────┼────┤
 01│ 0  │ 0  │ 1  │ 1  │   4,5,7,6
   ├────┼────┼────┼────┤
 11│ X  │ X  │ X  │ X  │   12,13,15,14 — ঘটে না
   ├────┼────┼────┼────┤
 10│ 1  │ 1  │ X  │ X  │   8,9,11,10
   └────┴────┴────┴────┘

Don’t-care ছাড়া: F = AB' + A'BC + A'BD — তিনটা term।

Don’t-care গুলোকে 1 ধরে নিলে বড় দল বানানো যায়:

  • পুরো নিচের দুই row (AB = 1x) → A
  • ডান দুই কলামের 01 row-এর সাথে → BC আর BD

F=A+BC+BD=A+B(C+D)F = A + BC + BD = A + B(C + D)

তিনটার বদলে দুইটা gate-স্তর, কম input।

ভেতরে কী ঘটছে

Gate থেকে delay — কেন minimization মানে গতি

প্রতিটা gate-এ propagation delay আছে — input বদলানোর পর output স্থির হতে যতটা সময় লাগে। আধুনিক CMOS-এ এটা কয়েক পিকোসেকেন্ড থেকে ন্যানোসেকেন্ড।

একটা circuit-এর critical path হলো input থেকে output পর্যন্ত সবচেয়ে দীর্ঘ gate-শৃঙ্খল। সেটাই clock period-এর সীমা টানে:

fmax⁡=1tcritical+tsetupf_{\max} = \frac{1}{t_{\text{critical}} + t_{\text{setup}}}

তাই gate-স্তরের সংখ্যা (depth) সরাসরি clock speed নির্ধারণ করে।

একটা expression সরল করা কী কী বাঁচায়
  1. কম termবীজগণিতিক minimization
  2. কম gateকম transistor
  3. কম সিলিকনছোট die, বেশি yield, কম দাম
  4. কম switchingকম dynamic power
  5. কম তাপসহজ cooling, কম throttling
  6. কম depthছোট critical path
  7. বেশি clock speedদ্রুত CPU

একটা সংখ্যা দিয়ে দেখুন: একটা ৩২-bit ripple-carry adder-এ carry এক প্রান্ত থেকে অন্য প্রান্তে যায় — ৩২টা full adder-এর মধ্য দিয়ে। প্রতিটায় ২ gate delay হলে critical path ৬৪ gate।

1 GHz clock মানে প্রতি cycle-এ 1 ns। Gate delay 50 ps হলে ৬৪ gate = 3.2 ns — এক cycle-এ শেষ হয় না।

সমাধান: carry-lookahead adder, যা বীজগণিত দিয়ে carry আগেভাগে হিসাব করে depth O(n) থেকে O(log n)-এ নামায়।

সেই বীজগণিতটা ঠিক এই লেসনের বীজগণিত। Level 2-এ আমরা carry-lookahead নিজে derive করব।

Functional completeness আবার

logical-equivalence লেসনে দেখেছি NAND দিয়ে সব হয়। এখানে কেন সেটা hardware-এ গুরুত্বপূর্ণ সেটা দেখি।

CMOS-এ transistor সংখ্যা:

GateTransistor
NOT2
NAND4
NOR4
AND6 (NAND + NOT)
OR6 (NOR + NOT)
XOR8–12

AND আর OR আসলে NAND/NOR-এর চেয়ে বেশি ব্যয়বহুল — কারণ CMOS স্বাভাবিকভাবে inverting। একটা non-inverting gate বানাতে একটা inverter যোগ করতে হয়।

তাই বাস্তব chip-এ প্রচুর NAND আর NOR, আর synthesis tool ইচ্ছাকৃতভাবে সেগুলোর দিকে রূপান্তর করে।

নিচে নিজে দেখুন — শুধু NAND দিয়ে NOT, AND, OR:

SIMULATOR

NAND দিয়ে সবকিছু

InputsOutputs¬A1A·B0A+B0
0A0BNANDNOT ANANDNANDA AND BNANDNANDNANDA OR B1¬A0A·B0A+B
AB¬AA·BA+B
00100
01101
10001
11011
শুধু NAND gate দিয়ে NOT, AND, OR বানানো — এজন্যই NAND-কে universal gate বলে।
টেবিলের যেকোনো row-তে ক্লিক করলে circuit সেই input-এ চলে যাবে।

Input toggle করে যাচাই করুন তিনটা output সত্যিই ¬A, A·B, আর A+B।

Multi-level logic

এতক্ষণ আমরা two-level logic দেখেছি — SOP মানে AND-স্তর তারপর OR-স্তর।

Two-level সবচেয়ে দ্রুত (depth ২), কিন্তু প্রায়ই সবচেয়ে বড়।

Multi-level factoring জায়গা বাঁচায়:

Two-level:   F = ABC + ABD + AEF + AEG      12 input, 5 gate
Factored:    F = A(B(C+D) + E(F+G))          8 input, 5 gate, কিন্তু depth 3

এটাই মূল trade-off:

Two-levelMulti-level
Depth (গতি)কম, স্থিরবেশি
Gate/areaবেশিকম
Powerবেশিকম

Synthesis tool-এ আপনি এই trade-off নিয়ন্ত্রণ করেন:

# Synopsys Design Compiler
set_max_delay 2.0 -to [all_outputs]    # গতিকে অগ্রাধিকার
set_max_area 10000                      # জায়গাকে অগ্রাধিকার

Compiler-এর -O2 বনাম -Os -এর হুবহু সমতুল্য — একই কোড, ভিন্ন লক্ষ্য।

Hazard — যেখানে গণিত বাস্তবতার সাথে ধাক্কা খায়

Boolean algebra ধরে নেয় gate তাৎক্ষণিক। বাস্তবে নয়।

ধরুন F = AB + A'C, আর B = C = 1। তাহলে গাণিতিকভাবে F = 1 সবসময়, A যাই হোক।

কিন্তু A যখন 1 থেকে 0 -তে বদলায়:

সময় →
A      ‾‾‾‾\____
A'     ____/‾‾‾‾     ← inverter-এর delay-র কারণে দেরিতে ওঠে
AB     ‾‾‾‾\____
A'C    ______/‾‾‾    
F      ‾‾‾‾\_/‾‾‾    ← একটা সংক্ষিপ্ত 0 — glitch!

Inverter-এর delay-র কারণে একটা মুহূর্তে দুইটা term-ই 0 হয়ে যায়, আর F-এ একটা glitch দেখা দেয়।

একে বলে static-1 hazard।

সমাধান: একটা redundant term যোগ করুন — BC।

F=AB+A′C+BCF = AB + A'C + BC

গাণিতিকভাবে BC অপ্রয়োজনীয় (consensus theorem অনুযায়ী)। কিন্তু সেটাই transition-এর সময় F কে ধরে রাখে।

উদাহরণ

একটা সম্পূর্ণ ডিজাইন — 7-segment decoder

সমস্যা: ৪-bit BCD input (০–৯) নিয়ে একটা 7-segment display চালানো।

     ─a─
    │   │
    f   b
    │   │
     ─g─
    │   │
    e   c
    │   │
     ─d─

শুধু segment a -এর জন্য ডিজাইন করি।

Truth table — কোন অঙ্কে a জ্বলবে:

অঙ্কABCDa
000001
100010
200101
300111
401000
501011
601101
701111
810001
910011
10–15X

a=∑m(0,2,3,5,6,7,8,9)+∑d(10,11,12,13,14,15)a = \sum m(0,2,3,5,6,7,8,9) + \sum d(10,11,12,13,14,15)

K-map:

       CD
     00   01   11   10
   ┌────┬────┬────┬────┐
AB 00│ 1  │ 0  │ 1  │ 1  │
   ├────┼────┼────┼────┤
 01│ 0  │ 1  │ 1  │ 1  │
   ├────┼────┼────┼────┤
 11│ X  │ X  │ X  │ X  │
   ├────┼────┼────┼────┤
 10│ 1  │ 1  │ X  │ X  │
   └────┴────┴────┴────┘

দল বাঁধা (don’t-care গুলো সুবিধামতো ১ ধরে):

দলঘরTerm
নিচের দুই rowAB = 1xA
ডান দুই কলাম, মাঝের দুই rowAB=01,11 আর CD=11,10BC
01+11 কলাম, row 01,11BD
চার কোণCD=00,10 আর AB=00,10B'D'
মাঝের ব্লকCD

a=A+C+BD+B′D′a = A + C + BD + B'D'

যাচাই করুন: অঙ্ক ১ (0001) → A=0, B=0, C=0, D=1

  • A = 0
  • C = 0
  • BD = 0·1 = 0
  • B'D' = 1·0 = 0

a = 0 ✓ (১ লিখতে উপরের দাগ লাগে না)

অঙ্ক ৪ (0100) → A=0, B=1, C=0, D=0

  • B'D' = 0·1 = 0, BD = 1·0 = 0, A = C = 0

a = 0 ✓

Canonical form-এ লাগত আটটা 4-input AND + একটা 8-input OR। Minimized-এ চারটা term, সর্বোচ্চ 2-input।

এই একই কাজ সাতটা segment-এর জন্য করলে একটা সম্পূর্ণ decoder হয় — আর এটাই 7447 IC-র ভেতরে আছে (১৯৭০-এর দশক থেকে)।

Level 2-এ আমরা এটা Verilog-এ লিখব আর synthesis tool-এর আউটপুট আমাদের হাতের ফলাফলের সাথে মেলাব।

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

EXPERIMENT

Compiler-ও Boolean minimization করে

Linux / macOS, gcc বা clang· ১৫ মিনিট

boolmin.c:

#include <stdbool.h>

/* canonical SOP — চারটা term */
bool f_canonical(bool A, bool B, bool C) {
    return (!A && !B && C) || (!A && B && C) ||
           ( A && !B && C) || ( A && B && C);
}

/* হাতে minimize করা — শুধু C */
bool f_minimal(bool A, bool B, bool C) {
    (void)A; (void)B;
    return C;
}

/* আরেকটা: F = A' + C */
bool g_canonical(bool A, bool B, bool C) {
    return (!A && !B && !C) || (!A && !B && C) ||
           (!A &&  B && !C) || (!A &&  B && C) ||
           ( A && !B &&  C) || ( A &&  B && C);
}

bool g_minimal(bool A, bool B, bool C) {
    (void)B;
    return !A || C;
}
gcc -O2 -S -masm=intel -o boolmin.s boolmin.c
for fn in f_canonical f_minimal g_canonical g_minimal; do
  echo "=== $fn ==="
  awk "/^${fn}:/,/ret/" boolmin.s | grep -v '^\s*\.'
done

-O2-তে f_canonical আর f_minimal প্রায় নিশ্চিতভাবে অভিন্ন assembly দেবে:

f_canonical:
        mov     eax, edx        ; শুধু তৃতীয় argument
        ret

Compiler নিজেই বুঝে ফেলেছে চারটা term মিলে শুধু C।

g_canonical -এও একই — ছয়টা term থেকে দুইটা instruction।

Instruction গুনুন:

for fn in f_canonical f_minimal g_canonical g_minimal; do
  n=$(awk "/^${fn}:/,/ret/" boolmin.s | grep -cE '^\s+[a-z]')
  printf "%-14s %d instruction\n" "$fn" "$n"
done

এবার -O0-তে দেখুন পার্থক্যটা:

gcc -O0 -S -masm=intel -o boolmin_O0.s boolmin.c
awk '/^f_canonical:/,/ret/' boolmin_O0.s | grep -cE '^\s+[a-z]'

Optimization ছাড়া f_canonical -এ ৩০+ instruction। -O2-তে ২টা।

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

আপনি যে K-map হাতে করছেন, compiler সেটাই যান্ত্রিকভাবে করে — এবং assembly-তে instruction সংখ্যা কমে যায়।

EXPERIMENT

Yosys দিয়ে সত্যিকারের synthesis

Linux / macOS (Yosys দরকার)· ২০ মিনিট
# ইনস্টল
brew install yosys          # macOS
sudo apt install yosys      # Debian/Ubuntu

bool.v:

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

module f_minimal(input A, B, C, output F);
  assign F = C;
endmodule

module seg_a_naive(input A, B, C, D, output Y);
  assign Y = (~A&~B&~C&~D) | (~A&~B& C&~D) | (~A&~B& C& D) |
             (~A& B&~C& D) | (~A& B& C&~D) | (~A& B& C& D) |
             ( A&~B&~C&~D) | ( A&~B&~C& D);
endmodule

module seg_a_min(input A, B, C, D, output Y);
  assign Y = A | C | (B & D) | (~B & ~D);
endmodule
for m in f_canonical f_minimal seg_a_naive seg_a_min; do
  echo "=========== $m ==========="
  yosys -q -p "read_verilog bool.v; hierarchy -top $m; \
               proc; opt; techmap; opt; abc -g AND,OR,NAND,NOR,NOT; \
               opt; stat" 2>&1 | grep -A 20 "Printing statistics"
done

আউটপুটে প্রতিটা gate type-এর সংখ্যা দেখাবে:

=========== f_canonical ===========
   Number of cells:                  1
     $_BUF_                          1

=========== f_minimal ===========
   Number of cells:                  1
     $_BUF_                          1

দুইটাই একই — Yosys-এর abc pass minimization করে ফেলেছে।

7-segment-এর ক্ষেত্রে:

=========== seg_a_naive ===========
   Number of cells:                  6

=========== seg_a_min ===========
   Number of cells:                  5

কাছাকাছি, কারণ tool ভালো কাজ করে। কিন্তু সবসময় নয় — বড় circuit-এ মানুষের কাঠামোগত অন্তর্দৃষ্টি (কীভাবে factor করবেন) tool-এর চেয়ে ভালো ফল দিতে পারে।

ছাড়াই minimization দেখুন:

yosys -q -p "read_verilog bool.v; hierarchy -top seg_a_naive; \
             proc; techmap; stat"      # opt ছাড়া

opt আর abc বাদ দিলে অনেক বেশি gate — এটাই optimization-এর প্রকৃত অবদান।

Level 2-এ আমরা Yosys দিয়ে একটা সম্পূর্ণ ALU synthesize করব।

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

Hardware synthesis tool-ও একই minimization করে, কিন্তু gate সংখ্যা সরাসরি রিপোর্ট করে — তাই আপনার হাতের K-map-এর ফলাফল সংখ্যা দিয়ে যাচাই করা যায়।

নিজে বানান

BUILD IT

Quine–McCluskey Minimizer

Python · ●●●●○
  1. Minterm-দের binary রূপে রাখুন, don not-care সহ
  2. যে জোড়াগুলো এক bit-এ আলাদা তাদের মিলিয়ে prime implicant বানান
  3. Prime implicant chart বানিয়ে essential গুলো বাছুন
  4. বাকি minterm ঢাকতে greedy cover করুন
  5. K-map-এ হাতে করা ফলাফলের সাথে মেলান

Quine–McCluskey হলো K-map-এর algorithmic রূপ — যেকোনো সংখ্যক variable-এ কাজ করে।

from itertools import combinations


def combine(a, b):
    """ঠিক এক position-এ আলাদা হলে মিলিয়ে '-' বসান"""
    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, names="ABCD"):
    if not minterms:
        return "0", []
    if len(set(minterms) | set(dontcares)) == 2 ** nbits:
        return "1", []

    primes = prime_implicants(minterms, dontcares, nbits)
    targets = [format(m, f'0{nbits}b') for m in minterms]   # don't-care ঢাকতে হবে না

    # ── chart: কোন prime কোন minterm ঢাকে ──
    chart = {m: [p for p in primes if covers(p, m)] for m in targets}

    # ── essential prime implicant ──
    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)}

    # ── greedy: বাকিগুলো ঢাকুন ──
    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 format_sop(chosen, names), sorted(chosen)


def format_sop(implicants, names):
    if not implicants: return "0"
    terms = []
    for imp in sorted(implicants):
        lits = [names[i] if b == '1' else f"{names[i]}'"
                for i, b in enumerate(imp) if b != '-']
        terms.append(''.join(lits) if lits else "1")
    return " + ".join(sorted(terms, key=len))


def truth_table_check(expr_fn, minterms, dontcares, nbits):
    """minimize-এর ফল সত্যিই একই function কি না যাচাই"""
    ok = True
    for m in range(2 ** nbits):
        if m in dontcares: continue
        bits = [(m >> (nbits-1-i)) & 1 for i in range(nbits)]
        expected = 1 if m in minterms else 0
        if expr_fn(*bits) != expected:
            print(f"  গরমিল m={m}: চাই {expected}, পেলাম {expr_fn(*bits)}")
            ok = False
    return ok


def make_evaluator(implicants, nbits):
    def f(*bits):
        for imp in implicants:
            if all(b == '-' or int(b) == bits[i] for i, b in enumerate(imp)):
                return 1
        return 0
    return f


# ── পরীক্ষা ──────────────────────────────────────────────────
cases = [
    ("F = Σm(1,3,5,7)",          [1,3,5,7],            [],                3, "ABC"),
    ("F = Σm(0,1,2,3,4,5,6,7)",  list(range(8)),       [],                3, "ABC"),
    ("F = Σm(0,1,2,3,5,7)",      [0,1,2,3,5,7],        [],                3, "ABC"),
    ("7-seg 'a'",                [0,2,3,5,6,7,8,9],    list(range(10,16)),4, "ABCD"),
    ("F = Σm(0,2,5,7,8,10,13,15)",[0,2,5,7,8,10,13,15],[],                4, "ABCD"),
]

for name, mt, dc, n, names in cases:
    expr, imps = minimize(mt, dc, n, names)
    f = make_evaluator(imps, n)
    valid = truth_table_check(f, set(mt), set(dc), n)
    lits = sum(1 for imp in imps for b in imp if b != '-')
    print(f"\n{name}")
    print(f"  minterm      : {mt}")
    if dc: print(f"  don't-care   : {dc}")
    print(f"  minimized    : {expr}")
    print(f"  term = {len(imps)}, literal = {lits}")
    print(f"  যাচাই        : {'সঠিক' if valid else 'ভুল'}")

প্রত্যাশিত আউটপুট:

F = Σm(1,3,5,7)
  minimized    : C
  term = 1, literal = 1
  যাচাই        : সঠিক

F = Σm(0,1,2,3,4,5,6,7)
  minimized    : 1
  ...

7-seg 'a'
  minimized    : A + C + BD + B'D'
  term = 4, literal = 6
  যাচাই        : সঠিক

শেষটা লক্ষ্য করুন — আমাদের হাতে করা K-map-এর ফলাফলের সাথে হুবহু মিলেছে।

নিজে বাড়ান:

  1. POS রূপও বের করুন (0-minterm নিয়ে একই algorithm চালিয়ে ফলাফল complement করুন), আর ছোটটা বাছুন
  2. Petrick’s method যোগ করুন — greedy-র বদলে প্রমাণিত minimal cover
  3. Multi-output minimization — একাধিক function একসাথে, term share করে
  4. NAND-only রূপে রূপান্তর করুন আর transistor সংখ্যা গুনুন
  5. Static hazard detect করুন — কোন দুইটা দল পাশাপাশি কিন্তু overlap করে না, সেখানে redundant term যোগ করুন
  6. আপনার minimizer-এর ফলাফল Yosys-এর abc -এর সাথে তুলনা করুন

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

Boolean minimization যেখানে চলছে

EDA tool। Synopsys Design Compiler, Cadence Genus, আর open-source Yosys — প্রতিটা chip-এর প্রতিটা module এই minimization-এর মধ্য দিয়ে যায়। একটা আধুনিক CPU-তে বিলিয়ন gate; ১% সাশ্রয় মানে কোটি gate।

FPGA synthesis। FPGA-তে logic থাকে LUT (lookup table) আকারে — সাধারণত ৬-input। Synthesis-এর কাজ হলো আপনার Boolean function-কে যত কম LUT-এ ফেলা যায়। Xilinx Vivado, Intel Quartus এটাই করে।

Compiler-এর instruction selection। LLVM-এর InstCombine আর DAGCombine pass আক্ষরিকভাবে Boolean rewriting করে — এই লেসনের নিয়মগুলো C++ pattern হিসেবে লেখা।

Database query optimization। WHERE clause-এর predicate CNF-এ এনে redundant শর্ত বাদ দেওয়া, contradiction ধরা (x > 5 AND x \< 3 → কখনো সত্য নয় → পুরো query খালি)।

SAT solver-এর preprocessing। Formula ছোট করা solving-এর আগে — variable elimination, subsumption, self-subsuming resolution। প্রায়ই এই preprocessing-ই সমাধানের বেশিরভাগ কাজ করে।

Firewall rule optimization। হাজারো rule-কে সমতুল্য কিন্তু ছোট rule set-এ রূপান্তর, যাতে প্রতিটা packet কম তুলনায় প্রক্রিয়া হয়।

Feature flag evaluation। জটিল targeting rule (country = BD AND (plan = pro OR beta_tester) AND NOT churned) minimize করলে প্রতিটা request-এ কম কাজ।

Formal verification। দুইটা circuit সমতুল্য কি না — equivalence checking। এটাই নিশ্চিত করে যে optimization আচরণ বদলায়নি। Intel প্রতিটা chip-এ এটা করে (Pentium FDIV-এর পর থেকে)।

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

“Boolean algebra আর propositional logic আলাদা দুইটা বিষয়।”

এরা একই গাণিতিক কাঠামো — শুধু সংকেত আর উদ্দেশ্য আলাদা।

Propositional logicBoolean algebra
প্রশ্নএটা কি সত্য?সবচেয়ে কম gate-এ কীভাবে?
সংকেত∧ ∨ ¬ T F· + ' 1 0
ক্ষেত্রদর্শন, গণিত, verificationcircuit, hardware

আরো সাধারণভাবে, দুটোই Boolean lattice-এর উদাহরণ — আর set algebra (∩ ∪ ')-ও তাই।

তিনটার নিয়ম হুবহু এক, কারণ তিনটাই একই বিমূর্ত কাঠামোর ভিন্ন মডেল।

এটা কেন জানা দরকার: একটা কাঠামো শিখলে তিনটা ক্ষেত্রেই কাজে লাগে। আর যখন আপনি একটা SQL WHERE clause optimize করছেন, তখন আপনি আসলে circuit minimization-এর একই বীজগণিত প্রয়োগ করছেন।

“কম gate মানেই ভালো circuit।”

Gate সংখ্যা তিনটা metric-এর একটা মাত্র।

Metricকী মাপে
Areagate/transistor সংখ্যা
Delaycritical path-এর gate depth
Powerswitching activity

আর এগুলো প্রায়ই পরস্পরবিরোধী।

Two-level SOP সবচেয়ে দ্রুত (depth ২) কিন্তু সবচেয়ে বড়। Multi-level factored ছোট কিন্তু ধীর।

একটা বাস্তব উদাহরণ: ৩২-bit adder

ধরনGateDepth
Ripple carry~160~64
Carry lookahead~500~10
Carry select~700~12

Carry-lookahead তিনগুণ বেশি gate ব্যবহার করে, কিন্তু ছয় গুণ দ্রুত। CPU-তে সেটাই ব্যবহার হয়, কারণ clock speed সবচেয়ে গুরুত্বপূর্ণ।

কিন্তু একটা low-power IoT chip-এ? সেখানে ripple carry-ই ঠিক।

উপসংহার: “optimal” প্রশ্নটার উত্তর নেই যতক্ষণ না বলা হয় কীসের জন্য optimal। Software-এর -O2 বনাম -Os -এর হুবহু একই কথা।

“K-map শেখা অপ্রয়োজনীয়, tool তো আছেই।”

হাতে ৩২-variable minimize করা অপ্রয়োজনীয়, সত্যি। কিন্তু K-map শেখার তিনটা আসল কারণ আছে:

১. Tool কী করছে বোঝা। Synthesis report-এ যখন দেখবেন আপনার ৫০-লাইনের Verilog ৩টা gate-এ নেমে গেছে, তখন কেন হলো সেটা বোঝা দরকার — নাহলে আপনি tool-কে বিশ্বাস করতে পারবেন না, আর ভুল ধরতেও পারবেন না।

২. Don’t-care-এর সিদ্ধান্ত। Tool জানে না কোন input অসম্ভব — সেটা আপনি বলে দেন। আর সেই সিদ্ধান্তটা minimization-এ সবচেয়ে বড় প্রভাব ফেলে।

৩. Hazard। Tool functional correctness নিশ্চিত করে, কিন্তু glitch নিয়ে সবসময় ভাবে না। Asynchronous পথে glitch ধরা আপনার কাজ, আর সেটা K-map-এ দৃশ্যমান।

আর সবচেয়ে গুরুত্বপূর্ণ — এই একই যুক্তি software-এ প্রতিদিন লাগে। একটা জটিল if condition সরল করা, একটা query predicate factor করা, একটা feature flag rule ছাঁটা — সবই হাতে করা Boolean minimization।

“Don't-care মানে output অপ্রাসঙ্গিক।”

Don’t-care মানে সেই input combination কখনো ঘটবে না।

যদি ঘটে যায়, output অনির্দিষ্ট — আর সেটা বিপর্যয়কর হতে পারে।

বাস্তব উদাহরণ: একটা state machine-এ ৫টা state, ৩ bit দিয়ে encode করা। 101, 110, 111 — এই তিনটা “অসম্ভব” ধরে don’t-care করা হলো।

এখন একটা cosmic ray বা power glitch যদি state register-কে 110 -তে ফেলে দেয়? Machine এমন একটা অবস্থায় যাবে যার আচরণ কেউ ডিজাইন করেনি — সম্ভবত সেখানেই আটকে থাকবে।

Safety-critical design-এ তাই নিয়ম: don’t-care ব্যবহার করবেন না; বরং সব অব্যবহৃত state থেকে একটা নিরাপদ state-এ ফেরার পথ রাখুন।

always @(*) case (state)
    IDLE:    next = ...;
    RUNNING: next = ...;
    DONE:    next = ...;
    default: next = IDLE;      // don't-care নয় — নিরাপদ recovery
endcase

Software-এ হুবহু সমতুল্য: switch-এ default case, আর undefined behaviour-এর উপর নির্ভর না করা।

C-তে signed overflow “don’t care” (UB), আর compiler সেটা কাজে লাগিয়ে optimize করে — ফলে যে কোড আপনি “কাজ করে” ভাবতেন সেটা -O2-তে ভেঙে যায়। একই গাণিতিক ধারণা, একই বিপদ।

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

1

Boolean algebra দিয়ে সরল করুন: F = AB + AB'C + A'BC

প্রয়োগ
F = AB + AB'C + A'BC
  = A(B + B'C) + A'BC                 [A common]
  = A(B + C) + A'BC                   [B + B'C = B + C, distribution]
  = AB + AC + A'BC                    [distribute]
  = AB + A'BC + AC                    [সাজানো]
  = B(A + A'C) + AC                   [B common]
  = B(A + C) + AC                     [A + A'C = A + C]
  = AB + BC + AC

চূড়ান্ত: F = AB + BC + AC

এটা majority function — তিনটার অন্তত দুইটা সত্য হলে সত্য।

K-map দিয়ে যাচাই:

F = Σm(3, 5, 6, 7)

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

তিনটা জোড়া:

  • m3, m7 (কলাম 11) → BC
  • m5, m7 (row A=1, কলাম 01,11) → AC
  • m6, m7 (row A=1, কলাম 11,10) → AB

F = AB + BC + AC ✓

গুরুত্বপূর্ণ পর্যবেক্ষণ — এই তিনটা term-এর একটাও বাদ দেওয়া যায় না। প্রতিটাই একটা করে minterm একা ঢাকে (m3 শুধু BC, m5 শুধু AC, m6 শুধু AB)। তিনটাই essential prime implicant।

Majority function কোথায় ব্যবহার হয়:

  • Full adder-এর carry-out — ঠিক এই function
  • Triple Modular Redundancy (TMR) — তিনটা redundant system-এর ভোট। মহাকাশযান আর পারমাণবিক নিয়ন্ত্রণে ব্যবহৃত, কারণ একটা component fail করলেও সঠিক আউটপুট আসে
  • Consensus protocol — quorum-ভিত্তিক ভোট, Level 9-এ
  • Error correction — bit-level voting
2

কেন K-map-এ দল সবসময় দুইয়ের ঘাত আকারের (১, ২, ৪, ৮) হতে হয়? তিনটা ঘরের দল কেন হয় না?

যুক্তি

কারণ প্রতিবার দলের আকার দ্বিগুণ করলে ঠিক একটা variable বাদ যায় — আর সেটা শুধু তখনই সম্ভব যখন সেই variable তার দুইটা মান (০ এবং ১) দলের ভেতরে সমানভাবে উপস্থিত।

উদাহরণ — দুইটা ঘর:

A'BC  +  ABC  =  BC(A' + A)  =  BC · 1  =  BC

A বাদ গেল, কারণ দলের ভেতরে A = 0 আর A = 1 দুটোই আছে।

চারটা ঘর → দুইটা variable বাদ। আটটা → তিনটা।

সাধারণভাবে 2ᵏ ঘরের দল থেকে k টা variable বাদ যায়।

তিনটা ঘর কেন হয় না:

তিনটা ঘরের একটা দলে কোনো variable-ই তার দুইটা মানে সমানভাবে থাকবে না। যেমন A'B'C, A'BC, ABC মিলে:

A'B'C + A'BC + ABC
= A'C(B' + B) + ABC
= A'C + ABC

সরল হলো, কিন্তু একটা term-এ নামল না — দুইটা term থেকে গেল।

তিনটা ঘরকে ঢাকতে হলে দুইটা overlapping দল লাগবে:

  • A'B'C, A'BC → A'C
  • A'BC, ABC → BC

F = A'C + BC — দুইটা term, কিন্তু প্রতিটা ছোট।

গভীর কারণ: একটা 2ᵏ-ঘরের দল একটা subcube — Boolean hypercube-এর একটা k-মাত্রিক মুখ। শুধু hypercube-এর প্রকৃত মুখগুলোই একটা product term হিসেবে প্রকাশযোগ্য।

৩-variable-এর Boolean function-কে একটা ঘনকের আটটা কোণ ভাবুন।

  • ১ কোণ = একটা minterm (৩ literal)
  • ১ ধার (২ কোণ) = ২ literal
  • ১ মুখ (৪ কোণ) = ১ literal
  • পুরো ঘনক (৮ কোণ) = ধ্রুবক ১

তিনটা কোণ ঘনকের কোনো মুখ বা ধার নয় — তাই একটা term-ও নয়।

আর দলগুলো “সংলগ্ন” হতে হয় কেন: কারণ K-map-এর Gray code ক্রমে পাশাপাশি ঘর ঠিক এক bit-এ আলাদা — অর্থাৎ hypercube-এ তারা একটা ধার দিয়ে যুক্ত। এলোমেলো ঘর নিলে সেই সম্পর্কটা থাকে না।

3

আপনি একটা 4-bit input থেকে “এই সংখ্যাটা মৌলিক কি না” detector বানাচ্ছেন (০–১৫)। Truth table বানিয়ে minimize করুন।

ডিজাইন

০–১৫ -এর মৌলিক: 2, 3, 5, 7, 11, 13

(১ মৌলিক নয়, ০ মৌলিক নয়)

F=∑m(2,3,5,7,11,13)F = \sum m(2, 3, 5, 7, 11, 13)

K-map (A = MSB, D = LSB):

       CD
     00   01   11   10
   ┌────┬────┬────┬────┐
AB 00│ 0  │ 0  │ 1  │ 1  │   0,1,3,2
   ├────┼────┼────┼────┤
 01│ 0  │ 1  │ 1  │ 0  │   4,5,7,6
   ├────┼────┼────┼────┤
 11│ 0  │ 1  │ 0  │ 0  │   12,13,15,14
   ├────┼────┼────┼────┤
 10│ 0  │ 0  │ 1  │ 0  │   8,9,11,10
   └────┴────┴────┴────┘

দল বাঁধা:

দলঘরTerm
m3, m7AB=00,01 আর CD=11A'CD
m3, m11AB=00,10 আর CD=11B'CD
m5, m7AB=01, CD=01,11A'BD
m5, m13AB=01,11 আর CD=01BC'D
m2, m3AB=00, CD=11,10A'B'C

সব minterm ঢাকতে দরকার:

  • m2 শুধু A'B'C -এ → essential
  • m11 শুধু B'CD -এ → essential
  • m13 শুধু BC'D -এ → essential
  • m3 ঢাকা পড়েছে A'B'C আর B'CD দিয়ে ✓
  • m5 ঢাকা পড়েছে BC'D দিয়ে ✓
  • m7 — এখনো বাকি। A'CD বা A'BD লাগবে।

F=A′B′C+B′CD+BC′D+A′BDF = A'B'C + B'CD + BC'D + A'BD

চারটা term, ১৪টা literal।

যাচাই — m7 (0111): A=0,B=1,C=1,D=1

  • A'B'C = 1·0·1 = 0
  • B'CD = 0·1·1 = 0
  • BC'D = 1·0·1 = 0
  • A'BD = 1·1·1 = 1 ✓

m9 (1001, ৯ — মৌলিক নয়): A=1,B=0,C=0,D=1

  • সব term-এ কমপক্ষে একটা factor ০ → F = 0 ✓
4

F = AB + A'C -এ static hazard আছে। BC যোগ করলে কেন সেটা দূর হয়, যদিও BC গাণিতিকভাবে অপ্রয়োজনীয়?

যুক্তি

প্রথমে দেখি BC কেন অপ্রয়োজনীয় (consensus theorem):

AB + A'C + BC = AB + A'C

প্রমাণ:

BC = BC(A + A')          [A + A' = 1]
   = ABC + A'BC
   = AB·C + A'C·B

দুইটাই ইতিমধ্যে ঢাকা (ABC ⊆ AB, A'BC ⊆ A'C)। তাই absorption-এ মুছে যায়।

তাহলে hazard কোথায়:

B = C = 1 ধরুন। তখন:

  • AB = A
  • A'C = A'
  • F = A + A' = 1 — সবসময়

গাণিতিকভাবে F কখনো 0 হবে না।

কিন্তু বাস্তবে A' আসে একটা inverter থেকে, যার নিজের delay আছে। A যখন 1 → 0 বদলায়:

সময় →     t0        t1        t2
A         1 ────────→ 0 ─────────
A'        0 ──────────────→ 1        ← inverter delay
AB        1 ────────→ 0
A'C       0 ──────────────→ 1
F         1 ────────→ 0 ──→ 1        ← glitch!

t1 আর t2-এর মাঝে দুইটা term-ই ০ — তাই F মুহূর্তের জন্য 0।

BC কীভাবে বাঁচায়:

B = C = 1 হলে BC = 1 — আর এটা A-এর উপর নির্ভরই করে না।

তাই A যতই transition করুক, BC স্থিরভাবে 1 ধরে রাখে, আর OR gate-এর output কখনো নামে না।

AB        1 ────────→ 0
A'C       0 ──────────────→ 1
BC        1 ─────────────────────    ← স্থির, glitch ঢেকে দেয়
F         1 ─────────────────────

K-map-এ hazard চেনা:

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

AB দল: m6, m7 (নিচের ডান) A'C দল: m1, m3 (উপরের মাঝ)

m3 আর m7 পাশাপাশি (একটা bit আলাদা — শুধু A), কিন্তু একই দলে নেই। এই সীমানা পার হওয়ার সময়ই glitch।

BC দল (m3, m7) ঠিক সেই সীমানাটা ঢেকে দেয়।

সাধারণ নিয়ম: K-map-এ দুইটা সংলগ্ন 1 যদি কোনো একটা সাধারণ দলে না পড়ে, সেখানে static-1 hazard আছে। একটা overlapping দল যোগ করে ঢেকে দিন।

কেন এটা গুরুত্বপূর্ণ:

Synchronous circuit-এ (clock-চালিত) glitch সাধারণত ক্ষতি করে না — flip-flop শুধু clock edge-এ sample করে, ততক্ষণে সিগন্যাল স্থির।

কিন্তু বিপজ্জনক যেখানে:

  • Asynchronous logic
  • Clock বা reset line-এ (একটা glitch = একটা ভুয়া clock pulse)
  • Latch-এর enable-এ
  • Level-sensitive interrupt line-এ

Software-এ সমতুল্য: একটা মান দুইটা source থেকে হিসাব হলে আর তাদের update সময়ে অসমন্বয় থাকলে, মধ্যবর্তী মুহূর্তে inconsistent state দেখা যায় — distributed system-এ এটাই read-your-writes সমস্যা।

5

F = A ⊕ B ⊕ C (তিন-input XOR) কে SOP আকারে লিখুন। এটা কি K-map দিয়ে minimize করা যায়?

প্রয়োগ

XOR সত্য যখন বিজোড় সংখ্যক input সত্য।

ABC# of 1sF
00000
00111
01011
01120
10011
10120
11020
11131

F=∑m(1,2,4,7)=A′B′C+A′BC′+AB′C′+ABCF = \sum m(1, 2, 4, 7) = A'B'C + A'BC' + AB'C' + ABC

K-map:

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

দাবাবোর্ডের প্যাটার্ন। কোনো দুইটা 1 পাশাপাশি নেই — প্রতিটা 1-এর চারপাশে শুধু 0।

তাই কোনো দল বাঁধা যায় না, আর SOP আকারে minimize করা অসম্ভব। চারটা term-ই থাকতে হবে।

এটাই XOR-এর মৌলিক বৈশিষ্ট্য: একটা input বদলালেই output বদলায়, তাই কোনো দুইটা সংলগ্ন ঘর একই মান পায় না।

তাহলে hardware-এ XOR কীভাবে বানানো হয়?

উপায় ১ — XOR gate কে primitive ধরা:

F = A ⊕ B ⊕ C = (A ⊕ B) ⊕ C

দুইটা 2-input XOR gate, depth ২।

উপায় ২ — CMOS-এ সরাসরি: XOR-এর একটা transmission-gate বাস্তবায়ন আছে যা মাত্র ৬-৮ transistor নেয়, SOP-এর ২৪+ transistor-এর তুলনায়।

কেন এটা গুরুত্বপূর্ণ:

XOR সর্বত্র:

ব্যবহারকেন XOR
Adder-এর sum bitsum = a ⊕ b ⊕ cin
Parity checkবিজোড়/জোড় গোনা
RAID 5parity = d1 ⊕ d2 ⊕ … ⊕ dn
CRCpolynomial division
Cryptographycipher = plain ⊕ key
Gray codeপরপর মান এক bit আলাদা
Swap without tempa^=b; b^=a; a^=b

এত ঘন ঘন লাগে বলেই chip designer XOR-কে একটা standard cell হিসেবে রাখেন — AND/OR-এ ভাঙেন না।

একটা সাধারণীকরণ: n-input XOR-এর SOP-এ সবসময় 2^(n-1) টা minterm থাকে, আর কোনোটাই মেলানো যায় না। তাই SOP আকার exponential, কিন্তু XOR-চেইন আকার linear।

পাঠ: সঠিক primitive বাছাই minimization-এর চেয়েও বেশি গুরুত্বপূর্ণ হতে পারে। AND/OR/NOT-এর জগতে XOR ব্যয়বহুল; XOR-কে primitive ধরলে সস্তা।

Level 2-এ আমরা XOR-এর transistor-স্তরের বাস্তবায়ন দেখব, আর Level 3-এ দেখব adder-এ এটা কীভাবে ব্যবহৃত হয়।

এরপর কী

Boolean algebra দিয়ে আমরা logic-কে circuit-এর দোরগোড়ায় পৌঁছে দিলাম। Level 2-এ এই gate-গুলো transistor দিয়ে বানানো হবে।

কিন্তু তার আগে আরো তিনটা গাণিতিক হাতিয়ার:

  • Number systems ও modular arithmetic — base conversion, GCD, মৌলিক সংখ্যা। Level 1-এ binary representation আর Level 10-এ RSA — দুটোরই ভিত্তি।
  • Linear algebra — vector আর matrix। Graphics, ML, PageRank আর signal processing-এর ভাষা।
  • Asymptotic notation — O, Θ, Ω আনুষ্ঠানিকভাবে, আর কখন এই বিমূর্তকরণ বিভ্রান্ত করে।

তারপর Level 0 শেষ, আর আমরা bit-এর জগতে নামব।

আরও পড়ুন

  • Digital Design and Computer Architecture — Harris and Harris · Level 2-এর প্রধান বই; এই অধ্যায়টা তার ভূমিকা
  • The Art of Computer Programming, Vol 4A §7.1 — Donald Knuth · Boolean function-এর গভীরতম আলোচনা