Carry Lookahead Adder

দুইটা সিগন্যাল প্রতিটা bit-position i-এ:

Gᵢ = Aᵢ · Bᵢ         (এই stage নিজেই carry generate করে)
Pᵢ = Aᵢ ⊕ Bᵢ         (আগের carry থাকলে propagate করে)
Cᵢ₊₁ = Gᵢ + Pᵢ·Cᵢ

Gᵢ, Pᵢ শুধু নিজের input-এর উপর নির্ভর করে — তাই সব stage-এ সমান্তরালে গণনা হয়। Recurrence বারবার expand করে প্রতিটা Cᵢ-কে শুধু A, B, C₀-এর সরাসরি SOP-তে লেখা যায় — কোনো Cᵢ অন্য Cⱼ-এর জন্য অপেক্ষা করে না।

সমস্যা: flat expansion-এ Cᵢ-এর সূত্র i বাড়ার সাথে বড় হয় (fan-in বাড়ে)। তাই বাস্তব CLA hierarchical — ছোট ব্লকে (৪-bit) lookahead, তারপর ব্লক-carry আবার lookahead দিয়ে। ফল: delay O(n) থেকে নেমে আনুমানিক O(\log n)।

৩২-bit-এ: ripple-carry ~১৬০ gate, ~৬৪ depth। CLA ~৫০০ gate (৩×), কিন্তু ~১০ depth (৬×দ্রুত)। এটাই [[asymptotic-notation]] লেসনের time–space trade-off-এর hardware সংস্করণ — gate (area) খরচ করে delay (time) কেনা।

মূল প্রস্তাবক: Weinberger ও Smith, ১৯৫৮। আধুনিক CPU বেশিরভাগ সময় hierarchical CLA-র উত্তরসূরি — carry-select বা Kogge-Stone prefix adder — ব্যবহার করে।