CODEWITHSUNDEEP
xorboolean-expressionkarnaugh-map
Hakim Marley
Hakim Marley

Reputation: 331

Detecting XOR in Karnaugh Maps

I got the following Karnaugh Maps but I am still having problems working out the expression for XOR from each table. 

                Table 1
                -------
                  WZ
         00    01   11   10
       -----------------------
    00 |     |    |    |  1  |
       -----------------------
    01 |  1  |    |    |     |
       -----------------------
XY  11 |     |    |    |  1  |
       -----------------------
    10 |  1  |    |    |     |
       -----------------------


                Table 2 
                -------
                   WZ
         00     01   11   10
       -----------------------
    00 |     |  1  |     |   |
       -----------------------
    01 |     |     |  1  |   |
       -----------------------
XY  11 |     |  1  |     |   |
       -----------------------
    10 |     |     |  1  |   |
       -----------------------

It is XORs, but how can I easily deduce the XOR expressions?

Upvotes: 5

Views: 28508

Answers (4)

mahesh waldiya
mahesh waldiya

Reputation: 39

Basic rule for xor is that it gives 1 when odd number of input are 1. So in KMAP just see if 1 is present in all the odd number of 1's. Like WXYZ ( 0010, 1110 etc) if all gives 1 than there is a XOR in kmap.

Upvotes: 1

M-J
M-J

Reputation: 1113

Just put a copy of this map on the right hand side of it (or left, no difference) and then choose two tilted cubes. Now, we write the simplified function for both of them:

(A = 1) (AND) (B=0 when C=1 and B=1 when C=0) (OR) (A = 0) (AND) (B=0 when C=0 and B=1 when C=1) that finaly gives this:

(A AND (B XOR C)) OR (¬A AND (B XNOR C))

on paper

Upvotes: 1

Kit Ostrihon
Kit Ostrihon

Reputation: 834

I would not dismiss the variable z from the expression, because I think, the expression ¬z·(¬x·y·¬w + ¬x·w·¬y + ¬y·¬w·x + w·y·x) is not equal to (¬x·y·¬w + ¬x·w·¬y + ¬y·¬w·x + w·y·x). That would mean, that the K-map contains four doubles of ones, but there is only four singles.

I would rather find the expression in the K-map and then use the laws of Boolean algebra.

K-map of expression including 3-input xor and 3-input xnor

For the first table:

¬x·¬y·w·¬z + ¬x·y·¬w·¬z + x·y·w·¬z + x·¬y·¬w·¬z

¬z·((¬x + ¬y + w)·(¬x + y + ¬w)·(x + y + w)·(x + ¬y + ¬w))       //distributivity

¬z· (¬x + ¬y + w)·(¬x + y + ¬w)·(x + y + w)·(x + ¬y + ¬w)        //relaxed syntax

¬z· (¬x·¬x + ¬x·y + ¬x·¬w + ¬y·¬x + ¬y·y + ¬y·¬w + w·¬x + w·y + w·¬w)·
    (x·x + x·¬y + x·¬w + y·x + y·¬y + y·¬w + w·x + w·¬y + w·¬w)  //distributivity

Because of the laws of

  • idempotence (e.g.: ¬x·¬x=¬x),
  • absorption (e.g.:¬x + ¬x·y=¬x)
  • and complementation (e.g.: ¬x·x=0)

the expression is equivalent to:

¬z· (¬x                           +   0  + ¬y·¬w        + w·y +  0)·
    ( x  +                   +  0   + y·¬w +     + w·¬y +  0  )

¬z· (¬x + ¬y·¬w + w·y)·(x + y·¬w + w·¬y)     //just formatted

¬z· (¬x·x + ¬x·y·¬w + ¬x·w·¬y 
     + ¬y·¬w·x + ¬y·¬w·y·¬w + ¬y·¬w·w·¬y
     + w·y·x + w·y·y·¬w + w·y·w·¬y)          //distributivity

¬z· (  0  + ¬x·y·¬w + ¬x·w·¬y 
     + ¬y·¬w·x +     0      +      0
     + w·y·x +    0     +     0   )          //using the three laws↑ again

¬z· (¬x·y·¬w + ¬x·w·¬y + ¬y·¬w·x + w·y·x)    //how the 3-input XOR is defined

¬z· (x xor y xor w)

For the second table:

¬x·¬y·¬w·z + ¬x·y·w·z + x·y·¬w·z + x·¬y·w·z

z·((¬x + ¬y + ¬w)·(¬x + y + w)·(x + y + ¬w)·(x + ¬y + w))        //distributivity

z· (¬x + ¬y + ¬w)·(¬x + y + w)·(x + y + ¬w)·(x + ¬y + w)         //relaxed syntax

z· (¬x·¬x + ¬x·y + ¬x·w + ¬y·¬x + ¬y·y + ¬y·w + ¬w·¬x + ¬w·y + ¬w·w)·
   (x·x + x·¬y + x·w + y·x + y·¬y + y·w + ¬w·x + ¬w·¬y + ¬w·w)   //distributivity

z· (  ¬x +                      +   0  + ¬y·w +       + ¬w·y +   0 )·
   ( x  +                  +  0   + y·w +      + ¬w·¬y +   0 )

z· (¬x + ¬y·w + ¬w·y)·(x + y·w + ¬w·¬y)     //just formatted

z· (¬x·x + ¬x·y·w + ¬x·¬w·¬y
    + ¬y·w·x + ¬y·w·y·w + ¬y·w·¬w·¬y
    + ¬w·y·x + ¬w·y·y·w + ¬w·y·¬w·¬y)       //distributivity

z· (  0 + ¬x·y·w + ¬x·¬w·¬y
    + ¬y·w·x +     0    +     0
    + ¬w·y·x +     0    +     0)            //using the three laws↑ again

z· (¬x·y·w + ¬x·¬w·¬y + ¬y·w·x + ¬w·y·x)    //how the 3-input XNOR is defined

z· (x xnor y xnor w)

Upvotes: 4

Student
Student

Reputation: 821

The first table contains an Xor expression :

`First table`
                       w
    \ wz          ___________
 xy  \-----------------------+
     |     |     |     |  1  |
     +-----+-----+-----+-----+
     |  1  |     |     |     | |
     +-----+-----+-----+-----+ | y
   | |     |     |     |  1  | |
 x | +-----+-----+-----+-----+
   | |  1  |     |     |     |
     +-----------------------+
            ___________
                 z

as you could see the middle of the table (Z area) is fake. that is, the table function is :

F(Table1) = w'x'yz' + wx'y'z' + w'xy'z' + wxyz'

in binary form you could see a zero column :

F(Table) = 0010   eliminating Z    F(xor)= 001
           0100  ---------------\          010
           1110  ---------------/          111
           1000                            100
              ^--> fake

and the final table must be something like this :

`simplified xor table`
                w
      \ w 0   __1__
   xy  \-----------+
    00 |     |  1  |
       +-----+-----+
    01 |  1  |     | |
       +-----+-----+ | y    And " F = wy' + w'y " is an Xor only
   |10 |  1  |     | |      between 2 variables, right?
 x |   +-----+-----+
   |11 |     |  1  |
       +-----------+


The second table just contains an Xnor expression of the first one :

`Second Table`
F(Table2) = w'xyz + wxy'z + w'x'y'z + wx'yz
                          w
       \ wz          ___________
    xy  \-----------------------+        negation of table 2 is table 1 and vise versa
        |     |  1  |     |     |      F(Table2) = 1101    F(Table2)'= F(Table1) = 0010
        +-----+-----+-----+-----+                  1011                            0100
        |     |     |  1  |     | |                0001                            1110
        +-----+-----+-----+-----+ | y              0111                            1000
      | |     |  1  |     |     | |                   ^--> fake                       ^
    x | +-----+-----+-----+-----+         
      | |     |     |  1  |     |         
        +-----------------------+
           ^   ___________   ^
           ^        z        ^
           ^                 ^
           ^--------z'-------^

    the final table is:
                w
      \ w 0   __1__
   xy  \-----------+
    00 |  1  |     |
       +-----+-----+
    01 |     |  1  | |
       +-----+-----+ | y    And " F = w'y' + wy " is an Xnor
   |10 |     |  1  | |
 x |   +-----+-----+
   |11 |  1  |     |
       +-----------+

Always remember the tables that contain the zigzag pattern
are either an Xor or Xnor expression.

Upvotes: 4

Related Questions