Adder Circuit — গণিত থেকে সিলিকনে যোগফল

আগে এটা বুঝি

computer-representation/unsigned-integers লেসনে আমরা প্রমাণ করেছিলাম: n-bit unsigned addition আসলে arithmetic mod 2ⁿ — কাগজে-কলমে carry-column addition করে, তারপর overflow হলে mod 2ⁿ reduce করে। সেই লেসনটা ছিল বিশুদ্ধ গণিত: সংখ্যা, carry, আর একটা modular সূত্র।

এই লেসনে আমরা সেই একই জিনিসটা তার বানাই। প্রশ্ন এখন আর “a + b mod 2ⁿ কত?” না — প্রশ্ন হলো: কয়েকটা gate সাজিয়ে এমন একটা circuit বানানো যায় যেটা যেকোনো দুইটা bit pattern নিলে, সবসময়, সঠিক sum আর carry বের করে দেবে?

উত্তরটা আশ্চর্যজনকভাবে ছোট — মাত্র দুইটা gate দিয়ে শুরু হয়, আর সেখান থেকে চেইন করেই একটা ৬৪-bit CPU adder পর্যন্ত পৌঁছানো যায়। কিন্তু সেই চেইনিং-এর একটা গোপন খরচ আছে — আর সেই খরচ কমানোর গল্পটাই এই লেসনের দ্বিতীয়ার্ধ।

মূল ধারণা

Half-adder — দুইটা bit, দুইটা gate

সবচেয়ে ছোট প্রশ্ন দিয়ে শুরু করি: দুইটা single bit, A আর B, যোগ করলে কী হয়? সাধারণ দশমিক যোগের মতোই — একটা sum digit আর সম্ভবত একটা carry।

Truth table

A	B	Sum	Carry
0	0	0	0
0	1	1	0
1	0	1	0
1	1	0	1

লক্ষ্য করুন 1 + 1 = 10 (বাইনারিতে ২) — একটা bit-এ আঁটে না, তাই Sum = 0, Carry = 1।

Minimization — আসলে করারই কিছু নেই

Sum column-টা চিনতে পারছেন? এটা ঠিক আগের লেসনের ২-input parity — Sum = A ⊕ B। K-map বসালে checkerboard প্যাটার্ন (0,1,1,0) — কোনো adjacent grouping নেই, তাই SOP-এ এটা simplify হয় না। সৌভাগ্যক্রমে XOR সরাসরি একটা primitive gate — কোনো SOP বানানোর দরকারই নেই।

Carry column আরো সহজ — এটা ঠিক AND-এর truth table। Carry = A · B।

$\text{Sum} = A \oplus B \qquad \text{Carry} = A \cdot B$

মাত্র দুইটা gate — একটা XOR, একটা AND — কোনো minimization algorithm ছাড়াই, কারণ দুইটা output-ই ইতিমধ্যে তাদের সবচেয়ে সরল রূপে।

      ┌─────┐
A ────┤     │
      │ XOR ├──── Sum
B ──┬─┤     │
    │ └─────┘
    │ ┌─────┐
    └─┤     │
A ────┤ AND ├──── Carry
      └─────┘

Half-adder — সম্পূর্ণ schematic, মাত্র দুইটা gate।

Half-adder-এর সীমাবদ্ধতা — নাম থেকেই বোঝা যায়

নামটাই ইঙ্গিত দেয় — এটা “অর্ধেক” adder। এতে carry-in নেওয়ার কোনো input নেই। তাই দুইটা মাত্র bit যোগ করা যায়, কোনো আগের স্তর থেকে আসা carry গ্রহণ করার উপায় নেই। একটা multi-bit adder-এ প্রথম (সবচেয়ে কম গুরুত্বপূর্ণ) bit ছাড়া বাকি সব bit-এই carry-in লাগবে — সেই জন্যই আমাদের একটা তৃতীয় input দরকার, আর তার নাম full-adder।

Full-adder — তিনটা input, দুইটা output

এবার বাস্তব সমস্যা: n-bit যোগ করতে গেলে প্রতিটা bit-position-এ তিনটা জিনিস যোগ করতে হয় — Aᵢ, Bᵢ, আর আগের position থেকে আসা Carry-in। Half-adder এই তৃতীয়টা নিতে পারে না।

Truth table

তিনটা input (A, B, Cin), দুইটা output (Sum, Cout) — ৮টা row:

A	B	Cin	Sum	Cout
0	0	0	0	0
0	0	1	1	0
0	1	0	1	0
0	1	1	0	1
1	0	0	1	0
1	0	1	0	1
1	1	0	0	1
1	1	1	1	1

হাতে যাচাই — প্রতিটা row আসলে A + B + Cin-এর বাইনারি যোগফল: 1+1+1 = 11₂ = 3, অর্থাৎ Sum=1, Cout=1 (শেষ row) ✓। 0+1+1 = 10₂ = 2, Sum=0, Cout=1 (চতুর্থ row) ✓।

Sum — আবার সেই parity

Sum কলামের minterm: Σm(1,2,4,7)। এটা হুবহু আগের লেসনের ৩-input parity function — Sum = A ⊕ B ⊕ Cin। K-map চেষ্টা করলে আবারও checkerboard — কোনো grouping সম্ভব না। XOR-ই একমাত্র সরল পথ।

Cout — majority function-এর প্রত্যাবর্তন

Cout কলামের minterm: Σm(3,5,6,7)।

        B,Cin
      00   01   11   10
    ┌────┬────┬────┬────┐
A 0 │ 0  │ 0  │ 1  │ 0  │   ← m3
    ├────┼────┼────┼────┤
  1 │ 0  │ 1  │ 1  │ 1  │   ← m5, m7, m6
    └────┴────┴────┴────┘

তিনটা জোড়া, প্রতিটা m7-কে ঘিরে (আগের লেসনের ভোটিং circuit-এর মতোই প্যাটার্ন):

জোড়া	Term
`m3, m7`	`B·Cin`
`m5, m7`	`A·Cin`
`m6, m7`	`A·B`

$\text{Cout} = AB + B\cdot Cin + A\cdot Cin$

এটাই majority function — Level 0-এর boolean-algebra লেসনের Q1-এ derive করা AB + BC + AC, আর আগের লেসনে যেটা “পরের লেসনেই ফিরে আসবে” বলে prediction করা হয়েছিল। এবার সেই prediction সত্যি হলো: carry-out ঠিক তখনই 1 যখন তিনটার মধ্যে অন্তত দুইটা input 1 — একটা natural majority vote।

Optimized ৫-gate realization — শেয়ার করা সিগন্যাল

Canonical SOP বসালে Sum-এ ৪টা 3-input AND + OR, Cout-এও ৩টা 2-input AND + OR — মোট প্রায় ৯টা gate, দুইটা output আলাদা আলাদাভাবে গণনা করলে।

কিন্তু একটা চমৎকার শেয়ারিং সুযোগ আছে। ধরুন P = A ⊕ B (এই নামকরণ ইচ্ছাকৃত — একটু পরেই এর তাৎপর্য দেখবেন)। তাহলে:

$\text{Sum} = P \oplus Cin$

$\text{Cout} = AB + Cin \cdot P$

দ্বিতীয় সমীকরণটা যাচাই করা যাক হাতে — প্রতিটা row-তে AB + Cin(A⊕B) বসিয়ে:

A B Cin	AB	A⊕B	Cin·(A⊕B)	AB+Cin(A⊕B)	সঠিক Cout
000	0	0	0	0	0 ✓
001	0	0	0	0	0 ✓
010	0	1	0	0	0 ✓
011	0	1	1	1	1 ✓
100	0	1	0	0	0 ✓
101	0	1	1	1	1 ✓
110	1	0	0	1	1 ✓
111	1	0	0	1	1 ✓

সবগুলো row মিলছে। তাই P = A⊕B সিগন্যালটা দুইবার পুনর্ব্যবহার করা যায় — একবার Sum বানাতে, একবার Cout বানাতে।

           ┌─────┐
   A ──────┤     │
           │ XOR ├──── P ──────────┬───────┐
   B ──────┤     │                 │        │
           └─────┘                 │        │
                                    │  ┌─────┴┐
   Cin ─────────────────────────┬──┴──┤ XOR  ├──── Sum
                                 │     └──────┘
                                 │     ┌──────┐
                                 └─────┤ AND  ├──┐
                                       └──────┘  │
                                                  │  ┌────┐
   A ──┬─────────────────────────────────────────┼──┤    │
       │            ┌──────┐                     └──┤ OR ├──── Cout
   B ──┴────────────┤ AND  ├────────────────────────┤    │
                     └──────┘                        └────┘

Full-adder — standard ৫-gate realization, P সিগন্যাল দুই output-এ শেয়ার হচ্ছে।

মোট: ২টা XOR + ২টা AND + ১টা OR = ৫টা gate। এটাই full-adder-এর “standard” গঠন — প্রায় প্রতিটা textbook, প্রায় প্রতিটা প্রকৃত চিপে এই একই কাঠামো (বা এর NAND-only সমতুল্য রূপ)।

ভেতরে কী ঘটছে

Ripple-carry adder — full-adder চেইন করে n বিট

একটা full-adder এক bit-position সামলায়। n-bit সংখ্যা যোগ করতে n-টা full-adder লাগে — আর প্রতিটার Cout পরেরটার Cin-এ সরাসরি তার দিয়ে জোড়া।

  Cin=0                                                    Cout
    │                                                        │
    ▼        C0        ▼        C1        ▼        C2        ▼
  ┌────┐    ────►    ┌────┐    ────►    ┌────┐    ────►    ┌────┐
  │ FA0│              │ FA1│              │ FA2│              │ FA3│
  └─┬┬─┘              └─┬┬─┘              └─┬┬─┘              └─┬┬─┘
   A0 B0                A1 B1                A2 B2                A3 B3
    │                    │                    │                    │
    ▼                    ▼                    ▼                    ▼
    S0                   S1                   S2                   S3

৪-bit ripple-carry adder — bit0 (সবচেয়ে ডানের/LSB) থেকে bit3 (MSB) পর্যন্ত carry একটার পর একটা 'ripple' করে।

এটাই ঠিক computer-representation/unsigned-integers-এ হাতে করা carry-column addition-এর physical রূপ — সেখানে আমরা কাগজে ডান থেকে বামে carry বহন করেছিলাম, এখানে সেই একই carry একটা তারে বহন হচ্ছে, একটা full-adder থেকে পরেরটায়। “Ripple” নামটাই বলে দেয় — carry পানির ঢেউয়ের মতো এক প্রান্ত থেকে অন্য প্রান্তে ছড়িয়ে যায়।

গুরুত্বপূর্ণ: প্রতিটা FAᵢ একই circuit — কোনো “বিশেষ” bit নেই (FA0-এর Cin external circuit থেকে আসা, যেমন 0 বা পূর্ববর্তী adder-এর carry, সাধারণত হার্ডওয়্যার-এ hardwired 0 অথবা subtractor mode-এ 1 — পরের লেসনে দেখবেন)।

Critical path — carry-কে সবার শেষ পর্যন্ত অপেক্ষা করতে হয়

সমস্যাটা এখানে: FA3-এর সঠিক Sum বের করতে C2 লাগে। C2 বের করতে FA2-এর কাজ শেষ হতে হবে, যেটা C1 চায়। C1 চায় C0। FA3 কাজ শুরুই করতে পারে না যতক্ষণ না C0, C1, C2 একে একে স্থির হয়।

প্রতিটা full-adder-এর carry-out নির্ভর করে carry-in-এর উপর (Cout = AB + Cin·P-এ Cin সরাসরি আছে) — তাই এই নির্ভরতা এড়ানো যায় না, শুধু গঠনগতভাবেই।

n-bit ripple-carry adder-এর critical path (input থেকে সবচেয়ে শেষ output পর্যন্ত সবচেয়ে দীর্ঘ gate-চেইন) n-টা full-adder-এর carry-path-এর যোগফল। প্রতিটা full-adder-এ carry পথে (AB + Cin·P) গড়ে ২ gate delay লাগে (AND + OR)। তাই:

$t_{\text{ripple}} = n \times t_{\text{carry-per-stage}} = O(n)$

৩২-bit ripple-carry adder-এর delay — একটা বাস্তব সংখ্যা

প্রতিটা full-adder-এর carry path~2 gate delay (AND + OR)
৩২টা stage চেইন32 × 2 = 64 gate delay, worst case
Gate delay (modern CMOS)~৫০ picosecond প্রতিটা
মোট critical path64 × 50ps = 3.2 nanosecond
1 GHz clock1 cycle = 1 ns বরাদ্দ
ফলাফল3.2ns > 1ns — এক cycle-এ শেষ হয় না!

এটাই আগের লেসনের boolean-algebra glossary entry-তে ইঙ্গিত করা সংখ্যা — একটা naive ৩২-bit ripple-carry adder দিয়ে ১ GHz clock চালানো সম্ভবই না, শুধু carry-র ripple করতে সময় লাগার কারণে। বাস্তব CPU-তে তাই ripple-carry কখনোই সরাসরি ব্যবহার হয় না বড় adder-এ।

Generate ও Propagate — সমাধানের বীজ

সমস্যাটা পুনর্বিবেচনা করুন: প্রতিটা Cᵢ₊₁ নির্ভর করে Cᵢ-এর উপর, তাই sequential হয়ে যায়। কিন্তু Cᵢ₊₁-এর সমীকরণ ভালো করে দেখুন:

$C_{i+1} = A_i B_i + C_i (A_i \oplus B_i)$

দুইটা অংশ চিহ্নিত করি:

$G_i = A_i \cdot B_i \qquad P_i = A_i \oplus B_i$

$C_{i+1} = G_i + P_i \cdot C_i$

Gᵢ (Generate): যদি Aᵢ = Bᵢ = 1, তাহলে এই stage নিজেই একটা carry তৈরি করে — আগের Cᵢ যাই হোক না কেন। 1+1=10, carry নিশ্চিত।
Pᵢ (Propagate): যদি Aᵢ ⊕ Bᵢ = 1 (ঠিক একটা 1), তাহলে এই stage নিজে carry তৈরি করে না, কিন্তু যদি আগে থেকে একটা carry আসে, সেটা পাস করে দেয় পরের stage-এ।

কেন এটা সাহায্য করে — carry expand করা

Cᵢ₊₁ = Gᵢ + Pᵢ Cᵢ recursively বসিয়ে দিলে, প্রতিটা carry কে শুধু মূল input (A, B) আর প্রাথমিক C_0-এর ভাষায় লেখা যায় — কোনো intermediate carry-র উপর অপেক্ষা না করেই:

$C_1 = G_0 + P_0 C_0$

$C_2 = G_1 + P_1 C_1 = G_1 + P_1 G_0 + P_1 P_0 C_0$

$C_3 = G_2 + P_2 G_1 + P_2 P_1 G_0 + P_2 P_1 P_0 C_0$

প্রতিটা Cᵢ এখন একটা সরাসরি SOP expression, শুধু A, B, C_0-এর উপর নির্ভর করছে — কোনো C_1, C_2 এর জন্য অপেক্ষা নেই। সব Gᵢ, Pᵢ একসাথে (parallel-এ) গণনা করা যায় (প্রতিটা মাত্র এক XOR/AND, Cᵢ-এর জন্য অপেক্ষা করে না), তারপর প্রতিটা Cᵢ একটা wide AND-OR network দিয়ে একই সময়ে বের করা যায়।

এটাই carry-lookahead adder (CLA)-এর মূল কৌশল — carry-কে sequentially “ripple” করানোর বদলে, algebra দিয়ে আগেভাগে (“look ahead”) গণনা করে ফেলা।

সীমা — এখানে পুরো CLA circuit বানাচ্ছি না

লক্ষ্য করুন C_3-এর সমীকরণে ইতিমধ্যে ৪টা term, C_4-এ আরো বেশি — যত bit বাড়ে, expression তত বড় আর wide-fan-in gate তত বেশি লাগে। এই কারণে বাস্তব CLA সরাসরি ৩২ বা ৬৪ bit-এ flat expand করে না, বরং ছোট ব্লকে (সাধারণত ৪-bit) ভাগ করে, তারপর সেই ব্লকগুলোর carry আবার একটা দ্বিতীয় স্তরের lookahead দিয়ে গণনা করে (hierarchical/block CLA) — এভাবে depth O(n) থেকে কমে আনুমানিক O(log n)-এর কাছাকাছি হয়। সেই hierarchical গঠনটা এই লেসনের সীমার বাইরে (Level 3-এ CPU datapath-এ আরো বিস্তারিত আসবে) — এখানে শুধু কেন সমান্তরাল গণনা সম্ভব সেই মূল অন্তর্দৃষ্টিটা ধরাই যথেষ্ট।

Ripple বনাম lookahead — asymptotic ভাষায়

এটা ঠিক mathematics/asymptotic-notation-এর ভাষায় বলা যায়:

Adder	Delay (depth)	Gate খরচ (area)
Ripple-carry	`O(n)`	কম — প্রায় `n` টা full-adder
Carry-lookahead (hierarchical)	`O(\log n)`-এর কাছাকাছি	বেশি — অতিরিক্ত G/P gate ও wide AND-OR network

এটা সেই একই time–space trade-off যেটা asymptotic-notation লেসনে dynamic array-তে দেখা গিয়েছিল (memory খরচ করে সময় কমানো) — এখানে সিলিকন এলাকা (transistor) খরচ করে সময় (delay) কমানো হচ্ছে। Software-এ hash table বনাম array-এর মতোই একটা choice, শুধু domain hardware।

আগের লেসনের boolean-algebra glossary entry-তে একটা বাস্তব সংখ্যাও ছিল: 32-bit adder-এ ripple-carry ~160 gate, ~64 depth; carry-lookahead ~500 gate (তিনগুণ বেশি), কিন্তু ~10 depth (ছয় গুণ দ্রুত)। CPU-তে carry-lookahead (বা তার আধুনিক উত্তরসূরি, যেমন carry-select বা Kogge-Stone adder) ব্যবহার হয় — clock speed-ই priority।

উদাহরণ

সম্পূর্ণ যাচাই — একটা ৪-bit যোগ হাতে-কলমে circuit দিয়ে

5 + 3 করি ৪-bit ripple-carry adder দিয়ে। 5 = 0101, 3 = 0011।

Bit	Aᵢ	Bᵢ	Cᵢ (in)	Sᵢ	Cᵢ₊₁ (out)
0	1	1	0	0	1
1	0	1	1	0	1
2	1	0	1	0	1
3	0	0	1	1	0

যাচাই প্রতি row:

bit0: 1+1+0 = 10₂ → S=0, Cout=1 ✓
bit1: 0+1+1(carry) = 10₂ → S=0, Cout=1 ✓
bit2: 1+0+1(carry) = 10₂ → S=0, Cout=1 ✓
bit3: 0+0+1(carry) = 01₂ → S=1, Cout=0 ✓

Sum bit গুলো (bit3 থেকে bit0): 1000 = 8। আর 5+3=8 ✓। Final Cout (bit3-এর carry-out) 0 — কোনো overflow না, কারণ 8 চার bit-এ আঁটে (0–15 range)।

যদি একইভাবে 10+7=17 করা হতো (৪-bit-এ ধরে না, যেহেতু সর্বোচ্চ 15), শেষ Cout=1 হতো — সেটাই computer-representation/unsigned-integers লেসনের mod 2⁴ wraparound-এর সরাসরি hardware সংকেত: Cout=1 মানে “সত্যিকারের যোগফল 2ⁿ বা তার বেশি ছিল, সংরক্ষিত মান mod 2ⁿ reduce হয়েছে”।

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

EXPERIMENT

Ripple-carry বনাম lookahead — delay simulate করুন

Python 3· ২০ মিনিট

# adder_delay.py — gate-level simulation, প্রতিটা "ধাপ" একটা gate-delay ধরা হচ্ছে

def full_adder(a, b, cin):
    s = a ^ b ^ cin
    cout = (a & b) | (cin & (a ^ b))
    return s, cout


def ripple_carry_add(a_bits, b_bits, cin=0):
    """LSB থেকে MSB — প্রতিটা full-adder-এর carry পরেরটাকে পাঠায়।
    'ধাপ' গোনা হচ্ছে কতগুলো stage সিরিয়ালি নির্ভরশীল, delay-র proxy হিসেবে।"""
    n = len(a_bits)
    sums, carries, steps = [], [cin], 0
    c = cin
    for i in range(n):
        s, c = full_adder(a_bits[i], b_bits[i], c)
        sums.append(s)
        carries.append(c)
        steps += 2                     # প্রতিটা stage-এ carry path ≈ ২ gate delay
    return sums, carries[-1], steps


def carry_lookahead_bit(i, a_bits, b_bits, cin):
    """C_i সরাসরি সূত্র থেকে, কোনো আগের C_{i-1} স্টেপ-বাই-স্টেপ না চেয়ে।"""
    G = [a_bits[k] & b_bits[k] for k in range(i)]
    P = [a_bits[k] ^ b_bits[k] for k in range(i)]
    c = cin
    for k in range(i):
        c = G[k] | (P[k] & c)          # গাণিতিকভাবে expand হলে এটাই সমতুল্য একধাপি SOP
    return c


def to_bits(n, width):
    return [(n >> i) & 1 for i in range(width)]


def from_bits(bits):
    return sum(b << i for i, b in enumerate(bits))


# ── পরীক্ষা: ৪, ৮, ১৬, ৩২-bit-এ ripple delay কীভাবে বাড়ে ──
print(f"{'bit width':>10} {'ripple steps (≈gate delay)':>28} {'lookahead depth (তাত্ত্বিক)':>28}")
for width in [4, 8, 16, 32, 64]:
    a_bits = to_bits(width - 1, width)     # dummy input
    b_bits = to_bits(1, width)
    _, _, ripple_steps = ripple_carry_add(a_bits, b_bits)
    lookahead_depth = 2                     # ২-স্তরের G/P গণনা + wide AND-OR, n-নির্বিশেষে (flat CLA-তে, ব্যবহারিকভাবে hierarchical হলে O(log n))
    print(f"{width:>10} {ripple_steps:>28} {lookahead_depth:>28}  (flat CLA ধরে; বাস্তবে hierarchical hলে O(log n))")

# ── সঠিকতা যাচাই: দুইটা পদ্ধতিই একই যোগফল দেয় কি না ──
import random
for _ in range(1000):
    width = 8
    a, b = random.randint(0, 255), random.randint(0, 255)
    a_bits, b_bits = to_bits(a, width), to_bits(b, width)
    sums, cout, _ = ripple_carry_add(a_bits, b_bits)
    ripple_result = from_bits(sums)

    # carry-lookahead দিয়ে প্রতিটা bit আলাদা করে verify
    c = 0
    la_sums = []
    for i in range(width):
        ci = carry_lookahead_bit(i, a_bits, b_bits, 0)
        s = a_bits[i] ^ b_bits[i] ^ ci
        la_sums.append(s)
    la_result = from_bits(la_sums)

    expected = (a + b) % 256
    assert ripple_result == expected == la_result, (a, b, ripple_result, la_result, expected)

print("\n১০০০টা random ৮-bit addition — ripple আর lookahead দুটোই mod 256 সূত্রের সাথে মিলেছে ✓")

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

 bit width  ripple steps (≈gate delay)  lookahead depth (তাত্ত্বিক)
         4                            8                            2  ...
         8                           16                            2  ...
        16                           32                            2  ...
        32                           64                            2  ...
        64                          128                            2  ...

১০০০টা random ৮-bit addition — ripple আর lookahead দুটোই mod 256 সূত্রের সাথে মিলেছে ✓

লক্ষ্য করুন: ripple steps ঠিক 2 × width — রৈখিকভাবে বাড়ছে, O(n)-এর সরাসরি প্রমাণ। Lookahead-এর তাত্ত্বিক depth এখানে স্থির দেখানো হয়েছে (flat/single-level সূত্র হিসেবে), কারণ প্রতিটা Cᵢ-ই independent সূত্র থেকে গণনা হচ্ছে — flat CLA-তে সমীকরণের size (term সংখ্যা, gate fan-in) i-এর সাথে বাড়ে, তাই বাস্তবে wide gate-এর delay-ও কিছুটা বাড়ে (log-স্কেলে) — সেই সূক্ষ্মতাই hierarchical CLA দিয়ে সামলানো হয়, যা এই lesson-এর সীমার বাইরে।

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

Ripple-carry adder-এ carry stabilize হতে যে ধাপ লাগে সেটা সত্যিই n-এর সমানুপাতিক বাড়ে, আর carry-lookahead সূত্র সেই একই carry bit একধাপেই (সরাসরি সূত্র থেকে) হিসাব করে — একই ফলাফল, ভিন্ন delay profile।

নিজে বানান

BUILD IT

N-bit Ripple-Carry Adder Simulator + Critical Path Visualizer

Python · ●●●○○

একটা full_adder(a, b, cin) ফাংশন লিখুন — উপরের truth table থেকে সরাসরি
সেটা চেইন করে n-bit ripple_carry_add(a_bits, b_bits, cin) বানান
Python-এর নিজস্ব + অপারেটরের সাথে সব 2^n সম্ভাব্য input মিলিয়ে ৪-bit-এ সম্পূর্ণ যাচাই করুন
প্রতিটা stage-এর carry কখন "স্থির" হয় সেটা track করে একটা টেক্সট-ভিত্তিক timing diagram আঁকুন
সেই একই adder দিয়ে overflow flag বের করুন (পরের লেসনের প্রস্তুতি)

"""
n_bit_adder.py — সম্পূর্ণ ripple-carry adder, exhaustive verification সহ
চালান: python n_bit_adder.py
"""

def full_adder(a, b, cin):
    p = a ^ b                      # propagate সিগন্যাল — Sum আর Cout দুটোতেই লাগবে
    s = p ^ cin
    cout = (a & b) | (cin & p)
    return s, cout


def ripple_carry_add(a_bits, b_bits, cin=0):
    n = len(a_bits)
    assert len(b_bits) == n
    sums = []
    carry_trace = [cin]
    c = cin
    for i in range(n):
        s, c = full_adder(a_bits[i], b_bits[i], c)
        sums.append(s)
        carry_trace.append(c)
    return sums, carry_trace                     # carry_trace[-1] = final carry-out


def to_bits(n, width):
    return [(n >> i) & 1 for i in range(width)]


def from_bits(bits):
    return sum(b << i for i, b in enumerate(bits))


def exhaustive_verify(width):
    """সব সম্ভাব্য input জোড়া মিলিয়ে Python-এর নেটিভ + এর বিরুদ্ধে যাচাই"""
    mismatches = 0
    total = 2 ** width
    for a in range(total):
        for b in range(total):
            a_bits, b_bits = to_bits(a, width), to_bits(b, width)
            sums, carry_trace = ripple_carry_add(a_bits, b_bits)
            result = from_bits(sums)
            cout = carry_trace[-1]
            expected_full = a + b                        # carry ছাড়া প্রকৃত গাণিতিক যোগফল
            expected_wrapped = expected_full % total       # mod 2^width — hardware যা আসলে রাখে
            expected_cout = 1 if expected_full >= total else 0
            if result != expected_wrapped or cout != expected_cout:
                mismatches += 1
                print(f"  MISMATCH a={a} b={b}: got sum={result},cout={cout} "
                      f"expected sum={expected_wrapped},cout={expected_cout}")
    print(f"width={width}: {total*total} case, mismatch={mismatches}")


def timing_diagram(a, b, width, cin=0):
    """প্রতিটা stage-এর carry কোন 'সময়ে' স্থির হয় (২ gate-delay/stage ধরে) দেখানো"""
    a_bits, b_bits = to_bits(a, width), to_bits(b, width)
    c = cin
    print(f"\n{a} + {b} (width={width}, cin={cin}) — critical path trace:")
    print(f"{'stage':>6} {'A':>2} {'B':>2} {'Cin':>4} {'Sum':>4} {'Cout':>5} {'stable at (গেট-ডিলে)':>22}")
    t = 0
    for i in range(width):
        s, c_new = full_adder(a_bits[i], b_bits[i], c)
        t += 2                                          # এই stage-এর carry stable হতে +2 delay লাগলো (আগের carry-র উপর নির্ভরশীল)
        print(f"{i:>6} {a_bits[i]:>2} {b_bits[i]:>2} {c:>4} {s:>4} {c_new:>5} {t:>18}")
        c = c_new
    print(f"  → শেষ stage-এর Sum stable হতে মোট {t} 'গেট-ডিলে ইউনিট' লাগলো — n={width}-এর সমানুপাতিক (O(n))")


if __name__ == "__main__":
    exhaustive_verify(4)          # 16×16 = 256 case, খুব দ্রুত
    timing_diagram(11, 6, width=4)
    timing_diagram(255, 1, width=8)   # সবচেয়ে খারাপ case — carry পুরো chain জুড়ে ripple করে

প্রত্যাশিত output (সংক্ষিপ্ত):

width=4: 256 case, mismatch=0

11 + 6 (width=4, cin=0) — critical path trace:
 stage  A  B  Cin  Sum  Cout   stable at (গেট-ডিলে)
     0  1  0    0    1     0                     2
     1  1  1    0    0     1                     4
     2  0  1    1    0     1                     6
     3  1  0    1    0     1                     8
  → শেষ stage-এর Sum stable হতে মোট 8 'গেট-ডিলে ইউনিট' লাগলো — n=4-এর সমানুপাতিক (O(n))

255 + 1 (width=8, cin=0) — critical path trace:
 stage  A  B  Cin  Sum  Cout   stable at (গেট-ডিলে)
     0  1  1    0    0     1                     2
     1  1  0    1    0     1                     4
     ...
     7  1  0    1    0     1                    16
  → শেষ stage-এর Sum stable হতে মোট 16 'গেট-ডিলে ইউনিট' লাগলো — n=8-এর সমানুপাতিক (O(n))

255 + 1 ইচ্ছাকৃতভাবে বেছে নেওয়া — এটাই ripple-carry-এর worst case: প্রতিটা bit-এ carry propagate হয় (11111111 + 00000001), তাই carry পুরো ৮ stage জুড়ে ripple করে, শেষ পর্যন্ত overflow (Cout=1, mod 256 wraparound)।

নিজে বাড়ান:

exhaustive_verify(6) চালিয়ে দেখুন (64×64 case) — সময় কেমন বাড়ে সেটা লক্ষ্য করুন, আর কেন exhaustive_verify(16) অবাস্তব (65536² ≈ ৪ বিলিয়ন case) সেটাও বুঝুন
carry_lookahead_bit (আগের experiment থেকে) দিয়ে একই timing_diagram-এর তুলনামূলক সংস্করণ বানান — দেখান lookahead-এ প্রতিটা bit “একই সময়ে” (parallel-এ) স্থির হয়
Worst-case input pattern (0xFF... + 0x00...1) স্বয়ংক্রিয়ভাবে খুঁজে বের করা একটা ফাংশন লিখুন যেকোনো width-এর জন্য
subtract mode যোগ করুন (পরের লেসনের প্রস্তুতি) — B-এর প্রতিটা bit XOR দিয়ে invert করে, cin=1 দিয়ে চালিয়ে দেখুন ফলাফল A - B-এর সাথে মেলে কি না

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

Adder circuit যেখানে সত্যিই চলছে

প্রতিটা CPU-র ALU। Integer addition, address calculation (base + offset), loop counter increment — সবকিছুর কেন্দ্রে এই একই full-adder চেইন (বা তার দ্রুততর সংস্করণ)। x86-64-এর ADD instruction, ARM-এর ADD/ADDS — সবই শেষ পর্যন্ত এই circuit-এ নামে।

Program Counter increment। প্রতিটা instruction fetch-এর পর PC = PC + 4 (বা instruction size)। এটাও একটা adder — প্রায়ই একটা dedicated, simplified adder (+4-এর জন্য পুরো general adder না লাগিয়েও করা যায়, কারণ B স্থির)।

Memory address calculation। array[i] মানে hardware-এ base_address + i × element_size — একটা multiply (shift, যদি element_size দুইয়ের ঘাত হয়) আর একটা adder।

Carry-lookahead-এর বংশধর। আধুনিক CPU ৩২/৬৪-bit adder-এ সরাসরি flat CLA ব্যবহার করে না (gate cost খুব বেশি) — বরং hierarchical CLA, carry-select adder (দুইটা সম্ভাব্য ফলাফল আগে থেকে গণনা করে, carry এলে সঠিকটা বেছে নেয়), বা Kogge-Stone / Brent-Kung adder (parallel prefix গঠন, O(log n) depth) ব্যবহার করে। সবগুলোই একই মূল ধারণা থেকে — generate/propagate — বিভিন্ন gate-cost/delay trade-off-এ।

