COMBINATIONAL CIRCUIT

Introduction:
• When logic Gates are connected to produce a specific output on certain specified
combinations of input variables, with no memory involved, then the resulting circuit is
called a combinational circuit.
• Output depends only on present input. O/P = f(I/O), combinational circuit performs an
operation that can be specified logically by a set of Boolean function.
• A combinational circuit may have ‘n-binary inputs’ and ‘m-binary outputs’.
• Application: Practical computer circuits normally contain combinational and sequential
logical circuits. E.g.- The part of ALU, that does mathematical calculations is
constructed using combinational logic.
Design Procedure:
1. Analyze the given problem and identify the number of I/O and O/P variables.
2. Write the truth table based on the specification of the problem.
3. Convert the truth in minimized Boolean expression using K-Map.
4. Draw the logic circuit for the above obtained output expression.
Classification:

1. Adder:
• An adder is a digital combinational circuit that performs addition of numbers. These
are used in the mathematical logic units or ALU.
• They are also utilized in other parts of the processor, where they are used to calculate
addresses, table indices, increment and decrement operators and similar operations.
• Although adders can be constructed for many number representations, such as binary-
coded decimal or excess-3, the most common adders operate on binary numbers.
• In cases where 2’s complement or 1’s complement is being used to represent negative
numbers; it is very easy to modify an adder into an adder-subtractor.
Need of a Half-Adder:
• A binary adder-subtractor is a combinational circuit that performs the arithmetic
operations of addition and subtractor with binary numbers.
• We will develop this circuit by means of a hierarchical design. The half adder design is
carried out first, from which we will develop the full adder.
 • Connecting ‘n’ full adders in cascade form, produces a binary adder for two ‘n-bit’
numbers.

Half Adder:
• The simplest form of addition is addition of two binary digits, consists of four possible
elementary operations.
• 0 + 0 =1 • 1+0=1
• 0+1=1 • 1+1=10
• The first 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.

• It is a combinational circuit, which perform the arithmetic addition of two one-bit

binary numbers is referred as a half adder.
• So, in half adder, inputs are two single binary bits A and B, and two outputs, sum (S)
and carry (C).
Implementation Cost of Half Adder:
• Cost of implementation of a half adder is one EX-OR Gate and one AND Gate.
• A half adder has only two inputs and there is no provision to add a carry coming from
the lower order bits when multi-bit number addition is performed.
• For this reason, we have designed a full adder.
Full Adder:
• A full adder is a combinational logic circuit that perform the arithmetic sum of three
input bits.
• Where An, Bn are the nth order bits of number A and B respectively and Cn is the carry
generated from the addition of (n-1)th order bits.
• It consists of three input bits, denoted by A (first operand), B (second operand) and Cin
(represent carry from previous lower significant position).

Implementation Cost of Full Adder:

• Two outputs are same as of half adder, which is Sum and Carryout.
• When the augend and addend of a number contain more significant digits, the carry
obtained from the two additions of two bits is added to the next higher order pair of
significant bits.
Four-Bit Parallel Binary Adder (Ripple Adder):
• As we know that full adder is capable of adding two 1-bit numbers and one previous
carry, but in order to add binary numbers with more than one-bit, additional full adders
must be employed.
• For example: A 4-bits binary adder can be constructed using four full adders.
• These four full adders are connected in cascade, carry output of each adder is connected
to the carry input of the next higher-order adder.
• So, a n-bits parallel adder is constructed using ‘n’ number of full adders.
 • The longest propagation delay in an adder is the time it takes the carry to propagate
through the full adders.
• For a carry in 4-bit adder, we have 2-Gate delays at each adder and for a sum, we
have 1-Gate delay at every full adder.
• For an n-bit adder, there are ‘2n’ Gate levels for the carry to propagate from input to
output and for a sum, we have ‘(2n-1)’ Gate delays.
• The time complexity = O(n)

Question: A half adder is implemented with X-OR and AND Gates. A full adder is implemented
with two half adders and one OR Gate. The propagation delay of an X-OR gate is twice that of
an AND/OR Gate. The propagation delay of an AND/OR Gate is 1.2 microseconds. A 4-bit
ripple-carry binary adder is implemented by using full adders. The total propagation time if
this 4-bit binary adder in microseconds is: GATE-2015

Four-Bit Ripple Adder/Subtractor:

• The subtractor of unsigned numbers can be done most conveniently by the means of
complements.
• The subtraction (A-B) can be done by the 1’s complement of B and adding 1 to 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.
• The circuit for subtracting (A-B) consists of an adder with X-OR Gates are placed
between each data input B and the corresponding input of the full adder.
Implementation of Adder/Subtractor:
• The mode input M controls the operation. When M = 0, the circuit is an adder, and
when M = 1, the circuit becomes a subtractor.

• When M = 0, we have B ⊕ 0 = B. The full adders receive the value of B, the input
carry is ‘0’, and the circuit performs A + B.
• When M = 1, we have B ⊕ 1 = B’ and C0 = 1. The B input are all complemented and
a 1 is added through the input carry. The circuit performs the operation A plus the 2’s
complement of B.
Disadvantage:
• Due to carry propagation delay, parallel calculation (addition or subtraction) is not
possible.
Solution:
• Solution is ‘Look Ahead Carry Generator’.
Look Ahead Carry Generator (Adder):
• In parallel adder, all bits of augend and addend are available for computation initially,
but sum and carry outputs of any stage cannot be produced until the input carry occurs.
• This leads to delay in the addition process known as carry propagation delay.
• In any combinational circuit, the signal must propagate through the gates before the
correct output sum is available in the output terminals.
• The total propagation time = (Propagation delay of a typical Gate)*(The number of
Gate levels in the circuit).
• The carry propagation time is an important attribute of the adder because it limits the
speed with which two numbers are added.
• The solution to delay is to increase the complexity of the equipment in such a way that
the carry delay time reduced.
• To solve this problem most widely used technique employs the principle of ‘Look
Ahead Carry’.
• This method utilizes logic Gates to look at the lower order bits of the augend and addend
to see if a higher order carry is to be generated. It is uses two functions: (1) Carry
Generate Gi and (2) Carry Propagate Pi.
1) Carry Generate (Gi): It produce a carry of 1 when Ai and Bi are 1, regardless of
input carry Ci.
2) Carry Propagate (Pi): It determines whether 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 substitute
the value of each Ci from the previous equation.

• Since, the Boolean function for each output carry is expressed in the form of sum-of-
product (SOP).
• Each function can be implemented with one level of AND Gates followed by an OR
Gate (or by a two-level NAND).
• The time complexity = O(1).
• All output ‘carries’ are generated after a delay through two levels of Gates.
• Thus, the output S1 through S3 have equal propagation delay time.
Implementation Diagram:
Note:
• A 4-bit ‘Look Ahead Carry Generator’ consists of 10-AND (1 + 2 + 3 + 4 = 10) Gates
and 4-OR (1 + 1 + 1 + 1 = 4) Gates.

2. Multiplexer (Selector):
• Multiplexer is a special and one of the most widely used combinational circuits.
• Main requirement is out of many inputs, we have to select one.
• For example: Telephone or train leaving the station.
• So, multiplexer do not perform any logical operation or comparison, it just acts as a
switch or relay.

• A multiplexer is a combinational circuit that selects binary information from one of

many input lines and directs it to a single output line.
• A multiplexer is also called a data selector, since it selects one of many inputs and steers
the binary information to the output line.
• The selection of a particular input line in controlled by a set of selection lines.
• There are 2n input lines and ‘n’ selection lines whose bit combinations determine which
one input is to be selected.
• Number of input line ≤ 2n
• Can never be two inputs connected to output at any time.
Applications:
• Parallel data to serial data conversion.
• Used as data selector, as the output of a multiplexer is directed from one of various
inputs.
• Used in communication systems, computer memory, telephone network, transmission
from the computer system of a satellite.
Two-to-One (2×1) Multiplexer:
• This multiplexer acts like an electronic switch selects one of two sources.
• 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 I0 has a path to the output.
• When S = 1, the lower AND Gate is enabled and I1 has a path to the output.
• Characteristic Equation: Y = S0’I0 + S0I1
Four-to-One (4×1) Multiplexer:

• Each of the four inputs, I0, I1, I2 & I3 are applied to one input of an AND Gate.
• Selection lines S1 and S0 are used to select a particular AND Gate.
• The output of the AND Gates are applied to a single OR Gate that provides the one-line
output.

• Characteristic Equation: Y = E[(S’1S’0I1) + (S1’S0I1) + (S1S0’I2) + (S1S0I3)]

Implementation of Higher Order MUX Using Lower Order MUX:

1) Number of 2×1 MUX required to implement 4×1 MUX.

2) Number of 4×1 MUX required to implement 16×1 MUX.

3) Number of 4×1 MUX required to implement 128×1 MUX.

4) Number of 4×1 MUX required to implement 128×1 MUX.

Note:
3. Demultiplexer:
• A demultiplexer is a device that takes a single output line and routes it to one of the
several digital output lines.
• A demultiplexer is also called a data distributor.
• It is conceptually same as MUX but just with reverse logic.

• A demultiplexer of 2n output has ‘n’ selection line, which are used to select to which
output line to send the input.
1×2 Demultiplexer:

1×4 Demultiplexer:
Implementation of Higher Order D-MUX using Lower Order D-MUX:
• Number of 1×2 D-MUX required to implement 1×4 D-MUX = 3.
• Number of 1×2 D-MUX required to implement 1×8 D-MUX = 7.

Applications:
• A D-MUX is a combinational circuit, which is used in data communication.
• It is used to serial to parallel conversion.
• D-MUX are mainly used in Boolean function generators and decoder circuits.
4. Decoders:
• A decoder is a combinational circuit that decodes binary information from ‘n’ input
lines to a maximum of 2n unique output lines.
• The decoders are called ‘n-to-m-line’ decoders, where m ≤ 2n.
• Their purpose is to generate the 2n (or fewer) minterms of ‘n’ input variables. Each
combination of inputs will assert a unique output.
• If n-bit coded information has unused combinations, the decoder may have fewer than
2n outputs.
• For simple decoders, it assumed that only one output line is active at a time.
 • Decoders are also combinational circuits, logically we can say a D-MUX can be
converted into a decoder by setting input line as enable line and selection line as input
lines.

1-to-2 Decoder:

2-to-4 Decoder:

Combinational Logic Implementation in Decoders:

• Any combinational circuit with ‘n’ inputs and ‘m’ outputs can be implemented with an
n-to-2n-line decoder and OR Gates.
• The procedure for implementing a combinational circuit by means of a decoder and OR
Gates requires that Boolean function for the circuit be expressed as a sum of minterms.
• A decoder is then chosen that generates all minterms of the input variables.
• The inputs to each OR Gate are selected from the decoder outputs according to the list
of minterms of each function.
Active High Decoder:
• When output is directly from AND Gate, we get exact minterms then, it is called active
high decoder.
• In the 2nd level here, we use OR Gate to find the function.

Active Low Decoder:

• In active low decoders, output will be from NAND Gates, on the 2nd level.
• On the 2nd level, we again use NAND Gate, as we know NAND-NAND implementation
that is same as AND-OR implementation.

Question-1: Implement a ‘Full-Adder’ with the help of Decoder.

Answer: From the truth of the full adder, we obtain the function for the combinational circuit
in ‘Sum of Minterms’ form:
• S(X, Y, Z) = ∑𝐦𝐦(𝟏𝟏, 𝟐𝟐, 𝟒𝟒, 𝟕𝟕)
• C(X, Y, Z) = ∑𝐦𝐦(𝟑𝟑, 𝟓𝟓, 𝟔𝟔, 𝟕𝟕)
 Example:

Note:

Implementation of Higher Order Decoder Using Lower Order Decoder:

• Number of 1-to-2 -Decoder required to implement 2-to-4-Decoder = 3.
 • Number of 2-to-4-Decoder required to implement 6-to-64-Decoder = 21.

• Number of 3-to-8-Decoder required to implement 7-to-128-Decoder = 19.

5. Encoder:
• An encoder is a combinational circuit that encode binary information from one of a 2n
input lines and encode it into ‘n’ output lines, which represent n-bit code for the input.
• For simple encoders, it is assumed that only one input line is active at a time.
• Encoder performs the inverse operation of a decoder.

2-to-1 Encoder:

4-to-2 Encoder:
Priority Encoder:
• In some practical cases, more than one input can be high at a time, there we cannot use
simple encoder.
• In a priority encoder, more than one input can be high at a time. A priority encoder is
an encoder circuit that includes the priority function.
• The operation of the priority encoder is such that, if two or more inputs are high at the
same time, the input having highest priority will take precedence.
• They are often used to control interrupt requests by acting on the highest priority
interrupt input.
• The priority encoders output corresponds to the currently active input which has the
highest priority.
• So, when an input with a higher priority is present, all other inputs with a lower priority
will be ignored.