University of Gondar

Institute IoT
of Technology
Digital Logic Design
(CoEng3092)

Lecture-04: Combinational Logic Circuits

By Kindu T.
 Objectives
 Analyze basic combinational logic circuits
 Write the Boolean output expression for any combinational logic circuit.
 Develop a truth table from the output expression for a combinational logic
circuit.
 Design a combinational logic circuit for a given boolean output expression
 Design a combinational logic circuit for a given truth table
 Simplify a combinational logic circuit to its minimum form

2
 What we have covered in the last
 Lectures?
In Lecture 01 and 02
 We learned about binary numbers and binary codes that represent discrete
quantities of information.
 The binary variables are represented physically by electric voltages or
some other type of signal.
 The signals can be manipulated in digital logic gates to perform
required functions
 In Lecture 03, we learned
 Basic logic gates and their operation
 Boolean algebra as a way to express logic functions algebraically.
 How to simplify Boolean functions to achieve economical (simpler) gate
implementations. 3
 Purpose of this lecture
 Lecture 04 => Current lecture
 The purpose of this lecture is to use the knowledge acquired in previous
lectures to formulate systematic analysis and design procedures for
combinational circuits.
 We will address those tasks:
 Analyze the behavior of a given logic circuit,
 Synthesize a circuit that will have a given behavior,

4
 Introduction to Combinational Logic
 Circuits
The digital system consists of two types of circuits, namely
I. Combinational circuits
II. Sequential circuits
 Combinational circuit consists of logic gates whose output at any time is
determined from the present combination of inputs.
 The logic gate is the most basic building block of combinational logic.
 Outputs at any time are determined from the present combination of inputs.
 Performs operation specified by a set of Boolean functions.
 The logical function performed by a combinational circuit is fully defined by a set of
Boolean expressions.
 Sequential circuits employ storage elements in addition to logic gates.
 Their outputs are a function of the inputs and the state of the storage elements.
 The output depend not only on present values of inputs, but also on past inputs.
 Circuit behavior must be specified by a time sequence of inputs and internal states. 5
 Introduction to Combinational Logic
 A Circuits
combinational circuit consists of input variables, logic gates, and output
variables.
 The logic gates accept signals from inputs and output signals are generated according to the
logic circuits employed in it.

Block diagram of combinational circuit

 For n input variables, there are 2n possible combinations of the binary inputs.
 For each possible input combination, there is one possible value for each output variable.
 A combinational circuit can be specified
1. With a truth table that lists the output values for each combination of input variables.
2. By m Boolean functions, one for each output variable.
 Each output function is expressed in terms of the n input variables 6
 Introduction to Combinational Logic
 Circuits
Classification of Combinational Logic

7
 Combinational Circuit Design
 Procedure
The design of combinational circuits starts from the specification of the design
objective and culminates in a logic circuit diagram or a set of Boolean functions
from which the logic diagram can be obtained.
 Steps in Designing Combinational Circuits
1. State the given problem completely and exactly according to the
specification
2. Interpret the problem and determine the available input variables and required
output variables
3. Assign a letter symbol to each input and output variables
4. Design the truth table that defines the required relations between inputs and
outputs
5. Obtain the simplified Boolean function for each output 8
 Combinational Circuit Design
Procedure
 Practical design must consider such constraints:
 The number of gates
 Number of inputs to a gate
 Propagation time of the signal through the gates
 Number of interconnections
 Limitations of the driving capability of each gate
 ...

9
 Designing a Combinational Circuit
 Example 1: A committee of three individuals decide issues for an organization.
Each individual votes either yes or no for each proposal that arises. A proposal is
passed if it receives at least two yes votes. Design a circuit that determines
whether a proposal passes.
 What if the committee are four?

10
 Designing a Combinational Circuit
 Example 2: Design a Combinational Circuit with three inputs and one output.
The output is 1 when the binary value of inputs is greater then 3.

11
 Designing a Combinational Circuit
 Example 3: Realize the following function

12
 BCD to 7-segment display decoder
 Example 4: Design BCD to 7-segment decoder circuit that used to convert the
input BCD into a form suitable for the 7-segment display.
 A 7-segment display is normally used for displaying any one of the decimal digits, 0—9.
 A BCD-to-seven segment decoder accepts a decimal digit in BCD and generates the
