University of Bisha

Faculty of Computing and Information Technology

Course title: Digital Design and Computer
Architecture

Chapter 4
Combinational logic

DR.MOHAMMED WASEEQU SHERAZ

Outlines
• Combinational logic function
• Half Adder
• Full Adder
• Half Sub
• Full Sub
• Subtraction using 2's complement
• Decoder and Encoder
• Multiplexer and Demultiplexer

2
Combinational Logic Circuit

• Logic circuits for digital systems may be Combinational circuit or

Sequential circuit.

• Combinational circuit: logic circuit whose outputs at any time are

determined directly and only from the present input combination.

• A combinational circuit performs a specific information-processing

operation fully specified logically by a set of Boolean functions.

3
Combinational circuit
• A combinational circuit consists of logic gates whose outputs at any
time are determined from only the present combination of inputs.

• A combinational circuit performs an operation that can be specified

logically by a set of Boolean functions.
5
Sequential circuits:
• 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.

• Because the state of the storage elements is a function of previous

inputs, the outputs of a sequential circuit depend not only on present
values of inputs, but also on past inputs, and the circuit behavior must
be specified by a time sequence of inputs and internal states.

6
ANALYSIS PROCEDURE

• Explain the analysis procedure. Analyze the combinational circuit the following logic
diagram.

i. The analysis of a combinational circuit requires that we determine the function that the
circuit implements.

ii. The analysis can be performed manually by finding the Boolean functions or truth
table or by using a computer simulation program.

iii. The first step in the analysis is to make that the given circuit is combinational or
sequential.

iv. Once the logic diagram is verified to be combinational, one can proceed to obtain the
output Boolean functions or the truth table.

7
➢ To obtain the output Boolean functions from a logic diagram:
✓Label all gate outputs that are a function of input variables with arbitrary
symbols or names.
✓Determine the Boolean functions for each gate output.
✓Label the gates that are a function of input variables and previously
labeled gates with other arbitrary symbols or names.
✓Find the Boolean functions for these gates.
✓Repeat the process in step 2 until the outputs of the circuit are obtained
✓By repeated substitution of previously defined functions, obtain the output
Boolean functions in terms of input variables.

8
9
▪ Proceed to obtain the truth table for the outputs of those gates which are a function of
previously defined values until the columns for all outputs are determined.

10
DESIGNPROCEDURE
Explain the procedure involved in designing combinational circuits.
➢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.
➢The procedure involved involves the following steps,
• From the specifications of the circuit, determine the required number of inputs
and outputs and assign a symbol to each.
• Derive the truth table that defines the required relationship between inputs and
outputs.
• Obtain the simplified Boolean functions for each output as a function of the
input variables.
• Draw the logic diagram and verify the correctness of the design.

11
CIRCUITS FOR ARITHMETIC OPERATIONS
❖Half adder:
• Construct a half adder with necessary diagrams.

• A half-adder is an arithmetic circuit block that can be used to add two bits and
produce two outputs SUM and CARRY.
• The Boolean expressions for the SUM and CARRY outputs are given by the
equations

Truth Table:

12
Logic Diagram: Half adder using NAND gate:

Half adder using NAND gate:

13
❖Full adder:
• Design a full adder using NAND and NOR gates respectively.

• A Full-adder is an arithmetic circuit block that can be used to add three

bits and produce two outputs SUM and CARRY.
• The Boolean expressions for the SUM and CARRY outputs are given by
the equations

14
Truth table:

15
❖Half subtractor:
• Design a half subtractor circuit.
• A half-subtractor is a combinational circuit that can be used to subtract
one binary digit from another to produce a DIFFERENCE output and a
BORROW output.
• The BORROW output here specifies whether a ‘1’ has been borrowed to
perform the subtraction.
• The Boolean expression for difference and borrow is:

16
Logic diagram:

17
❖Full subtractor:
• Design a full subtractor.
• A full subtractor performs subtraction operation on two bits, a minuend and a
subtrahend, and also takes into consideration whether a ‘1’ has already been
borrowed by the previous adjacent lower minuend bit or not.
• As a result, there are three bits to be handled at the input of a full subtractor,
namely the two bits to be subtracted and a borrow bit designated as Bin.
• There are two outputs, namely the DIFFERENCE output D and the BORROW
output Bo.
• The BORROW output bit tells whether the minuend bit needs to borrow a ‘1’
from the next possible higher minuend bit.
• The Boolean expression for difference and barrow is:

18
Full subtractor using two half subtractor:

19
Exercise:
• Question 1.1: Draw two truth tables illustrating the outputs of a half-adder, one table for the
sum output and other for the carry output.
• Question 1.2: Fill in the truth table at right for the following circuit. Ignore rows not included in the
table.

Solution Q.1.1

Solution Q.1.2

20
❖2’s complement:
• The 2’s complement of a binary number is formed by adding 1 with 1’s complement of a binary
number.
Example:
• 1. The 2’s complement of 1101100 is 0010100
• 2. The 2’s complement of 0110111 is 1001001

Subtraction using 2’s complement addition:

✓ The subtraction of unsigned binary number can be done by means of complements.
✓ Subtraction of A-B can be done by taking 2’s complement of B and adding it to A.
Check the resulting number.
✓ If carry present, the number is positive and remove the carry.
✓ If no carry present, the resulting number is negative, take the 2’s complement of
result and put negative sign.

21
➢Example:
• Given the two binary numbers X = 1010100 and Y = 1000011, perform the
subtraction
(a) X - Y and (b) Y - X by using 2’s complements.
Solution:
(a) X = 1010100
2’s complement of Y = + 0111101
Sum= 10010001
Discard end carry. Answer: X - Y = 0010001
(b) Y = 1000011
2’s complement of X= + 0101100
Sum= 1101111
There is no end carry.
Therefore, the answer is Y - X = -(2’s complement of 1101111)
= -0010001.

22
DECODERS AND ENCODERS

❖Decoder:
• Explain about decoders with necessary diagrams.

• A 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 of a decoder is to generate the 2n (or fewer) minterms of n

input variables, shown below for two input variables.

23
2 to 4 decoder:

24
❖ 3 to 8 Decoder:
▪ Design 3-to-8-line decoder with necessary diagram.

Truth Table:

25
Logic diagram:

26
Design for 3 to 8 decoder with 2 to 4 decoder:
Not that the two to four decoder design shown earlier, with its enable
inputs can be used to build a three to eight decoder as follows

27
❖ Implementation of Boolean function using decoder:
▪ Since the three to eight decoder provides all the minterms of three variables,
the realization of a function in terms of the sum of products can be achieved
using a decoder and OR gates as follows.
Example: Implement full adder using decoder.

Sum is given by Σm(1, 2, 4, 7) while Carry is given by Σm(3, 5, 6, 7) as

given by the minterms each of the OR gates are connected to.

28
❖ Encoder:
Explain about 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.

Octal to Binary Encoder:

▪ The encoder can be implemented with OR gates whose inputs are determined
directly from the truth table.
▪ Output z is equal to 1 when the input octal digit is 1, 3, 5, or 7.
▪ Output y is 1 for octal digits 2, 3, 6, or 7, and output x is 1 for digits 4, 5, 6, or 7.
These conditions can be expressed by the following Boolean output functions:

29
The encoder can be implemented with three OR gates.

Truth table:

Another ambiguity in the octal-to-binary encoder is that an output with all 0’s is
generated when all the inputs are 0; but this output is the same as when D0 is equal to 1.
The discrepancy can be resolved by providing one more output to indicate whether at
least one input is equal to 1.

30
MULTIPLEXERS AND DEMULTIPLEXERS

➢Multiplexer: (MUX)
✓Design a 2:1 and 4:1 multiplexer.
• A multiplexer is a combinational circuit that 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.
• Normally, there are 2n input lines and n selection lines whose bit combinations determine
which input is selected.
➢ 2 to 1 MUX:
• A 2 to 1 line multiplexer is shown in figure below, each 2 input lines A to B is applied to
one input of an AND gate.
• Selection lines S are decoded to select a particular AND gate.
• The truth table for the 2:1 mux is given in the table below.

31
• To derive the gate level implementation of 2:1 mux we need to have truth table
as shown in figure.
• And once we have the truth table, we can draw the K-map as shown in figure for
all the cases when Y is equal to '1'.
• Truth table:

Logic Diagram:

32
➢4 to 1 MUX:
• A 4 to 1 line multiplexer is shown in figure below, each of 4 input lines I0 to I3
is applied to one input of an AND gate.
• Selection lines S0 and S1 are decoded to select a particular AND gate.
• The truth table for the 4:1 mux is given in the table below.

33
➢DEMULTIPLEXERS:
• Explain about demultiplexers.
• The de-multiplexer performs the inverse function of a multiplexer, that is
it receives information on one line and transmits its onto one of 2n
possible output lines.
• The selection is by n input select lines.
• Example: 1-to-4 De-multiplexer

34
Logic Diagram: Truth Table:

35