Digital Design and Computer Organization BCS302

MODULE-2
Combinational Logic: Introduction, Combinational Circuits, Design Procedure, Binary Adder-
Subtractor,Decoders, Encoders, Multiplexers. HDL Models of Combinational Circuits – Adder, Multiplexer,
Encoder
Sequential Logic: Introduction, Sequential Circuits, Storage Elements: Latches, Flip-Flops.
COMBINATIONAL LOGIC
2.1 Introduction
 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 canbe specified logically by a set of Boolean
functions.
 Sequential circuitsemploy storage elements in addition to logic gates. Their outputs are a function of
theinputs and the state of the storage elements.
 Because the state of the storage elementsis a function of previous inputs, the outputs of a sequential
circuit depend not only onpresent values of inputs, but also on past inputs, and the circuit behavior must
be specified by a time sequence of inputs and internal states.

2.2 Combinational Circuits

Fig: Block diagram of combinational circuit

A combinational circuit consists of an interconnection of logic gates. Combinational logic gates react to the
values of the signals at their inputs and produce the value of the output signal, transforming binary information
from the given input data to a required output data.The n inputbinary variables come from an external source;
the m output variables are produced bythe internal combinational logic circuit and go to an external
destination.Each inputand output variable exists physically as an analog signal whose values are interpretedto
be a binary signal that represents logic 1 and logic 0.
For n input variables, there are 2n possible combinations of the binary inputs. For eachpossible input
combination, there is one possible value for each output variable. Thus, acombinational circuit can be specified

Dept. of CSE AIET, Mijar, Moodabidri Page 1

Digital Design and Computer Organization BCS302
with a truth table that lists the output values foreach combination of input variables. A combinational circuit
also can be described bym Boolean functions, one for each output variable. Each output function is expressed
in terms of the n input variables.
The solution of some typicalexamples will provide a useful catalog of elementary functions that are important
for theunderstanding of digital systems. We’ll address three tasks:
 Analyze the behavior of agiven logic circuit
 synthesize a circuit that will have a given behavior, and
 Writehardware description language (HDL) models for some common circuits.
There are several combinational circuits that are employed extensively in the designof digital systems.such as
adders, subtractor, comparators, decoders, encoders, and multiplexers.These components are available in
integrated circuits as medium-scale integration (MSI) circuits. They are also used as standard cells in complex
very large- scale integrated (VLSI) circuits such as application-specific integrated circuits (ASICs). The
standard cell functions are interconnected within the VLSI circuit in the same way that they are used in
multiple-IC MSI design.

2.3 Design Procedure

The design of combinational circuits starts from the specification of the design objectiveand culminates in a
logic circuit diagram or a set of Boolean functions from which thelogic diagram can be obtained. The procedure
involves the following steps:
1. From the specifications of the circuit, determine the required number of inputsand outputs and assign a
symbol to each.
2. Derive the truth table that defines the required relationship between inputs andoutputs.
3. Obtain the simplified Boolean functions for each output as a function of the inputvariables.
4. Draw the logic diagram and verify the correctness of the design (manually or bysimulation).
A truth table for a combinational circuit consists of input columns and outputcolumns. The input columns are
obtained from the 2n binary numbers for the n inputvariables. The binary values for the outputs are determined
from the stated specifications. The output functions specified in the truth table give the exact definition of
thecombinational circuit. It is important that the verbal specifications be interpretedcorrectly in the truth table,
as they are often incomplete, and any wrong interpretationmay result in an incorrect truth table.
2.3.1 Code Conversion Example
The availability of a large variety of codes for the same discrete elements of informationresults in the use of
different codes by different digital systems. It is sometimes necessaryto use the output of one system as the
input to another. A conversion circuit must beinserted between the two systems if each uses different codes for
the same information.
Dept. of CSE AIET, Mijar, Moodabidri Page 2
Digital Design and Computer Organization BCS302
To convert from binary code A to binary code B, the input lines must supply the bit combination of elements as
specified by code A and the output lines must generate the corresponding bit combination of code B. A
combinational circuit performsthis transformation by means of logic gates. The design procedure will be
illustratedby an example that converts binary coded decimal (BCD) to the excess-3 code for thedecimal digits.

Fig: Truth Table for Code Conversion Example

We designate the four input binaryvariables by the symbols A, B, C, and D, and the four output variables by w,
x, y , and z.

Fig: K-Maps for BCD-to-excess-3 code converter

Dept. of CSE AIET, Mijar, Moodabidri Page 3
Digital Design and Computer Organization BCS302
Implemented with three or more levels of gates:

Fig: Logic diagram for BCD-to-excess-3 code converter

2.4 Binary Adder- Subtractor
 Digital computers perform a variety of information-processing tasks. Among the functions encountered
are the various arithmetic operations.
 The most basic arithmeticoperation is the addition of two binary digits. This simple addition consists of
