0:00

[MUSIC]

In this lesson, we are going to introduce the definition of some

new components, very useful to implement digital circuits. The

first of them is the multiplexer. The simplest multiplexer

is the 2-to- 1 multiplexer, whose symbol is

this one. It has 2 data inputs, x0 and x1,

a control input "control" and a data output y.

Its working is defined by this table: if the

control input is equal to 0 then the

data output y is connected to the data input x0.

If the control input is equal to 1, then the output

y is connected to the input x1. So

we could say that the main function of a multiplexer is to

implement controllable connections. Here is a

typical example. The input of circuit_C

can be connected to the output of either circuit_A or to the output of

circuit_B in function of the value of a control signal.

If "control" is 1, then, the input of circuit

C is connected to the output of circuit A,

and if the control is 0,

the input of circuit C is connected to the output

of circuit B. More complex multiplexers can be defined.

This is the symbol of an m-bit multiplexer, namely

a 2-to-1 multiplexer. In this case, x0 and

x1 are m-bit vectors.

y is also an m-bit vector that can be equal

2:19

to either x0, when the control bit is equal to 0, or to

x1 when the control bit is equal to 1.

Multiplexers with more data inputs and more control bits can

also be defined, for example, this is a 4-to-1,

1-bit 4-to-1 multiplexer. According to the values

of the two control bits, C1 and C0, the

data output y can be connected to the data input

2:56

x0, x1, x2, or x3, according to

this table. Then, in the same way, we could define

an 8-to-1 multiplexer with three control signals, a 16-to-1

multiplexer with four control signals, and so on.

Now an exercise: try to implement a 2-bit

4-to-1 multiplexer using for that only

1-bit 2-to-1 multiplexers. Thus this

circuit allows to connect to the output vector

y1, y0, either this vector, this one, this one, or

this one, under the control of 2 control bits.

3:50

Here is a solution. As

an example, if c(1) c(0) is

equal to 00, then y(1)

will be connected to x(01)

and y(0) will be connected

to x(00), or another

example, if c(1) c(0) is

equal to 10, then y(1)

is connected to x(21) and

y(0) connected to x(20).

Now a little quiz. Apart of implementing controllable connections,

multiplexers can also be used to implement switching functions

defined by tables. Let us see an example: assume that we want to implement

functions y1 and y0 of three variables,

x2, x1, x0. A straightforward implementation

is this one. Aagain, assume that

x2 x1 x0 is equal to 000;

then y1 will be equal to 0

and y0 will be equal also to 0.

Another example: if we assume

that x2, x1, x0, is equal

to 101, then y1 is equal

to (1 0 1), that is to say

to 1, and y0 with 101 will be

equal to 0, and so on. Furthermore,

in many cases, the circuit can be simplified using

simple and obvious rules. Here are two examples:

in this multiplexer, we see that when

x is equal to 1, the output is equal

to 1, and when x is equal to 0

the output will be equal to 0, so we can see that this output

is just x. Another example:

if in our circuit there are two multiplexer with exactly the

same inputss a b x, a b x,

7:15

In this circuit, here, we have a multiplexer with two

identical data inputs. We can replace

this multiplexer by the constant value 1.

In this one, we see that the output is

equal to 1 when x0 is 1 and is equal to 0 when

x0 is equal to 0; so, we could eliminate

this multiplexer and put here x0.

Here, we could do the same, and

here we have a multiplexer whose both data inputs are equal to 0.

We can substitute this multiplexer by the constant 0.

So, we obtain this simplified circuit.

In the second part of the circuit, here, we can

put x0. This one can be eliminated

because it realizes exactly the same function as the second

one, so we can connect this

input to

the output of the second multiplexer, this one can be eliminated.

and finally here, once again, we can substitute this one by the

value of x0 and so we obtain

this simplified version of the same circuit.

8:58

Now, a last comment about multiplexers: a multiplexer-based

implementation of a switching function F, like

this one, is based on this simple decomposition:

that says that f(x0,x1) =

Not(x0)·f(0, x1, ··· ) +

x0·f(1, x1, ··· ).

It is only a matter of

checking that if you substitute, here,

x0 by 0 or by 1, in both cases you

obtain an equality. Then subfunctions

f(0, x1, ···) and f(1, x1, ···)

are functions of one variable less (of n-1 variables).

So, we could say that we with one 2-to-1

multiplexer we have extracted a variable,

the variable x0 in this example. So, by iteratively

applying this rule, we will eventually get either

simple variables, or already computed subfunctions.

Now, a second type of

component. We already know that "read only memory" blocks can

be used to implement switching functions defined by tables.

Nevertheless, generally, this is a very inefficient method.

11:00

As an example, assume that six input LUTS

(look up tables) are available. Then we could

iteratively apply, once again, this

rule and extract an input variable using for

that 2-to-1 multiplexer, and we

extract variables until all the obtained subfunctions

are functions of at most six variables that can be

implemented by a six-input look up table. Let us see

an example. to implement an 8-variable function,

you just need three 2-to-1 multiplexers that

allowed to extract x6 and x7, so that

the sub-functions that enter

those multiplexer are functions of at most 6 variables,

12:36

of 1, 2, 3, 4, 5, 6 variables. So, it could

also be implemented by a simple

look up table, so that this circuit is obtained:

it allows to synthesize, to implement, any 8-variable

function. A last comment: the preceding example is based

on an iterative application of the following rule: any function

f(x0, x1, x2, ···) can be the

decomposed under the following form.:

not(x0)·not(x1)·f(0, 0, x2, x3, ···)

13:27

plus

x0·not(x1)·f(1, 0, x2, x3, ···)

plus

not(x0)·x1·f(0, 1, x2, x3, ···)

plus x0·x1·f(1, 1, x2, x3, ···).

We have extracted

two variables x0 and x1 and the subfunctions

f(0, 0, x2, x3, ···), f(0, 1, x2, x3, ···),

f(1, 0, x2, x3, ···), f(1, 1, xx2, x3, ···)

are functions of n - 2 variables.

So, once again, by an iterative

application of this simple decomposition rule, we

eventually obtain constant values, simple variables,

or already available sub-functions, and this

extraction can be done with this circuit.

Now we propose you a quiz.

Other types of components: the planes. AND-planes and

OR-planes are sometimes used to implement switching functions.

An (n, p) AND-plane implements p n-variable

functions Yj, each of them being a product

of literals, that is to say that

Yj is a product of literals

Wj0, Wj1, and so on, where every

W can be a variable, an inverted

variable or 1. That means

that not all variable are present within

this product. Here is the symbol with p products

of n variable. Those planes can be predefined,

15:47

predefined when the corresponding integrated circuit is manufactured,

or can be defined by the user, in which case, there are

called "field programmable devices".

OR-planes can also be defined. In this case

a (p, s) OR-plane implements

s p-variable functions, Zj;

s functions of p variables where

each function is a Boolean sum of variables of

this form. That means that this expression, every W,

can be either a variable (one of the

input variables) or zero. Once again, those planes can be predefined

or can be field programmable. Obviously,

any set of Boolean functions that can be expressed as Boolean

sums of at most p different product of at

most n literals can be implemented

17:05

in this way. That means, with an AND-plane that

generate all those products (here there are p

products) and a (p, s) OR-plane that

computes the output functions. According to

the technology or to the manufacturer those

AND - OR circuits have different names such

17:34

as PAL (programmable array of logic), PLA (programmable logic array),

PLD (programmable logic device) and others.

The last type of useful and very common

component is the address decoder. An n-to-2**n

address decoder has n inputs and 2**n outputs,

and its function can be defined as follows:

if the n inputs Xn-1, Xn-2, and

so on, represent the number I expressed

in the binary numeration system, then

Yi = 1, and all the other outputs

are equal to 0. As an example,

here we have the symbol of a 2-to-4 address decoder,

and here is the table that defines its working.

You can see that if the address x1, x0 is 00, then y0 = 1

and the other outputs are equal to 0. If - another example - the address

is 10 (that means 2 in decimal) then

y2 = 1 and the other outputs are equal to 0

A first comment: an address decoder

implements the same function as an AND-plane

with n inputs and 2 to the n outputs,

an AND-plane that generate all the minterms,

all the expression of this type, in which all variables

appear under normal or under inverted form.

19:44

Then, if we connect this address decoder to an OR-plane,

the obtained circuit is equivalent to a read only memory block.

Here's an example: consider this circuit; it is equivalent

to this read only memory memory. As a matter of

fact, if, for example, x1 x0 = 2

(address 2) that means 10,

then this product is equal

to 1 but the other ones are equal to 0. Then at the

output we have that z2 = 1 because here there is a connection;

z1 = 0 because its inputs are

connected to a product equal to 0,

and z0 = 0 because this connection is

to a product equal to zero, so that

the result is 1, 0, 0, exactly what we have

defined within this ROM memory at address 2.

21:07

The other application of address decoders is the

control of buffers. Let us see an example.

With this 2-to-4 decoders, and with four 3-state buffer,

this signal z can be connected to either y0, y1, y2, or y3.

21:33

If, for example, x1 x0 = 11

(address 3) then only this

product is equal to 1 so that these 3-state

buffer outputs are equal to high impedance state,

while this output is

equal to y3. So, we have connected y3 to z.

22:06

Thus, we can implement a circuit in which the inputs

of some circuit E can be connected to the outputs

of either circuit

A, B, C, or D, under the control of two

address bits x1 and x0. As an example,

if x1 x0 = 01, for example

22:39

(1 in decimal) then this product is equal

to 1, the other ones are equal to 0 so that

this connection is in high impedance state,

this also, and this one also, and this

23:46

The concept of AND and OR planes have been introduced, once

again, in order to implement switching function or Boolean functions,

and finally, address decoders and 3-state buffers

have been used to implement buses.