Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

Digital Design Morris Mano > Gate Level Minimization > Flashcards

Gate Level Minimization Flashcards

1
Q

Gate-level minimization

A

Gate-level minimization is the design task of finding an optimal gate-level implementation of the Boolean functions describing a digital circuit.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

A Boolean function is recognized graphically in the map by?

A

Since any Boolean function can be expressed as a
sum of minterms, it follows that a Boolean function is recognized graphically in the map
from the area enclosed by those squares whose minterms are included in the function.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

what will u call a simplest algebraic expression? As what properties it should have..

A

simplest algebraic expression is an algebraic expression with a minimum number of terms and with the smallest possible number of literals in each term

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

The simplified expressions produced by the map are always in what form?

A

The simplified expressions produced by the map are always in one of the two standard
forms: sum of products or product of sums.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

2 variable K-Map

A

Karnaugh map
-2 variable, so 4 minterms: m0,m1,m2,m3; so four squares in the map.
-The minterms at which the function is asserted are
marked with a 1.
-Mark the squares whose minterms belong to a given function, to represent any one of the 16 Boolean functions of 2 variables.
[ Assign column var y: column 1:y’=0 & column 2:y=1
lly row1: x’=0 ; row2: x = 1]

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

3 Variable K Map

A
  • 3 variables so 8 minterms so 8 squares.
  • minterms are arranged in gray code, i.e only 1 bit changes in value from one adjacent
    column to the next.
  • Square belonging to row p, column qr [binary no. k = pqr] has value of minterm mk.
    -Each cell of the map corresponds to a unique minterm, so another way of looking at
    square m5 = xy’z is to consider it to be in the row marked x and the column belonging
    to y’z (column 01).
    primed: 0 &; unprimed:1.
    -Note that there are 4 squares in which each variable is equal to 1 and in another 4 they are 0.
    -For convenience, we write the variable with its letter
    symbol under the four squares in which it is unprimed.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

the basic property possessed by adjacent squares?

3 variable K map

A

Any two adjacent squares
in the map differ by only one variable.
Sum of 2 minterms in
adjacent squares can be simplified to a single product term consisting of only 2 literals.
Ex : m5 + m7 = xy’z + xyz = xz(y’ + y) = xz
- Thus, any two minterms in adjacent squares (vertically or horizontally, but not diagonally, adjacent) that are ORed together will cause a removal
of the dissimilar variable.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

the basic property possessed by adjacent squares being possessed by not adjacent squares:
3 variable K map.

A

In certain cases, two squares in the map are considered to be adjacent even though
they do not touch each other. m0 is adjacent to m2 and m4 to m6 cuz their minterms differ by 1 variable. This difference can be readily verified
algebraically:
m0 + m2 = x’y’z’ + x’yz’ = x’z’(y’ + y) = x’z’
m4 + m6 = xy’z’ + xyz’ = xz’(y ‘+ y) = xz’

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Simplification of combination of four adjacent squares in 3 variable K map:

A

Any such combination represents the logical sum of four minterms and results in an
expression with only one literal.

[the literal whose value is unchanged]

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Rules for simplification in 3 variable K map:

A

-two minterms in adjacent squares (vertically or horizontally, but not diagonally, adjacent) that are ORed together will cause a removal
of the dissimilar variable.
-Overlapping is allowed as it reduces literals.
-The number of adjacent squares that may be combined must always represent a
number that is a power of two, such as 1, 2, 4, and 8.
[ As more adjacent squares are combined, we obtain a product term with fewer literals.]
-1 square represents 1 minterm, giving a term with 3 literals.
-2 adjacent squares represent a term with 2 literals.
-4 adjacent squares represent a term with 1 literal.
-Eight adjacent squares encompass the entire map and produce a function that is always equal to 1.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

4 variable kmap:

A
  • 16 squares, The rows and columns are numbered in a Gray code sequence, with only one digit
    changing value between two adjacent rows or columns
  • to get the minterm of a square, concatenate the row number then column number.
  • For adjacent properties: the right n left edges of map touch and so do the topmost and bottom.
  • For Simplification:
    1 square - 4 literals
    2 adjacent sq = 3 literals
    4 sq = 2 literals
    8 sq = 1 literal
    16 sq: function = 1
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

Adjacent Squares

A

Adjacent squares are defined to be squares

next to each other.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

Prime Implicant

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

Essential Prime Implicant:

A

If a minterm in a square is covered by only one prime

implicant, that prime implicant is said to be essential.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

How to obtain prime Implicants of all the squares?

A

The prime implicants of a function can be obtained from the map by combining all
possible maximum numbers of squares.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

The process of finding the simplified expression from map:

A