four possible elementary operations: 0 + 0 = 0, 0 + 1 = 1, 1 + 0 = 1, and 1 + 1 = 10.
 Thefirst three operations produce a sum of one digit, but when both augend and addend bits are equal to
1; the binary sum consists of two digits.The higher significant bit of this result is called a Carry.
 A combinational circuit that performs the addition of two bits iscalled ahalf adder. One that performs
the addition of three bits is a full adder.
2.4.1 Half Adder
We find that this circuit needs two binaryinputs and two binary outputs. The input variables designate the
augend and addendbits; the output variables produce the sum and Carry. We assign symbols x and y to thetwo
inputs and S (for sum) and C (for Carry) to the outputs.The simplified Boolean functions for the two outputs can
be obtained directly from the truth table. The simplified sum-of-products expressions are
S = x’y + xy’
C = xy

Dept. of CSE AIET, Mijar, Moodabidri Page 4

Digital Design and Computer Organization BCS302
The logic diagram of the half adder implemented in sum of products, It can be also implemented with an
exclusive-OR and an AND gate

Fig: Half Adder truth table

Fig (a): The logic diagram of the half adder implemented using AND and OR gate
Fig (b): The logic diagram of the half adder implemented in using EX-OR and an AND gate
2.4.2 Full Adder
Addition of n-bit binary numbers requires the use of a full adder, and the process of addition proceeds on a bit-
by-bit basis, right to left, beginning with the least significant bit. Afterthe least significant bit, addition at each
position adds not only the respective bits of thewords, but must also consider a possible Carry bit from addition
at the previous position.
A full adder is a combinational circuit that forms the arithmetic sum of three bits. Itconsists of three
inputs and two outputs.Three of the input variables, denoted by x, y and z he two outputs are designated by the
symbols S for sum and C for Carry.The binary variable S gives the value of the least significant bit of the sum.
The binaryvariable C gives the output Carry formed by adding the input Carry and the bits of thewords.
S = x’y’z + x’yz’ + xy’z’ + xyz
C = xy + xz + yz

Fig: Full Adder truth table

Dept. of CSE AIET, Mijar, Moodabidri Page 5
Digital Design and Computer Organization BCS302

Fig (a):K-Map for Sum

Fig (b):K-Map for Carry

Fig: The logic diagram of the Full adder implemented in sum-of-products form
2.4.3 Binary Adder
A binary adder is a digital circuit that produces the arithmetic sum of two binary numbers. It can be constructed
with full adders connected in cascade, with the output Carry from each full adder connected to the input Carry
of the next full adder in the chain.the interconnection of four full-adder (FA) circuits toprovide a four-bit binary
ripple Carry adder. The augend bits of A and the addend bitsof B are designated by subscript numbers from
right to left, with subscript 0 denotingthe least significant bit. The carries are connected in a chain through the
full adders. Theinput Carry to the adder is C0, and it ripples through the full adders to the output CarryC4. The
S outputs generate the required sum bits. An n -bit adder requires n full adders,with each output Carry
connected to the input Carry of the next higher order full adder.

Fig: Implementation of full adder with two half adders and an OR gate
Dept. of CSE AIET, Mijar, Moodabidri Page 6
Digital Design and Computer Organization BCS302
To demonstrate with a specific example, consider the two binary numbers A = 1011and B = 0011. Their sum S
= 1110 is formed with the four-bit adder as follows:

The bits are added with full adders, starting from the least significant position (subscript0), to form the sum bit
and Carry bit. The input Carry C0 in the least significant positionmust be 0. The value of Ci+1 in a given
significant position is the output Carry of the fulladder. This value is transferred into the input Carry of the full
adder that adds the bitsone higher significant position to the left. The sum bits are thus generated starting
fromthe rightmost position and are available as soon as the corresponding previous Carrybit is generated. All
the carries must be generated for the correct sum bits to appear atthe outputs.
 Four-bit adder:

Fig: Four-bit adder

The four-bit adder is a typical example of a standard component. It can be used inmany applications involving
arithmetic operations. Observe that the design of this circuit by the classical method would require a truth table
with 29 = 512 entries, since thereare nine inputs to the circuit. By using an iterative method of cascading a
standard function, it is possible to obtain a simple and straightforward implementation.
 Carry Propagation
The number of gate levels for the Carry propagation can be found from the circuit of the full adder.The input
and output variables use the subscript i to denote a typical stage of the adder.The signals at Pi and Gi settle to
their steady-state values after they propagate throughtheir respective gates. These two signals are common to all
half adders and depend ononly the input augend and addend bits. The signal from the input CarryCi to the
outputCarry Ci+1 propagates through an AND gate and an OR gate, which constitute two gatelevels. If there are
four full adders in the adder, the output Carry C4 would have2 * 4 = 8 gate levels from C0 to C4. For an n -bit
adder, there are 2 n gate levels for theCarry to propagate from input to output.
Dept. of CSE AIET, Mijar, Moodabidri Page 7
Digital Design and Computer Organization BCS302

