Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Reducing 4 variable algebra in K-map

  1. Oct 5, 2005 #1
    I'm having problems reducing 4 variable boolean algebra in K-map. The equation is:

    A'B'C'D' + A'B'CD' + A'B + AB'C'D' + AB'CD'

    Drawing K-map reveil

    00 01 11 10
    00 1 0 0 1
    01 1 1 1 1
    11 0 0 0 0
    10 1 0 0 1

    So I wraped entire 2nd row. Then wraped the 4 corners to get
    A'B + B'D'

    But I'm missing C in the equation and obviously wrong. Anyone, please help. I'm going to have to get partial credit on this lab but still need to understand for the next exam. Thanks for all your help.
  2. jcsd
  3. Oct 5, 2005 #2
    the whole point of k-map is to minimize function representation, so that you use as less inputs possible...you should be happy that C went away!

    EDIT: you can even check it manually using theorem that X'(expression) + X(expression) = expression(X' + X) = expression(1) = expression.

    A'B'C'D' + AB'C'D' + A'B'CD' + AB'CD' + A'B
    = B'C'D'(A + A') + B'CD'(A' + A) + A'B
    = B'C'D' + B'CD' + A'B
    = B'D'(C' + C) + A'B
    = B'D' + A'B.
    Last edited: Oct 5, 2005
  4. Oct 5, 2005 #3

    you still could add 2 more terms A'C'D' + A'CD' but there is really no point.
  5. Oct 5, 2005 #4
    If there's 4 inputs to the circuit but one input "C" is not inplemented at all in the circuit, how does the circuit process inputs from "C"?

    I verified via the truth table that even without the C input the results are still correct. I guess the input for C is not part of the input or output of this circuit. I had a guy at work who's a phd candidate for EE and CE and he insisted that the equation must have C.
    Last edited: Oct 5, 2005
  6. Oct 6, 2005 #5
    did he happen to explain why?
  7. Oct 6, 2005 #6
    He said looking at my K-map that I can wrap the entire row 2 but can't cancel out C and D. He's reasoning is that they're more than 2 bits apart. Only adjacent cells can be canceled.

    He then had me draw 7 circles to wrap the 1's in the map. Somehow his analysis ended up with me having 2 XOR. I tried validating his new minimized equation in Multisim and the truth table is obviously wrong.

    He then asked me to input the entire 16 variations of ABCD input from the truth table into the original equation. I told him that the equation was a "sum of products". So that as long as 1 "product" if true would make the whole equations true. So instead of plugging entire 16 variations of inputs into the equation, I just find where the individual products are true in the truth table and mark them 1's and the rest would be zero.

    When I told him that my original answer was correct based on you guys' response, he told me I had to work out the entire equation step by step and not use the K-map. That's like going back into the stone age.
    Last edited: Oct 6, 2005
  8. Oct 6, 2005 #7
    I can't see anything you have done wrong with this problem because

    1- if you input your variation in A'B + B'D' it will give you the exact truth table of the full equation

    2-if you made some simple simplification you will realize that C has no effect on the value of the output

    3-Ask him to right the truth table of the original equation and the one you got out o k-map if the output is the same then your equation must be right,
    He doesn't have to be right just because he is carrying a PhD
  9. Oct 6, 2005 #8
    Thanks to all for validating my results.
  10. Oct 8, 2005 #9
    It might be a bit easier to work with K-Maps, if we explain a little bit just why they work. For this, I have attached a couple of template maps. One (Attachment 2) is laid out with the first variables (A & B) identifying rows (the way success2be does it above), and the other (Attachment 1) is laid out with the first variables identifying the columns of the map. Both methods will work, but I prefer The approach given in Attachment 1, because it reads out the way we are more accustomed --- so, this one is used to illustrate.

    The map has both the binary number values for A, B, C & D given along the top and side, and the identification of the states of the Literals (A or A', B or B', etc.). The actual map is put together in the standard way.

    The reason that the map is configured with the progression 1, 2, 4, 3, etc...., is because, in this way, as we move either vertically or horizontally from one "cell" of the map, to an adjacent cell, --- one and only one bit changes. (A Reflecting Gray-code arrangement). This means that when we take any cell and its adjacent cell, we will have one literal (say N) for which the values N and N' will be the case. And, where we have NN', we know from the Boolean Postulates that the result of this is that the represented variable equals '1', and can be eliminated.

    The attachments show which variable changes in any couple. In Attachment 1, for example, the indicators show which single variable changes as we cross any of the vertical or horizontal 'divider lines' between any two 'adjacent' cells. You can put in the binary values for the 'cell numbers' and see this.

    From this we can state the following:

    1) Call a "couple" any pair of adjacent cells on a map. (Take, for example cells '1' and '5' on attachment 1, or cells '14' and '15'.) {This holds for a map of any size, and is exclusive for a map of four variables or fewer. For larger maps, there may be couples that are not physically adjacent, but this is beyond the scope of what we are discussing here. Suffice it to say, any two adjacent cells form a couple.}

    2) Couples consist of vertically or horizontally adjacent cells only. Diagonally adjacent cells cannot form couples.

    3) Whenever a couple is formed one variable is eliminated from the term. That variable is the one that had a change ("0" to "1", or "1" to "0").

    4) Higher order couples can be formed by coupling adjacent lower order couples. Thus, two first-order couples, when coupled (adjacent) form a second-order couple (two variables are eliminated).

    5) From the way that higher order couples are formed, every coupling must have 2^N terms (ie. 2, 4, 8, 16 ....). Furthermore, a coupling must be rectangular.

    6) A K-Map is a closed entity. Therefore, the leftmost column is 'adjacent' to the rightmost column, and the top row is adjacent to the bottom row. Thus, couplings can occur across these.

    [7) If the map cells are numbered, as are the ones that I have attached, then the numbers in the cells, of any coupling will differ by an integral power of two. This is unimportant at the elementary level, but if ordered maps of more than four variables are employed this can be a useful checking tool.]

    8) The greatest minimization is obtained if a coupling of the greatest number of cells is taken. This is true even if there is an 'overlap' of the various terms.

    I hope this has been of some help, Now to answer some of the concerns:

    Actually, the fact that C is missing is good. This implies that where you have A'D', this occurrs when there is C and when there is C', but then, that is all the time with respect to C, so you can drop it out, as "waht" says in the following:

    Not so!

    Read number "6" above.

    The K-Map is a lot less prone to human error, and is totally reliable if used correctly.


    Attached Files:

    Last edited: Oct 8, 2005
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook