Simplifying Boolean Algebra (and XOR, XNOR)

Discussion in 'Homework Help' started by tripppah, Mar 28, 2011.

  1. tripppah

    Thread Starter New Member

    Mar 28, 2011
    2
    0
    I am trying to simplify a boolean expression that I have pulled from a K-Map with a "checkerboard pattern". I recall my lecturer saying something about in the case of not being able to group 1s in a k-map, it will always be a XNOR or XOR function, and that if the top left is 1/high/on then it will be XNOR but if it's 0/low/off it will be XOR (lease correct me if I'm wrong, it was a bit of a throw away statement.
    The top left in my k-map is a 0.

    (Question is: Design a 4-Bit Odd Parity Checker, output is 1 when exactly odd number of inputs (A,B,C,D is on )

    I have got down to

    <br />
A\cdot \overline B \cdot \overline C \cdot \overline D + \overline A \cdot \overline B \cdot \overline C \cdot D + A \cdot B \cdot \overline C \cdot D + \overline A \cdot B \cdot C \cdot D+ A \cdot \overline B \cdot C \cdot D + \overline A \cdot \overline B \cdot C \cdot \overline D + A \cdot B \cdot C \cdot \overline D<br />

    I am not comfortable simplifying this kind of thing at all, this is my first year at Uni after 5 years away from school! I think the fact that I don't remember "factoring" in decimal maths is what's holding me back here.

    I've been able to solve/simplify much simpler expressions, but this has just stumped me, I don't know where to start and feel like every time I make an attempt I'm just "guessing" my way through it, and going the wrong wrong way about it!

    I just need someone to give me a little push in the right direction, because I know the beginning and I have an idea of the end but I can't get through the middle...

    Also, XOR and XNOR are the two functions that we just barely touched but that I have not been able to get my head around. I understand the whole "equality gate"/"inequality gate" idea but I do not understand how to recognize this in an expression or put the function to use. I haven't been able to find anything detailed online, either.

    I was simply told if you see
    <br />
\overline A \cdot B + A \cdot \overline B<br />
    then you "know" its an XOR function. How do I "prove" this? What about XNOR?

    Sorry about the big post, I hope someone can point me in the right direction! Thanks for readin if you've gotten the whole way down here
     
  2. narasimhan

    Member

    Dec 3, 2009
    72
    6
    Last edited: Mar 28, 2011
  3. Georacer

    Moderator

    Nov 25, 2009
    5,142
    1,266
    You can prove this rather easily by induction:

    For starters, the simple 2-input XOR gate serves as a 2-bit odd parity checker. You can verify this by yourself. That means that you have a string of 2 bits that you know when it has an odd parity.

    Let's say now that you have a string of n-bits that you know that it has an odd parity. That result is stored in the variable Z. Z=1 for odd parity and 0 for even parity.
    Let A be a 1-bit variable that you want to add to the end of the n-bit string. You will find that Z XOR A gives the parity of the n+1 bit string.

    By induction, we come to the conclusion that for a n-bit string the parity function is:
    A0 XOR A1 XOR A2 XOR ... XOR An.

    Specifically for your problem F=A XOR B XOR C XOR D, which is the same as
    F= ((A XOR B) XOR C) XOR D.
     
  4. tripppah

    Thread Starter New Member

    Mar 28, 2011
    2
    0
    Thanks narasimhan you were right, I had been wrong all along, I filled out the output for that in my truth table wrong!
    That made it much easier, and that was were I was getting stuck, because I only had 7 pieces to work with not 8!
    Georacer thanks for your response and time, but I think that's a bit beyond where I'm at right now, I don't really understand what you've said.
     
  5. Georacer

    Moderator

    Nov 25, 2009
    5,142
    1,266
    Just try to remember that XOR gate is used to implement an odd parity checker for now.
    Did you manage to solve the question in the end?
     
Loading...