Chapter B, Problem 27E

Explanation of Solution

• The above diagram describes about the 64 bit carry look ahead adder that includes 64 numbers of 1-bit full adders to add the 64 bits.
• It includes carry generator, carry propagator and sum.
  • Carry generator denoted by G is used for generating the output query without depending on input query.
  • Carry propagator denoted by P is used for propagating the next state.
  • The sum of each adder is denoted by S.

From the above diagram, the carry propagator (P) and carry generator (G) are calculated as follows

${\text{P}}_{\text{i}}\text{=}{\text{A}}_{\text{i}}\oplus {\text{B}}_{\text{i}}$

${\text{G}}_{\text{i}}\text{=}{\text{A}}_{\text{i}}\cdot {\text{B}}_{\text{i}}$

Then, the sum of the each adder can be calculated as follows

${\text{Sum(S}}_{\text{i}}\text{)}\text{=}{\text{P}}_{\text{i}}\oplus {\text{C}}_{\text{i}}$

Thus, the required equation is ${\text{C}}_{\text{i}\text{+}\text{1}}\text{=}{\text{G}}_{\text{i}}\text{+}{\text{(P}}_{\text{i}}\cdot {\text{C}}_{\text{i}}\text{)}$ (1)

Substitute, “0” for “I” in the equation (1)

The first equation can be calculated as follows

${\text{C}}_{\text{1}}\text{=}{\text{G}}_0\text{+}{\text{(P}}_0\cdot {\text{C}}_0\text{)}$

The first equation with the new notation is ${\text{c}}_{\text{4}}\text{=}{\text{G}}_{\text{3,}\text{0}}\text{+}{\text{(P}}_{\text{3,}\text{0}}\cdot {\text{c}}_{\text{0}}\text{)}$.

Thus, the first equation with the new notation for 64 bit is ${\text{c}}_{16}\text{=}{\text{G}}_{\text{15,}\text{0}}\text{+}{\text{(P}}_{\text{15,}\text{0}}\cdot {\text{c}}_{\text{0}}\text{)}$.

The second equation can be calculated as follows

${\text{C}}_2\text{=}{\text{G}}_1\text{+}{\text{(P}}_1\cdot {\text{C}}_1\text{)}$ (2)

Substitute, “${\text{G}}_0\text{+}{\text{(P}}_0\cdot {\text{C}}_0\text{)}$” for “C₁” in the equation (2)

${\text{C}}_2\text{=}{\text{G}}_1\text{+}{\text{P}}_1\cdot {\text{G}}_0\text{+}{\text{P}}_1\cdot {\text{P}}_0\cdot {\text{C}}_0$

The second equation with new notation is ${\text{c}}_8\text{=}{\text{G}}_{\text{7,}\text{4}}\text{+}{\text{(P}}_{\text{7,}\text{4}}\cdot {\text{G}}_{\text{3,}\text{0}})+{\text{(P}}_{\text{7,}\text{4}}\cdot {\text{G}}_{\text{3,}\text{0}})+{\text{(P}}_{\text{7,}\text{4}}\cdot {\text{P}}_{\text{3,}\text{0}}\cdot {\text{c}}_{\text{0}}\text{)}$.

Thus, the second equation with new notation for 64 bit is ${\text{c}}_{32}\text{=}{\text{G}}_{\text{31,}16}\text{+}{\text{(P}}_{\text{31,}16}\cdot {\text{G}}_{\text{15,}\text{0}})+{\text{(P}}_{\text{31,}16}\cdot {\text{P}}_{\text{15,}\text{0}}\cdot {\text{c}}_{\text{0}}\text{)}$.

The third equation can be calculated as follows

${\text{C}}_3\text{=}{\text{G}}_2\text{+}{\text{(P}}_2\cdot {\text{C}}_2\text{)}$ (3)

Substitute, “${\text{G}}_2\text{+}{\text{(P}}_2\cdot {\text{C}}_2\text{)}$” for “C₂” in the equation (3)

