2
\$\begingroup\$

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.
Carry-Lookahead Model

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: propagation delay enter image description here

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: enter image description here

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?

\$\endgroup\$
0
+50
\$\begingroup\$

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

t ripple description

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\$.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Thank you so much for the answer, I will read it in two days or so because I'm very busy right now! \$\endgroup\$ – Tortellini Teusday Jun 22 at 2:52
0
\$\begingroup\$

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. Reducing the complexity of the circuit is done to save power and improve efficiency. Ripple carry adder is less complex, that is lesser gates are required when compared to a Carry Look ahead adder. A Carry Look ahead Adder has less propagation delay. Propagation delay does not matter for the last block as the values don't have to be propagated to another block. So ripple carry adder is used instead. As propagation delay is important for the other blocks, Carry Look Ahead adders are used for the other blocks.

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.

Let's look at how the expression for the total delay of the carry look ahead adder is derived:

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} \$

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Thank you so much for the answer, I will read it in two days or so because I'm very busy right now! \$\endgroup\$ – Tortellini Teusday Jun 22 at 2:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.