Adder — half adder, full adder, ripple carry আর carry-lookahead

১ · যোগই কম্পিউটারের সবচেয়ে ব্যস্ত কাজ

আপনার ফোনের CPU প্রতি সেকেন্ডে শত কোটিবার যোগ করে। শুধু হিসাবের অ্যাপে নয় — প্রতিটি loop-এর counter বাড়াতে, array-র পরের ঘরের ঠিকানা বের করতে, পরের instruction-এর ঠিকানা (PC + 4) হিসাব করতে, এমনকি বিয়োগ আর তুলনা করতেও। তাই ALU-র ভেতরে যে circuit যোগ করে, সেই adder CPU-র সবচেয়ে বেশি ব্যবহৃত অংশগুলোর একটি। এর গতি প্রায়ই ঠিক করে দেয় পুরো CPU-র clock কত দ্রুত চলতে পারবে।

পর্ব ০৪-এ (সংখ্যা পদ্ধতি) আপনি কাগজে binary যোগ করেছেন: ডান থেকে বাঁয়ে, প্রতিটি ঘরে দুটি বিট আর আগের ঘরের carry যোগ, ঘরে একটি বিট লেখা আর বাঁয়ে carry পাঠানো। পর্ব ০৫-এ (Integer-এর বিট-রূপ) দেখেছেন, একই যোগ two's complement সংখ্যার জন্যও কাজ করে, আর MSB-র carry থেকে overflow flag V পাওয়া যায়। এই পর্বে প্রশ্নটি অন্য: এই কাগজের পদ্ধতিটি logic gate দিয়ে কীভাবে বানানো যায়, আর কীভাবে দ্রুত করা যায়?

এই পর্বের সব circuit combinational circuit — আউটপুট শুধু এই মুহূর্তের ইনপুটের ওপর নির্ভর করে, কোনো স্মৃতি নেই। Boolean algebra-র সূত্র পর্ব ০৭-এ, gate আর gate delay পর্ব ০৮-এ, আর K-map দিয়ে সরলীকরণ পর্ব ০৯-এ বিস্তারিত আছে; এখানে যতটুকু দরকার ততটুকুই ব্যবহার করব। লেখার নিয়ম: A′ মানে NOT A (উল্টো), AB মানে A AND B, A + B মানে A OR B, আর A ⊕ B মানে XOR (ঠিক একটি ১ হলে ১). কোডে এগুলো ~, &, |, ^.

২ · Half adder — দুই বিটের যোগ

সবচেয়ে ছোট প্রশ্ন দিয়ে শুরু: দুটি বিট A আর B যোগ করলে কী হয়? ০ + ০ = ০, ০ + ১ = ১, ১ + ০ = ১, আর ১ + ১ = 10 (binary-তে দুই)। শেষ ক্ষেত্রে উত্তর দুই বিটের, তাই আউটপুটও দুটি: যোগফলের বিট S (sum) আর বাঁয়ে যাওয়া C (carry). এই circuit-এর নাম half adder. এর truth table:

K-map থেকে সূত্র। দুই চলকের K-map-এ চারটি ঘর। C-এর ১ মাত্র একটি ঘরে (A = 1, B = 1), পাশে কোনো ১ নেই, তাই C = AB. S-এর ১ দুটি ঘরে — A′B আর AB′ — যারা কর্ণ বরাবর, পাশাপাশি নয়; তাই দলে বাঁধা যায় না, আর S = A′B + AB′ = A ⊕ B. অর্থাৎ sum হলো XOR, carry হলো AND.

নাম “half” কেন? কারণ এটি বহু-বিটের যোগের অর্ধেক কাজ করে: শুধু সবচেয়ে ডানের ঘর (LSB) সামলাতে পারে, যেখানে আগের কোনো carry নেই। মাঝের যেকোনো ঘরে তিনটি বিট আসে — a_i, b_i আর ডানের ঘর থেকে আসা carry. সেটা সামলাতে লাগে full adder.

৩ · Full adder — তিন বিটের যোগ আর majority

Full adder-এর ইনপুট A, B আর C_in; আউটপুট S আর C_out. তিনটি বিটের যোগফল ০ থেকে ৩, তাই দুই বিটেই ধরে: C_out হলো দুইয়ের ঘর, S হলো একের ঘর। নিচের stepper-এ truth table থেকে শুরু করে দুটি সূত্র বের করে circuit পর্যন্ত যাওয়া যাক।

row  A B Cin │ total │ Cout S
 0   0 0  0  │   0   │  0   0
 1   0 0  1  │   1   │  0   1
 2   0 1  0  │   1   │  0   1
 3   0 1  1  │   2   │  1   0
 4   1 0  0  │   1   │  0   1
 5   1 0  1  │   2   │  1   0
 6   1 1  0  │   2   │  1   0
 7   1 1  1  │   3   │  1   1

S        B Cin = 00  01  11  10
A = 0             0   1   0   1
A = 1             1   0   1   0

S = 1 at rows 1, 2, 4, 7 (odd number of 1s)
no two 1s are adjacent -> no grouping
S = A'B'Cin + A'BCin' + AB'Cin' + ABCin
  = A xor B xor Cin

Cout     B Cin = 00  01  11  10
A = 0             0   0  [1]  0
A = 1             0  [1   1   1]

group 1: column 11, both rows   -> B Cin
group 2: row A=1, columns 01,11 -> A Cin
group 3: row A=1, columns 11,10 -> A B
Cout = AB + A Cin + B Cin   (majority)

Cout = AB + Cin(A + B)
A + B = (A xor B) + AB
Cout = AB + Cin(A xor B) + Cin·AB
     = AB(1 + Cin) + Cin(A xor B)
     = AB + Cin(A xor B)