${\text{C}}_3\text{=}{\text{G}}_{\text{2}}{\text{P}}_{\text{2}}\cdot {\text{G}}_1\text{+}{\text{P}}_2\cdot {\text{P}}_1\cdot {\text{G}}_0\text{+}{\text{P}}_2\cdot {\text{P}}_1\cdot {\text{P}}_0\cdot {\text{C}}_0$

The third equation with new notation is ${\text{c}}_{12}\text{=}{\text{G}}_{\text{11,}8}\text{+}{\text{(P}}_{\text{11,}8}\cdot {\text{G}}_{\text{7,}4})+{\text{(P}}_{\text{11,}8}\cdot {\text{P}}_{\text{7,}\text{4}}\cdot {\text{G}}_{\text{3,}\text{0}})+{\text{(P}}_{\text{11,}8}\cdot {\text{P}}_{\text{7,}\text{4}}\cdot {\text{P}}_{\text{3,}\text{0}}\cdot {\text{c}}_{\text{0}}\text{)}$.

Thus, the third equation with new notation for 64 bit is ${\text{c}}_{48}\text{=}{\text{G}}_{\text{47,}32}\text{+}{\text{(P}}_{\text{47,}32}\cdot {\text{G}}_{\text{31,}16})+{\text{(P}}_{\text{47,}32}\cdot {\text{P}}_{\text{31,}16}\cdot {\text{G}}_{\text{15,}\text{0}})+{\text{(P}}_{\text{47,}32}\cdot {\text{P}}_{\text{31,}16}\cdot {\text{P}}_{\text{15,}\text{0}}\cdot {\text{c}}_{\text{0}}\text{)}$.

The fourth equation can be calculated as follows

${\text{C}}_4\text{=}{\text{G}}_3\text{+}{\text{(P}}_3\cdot {\text{C}}_3\text{)}$ (4)

Substitute, “${\text{G}}_3\text{+}{\text{(P}}_3\cdot {\text{C}}_3\text{)}$” for “C₃” in the equation (4)

${\text{C}}_4\text{=}{\text{G}}_{\text{3}}{\text{P}}_{\text{3}}\cdot {\text{G}}_2{\text{P}}_3\cdot {\text{P}}_2\cdot {\text{G}}_1\text{+}{\text{P}}_3\cdot {\text{P}}_2\cdot {\text{P}}_1\cdot {\text{G}}_0\text{+}{\text{P}}_3\cdot {\text{P}}_2\cdot {\text{P}}_1\cdot {\text{P}}_0\cdot {\text{C}}_0$

The fourth equation with new notation is ${\text{c}}_{16}\text{=}{\text{G}}_{\text{15,}12}\text{+}{\text{(P}}_{\text{15,}12}\cdot {\text{G}}_{\text{11,}8})+{\text{(P}}_{\text{15,}12}\cdot {\text{P}}_{\text{11,}8}\cdot {\text{G}}_{\text{7,}4})+{\text{(P}}_{\text{15,}12}\cdot {\text{P}}_{\text{11,}8}\cdot {\text{P}}_{\text{7,}\text{4}}\cdot {\text{G}}_{\text{3,}0})+{\text{(P}}_{\text{15,}12}\cdot {\text{P}}_{\text{11,}8}\cdot {\text{P}}_{\text{7,}\text{4}}\cdot {\text{P}}_{\text{3,}\text{0}}\cdot {\text{c}}_{\text{0}}\text{)}$

Thus, the fourth equation with new notation for 64 bit is ${\text{c}}_{64}\text{=}{\text{G}}_{63,48}\text{+}{\text{(P}}_{63,48}\cdot {\text{G}}_{47,32})+{\text{(P}}_{63,48}\cdot {\text{P}}_{47,32}\cdot {\text{G}}_{31,16})+{\text{(P}}_{63,48}\cdot {\text{P}}_{47,32}\cdot {\text{P}}_{\text{31,}\text{16}}\cdot {\text{G}}_{15,0})+{\text{(P}}_{63,48}\cdot {\text{P}}_{47,32}\cdot {\text{P}}_{\text{31,}\text{16}}\cdot {\text{P}}_{\text{15,}\text{0}}\cdot {\text{c}}_{\text{0}}\text{)}$