Combinational Logic

CSE 4205: Digital Logic Design

Aashnan Rahman
Junior Lecturer
Department of Computer Science and Engineering (CSE)
Islamic University of Technology
 01

Logic Circuits
Memory or no Memory?

2
 LOGIC CIRCUIT

COMBINATIONAL LOGIC SEQUENTIAL LOGIC

CIRCUIT CIRCUIT

Output depends only on the Output depends only on the

current input combinations. current input combinations and
state of the memory elements.

3
 02

Combinational Circuit

4
Combinational Circuits
Combinational circuits consists of interconnection of logic gates
● Logic gates react to the values of the signal at the inputs and produce required output based on
the definition.
● These input and output signal exists physically as analog signal which must be interpreted as a
binary signal representing either logic-1 or logic-0

But, In many application, the source and destination of the combination circuit are
storage registers
● If the registers are included with the combinational circuit, then total circuit must be considered as
a sequential circuit

Note: A sequential circuit is circuit which has logic gates with feedback path or
memory elements
● A feedback path is a connection from output of any logic gate partially forms an input to any
previous gate

5
Combinational Circuits (block diagram)
Block diagram of a combinational circuit with n input and m output binary variables:

For n input variables, there are 2n possible combinations of the binary inputs (from external sources)
● For each input combination, there is one possible value for each output variable (to external
destinations)
A combinational circuit can be specified as a truth table that enlists output values for each input combination
● It is also specified as a Boolean function expressed in terms of the n input variables

6
Sequential Circuits (block diagram)

7
Combinational Circuits
Analysis of any combinational circuit starts with a logic diagram
● Finally we will determine the function that the circuit implements, generates the truth table and
feasibly explains the operation of the circuit.
● If the function name or its explanation are already mentioned with logic circuit, then we need to
verify it (verification)
● Another way to analyze any circuit with logic simulation if the number of inputs is very large

8
Combinational Circuits
Analysis Procedure: To obtain boolean function
1. Make sure that the given circuit is a combinational circuit, not sequential
2. To obtain Boolean function:
a. Label all the gate outputs that are the function of input variables with arbitrary symbols.
Determine those functions.
b. Also label the intermediate gate outputs that are the function of any input variables or
previously defined symbols (i.e. already labeled gate outputs). Find those functions as well.
c. Repeat the process of step (b) until the output of the logic circuit is obtained
d. By repeated substation of previously defined intermediate functions, obtain the output Boolean
function in terms of input variables

9
Combinational Circuits
Analysis Procedure: To obtain boolean function

10
Combinational Circuits
Analysis Procedure: To obtain boolean function

Step (a):

Step (b and c):

Step (d):

11
Combinational Circuits
Analysis Procedure: To obtain Truth Table
1. Make sure that the given circuit is a combinational circuit, not sequential
2. To obtain the truth table from the logic diagram directly:
a. Determine the number of input variables in the circuit
For n inputs, form the 2n possible input combinations and list them as binary number from 0 to
(2n-1).
b. Label the intermediate gate outputs that are the function of any input variables or previously
labeled gate outputs
c. Obtain the truth table for those intermediate outputs
d. Proceed to obtain for the outputs of those gates which are the function of previously defined
values until the columns for all outputs are determined
3. Otherwise, from the derived function, it can be obtained very easily.

12
Combinational Circuits
Analysis Procedure: To obtain Truth Table

Note: This truth table is identical to the truth table of the full adder

13
Combinational Circuits
Design Procedure
1. Design of a combinational circuit starts from a problem statement (design objective)
2. And it ends in a logic circuit diagram or a set of Boolean functions from where the logic
diagram can be obtained.
3. There are some steps to be followed to achieve the requested combinational circuit

14
Combinational Circuits
Design Procedure
1. From the specification of the circuit, determine the required number of inputs and
outputs. Assign a symbol to each input and output variables.
2. Derive the truth table from the specification that defines the required relationship
between inputs and outputs
a. Input columns have 2n different combinations for n input variables.
b. Output values are determined from the problem statement.
c. The specifications may indicate that some input combinations will not occur –
don’t care conditions.
3. Obtain the simplified Boolean functions for each output as a function of the input
variables.
a. These output functions gives the exact definition of the circuit
b. These output functions should be simplified by any simplification method like
k-map, tabular method, algebraic manipulation
4. Draw the logic diagram and verify the correctness of the design

15
Combinational Circuits
Design Procedure: Considerations
1. In a particular application, certain criteria will serve as a guide to choose an
implementation among different alternatives.
2. A practical design method considers such constraints:
a. Minimum number of gates
b. Minimum number of inputs to a gate
c. Minimum propagation time of the signal through the circuit
d. Minimum number of interconnections
e. Limitations of the driving capabilities of each gate (i.e. the number of gates to
which this output may be connected)
3. Based on the application, those constraints will be prioritized.
4. So there is no general statement to constitute an acceptable implementation
5. Most of the cases, the implementation begins with producing the simplified Boolean
functions in standard form. It may proceed to further steps to meet other performance
criteria

16
Combinational Circuits
Design Procedure: Example
1. Circuit specification:
a. In practical different digital systems may use different codes and they may need
to exchange information
b. So a code converter circuit is required between them to make these two systems
compatible even though they uses different binary codes
2. Initial Consideration:
a. To convert from binary code A to binary code B, the input lines must have the bit
combinations specified by code A.
● The output lines must generate the corresponding bit combinations
specified by code B.
● Now we have to design this combinational circuit assuming code A as BCD
and code B as excess-3 for decimal digits.

17
Combinational Circuits
Design Procedure: Example
Truth Table for 4 input and 4 output variables:

18
Combinational Circuits
Design Procedure: Example
K-map for 4 output variables to obtain their simplified Boolean functions:

19
Combinational Circuits
Design Procedure: Example

Two level logic diagrams of each output variables can be produced directly from their
respective simplified expression in SOP forms.
● But with multiple-output system, these expressions can be manipulated algebraically
further to obtain flexibility of common gates
● Here, gate implementation might require three or more level of gates

20
Combinational Circuits
Design Procedure: Example

21
 02

Binary Adder

22
Binary Adder
Fundamental digital circuit used to perform binary addition

Binary Adder

Half Adder Full Adder

Adds 2 bit Adds two bits and a carry

23
Half Adder
Two binary input bits (augend and addend) and two binary output bits (sum and carry)
● Two input and two output variables

Assignment of symbols – two inputs [x & y] and two outputs [S & C]

● S represents the LSB and C represents the MSB of the sum

24
Half Adder
Simplified Boolean Functions for two outputs

These functions could be implemented in different ways as well.

25
Full Adder
For addition of n-bit binary numbers, it requires the use of a full adder
● Bit by bit addition will be occurred beginning from the LSB

A full adder is a combinational circuit that performs the arithmetic sum of three input bits

Three inputs (x, y and z) and two outputs (S and C)

● x and y are two significant bits to be added
● z represents the carry from the previous lower significant position
● Two outputs are necessary because the arithmetic sum of three binary digits ranges in value from 0 to 3
● S is the LSB of the sum and C is the MSB

26
Full Adder

27
Full Adder (SoP)

28
Full Adder (with Half Adder)

29
Binary Ripple Carry Adder
A chain of n full adders or a chain of one half adder and (n – 1) full adders in cascade.
● Subscript 0 denotes the LSB and (n-1) denotes the MSB
● The input carry C0 in the least significant position of the first case must be 0.
Output carry of any full adder is connected to the input carry of the next full adder in the chain

Example: A=1011 and B=0011 will produce the sum, S=1110 with four bit adder as follows:

30
Binary Ripple Carry Adder
If we follow the classical method, it would require a truth table with 29=512 entries
● By using an iterative method of cascading a standard function, it is possible to obtain a simple and
straightforward implementation.
● All the carries must be generated to obtain correct sum at the outputs.

31
Carry Propagation

32
Carry Propagation with Full Adder

33
Carry Propagation with 4 bit Full Adder

34
Carry Lookahead Generator Circuit

35
4-bit Binary Adder with Carry Lookahead

36
 03

Binary Subtractor

37
Binary Subtractor
● The subtraction of two unsigned binary numbers – taking the complement of the subtrahend
and adding it to the minuend
● Complement of a number can be obtained by 1’s or 2’s complement
● So subtraction is a kind of addition operation – needs full adder for machine implementation
● If the minuend bit is smaller than the subtrahend bit, a 1 is borrowed from the next
significant position – also must be conveyed to the next higher pair of bits by means of a
binary signal from current stage to next higher stage
● For signed-complement system, addition and subtraction could be implemented using same
circuit like unsigned number system.
● Users should interpret the system wisely considering it is signed or unsigned number. So
same circuit could be used to handle both types of arithmetic

38
Binary Subtractor
Fundamental digital circuit used to perform binary subtraction of two unsigned numbers

Binary Subtractor

Half Subtractor Full Subtractor

Subtracts 2 bit Subtracts two bits and considers

borrow from last bit

39
Half Subtractor
Subtracts two bits and produces their differences and an output that specifies if a 1 is borrowed
or not to next stage.
● Designation of the input variables – minuend (x) and subtrahend (y)
Assignment of symbols – two inputs [x & y] and two outputs [D & B]
● B represents the borrow and D represents the Difference

40
Half Subtractor

41
Full Subtractor

42
Full Subtractor
Truth table of the full-subtractor:

K-map for full-subtractor to simplify:

43
Full Subtractor

44
Full Subtractor

45
4 bit Full Adder-Subtractor

46
Overflow
• When two numbers with n digits each are added and the sum is a number occupying n
+ 1 digits
• Problem in digital computers, as there is a finite number of bits
• Overflow detection is required to handle this occurrence
• Not possible with paper and pencil as there is no limit of space

• Only happens during addition, but not for subtraction

• When both numbers are either positive or negative

• Also depends on the types of numbers:

• Unsigned numbers:
• Overflow detected by end carry of the MSB
• Signed numbers :
• A range is maintained from max positive to min negative. If the sum crosses the range, an overflow occurs
• (n+1)th bit indicates the sign bit of the result
• Note: Sign bit is treated as a part of a number and carry doesn’t indicate an overflow

47
 Overflow

Note that the eight-bit result that should have been positive has a negative sign bit (i.e.,
the eighth bit) and the eight-bit result that should have been negative has a positive
sign bit. As 9-bit storage is not possible, an overflow has occurred.

Overflow condition: carry in and out in the MSB position is not same. (Try +70 and +50
to check overflow)
48
Additional Resources
1. Virtual Labs

49
Thank You !!
Feel free to ask any questions

50