Carry Look Ahead adder propagation delay calculation

Question

I'm studying Digital Design and Computer Architecture book, I'm stuck in the section of the carry-lookahead adder because there's something that I don't fully understand about the propagation delay of an N-bit carry-lookahead adder.

The book specifies the propagation delay through the 32 bit adder as firstly to calculate the generate or propagate signals G0 and P0, respectively, and then to calculate the generate and propagate signals of each block, and this is done concurrently in all blocks, and then the critical path goes through the and/or gates which has the carry-in as an input (through every block), so that the critical path delay will contain M * t_{AND_OR}, where M is the number of stages. this is (somewhat) understood and seems reasonable to me. The thing is that the book specifies the delay as:

What I don't understand here is that this equation implies that the number of stages which suffer from the AND/OR delay is \$(\frac{N}{k} - 1)\$, which is one less than the actual number of stages. Furthermore, it says that the critical path has \$k\$ full-adders. This is indeed what said in this paragraph:

Unfortunately, the book does not explain this further. My question is that why is the last stage is treated like this? Why isn't it treated like the previous stages? In my opinion or understanding, I don't see why Cout is calculated through the lookahead logic so that the number of stages would be \$ \frac{N}{k} \$ (increase by one) and the term \$ k * t_{FA} \$ would vanish away? Especially because the last block is considered a "4-bit CLA block", then why wouldn't I use the generate carry and propagate carry signals in order to calculate the Cout?

Answer 1

Why is the last stage treated like this? Why isn't it treated like the previous stages?

The last Carry Look Ahead Adder Block is a ripple carry adder to reduce the complexity of the circuit to save power and improve efficiency. A Ripple carry adder is less complex than a Carry Look Ahead Adder. A Carry Look ahead Adder does not need the output of previous stage to compute the current output. So the Carry Look ahead adder is used for all stages excepting the last one so that the addition operation can be done quickly. Ripple Carry Adder is used as the last block because the values don't have to be propagated to another block.

To maintain regularity in the block diagram the term '4-bit CLA block' is used. This is because the block is 4 bits wide and a block of the CLA. The block itself does not use Carry Look Ahead technique. It uses ripple carry technique.

Trade-offs have to be done between speed and complexity, in order to achieve the highest performance with the highest efficiency for the given budget.

What I don't understand here is that this equation implies that the number of stages which suffer from the AND/OR delay is \${N\over{k}}-1\$, which is 1 less than the actual number of stages

The total number of CLA blocks is \$({N\over{k}})\$ as the Carry Look ahead adder is \$N\$ bits wide and each block of the Carry Look Ahead adder is \$k\$ bits wide. Out of this \$({N\over{k}} - 1)\$ blocks use carry look ahead technique and 1 block uses ripple carry technique.

Number of carry look ahead adder blocks \$=\$ \$({N\over{k}} - 1)\$.
Number of ripple carry adder blocks \$=\$ \$1\$

The total delay from \$C_{in}\$ to \$C_{out}\$ of the Carry Look Ahead adder blocks \$=\ t_{AND\_OR} \$ (as this due to the \$AND/OR\$ logic.)

The delay of a ripple carry adder block\$ =\ k.t_{FA} \$.

The delay of the individual generate/propagate gates that generate the \$i^{th}\$ propagate and generate signals, \$P_i\$ and \$G_i\$, respectively \$=\ t_{pg} \$.

The total delay of the \$k\$-bit blocks (excluding the last \$k\$-bit ripple carry adder) to generate the propagate and generate signals \$P_{i:j}\$ and \$G_{i:j}\$, respectively \$=\$ \$ t_{pg\_block}\$. (where \$j - i = k - 1\$)

Thus,

\$ Total\ delay\ of\ CLA = (delay\ of\ the\ generate/propagate\ gates) + (total\ delay\ of\ the\ k-bit\ blocks)\ + \ (No.\ of\ carry\ look\ ahead\ adder\ blocks\ \times total\ delay\ of\ the\ carry\ look\ ahead\ blocks\ from \ C_{in}\ to\ C_{out})\ + \ (No. \ of\ ripple\ carry\ adder\ blocks\ \times delay\ of\ a\ ripple\ carry\ adder)\$

Substituting the terms we get,

\$ t_{CLA} = t_{pg} + t_{pg\_block} + ({N\over{k}} - 1).t_{AND\_OR} + k.t_{FA} \$

Answer 2

The delay calculated doesn't refer to the time taken to calculate the \$C_{out}\$ from the last stage. Instead it refers to the time taken for the full addition operation.

Time of Ripple Adder

To get an idea of what the symbol \$t_{x}\$ means, let's look at ripple adder first. Here \$t_{ripple}\$ refers to the time delay of the full ripple adder; i.e. the time taken to generate all bits \$S_i\$ and \$C_{out}\$. In the ripple counter, the total time is dictated by the time taken to calculate \$C_{out}\$, since \$S_{31}\$ is calculated just before \$C_{out}\$.

Time of CLA

However, in the case of carry look-ahead adder, \$C_{out}\$ gets calculated before \$S_{31}\$. Time to calculate \$C_{out}, t_{cout} = t_{pg} + t_{pg block} + (N/k)t_{AND-OR}\$ as expected. However \$S_{31}\$ is waiting for the ripple triggered by \$C_{27}\$. That rippling takes \$k\cdot t_{fa}\$. That along with time taken for generation of \$C_{27}\$ determines the delay of the full adder. \$C_{27}\$ is what introduces the number \$N/k - 1\$.