Talk:Kogge–Stone adder

Wrong picture ?

when I tried to implement a Kogge-Stone adder following the structure shown by this figure. I got totally wrong answers.

Assuming sparsity is 4, like the figure. Obviously, during the suming part, we need to use 4-bits Ripple-Carry Adder(RCA) to do the addition. RCA[0]=a[3:0]+b[3:0]+C0, RCA[1]=a[7:4]+b[7:4]+C1, ... . Those carries that we need are the carry from bit3 to bit4 (C[3]), the carry from bit7 to bit8 (C[7]), ... . However, according the figure, we can only get the final carry C[0], C[4], C[8] and C[12], definetely they are not what we need.

I used VHDL to implement it with C[3], C[7], C[11], C[15]. Seems it works correctly. — Preceding unsigned comment added by Herenvarno (talk • contribs) 20:30, 21 March 2015 (UTC)

Unclear!

Some Boolean equations or schematics made of normal gates would help a lot. The page in its current form just has a bunch of circles and squares of different colors, and I haven't yet figured out what they do. 200.125.115.82 (talk) 21:51, 26 June 2009 (UTC)

Yes this is VERY unclear and I agree this page needs improvement 112.119.94.203 (talk) 02:23, 10 July 2011 (UTC)

Han-Carlson

Han-Carlson needed to compare wide usage in industry. `a5b (talk) 02:22, 11 February 2010 (UTC)

Misleading in the illustration

"S[i] = P[i] xor C[i-1]" is misleading to the readers, as they may think here P[i] comes from the previous step according to the formulas written before, but actually it's from the first step (A[i] xor B[i]). —Preceding unsigned comment added by 88.64.32.96 (talk) 22:40, 27 February 2011 (UTC)

I somewhat agree that it looks confusing, but notice how the equation for S[i] is underneath the red box. The creator of this diagram meant for the P[i] to be the propagate out of the red box, which as you note is equal to A[i] xor B[i]. We can simply use the first stage P[i] for the sum since it has already been calculated.Mll1013 (talk) 00:33, 10 August 2016 (UTC)

Carry-In

Is there a way to give a carry-in to a kogge stone adder? --130.75.117.49 (talk) 13:46, 25 May 2011 (UTC)

yes there is. just wire the carry in to a XOR with the first propagate calculation (the XOR) like a normal adder.

112.119.94.203 (talk) 02:22, 10 July 2011 (UTC)

I think that might be wrong, because if the first bit would propagate and the carry-in is on, then it should generate a carry for that bit but does not. For the first bit, instead of the normal propagate and carry, have P₀ = 0 and G₀ = A₀B₀ + (A₀ xor B₀)C_in. Ghartshaw (talk) 08:18, 8 August 2011 (UTC)

Actually, I think the carry-in must be included in all stages as an extra yellow ball to the right of the other yellow balls. If you set P₀ = 0, then the carry-in can never be propagated through the addition. That also means the pseudo code is wrong, since it only uses the carry-in for bit 0. In fact, when running the pseudo code in C, more than half the results were wrong, even a few with a carry-in of zero. Try the pseudo code with a=7, b=8 and cin=1, and you will get the result 01110 instead of 10000. Fredrik Carlqvist — Preceding unsigned comment added by 213.136.49.54 (talk) 13:38, 9 December 2011 (UTC)

In my experience, the carry in needs to be included in the first generate bit, i.e.: G0 = A0 and B0 or P0 and Cin. P0 is still correct as A0 xor B0 because P0 denotes whether or not the first, single bit addition would create a carry out given a carry in. Because of this, the graphical and logical descriptions are wrong and need to be corrected as of 19 Nov 2012.

I solved this by using slightly different logic on the very first P/G generation as follows (additional logic in bold):

* P[i] = A[i] xor B[i] xor Cin
* G[i] = (A[i] and B[i]) or (A[i] and Cin) or (B[i] and Cin) 

I'm not sure if this implementation meets the pure intents of Kogge and Stone, but it is one way to solve the ambiguity here. Mll1013 (talk) 00:52, 10 August 2016 (UTC)

403 Forbidden Error on the External Link to "Java applet to create a Kogge–Stone adder"

Just letting the custodians know that the External Link does not seem to be available to the public any more. — Preceding unsigned comment added by 131.151.102.18 (talk) 00:31, 29 October 2013 (UTC)

Expansion

I could easily be in error but the S0,S1 terms I compute as:

 S0 = (1 xor 1) xor 0 = 0 xor 0 =0
 S1 = (0 xor 0) xor ( 1 and 1) = 0 xor 1 =1

whereas the expected sum 10101 has S1,S0 = 0,1.--Billymac00 (talk) 01:49, 21 April 2015 (UTC)

Notice that the sum is listed as S[i] = P[i] xor X[i-1]. This calculates as follows for each of the 5 sum bits:

 S[0] = 1 xor 0 = 1   (P[0] = 1, Cin  = 0)
 S[1] = 0 xor 0 = 0   (P[1] = 0, C[0] = 0)
 S[2] = 1 xor 0 = 1   (P[2] = 1, C[1] = 0)
 S[3] = 0 xor 0 = 0   (P[3] = 0, C[2] = 0)
 S[4] = 0 xor 1 = 1   (P[4] = 0, C[3] = 1)

Keep in mind that the propagates are generated in the first stage (i.e. red boxes). That is why the S[i] equation is under the red box. Also note that P[4] is an implicit zero, since it is from the overflow bit 5 position, so it would have a P/G of 0/0. Mll1013 (talk) 00:49, 10 August 2016 (UTC)

Description of carry-in is incorrect

As noted above on this page, the description of carry-in (in the text) is incorrect. Simply XORing Cin with P0 will not work. Trivial example: Let A = 0 (0b0000), B = 1 (0b0001), and Cin = 1. Listing values at each stage as P/G pairs...

• First stage (red boxes): [0/0] [0/0] [0/0] [1/0]
• Second stage: [0/0] [0/0] [0/0] and green circle [1/0]
• Third stage: [0/0] [0/0] and green circles [0/0] [1/0]
• Result: All Gs are 0 (and so all carries are 0, except Cin), and all Ps are 0 except the last (least significant): LSB of sum = 1 xor Cin = 0?!

I'm still puzzling my way through what will work, although I think the anonymous editor with the small print is on the right track. But even if I do work it out, that's not good enough. My analysis is original research. We need to find some verifiable source that explains how to handle carry-in (preferably less densely than the original paper, which I confess I can't make much of at all).

Anyway, that's the text. The diagram does not address this at all (it flatly states Cin = 0 and only implicitly suggests the incorrect action), so it may or may not need fixing. -- Perey (talk) 09:34, 5 July 2015 (UTC)

Yes, I discovered this as well and had to think through it. In my design, I solved this by using slightly different logic on the very first P/G generation as follows (additional logic in bold):

 * P[i] = A[i] xor B[i] xor Cin
 * G[i] = (A[i] and B[i]) or (A[i] and Cin) or (B[i] and Cin) 

I'm not sure if this implementation meets the pure intents of Kogge and Stone, but it is one way to solve the ambiguity here.:Mll1013 (talk) 00:40, 10 August 2016 (UTC)