+- 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: Expandable XOR gate (/thread-7163.html)
Expandable XOR gate - Azor_Ahai - 07-25-2015
WARNING: This will be a looooong post!
Hey guys I made something awesome the last couple of days. It’s an expandable XOR gate. So far I made a 2 input, a 5 input and a 10 input design for both of my version!
Originally I wanted to do this because I wanted my calculator to deactivate when no input, or too many inputs were given for A or B. I know now this could have been done simpler, but since then, the expandable XOR has become a project for me so I finished it!
So it started with examining this design for the normal XOR with 2 inputs.
LINK
Then when I learned how exactly it worked, I made this XOR with 3 inputs:
![[Image: WpQajWE.png]](http://i.imgur.com/WpQajWE.png)
Then I took a step up and made a XOR with 4 inputs:
![[Image: b1s1grD.png]](http://i.imgur.com/b1s1grD.png)
At this point I already knew this was not expandable. With each addition the amount of combinations I had to make went up like this:
x = combinations
n = amount of inputs
x = ( n2 – n) / 2
n – x
3 – 3
4 – 6
5 – 10
6 – 15
10 – 45
This meant that if I wanted to use all of those connections, it would get way too much really quickly, so I had to create an organized and expandable design where I could combine all pairs of inputs.
After a lot of trying, first horizontal, but soon moving over to diagonal since that solved some problems, I managed to do it. The version that I created is called Expandable XOR v1 (obviously because it is the first version of the expandable XOR). I should by now give a lot of credit to Jeppe. During the designing of the diagonal expandable XOR, he helped tremendously. Without him it wouldn’t have been possible.
This is the screenshot wherein all the expandable version I built are shown (including v2, which I will talk about in a sec)
![[Image: pcrZtNx.png]](http://i.imgur.com/pcrZtNx.png)
The way it works is as following:
The inputs go down in north-south lines. The go down to the bottom by repeaters and then turn into east-west lines. By doing that, they form a grid. Within this grid, each pair of levers is combined at intersections. This is done as following:
Top line ▷ repeater-├Torch ▷ Redstone dust dot ▷ Torch ▷ ‘Group’
Bottom line ▷ torch⏌
However we could exclude combining levers that were the same (a-a, b-b, c-c, d-d, e-e etc). This was very convenient as it gave us room to make the top lines be able to change into the bottom lines without taking in space.
These pairs of levers are grouped on top in the following way (in a 5 input version):
Group 1
a-b
a-c
a-d
a-e
Group 2
b-a
b-c
b-d
b-e
Group 3
c-a
c-b
c-d
c-e
Group 4
d-a
d-b
d-c
d-e
Group 5
e-a
e-b
e-c
e-d
And those groups were then inverted, and together formed the output. This makes it work as following:
While writing this thread I realized that I have a-b AND b-a. This is not very useful, because it takes in double the space. The problem with the version was that I NEEDED both of them. If I would delete either of them, the machine would stop working because a-b is the point where A can turn the output on, while b-a is the point where B can turn the output on. I cant do it at both!
I needed to design a version where at a-b, A AND B could turn the output on, thereby roughly halfing the size of the entire thing!
So that's how I came to designing Expandable XOR v2, which is way smaller than v1 and less messy! I made v2 completely by myself. What I had to do is replace the intersections like a-b with individual XORs. The XOR design I used fore those points where that of Tomy. This meant I no longer needed a-b and b-a, just a-b! I also made a 10 input, a 5 input and a 2 input version of this version to compare the two. This would be nice, but then I found out it didn't work! After alot of thinking before I went to sleep I realized I shouldn't put XORs at the intersections. Instead I should put ANDs at the intersections and have a big OR for the inputs!
So how this works:
The OR gate is checking if 0 inputs are on. If 0 are on, it sets the output to off.
Then, if you put one lever on, the OR deactivates and the output can turn on. However if any other lever is now also turned on, one of the ANDs will activate and turn the output back off.
When I showed v2.1 to Decapo and Tuchi, with its ANDs and OR, we found a better way to do it. I finalized the design, making it more compact and even faster. The result is my absolute pride, Expandable XOR v3!!!
This is the pictures where you can see how it developed from v1 to v3:
![[Image: vzbWph8.png]](http://i.imgur.com/vzbWph8.png)
Terminology Discussion
I have heard people disagreeing about the name, so I’ll explain why I’m near certain that this SHOULD be called a XOR gate.
DISCLAIMER: I am not an electrician or a computer programmer. I am not an expert at any of these things. This is just the explanation of my interpretation of why I think this should be called a XOR. You’re free to call it whatever you want!
Truthtable
00000=0
00001=1
00010=1
00011=0
00100=1
00101=0
00110=0
00111=0
01000=1
01001=0
01010=0
01011=0
01100=0
01101=0
01110=0
01111=0
10000=1
10001=0
10010=0
10011=0
10100=0
10101=0
10110=0
10111=0
11000=0
11001=0
11010=0
11011=0
11100=0
11101=0
11110=0
11111=0
The rule for this gate is:
If ONE input is ON, output is ON
If NO or MORE THAN ONE input is ON, output is OFF
XOR stand for Exclusively OR
Therefore one could phrase that this means:
If exclusively a or exclusively b or exclusively c or exclusively d or exclusively e is ON, output is ON (for 5bit)
To say that the rule for a XOR is that the output changes when an input changes is wrong, it is merely something that happens with a two input XOR, but has nothing to do with the term, Exclusively OR. You should create a rule from the name that already exists. The term, in my mind, clearly means that the output should only be on, if one, and only one, of the inputs is on. I am not the only one that thinks this, or at least acknowledges that this interpretation is well supported:
Logisim is a logic simulator which permits circuits to be designed and simulated using a graphical user interface, and when using multiple input XORs, it uses the rule: Output is 1, when a single input is 1
Advanced math blogs like this one discuss the different interpretations. (LINK: https://mindhunter74.wordpress.com/2011/04/25/xor-the-interesting-gate/)
A published book from IEEE about logic functions also say that the rule for a XOR gate is: "Exclusive OR. One and only one input must be active to activate the output."
Even the computer science branch of the university of Hamburg has the information about the two different interpretations on their website. (LINK: https://tams.informatik.uni-hamburg.de/applets/hades/webdemos/10-gates/00-gates/xor.html)
To say, a XOR is made of an AND and an OR, and therefore 11111 should equal 1 is also wrong. Using an AND and an OR is an essential part of creating a XOR, but the name and the intended function should make the design, not the other way around. In fact, v3 uses ANDs and an OR, but it doesn't make 11111=1.
Now in electronics, with a 3 input XOR when ALL inputs are ON, the output is ON. This contradicts my view of the XOR, but I think that electronics is doing it wrong. I must admit, I do not know a lot about electronics, but hear me out here. If I am right, and what electronics do is stacking the XOR like this:
A ⏋
B-├▷XOR▷-----├▷XOR▷ Output
C___________⏌
In that case, if electronics does it like that, I think electronics is doing it wrong. I am not saying it is not working, because apparently it works whatever they use it for, but I think the term Exclusively OR should not apply to that device simply because it contradicts the name of the machine since 111 = 1 while the rule should be, output is ON when exclusively a or exclusively b or exclusively c is ON (Exclusively being the key word here).
In conclusion, I made a cool expandable gate (with lots of help of Jeppe) and the meaning of the term XOR is more complicated than you might have thought. I will keep calling my gate a XOR, and you’re free not to! It is clear that both interpretations are widely used and while this interpretation is a little less popular does not mean it should be ignored, because it has a lot of reason to deserve the name ‘Exclusive OR’.
If you want to use this, feel free! The only thing I ask is that if you make a video about it, or publish it, just tell the viewer the expandable XOR was designed by me. If you need any help learning exactly how it put together, feel free to send me a message!
Whats next? I don't know, I think I'm done with the XORs for now. I'm gonna finish my calculator and then I think I want to learn how to build a CPU!
Sorry for the long post, here is a potato:
![[Image: 1324337899414602.jpg]](http://imgfave-herokuapp-com.global.ssl.fastly.net/image_cache/1324337899414602.jpg)
RE: Expandable XOR gate - PNWMan - 07-26-2015
How is ORE? it's been a while since I've been on, and since then I've realized something dastardly. Many people use some variant of the 5 torch XOR, when all you really need is 3 torches. All you do is take the torches off of the inputs. Think of it like this: If you invert one input of an XOR, it is the equivalent of inverting the output. Thus, if you invert both inputs, the output is double-inverted, reverting it back into an XOR. Now look at the inputs. They have double inversions themselves, which can then be replaced with a wire, taking off 2 torches and 1 tick.
This does NOT work for the standard 4-input XOR, however. that cannot be simplified further.
RE: Expandable XOR gate - Halflife390 - 07-26-2015
I like the Potato.
RE: Expandable XOR gate - Azor_Ahai - 07-26-2015
(07-26-2015, 12:43 AM)PNWMan Wrote: How is ORE? it's been a while since I've been on, and since then I've realized something dastardly. Many people use some variant of the 5 torch XOR, when all you really need is 3 torches. All you do is take the torches off of the inputs. Think of it like this: If you invert one input of an XOR, it is the equivalent of inverting the output. Thus, if you invert both inputs, the output is double-inverted, reverting it back into an XOR. Now look at the inputs. They have double inversions themselves, which can then be replaced with a wire, taking off 2 torches and 1 tick.
This does NOT work for the standard 4-input XOR, however. that cannot be simplified further.
I think ORE is doing good, then again I've only joined this server 10 days ago (Learned binary and became builder in 3 days) so I suppose i cant say much about it since I haven't seen what it was like before.
I can't exactly wrap my had around what you are saying, mainly because its 3:22 in the middle of the night, but I'll try this tomorrow and I'll post a reply here of what happened. (For some reason I don't think it will work)
(07-26-2015, 01:41 AM)Halflife390 Wrote: I like the Potato.
Thank you. As a 9gagger I have learned to apologise for a long paste by rewarding the reader with a potato...
RE: Expandable XOR gate - Legofreak - 07-26-2015
I believe can do this with hex in a fraction of the space with up to 15 inputs... it just wouldn't be syncronized
edit: my example:
![[Image: XXOR_zpsshfqurwc.png]](http://smg.photobucket.com/user/legofreak1988/media/minecraft/XXOR_zpsshfqurwc.png.html)
unary counter with a thing that turns off after 1
RE: Expandable XOR gate - Azor_Ahai - 07-26-2015
(07-26-2015, 05:17 AM)Legofreak Wrote: I believe can do this with hex in a fraction of the space with up to 15 inputs... it just wouldn't be syncronized
edit: my example:
unary counter with a thing that turns off after 1
Tried it, works, but is will be EXTREMELY slow, unless you make it diagonal. Which I wont do since I'm not good with comparators at all.
(07-26-2015, 12:43 AM)PNWMan Wrote: How is ORE? it's been a while since I've been on, and since then I've realized something dastardly. Many people use some variant of the 5 torch XOR, when all you really need is 3 torches. All you do is take the torches off of the inputs. Think of it like this: If you invert one input of an XOR, it is the equivalent of inverting the output. Thus, if you invert both inputs, the output is double-inverted, reverting it back into an XOR. Now look at the inputs. They have double inversions themselves, which can then be replaced with a wire, taking off 2 torches and 1 tick.
This does NOT work for the standard 4-input XOR, however. that cannot be simplified further.
Tried it, didn't work. If you have both inputs on, the output will stay on, which is not supposed to happen. Its because both of those torches are necessary for the AND
RE: Expandable XOR gate - Apuly - 07-26-2015
what book from IEEE?
RE: Expandable XOR gate - Azor_Ahai - 07-26-2015
(07-26-2015, 01:35 PM)Apuly Wrote: what book from IEEE?
IEEE-Std91a-1991
RE: Expandable XOR gate - dylanrusell - 07-26-2015
The most common interpretation of an XOR that uses more than 2 inputs is an odd parity. That's usually the case due to using the same cascading logic we apply to other logic gates, when we talk about multiple inputs. If you don't understand what I mean by cascading, I mean using 2 input Xors you put the output of the previous Xor into one of the next Xor's inputs and the other input is the Nth input.
Example lets say ^ = Xor, (A ^ B) = (A Xor B)
(A ^ B) ^ C
((A ^ B) ^ C) ^ D
RE: Expandable XOR gate - Azor_Ahai - 07-26-2015
(07-26-2015, 04:01 PM)dylanrusell Wrote: The most common interpretation of an XOR that uses more than 2 inputs is an odd parity. That's usually the case due to using the same cascading logic we apply to other logic gates, when we talk about multiple inputs. If you don't understand what I mean by cascading, I mean using 2 input Xors you put the output of the previous Xor into one of the next Xor's inputs and the other input is the Nth input.
Example lets say ^ = Xor, (A ^ B) = (A Xor B)
(A ^ B) ^ C
((A ^ B) ^ C) ^ D
But does that necessarily make it correct? I dont think so...
RE: Expandable XOR gate - dylanrusell - 07-26-2015
I just explained it is the most common interpretation. That implies there is more than one and does not mean one is more correct than the other. However it does say that your usage of multiple input Xors is used less. I didn't say that your usage is incorrect and it's wrong of you to say I did.
RE: Expandable XOR gate - Azor_Ahai - 07-26-2015
(07-26-2015, 04:23 PM)dylanrusell Wrote: I just explained it is the most common interpretation. That implies there is more than one and does not mean one is more correct than the other. However it does say that your usage of multiple input Xors is used less. I didn't say that your usage is incorrect and it's wrong of you to say I did.
I agree that there are different interpretations and they are both have good points
I was aware that this interpretation is less common and that saddens me, since I personally think that 1 input on, output on should be the rule for all xors and that this other interpretation should have a different name.
RE: Expandable XOR gate - Legofreak - 07-27-2015
I agree with it in the way a professor once explained "Exclusive OR"
"(XOR) is like: if you have 0 girlfriends, then you have 0 girlfriends.
Also, if you have 1 girlfriend, you have 1 girlfriend.
But, if you try to have more than 1 girlfriend, you will end up having 0 girlfriends."
RE: Expandable XOR gate - jxu - 07-27-2015
This is over-complicating a simple problem. Since xor is "chainable", a binary tree of xors would be sufficient (much smaller and O(log n) delay)
RE: Expandable XOR gate - Azor_Ahai - 07-27-2015
(07-27-2015, 03:44 AM)͝ ͟ ͜ Wrote: This is over-complicating a simple problem. Since xor is "chainable", a binary tree of xors would be sufficient (much smaller and O(log n) delay)
Like I said before, doesn't make it any more correct. Like I said, if you give it a different name that would suit it better, and the 1input, 1ouput gets the name XOR, it would make it more logical and the names would fit more. You could still use the binary tree.
RE: Expandable XOR gate - LordDecapo - 07-30-2015
Hey, I remember working on these with you
RE: Expandable XOR gate - Azor_Ahai - 08-01-2015
(07-30-2015, 04:45 PM)LordDecapo Wrote: Hey, I remember working on these with you
I do too!