Chapter 3: Combinational Logic Design Flashcards
What is an universal logic gate?
A gate type that alone can be used to implement all possible Boolean functions (it is said to be functionally complete)
What gates are universal gates?
The NAND and NOR gates
How can you obtain a NOT gate from a NAND gate?
IMAGE
How can you obtain an AND gate from two NAND gates?
IMAGE
How can you obtain an OR gate from three NAND gates?
IMAGE
What are the three steps to implement a given digital circuit with only NAND gates?
1) Replace each AND gate and OR gate with its equivalent circuit using NAND gates and NOT gates
2) Cancel all inverter pairs
3) Replace each inverter with its equivalent NAND gate
What is decoding?
The conversion of an n-bit input code to an m-bit output code with n <= m <= 2^n
What is a decoder?
A decoder is a combinational circuit with an n-bit binary code applied to its inputs and an m-bit binary code appearing at the outputs
What is a 1-to-2-line decoder?
A combinational circuit that decodes the single input 0 to the two outputs 1,0 and the single input 1 to the two outputs 0,1
How can the function, n-to-m-line decoding with enabling, be implemented?
By attaching m enabling circuits to the AND gates leading to the decoder outputs
How can you use decoders to form a sum-of-minterms implementation?
By using a decoder to generate the minterms and combining them with an external OR gate to form the sum-of-minterms implementation
What is the truth table for a 1-bit binary adder?
X Y Z C S
0 0 0 0 0
0 0 1 0 1
0 1 0 0 1
0 1 1 1 0
1 0 0 0 1
1 0 1 1 0
1 1 0 1 0
1 1 1 1 1
What is an encoder?
A digital function that performs the inverse operation of a decoder
How many input lines and output lines does an encoder have?
2^n (or fewer) input lines and n output lines
What is a priority encoder?
A combinational circuit that implements a priority function, which means if two or more inputs are equal to 1 at the same time, the input having the highest priority takes precedence
What is a multiplexer (MUX)?
A combinational circuit that selects binary information from one of many input lines and directs the information to a single output line
How many select inputs does a 2-to-1-line multiplexer need?
Only 1
Given a 2-to-1-line multiplexer with input I0 and input I1. When is output Y = 1 when S = 0?
When S = 0 the output Y is exactly equivalent to the input I0. So, Y is 1 whenever I0 is 1.
Given a 2-to-1-line multiplexer with input I0 and input I1. When is output Y = 1 when S = 1?
When S = 1 the output Y is exactly equivalent to the input I1. So, Y is 1 whenever I1 is 1.
What is the circuit symbol for a multiplexer?
IMAGE
A multiplexer is also called what?
Data selector
What kind and how many multiplexers do we need to implement a 1-bit binary adder with them?
We need two 8-to-1 multiplexers (implementation with two 4-to-1 multiplexers is also possible)
What is an arithmetic circuit?
A combinational circuit that performs arithmetic operations such as addition, subtraction, multiplication, and division with binary numbers
What is a half adder?
A combinational circuit that performs the addition of two bits
How does the circuit for a half adder look like?
IMAGE
What is a full adder?
A combinational circuit that performs the arithmetic sum of three input bits (two bits and a carry)
What is the Boolean function of the sum bit of a full adder?
X XOR Y XOR Z
What is the Boolean function of the carry bit of a full adder?
Z*(X XOR Y) + XY
Why don’t we use the boolean expression XZ + XY + YZ for the carry bit of a full adder in real life implementations even though it is simpler then the Z(X XOR Y) + XY that is used?
Because we need to compute X XOR Y anyways for the sum bit
What is a parallel binary adder?
A digital circuit that produces the arithmetic sum of two binary numbers using only combinational logic
Why is the parallel binary adder commonly referred to as a ripple carry adder?
Because a 1 carry may appear near the least significant bit of the adder and can propagate through many full adders to the most significant bit, just as a wave ripples outward from a pebble dropped in a pond
An n-bit ripple carry adder requires how many full adders?
n
If a binary number is signed, then the leftmost bit represents what?
The sign (+ if 0 and - if 1)
How is the signed 1s complement of a binary number obtained?
By changing all 1s to 0s and all 0s to 1s
How is the signed 2s complement of a binary number obtained?
By adding 1 to the 1s complement
What is 9 in binary, -9 in 1s complement and -9 in 2s complement?
Binary: 1001
1s complement: 0110
2s complement: 0111
How do you convert a 2s complement number back to regular binary?
1) Do the 1s complement
2) Add 1
What happens if overflow occurs when converting to 2s complement?
The overflow bit is simply discarded
What is the major drawback of signed magnitude number system as opposed to the signed complement number system?
The signed magnitude number system has a negative and a positive zero
In what special case can we implement a multiplication circuit with only wiring (no gates)?
When we multiply a binary number by a constant and the constant is a power of 2
Multiplication of a binary number by a binary number which is a power of 2 (2 to the power of some i) is called?
Left shift by i positions
