Chapter 3: Combinational Logic Design

Question 1

What is an universal logic gate?

Answer 1

A gate type that alone can be used to implement all possible Boolean functions (it is said to be functionally complete)

Question 2

What gates are universal gates?

Answer 2

The NAND and NOR gates

Question 3

How can you obtain a NOT gate from a NAND gate?

Answer 3

IMAGE

Question 4

How can you obtain an AND gate from two NAND gates?

Answer 4

IMAGE

Question 5

How can you obtain an OR gate from three NAND gates?

Answer 5

IMAGE

Question 6

What are the three steps to implement a given digital circuit with only NAND gates?

Answer 6

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

Question 7

What is decoding?

Answer 7

The conversion of an n-bit input code to an m-bit output code with n <= m <= 2^n

Question 8

What is a decoder?

Answer 8

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

Question 9

What is a 1-to-2-line decoder?

Answer 9

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

Question 10

How can the function, n-to-m-line decoding with enabling, be implemented?

Answer 10

By attaching m enabling circuits to the AND gates leading to the decoder outputs

Question 11

How can you use decoders to form a sum-of-minterms implementation?

Answer 11

By using a decoder to generate the minterms and combining them with an external OR gate to form the sum-of-minterms implementation

Question 12

What is the truth table for a 1-bit binary adder?

Answer 12

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

Question 13

What is an encoder?

Answer 13

A digital function that performs the inverse operation of a decoder

Question 14

How many input lines and output lines does an encoder have?

Answer 14

2^n (or fewer) input lines and n output lines

Question 15

What is a priority encoder?

Answer 15

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

Question 16

What is a multiplexer (MUX)?

Answer 16

A combinational circuit that selects binary information from one of many input lines and directs the information to a single output line

Question 17

How many select inputs does a 2-to-1-line multiplexer need?

Answer 17

Only 1

Question 18

Given a 2-to-1-line multiplexer with input I0 and input I1. When is output Y = 1 when S = 0?

Answer 18

When S = 0 the output Y is exactly equivalent to the input I0. So, Y is 1 whenever I0 is 1.

Question 19

Given a 2-to-1-line multiplexer with input I0 and input I1. When is output Y = 1 when S = 1?

Answer 19

When S = 1 the output Y is exactly equivalent to the input I1. So, Y is 1 whenever I1 is 1.

Question 20

What is the circuit symbol for a multiplexer?

Answer 20

IMAGE

Question 21

A multiplexer is also called what?

Answer 21

Data selector

Question 22

What kind and how many multiplexers do we need to implement a 1-bit binary adder with them?

Answer 22

We need two 8-to-1 multiplexers (implementation with two 4-to-1 multiplexers is also possible)

Question 23

What is an arithmetic circuit?

Answer 23

A combinational circuit that performs arithmetic operations such as addition, subtraction, multiplication, and division with binary numbers

Question 24

What is a half adder?

Answer 24

A combinational circuit that performs the addition of two bits

Question 25

How does the circuit for a half adder look like?

Answer 25

IMAGE

Question 26

What is a full adder?

Answer 26

A combinational circuit that performs the arithmetic sum of three input bits (two bits and a carry)

Question 27

What is the Boolean function of the sum bit of a full adder?

Answer 27

X XOR Y XOR Z

Question 28

What is the Boolean function of the carry bit of a full adder?

Answer 28

Z*(X XOR Y) + XY

Question 29

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?

Answer 29

Because we need to compute X XOR Y anyways for the sum bit

Question 30

What is a parallel binary adder?

Answer 30

A digital circuit that produces the arithmetic sum of two binary numbers using only combinational logic

Question 31

Why is the parallel binary adder commonly referred to as a ripple carry adder?

Answer 31

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

Question 32

An n-bit ripple carry adder requires how many full adders?

Answer 32

n

Question 33

If a binary number is signed, then the leftmost bit represents what?

Answer 33

The sign (+ if 0 and - if 1)

Question 34

How is the signed 1s complement of a binary number obtained?

Answer 34

By changing all 1s to 0s and all 0s to 1s

Question 35

How is the signed 2s complement of a binary number obtained?

Answer 35

By adding 1 to the 1s complement

Question 36

What is 9 in binary, -9 in 1s complement and -9 in 2s complement?

Answer 36

Binary: 1001
1s complement: 0110
2s complement: 0111

Question 37

How do you convert a 2s complement number back to regular binary?

Answer 37

1) Do the 1s complement
2) Add 1

Question 38

What happens if overflow occurs when converting to 2s complement?

Answer 38

The overflow bit is simply discarded

Question 39

What is the major drawback of signed magnitude number system as opposed to the signed complement number system?

Answer 39

The signed magnitude number system has a negative and a positive zero

Question 40

In what special case can we implement a multiplication circuit with only wiring (no gates)?

Answer 40

When we multiply a binary number by a constant and the constant is a power of 2

Question 41

Multiplication of a binary number by a binary number which is a power of 2 (2 to the power of some i) is called?

Answer 41

Left shift by i positions