The procedure for finding the simplified expression from the map requires that we
first determine all the essential prime implicants. The simplified expression is obtained
from the logical sum of all the essential prime implicants, plus other prime implicants
that may be needed to cover any remaining minterms not covered by the essential prime
implicants. Occasionally, there may be more than one way of combining squares, and
each combination may produce an equally simplified expression.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

The general form by which any Boolean function

is implemented when expressed in one of the standard forms:

A

AND gates are connected
to a single OR gate when in sum-of-products form;

OR gates are connected to a single
AND gate when in product-of-sums form

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

Simplify
given canonical form, sum of minterms:

and then express it in product of sums.

A
  1. on map mark one for corresponding minterms.
  2. Obtain a simplified expression( sum of products).
  3. Find F’ ( complement). [ Minterms with zero on map].
  4. complement that using De Morgans Law, and u have product of sums.

Heuristic Summary:
Remember maxterms complement of minterms?
So maxterms have 0’s unprimed and 1’s primed.
Now using that, from the map, combine maxterms with zero and u have it.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

how to handle a function expressed in Product of sum form?

A

Find its complement. F’. Due to De Morgans law it will be in form sum of products. Form its map and now combine minterms who show zero to get F in simplified and sum of products form.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

F (x, y, z) =PRODUCT OF (0, 2, 5, 7)

simplify this?:

A

U can form a map from this, start marking 0’s in those squares listed in the function.
Remember in truth table
the 1’s of the function represent the minterms and the 0’s represent the maxterms.
Once the 1’s and 0’s are marked, the function can be
simplified in either one of the standard forms. For the sum of products, we combine
the 1’s to obtain
F = x’z + xz’
For the product of sums, we combine the 0’s to obtain the simplified complemented
function
F’ = xz + x’z’
which shows that the exclusive-OR function is the complement of the equivalence function.
Taking the complement of F, we obtain the simplified function in
product-of-sums form:
F = (x + z)(x + z) .

21
Q

incompletely specified functions:

A

Functions that have unspecified outputs for

some input combinations are called incompletely specified functions.

22
Q

don’t-care conditions:

A

In most applications, we simply don’t care what value is assumed by the function for the unspecified
minterms.
These don’t-care conditions can be used on a map to provide
further simplification of the Boolean expression.
A don’t-care minterm is a combination of variables whose logical value is not specified.
To distinguish the don’t-care condition from 1’s and
0’s, an X is used
When simplifying the function, we can choose
to include each don’t-care minterm with either the 1’s or the 0’s, depending on which
combination gives the simplest expression.

23
Q

Nand as a universal gate, because any logic circuit can be implemented with it.
show that the logical operations of AND, OR, and complement can
be obtained with NAND gates alone.
How to do that?

A

A convenient way to implement a Boolean function with NAND gates is to obtain
the simplified Boolean function in terms of Boolean operators and then convert the
function to NAND logic
NAND : (pq)’
1. The complement
operation is obtained from a one-input NAND gate that behaves exactly like an inverter.
2. The AND operation requires two NAND gates. The first produces the NAND operation
and the second inverts the logical sense of the signal.
3. The OR operation is achieved
through a NAND gate with additional inverters in each input. [total 3] [ p + q = (p’q’)’ ]

24
Q

Nand Graphic Symbol:

A

1.The AND-invert symbol
2.Inver Or
symbol that is preceded by a bubble in each input.
[x’ + y’ + z’ = (xyz)’]

both symbols in same diagram: Mixed Notation.

25
Q

Two Level Implementation:

The implementation of Boolean functions with NAND gates requires:

A

The implementation of Boolean functions with NAND gates requires that the functions
be in sum-of-products form.
Recall the graphics.

The procedure for obtaining the
logic diagram from a Boolean function is as follows:
1. Simplify the function and express it in sum-of-products form.
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. This procedure
produces a group of first-level gates.
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 secondlevel NAND gate.

26
Q

MultiLevel Implementation:

Nand

A
  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.
27
Q

Nor Implementation biggest Hack:

A

The NOR operation is the dual of the NAND operation. Therefore, all procedures and
rules for NOR logic are the duals of the corresponding procedures and rules developed
for NAND logic.

28
Q

NOR graphics:

A

The OR-invert
symbol defines the NOR operation as an OR followed by a complement. (x + y + z)’
The invert-AND
symbol complements each input and then performs an AND operation. x’y’z’ = (x + y + z)’

29
Q

2 level Implementation: NOR

From map also.

A

Requires function simplified in Product of sum form. Get it from the map by combining the 0’s and complementing.
A product-of-sums expression is implemented with a first level of OR gates that produce the sum terms
followed by a second-level AND gate to produce the product.
The transformation from
the OR–AND diagram to a NOR diagram is achieved by changing the OR gates to
NOR gates with OR-invert graphic symbols and 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.

30
Q

Multi Level Gate, NOR:

A

For the NOR case, we must convert
each OR gate to an OR-invert symbol and each AND gate to an invert-AND symbol.
Any bubble that is not compensated by another bubble along the same line needs an
inverter, or the complementation of the input literal.

The equivalent AND–OR diagram can be recognized from the NOR diagram by removing all the bubbles. To compensate for the bubbles in four inputs, it is necessary to
complement the corresponding input literals.

31
Q

Wired Logic:

A

Some (but not all) 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.

32
Q

Wired logic example:
open-collector TTL NAND
gates.

A

open-collector TTL NAND
gates, when tied together, perform wired-AND logic.
The AND gate is drawn with the lines
going through the center of the gate to distinguish it from a conventional gate. The
wired-AND gate is not a physical gate, but only a symbol to designate the function
obtained from the indicated wired connection.
F = (AB)’….(CD)’ = (AB + CD)’ = (A’ + B’)(C’ + D’)
and is called an AND–OR–INVERT function.

33
Q

AND–OR–INVERT

A

F = (AB)’….(CD)’ = (AB + CD)’ = (A’ + B’)(C’ + D’)

34
Q

OR-AND-INVERT

A

the NOR outputs of ECL gates can be tied together to perform a wired-OR
function. The logic function implemented by the circuit of Fig. 3.26 (b) is
F = (A + B)’ + (C + D)’ = [(A + B)(C + D)]’
and is called an OR–AND–INVERT function.

35
Q

Degenrate forms meaning?

A

Eight out of 16 two level combinations are said to be degenerate forms because they degenerate to a single operation.

36
Q

AND OR INVERT IMPLEMENTATION:

A

POS Form
AND–NOR
NAND–AND [) requires an inverter for a single literal term. ]
F’ = Sum-of-products form by combining, 0’s in the map. [ And Or]
invert that to get F.
Revise graphics.’
implements function like F = (AB + CD + E)’

37
Q

OR AND Invert Implementation:

A

SOP Form
1. Or Nand
2. Nor Or [) requires an inverter for a single literal term.]
F’ = Product-of-sums
form by combining 1’s in the map and then complementing.
Invert F’ to get F.

38
Q

7 XOR properties:

A 
x ⊕ 0 = x
x ⊕ 1 = x'
x ⊕ x = 0
x ⊕ x' = 1
x ⊕ y' = x' ⊕ y = (x ⊕ y)'
Commutative
Associative
39
Q

Exclusive NOR?

A

Equivalence, complement of Exclusive OR.

40
Q

Implement ⊕ using and,or, inverters ;

just nands:

A

4 nands

and look at graphics.

41
Q

Generalise the n variable exclusive Or function:

A 
an n -variable exclusive-OR
function is an odd function defined as the logical sum of the 2^n / 2 minterms whose binary
numerical values have an odd number of 1’s.
42
Q

3 input XOR and equivalence implementations and maps:

Complement of odd function? [relate it ]

A

Map:
it will be of checkboard form for both.
in XOR: minterm 111 (7) will have one marked and in equivalence minterm 000 will be marked as 1.
Implementations:
1. XOR: by cascading XOR gates, look at the graphic.
2. Equivalence: replace the output by exclusive nor gate(just add a bubble).
Complement of odd function(XOR) is even (equivalence).

43
Q

XOR Applications:

A
  1. Arithmetic
  2. Error detection code.
  3. Correction Codes.
44
Q

Parity Bit:

A

A parity bit is an extra

bit included with a binary message to make the number of 1’s either odd or even.

45
Q

Parity Generator:

Parity checker:

A

The circuit that generates the parity bit in the transmitter is called
a parity generator.
The circuit that checks the parity in the receiver is called a parity
checker.

46
Q

When is an error detected or receiving a message:

A

An error is detected if the checked parity does not correspond with the
one transmitted.

47
Q

Even parity

how? [truth table, circuit]

A

p is an odd function because it is equal to 1 for those minterms whose numerical values have
an odd number of 1’s. Therefore, P can be expressed as a three-variable exclusive-OR
function.
Concatenating P with the message we get even parity message to transmit.

48
Q

Parity check error: circuit and truth table..

A 
function C consists of the eight minterms with binary numerical values having an odd number of 1’s.
its map represents an odd function. The parity checker can be implemented with exclusiveOR gates:
C = x ⊕ y ⊕ z ⊕ P
its circuit will have  XOR gates. 2 in first level taking 4 inputs whose outputs will serve as input to the third XOR gate and give final output as C.

It is worth noting that the parity generator can be implemented with the circuit of
checker mentioned here. if the input P is connected to logic 0 and the output is marked with P . This is
because z { 0 = z, causing the value of z to pass through the gate unchanged. The advantage of this strategy is that the same circuit can be used for both parity generation and
checking.

Digital Design Morris Mano (5 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions