Ali Adib Arnab�Senior Lecturer and Chairman, Department of Electrical and Electronic Engineering�University of Global Village�MSc in Telecommunication and Wireless Systems and Management, Queen Mary University of London

My Google Site Link: https://sites.google.com/view/ali-adib-arnab/home

Topic 4

Combinational Logic

Introduction

• Logic circuits of any digital system
• Combination Logic Circuit
• Sequential Logic Circuit
• A combinational circuit is the circuit whose outputs at any time are determined directly from the present combination of inputs without regard to previous inputs or outputs.
• On the other hand, Sequential circuits employ memory elements (binary cells) in addition to the logic gates.
• Their outputs are the function of the present inputs and the state of the memory elements. Its behavior must be time sequence specified.

Combinational Circuits

• Analysis
• Given a circuit, find out its function
• Function may be expressed as:
• Boolean function
• Truth table
• Design
• Given a desired function, determine its circuit
• Function may be expressed as:
• Boolean function
• Truth table

Introduction

Introduction…

Combinational Circuits consists of –

• Input variables (1/0) – n input variables from external sources – primed and unprimed
• Logic gates
• Output variables (1/0) – m output variables to external destinations

• For n input variables, there are 2ⁿ possible combinations of binary input values

– for each of them there is only one possible output combination.

• For m output variables, a combinational circuit can be described by m Boolean functions – one for each output variables.

Design Procedure

Design of a combinational circuit starts from a problem statement and ends in a logic circuit diagram.

The procedure involves:

• The problem is stated
• The number of available input variables and required output variables is determined
• The input and output variables are assigned letter symbols
• The truth table that defines the required relationships between inputs and outputs are derived
• The simplified Boolean function for each output is obtained
• The logic diagram is drawn

Design Procedure…

• The 1s and 0s in the input columns are obtained from the 2ⁿ binary

combinations available for n input variables

• The binary values for the outputs are determined from examination of the stated problem
• The specifications may indicate that some input combinations will not occur – don’t care conditions
• Truth table – exact definition of the combinational circuit
• Output Boolean Function from the truth table – simplified by any simplification method like k-map, tabular method, algebraic manipulation

Design Procedure…

• A practical design method considers such constraints:
1. Minimum number of gates
2. Minimum number of inputs to a gate
3. Minimum propagation time of the signal through the circuit
4. Minimum number of interconnections
5. Limitations of the driving capabilities of each gate
• Based on the application, those constraints will be prioritized.
• A logic diagram is useful to visualize the gate implementation of the expression

Adder

• A digital computer performs a variety of information processing tasks amongst them most common are arithmetic operations
• The most basic arithmetic operation – addition of two binary digits – 4 possible elementary operations

Adder…

• 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.
• When the augend and addend numbers contain more significant digits, the

carry obtained from the addition of two bits is added to the next higher order pair of significant bits.

• A combinational circuit that performs the addition of two bits is

called a half adder.

• One that performs the addition of three bits (two significant bits and a previous carry) is a full adder.
• Two half adders can be employed to implement a full adder.

Half Adder

• Two binary inputs (augend and addend) and two binary outputs (sum and carry)
• Determination the number of variables – two inputs and two outputs
• Assignment of symbols – two inputs [x & y] and two outputs [S & C]
• S represents the LSB and C represents the MSB of the sum
• Truth table to identify the function of the half adder

Half Adder…

• Simplified Boolean functions for two outputs:

It also can be written as: S = (x+y)(x’+y’) = (x’y’+xy) C = (x’+y’)’

• To be flexible, there are more available implementations.
• To be noted :
• XOR of x and y = (x+y)(x’+y’)
• Equivalence of x and y = (xy+x’y’)
• De Morgan’s Law: xy = (x’+y’)’

Half Adder…

Half Adder Implementation

Full Adder

• A combinational circuit that forms 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
• The two outputs are designated by the symbols S for sum and C for carry.
• S is the least significant bit of the sum and C is the most significant bit

Full Adder…

• The truth table of the full adder:

• The input-output logical relationship can be expressed in two Boolean functions – two unique maps are required for each to simplify

Full Adder…

In SOP form

Implementation of full adder

Full Adder…

Full Adder with two Half Adders and OR gate

Full Adder…

Binary Adder

• Binary adder – produces the arithmetic sum of two binary numbers
• Addition of n-bit numbers requires a chain of n full adders or a chain of one

half adder and (n – 1) full adders in cascade.

• The input carry C₀ in the least significant position must be 0.
• If we follow the classical method, it would require a truth table with 2⁹=512 entries. By using an iterative method of cascading a standard function, it is possible to obtain a simple and straightforward implementation.

Binary Adder

• Half Adder
• Adds 1-bit plus 1-bit
• Produces Sum and Carry

x

+ y

───

C S

Subtractors

• The subtraction of two binary numbers – taking the complement of the subtrahend and adding it to the minuend
• 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
• Two kind of subtractor based on the number of inputs P:
• Half-subtractor
• Full subtractor

Half-Subtractor

• A combinational circuit – subtracts two bits and produces their differences and the output that specifies if a 1 is borrowed or not to next stage.
• Designation of the input variables – minuend (x) and subtrahend (y)
• D = 2B + x – y, [if x<y, B=1]

Half-Subtractor…

• Boolean functions of two outputs of the half-subtractor:

D = x’y+xy’ B = x’y

• Logic for D is same as the logic for S in half-adder
• Circuit Implementation of half-subtractor:

Full-Subtractor

• A combinational circuit – performs a subtraction between two bits considering the previous borrow – three inputs and two outputs
• Designation of variables – inputs [minuend(x), subtrahend(y), previous borrow(z)] and outputs [difference(D) and current borrow (B)]
• Considering 2B+x-y-z, if z=0, it will be same as half-subtractor
• If (x<y+z),B=1

Full-Subtractor…

• Truth table of the full-subtractor:

• K-map for full-subtractor to simplify:

Full-Subtractor…

• The simplified Boolean function of full-subtractor:

𝐷 = 𝑥^′𝑦^′𝑧 + 𝑥^′𝑦𝑧^′ + 𝑥𝑦^′𝑧^′ + 𝑥𝑦z

𝐵 = 𝑥^′𝑦 + 𝑥^′𝑧 + 𝑦𝑧

• The output of B resembles the function for C in the full adder – except x is complemented
• The output of D is exactly same as the output S in the full adder
• Because of these similarities, it is possible to convert a full adder into a full subtractor - ???

Full-Subtractor with Half-Subtractors

Code Conversion

• Sometimes same information used in different codes by different digital systems – output of one system used as input to another
• A conversion circuit – between these two systems for this information flow.
• Code converter – makes these two systems compatible even though their code is different
• To convert from code A to code B – input lines supply the bit combination specified by A and output lines generates the bit combination specified by B

Example – BCD to Excess-3

• Since each code uses four bits to represent a decimal digit – there are

four input variables (A,B,C,D) and four output variables (w,x,y,z)

• The truth table relating the input and output variables:

Example – BCD to Excess-3…

• There are various possibilities for the logic diagram for this circuit – because of having don’t care conditions
• One of the possible solutions with multiple representations:

• Here we can see that the term (C+D) has been obtained in multiple outputs

Example – BCD to Excess-3…

• Logic diagram for BCD to Excess-3 Code Converter:

Analysis Procedure

• The design of a combinational circuit starts from the problem statement and its required specifications (or verbal explanation) and ends with a set of output Boolean functions or a logic diagram
• But the analysis of a combinational circuit is the reverse process – it starts with a logic diagram and ends with a set of Boolean functions, a truth table, or a verbal explanation of the circuit operation
• First step in this analysis – check the circuit – combinational or sequential

Analysis Procedure

• Truth Table Approach

= 0

= 0

= 0

= 0

= 0

= 0

= 0

= 0

= 0

= 0

= 0

= 0

0

0

0

0

0

0

1

0

0

0 0

Analysis Procedure

• Truth Table Approach

= 0

= 0

= 1

= 0

= 0

= 1

= 0

= 0

= 0

= 1

= 0

= 1

0

1

0

0

0

0

1

1

1

1 0

Analysis Procedure

• Truth Table Approach

= 0

= 1

= 0

= 0

= 1

= 0

= 0

= 1

= 0

= 0

= 1

= 0

0

1

0

0

0

0

1

1

1

1 0

Analysis Procedure

• Truth Table Approach

= 0

= 1

= 1

= 0

= 1

= 1

= 0

= 1

= 0

= 1

= 1

= 1

0

1

0

0

1

1

0

0

0

0 1

Analysis Procedure

• Truth Table Approach

= 1

= 0

= 0

= 1

= 0

= 0

= 1

= 0

= 1

= 0

= 0

= 0

0

1

0

0

0

0

1

1

1

1 0

Analysis Procedure

• Truth Table Approach

= 1

= 0

= 1

= 1

= 0

= 1

= 1

= 0

= 1

= 1

= 0

= 1

0

1

0

1

0

1

0

0

0

0 1

Analysis Procedure

• Truth Table Approach

= 1

= 1

= 0

= 1

= 1

= 0

= 1

= 1

= 1

= 0

= 1

= 0

0

1

1

0

0

1

0

0

0

0 1

Analysis Procedure…

• Combinational logic – no feed back path/ no memory element
• Feedback path – a connection from the output from one gate to input of second gate that forms part of the input to the first gate

Analysis Procedure…

• After verification of the circuit as combinational logic, we proceed to obtain the output Boolean functions or truth table (based on specification)
• Steps we follow to proceed:
• Label with arbitrary symbols all gate outputs that are a function of the input variables. Obtain the Boolean functions for each gate.
• Label with other arbitrary symbols those gates which are a function of input variables and/or previously labeled gates. Find the Boolean functions for those gates.
• Repeat the process outlined 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 only.

Analysis Procedure…

Analysis the following combinational circuit:

Analysis Procedure…

• The circuit has 3 binary inputs – A,B, and C and 2 binary outputs – F₁

and F₂

• The outputs of various gates are labeled with intermediate symbols
• The outputs of gates that are a function only of input variables are T₁

and T₂.

• Output F₂ can easily be derived from the input variables.

Analysis Procedure…

• Next, we consider outputs of gates that are a function of already defined symbols:

​

• To obtain F₁ as a function of A, B, and C, we form a series of substitutions as follows:

Analysis Procedure…

• To pursue the investigation and determine the information transformation task achieved by the circuit – truth table from the Boolean function.
• For example: this circuit is a full adder with F1 being the sum and F2 being the carry outputs. A,B and C are three inputs to be added.
• The derivation of the truth table for the circuit is a straightforward process when output Boolean functions are known

Analysis Procedure…

To obtain the truth table directly from the logic diagram without going through the derivations:

1. Determine the number of input variables in the circuit. For n inputs, form the 2ⁿ possible input combinations and list the binary numbers from 0 to (2ⁿ - 1) in a table.
2. Label the outputs of selected gates with arbitrary symbols.
3. Obtain the truth table for the outputs of those gates which are a function of the input variables only.
4. 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.

Analysis Procedure…

Truth table derivation directly from the logic diagram.

Combinational Circuit – NAND Implementation

• NAND – universal gate
• Both combination and sequential circuit can be constructed with NAND gates

NAND gate

NAND Implementation…

• It can be done by obtaining the simplified Boolean functions in terms of AND, OR, NOT gates and converting the functions to NAND logic
• Procedure of implementation of Boolean functions with NAND gates:

Block Diagram Method

• From the given algebraic expression, draw the logic diagram with AND, OR and NOT gates. Assume that both the normal and complement inputs are available.
• Draw the second logic diagram with the equivalent NAND logic substituted for each AND, OR and NOT gate
• Remove any two cascaded inverts from the diagram, since double inversion doesn't perform a logic function. Remove inverters connected to single external inputs and complement the corresponding input variable.

NAND Implementation…

In general, the number of NAND gates required to implement a function is equal to the number of AND-OR gates, except for an occasional inverter. It will be applicable when both normal and complement inputs are available.

NAND Implementation: Analysis Procedure

• Reverse process – starts from given NAND logic diagram and ends

with a Boolean expression or truth table

• Specialty – Application of De Morgan’s Law
• Derivation of Boolean Function from NAND Logic Diagram
• All gates’ outputs are labeled with arbitrary symbols
• The Boolean functions for the outputs of gates that receive only external inputs are derived. It may follow De Morgan’s law to make it convenient to use
• Boolean output functions of gates which have inputs from previously derived functions are determined in consecutive order until the output is expressed in terms of input variables

NAND Imp.: Analysis Procedure …

Example:

NAND Imp.: Derivation of Truth Table

Same as before.

NAND Imp.: Derivation of Truth Table …

Now we can use K-map to get the simplified expression of the given NAND logic circuit.

NAND Imp.: Block Diagram Transformation

• Without employing De Morgan’s Law.
• We use two alternate graphic symbols of NAND gates

NAND Imp.: Block Diagram Transformation…

• NAND logic diagram – AND-OR diagram conversion
• A change in symbols from AND-invert to an invert-OR in alternate levels of gates.
• At first we start from the last level, to be changed to an invert-OR symbol.
• These changes produce pairs of circles along the same line – can be removed as they can be cancelled.
• One input AND or OR gate can be changed to an inverter.
• Circle with external input can be changed to corresponding complemented variable.

NAND Imp.: Block Diagram Transformation…

NOR Implementation

• NOR function – Dual of NAND function – also dual of the corresponding procedures and rules for NAND logic
• NOR gate – universal gate – used to construct combinational and sequential circuit

NOR gate

Boolean Function Imp. With NOR Gates

Block Diagram Method:

1. Draw the AND-OR logic diagram from the given algebraic expression considering normal and complement form of inputs.
2. Draw the second logic diagram with the equivalent NOR logic

substituted for each AND, OR and NOT gate

3. Remove any two cascaded inverts from the diagram, since double inversion doesn't perform a logic function. Remove inverters connected to single external inputs and complement the corresponding input variable.

Block Diagram Method: NOR Imp.

In general, the number of NOR gates required to implement a function is equal to the number of AND-OR gates, except for an occasional inverter. It will be applicable when both normal and complement inputs are available.

NOR Implementation: Analysis Procedure

• To derive the Boolean function from a logic diagram, we mark the outputs of various gates with arbitrary symbols.
• By repetitive substitutions, we obtain the output variables as a function of the input variables.
• To obtain the truth table from a logic diagram without deriving the Boolean function first, we form a table listing the n input variables with 2ⁿ rows of 1s and 0s. The truth table of various NOR gate outputs is derived in succession until the output truth table is obtained.

Decoders

• Extract “Information” from the code
• Binary Decoder
• Example: 2-bit Binary Number

Only one lamp will turn on

0

​

0

1

0

0

0

Decoders

• 2-to-4 Line Decoder

Encoders

• Put “Information” into code
• Binary Encoder
• Example: 4-to-2 Binary Encoder

Only one switch should be activated at a time

Multiplexers

Multiplexers

• 2-to-1 MUX

​

​

​

• 4-to-1 MUX

Published Papers��[1] Ali Adib Arnab, Sheikh Sadia Afrin, F.M. Fahad, Hasan U. Zaman, "A cost effective way to build a web controlled search and CO detector rover," DOI:10.1109/CCWC.2017.7868451 (Received the track Best Paper Award), Proceedings of the 7th IEEE Annual Computing and Communication Workshop and Conference (IEEE CCWC 2017), Las Vegas, USA, 9-11 January, 2017, Publisher: IEEE�[2] Ali Adib Arnab, Sheikh Md. Razibul Hasan Raj, John Schormans, Sultana Jahan Mukta, Nafi Ahmad "Analysis of the Cost of Varying Levels of User Perceived Quality for Internet Access," https://doi.org/10.1007/978-3-030-68154-8_36 , Proceedings of the 3rd International Conference on Intelligent Computing & Optimization – ICO 2020, Hua Hin, Thailand, 22-23 April, 2021, Publisher: Springer

• Research and Teaching Interests: 
• Wireless and Mobile Communication
• Telecommunication Engineering
• Communication Theory
• Electronics
• Internet of Things
• Digital Electronics
• Renewable Energy
• VLSI

​