Implement the boolean function using only a multiplexer

Discussion in 'Homework Help' started by popeyes, Feb 25, 2013.

  1. popeyes

    Thread Starter New Member

    Feb 25, 2013
    6
    0
    Given logic signal a,b and c, along with their complements

    Using only a mux to perform the function below:

    [​IMG]

    It doesn't say any restriction on multiplexer, but assuming the simpler the better. It kind drive me nuts....I guess 2to1 mux will not work anyway, right?
     
  2. WBahn

    Moderator

    Mar 31, 2012
    17,720
    4,788
    If the restriction is that you can use "only a mux" ('a' mux, as in 'one' mux), then no, you can't use a 2:1 mux, in general, for a function of three variables. There are SOME functions of three variable in which you can, but not in general.

    In general, a 2^N:1 mux can implement ANY function of (N+1) variables or less and some functions of more than (N+1) variables
     
  3. panic mode

    Senior Member

    Oct 10, 2011
    1,319
    304
    if you are using 2:1 mux, you will need 3 levels or seven units.
    if you are using 8:1 mux, you can use just one.
     
  4. WBahn

    Moderator

    Mar 31, 2012
    17,720
    4,788
    Using 2:1 muxes you only need two levels with three muxes and possibly an inverter.

    Using 4:1 muxes you only need one mux and possibly an inverter.
     
  5. popeyes

    Thread Starter New Member

    Feb 25, 2013
    6
    0
    Just curious about how to do it in 4:1 mux....
     
  6. thatoneguy

    AAC Fanatic!

    Feb 19, 2009
    6,357
    718
    Have you diagrammed the truth table?

    Column 1 Column 2 Column 3 Column 4 Column 5
    A B C Out
    x x x x x
    x x x x
    x x x x
    x x x x
    x x x x
    x x x x
    x x x x
    x x x x



    Here's a blank 8:1 mux
    I0-I7 are Mux Inputs, S2-S0 are selectors

    Column 1 Column 2 Column 3 Column 4 Column 5 Column 6 Column 7 Column 8 Column 9 Column 10 Column 11 Column 12
    S2 S1 S0 I0 I1 I2 I3 I4 I5 I6 I7 Out
    0 0 0 x x
    0 0 1 x x
    0 1 0 x x
    0 1 1 x x
    1 0 0 x x
    1 0 1 x x
    1 1 0 x x
    1 1 1 x x





    Quote the post, fill in the Truth Table (swap numbers for each 'x'), post results, then fill in MUX entries.
     
    Last edited: Feb 27, 2013
    absf likes this.
  7. panic mode

    Senior Member

    Oct 10, 2011
    1,319
    304
    just do the truth table and see what comes out. if i'm not mistaken (it's late and i'm tired) this should be it:
     
    • mux.png
      mux.png
      File size:
      5.5 KB
      Views:
      97
  8. WBahn

    Moderator

    Mar 31, 2012
    17,720
    4,788
    Come on, panic mode, you have been around long enough to know better than to just post solutions!
     
  9. WBahn

    Moderator

    Mar 31, 2012
    17,720
    4,788
    Think about how you would implement a 2-input function using just a 2:1 mux. You have two inputs, A and B. Use one of them to select which channel of the mux to use. So let's use A for that. You now need to bring a signal into input D0 of the mux that is the correct signal given A=0 and, likewise, you need to bring in the signal into input D1 of the mux that is the correct signal given A=1. In either case, the signal can only depend on B and there are only four possibilities:

    B 0 1 B B'
    0 0 1 0 1
    1 0 1 1 0


    Use the one you need.

    It can help to write the truth table for your 2-input function this way

    B A=0 A=1
    0 1 1
    1 1 0


    So we tie the D0 input HI and apply B' to D1. The result is a 2-input NAND gate.
     
  10. thatoneguy

    AAC Fanatic!

    Feb 19, 2009
    6,357
    718
    Since Panic Mode just posted the answer, I'll fill this in. I did the truth table quick, so unsure if it is correct, but you get the idea.

    [​IMG]

    Function:
    A'C+A'B+AB'C'

    Column 1 Column 2 Column 3 Column 4
    A B C Out
    0 0 0 0
    0 0 1 1
    0 1 0 1
    0 1 1 1
    1 0 0 1
    1 0 1 0
    1 1 0 0
    1 1 1 0



    Here's a blank 8:1 mux
    I0-I7 are Mux Inputs, S2-S0 are selectors

    Column 1 Column 2 Column 3 Column 4 Column 5 Column 6 Column 7 Column 8 Column 9 Column 10 Column 11 Column 12
    S2 S1 S0 I0 I1 I2 I3 I4 I5 I6 I7 Out
    0 0 0 0 0
    0 0 1 1 1
    0 1 0 1 1
    0 1 1 1 1
    1 0 0 1 1
    1 0 1 0 0
    1 1 0 0 0
    1 1 1 0 0


    --ETA: DOH!, I messed it up, but somebody can fix it, I don't want to re-do that table. :(
     
  11. WBahn

    Moderator

    Mar 31, 2012
    17,720
    4,788
    As you say, since panic mode has posted the solution, we can go further.

    It would be nice if we had a simple way to get the mux inputs by just Boolean manipulation. Well, we can. First, expand things into SOP form:

    A'(B + C) + (A' + B + C)'
    A'B + A'C + AB'C'

    Now choose all but one of the variables to be your select lines.

    If A and B are the select lines, then we need something of the form:

    A'B'(?) + A'B(?) + AB'(?) + AB(?)

    This is the function for a 4:1 MUX. Each ? will be replaced with 0, 1, C, or C'

    So expanding our function, we get

    A'B + A'C + AB'C'
    A'B + A'(B+B')C + AB'C'
    A'B + A'BC + A'B'C + AB'C'
    A'B(1+C) + A'B'C + AB'C'
    A'B + A'B'C + AB'C'
    A'B(1) + A'B'(C) + AB'(C') + AB(0)

    So I get

    A'B'(C) + A'B(1) + AB'(C') + AB(0)

    Now panic mode used CB as the two channel selects, so for that choice it would be

    C'B'() + CB'() + C'B() + CB()

    A'B + A'C + AB'C'
    A'B(C+C') + A'(B+B')C + AB'C'
    A'BC + A'BC' + A'B'C + B'C + AB'C'
    AB'C' + A'BC' + (1+A')B'C + A'BC
    AB'C' + A'BC' + B'C + A'BC

    Reordering the factors in each term to match the pattern:

    C'B'(A) + C'B(A') + CB'(1) + CB(A')

    Which is not quite the solution panic mode had.

    Where we differ is CB'A, where his solution has that outputing a 0 and mine has it outputting a 1.

    Looking back at the original expression

    A'(B + C) + (A' + B + C)'

    It appears that panic mode is correct and mine has an error. Looking back, the error is pretty obvious and, upon fixing it, you can eliminate the two lines that follow it. But I'm going to leave finding it as an exercise for the reader (at least for now).
     
Loading...