Mathematical Redstone Circuits 9: Ladner Fischer Addition

This video talks about ladner-fischer adders and how they work, and why you might use this over another carry look ahead design

[navidryanrouf]

This is by far the best episode so far because of the sheer amount of derpation caused by benny

[bennyscube]

Most modern computer chips use a type of carry look ahead adder called a Kogge-Stone adder. Carry Look Everywhere is a form of carry look ahead which uses diodes to reduce circuit size.

[BlockandCube]

This Ladner-Fischer Adder is actually a Sklansky adder. Ladner-Fischer Adders are different.

[bennyscube]

Instant carry's big advantage is it's small and it can get you an answer pretty quickly.
The disadvantage is they often pulse, which can screw up some hardware, and you can't stream data through very quickly, which isn't desirable for things like CPU's.

The advantage of a well designed CLA system is you can get the same speed as instant carry while keeping fast streaming and avoiding pulsing, at the cost of size.

[numberxx]

you sir, are my new favorite person. I think ive seen you on the RDF but its about deserted by now. Im looking for an adder i can use in a giant multicore CPU for fractal generation. floating point adders.... your videos inspire me to build new things! thanks!

[bennyscube]

The logic in this adder is significantly faster than both of those. It's all a tradeoff between space and speed :)

[bennyscube]

Close, the only thing you're missing from that is that the Brent-Kung cells are only calculating carries, not sums. The adder still has a half adder at the start, and XOR at the end, so the only thing that has changed from a typical ripple carry adder is this more complex carry calculation method. That's the only reason the Brent-Kung cells are used, since in a layout like this it can spread the carry calculation into layers, rather than doing it one bit at a time. Does that help at all?

[danielk.]

Hey Benny,  
What would I have to do to add a carry in?
If I just take a Brent Kung Cell to combine the first bit and the carry out the thing with the "layers" doesnt work out... :(

[wayEmp]

100 layers of brent kung cells challenge

[MClightOfDay]

So if I understand this correct, it's like using Brent-Kung cells to hook together the bits into mini-adders, until it finally hooks together to create the final adder?

[bennyscube]

Just to keep both paths synced. If you don't care about synchronization, then glowstone would be fine.

[bennyscube]

The point of carry look ahead is that it isn't O(N). A layered system still isn't; it's O(log_2(n)) which is much more efficient than O(N).

Don't let the name fool you: "Instant" carry isn't O(1), nor is it in any way instant. It's still a ripple carry adder; it just carries much faster, at up to 1/8th tick per bit. Typically, it's faster when n is small. However, once it passes a certain value it is incomparably slower; log_2(n) grows much slower than n/8.

[henkie]

So if this would be made a 4 bit adder, you would need 2 layers, resulting in 4 tick addition, which will be 6 ticks because of 2 3 ticks xor gates. So in total it would be a stunning 2 ticks faster than the ripplecarry design, and about 3 times as big. I see why noone uses it for computers with a low bit adder xD. But no matter what, this still is huge if you are building an 8/16 bit adder. Not sure if this would be better than insta carry (now that the piston pulsing bug doesnt occur anymore as far as I know)

[TheTrueFreeStyle]

Hey Benny where is the difference between a Carry Look ahead adder and a Carry Look everywhere and am I right if I Day that most of the modern computerchipsets use look ahead adder?

[MrGquad]

I thought the point of a carry look ahead adder was that it was O of 1. Because you keep having to add more layers as you add more bits, this isn't O of 1. Wouldn't an instant carry adder with repeaters every 8 bits be faster and smaller?

[Groomtar]

Could you possibly add a schematic for the final build in this video ? I tried to build it twice now, but both times I made a mistake, or maybe I can't find the error you made and fixed later :) When you clip your video and changed your build, and then go to fix an error, I at least have a hard time keeping track of what is where :)

[OCoptimusconvoy]

Hey benny could you do Properinglish's 5tick proper lookahead logic?

[IDWpresents]

A Cary in is. The equivalent of a Generate from the outside of the adder. If you follow the pattern using it as a generate, if you understand the logic going into this you should be able to figure it out.

[IDWpresents]

Correction:

Ether make a 7 bit adder or just make an extra layer for it

[zxPivotManxz]

Are you trying to make it like its own unit that the devider connects to and sends/gets in/outs from or "software based" like built in to it? I mean I'm sure software based ones are slower. I've built something like what your talking about but can only input up to 2 and uses purely logic gates and I'm sure won't work with a divider since it's (I think this is what it's called) "Hardware based"