HA1: P = A xor B        G = A B
HA2: S = P xor Cin      T = P Cin
OR : Cout = G + T

gates: 2 XOR + 2 AND + 1 OR = 5
delay: Cin -> Cout = AND + OR = 2 gate delays
       A,B -> Cout = XOR + AND + OR = 3
       A,B -> S    = XOR + XOR = 2

Full adder সরাসরি SOP রূপেও বানানো যায়: C_out-এর জন্য তিনটি দুই-ইনপুটের AND আর একটি তিন-ইনপুটের OR, আর S-এর জন্য চারটি তিন-ইনপুটের AND, একটি চার-ইনপুটের OR আর তিনটি NOT. সেখানে gate বেশি, কিন্তু প্রতিটি আউটপুট মাত্র দুই স্তরের (NOT বাদ দিলে)। কোন রূপ ভালো, তা নির্ভর করে কোন gate কত সস্তা আর দ্রুত তার ওপর; CMOS-এ XOR তুলনামূলক বড় gate (পর্ব ০৮), তাই chip-এর নকশায় full adder প্রায়ই আলাদা transistor-স্তরের circuit হিসেবে আঁকা হয়।

৪ · Ripple-carry adder — full adder-এর শিকল

n বিটের দুটি সংখ্যা a = a_n−1…a₀ আর b = b_n−1…b₀ যোগ করতে n টি full adder পাশাপাশি বসান। ঘর i-এর full adder পায় a_i, b_i আর c_i; দেয় s_i আর c_i+1, যা সরাসরি বাঁয়ের ঘরের C_in. সবচেয়ে ডানের ঘরের c₀ সাধারণত ০ (বিয়োগে এটি ১ হয় — অংশ ৯), আর সবচেয়ে বাঁয়ের c_n হলো carry-out, যা থেকে carry flag C আসে। এই নকশার নাম ripple-carry adder, কারণ carry পুকুরের ঢেউয়ের মতো ডান থেকে বাঁয়ে ছড়ায়।

এবার একটি সত্যিকারের যোগ বিট ধরে ধরে দেখুন: 1011 (১১) + 0110 (৬). উত্তর হওয়া উচিত ১৭ = 1 0001. প্রতিটি ধাপে কোন ঘর কাজ করছে আর কোন carry সবে তৈরি হলো, তা দেখুন।

bit      3 2 1 0
carry    ? ? ? 0
a        1 0 1 1
b        0 1 1 0
sum      ? ? ? ?

bit      3 2 1 0
carry    ? ? 0 0
a        1 0 1 1
b        0 1 1 0
sum      ? ? ? 1      s0 = 1, c1 = 0

bit      3 2 1 0
carry    ? 1 0 0
a        1 0 1 1
b        0 1 1 0
sum      ? ? 0 1      s1 = 0, c2 = 1 (generated here)

bit      3 2 1 0
carry    1 1 0 0
a        1 0 1 1
b        0 1 1 0
sum      ? 0 0 1      s2 = 0, c3 = 1 (passed on)

bit      3 2 1 0
carry    1 1 0 0     c4 = 1
a        1 0 1 1
b        0 1 1 0
sum      0 0 0 1
result   1 0001 = 16 + 1 = 17

signal   c1  c2  c3  c4  s0  s1  s2  s3
ready at  2   2   4   6   2   3   3   5   (gate delays)

c2 is fast: bit 1 generates it (1 AND 1)
c3, c4 must wait for the carry chain: +2 each
whole adder settles after 6 gate delays

Ripple কেন ধীর — gate delay গুনে দেখা

প্রতিটি gate-এর ইনপুট বদলানোর পর আউটপুট বদলাতে কিছু সময় লাগে; একে বলে propagation delay. সরল হিসাবের জন্য আমরা ধরব প্রতিটি gate (AND, OR, XOR) = ১ gate delay, আর a, b, c₀ সবই সময় ০-তে হাজির। আসল chip-এ XOR সাধারণত AND-এর চেয়ে ধীর আর delay নির্ভর করে তারের দৈর্ঘ্য ও load-এর ওপর (পর্ব ০৮ আর পর্ব ১৮); কিন্তু তুলনার জন্য এই সরল মডেলই পাঠ্যবই আর পরীক্ষায় চলে।

সবচেয়ে খারাপ ক্ষেত্রের প্রমাণ। ঘর i-তে p_i = a_i ⊕ b_i তৈরি হয় সময় ১-এ। c₁ = g₀ + p₀c₀: AND সময় ২-এ, OR সময় ৩-এ। এরপর প্রতিটি ঘরে c_i+1 = g_i + p_ic_i-এর জন্য c_i আসার পর একটি AND আর একটি OR, অর্থাৎ ২ delay. তাই আরোহ (induction) দিয়ে c_i তৈরি হয় সময় 2i + 1-এ, আর:

অর্থাৎ delay n-এর সাথে রৈখিকভাবে বাড়ে — O(n). এই দীর্ঘতম পথটিকে বলে adder-এর critical path: সব ঘরে p_i = 1 হলে c₀-এর একটি পরিবর্তন সব ঘর পেরিয়ে c_n পর্যন্ত যায় (যেমন 1111 + 0000, c₀ = 1). ৪ বিটে ৯, ১৬ বিটে ৩৩, ৩২ বিটে ৬৫, ৬৪ বিটে ১২৯ gate delay.

সংখ্যাটা কতটা বড়? ধরুন একটি gate delay ২০ picosecond (কেবল বোঝানোর জন্য ধরা একটি মান; আসল মান process আর নকশার ওপর অনেক নির্ভর করে)। তাহলে ৬৪ বিট ripple adder-এ ১২৯ × ২০ = ২,৫৮০ ps ≈ ২.৬ ns লাগে, অর্থাৎ শুধু এই যোগের জন্যই clock প্রায় ৩৯০ MHz-এর বেশি হতে পারবে না। অথচ আজকের ডেস্কটপ CPU ৩–৫ GHz-এ চলে, যেখানে একটি cycle মাত্র ২০০–৩৩৩ ps, আর সেই সময়ের মধ্যে register পড়া, mux পেরোনো, ফল লেখা — সবই করতে হয়। তাই ৩২ আর ৬৪ বিটের CPU-তে খাঁটি ripple adder চলে না।

তবে delay ইনপুটের ওপরও নির্ভর করে। নিচের simulator একটু বাস্তবসম্মত মডেল ব্যবহার করে: AND-এর কোনো ইনপুট ০ হয়ে গেলে আউটপুট তখনই ০ নিশ্চিত, আর OR-এর কোনো ইনপুট ১ হয়ে গেলে আউটপুট তখনই ১ — বাকি ইনপুটের জন্য অপেক্ষা লাগে না। প্রতিটি সংকেতের সাথে “কখন স্থির হলো” সেই সময় রাখা হয়:

// Ripple-carry adder, bit by bit, with a simple timing model:
// every gate = 1 gate delay; inputs a, b, c0 are ready at t = 0;
// AND settles early on a 0 input, OR settles early on a 1 input.
const AND = (x, y) => (x.v & y.v) ? { v: 1, t: 1 + Math.max(x.t, y.t) }
  : { v: 0, t: 1 + Math.min(...[x, y].filter(z => !z.v).map(z => z.t)) };
const OR = (x, y) => (x.v | y.v)
  ? { v: 1, t: 1 + Math.min(...[x, y].filter(z => z.v).map(z => z.t)) }
  : { v: 0, t: 1 + Math.max(x.t, y.t) };
const XOR = (x, y) => ({ v: x.v ^ y.v, t: 1 + Math.max(x.t, y.t) });
function ripple(aStr, bStr, show) {
  const n = aStr.length;
  let c = { v: 0, t: 0 }, sum = "", worst = 0;
  if (show) console.log(" i  a b c_i | s c_i+1  t(s) t(c_i+1)");
  for (let i = 0; i < n; i++) {
    const a = { v: +aStr[n - 1 - i], t: 0 }, b = { v: +bStr[n - 1 - i], t: 0 };
    const g = AND(a, b), p = XOR(a, b);
    const s = XOR(p, c), co = OR(g, AND(p, c));
    if (show) console.log(`${String(i).padStart(2)}  ${a.v} ${b.v}  ${c.v}  | ${s.v}   ${co.v}` +
      `     ${String(s.t).padStart(2)}    ${String(co.t).padStart(2)}`);
    worst = Math.max(worst, s.t, co.t); sum = s.v + sum; c = co;
  }
  console.log(`${aStr} + ${bStr} = ${c.v} ${sum}  -> settles after ${worst}` +
    ` gate delays (n = ${n}, static worst case 2n+1 = ${2 * n + 1})`);
}
ripple("1111", "0001", true);
ripple("0101", "0010", true);
ripple("0110", "0110", true);
ripple("11111111", "00000001", false);
ripple("01100110", "01100110", false);

 i  a b c_i | s c_i+1  t(s) t(c_i+1)
 0  1 1  0  | 0   1      2     2
 1  1 0  1  | 0   1      3     4
 2  1 0  1  | 0   1      5     6
 3  1 0  1  | 0   1      7     8
1111 + 0001 = 1 0000  -> settles after 8 gate delays (n = 4, static worst case 2n+1 = 9)
 i  a b c_i | s c_i+1  t(s) t(c_i+1)
 0  1 0  0  | 1   0      2     2
 1  0 1  0  | 1   0      3     4
 2  1 0  0  | 1   0      5     6
 3  0 0  0  | 0   0      7     3
0101 + 0010 = 0 0111  -> settles after 7 gate delays (n = 4, static worst case 2n+1 = 9)
 i  a b c_i | s c_i+1  t(s) t(c_i+1)
 0  0 0  0  | 0   0      2     2
 1  1 1  0  | 0   1      3     2
 2  1 1  1  | 1   1      3     2
 3  0 0  1  | 1   0      3     3
0110 + 0110 = 0 1100  -> settles after 3 gate delays (n = 4, static worst case 2n+1 = 9)
11111111 + 00000001 = 1 00000000  -> settles after 16 gate delays (n = 8, static worst case 2n+1 = 17)
01100110 + 01100110 = 0 11001100  -> settles after 4 gate delays (n = 8, static worst case 2n+1 = 17)

৫ · Carry-lookahead — generate আর propagate

Ripple-এর সমস্যা হলো c_i+1 জানতে c_i-এর জন্য অপেক্ষা। কিন্তু c_i নিজেও তো a, b আর c₀-এরই একটি Boolean function! তাহলে সব carry সরাসরি মূল ইনপুট থেকে হিসাব করা যায় না কেন? এই ধারণার নাম carry-lookahead adder (CLA). এর জন্য প্রতিটি ঘরে দুটি সংকেত সংজ্ঞায়িত করুন:

অংশ ৩-এর সূত্র C_out = AB + C_in(A ⊕ B) এখন হুবহু লেখা যায় c_i+1 = g_i + p_ic_i, আর sum হয় s_i = p_i ⊕ c_i. এবার এই recurrence-কে বারবার নিজের ভেতরে বসিয়ে খুলে ফেলুন:

প্রতিটি পদের একটি সহজ অর্থ আছে। যেমন c₄-এর p₃p₂g₁ পদ বলে: “bit 1 carry তৈরি করেছে, আর bit 2 ও bit 3 সেটি পার করে দিয়েছে।” অর্থাৎ c_i+1 = 1 ঠিক তখনই, যখন i-এর নিচের কোনো ঘর j carry তৈরি করেছে (বা c₀ = 1) আর j-এর ওপরের i পর্যন্ত সব ঘর propagate করে। এটাই সূত্রের প্রমাণও — carry একমাত্র এভাবেই ঘর i পর্যন্ত পৌঁছাতে পারে, আর সূত্রটি সব সম্ভাব্য শুরুর ঘর j = −1 (c₀), 0, …, i-এর OR.

p = a ⊕ b, নাকি a + b? বইভেদে দুটিই দেখবেন। Carry-র জন্য দুটিই ঠিক: পার্থক্য শুধু a_i = b_i = 1 ঘরে, যেখানে OR-রূপে p_i = 1 কিন্তু XOR-রূপে ০. সেই ঘরে g_i = 1, তাই c_i+1 = g_i + p_ic_i = 1 দুই রূপেই — বাড়তি p_ic_i পদটি কিছু বদলায় না। (৪ বিটের a, b আর c₀-এর সব ৫১২টি সমন্বয়ে একটি স্ক্রিপ্ট দিয়েও আমরা মিলিয়ে দেখেছি।) OR gate XOR-এর চেয়ে ছোট আর দ্রুত, তাই lookahead logic-এ অনেক সময় OR-রূপ নেওয়া হয়। কিন্তু sum-এর জন্য XOR-রূপ লাগে: s_i = p_i ⊕ c_i কেবল p_i = a_i ⊕ b_i হলেই ঠিক। আর XOR-রূপে g আর p কখনো একসাথে ১ হয় না, যা carry-skip-এর মতো নকশায় কাজে লাগে।

এবার অংশ ৪-এর একই যোগ 1011 + 0110 নিন, কিন্তু এবার c₄ সরাসরি সূত্র দিয়ে — কোনো ঘরের অপেক্ষা ছাড়া:

bit          3 2 1 0
a            1 0 1 1
b            0 1 1 0
g = a AND b  0 0 1 0     g3 g2 g1 g0
p = a XOR b  1 1 0 1     p3 p2 p1 p0
c0 = 0

c1 = g0 + p0 c0           = 0 + 1·0         = 0
c2 = g1 + p1 g0 + p1 p0 c0
   = 1  + 0·0  + 0·1·0    = 1   (g1 = 1 is enough)

c3 = g2 + p2 g1 + p2 p1 g0 + p2 p1 p0 c0
   = 0  + 1·1  + 1·0·0    + 1·0·1·0
   = 1   (bit 1 generates, bit 2 propagates)

c4 = g3 + p3 g2 + p3 p2 g1 + p3 p2 p1 g0 + p3 p2 p1 p0 c0
   = 0  + 1·0   + 1·1·1    + 1·1·0·0     + 1·1·0·1·0
   = 1   (bit 1 generates, bits 2 and 3 propagate)

carries c4 c3 c2 c1 c0 = 1 1 1 0 0   (same as ripple)
sum s = p xor c = 1101 xor 1100 = 0001  -> 1 0001 = 17

time: g, p at 1 -> all AND terms at 2 -> all ORs at 3
      every carry ready at 3, every sum at 4
ripple needed 6 here, 9 in the worst case

৪ বিটের CLA ব্লক — delay আর দাম

৪ বিটের CLA ব্লকে তিনটি অংশ: (১) চারটি AND আর চারটি XOR দিয়ে g আর p (১ delay); (২) উপরের চারটি সূত্রের AND-OR লজিক (আরও ২ delay); (৩) চারটি XOR দিয়ে sum (আরও ১ delay). মোট ৪ gate delay, ripple-এর ৯-এর জায়গায়। Carry লজিকে AND লাগে ১ + ২ + ৩ + ৪ = ১০টি আর OR লাগে ৪টি; সব মিলিয়ে ৪ + ৪ + ১৪ + ৪ = ২৬টি gate, ripple-এর ২০টির চেয়ে একটু বেশি।

তাহলে ৬৪ বিটে কেন একবারে খুলে লিখি না? দুটি বাধা। প্রথম, gate-এর fan-in: c₆₄-এর শেষ পদে ৬৫টি ইনপুটের AND, আর পুরো সূত্রে ৬৫ ইনপুটের OR লাগবে। CMOS-এ ৪–৫টির বেশি ইনপুটের gate ধীর হয়ে যায় (series transistor বাড়ে — পর্ব ০৮), তাই “দুই স্তর” আসলে আর দুই স্তর থাকে না। দ্বিতীয়, আকার: n বিট একবারে খুললে AND gate লাগে 1 + 2 + … + n = n(n + 1)/2, অর্থাৎ ৬৪ বিটে ২,০৮০টি — O(n²), আর প্রতিটি p_i-কে অসংখ্য gate-এ তার টেনে নিতে হয়। সমাধান: ছোট ব্লক, আর ব্লকের ওপরে আবার lookahead.

৬ · বড় adder-এ lookahead — group G, P আর বহুস্তর CLA

৪ বিটের একটি ব্লককে বাইরে থেকে একটি “বড় ঘর” হিসেবে দেখুন। এটিও দুই কাজের একটি করতে পারে: নিজেই carry তৈরি করা, বা ঢোকা carry পার করে দেওয়া। তাই এর জন্যও group generate আর group propagate সংজ্ঞায়িত করা যায়:

অর্থাৎ ব্লকের carry-out = G + P·c_in — একটি বিটের সূত্রের হুবহু একই আকার! P বলে “চারটি ঘরই পার করে” আর G বলে “ব্লকের ভেতরে কোথাও carry তৈরি হয়ে বাইরে পর্যন্ত গেছে।” তাই চারটি ব্লকের (G₀, P₀) … (G₃, P₃) নিয়ে একটি দ্বিতীয় স্তরের lookahead carry unit (LCU) ঠিক আগের সূত্রগুলো দিয়ে c₄, c₈, c₁₂, c₁₆ বের করতে পারে:

Delay-এর হিসাব (একই মডেল: প্রতি gate ১, fan-in ৫ পর্যন্ত চলে, NOT ধরা হয়নি)। ১৬ বিটে: g, p সময় ১-এ; ব্লকের P সময় ২-এ (একটি AND), G সময় ৩-এ (AND-OR); LCU-র c₄, c₈, c₁₂, c₁₆ সময় ৫-এ (আরও AND-OR); প্রতিটি ব্লক তার ভেতরের carry বের করে সময় ৭-এ; sum সময় ৮-এ। ৬৪ বিটে আরেকটি স্তর: ১৬টি ব্লক → ৪টি ১৬ বিটের দল → একটি শীর্ষ unit. প্রতিটি স্তর ওঠার সময় +২ আর নামার সময় +২ — L স্তরে মোট 4L gate delay, যেখানে L = ⌈log₄ n⌉. তাই delay বাড়ে log n হারে: ৪ বিটে ৪, ১৬ বিটে ৮, ৬৪ বিটে ১২. (৩২ বিটেও এই মডেলে তিন স্তর লাগে, তাই ১২.)

আরেকটি সস্তা মাঝামাঝি পথ: ৪ বিটের CLA ব্লকগুলোকে ripple-এর মতো শিকলে জোড়া, অর্থাৎ প্রতিটি ব্লকের c_out = G + P·c_in পরের ব্লকে যায়। প্রথম ব্লকের c₄ সময় ৩-এ, তারপর প্রতি ব্লকে +২, শেষ ব্লকের sum আরও ৩ পরে: মোট n/2 + 2. নিচের calculator প্রথমে ৪ বিট আর ১৬ বিট ইনপুটে প্রতিটি carry সরাসরি খোলা সূত্র দিয়ে বের করে ripple-এর সাথে মেলায়, তারপর চার রকম নকশার delay পাশাপাশি দেখায় (carry-select পরের অংশে):

// Carry-lookahead: g, p and every carry from the flat two-level equation
// c(i+1) = g_i + p_i g_(i-1) + ... + p_i...p_0 c0, checked against ripple.
const str = (arr) => [...arr].reverse().join("");   // MSB on the left
function cla(a, b, n, c0 = 0) {
  const g = [], p = [], c = [c0];
  for (let i = 0; i < n; i++) { g[i] = (a >> i) & (b >> i) & 1; p[i] = ((a ^ b) >> i) & 1; }
  for (let i = 0; i < n; i++) {
    let ci = 0;                                     // OR of product terms
    for (let j = -1; j <= i; j++) {
      let term = j < 0 ? c0 : g[j];
      for (let k = j + 1; k <= i; k++) term &= p[k];
      ci |= term;
    }
    c[i + 1] = ci;
  }
  let rc = c0, ok = true;                          // ripple check
  for (let i = 0; i <= n; i++) { ok = ok && rc === c[i]; if (i < n) rc = g[i] | (p[i] & rc); }
  const s = p.map((x, i) => x ^ c[i]);
  console.log(`n=${n}  g = ${str(g)}  p = ${str(p)}`);
  console.log(`      carries c${n}..c0 = ${str(c)}  sum = ${c[n]} ${str(s)}  ripple agrees: ${ok}`);
  if (n === 16) for (let k = 0; k < 4; k++) {       // group G, P per 4-bit block
    const [g0, g1, g2, g3] = g.slice(4 * k), [p0, p1, p2, p3] = p.slice(4 * k);
    const G = g3 | (p3 & g2) | (p3 & p2 & g1) | (p3 & p2 & p1 & g0), P = p3 & p2 & p1 & p0;
    console.log(`      block ${k}: G=${G} P=${P}  c${4 * k + 4} = G + P*c${4 * k} = ${G | (P & c[4 * k])}`);
  }
}
cla(0b1011, 0b0110, 4);
cla(0xBEEF, 0x4111, 16);
// Delay in gate delays (every gate 1, any fan-in up to 5, NOT ignored)
console.log("\n   n  ripple  4-bit CLA rippled  multi-level CLA  carry-select(4-bit)");
for (const n of [4, 16, 32, 64]) {
  const L = Math.ceil(Math.log(n) / Math.log(4) - 1e-9);   // lookahead levels
  const row = [2 * n + 1, n / 2 + 2, 4 * L, 9 + 2 * (n / 4 - 1)];
  console.log(String(n).padStart(4) + row.map((d, i) => String(d).padStart([8, 19, 17, 21][i])).join(""));
}

n=4  g = 0010  p = 1101
      carries c4..c0 = 11100  sum = 1 0001  ripple agrees: true
n=16  g = 0000000000000001  p = 1111111111111110
      carries c16..c0 = 11111111111111110  sum = 1 0000000000000000  ripple agrees: true
      block 0: G=1 P=0  c4 = G + P*c0 = 1
      block 1: G=0 P=1  c8 = G + P*c4 = 1
      block 2: G=0 P=1  c12 = G + P*c8 = 1
      block 3: G=0 P=1  c16 = G + P*c12 = 1

   n  ripple  4-bit CLA rippled  multi-level CLA  carry-select(4-bit)
   4       9                  4                4                    9
  16      33                 10                8                   15
  32      65                 18               12                   23
  64     129                 34               12                   39

খরচ কত? প্রতিটি ৪ বিটের ব্লক বা unit-এ মোটামুটি নির্দিষ্ট সংখ্যক gate, আর ব্লক থাকে n/4টি, তাদের ওপরে n/16টি unit, তার ওপরে n/64… — যোগফল প্রায় n/3টি unit. তাই বহুস্তর CLA-র আকার মোটামুটি n-এর সমানুপাতিক থাকে (ripple-এর কয়েক গুণ), কিন্তু delay হয় O(log n). একবারে খোলা সূত্রের O(n²) আকারের তুলনায় এটি অনেক বাস্তবসম্মত। দাম অবশ্য শুধু gate-এ নয়: লম্বা তার, বেশি fan-out আর বেশি switching মানে বেশি power.

৭ · আরও দ্রুত adder — carry-select, carry-skip আর prefix adder

Lookahead একমাত্র কৌশল নয়। প্রকৌশলীরা বহু দশক ধরে carry-র অপেক্ষা কমানোর নানা উপায় বের করেছেন। তিনটি গুরুত্বপূর্ণ ধারণা:

Carry-select — দুই উত্তর আগেই তৈরি রাখা

পরীক্ষার ফল বের হওয়ার আগে একজন ছাত্র দুটি পরিকল্পনা তৈরি রাখেন — পাস করলে এক পথ, না করলে আরেক পথ; ফল আসামাত্র একটি বেছে নেন। Carry-select adder একই কাজ করে। ১৬ বিটকে চারটি ৪ বিটের ব্লকে ভাগ করুন। ব্লক ০ সাধারণ ripple. বাকি প্রতিটি ব্লকে দুটি ৪ বিটের ripple adder — একটি ধরে নেয় carry-in = 0, অন্যটি carry-in = 1 — দুটিই একই সময়ে কাজ শুরু করে। আসল carry-in এলে একটি multiplexer (পর্ব ১২) ঠিক উত্তরটি বেছে নেয়।

Delay-এর হিসাব: সব ৪ বিটের ripple ব্লক একসাথে শেষ হয় সময় ২ × ৪ + ১ = ৯-এ। ব্লক ০-এর c₄ তখনই হাজির। ব্লক k-এর carry-out বাছাই করতে c_out = c_out⁽⁰⁾ + c_out⁽¹⁾·c_in — একটি AND আর একটি OR, অর্থাৎ ২ delay (এখানে inverter-ও লাগে না, কারণ c_out⁽¹⁾ কখনো c_out⁽⁰⁾-এর চেয়ে ছোট নয়)। তাই c₈ সময় ১১-এ, c₁₂ ১৩-এ, c₁₆ আর শেষ ব্লকের বাছাই করা sum ১৫-এ। সাধারণভাবে 9 + 2(n/4 − 1): ১৬ বিটে ১৫, ৬৪ বিটে ৩৯ — ripple-এর ৩৩ আর ১২৯-এর চেয়ে অনেক কম, যদিও প্রায় দ্বিগুণ adder লাগে। ব্লকগুলোর আকার সমান না রেখে ধীরে ধীরে বড় করলে (প্রায় √n আকারের ব্লক) delay আরও কমে, O(√n).

Carry-skip বা carry-bypass — লাফিয়ে পার হওয়া

Carry-skip adder-এ প্রতিটি ripple ব্লকের পাশে একটি “বাইপাস সড়ক”। ব্লকের group P = 1 হলে (সব ঘর propagate করে) ঢোকা carry সরাসরি বেরিয়ে যায়, ব্লকের ভেতর দিয়ে হাঁটতে হয় না: c_out = (ripple থেকে আসা carry) + P·c_in. যুক্তিটি সুন্দর: P = 0 হলে ব্লকের অন্তত একটি ঘর propagate করে না, তাই ব্লকের carry-out ঢোকা carry-র ওপর নির্ভরই করে না — সেটি ব্লকের ভেতরেই তৈরি হয় বা ০ হয়। ফলে বাইরের carry-কে কখনো পুরো ব্লকের ভেতর দিয়ে হাঁটতে হয় না। Hardware সামান্য বাড়ে (প্রতি ব্লকে একটি AND আর একটি OR), কিন্তু সবচেয়ে খারাপ delay অনেক কমে। এর delay ইনপুটভেদে বদলায় বলে এর সঠিক timing বিশ্লেষণ একটু কঠিন।

Prefix adder — Kogge–Stone আর Brent–Kung

একটি বিমূর্ত পর্যবেক্ষণ সব দ্রুত adder-কে একসূত্রে বাঁধে। (G, P) জোড়ার ওপর একটি অপারেটর ভাবুন: (G_hi, P_hi) ∘ (G_lo, P_lo) = (G_hi + P_hiG_lo, P_hiP_lo). এটি ঠিক অংশ ৬-এর “দুটি পাশাপাশি দলকে একটি বড় দল বানানো”, আর এটি associative (বন্ধনী যেভাবেই বসান, ফল একই)। তাই সব carry বের করা মানে একটি prefix computation — অনেকটা prefix sum-এর মতো (যা DSA কোর্সের prefix sums পর্বে আছে)। Associative অপারেটরের prefix গাছের আকারে log₂ n স্তরে হিসাব করা যায়। এভাবে বানানো adder-কে বলে prefix adder.

এদের মাঝামাঝি আরও নকশা আছে (Sklansky, Han–Carlson, Ladner–Fischer ইত্যাদি), প্রতিটি স্তর, cell, fan-out আর তারের মধ্যে আলাদা আপস করে। আমাদের ৪ বিটের বহুস্তর CLA আসলে prefix-এরই একটি রূপ, যেখানে প্রতি স্তরে চারটি দল একসাথে মেলানো হয়।

৮ · BCD adder — দশমিক অঙ্কের যোগ আর +6 সংশোধন

পর্ব ০৪-এ আপনি BCD-তে হাতে যোগ করেছেন: প্রতিটি দশমিক অঙ্ক ৪ বিটে, আর যোগফল ৯-এর বেশি হলে 0110 (৬) যোগ। এবার এর hardware: BCD adder. এক অঙ্কের BCD adder-এ তিনটি অংশ — একটি সাধারণ ৪ বিটের binary adder (আমাদের ripple বা CLA), একটি সংশোধন-শর্ত বের করার ছোট circuit, আর শর্ত ১ হলে 0110 যোগ করার জন্য দ্বিতীয় একটি ৪ বিটের adder.

শর্তের প্রমাণ। দুটি BCD অঙ্ক আর carry-in মিলে যোগফল সর্বোচ্চ ৯ + ৯ + ১ = ১৯. প্রথম adder-এর আউটপুট carry K আর ৪ বিট Z₃Z₂Z₁Z₀. সংশোধন লাগে যখন যোগফল ≥ ১০, দুই ক্ষেত্রে:

• যোগফল ১৬–১৯: binary adder নিজেই carry দেয়, K = 1. (Z তখন 0000–0011, যা দেখতে বৈধ BCD, কিন্তু ১৬ বাদ গেছে — তাই K দেখা জরুরি।)
• যোগফল ১০–১৫: K = 0, আর Z = 1010 থেকে 1111. এই ছয়টি প্যাটার্নের K-map-এ Z₃ = 1 দুই সারিতে: Z₃Z₂ = 11 (১২–১৫) পুরো সারিটি একটি দল, আর Z₃Z₁ = 1-এর ঘরগুলো (১০, ১১, ১৪, ১৫) আরেকটি দল। ১০–১৫ ছাড়া কোনো ৪ বিট প্যাটার্নে এই দুই দলের কোনোটি ১ হয় না, কারণ Z₃ = 1 মানে ≥ ৮, আর ৮ (1000) ও ৯ (1001)-এ Z₂ = Z₁ = 0.

C = 1 হলে Z-এর সাথে 0110 যোগ হয়, আর C নিজেই পরের (দশকের) অঙ্কের carry হয়ে যায়। কেন ঠিক ৬? কারণ ৪ বিট ১৬-তে ঘুরে আসে কিন্তু দশমিক অঙ্ক ১০-এ; ৬ যোগ করলে মাঝের ছয়টি অবৈধ প্যাটার্ন (1010–1111) লাফিয়ে পার হয়, আর ১০ বেশি মানে carry-তে চলে যায়: (Z + 6) mod 16 = Z − 10. নিচের simulator কয়েকটি অঙ্ক-জোড়া, একটি দুই অঙ্কের যোগ আর সব ২০০টি সম্ভাব্য ক্ষেত্র যাচাই করে:

// One-digit BCD adder: 4-bit binary add, then add 0110 when
// C = K + Z3*Z2 + Z3*Z1 (K = binary carry-out, Z3..Z0 = binary sum).
const b4 = (v) => v.toString(2).padStart(4, "0");
function bcdDigit(x, y, cin) {
  const t = x + y + cin, K = t >> 4, Z = t & 15;
  const z3 = (Z >> 3) & 1, z2 = (Z >> 2) & 1, z1 = (Z >> 1) & 1;
  const C = K | (z3 & z2) | (z3 & z1);              // correction needed?
  const D = C ? (Z + 6) & 15 : Z;                    // corrected digit
  return { K, Z, C, D };
}
console.log("x + y + cin | K Z3..Z0 | C | BCD out   | decimal");
for (const [x, y, cin] of [[5, 3, 0], [4, 6, 0], [8, 7, 0], [9, 9, 0], [9, 9, 1]]) {
  const { K, Z, C, D } = bcdDigit(x, y, cin);
  console.log(`${x} + ${y} + ${cin}   | ${K} ${b4(Z)}   | ${C} | ${C} ${b4(D)}    | ` +
    `${C * 10 + D}${C ? "  (+0110 added)" : ""}`);
}
// Two-digit BCD: 58 + 67, units digit first, carry goes to the tens digit
const u = bcdDigit(8, 7, 0), t = bcdDigit(5, 6, u.C);
console.log(`\n58 + 67 -> ${t.C} ${b4(t.D)} ${b4(u.D)} = ${t.C}${t.D}${u.D}`);
let bad = 0;                                         // check all 200 cases
for (let x = 0; x <= 9; x++) for (let y = 0; y <= 9; y++) for (let c = 0; c <= 1; c++) {
  const r = bcdDigit(x, y, c);
  if (r.C * 10 + r.D !== x + y + c) bad++;
}
console.log(`all 200 digit cases checked, mismatches = ${bad}`);

x + y + cin | K Z3..Z0 | C | BCD out   | decimal
5 + 3 + 0   | 0 1000   | 0 | 0 1000    | 8
4 + 6 + 0   | 0 1010   | 1 | 1 0000    | 10  (+0110 added)
8 + 7 + 0   | 0 1111   | 1 | 1 0101    | 15  (+0110 added)
9 + 9 + 0   | 1 0010   | 1 | 1 1000    | 18  (+0110 added)
9 + 9 + 1   | 1 0011   | 1 | 1 1001    | 19  (+0110 added)

58 + 67 -> 1 0010 0101 = 125
all 200 digit cases checked, mismatches = 0

৯ · Adder কোথায় বসে — ALU, subtractor, Verilog আর software

বিয়োগ। Two's complement-এ A − B = A + B′ + 1 (পর্ব ০৫)। তাই একটি adder-এর B ইনপুটে প্রতিটি বিটের সামনে একটি XOR বসান, যার অন্য ইনপুট একটি নিয়ন্ত্রণ-সংকেত SUB: SUB = 0 হলে b_i ⊕ 0 = b_i (যোগ), SUB = 1 হলে b_i ⊕ 1 = b_i′. আর “+1”-টি আসে c₀ = SUB দিয়ে, বিনা খরচে। এই adder-subtractor, তার carry, overflow, zero আর negative flag-এর পুরো হিসাব পর্ব ২০-এ, আর যোগ-বিয়োগ-লজিক এক জায়গায় করা ALU-র নকশা পর্ব ১৩-এ। গুণের দ্রুত circuit (পর্ব ২১) আসলে অনেকগুলো adder-এর সারি, আর তুলনা (A < B?) মূলত একটি বিয়োগের চিহ্ন দেখা। RISC-V-র add, sub, addi, slt, এমনকি load-store-এর ঠিকানা হিসাব — সবখানেই এই একই adder.