corresponding seven-segment code.
 It has four input lines (A, B, C and D) and 7 output lines (a, b, c, d, e, f and g)

13
BCD to 7-segment display decoder ...

14
BCD to 7-segment display decoder ...

15
BCD to 7-segment display decoder ...

16
BCD to 7-segment display decoder ...

17
BCD to 7-segment display decoder ...

18
BCD to 7-segment display decoder ...

19
BCD to 7-segment display decoder ...

20
BCD to 7-segment display decoder ...

21
BCD to 7-segment display decoder ...

22
BCD to 7-segment display decoder Logic Circuit
 Code Conversion
 A code converter is a logic circuit that changes data presented in one type of
binary code to another form of binary code.

Input: supply the bit Output: generate

Combinational the corresponding
combination of
elements specified by Circuit bit combination of
code A code B.

Block diagram to convert from binary code A to binary code B

23
 Code Conversion
 Design the logic circuit for each of the following code converters.
1. Binary-to-Gray code
2. Gray-to-Binary code
3. BCD-to-Excess-3
4. Excess-3-to-BCD
5. Binary-to-BCD
6. BCD-to-binary
7. Gray-to-BCD
8. BCD-to-Gray
9. Decimal to BCD converter

24
 Adder
 The Basic operation in digital computer is binary addition.
 The circuit which perform the addition of binary bits are called as Adder.
 The logic circuit that performs the addition of two bits is called a half adder.
 One that performs the addition of three bits (two significant bits and a
previous carry) is a full adder.
 Two half adders can be employed to implement a full adder.

 Rules for two bit addition

 0+0= 0
 0+1= 1
 1+0= 1
 1 + 1 = 10 (Carry 1 to the next significant bit)
25
 The Half-Adder
 The half-adder (HA) accepts two binary digits on its inputs and produces two
binary digits on its outputs—a sum bit and a carry bit.

Logic symbol for a half-adder

Half-adder logic diagram

26
 The Full-Adder
 The full-adder(FA) accepts two input bits and an input carry and generates a sum
output and an output carry.

Logic symbol for a full-adder

Full-adder truth table

27
 The Full-Adder

logic circuit for a full-

adder

Arrangement of two half-adders to form a full- 28

 Parallel Binary Adders
 A single FA is capable of adding two 1-bit numbers and an input carry.
 To add binary numbers with more than one bit, you must use additional FA.
 Two or more full-adders can be connected to form parallel binary adders.
 To add two binary numbers, a full-adder (FA) is required for each bit in the
numbers.
 For 2-bit numbers, two FA are needed
 For 4-bit numbers, four FA are used
 For 8-bit numbers, two 4-bit adders or eight FA are used

29
Block diagram of a basic 2-bit parallel adder using two full-adders
 Parallel Binary Adders
 Example: Determine the sum generated by the 3-bit parallel adder in Figure 6–8
and show the intermediate carries when the binary numbers 101 and 011 are being
added.

30
 Parallel Binary Adders
 Four-Bit Parallel Adders
 A basic 4-bit parallel adder is implemented with four full-adder stages

31
 Parallel Binary Adders
 Adder Expansion
 The 4-bit parallel adder can be expanded to handle the addition of two 8-bit numbers by
using two 4-bit adders.

32
 Ripple Carry and Look-Ahead Carry
 Parallel Adders
adders can be placed into two categories based on the way in which
internal carries from stage to stage are handled.
1. Ripple carry adder
2. Look-ahead carry adder
 Externally, both types of adders are the same in terms of inputs and outputs.
 The difference is the speed at which they can add numbers.
 The look ahead carry adder is much faster than the ripple carry adder.

33
 Ripple Carry Adders
 A ripple carry adder is one in which the carry output of each full-adder is connected to
the carry input of the next higher-order stage (a stage is one full-adder).
 The sum and the output carry of any stage cannot be produced until the input carry
occurs; this causes a time delay in the addition process.

A 4-bit parallel ripple carry adder showing “worst-case” carry propagation delays. 34
 Look-Ahead Carry Adders
 The Look-Ahead Carry Adder is one of the methods of speeding up the addition process by
