The CCA - Carry-Cancel Adder - Printable Version

The CCA - Carry-Cancel Adder - Printable Version

+- Forums - Open Redstone Engineers (https://forum.openredstone.org)
+-- Forum: ORE General (https://forum.openredstone.org/forum-39.html)
+--- Forum: Projects & Inventions (https://forum.openredstone.org/forum-19.html)
+---- Forum: Completed Projects (https://forum.openredstone.org/forum-21.html)
+---- Thread: The CCA - Carry-Cancel Adder (/thread-5493.html)

The CCA - Carry-Cancel Adder - Magic :^) - 01-07-2015

./warp cca
video here: https://www.youtube.com/watch?v=FrWNrTTcdXg

NOTE: There have been massive improvements to the CCA design, so I may redo this OP at some point. So there will be some trimming done to this post, and I'll probably do a tutorial post on how to build one in a new thread.

First, I'd like to say that Yap7 also came up with the same type of carry logic independently of myself a few months later, before joining ORE. I figure he deserves just as much credit as I do for coming up with this style of addition.

- for future reference, my original design was created in September 2014

How it works:

The adder is comprised of 3 stages:

In stage 1, the adder performs XOR, AND, and NOR.
XOR is pretty straightforward. It's just the sum without the carry.
AND is the Generate signal G.
NOR is the Carry Cancel signal CC.

In stage 2, the G and CC signals are sent to two separate slab stacks. The G signal goes to a slab stack that connects to the base input of every comparator in the CCA carry tower. The CC signal goes to a slab stack that connects to the side input of every carry tower comparator.

When these signals hit the slab stacks, you need to provide full power (15 signal strength). The carry calculation works in ratios of signal strength so make sure that your input strengths are all the same! Also keep in mind that these slab stacks are supposed to 'bleed upwards' to the other comparators, that's the core of how this system works.

The two slab stacks are used by a comparator at each level to calculate whether there is a valid carry. The G signal is what is passed through the comparator, and the CC signal is what goes into the side for comparison. If the signal strength read from the CC stack is higher than the signal strength from G, the carry is 'cancelled'.

This works because a physically higher CC will always have a higher signal strength than a G signal from below.
The same goes for if G is stronger than CC, it can only mean that G happened at least 1 level higher than CC. This would force signal out of the comparator as the CC signal can't subtract it all. This comparator's output would signify that a carry happened, and needs to be XORed in stage 3.

In stage 3, the output of the comparators of stage 2 are fed into a final XOR with the first XOR result from stage 1. The output of this XOR is the final result.

In summary:
Stage 1: xor, and, nor. (2 ticks)
Stage 2: carry calculations. (1 tick)
Stage 3: final xor. (2 ticks) (This can be 1 tick with a special type of XOR I designed)

Now here's the example adder:

First, here's a top-down view of the adder. The blue part is stage 1, the white is stage 2, and the yellow is stage 3. Green is the signal source for AND/Generate, and red is the signal source for NOR/Carry-Cancel.
[Image: 9wHWSTZ.png]

In stage 1 to create the AND, I NOR the 1 tick XOR and NOR using the existing circuitry. I then add 1 tick to the NOR and XOR to sync with the AND. (that makes 2 ticks in total.)
The nor is on the far right.
[Image: z6ACLsM.png]

Here's a close-up of the comparator that does the carry calculations. Note the difference in signal strength here where G>CC. That's allowing the carry to go through as G happened above CC.
[Image: eiMRkw5.png]

(For later comment context, this post was originally on what this adder design should be called)

RE: About my vertical adder, name TBC - Phase - 01-07-2015

it looks like a bunch of horz circuits bussed vertical. Those XORs aren't the best design for that :\

RE: About my vertical adder, name TBC - Magic :^) - 01-07-2015

(01-07-2015, 07:23 PM)Phasesaber Wrote: it looks like a bunch of horz circuits bussed vertical. Those XORs aren't the best design for that :\

I assume you're talking about the first screenshot? That's derp, I know full well Tongue

EDIT [23/11/15]: referenced screenshot no longer in OP

RE: About my vertical adder, name TBC - Nuuppanaani - 01-07-2015

This is an incredibly original adder with probably the fanciest carry logic there is, but isn't it like 6 ticks?

Can't be the fastest vertical adder Big Grin

We need a vertical PLA!

RE: About my vertical adder, name TBC - Magic :^) - 01-07-2015

oh and i'd might as well post some specs:
5 tick, synced
6 wide, 11 long.
doesn't need strong signal in, but strong signal is outputted.

RE: About my vertical adder, name TBC - GISED_Link - 01-08-2015

Very nice Topic !

[edit]AAAAAAAH The post was so long that I've miss you have mention the Yap's trial creation ^^. Anyway, there are two other pics', maybe will show another way to realise this new design of adder (but not a new technology).[/edit]

[Image: 96432320150108090117.png]

Those pictures don't show the latest version. Contact Yap for further informations.

All the carry are generate in the same "diod tower".

Maybe this design will be the new classic CLA adder ? (Why CLA, because it runs like the CLA, with only one diod tower)

RE: About my vertical adder, name TBC - Konstacon - 01-08-2015

(01-07-2015, 08:43 PM)Nuuppanaani Wrote: This is an incredibly original adder with probably the fanciest carry logic there is, but isn't it like 6 ticks?

Can't be the fastest vertical adder

We need a vertical PLA!

The purpose of PLA is it to be horizontal and fast...

Also, instead of some carry cancel shit call it VCLE (vertical CLE) or at least VCE (vertical carry everywhere)

RE: About my vertical adder, name TBC - LordDecapo - 01-08-2015

This honestly seems like a Non-piston ICA... I have looked and looked, and can't justify calling it a CLA/E

I like the name SSA (Special Snowflake Adder)
Big Grin

PS, that name wins, it has over NINE THOUSAND!

RE: About my vertical adder, name TBC - Magic :^) - 01-08-2015

