EECC341 - ShaabanEECC341 - Shaaban#1 Lec # 10 Winter 2001 1-15-2002Implementing n-variable Functions Using2n-to-1 Multiplexers• Any n-variable logic function, in canonical sum-of-minterms form can be implemented using a single 2n-to-1multiplexer:– The n input variables are connected to the muxselect lines.– For each mux data input line Ii ( 0 ≤≤ i ≤ ≤ 2n - 1):• Connect 1 to mux input line Ii if i is a minterm of thefunction.• Otherwise, connect 0 to mux input line Ii (because i isnot a minterm of the function thus the selected inputshould be 0).EECC341 - ShaabanEECC341 - Shaaban#2 Lec # 10 Winter 2001 1-15-2002Example: 3-variable Function Using 8-to-1 mux• Implement the function F(X,Y,Z) = ΣΣ(1,3,5,6) usingan 8-to-1 mux.– Connect the input variables X, Y, Z to mux select lines.– Mux data input lines 1, 3, 5, 6 that correspond to functionminterms are connected to 1.– The remaining mux data input lines 0, 2, 4, 7 are connected to 0.muxX Y Z0123456701010110 FMux Select LinesMux DataInput LinesEECC341 - ShaabanEECC341 - Shaaban#3 Lec # 10 Winter 2001 1-15-2002Implementing n-variable Functions Using 2n-1-to-1Multiplexers• Any n-variable logic function can be implemented using a smaller 2n-1-to-1multiplexer and a single inverter (e.g 4-to-1 mux to implement 3 variablefunctions) as follows:– Express function in canonical sum-of-minterms form.– Choose n-1 variables as inputs to mux select lines.– Construct the truth table for the function, but grouping inputs byselection line values (i.e select lines as most significant inputs).– Determine multiplexer input line i values by comparing the remaininginput variable and the function F for the corresponding selection linesvalue i:• Four possible mux input line i values:– Connect to 0 if the function is 0 for both values of remaining variable.– Connect to 1 if the function is 1 for both values of remaining variable.– Connect to remaining variable if function is equal to the remainingvariable.– Connect to the inverted remaining variable if the function is equal tothe remaining variable inverted.EECC341 - ShaabanEECC341 - Shaaban#4 Lec # 10 Winter 2001 1-15-2002• Implement the function F(X,Y,Z) = ΣΣ(0,1,3,6) using a single 4-to-1mux and an inverter.– We choose the two most significant inputs X, Y as mux select lines.– Construct truth table:Example: 3-variable Function Using 4-to-1 muxX Y Z F0 0 0 10 0 1 10 1 0 00 1 1 11 0 0 01 0 1 01 1 0 11 1 1 0MuxInput i1Z0Z’Select LinesValue i 0123Select LinesmuxX Y012310 FZ• We Determine multiplexer input line i values by comparing the remaining inputvariable Z and the function F for the corresponding selection lines value i:– when XY=00 the function F=1 (for both Z=0, Z=1) thus mux input0 = 1– when XY=01 the function F=Z thus mux input1 = Z– when XY=10 the function F=0 (for both Z=0, Z=1) thus mux input2 = 0– when XY=11 the function F=Z’ thus mux input3 = Z’Mux Select LinesMux DataInput LinesEECC341 - ShaabanEECC341 - Shaaban#5 Lec # 10 Winter 2001 1-15-2002Example: 4-variable Function Using 8-to-1 mux• Implement the function F(x1,x2,x3,x4) = ∑∑(0,1,2,3,4,9,13,14,15) usinga single 74151A 8-to-1 mux and an inverter.– We choose the three most significant inputs x1,x2,x3 as mux select lines.– Construct truth table.– Determine multiplexer Data input line Di