Chapter 2: Combinational Logic Circuits Flashcards
What are the three basic logical operations?
AND, OR, and NOT
By what is AND represented in Boolean Algebra?
By a dot (or the absence of an operator between variables)
By what is OR represented in Boolean Algebra?
+
By what is NOT represented in Boolean Algebra?
By a bar over the variable
When is X AND Y true (or 1)?
Only when both, X = 1 and Y = 1
When is X OR Y true (or 1)?
When X = 1 or when Y = 1 or when both are 1
When is NOT X true (or 1)?
When X = 0
How much Volt does the Apple M2 chip represent as a bit of 1?
1.1V
What are logic gates?
Electronic circuits that operate on one or more input signals to produce an output signal
What’s the electronic symbol for an AND gate?
IMAGE
What’s the electronic symbol for an OR gate?
IMAGE
What’s the electronic symbol for a NOT gate?
IMAGE
What’s another name given to a NOT gate?
Inverter
What is a gate delay?
It is the length of time it takes for an input change to result in the corresponding output change
What does NAND represent?
The complement of the AND operation (NOT-AND)
What does NOR represent?
The complement of the OR operation (NOT-OR)
When is X NAND Y true (or 1)?
When any of the following cases are true:
1) X = 0 and Y = 0
2) X = 0 and Y = 1
3) X = 1 and Y = 0
When is X NOR Y true (or 1)?
Only when X = 0 and Y = 0
What is XOR?
The exclusive-OR, which excludes the combination with both X and Y equal to 1
What is XNOR?
The complement of the XOR
Why is the XOR also called the odd function?
Because the output of XOR is true (or 1) when the number of true (or 1) inputs is odd
What is Boolean algebra?
An algebra dealing with binary variables and logic operations
In Boolean algebra, what is X + 0?
X
In Boolean algebra, what is X * 1?
X
In Boolean algebra, what is X + 1?
1
In Boolean algebra, what is X * 0?
0
In Boolean algebra, what is X + X?
X
In Boolean algebra, what is X * X?
X
In Boolean algebra, what is X + NOT(X)?
1
In Boolean algebra, what is X * NOT(X)?
0
In Boolean algebra, what is NOT(NOT(X))?
X
In Boolean algebra, what are the commutative laws?
1) X + Y = Y + X
2) XY = YX
In Boolean algebra, what are the associative laws?
1) X + (Y + Z) = (X + Y) + Z = X + Y + Z
2) X(YZ) = (XY)Z = XYZ
In Boolean algebra, what are the distributive laws?
1) X(Y + Z) = XY + XZ
2) X + YZ = (X + Y)(X + Z)
In Boolean algebra, what are DeMorgan’s laws?
1) NOT(X + Y) = NOT(X) * NOT(Y)
2) NOT(X * Y) = NOT(X) + NOT(Y)
What are the four main reasons of simplifying digital circuits?
1) Faster operations
2) Less costs
3) Lower gate delay
4) Less power consumption
Simplify X + XY to one literal
X
Simplify XY + X*NOT(Y) to one literal
X
Simplify X + NOT(X)*Y to two literals
X + Y
Simplify X(X + Y) to one literal
X
Simplify (X + Y)(X + NOT(Y)) to one literal
X
Simplify X * (NOT(X) + Y) to two literals
XY
What is the Consensus theorem?
XY + NOT(X)*Z + YZ = XY + NOT(X) * Z
What is the dual of a Boolean expression?
It is simply the same expression just that * is replaced with + and + is replaced with *
What is the complement of a Boolean function?
It is the NOT of the function or the function inverted
What is a simple method of obtaining the complement of a Boolean function?
Take the dual of the function and complement each literal
What are standard forms of Boolean functions?
It is a specific way of writing Boolean expressions to simplify them
What is a minterm?
A product term in which all the variables appear exactly once, either complemented or uncomplemented
What does a minterm represent?
It represents exactly one combination of binary variable values in the truth table, where the value of the Boolean function is 1 for that combination and 0 for all others
What is a maxterm?
A sum term that contains all the variables exactly once, either in complemented or uncomplemented form
The value of a max term represents what?
The value of a maxterm is 0 for the corresponding combination and 1 for all other combinations
How can a Boolean function be represented algebraically using minterms?
It can be represented by forming the logical sum of all the minterms that produce a 1 in the function
What is sum-of-product form?
A logical sum of products (or minterms)
What is a two-level implementation (or two-level circuit)?
It is a circuit with two levels of logic gates (f.ex. sum-of-products or product-of-sums)
If you can describe your circuit as a sum of products or a product of sums you can always design what kind of circuit?
A two-level implementation or two-level circuit
Why do we prefer two-level circuits over three-level circuits?
Because it is faster as it has two times the gate delay while three-level circuits have 3 times the gate delay
What is product-of-sum form?
A logical product of sums (or maxterms)
What is the map method of optimizing Boolean functions called?
Karnaugh map (K-map)
What does each square in a K-map represent?
One row of the truth table
The number of squares in each K-map is equal to the number of what in the corresponding function?
Minterms
Given two variables X and Y, how many squares does our K-map need?
4
What binary code is used to describe the squares when using K-maps?
Gray code
When drawing largest rectangles in a K-map what is the restriction?
The rectangles are constricted to contain numbers of squares that are powers of 2 (ie. 1, 2, 4, 8, 16, …)
What is the main goal while using K-maps?
To find the fewest (largest) rectangles that include or cover all of the squares marked with 1s
How many squares does a three-variable K-map need?
8
How many squares does a four-variable K-map need?
16
What are prime implicants?
A group of squares or rectangles made up of bunch of adjacent minterms (i.e. all possible (largest!!) groups formed in the K-map)
What are essential prime implicants?
Groups that cover at least one minterm (or square) in the K-map that cannot be covered by any other prime implicant
What is the special property of essential prime implicants?
In the simplified expression the essential prime implicants have to occur, there is no way to leave them out
What are the two cases in which don’t-care conditions occur?
1) The input combinations never occur
2) They occur, but we do not care what the outputs are in response to these combinations
What are don’t-care conditions?
The unspecified minterms of a function
How do we denote don’t-care conditions in the K-map?
With an X
What is the symbol of the XOR?
An encircled plus sign
What is X XOR Y equivalent to?
X XOR Y = X * NOT(Y) + NOT(X) * Y
What is propagation delay?
The time required for a change in value of a signal to propagate from input to output of a logic gate
The operating speed of a circuit is in what way related to the longest propagation delay through the gates of the circuit?
Inversely
What is the high-to-low propagation time?
The time it takes for a change from 0 to 1 at the input to be shown at the output
What is the low-to-high propagation time?
The time it takes for a change from 1 to 0 at the input to be shown at the output
