2
\$\begingroup\$

I am a bit stuck with the concept of carry-lookahead adder so I'd like to compare it with another concept I'm more familiar with: the ripple-carry adder. I'm trying to make some basic math comparison between the two ones.

Assuming every gate can accept at most 2 (two) inputs and has a delay of '1', and that, at least for the moment, we're adding two 4-bit numbers.

Let's start with the ripple-carry adder. I've built it putting four full-adder in column. Every carry-out is computed as

$$c_i^{(\text{out})} = a_i \cdot b_i + \left[ a_i + b_i \right] \cdot c_i^{(\text{in})} \qquad \text{where} \; \cdot \equiv \text{AND},\, + \equiv \text{OR}$$

Since

$$\left[ a_i + b_i \right]$$

is computed in parallel for every full-adder, the cost for computing the k-th carry-out is

$$1 + 2k$$

right?

Now say we want to compute carry's at first, then the sum -- bit by bit. Using the formula above, (and omitting the superscript) we write that

$$c_{i+1} = g_i + p_i c_i$$

Hence, we can write recursively the fourth term as a function of the first one, i.e.

$$c_1 = g_0 + p_0 c_0 \\ c_2 = g_1 + p_1 g_0 + p_1 p_0 c_0 \\ \vdots \\ c_4 = g_3 + p_3 g_2 + p_3 p_2 g_1 + p_3 p_2 p_1 g_0 + p_3 p_2 p_1 p_0 c_0$$

Of course it is the last term that costs more. How much? I'd say

$$\lceil \log_2{4} \rceil + \lceil \log_2{4} \rceil $$

where the first term is needed for computing every AND operations, while the second one for computing every OR operation.

Hence for an overview ...

$$1 + \lceil \log_2{k} \rceil + 2$$

where the first term is the gate delay needed for computing every propagator/generator term, the second term is the one needed for computing every carry_in, then the last term is the gate delay of a single full-adder.

That is, the comparison of "time" between a ripple-carry adder and a carry-lookahead's one is the comparison of the following two functions

$$1 + 2k$$ $$3 + \lceil \log_2{k} \rceil$$

I know that carry-lookahead can be improved more, and I've done that by myself...though I'd like you give me some feedback about the stuff above for now.

\$\endgroup\$
8
  • \$\begingroup\$ I think your assumption that each port can take 2 inputs does not correspond with reality: a 4 input NAND port would have 2 port delays under your assumption, but in reality it has just 1 port delay, just like a 2 input port. \$\endgroup\$ Commented Dec 15, 2013 at 20:40
  • \$\begingroup\$ @WoutervanOoijen uhm yes!, I would've implemented a 4 input NAND !(abcd) with two NAND's in parallel then a OR gate !(ab) + !(cd), resulting in a 2 port delay. Where am I wrong? \$\endgroup\$ Commented Dec 15, 2013 at 21:32
  • 1
    \$\begingroup\$ A 4 input NAND is just that: a 4 input NAND, with delay 1. That's (roughly) how the hardware works. \$\endgroup\$ Commented Dec 15, 2013 at 21:48
  • \$\begingroup\$ @WoutervanOoijen Hence, a + b + c + d + e + f can be implemented simply with a 6 input OR, with delay 1? I mean: I should not care about the number of inputs of the gates but instead about the number of gates I have to pass through before the output become stable, right? \$\endgroup\$ Commented Dec 15, 2013 at 22:00
  • 1
    \$\begingroup\$ The delay through a logic gate as a function of the number of inputs depends greatly on how you are implementing the gate. For an FPGA, logic functions might be implemented using a 4 or 5-input MUX so anything with up to 5 inputs would have the same delay. In an ASIC, the gate delay tends to increase with the number of inputs (all else being equal). \$\endgroup\$
    – Joe Hass
    Commented Dec 15, 2013 at 23:29

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.