OSDev.org

The Place to Start for Operating System Developers
It is currently Thu Mar 28, 2024 10:12 am

All times are UTC - 6 hours




Post new topic Reply to topic  [ 9 posts ] 
Author Message
 Post subject: Algorithm to XOR Logic Gates (with JavaScript code snippet)
PostPosted: Fri Dec 30, 2016 8:42 am 
Offline
Member
Member
User avatar

Joined: Tue Mar 06, 2007 11:17 am
Posts: 1225
Image

Video (source code at the end of this message): How XOR Gates Work. JavaScript Source Code Snippet.

The explanation of the workings of the XOR function at the logic gate level is very simple.

In principle, we have as a minimum an input of 2 different bits.

The XOR circuit will return an 1 as a result of operating two bits with different values.

At the input, we need an OR gate with two inputs.

We also need an AND gate with two inputs, and a negation gate in front of this AND to invert its result.

The first input pin of the OR gate is connected to the first input pin of the inverted AND gate, and the second pin of the OR gate is connected to the second input pin of the inverted AND gate.

In other words, we want to get the OR and the invertd AND results for the two input bits.

The two result bits we get from the OR and the negated AND gate are passed to a final AND gate with two inputs.

The result of this last AND gate will be the XOR value.

The intention of this circuit is to use the OR gate to detect the presence of a 1 and return a 1 as a result; and the intention of the negated AND gate is detect the presence of a 0 and return a 1 as a result.

The OR gates are oriented to return 1 when there is at least a 1 as input.

The AND gates are oriented to return 0 when there is at least a 0 as input. With the negation gate we get a 1 from the AND when tehre is a 0 present.


So with the OR we detect if there is a 1 present, and return 1.
With the AND we detect if there is a 0 present, and in that case we get a 0 which we negate to get a 1 in the presence of an input 0.

Now, if there is a 1 present, the OR will return 1.
And if there is a 0 present, the negated AND will return 1.


Let's take as example 11 binary.
When the OR gate processes it, we will get 1, which means that there is a 1 present at the input.
Now, when the AND gate processes the two original input bits set to 1, it will also return 1, but the negation gate in front of it will invert this result from 1 to 0 to indicate that there wasn't any 0 at the input.
When the 1 from the OR and the 0 from the negated AND get through the final AND gate, we will get a 0 in response of the original 11 binary input value. It will indicate that both input bits had the same value.

It's as if the XOR circuit was a question.: Are both input bits different? We will get a 1 indicating TRUE as a response if both input bits are different.
Now we can clearly see that if both input bits have the same value as in this case with 11 binary, the value returned by the XOR function will be 0.



Let's take another example, like 10 binary.
The OR gate takes both bits, 1 and 0, and returns 1 since there's at least a 1 present at the input.
The AND gate takes both bits 1 and 0, and returns 0 since there's at least a 0 present.
But with the negation gate in front of this AND we get a 1, which indicates that there was a 0 present at the input.

Now, the bit with value 1 from the OR result, and the bit with value 1 from the negated AND result enter the last AND, the output AND, the result AND, and since both bits are 1, we return 1.
What this indicates is that the OR took the input 1 and 0 and detected the presence of a 1, returning 1.
It also indicates that the negated AND took the input 1 and 0 and detected the presence of a 0, returning 1.
Since the OR and the negated AND gates indicate on their own both the presence of an input 1 and an input 0, respectively, we return a 1 for the XOR function of the whole circuit, to indicate that both bits were different.

As we can also see, at the most fundamental level we always operate the gates two by two, so solving will be easy. Even in the normal arithmetic we operate results two by two at the simplest logical level.

The next JavaScript code demonstrates how the logic of the XOR function would look like implemented as a program. Whenever both input bits have the same value, the program will return 0. If they are different, it will return 1.

Step 1.: We need 2 input variables of at least 1 bit in size.
Step 2.: OR the values of both input variables.
Step 3.: AND the values of both variables and negate the bit values of this result.
Step 4.: Apply AND to the OR and the NAND results. This is the XOR value.


