Talk:Kogge–Stone adder

	Electronics portal This article is part of WikiProject Electronics, an attempt to provide a standard approach to writing articles about electronics on Wikipedia. If you would like to participate, you can choose to edit the article attached to this page, or visit the project page, where you can join the project and see a list of open tasks. Leave messages at the project talk pageElectronicsWikipedia:WikiProject ElectronicsTemplate:WikiProject Electronicselectronic articles
???	This article has not yet received a rating on the project's importance scale.

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)[reply]

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)[reply]

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

Han-Carlson

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

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]