Kogge–Stone adder#SKA
{{Short description|Arithmetic logic circuit}}
{{Sidebar arithmetic logic circuits|expand=Components|expand-components=Adder}}
Image:4 bit Kogge Stone Adder Example new.png
In computing, the Kogge–Stone adder (KSA or KS) is a parallel prefix form of carry-lookahead adder. Other parallel prefix adders (PPA) include the Sklansky adder (SA),{{cite journal |first=J. |last=Sklansky |title=Conditional-sum addition logic |journal=IRE Transactions on Electronic Computers |volume=EC-9 |issue=2 |pages=226–231 |date=1960 |doi=10.1109/TEC.1960.5219822 |url=http://bwrcs.eecs.berkeley.edu/Classes/icdesign/ee241_s10/Readings/Sklansky60.pdf}} Brent–Kung adder (BKA), the Han–Carlson adder (HCA), the fastest known variation, the Lynch–Swartzlander spanning tree adder (STA), Knowles adder (KNA){{cite web |first=Simon |last=Knowles |title=A Family of Adders |date= |publisher=Element 14 |location=Aztec Centre, Bristol, UK |url=http://acsel-lab.com/Projects/fast_adder/references/papers/Knowles-family_of_add.pdf }} and Beaumont-Smith adder (BSA) (like Sklansky adder (SA), radix-4).{{cite conference |last1=Beaumont-Smith |first1=A. |last2=Lim |first2=C.C. |title=Parallel prefix adder design |doi=10.1109/ARITH.2001.930122 |book-title=Proceedings 15th IEEE Symposium on Computer Arithmetic. ARITH-15 2001 |publisher=IEEE |date=June 2001 |isbn=0-7695-1150-3 |pages=218–225 |url=https://www.researchgate.net/publication/3900704}}
The Kogge–Stone adder takes more area to implement than the Brent–Kung adder, but has a lower fan-out at each stage, which increases performance for typical CMOS process nodes. However, wiring congestion is often a problem for Kogge–Stone adders. The Lynch–Swartzlander design is smaller, has lower fan-out, and does not suffer from wiring congestion; however to be used the process node must support Manchester carry chain implementations. The general problem of optimizing parallel prefix adders is identical to the variable block size, multi level, carry-skip adder optimization problem, a solution of which is found in Thomas Lynch's thesis of 1996.
Design
Like all carry-lookahead adders, the Kogge-Stone adder internally tracks "generate" and "propagate" bits for spans of bits. We start with 1-bit spans, where a single column in the addition generates a carry bit if both inputs are 1 (logical AND), and propagates a carry bit if exactly one input is 1 (logical XOR). Then adjacent spans are merged together to produce generate and propagate bits for wider spans.
Merging continues until generate bits are known for all spans ending at the least significant bit, at which point these may be used as the carry inputs to compute all the sum bits in parallel.
The difference between different carry-lookahead adder designs lies in how the span merging takes place. Most designs use {{math|log2 n}} stages, doubling the width of the merged spans at each stage, but they differ in how spans which are not a power of two in size are divided into subspans. The Kogge–Stone design truncates the less-significant spans, and always uses full-width more-significant spans.
Starting with the 1-bit spans, all adjacent spans are merged to produce 2-bit spans. The least-significant span is treated specially: it is merged with the carry in to the addition, and it only produces a generate bit, as no propagation is possible. The next stage, each 2-bit wide span is merged with the preceding 2-bit span to produce a 4-bit span. This is with the exception of the least significant three spans. The least significant span has already been computed, while the next two are merged with the carry in and the previously computed least significant span respectively, producing generate bits for 3- and 4-bit spans including the carry in.
This process repeats, doubling the span widths at each stage, and with simplified computation of least-significant spans, until all of the desired generate bits are known.
Since each span is merged with at most two other spans in the next stage (one more significant and one less significant), fan-out is minimal. However, there is significant wiring congestion; in the second-last stage of a 64-bit adder, the most significant half of the spans to be merged each require separate generate and propagate signals from spans 16 bits away, necessitating 32 horizontal wires across the adder. The final stage is similar; although only generate bits are needed, 32 of them are required to cross the adder.
Examples
An example of a 4-bit Kogge–Stone adder is shown in the diagram. Each vertical stage produces a "propagate" and a "generate" bit, as shown. The culminating generate bits (the carries) are produced in the last stage (vertically), and these bits are XOR'd with the initial propagate after the input (the red boxes) to produce the sum bits. E.g., the first (least-significant) sum bit is calculated by XORing the propagate in the farthest-right red box (a "1") with the carry-in (a "0"), producing a "1". The second bit is calculated by XORing the propagate in second box from the right (a "0") with C0 (a "0"), producing a "0".
= Binary, radix-2, 4-bit =
4-bit Kogge-Stone adder, Radix-2, without Cin on Borland Turbo Basic 1.1:
{{sxhl|2=basic|1=
'--- Step=0 --------------------------------------------
P00 = A0 XOR B0 '1dt, dt - delay time
G00 = A0 AND B0 '1dt
P01 = A1 XOR B1 '1dt
G01 = A1 AND B1 '1dt
P02 = A2 XOR B2 '1dt
G02 = A2 AND B2 '1dt
P03 = A3 XOR B3 '1dt
G03 = A3 AND B3 '1dt
'--- Step=1, Valency-2, Distance=Radix^(Step-1)=2^0
G10 = G00 '1dt
G11 = G01 OR (P01 AND G00) '3dt Distance=2^0=1
P12 = P02 AND P01 '2dt Distance=2^0=1
G12 = G02 OR (P02 AND G01) '3dt Distance=2^0=1
' 1dt 1dt 1dt
P13 = P03 AND P02 '2dt Distance=2^0=1
G13 = G03 OR (P03 AND G02) '3dt Distance=2^0=1
' 1dt 1dt 1dt
'--- Step=2, Valency-2, Distance=Radix^(Step-1)=2^1=2
G20 = G10 '1dt, C1
G21 = G11 '3dt, C2
G22 = G12 OR (P12 AND G10) '4dt, C3 Distance=2^1=2
' 3dt 2dt 1dt
G23 = G13 OR (P13 AND G11) '5dt, C4 Distance=2^1=2
' 3dt 2dt 3dt
'--- Sum ------------------------------
S0 = P00 '1dt
S1 = P01 XOR G20 '2dt
S2 = P02 XOR G21 '4dt
S3 = P03 XOR G22 '5dt
S4 = G23 '5dt. S4=C4=Cout
}}https://andserkul.narod.ru/R2KS4.bas {{Bare URL inline|date=August 2024}}
= Binary, radix-2, 4-bit, with Cin =
4-bit Kogge-Stone adder, Radix-2, with Cin:
{{sxhl|2=basic|1=
'--- Step Pre -------------------
G0a = A0 AND Cin '1dt
G0b = B0 AND Cin '1dt
G0c = A0 AND B0 '1dt
'--- Step 0 ---------------------
P00 = A0 XOR B0 '1dt
G00 = G0a OR G0b OR G0c '2dt
P01 = A1 XOR B1 '1dt
G01 = A1 AND B1 '1dt
P02 = A2 XOR B2 '1dt
G02 = A2 AND B2 '1dt
P03 = A3 XOR B3 '1dt
G03 = A3 AND B3 '1dt
'--- Step 1 ---------------------
G10 = G00 '2dt
G11 = G01 OR (P01 AND G00) '4dt
P12 = P02 AND P01 '2dt
G12 = G02 OR (P02 AND G01) '3dt
P13 = P03 AND P02 '2dt
G13 = G03 OR (P03 AND G02) '3dt
'--- Step 2 -------------------------
G20 = G10 '2dt, C1
G21 = G11 '4dt, C2
G22 = G12 OR (P12 AND G00) '5dt, C3
G23 = G13 OR (P13 AND G11) '6dt, C4
'--- Sum ------------------------
S0 = P00 XOR Cin '2dt
S1 = P01 XOR G20 '3dt
S2 = P02 XOR G21 '5dt
S3 = P03 XOR G22 '6dt
S4 = G23 '6dt, S4=C4=Cout
}}
= Binary, radix-2, 8-bit =
8-bit Kogge-Stone adder, radix-2, valency-2:
{{sxhl|2=basic|1=
'---Step 0 ---------------------
P00 = A0 XOR B0 '1dt
G00 = A0 AND B0 '1dt
P01 = A1 XOR B1 '1dt
G01 = A1 AND B1 '1dt
P02 = A2 XOR B2 '1dt
G02 = A2 AND B2 '1dt
P03 = A3 XOR B3 '1dt
G03 = A3 AND B3 '1dt
P04 = A4 XOR B4 '1dt
G04 = A4 AND B4 '1dt
P05 = A5 XOR B5 '1dt
G05 = A5 AND B5 '1dt
P06 = A6 XOR B6 '1dt
G06 = A6 AND B6 '1dt
P07 = A7 XOR B7 '1dt
G07 = A7 AND B7 '1dt
'--- Step 1, Distance=2^0=1 --------
G10 = G00 '1dt
G11 = G01 OR (P01 AND G00) '3dt
P12 = P02 AND P01 '2dt
G12 = G02 OR (P02 AND G01) '3dt
P13 = P03 AND P02 '2dt
G13 = G03 OR (P03 AND G02) '3dt
P14 = P04 AND P03 '2dt
G14 = G04 OR (P04 AND G03) '3dt
P15 = P05 AND P04 '2dt
G15 = G05 OR (P05 AND G04) '3dt
P16 = P06 AND P05 '2dt
G16 = G06 OR (P06 AND G05) '3dt
P17 = P07 AND P06 '2dt
G17 = G07 OR (P07 AND G06) '3dt
'--- Step 2, Distance=2^1=2 ----
G20 = G10 '1dt
G21 = G11 '3dt
G22 = G12 OR (P12 AND G10) '4dt
' 3dt 2dt 1dt
G23 = G13 OR (P13 AND G11) '5dt
' 3dt 2dt 3dt
P24 = P14 AND P12 '3dt
G24 = G14 OR (P14 AND G12) '5dt
' 3dt 2dt 3dt
P25 = P15 AND P13 '3dt
G25 = G15 OR (P15 AND G13) '5dt
' 3dt 2dt 3dt
P26 = P16 AND P14 '3dt
G26 = G16 OR (P16 AND G14) '5dt
' 3dt 2dt 3dt
P27 = P17 AND P15 '3dt
G27 = G17 OR (P17 AND G15) '5dt
' 3dt 2dt 3dt
'--- Step 3, Distance=2^2=4 --------
G30 = G20 '1dt, C1
G31 = G21 '3dt, C2
G32 = G22 '4dt, C3
G33 = G23 '5dt, C4
G34 = G24 OR (P24 AND G20) '6dt, C5
' 5dt 3dt 1dt
G35 = G25 OR (P25 AND G21) '6dt, C6
' 5dt 3dt 3dt
G36 = G26 OR (P26 AND G22) '6dt, C7
' 5dt 3dt 4dt
G37 = G27 OR (P27 AND G23) '7dt, C8
' 5dt 3dt 5dt
'---Sum ------------------------
S0 = P00 '1dt
S1 = P01 XOR G30 '2dt
S2 = P02 XOR G31 '4dt
S3 = P03 XOR G32 '5dt
S4 = P04 XOR G33 '6dt
S5 = P05 XOR G34 '7dt
S6 = P06 XOR G35 '7dt
S7 = P07 XOR G36 '7dt
S8 = G37 '7dt, S8=C8=Cout
}}https://andserkul.narod.ru/R2KS8.bas {{Bare URL inline|date=August 2024}}
= Binary, radix-4, 4-bit =
4-bit PPA radix-4 (valency-2,3,4) adder (is 4-bit CLA radix-4 (valency-2,3,4) adder and 4-bit Sklansky radix-4 (valency-2,3,4) adder and 4-bit Kogge-Stone radix-4 (valency-2,3,4) adder and 4-bit Beaumont-Smith radix-4 (valency-2,3,4) adder):
{{sxhl|2=basic|1=
'--- Step 0 ----------
P00 = A0 XOR B0 '1dt
G00 = A0 AND B0 '1dt
P01 = A1 XOR B1 '1dt
G01 = A1 AND B1 '1dt
P02 = A2 XOR B2 '1dt
G02 = A2 AND B2 '1dt
P03 = A3 XOR B3 '1dt
G03 = A3 AND B3 '1dt
'--- Step 1 --------------------------------------------------------
G10 = G00 '1dt, C1, valency-1, distance-0
G11 = G01 OR_
P01 AND G00 '3dt, C2, valency-2, distance-0,1
G12 = G02 OR_
P02 AND G01 OR_
P02 AND P01 AND G00 '3dt, C3, valency-3, distance-0,1,2
G13 = G03 OR_
P03 AND G02 OR_
P03 AND P02 AND G01 OR_
P03 AND P02 AND P01 AND G00 '3dt, C4, valency-4, distance-0,1,2,3
'--- Sum ------------------------------------
S0 = P00 '1dt
S1 = P01 XOR G10 '2dt
S2 = P02 XOR G11 '4dt
S3 = P03 XOR G12 '4dt
S4 = G13 '3dt, S4=C4=Cout
}}https://andserkul.narod.ru/R4KS4F.bas {{Bare URL inline|date=August 2024}}
= Binary, radix-4, 8-bit =
8-bit Kogge-Stone adder, radix-4, valency-2,3,4:
{{sxhl|2=basic|1=
'--- Step 0 -----------
P00 = A0 XOR B0 '1dt
G00 = A0 AND B0 '1dt
P01 = A1 XOR B1 '1dt
G01 = A1 AND B1 '1dt
P02 = A2 XOR B2 '1dt
G02 = A2 AND B2 '1dt
P03 = A3 XOR B3 '1dt
G03 = A3 AND B3 '1dt
P04 = A4 XOR B4 '1dt
G04 = A4 AND B4 '1dt
P05 = A5 XOR B5 '1dt
G05 = A5 AND B5 '1dt
P06 = A6 XOR B6 '1dt
G06 = A6 AND B6 '1dt
P07 = A7 XOR B7 '1dt
G07 = A7 AND B7 '1dt
'--- Step 1 ---------------------------
G10 = G00 '1dt
G11 = G01 OR_
P01 AND G00 '3dt
G12 = G02 OR_
P02 AND G01 OR_
P02 AND P01 AND G00 '3dt
G13 = G03 OR_
P03 AND G02 OR_
P03 AND P02 AND G01 OR_
P03 AND P02 AND P01 AND G00 '3dt
P14 = P04 AND P03 AND P02 AND P01 '2dt
G14 = G04 OR_
P04 AND G03 OR_
P04 AND P03 AND G02 OR_
P04 AND P03 AND P02 AND G01 '3dt
P15 = P05 AND P04 AND P03 AND P02 '2dt
G15 = G05 OR_
P05 AND G04 OR_
P05 AND P04 AND G03 OR_
P05 AND P04 AND P03 AND G02 '3dt
P16 = P06 AND P05 AND P04 AND P03 '2dt
G16 = G06 OR_
P06 AND G05 OR_
P06 AND P05 AND G04 OR_
P06 AND P05 AND P04 AND G03 '3dt
P17 = P07 AND P06 AND P05 AND P04 '2dt
G17 = G07 OR_
P07 AND G06 OR_
P07 AND P06 AND G05 OR_
P07 AND P06 AND P05 AND G04 '3dt
'--- Step 2 -----------------------
G20 = G10 '1dt, C1
G21 = G11 '3dt, C2
G22 = G12 '3dt, C3
G23 = G13 '3dt, C4
G24 = G14 OR (P14 AND G10) '4dt, C5
G25 = G15 OR (P15 AND G11) '4dt, C6
G26 = G16 OR (P16 AND G12) '4dt, C7
G27 = G17 OR (P17 AND G13) '5dt, C8
'--- Sum --------------------------
S0 = P00 '1dt
S1 = P01 XOR G20 '2dt
S2 = P02 XOR G21 '4dt
S3 = P03 XOR G22 '4dt
S4 = P04 XOR G23 '4dt
S5 = P05 XOR G24 '5dt
S6 = P06 XOR G25 '5dt
S7 = P07 XOR G26 '5dt
S8 = G27 '5dt, S8=C8=Cout
}}https://andserkul.narod.ru/R4KS8F.bas {{Bare URL inline|date=August 2024}}
= Binary, radix-8, 8-bit =
8-bit radix-8 PPA valency-2,3,4,5,6,7,8 adder (is 8-bit CLA valency-2,3,4,5,6,7,8 adder and 8-bit Sklansky valency-2,3,4,5,6,7,8 adder and 8-bit Kogge-Stone valency-2,3,4,5,6,7,8 adder):
{{sxhl|2=basic|1=
'--- Step 0 ---------------------------
P00 = A0 XOR B0 '1dt
G00 = A0 AND B0 '1dt
P01 = A1 XOR B1 '1dt
G01 = A1 AND B1 '1dt
P02 = A2 XOR B2 '1dt
G02 = A2 AND B2 '1dt
P03 = A3 XOR B3 '1dt
G03 = A3 AND B3 '1dt
P04 = A4 XOR B4 '1dt
G04 = A4 AND B4 '1dt
P05 = A5 XOR B5 '1dt
G05 = A5 AND B5 '1dt
P06 = A6 XOR B6 '1dt
G06 = A6 AND B6 '1dt
P07 = A7 XOR B7 '1dt
G07 = A7 AND B7 '1dt
'--- Step 1 ---------------------------
G10 = G00 '1dt
G11 = G01 OR P01 AND G00 '3dt, C2, valency-2, distance-1
G12 = G02 OR_ '3dt, C3, valency-3, distance-1,2
P02 AND G01 OR_
P02 AND P01 AND G00 '3-in AND
G13 = G03 OR_ '3dt, C4, valency-4, distance-1,2,3
P03 AND G02 OR_
P03 AND P02 AND G01 OR_
P03 AND P02 AND P01 AND G00 '4-in AND
G14 = G04 OR_ '3dt, C5, valency-5, distance-1,2,3,4
P04 AND G03 OR_
P04 AND P03 AND G02 OR_
P04 AND P03 AND P02 AND G01 OR_
P04 AND P03 AND P02 AND P01 AND G00 '5-in AND
G15 = G05 OR_ '3dt, C6, valency-6, distance-1,2,3,4,5
P05 AND G04 OR_
P05 AND P04 AND G03 OR_
P05 AND P04 AND P03 AND G02 OR_
P05 AND P04 AND P03 AND P02 AND G01 OR_
P05 AND P04 AND P03 AND P02 AND P01 AND G00 '6-in AND
G16 = G06 OR_ '3dt, C7, valency-7, distance-1,2,3,4,5,6
P06 AND G05 OR_
P06 AND P05 AND G04 OR_
P06 AND P05 AND P04 AND G03 OR_
P06 AND P05 AND P04 AND P03 AND G02 OR_
P06 AND P05 AND P04 AND P03 AND P02 AND G01 OR_
P06 AND P05 AND P04 AND P03 AND P02 AND P01 AND G00 '7-in AND
G17 = G07 OR_ '3dt, C8, valency-8, distance-1,2,3,4,5,6,7
P07 AND G06 OR_
P07 AND P06 AND G05 OR_
P07 AND P06 AND P05 AND G04 OR_
P07 AND P06 AND P05 AND P04 AND G03 OR_
P07 AND P06 AND P05 AND P04 AND P03 AND G02 OR_
P07 AND P06 AND P05 AND P04 AND P03 AND P02 AND G01 OR_
P07 AND P06 AND P05 AND P04 AND P03 AND P02 AND P01 AND G00 '8-in AND
'--- Sum --------------
S0 = P00 '1dt
S1 = P01 XOR G10 '2dt
S2 = P02 XOR G11 '4dt
S3 = P03 XOR G12 '4dt
S4 = P04 XOR G13 '4dt
S5 = P05 XOR G14 '4dt
S6 = P06 XOR G15 '4dt
S7 = P07 XOR G16 '4dt
S8 = G17 '3dt, S8=C8=Cout
}}https://andserkul.narod.ru/R8KS8F.bas {{Bare URL inline|date=August 2024}}
= Binary, radix-16 16-bit, radix-32 32-bit, radix-64 64-bit,... =
{{sxhl|2=basic|1=
'--- Step 0 -----------------------------------------------------------
FOR I=0 TO N 'N=15 (31 for radix-32 32-bit, 63 for radix-64 64-bit,...)
P0[I] = A[I] XOR B[I] '1dt
G0[I] = A[I] AND B[I] '1dt
NEXT I
'--- Step 1 ----------------------------------------------------------
FOR I=0 TO N 'G1[I]
G1[I] = 0
FOR J=0 TO I 'String J
OUT1[J] = 1
FOR K=I TO I-J STEP -1 'Number of up to 16-in AND
IF K<>I-J THEN
OUT1[J] = OUT1[J] AND P0[K] 'AND'ing, 2dt
ELSE
OUT1[J] = OUT1[J] AND G0[K] 'AND'ing, 2dt
END IF
NEXT K
IF J=0 THEN G1[I] = OUT1[J] ELSE G1[I] = G1[I] OR OUT1[J] 'OR'ing, 3dt
'G1[15]=S[16]=C[16]=Cout, 3dt
NEXT J
NEXT I
'--- Sum -----------------------------
FOR I=0 TO N 'Shift Left 1 bit
G1[N+1-I] = G1[N-I]
NEXT I
G1[0] = 0
P0[N+1] = 0
FOR I=0 TO N+1
S[I] = P0[I] XOR G1[I] 'XOR'ing, 4dt (Kogge-Stone, binary, radix-2, 64-bit - 14dt)
NEXT I
}}https://andserkul.narod.ru/R16KSFM.bas {{Bare URL inline|date=August 2024}}
= Velocity of Kogge-Stone adders with parallel operators G =
{{pre|1=
Numbers of bits n=2 n=4 n=8 n=16 n=32 n=64
Radix-2
Numbers of steps s=1 s=2 s=3 s=4 s=5 s=6
Adding time 4dt 6dt 8dt 10dt 12dt 14dt
Radix-4
Numbers of steps s=1 s=2 s=2 s=3 s=3
Adding time 4dt 6dt 6dt 8dt 8dt
Radix-8
Numbers of steps s=1 s=2 s=2 s=2
Adding time 4dt 6dt 6dt 6dt
Radix-16
Numbers of steps s=1 s=2 s=2
Adding time 4dt 6dt 6dt
Radix-32
Numbers of steps s=1 s=2
Adding time 4dt 6dt
Radix-64
Numbers of steps s=1
Adding time 4dt
}}
= Velocity of Kogge-Stone adders on inverting CMOS gates =
{{pre|1=
Numbers of bits n=2 n=4 n=8 n=16 n=32 n=64
Radix-2
Numbers of steps s=1 s=2 s=3 s=4 s=5 s=6
Adding time 5dt 6dt 7dt 8dt 9dt 10dt
Radix-4
Numbers of steps s=1 s=2 s=2 s=3 s=3
Adding time 5dt 6dt 6dt 7dt 7dt
Radix-8
Numbers of steps s=1 s=2 s=2 s=2
Adding time 5dt 6dt 6dt 6dt
Radix-16
Numbers of steps s=1 s=2 s=2
Adding time 5dt 6dt 6dt
Radix-32
Numbers of steps s=1 s=2
Adding time 5dt 6dt
Radix-64
Numbers of steps s=1
Adding time 5dt
}}
= Velocity of Kogge-Stone adders on inverting CMOS gates with paraphase input bits =
{{pre|1=
Numbers of bits n=2 n=4 n=8 n=16 n=32 n=64
Radix-2
Numbers of steps s=1 s=2 s=3 s=4 s=5 s=6
Adding time 4dt 5dt 6dt 7dt 8dt 9dt
Radix-4
Numbers of steps s=1 s=2 s=2 s=3 s=3
Adding time 4dt 5dt 5dt 6dt 6dt
Radix-8
Numbers of steps s=1 s=2 s=2 s=2
Adding time 4dt 5dt 5dt 5dt
Radix-16
Numbers of steps s=1 s=2 s=2
Adding time 4dt 5dt 5dt
Radix-32
Numbers of steps s=1 s=2
Adding time 4dt 5dt
Radix-64
Numbers of steps s=1
Adding time 4dt
}}
= Velocity of Kogge-Stone adders on noninverting Key gates =
{{pre|1=
Numbers of bits n=2 n=4 n=8 n=16 n=32 n=64
Radix-2
Numbers of steps s=1 s=2 s=3 s=4 s=5 s=6
Adding time 3dt 4dt 5dt 6dt 7dt 8dt
Radix-4
Numbers of steps s=1 s=2 s=2 s=3 s=3
Adding time 3dt 4dt 4dt 5dt 5dt
Radix-8
Numbers of steps s=1 s=2 s=2 s=2
Adding time 3dt 4dt 4dt 4dt
Radix-16
Numbers of steps s=1 s=2 s=2
Adding time 3dt 4dt 4dt
Radix-32
Numbers of steps s=1 s=2
Adding time 3dt 4dt
Radix-64
Numbers of steps s=1
Adding time 3dt
}}
The Kogge-Stone adder concept was developed by Peter M. Kogge and Harold S. Stone, who published it in a seminal 1973 paper titled A Parallel Algorithm for the Efficient Solution of a General Class of Recurrence Equations.
{{anchor|SKA}}Enhancements
Enhancements to the original implementation include increasing the radix and sparsity of the adder. The radix of the adder refers to how many results from the previous level of computation are used to generate the next one. The original implementation uses radix-2, although it's possible to create radix-4 and higher. Doing so increases the power and delay of each stage, but reduces the number of required stages. In the so-called sparse Kogge–Stone adder (SKA) the sparsity of the adder refers to how many carry bits are generated by the carry-tree. Generating every carry bit is called sparsity-1, whereas generating every other is sparsity-2 and every fourth is sparsity-4. The resulting carries are then used as the carry-in inputs for much shorter ripple carry adders or some other adder design, which generates the final sum bits. Increasing sparsity reduces the total needed computation and can reduce the amount of routing congestion.
Image:Kogge-stone-sparsity-4.png
Above is an example of a Kogge–Stone adder with sparsity-4. Elements eliminated by sparsity shown marked with transparency. As shown, power and area of the carry generation is improved significantly, and routing congestion is substantially reduced. Each generated carry feeds a multiplexer for a carry select adder or the carry-in of a ripple carry adder.
16-bit Kogge-Stone adder valency-2 without Cin:
P00 = A0 XOR B0 '1dt, S0, dt - type delay time
G00 = A0 AND B0 '1dt, C0
P10 = A1 XOR B1 '1dt
G10 = A1 AND B1 '1dt
P20 = A2 XOR B2 '1dt
G20 = A2 AND B2 '1dt
P30 = A3 XOR B3 '1dt
G30 = A3 AND B3 '1dt
P40 = A4 XOR B4 '1dt
G40 = A4 AND B4 '1dt
P50 = A5 XOR B5 '1dt
G50 = A5 AND B5 '1dt
P60 = A6 XOR B6 '1dt
G60 = A6 AND B6 '1dt
P70 = A7 XOR B7 '1dt
G70 = A7 AND B7 '1dt
P80 = A8 XOR B8 '1dt
G80 = A8 AND B8 '1dt
P90 = A9 XOR B9 '1dt
G90 = A9 AND B9 '1dt
P100 = A10 XOR B10 '1dt
G100 = A10 AND B10 '1dt
P110 = A11 XOR B11 '1dt
G110 = A11 AND B11 '1dt
P120 = A12 XOR B12 '1dt
G120 = A12 AND B12 '1dt
P130 = A13 XOR B13 '1dt
G130 = A13 AND B13 '1dt
P140 = A14 XOR B14 '1dt
G140 = A14 AND B14 '1dt
P150 = A15 XOR B15 '1dt
G150 = A15 AND B15 '1dt
G11 = G10 OR P10 AND G00 '3dt, C1
P21 = P20 AND P10 '2dt
G21 = G20 OR P20 AND G10 '3dt
P31 = P30 AND P20 '2dt
G31 = G30 OR P30 AND G20 '3dt
P41 = P40 AND P30 '2dt
G41 = G40 OR P40 AND G30 '3dt
P51 = P50 AND P40 '2dt
G51 = G50 OR P50 AND G40 '3dt
P61 = P60 AND P50 '2dt
G61 = G60 OR P60 AND G50 '3dt
P71 = P70 AND P60 '2dt
G71 = G70 OR P70 AND G60 '3dt
P81 = P80 AND P70 '2dt
G81 = G80 OR P80 AND G70 '3dt
P91 = P90 AND P80 '2dt
G91 = G90 OR P90 AND G80 '3dt
P101 = P100 AND P90 '2dt
G101 = G100 OR P100 AND G90 '3dt
P111 = P110 AND P100 '2dt
G111 = G110 OR P110 AND G100 '3dt
P121 = P120 AND P110 '2dt
G121 = G120 OR P120 AND G110 '3dt
P131 = P130 AND P120 '2dt
G131 = G130 OR P130 AND G120 '3dt
P141 = P140 AND P130 '2dt
G141 = G140 OR P140 AND G130 '3dt
P151 = P150 AND P140 '2dt
G151 = G150 OR P150 AND G140 '3dt
G22 = G21 OR P21 AND G00 '4dt, C2
G32 = G31 OR P31 AND G11 '5dt, C3
P42 = P41 AND P21 '3dt
G42 = G41 OR P41 AND G21 '5dt
P52 = P51 AND P31 '3dt
G52 = G51 OR P51 AND G31 '5dt
P62 = P61 AND P41 '3dt
G62 = G61 OR P61 AND G41 '5dt
P72 = P71 AND P51 '3dt
G72 = G71 OR P71 AND G51 '5dt
P82 = P81 AND P61 '3dt
G82 = G81 OR P81 AND G61 '5dt
P92 = P91 AND P71 '3dt
G92 = G91 OR P91 AND G71 '5dt
P102 = P101 AND P81 '3dt
G102 = G101 OR P101 AND G81 '5dt
P112 = P111 AND P91 '3dt
G112 = G111 OR P111 AND G91 '5dt
P122 = P121 AND P101 '3dt
G122 = G121 OR P121 AND G101 '5dt
P132 = P131 AND P111 '3dt
G132 = G131 OR P131 AND G111 '5dt
P142 = P141 AND P121 '3dt
G142 = G141 OR P141 AND G121 '5dt
P152 = P151 AND P131 '3dt
G152 = G151 OR P151 AND G131 '5dt
G43 = G42 OR P42 AND G00 '6dt, C4
G53 = G52 OR P52 AND G11 '6dt, C5
G63 = G62 OR P62 AND G22 '6dt, C6
G73 = G72 OR P72 AND G32 '7dt, C7
P83 = P82 AND P42 '4dt
G83 = G82 OR P82 AND G42 '7dt
P93 = P92 AND P52 '4dt
G93 = G92 OR P92 AND G52 '7dt
P103 = P102 AND P62 '4dt
G103 = G102 OR P102 AND G62 '7dt
P113 = P112 AND P72 '4dt
G113 = G112 OR P112 AND G72 '7dt
P123 = P122 AND P82 '4dt
G123 = G122 OR P122 AND G82 '7dt
P133 = P132 AND P92 '4dt
G133 = G132 OR P132 AND G92 '7dt
P143 = P142 AND P102 '4dt
G143 = G142 OR P142 AND G102 '7dt
P153 = P152 AND P112 '4dt
G153 = G152 OR P152 AND G112 '7dt
G84 = G83 OR P83 AND G00 '8dt, C8
G94 = G93 OR P93 AND G11 '8dt, C9
G104 = G103 OR P103 AND G22 '8dt, C10
G114 = G113 OR P113 AND G32 '8dt, C11
G124 = G123 OR P123 AND G43 '8dt, C12
G134 = G133 OR P133 AND G53 '8dt, C13
G144 = G143 OR P143 AND G63 '8dt, C14
G154 = G153 OR P153 AND G73 '9dt, C15
S0 = P00 '1dt
S1 = P10 XOR G00 '2dt
S2 = P20 XOR G11 '4dt
S3 = P30 XOR G22 '5dt
S4 = P40 XOR G32 '6dt
S5 = P50 XOR G43 '7dt
S6 = P60 XOR G53 '7dt
S7 = P70 XOR G63 '7dt
S8 = P80 XOR G73 '8dt
S9 = P90 XOR G84 '9dt
S10 = P100 XOR G94 '9dt
S11 = P110 XOR G104 '9dt
S12 = P120 XOR G114 '9dt
S13 = P130 XOR G124 '9dt
S14 = P140 XOR G134 '9dt
S15 = P150 XOR G144 '9dt
References
{{reflist|refs=
{{cite journal |author-first1=Thomas Walker |author-last1=Lynch |author-first2=Earl E. |author-last2=Swartzlander, Jr. |title=A spanning tree carry lookahead adder |journal=IEEE Transactions on Computers |volume=41 |pages=931–9 |date=August 1992 |issue=8 |doi=10.1109/12.156535}}
{{cite web |author-last=Lynch |author-first=Thomas Walker |url=http://repositories.lib.utexas.edu/handle/2152/13960 |title=Binary Adders |publisher=University of Texas |type=Thesis |date=May 1996 |access-date=2018-04-14 |url-status=live |archive-url=https://web.archive.org/web/20180414171823/https://repositories.lib.utexas.edu/bitstream/handle/2152/13960/txu-oclc-35052840.pdf?sequence=2&isAllowed=y |archive-date=2018-04-14}}
{{cite journal |author-last1=Kogge |author-first1=Peter Michael |author-link=Peter Michael Kogge |author-last2=Stone |author-first2=Harold S. |title=A Parallel Algorithm for the Efficient Solution of a General Class of Recurrence Equations |journal=IEEE Transactions on Computers |date=August 1973 |volume=C-22 |issue=8 |pages=786–793 |doi=10.1109/TC.1973.5009159|s2cid=206619926 }}
{{cite journal |author-first1=Richard Peirce |author-last1=Brent |author-link1=Richard Peirce Brent |author-first2=Hsiang Te |author-last2=Kung |title=A Regular Layout for Parallel Adders |journal=IEEE Transactions on Computers |volume=C-31 |issue=3 |date=March 1982 |pages=260–4 |issn=0018-9340 |doi=10.1109/TC.1982.1675982 |s2cid=17348212 |url=https://apps.dtic.mil/sti/pdfs/ADA074455.pdf|archive-url=https://web.archive.org/web/20170924184528/http://www.dtic.mil/get-tr-doc/pdf?AD=ADA074455|url-status=live|archive-date=September 24, 2017}}
{{cite journal |author-first1=Tackdon |author-last1=Han |author-first2=David A. |author-last2=Carlson |title=Fast area-efficient VLSI adders |journal=Proceedings 8th Symposium on Computer Arithmetic |pages=49–56 |publisher=IEEE |date=October 1987}}
{{cite journal |author-first1=Tackdon |author-last1=Han |author-first2=David A. |author-last2=Carlson |author-first3=Steven P. |author-last3=Levitan |title=VLSI design of high-speed, low-area addition circuitry |journal=Proceedings 1981 IEEE International Conference on Computer Design: VLSI in Computers & Processors |pages=418–422 |publisher=IEEE |date=October 1982 |url=https://yonsei.pure.elsevier.com/en/publications/vlsi-design-of-high-speed-low-area-addition-circuitry |isbn=0-81860802-1}}
}}
Further reading
{{refbegin}}
- {{cite book |chapter=Energy-Delay Characteristics of CMOS Adders |chapter-url={{GBurl|LmfHof1p3qUC|p=147}} |title=High-Performance Energy-Efficient Microprocessor Design |date=2006 |editor-last1=Oklobdzija |editor-first1=Vojin G. |editor-first2=Ram K. |editor-last2=Krishnamurth |author-last=Zeydel |author-first=Bart R. |pages=147–169 |series=Series on Integrated Circuits and Systems |publisher=Springer |isbn=978-0-387-34047-0 |doi=10.1007/978-0-387-34047-0_6 |url=https://books.google.com/books?id=LmfHof1p3qUC&q=9780387285948}}
- {{cite web |first=Ken |last=Shirriff |title=Reverse-engineering a carry-lookahead adder in the Pentium |date=January 2025 |quote=In this article, I reverse-engineer an 8-bit adder in the Pentium's floating point unit. This adder turns out to be a carry-lookahead adder, in particular, a type known as "Kogge-Stone." |url=http://www.righto.com/2025/01/pentium-carry-lookahead-reverse-engineered.html}}
{{refend}}
{{DEFAULTSORT:Kogge-Stone adder}}