[SOLVED] Detecting XOR in Karnaugh Maps

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?

Solution

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.

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)