+- 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: Principles of Analog (signal strength) Arithmetic (/thread-1680.html)
Principles of Analog (signal strength) Arithmetic - Hans_Lemurson - 12-22-2013
Note: This is a re-post of a topic of mine that I rescued from the old RDF forums.
The ability to subtract the strength of one signal from another using a Comparator opens up the possibility of doing arithmetic and numerical manipulations by using the charge strength to encode a numerical value. This, most of us know. Knowing the possibility exists however is rather different from understanding how to manipulate the mechanics to create Arithmetic Devices.
With the Comparator, we have a subtractor, but one of limited utility. It's chief weakness is that it cannot produce negative numbers. However, via clever manipulation and special configurations, it is possible to do more than just subtract. The project I am working on right now is building a 4-wide analog adder, and in the process of design and refinement, I have made much use of the following arithmetic operations:
-Inversion
To perform this operation, you subtract the current signal value "A" from 15.
15 - A = ~A
You might wonder how you can perform inversion on positive non-binary numbers. The answer is that you technically can't (you're taking the complement, but it doesn't matter because it's functionally equivalent to the uses of Inversion in Binary Arithmetic.
Here is the table of complements: (can you decipher the pattern?)
0<->15
1<->14
2<->13
3<->12
4<->11
5<->10
6<->9
7<->8
It is interesting to note that if you look at the Binary representation of each of the Complement pairs, they are in fact the bitwise inverses of each other; Six (0110) and Nine (1001), for example. This lends further justification to the functional equivalence of Inversion and Complement. (It is important to note though that this equivalence holds even for numerical bases that are not readily converted into Binary, such as Decimal.)
The important principle to keep in mind for conceptualizing Inversion/Complement is: Big becomes Small, Small becomes Big. Seems trivial, but it's vital to allow you to keep track of what's going on in a circuit and why.
-Negation
Inverting a number is mathematically the same as flipping the sign and subtracting 1.
~B = -B -1
-B = ~B +1
These two equivalent equations are the mathematical basis that allows you to use Inversion to create Negative values (or make negative ones positive). In many cases their utility will be merely conceptual, since Comparators cannot yield negative numbers.
-Addition
Converting a Subtractor to an Adder requires Negating the "subtractant" input. Negating a single input is done in ALUs all the time to turn an Adder into a Subtractor. Fortunately, two negations cancel out, so the same tweaks that convert A+B into A-B can be used to turn A-B into A+B.
There are two ways of doing this for adders:
A - B = A + ~B +1 (this isn't feasible since it requires addition in the first place which we don't have yet.)
~(~A + B) = A - B (This is the one we'll use, when reconfigured for addition)
You can indirectly Negate the B input by Inverting A and then Inverting the Output. When applied to a subtraction operation (A-B) you get:
~(~A - B) = A + B
Structurally, you have a Subtractor that lies between two Inverters. I like to think of the 'between-two-Inverters' as "The Negative Zone" where any operation you perform has the opposite of it's normal effect. Thus, performing Subtraction while in the "Negative Zone" results in addition. Let's see it in action with an example:
Suppose we want to do 8+5. Let 8 be 'A' and 5 be 'B' (it works either way).
~8 = 7
7 - 5 = 2
~2 = 13
Thus, 8 + 5 = 13. Crazy, huh?
Let's try another example: 12 + 9!
~12 = 3
3 - 9 = 0 Uh-oh! Comparators can't give negative numbers
~0 = 15 Hmm...not looking good
Thus 12 + 9 = 15. This is not correct. This is far from correct. This is bad, since it's not uncommon when adding numbers that the result will exceed 15. How do we deal with this?
-Overflow Sum
You can't have negative signal strength values, and you can't have a signal strength that exceeds 15. What do you do? You use a second adder designed to handle exactly these cases! One that can compute sums for values greater than 15 (and ONLY for greater than 15).
The problem was that we were getting a negative number from subtraction, but as I'm sure you know, if you swap the values in subtraction, the answer is the negative of what it was before.
Instead of doing (~A - B), we will do (B - ~A). (To swap the inputs on a Comparator, all you have to do is rotate it 90 degrees).
Let's see how this works with that 12+9 example again:
~12 = 3 (~A)
9 - 3 = 6 (B - ~A)
...And then we keep the 6. We're done here. (B - ~A) is actually the value we want out of this. Why? Because MATH!!!
Remember the definition of Inversion in the first section?
~A = 15 - A
Substitute (15-A) for (~A)
(B - ~A)
(B -(15-A)) [substitute]
(B - 15 + A) [distribute the negative]
(A + B - 15) [re-arrange to look pretty]
So...that answer of 6? That's 12 + 9 - 15. The -15 is vitally important here, since it reduces an answer of 21 (out of our range) to an answer of 6 (inside our range). More importantly still, it's just 1 larger than the answer we need for the Sum when the addition produces a Carry.
We're working with base16 here, so whenever you get a number like 21, which cannot fit within the 0-15 range, you have to split it into a 16 and a 5. The 16 gets carried over the the next digit where it acts as a +1, and the 5 remains as the Sum for that digit.
This means that the value for the Sum when A+B exceeds 15 is:
(A + B -16)
This is 1 less than the result of (B-~A), but that's easy enough to fix since subtracting 1 is ridicuously easy to do in Signal-Strength manipulation: Just make the wire 1 longer.
This will be referred to as the "Modified Overflow Sum", for reasons which will become clear in a minute. Unmodified, the Overflow Sum displays values 1-15. Modified, it shows values 0-14. This is not a problem, since the largest value a half-adder will encounter is 30 from 15+15, whose proper Sum is (30-16 =?) 14.
-Carrying
(No algebra in this section, just design principles)
In order to make a useful adding machine, you have to be able to send a "Carry" signal to the next digit. Once you can generate a proper Sum and a Carry, then you have a Half Adder.
Quite fortuitously, the unmodified Overflow Sum is our "Carry" signal. It only ever yields a signal if the total is greater than 15...which is exactly the situation when you have to carry. How convenient!
The Carry signal in this sort of adder though has to do more than just communicate with the next digit though. Although we now have the ability to get the correct Sum for any set of inputs...we still have two different Sum outputs: the "Normal" and "Overflow" Sums. This can't do!
The Normal Sum should only give its output when the value is 15 or less. If it is more than 15, then it needs to kindly STFU, since it's stuck blaring a full-strength signal as it's output. We can't use that! In yet another piece of convenience, whenever the Normal Sum becomes irrelevant...that's when you have to Carry! This means that you can use the Carry Signal to disable the Normal Sum whenever A+B>15. (How you go about doing this is the personal choice of the engineer)
Once you have the Normal-Sum properly controlled, you can then just join the Normal and and Overflow sums together in one SUM wire for the output. The Overflow won't cause any problems, since it just outputs a 0 whenever the value is 15 or less.
Once you have all these things in place, then you've got yourself a Half Adder, my friend!
You should be able to figure out how to go and make a Full-Adder out of Half-Adders. I'm not going to explain that here, since this is kinda long already, and all I was trying to do was explain how you manipulate "Analog" signals to do Addition.
Conclusion
So that's my attempt so far at an algebraic explanation of how Analog Adders can be made from Subtractors (without the use of negative numbers).
And if I stop being a lazy bum, I might even include pictures at some point!
Note: 11 months later and I am still a lazy bum.
RE: Principles of Analog (signal strength) Arithmetic - Iceglade - 12-22-2013
That's brilliant... I was never able to get into analog but this thread might do it. Amazing read!
RE: Principles of Analog (signal strength) Arithmetic - Chibill - 12-22-2013
I can make it use negative numbers but then it's only 7 number both - & + plus 0
RE: Principles of Analog (signal strength) Arithmetic - WrytXander - 12-22-2013
Thank you Hans! Pure amazing :')
RE: Principles of Analog (signal strength) Arithmetic - jasonrubik - 01-27-2014
I know its off-topic, but I really couldn't find a good subforum to even mention this !
Whoa ! I just joined ORE recently, and here I am reading a post from Hans "The Lemur" Lemurson !
What a great coincidence !! I learned about you by reading Ohmganesha's post about his 16-bit CPU, and your collaboration with him... You sir are a genius ! And I remember your music video that you filmed on campus !!
The post: http://www.minecraftforum.net/topic/526445-my-alucpucomputer-progress-thread-video-and-worldsave/
... and now, low and behold, I discover that he is back from his almost-two-year-long hiatus ! He is NOT dead !
http://www.youtube.com/user/ohmgane3sha
http://www.youtube.com/watch?v=KzrFzkb3A4o
Does anyone else remember Ohm's 16-bit CPU from August 2011 ?
I know it is VERY outdated nowadays, but has there been anything else designed that is as compact and as elegant as his creation ?
... and to re-iterate, I could not find a good subforum to ask about Ohmganesha's CPU, so this seemed the most fitting place.
Thanks,
jasonrubik
RE: Principles of Analog (signal strength) Arithmetic - Iceglade - 01-27-2014
Build discussion, or maybe off topic? :p
RE: Principles of Analog (signal strength) Arithmetic - jasonrubik - 01-28-2014
(01-27-2014, 08:35 PM)Iceglade Wrote: Build discussion, or maybe off topic? :p
What subforum do you recommend we discuss redstone creations and/or best practices that are not related to specific creations on this server ?
And yes, as I stated it was off-topic, but what can I say I was rather excited when I both learned that Ohmganesha was not dead
and that Hans Lemurson is here... what a blast from the past !
TL;DR it won't happen again
RE: Principles of Analog (signal strength) Arithmetic - Frontrider - 03-22-2016
Really old, but I post the exact logic for decimal anyways (probably your best bet in analog for multiple reasons).
This is the logic of how I built mine back in the past.
if A+B <10 than A+B = A+B
if A+B >10 and A<5 and B <5 than A+B = A+B -10 + carry
if A+B >10 and A>5 and B >5 than A+B = A-5+B-5 + carry
The second 2 removes 10 from the values to keep the number inside valid bounds.
If you want to use real negative values, go for base8.
if only positives present,all the logic what you need is to check if the output is greater than 7, if it is subtract 8. you will never ever "run out of the signal".
If you don't work with decimal, than I would say to work with octal, the benefits can be really big.
For addition all you need is the standard hex adder, you can use the rest for either negative values, or just transmission.
I haven't got there in the time when I was into it, but you may be able to go balanced hex. balanced ternary was beneficial to saturn, so it should work in minecraft. (I'm aware that this statement is really wrong, since there are more things to it, but you know what I'm pointing towards)
I can't remember the exact logic what I had for subtraction, but I know that it was kinda funny, that I had more work with that.