Most programming languages and assemblers have a XOR operator or instruction. It's very useful to generate shorter code which assigns 0 to a variable or register by applying XOR using its own value. As we have seen, since all bits will be the same by using the same processor register or memory variable as the first and second XOR operands, all bits will be cleared to 0 to indicate that they all had the same values.


Code:

function XOR(bits_A, bits_B)
{
/* Step 1: We need 2 input variables of at least 1 bit in size. */

var OR_0        = bits_A|bits_B;     /* Step 2: OR the values of both input variables. */
var NAND_0      = ~(bits_A&bits_B);  /* Step 3: AND the values of both variables and negate the bit values of this result. */
var XOR_AND_OUT = OR_0&NAND_0;       /* Step 4: Apply AND to the OR and the NAND results. This is the XOR value. */

return(XOR_AND_OUT);
}


_________________
Live PC 1: Image Live PC 2: Image

YouTube:
http://youtube.com/@AltComp126/streams
http://youtube.com/@proyectos/streams

http://master.dl.sourceforge.net/projec ... 7z?viasf=1


Last edited by ~ on Fri Dec 30, 2016 6:24 pm, edited 1 time in total.

Top
 Profile  
 
 Post subject: Re: Algorithm to XOR Logic Gates (with JavaScript code snipp
PostPosted: Fri Dec 30, 2016 9:38 am 
Offline
Member
Member
User avatar

Joined: Tue Aug 02, 2016 1:52 pm
Posts: 286
Location: East Riding of Yorkshire, UK
Well, you overcomplicated that a bit.

_________________
com.sun.java.swing.plaf.nimbus.InternalFrameInternalFrameTitlePaneInternalFrameTitlePaneMaximizeButtonWindowNotFocusedState
Compiler Development Forum


Top
 Profile  
 
 Post subject: Re: Algorithm to XOR Logic Gates (with JavaScript code snipp
PostPosted: Fri Dec 30, 2016 11:07 am 
Offline
Member
Member
User avatar

Joined: Fri Mar 07, 2008 5:36 pm
Posts: 2111
Location: Bucharest, Romania
I don't understand the point of this huge post that is obvious to anyone who understands 5th grade propositional logic or Boolean algebra:

A ⊕ B ≡ (A ∧ ¬B) ∨ (¬A ∧ B)

Everything you explained follows from plugging values into A and B. And you can use symbolic manipulation to come up with whichever implementation is more convenient. For instance, using De Morgan's law a couple of times you get:

A ⊕ B ≡ (A ∨ B) ∧ (¬A ∨ ¬B) ≡ (A ∨ B) ∧ ¬(A ∧ B)

In practice, NAND gates and NOR gates are often the most economical.

_________________
"Computers in the future may weigh no more than 1.5 tons.", Popular Mechanics (1949)
[ Project UDI ]


Top
 Profile  
 
 Post subject: Algorithm to XOR Logic Gates (with JavaScript code snippet)
PostPosted: Fri Dec 30, 2016 6:35 pm 
Offline
Member
Member
User avatar

Joined: Tue Mar 06, 2007 11:17 am
Posts: 1225
The point is showing the most basic logic that was used to come up with this.

The XOR is like a bag of binary bits.

We have at least two inputs, at least two bits in the bag to operate with each other. We assume that we have at least 1 bit per input. Those are two bits to operate with.

The OR grabs the bits from the first and the second variable inputs, inside the XOR bag (circuit), searching at least for a 1, and returning a 1 if it's there.

The NAND also grabs the bits from the first and the second variable inputs, inside the XOR bag, and sees if there is at least a 0, returning 1 in that case.

Now, the output AND of the XOR circuit build just operates the ORed and NANDed bits. If they were different, both input bits will be 1 and we will also get 1 with the last AND.

This is because if the OR tells us that there was at least a 1, and if the NAND tells us that there was at least a 1, then we actually have two bits with different values, 0 and 1, because they return 1 in those cases (the OR returns 1 if it found at least a 1 and the NAND returns 1 if it found at least a 0 - in other words they found two bits that have different value) and the XOR dictates that in that case, whenever the two input bits have different value we will get a 1.

This is a more abbreviated version of the same explanation.

_________________
Live PC 1: Image Live PC 2: Image

YouTube:
http://youtube.com/@AltComp126/streams
http://youtube.com/@proyectos/streams

http://master.dl.sourceforge.net/projec ... 7z?viasf=1


Top
 Profile  
 
 Post subject: Re: Algorithm to XOR Logic Gates (with JavaScript code snipp
PostPosted: Sat Dec 31, 2016 1:55 am 
Offline
Member
Member
User avatar

Joined: Sat Mar 31, 2012 3:07 am
Posts: 4591
Location: Chichester, UK
You have a great knack for making the simple sound complicated.

XOR is defined by a logic table, just as AND and OR are. Simples.


Top
 Profile  
 
 Post subject: Re: Algorithm to XOR Logic Gates (with JavaScript code snipp
PostPosted: Sat Dec 31, 2016 4:00 am 
Offline
Member
Member
User avatar

Joined: Wed Jul 13, 2011 7:38 pm
Posts: 558
~ wrote:
The point is showing the most basic logic that was used to come up with this.

L4B already posted the most basic logic for XOR. There is no need to complicate it further than this.

Love4Boobies wrote:
A ⊕ B ≡ (A ∧ ¬B) ∨ (¬A ∧ B)


Top
 Profile  
 
 Post subject: Re: Algorithm to XOR Logic Gates (with JavaScript code snipp
PostPosted: Sat Dec 31, 2016 12:41 pm 
Offline
Member
Member
User avatar

Joined: Tue Mar 06, 2007 11:17 am
Posts: 1225
Kazinsal wrote:
~ wrote:
The point is showing the most basic logic that was used to come up with this.

L4B already posted the most basic logic for XOR. There is no need to complicate it further than this.

Love4Boobies wrote:
A ⊕ B ≡ (A ∧ ¬B) ∨ (¬A ∧ B)
But that sure doesn't explain or makes anyone understand the simple intention of each of the four components of the minimal XOR circuit, as I just did.

_________________
Live PC 1: Image Live PC 2: Image

YouTube:
http://youtube.com/@AltComp126/streams
http://youtube.com/@proyectos/streams

http://master.dl.sourceforge.net/projec ... 7z?viasf=1


Top
 Profile  
 
 Post subject: Re: Algorithm to XOR Logic Gates (with JavaScript code snipp
PostPosted: Sat Dec 31, 2016 6:10 pm 
Offline
Member
Member

Joined: Mon Mar 25, 2013 7:01 pm
Posts: 5099
A typical XOR gate in CMOS is 6 transistors.

An OR, NAND, and AND gate in CMOS is 16 transistors.

Anyone building complex circuits will use 6-transistor XOR gates to minimize transistor count.

Instead of spending paragraphs explaining an XOR design that no one uses, you can explain it in a single sentence: an XOR gate outputs 0 when its inputs are both the same, and 1 when its two inputs are different.


Top
 Profile  
 
 Post subject: Re: Algorithm to XOR Logic Gates (with JavaScript code snipp
PostPosted: Sat Dec 31, 2016 8:24 pm 
Offline
Member
Member
User avatar

Joined: Fri Mar 07, 2008 5:36 pm
Posts: 2111
Location: Bucharest, Romania
~ wrote:
Kazinsal wrote:
~ wrote:
The point is showing the most basic logic that was used to come up with this.

L4B already posted the most basic logic for XOR. There is no need to complicate it further than this.

Love4Boobies wrote:
A ⊕ B ≡ (A ∧ ¬B) ∨ (¬A ∧ B)
But that sure doesn't explain or makes anyone understand the simple intention of each of the four components of the minimal XOR circuit, as I just did.


What are you talking about? Each operand is negated in one conjunction so one conjunction will evaluate to 1 iff the operands are different. That's it; the other conjunction is irrelevant and discarded by the disjunction. As for your circuit, I already derived it above. I don't want to see how you explain other one-liners, like multiplication, integration, or derivation. :)

_________________
"Computers in the future may weigh no more than 1.5 tons.", Popular Mechanics (1949)
[ Project UDI ]


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 9 posts ] 

All times are UTC - 6 hours


Who is online

Users browsing this forum: No registered users and 25 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group