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 3

Gate Level Minimization

The Map Method

• Complexity of the digital logic gates depends on the complexity of algebraic expression.
• Simplification – truth table can be used – but no specific rules
• Veitch / Karnaugh Map – simple straightforward procedure
• Made of squares – represent minterms

2 or 3 Variables Map

• There are 4 minterms for 2 variables and 8 minterms for 3 variables where variables are appeared in primed or not-primed form.
• Minterms are in binary sequence but in a sequence similar to the reflected code
• Only one bit changes in value from one adjacent column to the next
• Any two adjacent squares in the map differ by only one variable

​

​

• A prime implicant is a product term obtained by combining the maximum possible number of adjacent squares in the map. (number = 2ⁿ)

2 or 3 Variables Map

Two variables K-map

Three variables K-map

2 or 3 Variables Map…

F = x’yz + x’yz’ + xy’z’ + xy’z

F = x’yz + xy’z’ + xyz + xyz’

2 or 3 Variables Map…

Solve these ?

F = x’yz + x’yz’ + xy’z’ + xy’z F = A’C + A’B + AB’C + BC

Example 11

• Example 11: simplify the Boolean function F(x, y, z) = S(2, 3, 4, 5)
• F(x, y, z) = S(2, 3, 4, 5) = x'y + xy'

​

Map for Example 11, F(x, y, z) = Σ(2, 3, 4, 5) = x'y + xy'

Example 12

• Example 12: simplify F(x, y, z) = Σ(3, 4, 6, 7)
• F(x, y, z) = Σ(3, 4, 6, 7) = yz+ xz'

​

Map for Example 12; F(x, y, z) = Σ(3, 4, 6, 7) = yz + xz'

Example 13

• Example 13: simplify F(x, y, z) = Σ(0, 2, 4, 5, 6)
• F(x, y, z) = Σ(0, 2, 4, 5, 6) = z'+ xy'

​

Map for Example 13, F(x, y, z) = Σ(0, 2, 4, 5, 6) = z' +xy'

Example 14

• Example 14: let F = A'C + A'B + AB'C + BC
1. Express it in sum of minterms.
2. Find the minimal sum of products expression.

Ans:

F(A, B, C) = Σ(1, 2, 3, 5, 7) = C + A'B

​

Map for Example 14, A'C + A'B + AB'C + BC = C + A'B

4 Variables Map

Remember:

1. square = 4 literals term
2. squares = 3 literals term

4 squares = 2 literals term

8 squares = 1 literal term

16 squares = 1

4 Variable Map

Solve this:

NAND & NOR implementation

• NAND and NOR are easier to implement

NAND Implementation

Figure 3.23 Implementing F = (AB′ +A′B)(C+ D′)

NOR Implementation

• NOR function is the dual of NAND function.
• The NOR gate is also universal.

​

Figure 3.24 Logic Operation with NOR Gates

Example 15

• Example 15: simplify F(w, x, y, z) = Σ(0, 1, 2, 4, 5, 6, 8, 9, 12, 13, 14)

​

F = y'+w'z'+xz'

Map for Example 15; F(w, x, y, z) = Σ(0, 1, 2, 4, 5, 6, 8, 9, 12, 13, 14) = y' + w' z' +xz'

Example 16

• Example 16: simplify F = A′B′C′ + B′CD′ + A ′ BCD ′ + AB′C′

​

​

Map for Example 16; A′B′C′ + B′CD′ + A′B′C′D′ + AB′C′= B′D′ + B′C′ +A′CD′

Example 17

• Example 17: simplify F = Σ(0, 1, 2, 5, 8, 9, 10) into (a) sum-of-products form, and (b) product-of-sums form:

​

​

​

Map for Example 17, F(A, B, C, D)= Σ(0, 1, 2, 5, 8, 9, 10) = B'D'+B'C'+A'C'D

• F(A, B, C, D)= Σ(0, 1, 2, 5, 8, 9, 10) = B'D'+B'C'+A'C'D
• F' = AB+CD+BD'
• Apply DeMorgan's theorem; F=(A'+B')(C'+D')(B'+D)
• Or think in terms of maxterms

​

​

Example 17 (cont.)

• Gate implementation of the function of Example 17

​

Figure 3.15 Gate Implementation of the Function of Example 17

Product-of sums form

Sum-of products form

Sum-of-Minterm Procedure

• Consider the function defined in Table 3.2.
• In sum-of-minterm:

​

​

​

• In sum-of-maxterm:

​

​

​

• Taking the complement of F′

Sum-of-Minterm Procedure

• Consider the function defined in Table 3.2.
• Combine the 1’s:

​

​

​

• Combine the 0’s :

​

​

​

Figure 3.16 Map for the function of Table 3.2

'

3-6 Don't-Care Conditions

• The value of a function is not specified for certain combinations of variables
• BCD; 1010-1111: don't care
• The don't-care conditions can be utilized in logic minimization
• Can be implemented as 0 or 1
• Example 18: simplify F(w, x, y, z) = S(1, 3, 7, 11, 15) which has the don't-care conditions d(w, x, y, z) = S(0, 2, 5).

​

​

​

Don’t Care Condition

The Tabular Method / Quine-McCluskey Method

The Tabular Method (Alternative Way)

The Tabular Method

• Verification using K-map:

Prime Implicants Determination

• Another Example:

Prime Implicants Selections

The Tabular Method

Verification using K-map:

XOR and XNOR …

• When the number of variables (n) in a function is odd, the minterms with an even number of 0s (XNOR) and an odd number of 1s (XOR) are same. (XOR = XNOR, when they have same odd number of variables)
• But when the number of variables (n) in a function is even, they form the complements of each other.
• Odd function: In multiple variable XOR operation, if the number of 1 is odd.
• Even function: In multiple variable XOR operation, if the number of 1 is even.

Implementation of XOR and XNOR

• In S output of a full adder and D output of a full subtractor
• Also, very useful in systems requiring error detection and error correction code (in parity bit)
• Parity generator – generates the parity bit in the transmitter
• Parity checker – checks the parity bit in the receiver

Parity Generation and Checking

• Parity Generation and Checking
• A parity bit: P = x⊕y⊕z
• Parity check: C = x⊕y⊕z⊕P
• C=1: one bit error or an odd number of data bit error
• C=0: correct or an even # of data bit error

​

Figure 3.36 Logic Diagram of a Parity Generator and Checker

Parity Generation and Checking

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

​