eliminating the ripple carry delay.
 The look-ahead carry adder anticipates the output carry of each stage, and based on the
inputs, produces the output carry by either carry generation or carry propagation.
 Carry generation occurs when an output carry is produced (generated) internally by the
full-adder.
 A carry is generated only when both input bits are 1s.
 The generated carry is expressed as the AND function of the two input bits, A and B.
Cg = AB
 Carry propagation occurs when the input carry is rippled to become the output carry.
 An input carry may be propagated by the FA when either or both of the input bits are 1s.
 The propagated carry, Cp, is expressed as the OR function of the input bits.
Cp = A + B
35
 Look-Ahead Carry Adders
 The conditions for carry generation and carry propagation
 The three arrowheads symbolize ripple (propagation).

Illustration of conditions for carry generation and carry propagation 36

 Look-Ahead Carry Adders
 The output carry of a FA can be expressed in terms of both the generated carry (Cg) and the
propagated carry (Cp).
 The output carry (Cout) is a 1 if Cg is a 1 OR if Cp is a 1 AND the input carry (Cin) is a 1.
 This relationship is expressed as
Cout = Cg + Cp Cin

37
Carry generation and carry propagation in terms of the input bits to a 4-bit adder
 Look-Ahead Carry Adders
 We can now develop expressions for the output carry, Cout, of each full-adder stage for the
4-bit example.

38
 Look-Ahead Carry Adders
 The output carry for each FA stage is dependent only on the initial input carry (Cin1), the Cg
and Cp functions of that stage, and the Cg and Cp functions of the preceding stages.

39
 Binary Subtractor
 Design a combinational logic circuit that performs arithmetic operation for
subtraction
 Half Subtractor
 Full Subtractor
 4-bit Subtractor
 Design Adder-Subtractor logic Circuit that performs arithmetic operation for
addition and subtraction of two 4-bit numbers.

40
 Decoders
 Discrete quantities of information are represented in digital systems by binary codes.
 A binary code of n bits is capable of representing up to 2n distinct elements of coded
information.
 The name Decoder means to translate or decode coded information from one format
into another.
 A binary decoder is a combinational circuit that converts binary information from n
input lines to a maximum of 2n unique output lines.
 If the n-bit coded information has unused combinations, the decoder may have fewer than
2n outputs.
 The purpose is to generate the 2n (or fewer) minterms of n input variables.
 Each combination of inputs will assert a unique output.
 The decoders presented here are called n-to-m-line decoders, where m ≤ 2n

41
 Decoders
 Only one output is asserted at a time, and each output corresponds to one valuation of
the inputs.
 The decoder also has an enable input, En, that is used to disable the outputs;
 If En = 0, then none of the decoder outputs is asserted.
 If En = 1, the valuation of wn−1 · · · w1w0 determines which of the outputs is asserted.
 An n-bit binary code in which exactly one of the bits is set to 1 at a time is referred to as
one-hot.
 The single bit that is set to 1 is deemed to be “hot.”
 The outputs of a binary decoder are one-hot encoded

An n-to-2n binary decoder 42

 Decoders
 Example: 2-bit binary number
 Only one lamp turn on at a time

1
x1 0 0
Binary
0 0
x0 Decoder
0

43
 Decoders
 Example: 2-bit binary number
 Only one lamp turn on at a time

0
x1 0 1
Binary
1 0
x0 Decoder
0

44
 Decoders
 Example: 2-bit binary number
 Only one lamp turn on at a time

0
x1 1 0
Binary
0 1
x0 Decoder
0

45
 Decoders
 Example: 2-bit binary number
 Only one lamp turn on at a time

0
x1 1 0
Binary
1 0
x0 Decoder
1

46
 Decoders
 2-to-4 Line Decoder

I1 I 0 Y0 Y1 Y2 Y3 Y3
0 0 1 0 0 0 Y0 I1 I 0
Y1 I1 I 0 Y2
0 1 0 1 0 0
1 0 0 0 1 0 Y2 I1 I 0 Y1
1 1 0 0 0 1 Y3 I1 I 0
Y0

y3
I1 I1
2-to-4 y2 I0
Decoder y
I0 1
y0
47
 Decoders
 2-to-4 Line Decoder
 With enable (En) control
En I1 I0 Y0 Y1 Y2 Y3
0 x x 0 0 0 0 Y0 EnI1 I 0
1 0 0 1 0 0 0 Y1 EnI1 I 0
1 0 1 0 1 0 0
Y2 EnI1 I 0
1 1 0 0 0 1 0
Y3 EnI1 I 0
1 1 1 0 0 0 1

I1 y3
I0 2-to-4 y2
Decoder y
En 1
y0 48
 Decoders
 3-to-8 Line Decoder

I2 I1 I0 Y0 Y1 Y2 Y3 Y4 Y5 Y6 Y7
Y7
0 0 0 1 0 0 0 0 0 0 0
Y6
I2 Y5 0 0 1 0 1 0 0 0 0 0 0
I1 3-to-8 Y4 0 1 0 0 0 1 0 0 0 0 0
I0 Decoder Y3 0 1 1 0 0 0 1 0 0 0 0
Y2 1 0 0 0 0 0 0 1 0 0 0
Y1 1 0 1 0 0 0 0 0 1 0 0
Y0
1 1 0 0 0 0 0 0 0 1 0
1 1 1 0 0 0 0 0 0 0 1

49
 Decoders
 3-to-8 Line Decoder

Y7
Y6
I2 Y5
I1 3-to-8 Y4
I0 Decoder Y3
Y2
Y1
Y0

50
 Decoders
 3-to-8 Line Decoder from two 2-to-4 decoder
 Decoders with enable inputs can be connected together to form a larger decoder circuit.
 2-to-4 line decoders with enable inputs can be connected to form a 3-to-8 line decoder.

 When I2 = 0, bottom decoder enabled and other disabled.

 The bottom decoder outputs all 0’s.
 The top four outputs generate minterms 000 to 011.
 When I2 = 1, top decoder enabled and other disabled.
 The top decoder outputs all 0’s.
 The bottom four outputs generate minterms 100 to 111.

3-to-8 line decoder

51
 Decoders
 3-to-8 Line Decoder from two 2-to-4 decoder

I2 I 1 I 0 Y7 Y6 Y5 Y4 Y3 Y2 Y1 Y0

0 0 0 0 0 0 0 0 0 0 1
0 0 1 0 0 0 0 0 0 1 0
0 1 0 0 0 0 0 0 1 0 0
0 1 1 0 0 0 0 1 0 0 0
1 0 0 0 0 0 1 0 0 0 0
1 0 1 0 0 1 0 0 0 0 0
1 1 0 0 1 0 0 0 0 0 0
1 1 1 1 0 0 0 0 0 0 0
3-to-8 line decoder
52
 Decoders
 4-to-16 decoder constructed with two 3-to- 8 decoders

 When w = 0, top decoder enabled and other disabled.

 The bottom decoder outputs all 0’s.
 The top eight outputs generate minterms
0000 to 0111.
 When w = 1, bottom decoder enabled and other
disabled.
 The top decoder outputs all 0’s.
 The bottom decoder outputs generate minterms
1000 to 1111
4-to-16 line decoder

53
 Decoders
 A 4-to-16 decoder built using a decoder tree(five 2-to-4 decoder)

54
 Decoders
 Active-High / Active-Low

I1 I 0 Y3 Y2 Y1 Y0 I1 I 0 Y3 Y2 Y1 Y0 Y3
0 0 0 0 0 1 0 0 1 1 1 0
Y2
0 1 0 0 1 0 0 1 1 1 0 1
1 0 0 1 0 0 1 0 1 0 1 1 Y1
1 1 0 1 1 1
1 1 1 0 0 0
Y0

Y3 I1 Y3 I1
I1 Binary Y2 I0
Binary Y2
DecoderY1 DecoderY
I0 I0 1
Y0 Y0 55
 Decoders
 Combinational Logic Implementation
 A decoder provides the 2n minterm (product term) of n input variables.
 Since any Boolean function can be expressed in sum of minterms
 Use decoder to generate the minterms
 An external OR gate to form the logical sum.
 Any combinational circuit with n inputs and m outputs can be implemented
with an n-to-2n line decoder and m OR gates.

56
 Decoders
 Full-adder circuit from decoder
 From the truth table of the full adder, we obtain the functions for the combinational circuit
in sum-of-minterms form:

Implementation of a full adder with a decoder

57
 Encoders
 An encoder is a digital circuit that performs the inverse operation of a decoder.
 An encoder has 2n (or fewer) input lines and n output lines.
 The output lines, as an aggregate, generate the binary code corresponding to
the input value.
 It encodes given information into a more compact form.

58
 Encoders
 An encoder is a digital circuit that performs the inverse operation of a decoder.
 A binary encoder encodes information from 2n inputs into an n-bit code
 Exactly one of the input signals should have a value of 1, and the outputs present the binary
number that identifies which input is equal to 1.
 Encoders are used to reduce the number of bits needed to represent the given information.
 A practical use of encoders is for transmitting information in a digital system.
 Encoding the information allows the transmission link to be built using fewer wires.
 Encoding is also useful if information is to be stored for later use because fewer bits need to
be stored

A 2-to-n binary 59
 Encoders
 The encoder converts information, such as a decimal number or an alphabetic
character, into some coded form.

An encoder used to encode a calculator keystroke into a binary code for storage or for calculation.
60
 Encoders
 Example: 4-to-2 Binary Encoder

x1

x2 y1
Binary
Encoder
y0
x3

61
 Encoders
 A 4-to-2 binary encoder
 The output y0 is 1 when either input w1 or w3 is 1, and output y1 is 1 when
input w2 or w3 is 1.
 Note that the inputs are assumed one-hot encoded.

62
 Encoders
 Octal-to-Binary Encoder (8-to-3)

I7 I6 I5 I4 I3 I2 I1 I0 Y2 Y1 Y0
0 0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 1 0 0 0 1
0 0 0 0 0 1 0 0 0 1 0
0 0 0 0 1 0 0 0 0 1 1
0 0 0 1 0 0 0 0 1 0 0
0 0 1 0 0 0 0 0 1 0 1
0 1 0 0 0 0 0 0 1 1 0
1 0 0 0 0 0 0 0 1 1 1

63
 Multiplexers (Data Selectors)
 A multiplexer (MUX) is a logic circuit that switches digital data from several
input lines onto a single output line in a specified time sequence
 Selects binary information from one of many input lines and directs it to a single output
line.
 The selection of a particular input line is controlled by a set of selection lines.
 There are 2n input lines and n selected lines.
 A multiplexer (MUX) is a circuit that has
 Data inputs
 Control inputs
 An output

64
Multiplexers (Data Selectors)

65
 Multiplexers (Data Selectors)
 2-to-1 multiplexer
 A two-to-one-line multiplexer connects one of two 1-bit sources to a common destination.
 The circuit has two data input lines, one output line, and one selection line S
 When S = 0, the upper AND gate is enabled and w0 has a path to the output.
 When S = 1, the lower AND gate is enabled and w1 has a path to the output.
 The multiplexer acts like an electronic switch that selects one of two sources.

66
 Multiplexers (Data Selectors)
 4-to-1 multiplexer

67
 Multiplexers (Data Selectors)
 It is possible to build larger multiplexers using the same approach.
 A multiplexer that has n data inputs, w0, . . . , wn−1, requires [log2n]select inputs.
 Larger multiplexers can also be constructed from smaller multiplexers.
 For example, the 4-to-1 multiplexer can be built using three 2-to-1 multiplexers

Using 2-to-1 multiplexers to build a 4-to-1 68

 Multiplexers (Data Selectors)

Using 4-to-1 multiplexers to build a 16-to-1 69

 Demultiplexers
 A demultiplexer (DEMUX) is a combinational logic circuit that receives
information on a single input and transmits the same information over one of
several (2n) output lines.
 A demultiplexer basically reverses the multiplexing function
 Demultiplexing is the process of taking information from one input and
transmitting the same over one of several outputs.
 It takes digital information from one line and distributes it to a given number of output
lines.

70
Demultiplexers

71
 Demultiplexers
 1-to-4 Demux

72
Multiplexer/DeMultiplexer Pairs

73
Multiplexer/DeMultiplexer Pairs

74
Thank you!

75