Hardware description language-এ। আসল chip-এর নকশাকার gate হাতে আঁকেন না; লেখেন Verilog-এর মতো ভাষায় (পর্ব ১৪)। নিচে একটি full adder আর তা দিয়ে ৪ বিটের ripple adder — synthesizable ধাঁচে:

module full_adder (input  wire a, b, cin,
                   output wire s, cout);
  assign s    = a ^ b ^ cin;
  assign cout = (a & b) | (cin & (a ^ b));
endmodule

module ripple4 (input  wire [3:0] a, b,
                input  wire       c0,
                output wire [3:0] s,
                output wire       c4);
  wire [4:0] c;
  assign c[0] = c0;
  genvar i;
  generate
    for (i = 0; i < 4; i = i + 1) begin : stage
      full_adder fa (.a(a[i]), .b(b[i]), .cin(c[i]), .s(s[i]), .cout(c[i+1]));
    end
  endgenerate
  assign c4 = c[4];
endmodule

বাস্তবে অনেক নকশাকার শুধু assign {c4, s} = a + b + c0; লেখেন, আর synthesis tool timing-এর লক্ষ্য দেখে নিজেই ripple, CLA বা prefix নকশা বেছে নেয়। তবু কোন নকশা কেন বাছা হলো, তা বুঝতে এই পর্বের জ্ঞানই লাগে।

Software-এ full adder. Hardware-এর সূত্র সত্যিই ঠিক কি না, তা software-এ লাখো ইনপুটে চালিয়ে দেখা যায়। নিচের C প্রোগ্রাম ৩২টি full adder-এর সূত্র লুপে চালিয়ে দুটি uint32_t যোগ করে, আর CPU-র নিজের +-এর সাথে মেলায়। ইনপুট আসে নির্দিষ্ট seed-এর একটি সরল pseudo-random generator থেকে, তাই প্রতিবার একই সংখ্যা:

#include <stdio.h>
#include <stdint.h>

/* 32 full adders in software: sum and carry formulas, bit by bit */
static uint32_t ripple_add(uint32_t a, uint32_t b, unsigned *cout) {
    uint32_t s = 0, c = 0;
    for (int i = 0; i < 32; i++) {
        uint32_t x = (a >> i) & 1u, y = (b >> i) & 1u;
        s |= (x ^ y ^ c) << i;              /* S    = A xor B xor Cin   */
        c = (x & y) | (c & (x ^ y));        /* Cout = AB + Cin(A xor B) */
    }
    *cout = (unsigned)c;
    return s;
}

int main(void) {
    uint32_t seed = 2026u;                  /* fixed seed: same numbers every run */
    long bad = 0, N = 1000000;
    unsigned c;
    for (long t = 0; t < N; t++) {
        seed = seed * 1664525u + 1013904223u;  uint32_t a = seed;
        seed = seed * 1664525u + 1013904223u;  uint32_t b = seed;
        uint32_t s = ripple_add(a, b, &c);
        uint64_t ref = (uint64_t)a + b;         /* the CPU's own adder */
        if (s != (uint32_t)ref || c != (unsigned)(ref >> 32)) bad++;
        if (t < 3) printf("0x%08X + 0x%08X = 0x%08X carry %u\n",
                          (unsigned)a, (unsigned)b, (unsigned)s, c);
    }
    uint32_t s = ripple_add(0xFFFFFFFFu, 1u, &c);
    printf("0xFFFFFFFF + 0x00000001 = 0x%08X carry %u\n", (unsigned)s, c);
    printf("random tests: %ld, mismatches with + : %ld\n", N, bad);
    return 0;
}

0x05709641 + 0x0B5D7AAC = 0x10CE10ED carry 0
0x09DAB61B + 0xA9BBF4BE = 0xB396AAD9 carry 0
0xA50C1505 + 0x7BE902A0 = 0x20F517A5 carry 1
0xFFFFFFFF + 0x00000001 = 0x00000000 carry 1
random tests: 1000000, mismatches with + : 0

১০ · AI-এর যুগে adder নকশা

AI টুল half adder-এর সূত্র নির্ভুল বলে, কিন্তু lookahead-এর খোলা সূত্র, delay গোনা আর BCD সংশোধনের মতো জায়গায় প্রায়ই সূক্ষ্ম ভুল করে। কয়েকটি সাধারণ উদাহরণ:

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

• Full adder-এর ৮টি সারি নিজে truth table-এ মিলিয়েছি
• Lookahead সূত্রের প্রতিটি পদের অর্থ (কোন ঘর তৈরি করল, কোন ঘরগুলো পার করল) পড়ে দেখেছি
• Delay-এর মডেল (কোন gate কত, fan-in সীমা, XOR আলাদা কি না) স্পষ্ট লেখা আছে
• সবচেয়ে খারাপ ইনপুট (দীর্ঘ propagate শিকল, যেমন 0xFFFF + 0x0001) আর সীমানার ক্ষেত্র দিয়ে পরীক্ষা করেছি
• BCD-তে ৯ + ৯ আর ৯ + ৯ + ১ চালিয়ে দেখেছি
• Verilog কোড simulator-এ চালিয়ে testbench-এ সব ইনপুট মিলিয়েছি, synthesis-এর latch warning নেই