Combinational Circuits

1
Overview

• Signal Naming
• Decoders
• Encoders
– Binary, priority
• Multiplexers
• Three-state buffers

2
Active States and Bubbles

• Primarily applies to control signals; used to denote when a condition

is active or enabled

• Active State - signal state (0 or 1) that indicates the assertion of

some condition or action
– A signal is asserted when it is in the active state
– A signal is negated when it is in the inactive state
– Active-1 (active high) is when active state is logic 1
– Active-0 (active low) is when active state is logic 0
• Symbol pins without bubbles denote active-1 signals

• Symbol pins with bubbles denote active-0 signals

3
Signal Naming Conventions

• The problem is how to distinguish between active-1 and active-0 signals.

– Use suffix of ‘_0’; (i.e A_0) after signal name
– Use suffix of ‘_LO’ or ‘_L’
– Use suffix of ‘_BAR’
• No matter what you use, BE CONSISTENT!

4
Signal Naming

5
Active Levels For Pins

6
Be Careful!

7
What is a decoder?

• Decoder: A combinational circuit with an n-bit code word applied to

its inputs and m-bit (m=2^n) code word appearing at the outputs.

– Detect which of the 2^n input code words is represented at the inputs
– Produce m outputs, only one of which is asserted

8
1-to-2 (Line) Decoder

9
2-to-4 Decoder

• A 2-to-4 decoder operates according to the following truth table

– The 2-bit input is called S1-S0, and the four outputs are Q0-Q3

S1 S0 Q0 Q1 Q2 Q3
0 0 1 0 0 0
0 1 0 1 0 0
1 0 0 0 1 0
1 1 0 0 0 1

• If the input is the binary number i, then output Qi is uniquely true

– For instance, if the input S1 S0 = 10 (decimal 2), then output Q2 is true,
and Q0, Q1, Q3 are all false

• This circuit “decodes” a binary number into a “one-of-four” code

10
How can you build a 2-to-4 decoder?

• Follow the design procedures from last time! We have a truth table, so
we can write equations for each of the four outputs (Q0-Q3)

S1 S0 Q0 Q1 Q2 Q3
0 0 1 0 0 0
0 1 0 1 0 0
1 0 0 0 1 0
1 1 0 0 0 1

Q0 = S1’ S0’
• Q1to=be
In this case there’s not much S1’simplified.
S0 Here are the equations:
Q2 = S1 S0’
Q3 = S1 S0

11
2-to-4 Decoder

S1 S0 Q0 Q1 Q2 Q3
0 0 1 0 0 0
0 1 0 1 0 0
1 0 0 0 1 0
1 1 0 0 0 1

12
Enable Inputs

• Many devices have an additional enable input, which is used to “activate”

or “deactivate” the device

• For a decoder,

– EN=1 activates the decoder, so it behaves as specified earlier. Exactly

one of the outputs will be 1
– EN=0 “deactivates” the decoder. By convention, that means all of the
decoder’s outputs are 0

• We can include this additional input in the decoder’s truth table:

EN S1 S0 Q0 Q1 Q2 Q3
0 0 0 0 0 0 0
0 0 1 0 0 0 0
0 1 0 0 0 0 0
0 1 1 0 0 0 0
1 0 0 1 0 0 0
1 0 1 0 1 0 0
1 1 0 0 0 1 0
1 1 1 0 0 0 1 13
An aside: abbreviated truth tables

EN S1 S0 Q0 Q1 Q2 Q3
0 0 0 0 0 0 0
• In this table, note that whenever
0 0 1 0 0 0 0
EN=0, the outputs are always 0,
0 1 0 0 0 0 0
regardless of inputs S1 and S0. 0 1 1 0 0 0 0
1 0 0 1 0 0 0
1 0 1 0 1 0 0
1 1 0 0 0 1 0
1 1 1 0 0 0 1

EN S1 S0 Q0 Q1 Q2 Q3
• We can abbreviate the table by 0 x x 0 0 0 0
writing x’s in the input columns 1 0 0 1 0 0 0
for S1 and S0 1 0 1 0 1 0 0
1 1 0 0 0 1 0
1 1 1 0 0 0 1

