Combinational Logic
Rab Nawaz Khan Jadoon
Department of Computer Science Lecturer
COMSATS Lahore
DCS
Pakistan
COMSATS Institute of
Information Technology
Digital Logic and Computer Design
Department of Computer Science 2
Combinational logic
A combinational circuit consists of logic gates whose
outputs at any time are determined directly from the
present combination of inputs without regard to
previous outputs.
A combinational circuit performs a specific information
processing operation fully specified logically by a set of
Boolean functions.
A Combinational circuit consists of input variables, logic
gates, and output variables.
Department of Computer Science 3
Combinational logic
The logics gate accept signals from the inputs and
generate signals to the outputs.
This process transforms binary information from the
given input data to the required output data.
Department of Computer Science
Combinational logic
Design Procedures
Starts from the verbal outline of the problem and
ends in a logic circuit diagram.
The procedure involves the following step,
The problem is stated.
Input and required output variables are
determined.
Assigned the variables letter symbols.
Make the truth table.
The simplified Boolean functions for each output
is obtained.
The logic diagram is drawn.
Department of Computer Science 5
Combinational logic
Adders
Adders are important in computers and also in other
types of digital systems in which numerical data are
processed.
An understanding of the basic adder operation is
fundamental to the study of digital systems.
The most basic operation is no doubt is the addition of
two binary digits.
Department of Computer Science
The Half Adder
Half Adder
The combinational circuit that performs the additions
of two bit is called Half adder.
One that performs the addition of three bits including
two digits and one previous carry is a full adder.
Two half adders can be employed to form a full adder.
Department of Computer Science
Combinational logic
Half Adder
It has two inputs and two outputs.
The input variables designates the augends and
addend bits; the output variables produces the sum
and carry.
It is necessary to specify two output variables because
the result may consist of two binary digits.
A and B are two inputs binary variables while C and S
used for carry and Sum to the outputs.
Department of Computer Science 8
Combinational logic
Half Adder
The half-adder accepts two binary digits on its inputs
and produces two binary digits on its outputs, a sum
bit and a carry bit.
The truth table look like this,
A B Cout S
0 0 0 0
0 1 0 1
1 0 0 1
1 1 1 0
Department of Computer Science
Combinational logic
Half Adder
A half-adder is represented by the logic symbol in
Figure below,
Department of Computer Science 10
Half Adder
Half-Adder Logic
Notice that the output Carry (Cout) is a 1 only when
both A and B are 1s; therefore Cout can be expressed
as the AND of the input variables.
Cout = AB
Now observe that the sum output (Σ) is a 1 only if
the input variables. A and B, are not equal.
The sum can therefore be expressed as the
exclusive-OR of the input variables.
Department of Computer Science 11
Related Example
Half-Adder Logic
The logic implementation required for the half adder
function can be developed.
The output carry is produced with an AND gate with
A and B on the inputs.
The sum output is generated with an exclusive-OR
gate.
Department of Computer Science
Half Adder
Half-Adder Logic diagram
Department of Computer Science
Solutions
Department of Computer Science
Full Adder
Full Adder
The second category of adder is the full-adder.
The full-adder accepts two input bits and an input
carry and generates a sum output and an output
carry.
The basic difference between a full-adder and a half-
adder is that the full-adder accepts an input carry.
Department of Computer Science
Full Adder
Logical symbol for full adder is,
Department of Computer Science
Full Adder
Truth Table
Cin = input carry, sometime designated as CI
Cout = output carry sometimes designated as CO
Σ=sum
A and B = input variables (operands)
Department of Computer Science
Full Adder
Full Adder Logic
The full-adder must add the two input bits and the
input carry.
From the half-adder you know that the sum of the
input bits A and B is the exclusive-OR of those two
variables, A xor B.
For the input carry (Cin ) to be added to the input
bits. it must be exclusive-ORed with A xor B, yielding
the equation for the sum output of the full-adder.
Department of Computer Science
Full Adder
Map for Full Adder (For Sum Function)
yz
x
S= x’y’z + x’yz’ + xy’z’ + xyz
Department of Computer Science
Full Adder
For Carry Simplified Expression
yz
x
C= xy + xz + yz
Department of Computer Science
Implementation of Full Adder in SOP
Logic Diagram
Department of Computer Science
Implementation of Full Adder
Implementation of a full adder with two half adders
and an OR Gate
Department of Computer Science
Adders
Department of Computer Science
Problem
For each of the three full-adders in Figure
below, determine the outputs for the inputs
shown.
Department of Computer Science
Solution
Department of Computer Science
Quiz
Department of Computer Science
Department of Computer Science
Department of Computer Science
Parallel Binary Adders
Two or more full-adders are connected to form
parallel binary adders.
a single full-adder 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 full-adders.
When one binary number is added to another,
each column generates a sum bit and a 1 or 0
carry bit to the next column to the left.
Department of Computer Science
Department of Computer Science
Parallel Binary Adder
To add two binary numbers, a full-adder is required for
each bit in the numbers.
So for 2-bit numbers, two adders are needed.
For 4-bit numbers, four adders are used; and so on.
The carry output of each adder is connected to the
carry input of the next higher-order adder.
Notice that either a half-adder can be used
for the least significant position or the carry input of a
full-adder can be made 0 (grounded) because there is
no carry input to the least significant bit position.
Department of Computer Science
Parallel Binary Adder
Department of Computer Science
Parallel Binary Adder
In Figure the least significant bits (LSB) of the
two numbers are represented by A1 and B1.
The next higher-order bits are represented by
A2 and B2 .
The three sum bits are Σ1,Σ2 and Σ3.
Notice that the output carry from the left-most
full-adder becomes the most significant bit
(MSB) in the sum, Σ3.
Department of Computer Science
Example
Determine the sum generated by the 3-bit
parallel adder and show the intermediate carries
when the binary numbers 101 and 011 are
being added.
Department of Computer Science
Four Bit Parallel Adder
A group of four bits is called a nibble.
A basic 4-bit parallel adder is implemented with
four full-adder stages as shown in Figure .
Department of Computer Science
Logical Symbol for 4 bit Parallel Adder
Department of Computer Science
4 bit parallel adder
The input labeled Co is the input carry to the
least significant bit adder.
C4 in the case of four bits, is the output carry of
the most significant bit adder; and Σ1 (LSB)
through Σ4 (MSB) are the sum outputs.
The 4-bit parallel adder can be expanded to
handle the addition of two 8-bit numbers by
using two 4-bit adders.
Department of Computer Science
8 Bit Adder
Cascading of two 4-bit adders to form an 8-bit adder
Department of Computer Science
Subtractors
Subtraction of two binary number is
accomplished by taking the complement of the
subtrahend and adding it to the minuend.
Logically it can be done through direct method.
In this method each bit of the subtrahend is
subtracted from its corresponding significant
minuend bit to form a difference bit.
If the minuend bit is smaller then a 1 borrow is
taken from the next higher pair of the bits.
Department of Computer Science
Subtractors
Half Subtractor
It subtract two bits and produces their difference.
It also has an output to specify if a 1 has been
borrowed.
x and y are minuend and subtrahend veriable.
For subtraction we check the relative magnitude of
the x and y.
If x>=y then no issue.
If x<y then it is necessary to take a borrow from the
next higher stage.
Department of Computer Science
Half subtractor
Truth table of half subtractor is,
X Y B D
0 0 0 0
0 1 1 1
1 0 0 1
1 1 0 0
D=x’ y + x y’
B=x’ y
Department of Computer Science
Problem
Draw a circuit diagram against Difference D and
Borrow B.
Department of Computer Science
Full Subtractor
It performs a subtraction between two bits,
taking in to account that a 1 may have been
borrowed by a lower significant stage.
It has three inputs and two outputs.
Three inputs x, y and z shows the minuend,
subtrahend and previous borrow respectively.
B and D represents the output borrow and
Difference.
Department of Computer Science
Full Subtractor
Truth table is as under,
Department of Computer Science
Full Subtractor
The function against B and D are,
Department of Computer Science
Code conversion
Some times the output of the one system as the
input to another.
If both the system uses different coding system,
then code convertor is needed between them.
Thus a code convertor is a circuit that makes
the two system compatible.
To convert from binary code A to B,
Input lines supply the bit combination of elements by
Code A and the output lines must generate the
corresponding bit combination for code B.
Department of Computer Science 46
Code conversion from BCD to Excess 3 is
illustrated below,
Department of Computer Science 47
Outputs Simplification
Department of Computer Science 48
Circuit Diagram
Department of Computer Science 49
Binary to Gray code
Department of Computer Science 50
Gray to Binary
Department of Computer Science 51
Q?
Related Problem
How many exclusive-OR gates are required to convert 8-bit
binary to Gray?
Department of Computer Science 52
Department of Computer Science 53
