Multiplexers decoders and Boolean function implementation

Select data or select a position

A multiplexer (MUX) selects one data input and copies it to an output. A decoder translates an input code into an asserted output position. Both are combinational in this lesson: outputs are evaluated after signals settle, with no stored state. Understanding the input/output contract is more reliable than recognizing a box symbol.

Prerequisites: binary indexing, Boolean gates and minterms. Goals: write MUX equations, map a truth table onto data inputs, use active-high or active-low decoder outputs correctly, and count a simple MUX tree. We assume one-bit data unless a width is explicitly stated. Timing, hazards, priority encoders, tristate buses and sequential circuits are outside this lesson.

A two-to-one multiplexer

A 2:1 MUX has data inputs D_0,D_1, select bit S and output Y. Our convention is S=0 selects D_0; S=1 selects D_1. Therefore Y=S′D_0+SD_1. Here + is Boolean OR and juxtaposition is AND. When S=0, the first term becomes D_0 and the second vanishes; when S=1, the reverse happens.

S	Selected input	Y
0	D_0	D_0
1	D_1	D_1

A select bit chooses a source; it is not automatically the output's value. If D_0=1,D_1=0, then Y=S′, not S. If both data inputs are 1, Y=1 for either select. If both are 0, Y=0.

Worked example 1: use a MUX to implement F(A,B)=A′B+AB′, the XOR function. Set S=A, D_0=B and D_1=B′. For A=0, output is B; for A=1, output is B′. Checking B=0 and B=1 in both cases gives outputs 0,1,1,0 in row order 00,01,10,11. An inverter supplies B′ unless the complemented signal is already available.

Four-to-one selection and bit significance

A 4:1 MUX has selects S_1,S_0 and data D_0…D_3. Treat S_1 as the most significant select bit. Select codes 00,01,10,11 choose D_0,D_1,D_2,D_3 respectively. Its equation is

Y=S_1′S_0′D_0 + S_1′S_0D_1 + S_1S_0′D_2 + S_1S_0D_3.

Exactly one select minterm is 1 for a given code, so only the chosen data term survives. In general, a fully populated 2^k:1 MUX uses k binary select bits. The label 4:1 counts data choices and outputs; it does not mean four select bits. Swapping select significance changes the data mapping unless you also reorder the inputs.

Worked example 2: S_1S_0=10 and (D_0,D_1,D_2,D_3)=(1,0,1,0). The selected input is D_2, so Y=1. It is not D_1 merely because the leftmost written select bit is 1.

Implement a truth table with a MUX

For a function of k variables, connect those variables to the k selects of a 2^k:1 MUX in a declared order. Set each data input to the function's constant truth-table output on that row. This realizes any Boolean function of those k inputs, but the data count grows exponentially.

A smaller MUX can leave one variable in the data inputs. This is repeated use of the identity F=A′F|_(A=0)+AF|_(A=1), often called Shannon expansion. The restricted functions are obtained by fixing A, not by taking a derivative. At A=0 only the first restriction is selected; at A=1 only the second is selected.

Worked example 3: implement F(A,B,C)=Σm(1,2,6,7) with a 4:1 MUX and selects S_1=A,S_0=B. Examine C=0 and C=1 for each fixed AB:

AB	F when C=0	F when C=1	Connect data input to
00	0	1	D_0=C
01	1	0	D_1=C′
10	0	0	D_2=0
11	1	1	D_3=1

For instance AB=01 visits rows 010 and 011, whose outputs are 1 and 0; that is C′. This pairwise procedure prevents guessing from the minterm list. Verify all eight rows after connecting the MUX. Use an inverter for C′ if needed; the MUX alone does not create an available complemented input automatically.

Decoder outputs and enable

An active-high 2-to-4 decoder has inputs A,B, active-high enable E and outputs Y_0…Y_3. With E=1 it asserts exactly the output indexed by AB; with E=0 all outputs are 0. The equations are Y_0=EA′B′, Y_1=EA′B, Y_2=EAB′, Y_3=EAB. “Asserted” means active, which here is logic 1.

E	AB	Y_0 Y_1 Y_2 Y_3
0	any	0 0 0 0
1	00	1 0 0 0
1	01	0 1 0 0
1	10	0 0 1 0
1	11	0 0 0 1

The output list is in index order Y_0 through Y_3; it is not a binary numeral with Y_0 as its most significant value. With E=1, these outputs are all minterms of A,B. An enabled active-high 3-to-8 decoder similarly produces the eight minterms of A,B,C, with A declared most significant.

Worked example 4: to implement G=Σm(0,3,5,6), OR the active-high outputs Y_0,Y_3,Y_5,Y_6 of an enabled 3-to-8 decoder. On a listed row its corresponding output is 1; on any other row all four chosen outputs are 0. A single decoder can feed different OR combinations for multiple functions, subject to physical constraints not modeled here.

Active-low outputs change the combining gate

Not all decoders assert a high voltage. An active-low output is asserted at logic 0. Suppose an enabled decoder exposes Z_i=m_i′, the complement of each minterm. Then the same G is (Z_0Z_3Z_5Z_6)′ by De Morgan, so use a NAND of those four outputs, not their OR. On a selected row one chosen Z is 0, making the NAND 1; otherwise all four are 1, making it 0.

