1.7 Multiplexer Trees

A 2ⁿ-input multiplexer can be implemented by a two-level network of 2^n/2-input multiplexer modules as shown in Figure 1.41. The first level has 2^n/2 multiplex­ers, and n/2 of the select inputs are used to select a group of 2^n/2 from the 2ⁿ data inputs (one per multiplexer module). The second level uses the other n/2 select inputs to select one data input from the group already selected in the first level.

A high-level description of the network is as follows. The select input s is decomposed into two parts s_L and s_R so that

s = s_L  2^n/2 + s_R

The vector s_R is applied to the first level and the vector s_L to the second. Consequently, the outputs of the first level are

j = 0, 1, … , 2^n/2 - 1

and the output of the whole multiplexer is

Fig. 1.41 - Multiplexer tree.

The enable input E is applied to the multiplexer in the second level. A functional description of a two-level multiplexer tree is

where x is divided into n/2 subvectors of n/2 bits each, so that

(Remember that the three arguments of the MUX function are the data vector, the select vector, and the enable input.)

The network shown in Figure 1.42 implements a 16-input multiplexer because

and

where

The multiplexer-tree scheme can be generalized to the case in which there are r levels. If n=rk, the network uses (2ⁿ-1)/(2^k-1) modules. This result is derived in a fashion similar to that for decoder trees.

Demultiplexer Networks

Since a demultiplexer is a decoder with a data input, a large demultiplexer can be implemented in the same ways as large decoders.

Encoder Networks

A 2ⁿ-input encoder can be implemented by a network of 2^k-input encoders and some other modules. We assume in the following discussion that n = 2k.

Fig. 1.42 - 16-input multiplexor implementation.

1.8 Demultiplexers (Distributors)

A demultiplexer can be used to distribute input information d to various outputs. It represents an extension of the 1-out-of-n decoder. The addressed output does not go to "one", but assumes the value of input variable d. Figure 1.43 illustrates the principle by means of switches, Fig. 1.44. shows its implemen­tation using gates. If we make d = const = 1, the multiplexer operates as a 1-out-of-n decoder. Commonly used demultiplexers are listed in Fig. 1.45

Fig. 1.43 - Basic mode of operation. Fig. 1.44 - Demultiplexer circuit.

Outputs	TTL	ECL	CMOS
16	74LS154		4514
8	74LS138	10162	74HC138
8	74ALS5381		40H.138
2 x 4	74LS139	10172	74HC139
2x4	74ALS5391		4555

¹ Output polarity reversible

Fig. 1.45 - Integrated demultiplexers.

A 2ⁿ -output demultiplexer is a combinational system with n control (select) inputs s=(s_{n-1, . . . ,} s₀), one data input x, a module-enable input E, and 2ⁿ data outputs y = ( , . . . , y₀) (Figure 1.46.). It performs the inverse operation of the multiplexer: the input is routed to the output selected by the select variables. All other outputs are zero.

Fig. 1.46 - n-input demultiplexor.

A high-level description is

yi=	x if i=s and E= 1
	0 if i s and E=0

where

and

In the description of systems this module is denoted as

y = DMX(x,s,E)

For example, DMX(1, (1,0,1),1)=(0,0,1,0,0,0,0,0).

The switching expressions representing the outputs are

These expressions are similar to those of the decoder, the difference being the additional data input in the demultiplexer case. Consequently, a demultiplexer can be used as a decoder. The use of a decoder as a demultiplexer is also possible provided that the enable input of the decoder is used as the data input of the demultiplexer. Of course, in this last situation the resulting demultiplexer would not have an enable input. A vector demultiplexer can be defined in a manner similar to a vector multiplexer.

The basic use of a demultiplexer is to transmit the input to one out of several outputs under control of the select inputs.