14
2-to-4 Decoder with Enable

Y0 = (S1’ S0’) EN
Y1 = (S1’ S0) EN
Y2 = (S1 S0’) EN
Y3 = (S1 S0) EN

15
A variation of the standard decoder

• The decoders we’ve seen so far are active-high decoders.

EN S1 S0 Q0 Q1 Q2 Q3
0 x x 0 0 0 0
1 0 0 1 0 0 0
1 0 1 0 1 0 0
1 1 0 0 0 1 0
1 1 1 0 0 0 1

G A
• An active-low decoder is the same thing, butBwithY0 Y1 Y2 Y3
an inverted EN input
and inverted outputs 1 x x 1 1 1 1
0 0 0 0 1 1 1
0 0 1 1 0 1 1
0 1 0 1 1 0 1
0 1 1 1 1 1 0
16
2-to-4 Active-Low Decoder

G A B Y0 Y1 Y2 Y3
1 x x 1 1 1 1 Y0 = (S1 + S0) + G
0 0 0 0 1 1 1 Y1 = (S1 + S0’) + G
0 0 1 1 0 1 1 Y2 = (S1’ + S0) + G
0 1 0 1 1 0 1 Y3 = (S1’ + S0’) + G
0 1 1 1 1 1 0

17
Complete 74x139 Decoder

18
3-to-8 decoder

• Larger decoders are similar. Here is a 3-to-8 decoder

– A truth table (without EN) is below
– Output equations are at the bottom right

• Again, only one output is true for any input combination

S2 S1 S0 Q0 Q1 Q2 Q3 Q4 Q5 Q6 Q7
Q0 = S2’ S1’ S0’
0 0 0 1 0 0 0 0 0 0 0
Q1 = S2’ S1’ S0
0 0 1 0 1 0 0 0 0 0 0
Q2 = S2’ S1 S0’
0 1 0 0 0 1 0 0 0 0 0
Q3 = S2’ S1 S0
0 1 1 0 0 0 1 0 0 0 0
Q4 = S2 S1’ S0’
1 0 0 0 0 0 0 1 0 0 0
Q5 = S2 S1’ S0
1 0 1 0 0 0 0 0 1 0 0
Q6 = S2 S1 S0’
1 1 0 0 0 0 0 0 0 1 0
Q7 = S2 S1 S0
1 1 1 0 0 0 0 0 0 0 1

19
74x138 3-to-8 Active-Low Decoder

20
Cascading - 3-to-8 Active-High Decoder

• You can use enable inputs to string decoders together. Here’s a 3-to-8
decoder constructed from two 2-to-4 decoders:

S2 S1 S0 Q0 Q1 Q2 Q3 Q4 Q5 Q6 Q7
0 0 0 1 0 0 0 0 0 0 0
0 0 1 0 1 0 0 0 0 0 0
0 1 0 0 0 1 0 0 0 0 0
0 1 1 0 0 0 1 0 0 0 0
1 0 0 0 0 0 0 1 0 0 0
1 0 1 0 0 0 0 0 1 0 0
1 1 0 0 0 0 0 0 0 1 0
1 1 1 0 0 0 0 0 0 0 1 21
Cascading - 4-to-16 Active-Low Decoder

22
So what good is a decoder?

• Do the truth table and equations look familiar?

S1 S0 Q0 Q1 Q2 Q3
Q0 = S1’ S0’
0 0 1 0 0 0 Q1 = S1’ S0
0 1 0 1 0 0 Q2 = S1 S0’
1 0 0 0 1 0 Q3 = S1 S0
1 1 0 0 0 1

• Decoders are sometimes called minterm generators

– For each of the input combinations, exactly one output is true

– Each output equation contains all of the input variables
– These properties hold for all sizes of decoders

• Arbitrary functions can be implemented with decoders. If a sum of

minterms equation for a function is given, a decoder (a minterm generator)
is used to implement that function
23
Design example: Addition

• Let’s make a circuit that adds three 1-bit inputs X, Y and Z

• We will need two bits to represent the total; let’s call them C and S, for
“carry” and “sum.” Note that C and S are two separate functions of the
same inputs X, Y and Z

• Here are a truth table and sum-of-minterms equations for C and S

X Y Z C S
0 0 0 0 0
0 0 1 0 1
0 1 0 0 1
C(X,Y,Z) = m(3,5,6,7)
0 + 1 + 1 = 10 0 1 1 1 0
1 0 0 0 1 S(X,Y,Z) = m(1,2,4,7)
1 0 1 1 0
1 1 0 1 0
1 1 1 1 1 1 + 1 + 1 = 11

24
Decoder-based Adder

• 3-to-8 decoders implement C(X,Y,Z) = m(3,5,6,7) and S(X,Y,Z) =

m(1,2,4,7)

25
Active-Low Decoders

• The output equations for an active-low decoder are mysteriously similar,

yet somehow different

Q3’ = (S1 S0)’ = S1’ + S0’

Q2’ = (S1 S0’)’ = S1’ + S0
Q1’ = (S1’ S0)’ = S1 + S0’
Q0’ = (S1’ S0’)’ = S1 + S0

• It turns out that active-low decoders generate maxterms

• So we can use active-low decoders to implement arbitrary functions too,

but as a product of maxterms, i.e., f(x,y,z) = M(4,5,7)

26
Summary of Decoders

• A n-to-2n decoder generates the minterms of an n-variable function

– As such, decoders can be used to implement arbitrary functions
– Later on we’ll see other uses for decoders too

• Some variations of the basic decoder include:

– Adding an enable input
– Using active-low inputs and outputs to generate maxterms

• We also talked about:

– Applying our circuit analysis and design techniques to understand and
work with decoders
– Using block symbols to encapsulate common circuits like decoders
– Building larger decoders from smaller ones

27
Binary Encoders

• An encoder is a digital function that performs the inverse operation

of a decoder

Only one input can have the

value of 1 at any given time

28
Octal-to-Binary Encoder

• This encoder has eight inputs, one for each of the octal digits.

• Three outputs that generate the corresponding binary number.

D7
D6
A2
D5
D4
D3
Encoder A1
D2
A0
D1
D0

29
Octal-to-Binary Encoder

A0= D1 + D3 + D5 + D7,
A2= D4 + D5 + D6 +
D7
A1= D2 + D3 + D6 + D7 30
Priority Encoder

• A priority encoder is a combinational circuit that implements a priority

function

More than one input Code of highest priority

lines are asserted line asserted

31
4-Input Priority Encoder

32
4-Input Priority Encoder

33
4-Input Priority Encoder

34
74x148 8-input priority encoder

35
Cascaded Priority Encoders

36
Multiplexers

• Multiplexers, or muxes, are used to choose between resources

• A real-life example: in the old days before networking, several computers

could share one printer through the use of a switch.

37
Multiplexers

• A n-to-1 multiplexer sends one of n input lines to a single output line

– A multiplexer has two sets of inputs:

• n data input lines
• s=log2n select lines, to pick one of the n data inputs

38
2-to-1 Mux

• The select bit S controls which of the data bits D0-D1

is chosen: S D1 D0 Q
0 0 0 0
– If S=0, then D0 is the output (Q=D0). 0 0 1 1
– If S=1, then D1 is the output (Q=D1). 0 1 0 0
0 1 1 1
1 0 0 0
Q = S’ D0 + S D1
1 0 1 0
1 1 0 1
1 1 1 1

• Here is another kind of abbreviated truth table

S Q
0 D0
– Input variables appear in the output column
1 D1
– This table implies that when S=0, the output Q=D0,
and when S=1 the output Q=D1
– This is a pretty close match to the equation

39
2-to-1 Mux

40
74x157 Quad 2-to-1 Mux

41
4-to-1 Mux

Y= (S1’S0’) I0 + (S1’S0) I1 + (S1S0’) I2 + (S1S0) I3

Decoder

42
4-to-1 Mux

43
Quad 4-to-1 Mux

44
74x151 8-to-1 Multiplexer

45
74x151 8-to-1 Multiplexer

