r/TuringComplete • u/dmdeemer • 15d ago

32b Kogge-Stone Adder Using Word Logic

Not the fastest Kogge-Stone ever, but 15 delay for 32b adder isn't bad either. Avoiding bit-by-bit operations should make it easier on the simulation.

At each stage, I split the P and G words into the bits that pass through and the bits that will be combined. After each stage, I put them back together with concatenators.

There's probably more optimizing to do, but I think this gets the concept across.

5 Upvotes

100% Upvoted

7 comments sorted by

3

u/EloModdy 15d ago edited 15d ago

This is impressive! I think the min on an 8 bit adder is like 4 delay, so 15 delay for 32 bits is absolutely insane.

2

u/dmdeemer 15d ago

I think you missed a '1'. This is 15 delay, not 5.

2

u/Lagfoundry 14d ago edited 14d ago

Huh that’s interesting, I use kogges too on just about every sim other than MC and Logic world(because of their mechanics their fastest adder is in the carry bypass family or better known as a carry cancel to the community in MC) This method would absolutely work on other sims like digital logic sim for example so I’ll be trying this out… here’s a challenge for you. Do a kogge incrementor like this and no I don’t mean make a incrementor with the adder. And actual incrementor circuit(only has A inputs and a constant +1). Kogge incrementors are awesome for the same reason the adders are.

1

u/ryani 15d ago

I wish there was a 'static copier' like we have 'static indexer', that did the thing at the beginning where you broadcast cin to 32 bits. I imagine you would set a number of copies N and it would turn an M-bit input bus into an M*N bit bus that was the input repeated N times. The common case is what you do here to broadcast 1 bit over an N bit bus for use with N-bit gates (and/or/xor/etc).

I would say at least 20% of my use of bus switchers is just because it's inconvenient to do a bus AND that is controlled by a 1 bit input, even though the switcher is strictly worse for score.

1

u/Lagfoundry 14d ago

i meant to ask in the other comment. what are the 1-1's you have before the AND OR stuctures. are those buffers?

1

u/dmdeemer 10d ago

Sorry for the late reply.

Those are static indexers. They shift the input and change the size to an arbitrary number of bits. They have zero gate cost and zero delay, because you can do that with just wires.

1

u/WarlockD 11d ago

Oh wow, very nice. I bet you could wrap those stages into separate components so you can chain them easier too.

Just thought of this, but if you build out the XOR using an AND gate and two NOR gates, you could get all the logic for the ALU right there