Decap, think of the comparators as using hex compression to store the 8 stacks used in 8-bit cle logic. That's why I say it's using modified cle logic.

SSA... HhhmmmmMMMMmmnnn

RE: About my vertical adder, name TBC - Magic :^) - 01-09-2015

What about this: I'll call it CCA. It can stand for Comparator Carry Adder. Because, that's what it does. Also it avoids the CLE vs ICA thing

EDIT: actually nah it'll stand for Carry Cancel.

RE: About my vertical adder, the CCA - Nuuppanaani - 01-10-2015

(01-08-2015, 01:20 PM)snugglycreeper9 Wrote: The purpose of PLA is it to be horizontal and fast...

I agree with it being supposed to be fast, but WTF, how does the logic in the adder have anything to do with its physical shape? PLA can be built diagonal or vertical too? Seriously I want to hear your thoughts on this, why does PLA have to be horizontal when so many people prefer diagonal (or vertical in this case)?

RE: About my vertical adder, the CCA - Konstacon - 01-11-2015

(01-10-2015, 10:43 PM)Nuuppanaani Wrote:
(01-08-2015, 01:20 PM)snugglycreeper9 Wrote: The purpose of PLA is it to be horizontal and fast...

I agree with it being supposed to be fast, but WTF, how does the logic in the adder have anything to do with its physical shape? PLA can be built diagonal or vertical too? Seriously I want to hear your thoughts on this, why does PLA have to be horizontal when so many people prefer diagonal (or vertical in this case)?

Firstly, you'd have to come up with a diagonal LFA, and also for C1 step (handling 4 bits) you'd need a diagonal carry AND propagation.

Also, if you need diagonal adders, go to CLE, it's the same speed, and won't take nearly as much space. However, we never had really any 4 tick horizontal SS adders, which is what cut and embi went for when designing it...

If you meant VERTICAL, good luck designing a vertical LFA, then removing the first two bit calculations and making them 4 bit propagation and carry systems...

RE: About my vertical adder, the CCA - Nuuppanaani - 01-17-2015

uh oh...

So all you're saying is it's harder to implement? That's indeed true, but hasn't stopped redstoners before.

But PLA is more compact than CLE, it's optimized CLE. PLA is also synced by default. It has less signal strength problems for input & output. Great explained the shape very well in a different thread, so there's that. I prefer PLA's shape over CLE, but that's subjective.

I feel like making somesorta ranty video about PLA vs CLE because a lot of people don't seem to understand it.

RE: About my vertical adder, the CCA - Magic :^) - 01-20-2015

g-guys...
I made it 4-wide Big Grin

I found out I could use XNOR instead of AND for this, as even signal strength still cancels what's coming out of the comparators.

So the signals in the generate stack are not as 'clean', but meh. I may be able to design a smaller alu too with this technique ^^

RE: About my vertical adder, the CCA - Apocryphan - 01-20-2015

congrats! i know the feel, its good.

RE: The CCA - Carry-Cancel Adder - Magic :^) - 01-26-2015

For the lulz I made a diagonal CCA ALU. Now might be a good time to point out that all the ALU designs I have for this are OR based.

It's 7 ticks (5+2 because inverters)... but hey, it's got good throughput Big Grin

RE: The CCA - Carry-Cancel Adder - Magic :^) - 01-27-2015

I've made a logisim circuit of the adder's design. It shows how much stuff is compressed by the comparators quite (horribly) well Wink

Adder cell:
[Image: lMkEB0n.png]

Carry logic:
[Image: YvjQsAD.png]

notice how it is ORing together the relevant weighted cancel wires before cancelling weighted generates

there's a .circ file in the .zip attached here
(admins plz allow .circ attachments)

RE: The CCA - Carry-Cancel Adder - tokumei - 01-27-2015

I just found out that there is a logisim build for linux Big Grin

O happy day!

RE: The CCA - Carry-Cancel Adder - Magic :^) - 01-27-2015

Big Grin

decap was able to run it on his phone before iirc, I think he had to compile everything himself tho

RE: The CCA - Carry-Cancel Adder - AFtExploision - 01-27-2015

PLA is sklanky's not LFA... and it isn't cle at all

RE: The CCA - Carry-Cancel Adder - LordDecapo - 01-28-2015

(01-27-2015, 06:08 AM)The Magical Gentleman Wrote:

decap was able to run it on his phone before iirc, I think he had to compile everything himself tho

The jar version works on anything with a mouse and keyboard and supports java for the most part.
as for my mobile version.... let's not talk about that xD my compile way didn't work fully... but I did find a relatively easy way to port it over with not many changes (since android can run java).
just been to lazy to port it... 8 really want to tho xD who knows I may start back on that.
if anyone wants to help PM me

RE: The CCA - Carry-Cancel Adder - Magic :^) - 01-30-2015

IT'S 4 TICKS!!

Big Grin

I made a special xor gate to save a tick, so now it's pretty fast. I also sacrificed a lot of signal strength for the output though, but I would be putting a shifter on the end etc. anyways for the alu so it shouldn't matter too much :3

So basically I made an xor that is 1 tick in one side, and 2 ticks in the other. It doesn't depend on input strenghts, but a low input strength on the 1-tick side will give a low output strength.

[Image: wwwg5IB.png]

The xor:

RE: The CCA - Carry-Cancel Adder - GISED_Link - 01-30-2015

Well done !

RE: The CCA - Carry-Cancel Adder - Yap7 - 02-01-2015

Ho, so it really wasn't a CLE Adder?

Good job for making it 4 ticks, if it become the new best design for adder in cpu, I'll have a fun time saying I failed my trial by building the very first one.

RE: The CCA - Carry-Cancel Adder - Magic :^) - 02-01-2015

Your genius was just too much for them to comprehend xD

RE: The CCA - Carry-Cancel Adder - Magic :^) - 03-03-2015

UPDATE:

.. well a late update really.

me and embi made a 4 tick 4 wide CCA a good while ago, and have been messing around with it for a while. It has a signal strength problem where in some cases it only outputs 1 signal strength Sad

However!
I have designed a 4 tick 5 wide CCA which has 4 signal strength output worst case, and has the possibility of being expanded to be able to perform 4 tick 9bit calculations?!
idek anymore xD

I'm using this design in my new dataloop for my new CPU.
The aluified design has many possibilities too, like a feasible 7 tick accumulator based dataloop.
(you could go for 6 if you wanted a headache)

no pics because i'm sleepy. You can find the newest design at ./warp cca

RE: The CCA - Carry-Cancel Adder - PNWMan - 03-27-2015

A while ago i made a derpy adder called the SCI (Section-Carry Inversion) Adder. It ended up having two carries and was an overcomplicated RCA. Imagine a derpy 2's complement device with tons of crap added on: that's what the SCI adder turned into.

RE: The CCA - Carry-Cancel Adder - LordDecapo - 03-27-2015

(03-27-2015, 06:31 PM)PNWMan Wrote: A while ago i made a derpy adder called the SCI (Section-Carry Inversion) Adder. It ended up having two carries and was an overcomplicated RCA. Imagine a derpy 2's complement device with tons of crap added on: that's what the SCI adder turned into.

WHERE HAVE YOU BEEN?! Haven't seen u online in ages. XD

RE: The CCA - Carry-Cancel Adder - Magic :^) - 03-27-2015

ooh based on carry select?
I've toyed with the idea of carry select, but no matter how I see it the time it takes to select the outputs ends up around the same speed or slower than a normal carry system.
The control signal busing is so critically timed it is pretty much useless. Once you add a repeater to your cout and point it at the mux, any performance you would have gained is already lost ;-;

RE: The CCA - Carry-Cancel Adder - CrazyGuy108 - 06-19-2015

(01-26-2015, 12:04 AM)MagicalGentleman Wrote: For the lulz I made a diagonal CCA ALU. Now might be a good time to point out that all the ALU designs I have for this are OR based.

It's 7 ticks (5+2 because inverters)... but hey, it's got good throughput

How do you get the OR function in a CCA ALU?

RE: The CCA - Carry-Cancel Adder - Magic :^) - 06-19-2015

[Image: dTxHiq0.png]

The pink line that goes in to the third comparator on the blue section is the OR control line.

That comparator when not disabled floods the xor output with an OR signal instead. It does not matter that the XOR is still active, as the only time that an XOR is on is also a time when the OR line is on.

RE: The CCA - Carry-Cancel Adder - Legofreak - 06-21-2015

the simplicity of how you make it OR makes me want to re-think my life choices.

RE: The CCA - Carry-Cancel Adder - Chibill - 08-22-2015

Sorry for the bump. But I am going to try and make a diagonal or horizontal one of this.

RE: The CCA - Carry-Cancel Adder - Magic :^) - 08-22-2015

nice Big Grin

it's really interesting seeing other people's takes on the design :3

RE: The CCA - Carry-Cancel Adder - CrazyGuy108 - 08-22-2015

Can't wait till 3 tick CCA comes around. Combining the carry logic with the final XOR, according to Yap7, would definitely tie CLE and CCA for fastest adder, making vertical CPUs not such a bad idea.

But still...

#diagonalmasterrace

RE: The CCA - Carry-Cancel Adder - Yap7 - 08-23-2015

My theory is that a 3 ticks CCA is possible if we use some tricks.

The minimum ticks is 3 because there is at least 3 successive components:

1 - The first XOR, a NOR, a AND
2 - The comparator's carry
3 - The last XOR

As the comparator is 1 tick and it exist design for 1 tick XOR, steps 2 and 3 can take 1 ticks each. If we want 3 ticks, we have to make the first step 1 tick too.

There is 3 components:
- The XOR : We can make it 2 ticks because it can be done at the same time as the carry (the output of this XOR is linked to the input of the last XOR)
- The NOR : /(A+B) It's easy to make it 1 ticks
- The AND : /(/A+/B) It need 2 ticks to build an AND gate, that's the problem here.

A way to solve this is to give the illusion of a 3 ticks CCA in a CCA ALU by using the input inverter (either way, what the need of a CCA if it's not for an ALU?). As it can give both inverted and non inverted input within 1 tick, we can use it to take inverted inputs for the AND gate and make it a NOR witch is 1 tick.

So the CCA will have 4 inputs: A,B,/A,/B and the inverter will have 4 outputs. By mixing them, it's possible to have a system inverter+CCA witch is 4 ticks. As the inverter will be 1 ticks, it will be like the CCA is 3 ticks.

So in theory, it is possible to have a 3 ticks CCA inside a CCA ALU, but the design is hard to find as we had to fit 4 inputs inside a very compact space.

RE: The CCA - Carry-Cancel Adder - Don_Manuel_1229 - 08-23-2015

I was studying CCA today. (I'm confident that i can prove that it is a carry look ahead adder).
There is no AND gate, thus no generate line. The AND is implicit in the (A xnor B) nimplies (A nor B) ....along with a lot other calculations happening on the carry-logi comparator.

I Too believe that CCA can be 3 ticks, but i think that the problem is equivalent to making a 1 tick XNOR gate

#Let me know if you want me to post a proof Big Grin

RE: The CCA - Carry-Cancel Adder - Magic :^) - 08-23-2015

yeah i found out about the xnor thing a while ago, that's how there's a 4-wide 4-tick one in existance.

and yeah, the biggest problem in making it 3 tick is making a 1 tick XNOR gate that outputs full signal strength.

also don, if you look back a few pages i have a logisim circuit modelling how CCA behaves, with an array of transistors, or gates, and weighted wires to represent the signal strength being handled by the comparators. It looks very similar to CLA

RE: The CCA - Carry-Cancel Adder - Don_Manuel_1229 - 08-23-2015

(to any future ppl reading this: a full signal strength xnor or a 14signal strength xnor; for 8 bits)
Yeah, I saw the logisim post. I realized it would be more fun if i figured it out (since i know the 4 tick layout by heart). Hex logic ftw! Spend all night on it, basically ~6hrs. I was sad to learn that there is no generate line, only a propagate line and a "pre generate line" (what you call the cancel line), bc it complicates some project i have. Hopefully I'll overcome it!
Hate to sound like a fan-girl... but great stuff, Magic!

RE: The CCA - Carry-Cancel Adder - jxu - 08-24-2015

I'm still not sure what this is (I never took the time to figure out the carry system), but the title reminds me of an old prototype I had on my plot years ago of a carry-skip adder that delivers good performance increases with very limited extra logic. Maybe this is similar, maybe not, but I haven't seen anyone ever develop the idea.

RE: The CCA - Carry-Cancel Adder - Magic :^) - 05-24-2017

https://www.google.com/patents/US5487025
[Image: US5487025-6.png]

welp
finally found the real world equivalent for CCA, took me a while. That carry chain looks exactly like the CMOS chain I designed for my real world implementation.

>propagate-kill circuit
ayyyyyyyyyyyyyyyyyyyyyyyyy

I think it's kinda cool I designed this independently though, this is a pretty obscure algorithm. Found it through searching "complementary transistor carry chain".

on second thought, my implementation is slightly different with an implicit propogate instead of their generate, but essentially it all boils down to the same thing.

On further searching, later iterations in other patents referencing this get even closer to my design lol https://www.google.com/patents/US6367059
[Image: US06367059-20020402-D00005.png]

I should go grab that logism file off my old laptop for comparison. will go grab it this evening. (the logism screenshot earlier in this thread is different, modelling the MC implementation)

RE: The CCA - Carry-Cancel Adder - LambdaPI - 05-24-2017

Nice magic(no sarcasm intended)

RE: The CCA - Carry-Cancel Adder - Chibill - 05-24-2017

COOL! I like how we invent things separately from history then find wait this exists!

RE: The CCA - Carry-Cancel Adder - Magic :^) - 05-25-2017

[Image: Zo6kZFW.png]

gottit
this was the final version of my design

RE: The CCA - Carry-Cancel Adder - Chibill - 05-26-2017

nice!

RE: The CCA - Carry-Cancel Adder - Koyarno - 05-28-2017

How many transistors can you chain on 1 line though. I would get that each pass loses some signal that you have to introduce a fresh source again

RE: The CCA - Carry-Cancel Adder - Magic :^) - 06-06-2017

I figure that would be down to the transistor specs. When working directly with silicon, you can specify quite a few of the parameters which could change how much resistance is in the channel etc.