Fig: Full adder with P and G shown

If we define two new binary variables
Pi = Ai⊕Bi
Gi = AiBi
the output sum and Carry can respectively be expressed as
Si = Pi⊕Ci
Ci+1 = Gi + PiCi
Gi is called a Carry generate, and it produces a Carry of 1 when both Ai and Bi are 1,regardless of the input
CarryCi. Pi is called a Carry propagate, because it determineswhether a Carry into stage i will propagate into
stage i + 1, We now write the Boolean functions for the Carry outputs of each stage and substitutethe value of
each Ci from the previous equations:
C0 = input Carry
C1 = G0 + P0C0
C2 = G1 + P1C1 = G1 + P1(G0 + P0C0) = G1 + P1G0 + P1P0C0
C3 = G2 + P2C2 = G2 + P2G1 + P2P1G0 + P2P1P0C0
 CarryLookahead logic:
There are several techniques for reducing the Carry propagation time in a parallel adder. The most widely used
technique employs the principle of CarryLookahead logic.The three Boolean functions for C1, C2, and C3 are
implemented in the CarryLookahead generator. Note that this circuit canadd in less time because C3 does not
have to wait for C2 and C1 to propagate; in fact, C3is propagated at the same time as C1 and C2. This gain in
speed of operation is achievedat the expense of additional complexity.
The construction of a four-bit adder with a CarryLookahead, Each sum output requires two exclusive-
OR gates. The output of the first exclusive-ORgate generates the Pi variable, and the AND gate generates the Gi
variable. The carriesare propagated through the CarryLookahead andapplied as inputs to the second exclusive-
OR gate. All output carries are generated aftera delay through two levels of gates. Thus, outputs S1 through S3
have equal propagationdelay times. The two-level circuit for the output Carry C4 is not shown. This circuit
caneasily be derived by the equation-substitution method.

Dept. of CSE AIET, Mijar, Moodabidri Page 8

Digital Design and Computer Organization BCS302

Fig: Logic diagram of CarryLookahead generator

Fig: Four-bit adder with Carry Lookahead

Dept. of CSE AIET, Mijar, Moodabidri Page 9

Digital Design and Computer Organization BCS302
2.4.4 Binary Subtractor
The subtraction A - B can be done by taking the 2’s complement of B and adding it to A. The 2’s complement
can be obtained by taking the 1’s complement and adding 1 to the least significant pair of bits. The 1’s
complement can be implemented with inverters, and a 1 can be added to the sum through the input Carry.

Fig: Four-bit adder–subtractor (with overflow detection)

The circuit for subtracting A - B consists of an adder with inverters placed betweeneach data input B and the
corresponding input of the full adder. The input carry C0 mustbe equal to 1 when subtraction is performed. The
operation thus performed becomes A,plus the 1’s complement of B, plus 1. This is equal to A plus the 2’s
complement of B. For unsigned numbers, that gives A - B if A ≥ B or the 2’s complement of 1B - A2 if A <B.
For signed numbers, the result is A - B, provided that there is no overflowthe addition and subtraction
operations can be combined into one circuit with onecommon binary adder by including an exclusive-OR gate
with each full adder. A four-bitadder–subtractor circuit is shown above.
The mode input M controls the operation.When M = 0, the circuit is an adder, and when M = 1, the circuit
becomes a subtractor.Each exclusive-OR gate receives input M and one of the inputs of B. When M = 0, we
have B⊕0 = B. The full adders receive the value of B, the input carry is 0, and thecircuit performs A plus B .
When M = 1, we have B⊕1 = B’ and C0 = 1. The B inputsare all complemented and a 1 is added through the
input carry. The circuit performs theoperation A plus the 2’s complement of B
 Overflow:
When two numbers with n digits each are added and the sum is a number occupying n + 1 digits, we say that an
overflow occurred. This is true for binary or decimal numbers, signed or unsigned.Overflow is a problem in
digital computers because the number of bits thathold the number is finite and a result that contains n + 1 bits
cannot be accommodatedby an n -bit word.
The detection of an overflow after the addition of two binary numbers depends onwhether the numbers
are considered to be signed or unsigned. When two unsignednumbers are added, an overflow is detected from
the end carry out of the most significant position.
Dept. of CSE AIET, Mijar, Moodabidri Page 10
Digital Design and Computer Organization BCS302
An overflow cannot occur after an addition if one number is positive and the otheris negative, since adding a
positive number to a negative number produces a resultwhose magnitude is smaller than the larger of the two
original numbers.An overflow may occur if the two numbers added are both positive and both negative.
Two signed binary numbers, +70 and +80, are stored in two eight-bit registers. The range of numbers
that each register can accommodate is from binary +127 to binary -128. Since the sum of the two numbers is
+150, it exceeds the capacity of an eight-bit register. This is also true for -70 and -80.

Dept. of CSE AIET, Mijar, Moodabidri Page 11