DSP আর FPGA-র dedicated carry chain। Xilinx/Intel FPGA-তে প্রতিটা logic block-এর সাথে একটা dedicated, hand-optimized carry-chain circuit থাকে (CARRY4, CARRY8 primitive) — কারণ generic LUT দিয়ে carry বানালে ripple delay এত বেশি হতো যে প্রতিটা adder-heavy design ধীর হয়ে যেত।

Checksum/CRC hardware। নেটওয়ার্ক ইন্টারফেস কার্ড, disk controller — এদের ভেতরের checksum accumulator একটা repeated adder circuit, প্রতিটা প্যাকেট/সেক্টরের জন্য।

Financial/scientific computing accelerator। GPU, TPU-র ভেতরে হাজার হাজার parallel adder — matrix multiplication, neural network inference-এর মূল building block এখনো এই একই full-adder, শুধু বিশাল সংখ্যায় সমান্তরালে বসানো।

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

“Full-adder-এর Sum output-ও K-map দিয়ে minimize করা যায়, শুধু আমরা চেষ্টা করিনি।”

চেষ্টা করলে দেখা যাবে আসলেই যায় না — এটা এই লেসনের একটা verified তথ্য, ধারণা না।

Sum = Σm(1,2,4,7) — checkerboard pattern, কোনো দুইটা 1-cell প্রতিবেশী না। এটা আগের লেসনের parity function-এর সাথে হুবহু একই কাঠামো (৩-input XOR)। এই ধরনের function-এর জন্য SOP minimization structurally অসম্ভব, কোনো ভুল প্রচেষ্টার কারণে না।

কেন এটা গুরুত্বপূর্ণ: যদি কেউ Sum-কে জোর করে SOP-তে লেখে (A'B'Cin + A'BCin' + AB'Cin' + ABCin), সেটা ৪টা 3-input AND

১টা OR = ৫টা gate লাগবে — অথচ একটা মাত্র A ⊕ B ⊕ Cin (দুইটা XOR gate) দিয়েই একই কাজ হয়। XOR সবসময় প্রথম পছন্দ হওয়া উচিত parity-জাতীয় output-এর জন্য, SOP-তে জোর করার আগে।

“Ripple-carry adder পুরোনো, বাতিল প্রযুক্তি — বাস্তবে কেউ ব্যবহার করে না।”

ভুল — যেখানে speed গুরুত্বপূর্ণ না, ripple-carry এখনো পছন্দের সমাধান, কারণ এটা সবচেয়ে কম gate, কম area, কম power ব্যবহার করে।

ব্যবহার	Adder ধরন	কারণ
High-end CPU ALU	Carry-lookahead/prefix	Clock speed সবচেয়ে জরুরি
Low-power IoT sensor chip	Ripple-carry	Power/area সবচেয়ে জরুরি, speed কম গুরুত্বপূর্ণ
Simple microcontroller (৮-bit)	Ripple-carry	৮ bit-এ delay এমনিতেই ছোট, CLA-র বাড়তি জটিলতার দরকার নেই
FPGA soft-core, non-critical path	Ripple-carry	Tool automatically synthesize করে, hand-optimization অপ্রয়োজনীয়

এই লেসনের boolean-algebra-র মতোই এখানেও “optimal” মানে কীসের জন্য optimal সেই প্রশ্নের উত্তর ছাড়া অর্থহীন। ৮-bit adder-এ ripple-carry-র worst-case delay এমনিতেই এত ছোট (মাত্র ১৬ gate delay) যে CLA-র বাড়তি gate cost এর কোনো লাভ দেয় না।

“Carry-lookahead সব ক্ষেত্রেই O(1) delay দেয় — carry ripple করার সমস্যা পুরোপুরি সমাধান।”

আংশিক সত্য, কিন্তু ভুল দিকে। Flat (single-level) CLA সত্যিই প্রতিটা Cᵢ-কে একটা সরাসরি SOP সূত্র দিয়ে গণনা করে — কোনো আগের Cᵢ₋₁-এর জন্য অপেক্ষা নেই। কিন্তু এই সূত্রের size (term সংখ্যা এবং প্রতিটা AND gate-এর fan-in) i বাড়ার সাথে বাড়ে (C_31-এর সূত্রে ৩২টা পর্যন্ত term থাকতে পারে)। বাস্তব gate-এর fan-in সীমিত (সাধারণত ২-৪ input), তাই এত বড় AND/OR বানাতে গেলে সেটাও কয়েক স্তরের gate-tree লাগে — যেটার নিজস্ব delay আছে, O(\log n)-এর কাছাকাছি, শূন্য না।

তাই বাস্তব “flat” CLA n বড় হলে scale করে না — এই জন্যই hierarchical/block CLA ব্যবহার হয়, যেখানে ছোট ব্লক (৪-বিট) লেভেল-১ CLA দিয়ে দ্রুত গণনা হয়, তারপর ব্লকগুলোর মধ্যে carry আবার একটা লেভেল-২ lookahead দিয়ে সমান্তরালে গণনা হয়। ফলাফল O(1) না, কিন্তু O(n)-এর চেয়ে অনেক ভালো — বাস্তবে প্রায় O(\log n)।

নিয়ম: “lookahead” মানে “delay সম্পূর্ণ উবে যায়” না, মানে “delay-র growth rate কমে” — ঠিক যেমন asymptotic-notation লেসনে merge sort O(n)-কে শূন্য করে না, O(n²) থেকে O(n \log n)-এ নামায়।

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

Half-adder আর full-adder-এর মধ্যে ঠিক কী পার্থক্য, আর কেন একটা n-bit adder চেইনে (LSB বাদে) সব বিটেই full-adder লাগে?

স্মরণ

Half-adder: দুইটা input (A, B), দুইটা output (Sum, Carry)। কোনো carry-in নেই। Sum = A⊕B, Carry = A·B।

Full-adder: তিনটা input (A, B, Cin), দুইটা output (Sum, Cout)। Sum = A⊕B⊕Cin, Cout = AB + Cin(A⊕B)।

কেন LSB বাদে সব বিটে full-adder লাগে: n-bit addition-এ bit position 1 (দ্বিতীয় থেকে গোনা) থেকে শুরু করে প্রতিটা position-এ আগের position থেকে একটা সম্ভাব্য carry আসতে পারে — সেটা গ্রহণ করার input (Cin) দরকার। শুধু সবচেয়ে প্রথম (LSB, position 0) position-এ কোনো আগের carry নেই বলে সেখানে আসলে half-adder যথেষ্ট (Cin=0 সবসময়)। তবে practical design-এ এমনকি bit0-এও full-adder ব্যবহার করা হয় (Cin hardwired 0), কারণ একটা uniform, পুনরাবৃত্ত module ব্যবহার করলে layout ও design সহজ হয় — আর পরের লেসনে দেখবেন সেই Cin bit0-এ সবসময় 0 না-ও হতে পারে (subtraction mode-এ 1 হয়)।

Full-adder-এর Cout সমীকরণ AB + Cin(A⊕B)। এটা কি সবসময় canonical majority সমীকরণ AB + BCin + ACin-এর সমান? দুইটাই সত্য হলে, কোনটা hardware-এ পছন্দনীয় আর কেন?

যুক্তি

হ্যাঁ, দুইটা algebraically সমতুল্য — এই লেসনের truth table দিয়ে যাচাই করা হয়েছে (৮ row-ই মেলে)। বীজগণিতে দেখানো যায়:

AB + Cin(A⊕B) = AB + Cin(AB' + A'B)
              = AB + ABCin' ... (এভাবে না, বরং সরাসরি)

সহজ পথ: Cin(A⊕B) = CinAB' + CinA'B। তাই: AB + CinAB' + CinA'B। এখন AB(Cin+Cin') = AB ব্যবহার করে পুনর্বিন্যাস করলে AB + BCin + ACin-এ পৌঁছানো যায় (বিস্তারিত algebra খাতায় করে দেখুন — প্রতিটা ধাপ boolean-algebra লেসনের distributive/absorption rule)।

কোনটা hardware-এ ভালো — AB+Cin(A⊕B) জেতে, কারণ:

AB + BCin + ACin আলাদাভাবে বানালে ৩টা 2-input AND + ১টা 3-input OR = ৪টা gate লাগে, আর A⊕B (P সিগন্যাল) কোথাও পুনর্ব্যবহার হয় না।

AB + Cin·P ব্যবহার করলে — যেখানে P = A⊕B ইতিমধ্যে Sum বানাতে গণনা করা হয়েছে — এই একই P তার Cout-এও পুনর্ব্যবহার করা যায়। ফলে পুরো circuit (Sum + Cout একসাথে) মাত্র ৫টা gate-এ (২ XOR + ২ AND + ১ OR) হয়ে যায়, যেখানে দুইটা আলাদা canonical expression বানালে বেশি লাগত।

মূল পাঠ: দুইটা আলাদা output-এর জন্য minimization আলাদাভাবে না করে, তাদের মধ্যে shared intermediate signal খুঁজে বের করাটাই multi-output circuit optimization-এর আসল কৌশল — এটা K-map-এর single-output minimization-এর চেয়ে এক ধাপ এগিয়ে।

একটা ৪-bit ripple-carry adder-এ A=1111, B=0001 (অর্থাৎ 15+1) যোগ করুন bit-by-bit, প্রতিটা full-adder-এর Sum আর Cout দেখান। ফলাফল ৪ bit-এ আঁটে কি না?

প্রয়োগ

bit	Aᵢ	Bᵢ	Cin	Cout
0	1	1	0	1
1	1	0	1	1
2	1	0	1	1
3	1	0	1	1

Sum bits (bit3→bit0): 0000। চূড়ান্ত Cout (bit3-এর carry-out) = 1।

যাচাই: 15 + 1 = 16, আর 16 চার bit-এ আঁটে না (সর্বোচ্চ 15)। 16 mod 16 = 0 — আর সেটাই আমরা পেয়েছি (Sum=0000)। Cout=1 ঠিক এই wraparound-এর সংকেত — ঠিক computer-representation/unsigned-integers লেসনে প্রমাণিত mod 2ⁿ reduction-এর hardware flag।

লক্ষ্য করুন — এটাই worst-case ripple পরিস্থিতি: carry bit0 থেকে bit3 পর্যন্ত প্রতিটা stage-এই propagate হয়েছে (কারণ Pᵢ = Aᵢ⊕Bᵢ = 1 প্রতিটা higher bit-এ), তাই পুরো critical path সক্রিয় — ঠিক এই লেসনের ripple-carry delay বিশ্লেষণে যে worst case ব্যবহার করা হয়েছিল।

Generate সিগন্যাল Gᵢ = Aᵢ·Bᵢ কেন Cᵢ (আগের carry)-এর উপর নির্ভর করে না, অথচ Cᵢ₊₁ (এই stage-এর carry-out) নির্ভর করে? এই পার্থক্যটাই কীভাবে carry-lookahead সম্ভব করে তোলে ব্যাখ্যা করুন।

যুক্তি

Gᵢ = Aᵢ·Bᵢ শুধুমাত্র এই bit position-এর নিজের input (Aᵢ, Bᵢ) দিয়ে সংজ্ঞায়িত — Cᵢ কোথাও সমীকরণে নেই। তাই Gᵢ গণনা করতে কোনো আগের carry-র জন্য অপেক্ষা করতে হয় না; এটা সব stage-এ একই মুহূর্তে, সমান্তরালে গণনা করা যায় (প্রতিটা মাত্র এক AND gate)। একইভাবে Pᵢ = Aᵢ⊕Bᵢ-ও শুধু নিজের input-এর উপর নির্ভর করে, সমান্তরাল-বান্ধব।

Cᵢ₊₁ = Gᵢ + Pᵢ·Cᵢ — এখানে Cᵢ আছে, তাই সরল ripple গঠনে এটা sequential (আগের carry ছাড়া গণনা করা যায় না)। কিন্তু এই recurrence-টা algebraically expand করা যায় (এই লেসনের “কেন এটা সাহায্য করে” অংশে দেখানো হয়েছে) — বারবার Cᵢ-কে তার নিজের G, P আর তার আগের C-দিয়ে replace করতে করতে, শেষ পর্যন্ত প্রতিটা Cᵢ-কে শুধু G₀...Gᵢ₋₁, P₀...Pᵢ₋₁, C₀-এর একটা সরাসরি SOP এক্সপ্রেশনে লেখা যায়।

মূল অন্তর্দৃষ্টি: যেহেতু সব Gᵢ, Pᵢ ইতিমধ্যেই সমান্তরালে (এক ধাপে) পাওয়া যায়, আর প্রতিটা Cᵢ-র expanded সূত্র শুধু সেই G, P মানগুলোর (আর C₀-এর) একটা function — তাই সব Cᵢ-ও এখন সমান্তরালে (একটা wide AND-OR network দিয়ে, একই সাথে) গণনা করা সম্ভব, একটার জন্য আরেকটাকে অপেক্ষা না করেই। Sequential dependency-টাই ছিল আসল বাধা — generate/propagate সেই dependency-কে “unroll” করে সমান্তরাল করার উপায় বের করে দেয়, বীজগণিতের মাধ্যমে, কোনো নতুন hardware primitive ছাড়াই।

আপনি একটা ৬৪-bit adder ডিজাইন করছেন এমন একটা চিপে যেখানে gate/transistor বাজেট খুবই সীমিত (একটা ছোট, ব্যাটারি-চালিত sensor), কিন্তু একই সাথে speed-ও পুরোপুরি অগ্রাহ্য করা যাবে না। কী কৌশল নেবেন?

ডিজাইন

বিশুদ্ধ ripple-carry (৬৪ stage, worst-case ~১২৮ gate delay) আর flat carry-lookahead (বিশাল gate cost, wide fan-in gate যা বাস্তবে বানানোই কঠিন) — দুইটাই চরম প্রান্তে। মাঝামাঝি সমাধান দরকার।

ব্যবহারিক সিদ্ধান্ত — hierarchical/block approach:

৬৪ বিটকে ছোট ব্লকে ভাগ করুন (যেমন ৮টা ব্লক, প্রতিটা ৮-বিট)
প্রতিটা ৮-বিট ব্লকের ভেতরে ripple-carry ব্যবহার করুন (ছোট n-এ ripple delay এমনিতেই সহনীয়, আর gate cost সর্বনিম্ন)
ব্লকগুলোর মধ্যে carry পাস করার জন্য একটা হালকা lookahead বা carry-select কৌশল ব্যবহার করুন — যাতে block-থেকে-block carry দ্রুত পৌঁছায়, প্রতিটা ব্লক নিজের ভেতরের ripple শেষ হওয়া পর্যন্ত অপেক্ষা না করেই আংশিকভাবে কাজ শুরু করতে পারে

এটাই বাস্তব carry-select adder-এর মূল ধারণা: প্রতিটা ব্লক দুইবার গণনা করে — একবার ধরে নিয়ে carry-in 0, একবার 1 — তারপর প্রকৃত carry-in এলে একটা multiplexer দিয়ে সঠিক ফলাফল বেছে নেয়। এতে gate cost প্রায় দ্বিগুণ (দুইটা adder প্রতি ব্লকে) কিন্তু delay অনেক কমে, কারণ block-এর ভেতরের ripple আর block-থেকে-block carry propagation সমান্তরালে চলে।

সংক্ষেপে: সম্পূর্ণ ripple বা সম্পূর্ণ flat-lookahead কোনোটাই বেছে না নিয়ে, ব্লক আকার নিয়ে পরীক্ষা করে gate-cost বনাম delay-র sweet spot বের করা — ঠিক এই লেসনের misconception অংশে বলা “optimal মানে কীসের জন্য optimal” প্রশ্নের ব্যবহারিক উত্তর।

এরপর কী

এরপর — যোগ থেকে বিয়োগ, বিনামূল্যে

Adder circuit হাতে আছে এখন। কিন্তু computer-representation/signed-integers লেসনে আমরা একটা চমকপ্রদ দাবি করেছিলাম, শুধু প্রতিশ্রুতি হিসেবে রেখে দিয়েছিলাম: বিয়োগের জন্য আলাদা কোনো circuit লাগে না। A - B = A + (\sim B + 1)-এর দুই’s complement প্রমাণটা এতদিন বিশুদ্ধ গণিত ছিল।

পরের লেসনে আমরা সেই প্রমাণটা সরাসরি circuit-এ রূপান্তর করব — এই লেসনের full-adder চেইনের সাথে মাত্র একটা সারি XOR gate আর একটা control সিগন্যাল যোগ করে, একই hardware যোগ এবং বিয়োগ দুটোই করবে। তারপর সেই একই adder পুনর্ব্যবহার করে comparator বানাব (A \< B, A = B, A > B), আর দেখব ALU-র zero, carry, আর overflow flag ঠিক কোন circuit থেকে আসে — যেটা computer-representation/integer-overflow লেসনে “Level 2-তে এই hardware mechanism দেখব” বলে প্রতিশ্রুতি দেওয়া হয়েছিল।

Adder Circuit — গণিত থেকে সিলিকনে যোগফল

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

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

আগে এটা বুঝি

মূল ধারণা

Half-adder — দুইটা bit, দুইটা gate

Truth table

Minimization — আসলে করারই কিছু নেই

Full-adder — তিনটা input, দুইটা output

Truth table

Sum — আবার সেই parity

Cout — majority function-এর প্রত্যাবর্তন

Optimized ৫-gate realization — শেয়ার করা সিগন্যাল

ভেতরে কী ঘটছে

Ripple-carry adder — full-adder চেইন করে n বিট

Critical path — carry-কে সবার শেষ পর্যন্ত অপেক্ষা করতে হয়

Generate ও Propagate — সমাধানের বীজ

কেন এটা সাহায্য করে — carry expand করা

Ripple বনাম lookahead — asymptotic ভাষায়

উদাহরণ

সম্পূর্ণ যাচাই — একটা ৪-bit যোগ হাতে-কলমে circuit দিয়ে

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

Ripple-carry বনাম lookahead — delay simulate করুন

নিজে বানান

N-bit Ripple-Carry Adder Simulator + Critical Path Visualizer

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

Adder circuit যেখানে সত্যিই চলছে

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

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

এরপর কী

এরপর — যোগ থেকে বিয়োগ, বিনামূল্যে

আরও পড়ুন

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

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

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

◆মূল ধারণাCore concept

Half-adder — দুইটা bit, দুইটা gate

Truth table

Minimization — আসলে করারই কিছু নেই

Full-adder — তিনটা input, দুইটা output

Truth table

Sum — আবার সেই parity

Cout — majority function-এর প্রত্যাবর্তন

Optimized ৫-gate realization — শেয়ার করা সিগন্যাল

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

Ripple-carry adder — full-adder চেইন করে n বিট

Critical path — carry-কে সবার শেষ পর্যন্ত অপেক্ষা করতে হয়

Generate ও Propagate — সমাধানের বীজ

কেন এটা সাহায্য করে — carry expand করা

Ripple বনাম lookahead — asymptotic ভাষায়

▶উদাহরণExample

সম্পূর্ণ যাচাই — একটা ৪-bit যোগ হাতে-কলমে circuit দিয়ে

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

Ripple-carry বনাম lookahead — delay simulate করুন

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

N-bit Ripple-Carry Adder Simulator + Critical Path Visualizer

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

Adder circuit যেখানে সত্যিই চলছে

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

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

→এরপর কীNext step

এরপর — যোগ থেকে বিয়োগ, বিনামূল্যে

আরও পড়ুন

আগে এটা বুঝি

মূল ধারণা

ভেতরে কী ঘটছে

উদাহরণ

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

নিজে বানান

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

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

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

এরপর কী