Read a component's enable and output polarities before applying this rule. The TI SN74HC138, for example, has active-low outputs and more than one enable input; it is not the single-active-high-enable abstraction above. This lesson's circuit calculations use their explicitly declared truth tables, not an unstated commercial pin convention.

A decoder with equations Y_i=E m_i also behaves as a one-to-many demultiplexer if E is the data bit and the address inputs choose its destination. A MUX selects among data sources; a demultiplexer directs one data source to a selected output. Neither is a priority encoder, which solves a different input contract.

Build larger selectors and check your work

An 8:1 one-bit MUX can be built from seven 2:1 MUXes: four in the first level select adjacent pairs using S_0, two in the second select pairs of first-level outputs using S_1, and one in the last level uses S_2. The path has three MUX levels. Seven is a component count, not seven levels. No numerical delay follows without a component-delay model.

For an eight-bit-wide 8:1 bus selector, repeat this network for each output bit while sharing select signals: 8×7=56 one-bit 2:1 MUXes in this construction. Width and number of selectable words are different quantities.

Key points: declare select significance; distinguish data bits from selects; derive every data connection from restricted truth-table rows; check enable and output polarity; distinguish gate count from path depth. A correct steady-state truth table does not guarantee absence of glitches when selects change.

Original practice

These six single-correct MCQs are original learning questions, not previous-year questions. Choose exactly one option.

C01. For a 2:1 MUX, S=0 selects D_0 and S=1 selects D_1. With D_0=1 and D_1=0, what is Y?

A. S B. 0 C. 1 D. S′

Answer: D

A is incorrect: at S=0 the output is 1, not 0.

B is incorrect: choosing D_0 produces 1.

C is incorrect: choosing D_1 produces 0.

D is correct: Y=S′×1+S×0=S′.

C02. A 4:1 MUX uses S_1 as the most significant select bit. If S_1S_0=10, which data input is selected?

A. D_0 B. D_1 C. D_2 D. D_3

Answer: C

A is incorrect: D_0 corresponds to 00.

B is incorrect: D_1 corresponds to 01.

C is correct: binary 10 is index 2.

D is incorrect: D_3 corresponds to 11.

C03. Implement F(A,B,C)=Σm(1,2,6,7) with a 4:1 MUX whose selects are S_1=A,S_0=B. Which tuple (D_0,D_1,D_2,D_3) is correct?

A. (C,C′,0,1) B. (C′,C,0,1) C. (C,0,C′,1) D. (C,C′,1,0)

Answer: A

A is correct: restricted output pairs for AB=00,01,10,11 are 01,10,00,11, giving C,C′,0,1.

B is incorrect: it reverses both AB=00 and AB=01 output pairs; for row 000 it wrongly gives 1.

C is incorrect: it misplaces the C′ connection; row 010 should give 1, not 0.

D is incorrect: it swaps constant 0 and 1; row 100 should give 0, not 1.

C04. An active-high 2-to-4 decoder has active-high enable E and outputs in order Y_0,Y_1,Y_2,Y_3. With E=1 and AB=10, what is the output list?

A. 1,0,0,0 B. 0,0,1,0 C. 0,1,0,0 D. 0,0,0,0

Answer: B

A is incorrect: this asserts index 0, corresponding to AB=00.

B is correct: AB=10 selects index 2, so only Y_2 is 1.

C is incorrect: this asserts index 1, corresponding to AB=01.

D is incorrect: all-zero outputs describe disabled operation here, but E=1.

C05. How many one-bit 2:1 MUXes and how many MUX levels are used in the balanced tree construction of one one-bit 8:1 MUX?

A. 8 MUXes, 3 levels B. 7 MUXes, 7 levels C. 7 MUXes, 3 levels D. 3 MUXes, 7 levels

Answer: C

A is incorrect: the tree contains 4+2+1=7 components, not eight.

B is incorrect: seven counts all components, while an input-to-output path crosses only three.

C is correct: first, second and third levels contain 4,2,1 MUXes respectively.

D is incorrect: three counts levels, not enough components to combine eight arbitrary inputs.

C06. An enabled active-low decoder provides Z_i=m_i′. How should F=m_1+m_4 be formed from Z_1 and Z_4?

A. Z_1+Z_4 B. Z_1Z_4 C. (Z_1+Z_4)′ D. (Z_1Z_4)′

Answer: D

A is incorrect: at any other row both Z values are 1, so OR wrongly gives 1.

B is incorrect: AND gives the complement of the required function, not the function.

C is incorrect: by De Morgan this is m_1m_4, which is always 0 because distinct minterms cannot both be 1.

D is correct: NAND gives Z_1′+Z_4′=m_1+m_4.

Scope and sources

This is one bounded Digital Logic lesson, not complete GATE CS coverage. The official syllabus establishes relevance only; the derivations, examples and practice are original. Technical references were used to check representation and circuit conventions, not to reproduce their exercises.

• Official GATE 2027 CS syllabus Section 2
• MIT Computation Structures combinational logic
• Texas Instruments SN74HC138 product and data sheet

Sources checked 14 October 2026.