GATE LEVEL MINIMIZATION

Question 1

Draw the:
2-Variable KMap
3-Variable KMap
4-Variable KMap
5-Variable KMap

Answer 1

*See notes

Question 2

What is a prime Implicant?

Answer 2

A prime implicant is a product term obtained by
combining the maximum possible number of adjacent squares in the map.

*See notes for pic

Question 3

What is an essential prime implicant?

Answer 3

Essential prime implicants(EPI) are those prime implicants which always appear in final solution.

*See notes for pic

Question 4

What is a redundant prime implicant

Answer 4

The prime implicants for which each of its minterm is covered by some essential prime implicant are redundant prime implicants(RPI).
This prime implicant never appears in final solution.

*See notes for pic

Question 5

What is a Selective Prime Implicant (SPI)

Answer 5

 These are the prime implicants for which are neither essential nor redundant prime implicants.
 These are also known as non-essential prime implicants.
 They may appear in some solution or may not appear in some solution.

*See notes for pic

Question 6

Do the examples from the following pages in the lecturer’s material:
9, 11, 13, 15-18, 21-22, 28-30, 33

Answer 6

*See Lec material

Question 7

Draw a table showing the relationship between number of adjacent squares and the number of the literals in the term

Answer 7

*See notes

Question 8

How does one express sum of minterms as POS

Answer 8

Combine squares marked with 0’s (usual way like minterms)
Apply DeMorgan’s theory on this simplified function
*See notes

Question 9

What is a don’t care condition?

Answer 9

A combination of variables whose logical value is not
specified.
 Cannot be marked with a 1 or 0 in the map
 Marked with an X
Denoted as d(w, x, y, z) = (0, 2, 5)

*See notes pg 41 of lec material

Question 10

Why are digital circuits constructed with NAND or NOR gates?

Answer 10

 Easier to fabricate with electronic components
 The basic gates used in all IC digital logic families.

Question 11

Draw circuits which show that NAND and NOR are universal circuits and any logic circuit can be implemented with them

Answer 11

*See notes

Question 12

Draw an alternative symbol of the NAND and the NOR gate

Answer 12

*See notes

Question 13

What are the steps of two-level implementation of NAND gates

Answer 13

1. Simplify the function and express it in SOP
2. Draw a NAND gate for each product term of the expression that has at least two literals. The inputs to each NAND gate are the literals of the term.
3. Draw a single gate using the AND-invert or the invert-OR graphic symbol in the second level, with inputs coming from outputs of
   first-level gates.
4. A term with a single literal requires an inverter in the first level. However, if the single literal is complemented, it can be connected
   directly to an input of the second level NAND gate.

*Do examples on page 46 and 47

Question 14

What are the steps to multilevel implementation of NOR gates

Answer 14

1. Convert all AND gates to NAND gates with AND-invert graphic symbols.
2. Convert all OR gates to NAND gates with invert-OR graphic symbols.
3. Check all the bubbles in the diagram. For every bubble that is not compensated by another small circle along the same line, insert an inverter (a one-input NAND gate) or complement the input literal.

*Do examples on page 50 and 51

Question 15

What are the steps of implementing circuits with the NOR gates

Answer 15

 Simplify the function into POS form.
 Change the OR gates to NOR gates with OR-invert graphic symbols
 Change the AND gate to a NOR gate with an invert-AND graphic symbol.
 A single literal term going into the second-level gate must be complemented.

*Do examples on page 56

Question 16

Describe wired logic

Answer 16

 Some NAND or NOR gates allow the possibility of a wire connection between the outputs of two gates to provide a specific logic function.
 This type of logic is called wired logic.
-Eg the AND-OR-INVERT and the OR-AND-INVERT
*These are not physical gates

Question 17

Illustrate how the AND-OR-INVERT gate is implemented

Answer 17

*See notes

Question 18

Illustrate how the OR-AND-INVERT gate is implemented

Answer 18

*See notes

Question 19

What is a degenerate form

Answer 19

 We consider four types of gates: AND, OR, NAND, and
NOR. These will have 16 combinations of two-level forms. (by assigning one type of gate for the first level and one type for the second level)
 Eight of these combinations are said to be degenerate
forms, because they degenerate to a single operation.

Question 20

What are nondegenerate forms

Answer 20

Combinations of the four gates that produce SOPs or POSs

Question 21

Illustrate how the NAND-AND and AND-NOR combinations are treated

Answer 21

*See notes