• We’re currently investigating an issue related to the forum theme and styling that is impacting page layout and visual formatting. The problem has been identified, and we are actively working on a resolution. There is no impact to user data or functionality, this is strictly a front-end display issue. We’ll post an update once the fix has been deployed. Thanks for your patience while we get this sorted.

Logic Problem

N

NogginBoink

Diamond Member
I'm trying to build the equivalent of an eight-input XOR gate using discrete logic chips.

Either this problem is harder than I thought it was, or my brain is turning into mush.

What's the simplest way to implement this circuit?
 
Think about hte invesrse?

Put it into a matrix and crunch the simplest solution? Do the work to figure out the optimized logic first.
 
Originally posted by: Pepsi90919
Originally posted by: IHateMyJob2004
8 input XOR? How hte hell does that work? 2,3,4,5,6 or 7 total high bits produce an output of 1? 1,8 produce 0?
Click to expand...

no, just 256 produces 0
Click to expand...

How is that exclusive for 8 bits?

Sounds liek you jsut need to AND 1,2:3,4:5,6:7,8. Then just take hte results of those and AND them. And at the end, do an inverse(NOT).

EIDT: I think this is half of the solution. I still think 0 is another answer required for XOR.

EDIT 2: Wouldn't doing the same as the above AND exmaple, using ORs produce an answer for 0? I think those are the two cases that are of concern. If cases need to be inverted at the end of each case is to much work for my brain right now. But those two results will jsut need an OR, XOR or AND operation possibly followed by a NOT operation.
 
A chain of 7 XOR's me thinks.

((AxorB)xorC)xorD...

Or you could do the parallel implementation

[(AxB)x(CxD)]x[(ExF)x(FxH)]
 
Originally posted by: wasserkool
what year engineering course is that?
Click to expand...

It's not.

Believe it or not, it's for a practical application.

(My degree is in biology; I never got past my third semester of being an engineering major.)
 
Originally posted by: NogginBoink
I want a logic 1 output when any single input is logic 1. Else, I want a logic 0 output.
Click to expand...

Oh, that's jsut a tree of ORs.
1 OR 2 = A
3 OR 4 = B
5 OR 6 = C
7 OR 8 = D

A or B = Y
C or D = Z

Y OR Z = P <== EDIT 2

output = NOT(P) <== EDIT 2

EDIT, put this into a big formula, then do the negation and conversion to AND/OR trick. I forget what it's calle.d I'm 30, drunk and surprised I remember half of this stuff.
 
Originally posted by: NogginBoink
I want a logic 1 output when any single input is logic 1. Else, I want a logic 0 output.
Click to expand...

This is a NAND gate.

An XOR gate will be 1 if the input "byte" is odd, 0 if even.

EDIT: I mean OR, not NAND
 
Originally posted by: walla
Originally posted by: NogginBoink
I want a logic 1 output when any single input is logic 1. Else, I want a logic 0 output.
Click to expand...

This is a NAND gate.

An XOR gate will be 1 if the input "byte" is odd, 0 if even.

EDIT: I mean OR, not NAND
Click to expand...


No, an OR will give a 1 when both inputs are 1:

A B Out
0 0 0
0 1 1
1 0 1
1 1 1


An XOR will give a 1 when only one of the two inputs is 1.

A B Out
0 0 0
0 1 1
1 0 1
1 1 0
 
Build a 3-bit adder and take the output (Y2, Y1, Y0) and run Y0 through an inverter. Then run the output of the inverter and Y2 and Y1 into a NOR gate. I have no idea if this is the most efficient way (probably not), but it came into my head first.
 
i thought this was one of those figure out who walked the dog on sunday while wearing a red vest and drinking a glass of water type things. oh well.
 
Well, I give up for the night. I modeled both in Excel and in VBScript and the cascading two input XOR gates isn't the right solution. I obviously misinterpreted the homework problem I linked to.

(I emailed the prof with this problem; maybe he'll write back.)
 
Aha! The homework problem (cascading two-input XOR gates) will give a 0 output if there are an even number of 0 inputs, and a 1 output if there are an odd number of 0 inputs.
 
Well, one Xor with two inputs works like this: (A && !B) || (!A && B). So, to make an eigth input Xor gate, you just use 7 dual-input Xor gate. So you have this, with inputs (A,B,C,D,E,F,G,H) and output (O):

(A && !B) || (!A && B) = O1
(C && !D) || (!C && D) = O2
(E && !F) || (!E && F) = O3
(G && !H) || (!G && H) = O4, then

(O1 && !O2) || (!O1 && O2) = O5
(O3 && !O4) || (!O3 && O4) = O6, finally

(O5 && !O6) || (!O5 && O6) = O

So it takes a total of 7 Xor gates, but should give you what you're looking for. 0 for an even number of 1's or 0's, and 1 for and odd number of 1's or 0's.
 
Originally posted by: NogginBoink
Aha! The homework problem (cascading two-input XOR gates) will give a 0 output if there are an even number of 0 inputs, and a 1 output if there are an odd number of 0 inputs.
Click to expand...


To be technically correct, you should count the number of ones as odd or even as opposed to the zeros (XOR is odd parity). If you had a 9-input XOR, an even number of zeros would actually result in a 1 output. So, to be consistent, count the ones... 🙂

However that problem is distinctly different than logic that is 1 if an only if a single bit is 1. For instance, a bitwise XOR of 00100011 gives 1, whereas the above logic would give 0 since more than one input bit is 1.

EDIT:

I think one solution to the above problem is as follows

[((A xor B) xor (C xor D)) and ((A and B) nor (C and D))]
xor
[((E xor F) xor (G xor H)) and ((E and F) nor (G and H))]


Explanation:
"((A xor B) xor (C xor D))" is true when either one or three of the inputs is one.
"((A and B) nor (C and D))" is automatically false when three inputs are true, and automatically true when only one input is true (i.e. three are false).
ANDing the two together means the output is only true when one input is true.

Do this for the top and bottom four input bits. XOR the results. This ensures that the output is true if exclusively one bit is true among the top 4 or one bit is true among the bottom four.

Hence, this logic is one if and only if a single bit (among A-E) is one.

Yet another solution is to do

AB^C^D^E^F^G^H^+A^BC^D^E^F^G^H^... (where ^ is complement, or NOT of input) all the way through the sequence. however that would require many more logic gates.
 
Walla is very close. [((A xor B) xor (C xor D)) and ((A and B) nor (C and D))] definitely does a four input XOR function, but you can't do two of those and then XOR the result as Walla suggested.

What you need to do is expand the concept of the four input XOR that Walla had.

[((A xor B) xor (C xor D)) xor ((E xor F) xor (G xor H))] and [((A and B) nor (C and D)) nor ((E and F) nor (G and H))] ...Done with 7 2-input XOR gates, 5 2-input AND gates, and 3 2-input NOR gates. (15 total)

OR you can use 56 2-input AND gates with 8 inverters and implement the second solution that Walla provided. That will work, too.
 
Hm. Maybe this is the universe's way of telling me it's time to start getting into FPGA's. 🙂

Thanks for the input, everyone!
 
Originally posted by: NogginBoink
I want a logic 1 output when any single input is logic 1. Else, I want a logic 0 output.
Click to expand...

Make a good old truth table and your your boolean skillz. Better yet, go with a Karnaugh (??? spelling) diagram.

 
You must log in or register to reply here.

TRENDING THREADS

Back
Top