Carry Look-Everywhere Addition [Text + Images] [My first tutorial]

Carry Look-Everywhere Addition [Text + Images] [My first tutorial] - Printable Version

+- Forums - Open Redstone Engineers (https://forum.openredstone.org)
+-- Forum: ORE General (https://forum.openredstone.org/forum-39.html)
+--- Forum: Tutorials (https://forum.openredstone.org/forum-24.html)
+---- Forum: Advanced Tutorials (https://forum.openredstone.org/forum-26.html)
+----- Forum: Concepts (https://forum.openredstone.org/forum-28.html)
+----- Thread: Carry Look-Everywhere Addition [Text + Images] [My first tutorial] (/thread-1482.html)

Carry Look-Everywhere Addition [Text + Images] [My first tutorial] - AFtExploision - 12-04-2013

Note: This assumes you know binary logic gates and Ripple-Carry addition
------------------------------------------------------------------------
Carry Look-Everywhere Addition (CLE) is a Minecraft optimized carry-look ahead adder. But what is CLA (Carry Look-Ahead)?
------------------------------------------------------------------------
CLA is an adder that calculates carry at the same time as the sum, unlike RCA, where it is sum-carry rippling through the adders.
The first component of CLA is the half-adder. This is just an XOR and AND gate on the same two input lines. We'll call the XOR's output Pn and the AND's output Gn where n is the number of the half-adder, starting at 0.
So, we have the first part of the adder. Now how can we calculate sums with CLA using them?
Well, lets start at the carry calculation. For the first bit, bit 0 (in computers you start counting at 0, not 1), the only possible way to get a carry input is through Cin. So, the sum for the first bit (S0) is:

Code:
S0 = P0 xor Cin

Remember, P0 is the output of the XOR gate of the half-adder. So, basically it is:

Code:
s0 = (A0 XOR B0) xor Cin

the same as RCA. Simple right?
In fact, the sum of bit 'n' is:

Code:
Sn = Pn xor C(n-1)

where C(n-1) is the carry for the bit before bit 'n.' (For the first bit, C(n-1) is just Cin)
So far, this is the same as RCA. What's the difference? The difference is how C, the carry is calculated. In RCA you need to calculate the bit before to get the carry value, but in CLA you can calculate the value of all carries at the same time. Using equations (where the terms are next to each other is AND, a + is OR) you can get C0:

Code:
C0 = P0Cin + G0

How do you arrive here? Well for bit 0, when can you generate a carry? When one input is on (P0, xors are only on with one input, remember?) AND when it receives a carry in signal (which for bit 0 is just Cin) OR when both inputs are on (When both inputs are on, the carry-in doesn't effect the carry calculation. Remember G0 is the AND of both inputs).
OK, so for CLA carry calculations you OR together all possible combinations. Sounds hard to keep track of it all? Well, here is the equation for bit 1...

Code:
C1 = P1P0Cin + P1G0 + G1

Looking familiar? Yes, the carry calculations for bit 1 is all the terms from the carry calculation with an extra AND P1 added, OR'd with a G1. Why is this? Think about it. The terms for C0 tell you when you get a carry from bit 0. So, how do you calculate a carry from a carry-in? You AND it with the P output. So the "P1P0Cin + P1G0" is just AND'ing the possible carry-ins and adding a + 'Gn'. So, the carry calculation for any bit n can be found by taking the calculation for bit n-1, AND'ing a 'Pn' with the terms, and adding a '+ Gn', all the way to bit 0, where again,

Code:
C0 = P0Cin + G0

Why is this better than RCA? Well, for calculating carries you do NOT have to wait for the sum of the last bit to finish, only the P's, which, if you built your half-adders correctly, are sync'ed. This allows all the sums to be calculated faster, especially the ones near the end of the adder, where in RCA they would have to wait for the signal to 'ripple' to them.
----------------------------------------------------------------------
So, that is CLA. But what is CLE and why is it MC optimized? CLE is the exact same as in it follows the same logic, but different in that carries use the same line. Let me explain. In CLA, even though bit 0 and bit 1 both use the term 'Cin' to calculate their carries, there are different lines from Cin to the bits. In CLE, they use the same line. In this example, bit 0 would have P0Cin going into its carry line, but, with an instant diode or something of the sort. So then, we have a line for P0Cin. We add another instant diode (like glowstone) and wire it to bit 1. Here, we and P1 with P0Cin to git P1P0Cin. Because of the instant diode, it does not interfere with the calculations for bit 0's carry, and because of the instant diode from P0Cin to the carry line of bit 0, the rest of the possible carries does not interfere with P0Cin. This continues for the rest of the adder. Every new bit, one new term that can carry is added, but, we do the same for these. A practical way to do this is to Invert Cin, Invert P0, then use that line as the place for the instant diode to branch off. Then on bit 1, we connect an inverted P1 to the line and instant diode off to bit 2, and so on. Then, on each bit, we invert this signal to input to the carry line. This works on the idea that AND gates are just inverters, ORs, and another inverter. On the first bit, we invert the two inputs on the AND then or them. Next, we invert it to get P0 AND Cin. However, because we carry the inverted line, when we combine with P1 and invert for bit 1's carry line, we are basically making a big AND gate of P1, P0 and Cin that does not interfere with the first AND, and so on.
----------------------------------------------------------------------
Here is an example of the carries from Newomaster's CLE:
[Image: wLwCD9B.png]

The carry lines
[Image: PLw97RY.png]

The inverted Cin, the only thing needed to calculate carry for bit 0
[Image: do4Ry36.png]

Using half-slab insta diodes to carry the inverted Cin up to other carry lines
[Image: p5ZqSoe.png]

The gold block substitutes for P0. There is a torch on the other side to invert it and add it to the slab line.
[Image: nms3Jwp.png]

We do the same for the rest of the bits.
[Image: uZU0yqC.png]

Now, for the G0, which goes to the line for bit 1. This is the start, so the torch represents an inverted G0 going in.
[Image: 3cuOaaX.png]

Now we do the slab tower and torches. Wait for what we do with these.
[Image: naP8Xy7.png]

Finish this up for the rest of the terms....
[Image: ZQ9smtp.png]

Here we connect the torches in the horizontals. This is because the horizontals are all the same 'Pn" term.
This example is 4 bits, the 5th carry line is the Cout of the adder. We would XOR each of these lines with their respective P to get the sum.

RE: Carry Look-Everywhere Addition [Text + Images] [My first tutorial] - newomaster - 12-04-2013

Nice explanation... although I'm much too lazy to read it right now. It looks very delicious though.

RE: Carry Look-Everywhere Addition [Text + Images] [My first tutorial] - Jmking80 - 12-04-2013

Might be just me, but half for me I need to keep scrolling side ways to read everything. I find that rather annoying. Maybe you could thumbnail the pictures? But other then that very well explained.

RE: Carry Look-Everywhere Addition [Text + Images] [My first tutorial] - AFtExploision - 12-23-2013

(12-04-2013, 04:52 PM)Jmking80 Wrote: Might be just me, but half for me I need to keep scrolling side ways to read everything. I find that rather annoying. Maybe you could thumbnail the pictures? But other then that very well explained.

how do I do that exactly? NEED A TUTORIAL ASAP

RE: Carry Look-Everywhere Addition [Text + Images] [My first tutorial] - Jmking80 - 12-23-2013

lol, just resize the images would suffice.
And for the thumbnails, *glares at mort*

RE: Carry Look-Everywhere Addition [Text + Images] [My first tutorial] - WrytXander - 12-24-2013

I am thankful, great tutorial, +1 Smile

RE: Carry Look-Everywhere Addition [Text + Images] [My first tutorial] - Kotov - 01-08-2015

coolt being coolt :3

RE: Carry Look-Everywhere Addition [Text + Images] [My first tutorial] - CreepyTacoMan - 01-09-2015

wat. This is more than a year old. Like, wat?

RE: Carry Look-Everywhere Addition [Text + Images] [My first tutorial] - Magic :^) - 01-09-2015

(01-08-2015, 01:01 PM)Kotov Wrote: coolt being coolt :3

Aggreed xD

RE: Carry Look-Everywhere Addition [Text + Images] [My first tutorial] - AFtExploision - 01-09-2015

My tutorial lives

RE: Carry Look-Everywhere Addition [Text + Images] [My first tutorial] - Legofreak - 02-06-2015

am i going crazy or are those pictures for a 5 bit adder?

RE: Carry Look-Everywhere Addition [Text + Images] [My first tutorial] - AFtExploision - 02-06-2015

It is 5 bit

RE: Carry Look-Everywhere Addition [Text + Images] [My first tutorial] - Legofreak - 02-06-2015

(12-04-2013, 01:12 AM)AFtExploision Wrote: This example is 4 bits, the 5th carry line is the Cout of the adder.

I just kept looking at it and thinking "why are there 6 carry lines then?"

btw, took me long enough to want to take time to learn this, huh?

RE: Carry Look-Everywhere Addition [Text + Images] [My first tutorial] - LordDecapo - 02-07-2015

Just saw this post for the first time cause of (^those bumbs) and I dropped an f bomb in one of those logs xD lol. I feel like a bk