Mathematical Redstone Circuits 10: Carry Look Everywhere (CLE) Addition

This video discusses what Carry Look Everywhere addition is and shows how to make a relatively basic CLE adder

[wingdinger]

Yeah, I had that problem here too. What I found out is very interesting. The CLE algorithm actually operates under 2's complement, not the normal 1's complement. The output also gets inverted during subtraction mode, because the adder actually overflows and ends up with the 1's complement of the 2's complement answer. So all you have to do is add another toggleable inverter at the output and your CLE will produce proper differences. And don't worry, 1's complement could be done in a few steps.

[eideticex]

Generate represents whether the bit generates a carry value. Propogate represents whether the bit can generate a carry value. The reason why both are equally as important is so that we can factor in the carry from the previous bit.

Before the look ahead portion the logic is as follows:
Sum = A XOR B XOR Cin.
Propogate = A OR B.
Generate = A AND B.

One could replace the two XORs with a look-up. If an odd number of inputs are 1, so is the result. Not sure if it'd be faster.

[popcorny]

You've almost definitely gone over this before, but what exactly constitutes a propagate or generate? Basically, which combination of the 2 inputs per bit would give these values?

[utrathunder]

GAAAAHHH Please make more advanced computer tutorials! I'm so hooked! They are so am amazing and helpful. Oh, Btw: this was a great video too

[rcollins]

Oh man! 6-tick 16-bit adder? Mind sharing the recipe?

[SiberianHat]

Nice (: What's the id or damage value for the upside down stone slab? Thanks

[christopherhall]

It's called OCD texture pack, made by disco.

[tobiasklecker]

I Just made a 16 bit adder and it is REALLY big.

[wingdinger]

I do have a problem of my own. I think you forgot the Carry In, Benny, so I don't know where it's suppose to go. I guess I don't really need it, since I'm only using the Carry Out as an overflow/underflow indicator. Although I'm also trying to use the Carry Out as a negative indicator so that I can double the system's capacity, and I guess I could just store the negative bit and use it as a control signal for the ALU. Also, I would appreciate if you elaborated on how to improve the adder. :P

[CsharpPreza]

What has adder to do with carrying? I saw his adder tutorial and i think I understand it not bad but I don't know about any relationship between adder and carry.

[MoreBassieIsMoreFun]

I've build one of those for my computer, but in another vid you explained that a subtractor is just a adder with input A or B inverted and the carry in turned on. But with this CLE adder it doesn't work. Am I just derping or is this something with the design?

I just added a row of multiplexers for every input A so I can switch between adder/subtractor

Help please!

[KSICsavtcsg]

So Benny, when are you going to start doing multiplication in this series?

[ExhaustedPenguin]

I made two 10 bit ones that were 6 ticks each and made them work together using the carry-in method I made up. damn carry was 4 ticks because of signal extension, but that made it a maximum of 10 ticks for 20 bits. would have been a worst-case 14 ticks for 30 bits

[Cakeinator]

yeh carrying is kinda hard to explane in words without you seeing it. I would advise you looking up a basic adder tutorial that explains that if you want to know more :P

[CsharpPreza]

Ok, thx. Things are getting simpler :-)

[OmegaCraftable]

Wow, but that's massive for an adder though! great video anyway!

[rcollins]

So where can i find out more about optimizing something like this?

[oddball]

so when you add numbers in decimal for example add 9+1 you get 10 because 9+1=0 in the 1's place and in the 10's place you CARRY the 1 and get 10, same idea in binary only in base 2

[rcollins]

what kind of speed are you getting out of it?

[wingdinger]

But then wouldn't there be a tenth bit carry-Out? And seriously? Half a tick per bit? I only got my 8-bit adder working in 12 ticks. But like I said, I don't really need the carry-In for my project, because the carry-Out is being used as a control bit that an instruction can use to decide whether to add or subtract a value depending on whether it's negative. Good for finding absolute values or their negatives. For some reason, the CLE just seems more legit than instant-carry.