# OSDev.org

The Place to Start for Operating System Developers
 It is currently Mon Mar 27, 2017 8:38 am

 All times are UTC - 6 hours

 Page 1 of 1 [ 9 posts ]
 Print view Previous topic | Next topic
Author Message
 Post subject: Algorithm to XOR Logic Gates (with JavaScript code snippet)Posted: Fri Dec 30, 2016 8:42 am
 Member

Joined: Tue Mar 06, 2007 11:17 am
Posts: 867

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);
}

_________________
http://www.archefire.org/_PROJECTS_/

YouTube Development Videos:
http://www.youtube.com/user/AltComp126/videos

If my website doesn't work, please reload until the webpages can display. My server is really slow.

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

Top

 Post subject: Re: Algorithm to XOR Logic Gates (with JavaScript code snippPosted: Fri Dec 30, 2016 9:38 am
 Member

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

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

Top

 Post subject: Re: Algorithm to XOR Logic Gates (with JavaScript code snippPosted: Fri Dec 30, 2016 11:07 am
 Member

Joined: Fri Mar 07, 2008 5:36 pm
Posts: 2049
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

 Post subject: Algorithm to XOR Logic Gates (with JavaScript code snippet)Posted: Fri Dec 30, 2016 6:35 pm
 Member

Joined: Tue Mar 06, 2007 11:17 am
Posts: 867
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.

_________________
http://www.archefire.org/_PROJECTS_/

YouTube Development Videos:
http://www.youtube.com/user/AltComp126/videos

If my website doesn't work, please reload until the webpages can display. My server is really slow.

Top

 Post subject: Re: Algorithm to XOR Logic Gates (with JavaScript code snippPosted: Sat Dec 31, 2016 1:55 am
 Member

Joined: Sat Mar 31, 2012 3:07 am
Posts: 2644
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

 Post subject: Re: Algorithm to XOR Logic Gates (with JavaScript code snippPosted: Sat Dec 31, 2016 4:00 am
 Member

Joined: Wed Jul 13, 2011 7:38 pm
Posts: 486
Location: Victoria, Canada
~ 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)

_________________
The good thing about Unix is when it screws up, it does so very quickly.

Top

 Post subject: Re: Algorithm to XOR Logic Gates (with JavaScript code snippPosted: Sat Dec 31, 2016 12:41 pm
 Member

Joined: Tue Mar 06, 2007 11:17 am
Posts: 867
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.

_________________
http://www.archefire.org/_PROJECTS_/

YouTube Development Videos:
http://www.youtube.com/user/AltComp126/videos

If my website doesn't work, please reload until the webpages can display. My server is really slow.

Top

 Post subject: Re: Algorithm to XOR Logic Gates (with JavaScript code snippPosted: Sat Dec 31, 2016 6:10 pm
 Member

Joined: Mon Mar 25, 2013 7:01 pm
Posts: 1014
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

 Post subject: Re: Algorithm to XOR Logic Gates (with JavaScript code snippPosted: Sat Dec 31, 2016 8:24 pm
 Member

Joined: Fri Mar 07, 2008 5:36 pm
Posts: 2049
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

 Display posts from previous: All posts1 day7 days2 weeks1 month3 months6 months1 year Sort by AuthorPost timeSubject AscendingDescending
 Page 1 of 1 [ 9 posts ]

 All times are UTC - 6 hours

#### Who is online

Users browsing this forum: Bing [Bot] and 5 guests

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

Search for:
 Jump to:  Select a forum ------------------ Operating System Development    OS Development    OS Design & Theory    Announcements, Test Requests, & Job openings Everything Else    General Programming    General Ramblings    Auto-Delete Forum OSDev.org    OSDev Wiki    About this site
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group