46
Expanding Multiplexers

47
Implementing functions with multiplexers
• Muxes can be used to implement arbitrary functions

• One way to implement a function of n variables is to use an 2^n-to-1 mux:

– For each minterm mi of the function, connect 1 to mux data input Di.
Each data input corresponds to one row of the truth table
– Connect the function’s input variables to the mux select inputs. These
are used to indicate a particular input combination

• For example, let’s look at f(x,y,z) = m(1,2,6,7).

x y z f
0 0 0 0
0 0 1 1
0 1 0 1
0 1 1 0
1 0 0 0
1 0 1 0
1 1 0 1
1 1 1 1 48
A more efficient way
• We can actually implement f(x,y,z) = m(1,2,6,7) with
just a 4-to-1 mux, instead of an 8-to-1 x y z f
0 0 0 0
• Step 1: Find the truth table for the function, and 0 0 1 1
0 1 0 1
group the rows into pairs. Within each pair of rows, 0 1 1 0
x and y are the same, so f is a function of z only. 1 0 0 0
1 0 1 0
– When xy=00, f=z
1 1 0 1
– When xy=01, f=z’
1 1 1 1
– When xy=10, f=0
– When xy=11, f=1

• Step 2: Connect the first two input variables of the

truth table (here, x and y) to the select bits S1 S0
of the 4-to-1 mux.

• Step 3: Connect the equations above for f(z) to the

data inputs D0-D3. 49
Example: multiplexer-based adder

• Let’s implement the adder carry function, C(X,Y,Z), with muxes

• There are three inputs, so we’ll need a 4-to-1 mux

• The basic setup is to connect two of the input variables (usually the first
two in the truth table) to the mux select inputs

X Y Z C
0 0 0 0
0 0 1 0
0 1 0 0
0 1 1 1
1 0 0 0
1 0 1 1
1 1 0 1
With S1=X and S0=Y, then
1 1 1 1
Q=X’Y’D0 + X’YD1 + XY’D2 + XYD3

50
Multiplexer-based carry

• We can set the multiplexer data inputs D0-D3, by fixing X and Y and
finding equations for C in terms of just Z.

X Y Z C
0 0 0 0
When XY=00, C=0
0 0 1 0
0 1 0 0
When XY=01, C=Z
0 1 1 1
1 0 0 0
When XY=10, C=Z
1 0 1 1
1 1 0 1
When XY=11, C=1
1 1 1 1
C = X’ Y’ D0 + X’ Y D1 + X Y’ D2 + X Y D3
= X’ Y’ 0 + X’ Y Z + X Y’ Z + X Y 1
= X’ Y Z + X Y’ Z + XY
= m(3,5,6,7)
51
Multiplexer-based sum

• Here’s the same thing, but for the sum function S(X,Y,Z)

X Y Z S
0 0 0 0
0 0 1 1 When XY=00, S=Z
0 1 0 1
When XY=01, S=Z’
0 1 1 0
1 0 0 1
When XY=10, S=Z’
1 0 1 0
1 1 0 0
When XY=11, S=Z
1 1 1 1
S = X’ Y’ D0 + X’ Y D1 + X Y’ D2 + X Y D3
= X’ Y’ Z + X’ Y Z’ + X Y’ Z’ + X Y Z
= m(1,2,4,7)

52
Summary of Muxes

• A n-to-1 multiplexer routes one of n input lines to a single output line

• Just like decoders,
– Muxes are common enough to be supplied as stand-alone devices for
use in modular designs.
– Muxes can implement arbitrary functions

• We saw some variations of the standard multiplexer:

– Smaller muxes can be combined to produce larger ones
– We can add active-low or active-high enable inputs

• As always, we use truth tables and Boolean algebra to analyze things

53
Three-state Buffers

• Output = LOW, HIGH, or Hi-Z

• Wire can be considered disconnected

• Can tie multiple outputs together if at most one at a time is enabled

• Different flavors:

54
Selecting based on 3-state buffers

55
Sharing a Wire

56
Three-State Drivers – 74x541

57
Driver Application

58
Three-State Transcievers

59
Transciever Application

60