Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Carry lookahead adder - How is this possible?

  1. Sep 29, 2010 #1
    1. The problem statement, all variables and given/known data

    I have a book which says that the gate delay for generating Ci is 2 logr(n) + 1, where r is the fan-in for each gate and n is the number of bits.

    This implies that with a fan-in of 2 and 4 bits, the delay for a generating C5 as shown below should be 5 gate delays. How is this possible?


    2. Relevant equations

    For an n-bit carry lookahead adder, it is well known that the carry out can be determined by examining the 'carry propagate' and 'carry generate' for each of the inputs. This allows the carry out to be expressed solely in terms of the input bits and carry-in.

    As an example, the carry-out for a four bit adder is given by:

    C5 = G4 + P4G3 + P4P3G2 + P4P3P2G1 + P4P3P2P1C

    Where
    C is the carry in,
    Carry propagate Pi = Ai + Bi,
    Carry generate Gi = AiBi


    3. The attempt at a solution

    Initially:
    We have the inputs
    C,
    A1,
    B1,
    A2,
    B2,
    A3,
    B3,
    A4,
    B4

    After one gate delay:
    The carry-propagate and carry generate for each bit can be determined. So we have
    C,
    G1,
    P1,
    G2,
    P2,
    G3,
    P3, G4, P4

    After two gate delays:
    We can use 'and' to start the carry propagates and carry generates together. So we have

    P4G3,
    P4P3,
    P2G1,
    P2P1

    After three gate delays:
    Now we can use 'or', and also continue 'anding' together the propogates
    So
    G4 + P4G3,
    P4P3G2,
    P4P3P2G1,
    P4P3P2P1


    After four gate delays:

    G4 + P4G3 + P4P3G2,
    P4P3P2G1,
    P4P3P2P1C


    After five gate delays:
    G4 + P4G3 + P4P3G2 + P4P3P2G1,
    P4P3P2P1C

    This is too slow. There is still more work to be done as we need another 'OR' to put the two remaining terms together.

    How is it possible to determine the carry out in only five gate delays?
     
  2. jcsd
  3. Sep 29, 2010 #2

    berkeman

    User Avatar

    Staff: Mentor

    I only skimmed the question, but why are you constrained to 2-input AND logic?
     
  4. Sep 29, 2010 #3
    That's the difficulty...The book states that Ci can be found in 2 logr(n) + 1 delays, where r is the number of inputs for each gate. So for 2 inputs and 4 bits, that's 5 delays.

    Apparently it's possible, but I can't do it in less than six. There must be some trick or logic identity to exploit.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook