Hello. I am unsure if this sub-forum is the right place for this question, but I will dare to post it here.

A few days ago I received an assignment which is about the creation of a Sklansky adder in VHDL. However, before I move to the coding part, I have

trouble understanding the exact mechanisms of the algorithm. Below you can see 2 pictures I have found which show the tree of a 16-bit Sklansky

adder and the circuits that are represented by the black and grey boxes. The triangles are just buffers.


Assuming we add the 16-bit A and B, I know that I have to find the generate and propagate values for each pair of bits A(i) and B(i) which are produced

from the following equations

and

I also know that at some point I will have to find carry values with the equation:

but I can't find a detailed explanation about how all that ties together. I don't know which are the steps that take place after I get to the final

stage in the picture, which is depicted by the bottom box (the one with the numbering 0:0, ... 15:0), and the professor who assign this has been

less than helpful so far with cryptic explanations and confusing clarifications. I have no idea what happens after I am through with the black/grey

components and the buffers. Since the signal that reaches the final stage are exits from the grey components, I assume these will be G (generate) values. How do I go from there to the output of the circuit? Is a full adder used at that point. Where do I use the carry values that the image shows? If someone can help me understand the basics and the flow of the algorithm, I will be grateful, even if it's only a link that offers the explanation I seek. Thank you

 

Have you Googled "Sklansky adder"?

This is just one example of what are known as "tree adders", so it would probably be best to come up to speed on the basic concepts associated with tree adders in general.

 

One thing which is confusing about the diagram is that A and B are completely missing. They must be part of a different diagram, since this one is only concerned with generate and propagate by groups.

 

Have you Googled "Sklansky adder"?

This is just one example of what are known as "tree adders", so it would probably be best to come up to speed on the basic concepts associated with tree adders in general.

Yes, I have, but unlike other adders like Brent-Kung and Kogge-Stone, I have not found much about Sklansky. The name is referenced in several papers, but that's where it usually ends. Only a handful of images for the Sklansky, the majority of them about the tree algorithm, but not even a basic example about how the result (output) of the addition is created.

Now, I have created the code for the components I need, but I haven't found much about the process after a point. After calculating the G, P values that enter the first row of components using the equations I posted, I calculate the products of the black/grey components; G, P for the black boxes and just G for the grey boxes, and I reach to the bottom of the tree, which is where I am stuck. Even in the image I posted it shows there are carry values (Cx:y) I can calculate, but these are not used even once in the black/grey components that are the most significant part of the tree. I don't know what to do with them or how they are used. Even a 4-bit example would be great help in helping me understand how it works towards generating the final output.

 

The bits along the top row are the values of G for each position of the adder. The right most vertical path shows that C(0:0) = G(0) because there is just a buffer. What this tree is doing is computing generate and propagate groups in such a way as to minimize the total delay from a fixed amount which is a function of the number of stages to a smaller amount which depends on the size of the groups in the final level.

 

Let me use an example to show how far I have gone so far in case you spot if I'm going something wrong. Say we want to add the 6 + 3. The last 4 bits of the 16-bit signals will be
a = 6 => 0110
b = 3 => 0011
So we have a(0) = 0 and b(0) = 1 so the generate and propagate values are
G(0) = a(0) AND b(0) = 0 AND 1 = 0
P(0) = a(0) XOR b(0) = 0 XOR 1 = 1

When I asked the professor what value gets through the buffer he told me to check the other "final" buffers in each vertical line. Since the final component (before the buffer) is a grey box which gives a G, I answered that it would also be the G(0) that gets through the buffer, and he didn't object.
For the second less significant bit we have
a(1) = 1 and b(1) = 1 so
G(1) = a(1) AND b(1) = 1 AND 1 = 1
P(1) = a(1) XOR b(1) = 1 XOR 1 = 0

and the inputs to the grey box are G(1), P(1) and G(0) and the output of the grey box is
G(1) OR (P(1) AND G(0)) = (1 OR (0 AND 1)) = 1

SO for the first 2 bits that reach the bottom are
G0:0 = 0 and G1:0 = 1
which would make the result xx10

But this can't be the result of the addition because the result has to be 9 = 0000000000001001
which means there are more calculation involved, or that mine are wrong so far.
The prof gave us a couple more equations,

S(i) = P(i) XOR G(i - 1:0)
Cout = G(N:0) = G(N) + P(N)G(N - 1:0)

but he just won't say where they are used. I considered using them at the last stage of the tree (after the signal passes through the last buffer for each "column"), but don't we have just G values at this point since the last component was a grey cell? I'm just lost at this point. If someone can show me how to calculate the output value for the first 2-3 bits in the example I gave, I'm sure I can get the rest. Thank you for your patience.

 

I have a follow question about the drawings posted. I do not see where the carry in is used in the various stages. Can someone advise on this? How does this design handle a carry in of '1'?

 

Heads up this is an old thread.

But i dont know about you but i hate drawings that are stretched so far that they are kind of ridiculous to try to read so here is a quick redraw of the Black and Gray cells that makes a visual comparison a lot easier and a lot more pleasant...