Problem Set 2

Source: DL_P2.pdf Revision: 2/3/19

Warning

The overline symbol (A̅) may be hidden in Firefox if the default zoom level is used. The symbol below should have an overline like A̅. De- or increase the zoom level if you encounter any Boolean equations.

\( \overline A \)

1

Complete the truth tables below.

---

AND

A	B	F
0	0	0
0	1	0
1	0	0
1	1	1

OR

A	B	F
0	0	0
0	1	1
1	0	1
1	1	1

XOR

A	B	F
0	0	0
0	1	1
1	0	1
1	1	0

INV

A	F
0	1
1	0

2

Sketch non-minimized SOP and POS circuits for the truth table below.

A	B	C	F
0	0	0	0
0	0	1	1
0	1	0	0
0	1	1	1
1	0	0	1
1	0	1	1
1	1	0	0
1	1	1	0

---

SOP:

For SOP we look at the conditions which lead to a 1 and combine them using OR:

\( F = ( \overline{A} \cdot \overline{B} \cdot C ) + ( \overline{A} \cdot B \cdot C ) + ( A \cdot \overline{B} \cdot \overline{C} ) + ( A \cdot \overline{B} \cdot C ) \)

POS:

For POS we look at the conditions which lead to a 0. In an AND chain we only get a 1 if all the components are 1, otherwise zero. So if none of these conditions is 1 then the output is 1. So we should make sure that the individual conditions that lead to a 0 should lead to 0 if the condition is 1. We can achieve that by negating the condition:

Let C be the a condition that must lead to a 0 or must be False and A and B the inputs: \( C = A \cdot B = \mathrm{False} \Rightarrow \overline{A \cdot B} = \overline{\mathrm{False}} \Rightarrow \overline{A} + \overline{B} = \mathrm{True} \)

\( F = ( A + B + C ) \cdot ( A + \overline{B} + C ) \cdot ( \overline{A} + \overline{B} + C ) \cdot ( \overline{A} + \overline{B} + \overline{C} ) \)

3

Complete the truth tables and provide minterm equations.

3.1

\(F = \overline{A} \cdot B + C \)

A	B	C	F
0	0	0
0	0	1
0	1	0
0	1	1
1	0	0
1	0	1
1	1	0
1	1	1

---

A	B	C	F
0	0	0	0
0	0	1	1
0	1	0	1
0	1	1	1
1	0	0	0
1	0	1	1
1	1	0	0
1	1	1	1

\( F = ( \overline{A} \cdot \overline{B} \cdot C ) + ( \overline{A} \cdot B \cdot \overline{C} ) + ( \overline{A} \cdot B \cdot C ) + ( A \cdot \overline{B} \cdot C ) + ( A \cdot B \cdot C ) \)

3.2

\( F = A \cdot B \cdot \overline{C} + B \cdot C \)

A	B	C	F
0	0	0
0	0	1
0	1	0
0	1	1
1	0	0
1	0	1
1	1	0
1	1	1

---

A	B	C	F
0	0	0	0
0	0	1	0
0	1	0	0
0	1	1	1
1	0	0	0
1	0	1	0
1	1	0	1
1	1	1	1

\( F = ( \overline{A} \cdot B \cdot C ) + ( A \cdot B \cdot \overline{C} ) + ( A \cdot B \cdot C ) \)

3.3

\(F = B \cdot \overline{C} + \overline{B} \cdot C \)

A	B	C	F
0	0	0
0	0	1
0	1	0
0	1	1
1	0	0
1	0	1
1	1	0
1	1	1

---

A	B	C	F
0	0	0	0
0	0	1	1
0	1	0	1
0	1	1	0
1	0	0	0
1	0	1	1
1	1	0	1
1	1	1	0

\( F = ( \overline{A} \cdot \overline{B} \cdot C ) + ( \overline{A} \cdot B \cdot \overline{C} ) + ( A \cdot \overline{B} \cdot C ) + ( A \cdot B \cdot \overline{C} ) \)

4

Write the number of transistors required for each logic gate below inside the gate symbol, and then write the logic gate name below the symbol.

Note

The number of transistors can vary dependent on the semiconductor technology. Most likely the author means the number of transistor required in CMOS technology.

4.1

---

When we push the bubbles to the output, we get a NOR:

We need four transistors.

If we have two inputs, remember that we can connect two NFET transistors in series to the ground to build a logical gate. To have a logical zero, we have to activate them both. This corresponds to the NAND logic. In CMOS we complement the NFETs with PFETs. NOR is like NAND an additional logic gate that we can build using four transistors. In NOR we have two NFETs in parallel to the ground.

Besides NOR and NAND we can also build a NOT using a single NFET to the ground and complementing that. If we activate the NFET the gate will output a zero, and thus invert our input. We need two transistors in total.

4.2

---

This is an OR. We need six transistors.

In CMOS the logic gates that we can build using minimal number of transistors are NOT, NAND and NOR. We build other functions using these elementary gates.

To get an OR, we have to connect an additional inverter (NOT) after the NOR. So we need \(4+2=6\) transistors.

4.3

---

Three input NAND. We need six transistors.

In 4.1 we already explained how to build a NAND. Instead of two inputs now we have three inputs. So we have three NFETs in series connected to the ground and these transistors are complemented with three PFETs above which are in parallel to the supply rail.

4.4

---

This is a NOT. As discussed in 4.1 we need two transistors.

4.5

---

This is a two input NOR, we need four transistors. Same as 4.1.

4.6

---

After bubble-pushing we get a three input NAND. We need six transistors, similar to ps02.4.3.

5

assign F = (A & ~B) | (~A & ~C) | (A & B & C)

1. Complete the following truth table based on the Verilog assignment statement

2. Write the minterm equation for F.

3. Write the maxterm equation for F.

A	B	C	F
0	0	0
0	0	1
0	1	0
0	1	1
1	0	0
1	0	1
1	1	0
1	1	1

---

We can fill the truth table from the Verilog line above by extending the first two products with the missing third variable which can be both 0 and 1. In other words, we do not care what C and B are in the first and second term, respectively.

A	B	C	F
0	0	0	1
0	0	1	0
0	1	0	1
0	1	1	0
1	0	0	1
1	0	1	1
1	1	0	0
1	1	1	1

Minterm equation:

\( F = \mathrm{m}_0 + \mathrm{m}_2 + \mathrm{m}_4 + \mathrm{m}_5 + \mathrm{m}_7 \)

or in short:

\( F = \sum_{n=\left\{0,2,4,5,7\right\}} \mathrm{m}_n \)

If we wanted to write the terms out:

\( F = ( \overline{A} \cdot \overline{B} \cdot \overline{C} ) + ( \overline{A} \cdot B \cdot \overline{C} ) + ( A \cdot \overline{B} \cdot \overline{C} ) + ( A \cdot \overline{B} \cdot C ) + ( A \cdot B \cdot C ) \)

Maxterm equation:

\( F = \prod_{n=\left\{1,3,6\right\}} \mathrm{m}_n \)

If we wanted to write all the terms out:

\( F = ( A + B + \overline{C} ) \cdot ( A + \overline{B} + \overline{C} ) \cdot ( \overline{A} + \overline{B} + C ) \)

6

Sketch circuits and write Verilog assignment statements for the following logic equations.

Note

Sketching circuits based on logic gate symbols is enough. You can also draw circuits based on CMOS for a challenge.

6.1

\( F = \overline{A} \cdot B \cdot C + A \cdot \overline{B} \cdot \overline{C} + \overline{A} \cdot C \)

---

module m (output F, input A,B,C);
assign F = ~A & B & C | A & ~B & ~C | ~A & C;
endmodule

CMOS circuit:

6.2

\( F = \overline{ \overline{A} \cdot B \cdot \overline{C} } + \overline{ A + B } \)

---

module m (output F, input A,B,C);
assign F = ~(~A & B & ~C) | ~(A | B);
endmodule

6.3

\( F = ( A + \overline{B} ) \cdot \overline{ \overline{B + C} \cdot \overline{A} } \)

---

module m (output F, input A,B,C);
assign F =
	 (A | ~B) &
	~(~(~B | C) & A);
endmodule

6.4

\( F = \sum \mathrm{m}(1, 2, 6) \)

---

This is a sum of three minterms (we have three arguments) with three inputs (the arguments go up to 6, so we have \(\lceil \log_{2} 6 \rceil = 3\) inputs).

Why three inputs? Because the output is obviously not dependent on further (e.g., fourth, fifth) inputs as the output apparently does not change if these further inputs are high (otherwise we would have higher numbers than 7 in our F)

module m (output F, input A,B,C);
assign F = (~A & ~B &  C) |
           (~A &  B & ~C) |
           ( A &  B & ~C);
endmodule

6.5

\( F = \prod \mathrm{M}(0, 7) \)

---

This is a product of two maxterms with three inputs.

module m (output F, input A,B,C);
assign F = ( A &  B &  C) &
           (~A & ~B & ~C);
endmodule

7

In a logic function with \(n\) inputs, there are \(2𝑛\) unique combinations of inputs and \(2^{2^𝑛}\) possible logic functions. The table below has four rows that show the four possible combinations of two inputs (\(2^2 = 4\)), and 16 output columns that show all possible two-input logic function (\(2^{2^2}=16\)). Six of these output columns are associated with common logic functions of two variables.

• Circle the six columns

• label them with the appropriate logic gate name

• Draw the circuit symbols for the functions represented.

• A table like the one above for 3 inputs would need _________ rows and _________ columns.

• A table like the one above for 4 inputs would need _________ rows and _________ columns.

• A table like the one above for 5 inputs would need _________ rows and _________ columns

---

The six common logic functions with two variables:

1. NAND: Column 8

2. AND: 9

3. NOR: 2

4. OR: 15

5. XOR: 6

6. XNOR: 10

ANSI, IEC and DIN circuit symbols

We discussed the following in the exercises Exercise 45 and Exercise 46:

• A table like the one above for 3 inputs would need \(2^3 = 8\) rows and \(2^8 = 256\) columns.

• A table like the one above for 4 inputs would need \(2^4 = 16\) rows and \(2^{16} = 64\,\mathrm{Ki}\) columns.

• A table like the one above for 5 inputs would need \(2^5 = 32\) rows and \(2^{32} = 4\,\mathrm{Gi}\) columns

8

Complete truth tables for the circuits shown below.

8.1

---

The straightforward approach is that we calculate F dependent on the inputs by propagating the individual values of the inputs for each of the eight conditions. This is a input to output approach.

An faster alternative is that we propagate from the output to the input. We have a NAND connected to the output and a NAND can be only 0 if the inputs are both 1. Now we have two gates which must output a 0:

1. NOR: If NOR must deliver a 1, we should think about the conditions when OR outputs 0. Both A and B must be 0.

2. OR with a negated C. If OR must output a 1, then the inputs ~C and B can be 00, 10, 01.

According to 1. A and B both must be 0, and if we consider 2., then C can be both 0 and 1

Now we can list all the input conditions for the inputs where F is 0.

A	B	C
0	0	0
0	0	1

For the rest of the conditions F must be 1.

A	B	C	F
0	0	0	0
0	0	1	0
0	1	0	1
0	1	1	1
1	0	0	1
1	0	1	1
1	1	0	1
1	1	1	1

Note

Did you notice that we solved the problem using SOP logic by compiling the conditions which must occur to get a 1?

8.2

---

Let us use the same output-to-input approach. This time we have an OR at our output, so consider the case when OR is 0. If OR must output 0, then all the ANDs must output 0. ANDs output 0 if their inputs are not 1, so we get the following statements for the three ANDs from top to bottom.

1. ABC must not be 001.

2. BC must not be 10.

3. CA must not be 11.

If these statements are true, then F will Using these statements we can write:

A	B	C	F
0	0	1	0
0,1	1	0	0
1	1	1	0

In the rest of the conditions F must be 1. In summary:

A	B	C	F
0	0	0	1
0	0	1	0
0	1	0	0
0	1	1	1
1	0	0	1
1	0	1	1
1	1	0	0
1	1	1	0

Note

Did you notice that we solved the problem using POS logic by compiling the cases which must not occur to get a 1?

9

1. Show the total transistor count and gate/input number for the circuits below.

2. Sketch equivalent circuits using NAND gates that use fewer transistors (do not minimize the circuits).

G:

module m (output G, input A,B,C,D);
assign G = ~A & B & C | A & C | C & ~D;
endmodule

F:

module m (output F, input A,B,C);
assign F = ~A & B | B & ~C;
endmodule

---

Total transistor counts:

• G

  • 2x inverter: \(2 \cdot 2 = 4\)

  • 1x AND with three inputs: \(6+2=8\)

  • 2x AND with two inputs: \(2 (4+2) = 12\)

  • 1x OR with three inputs: \(6+2=8\)

  • Total: 32

• F

  • 2x inverter: \(2 \cdot 2 = 4\)

  • 2x AND with two inputs: \(2 (4+2) = 12\)

  • 1x OR with two inputs: \(4+2=6\)

  • Total: 22

Gate/input counts:

• G: 4 gates / 10 inputs

• F: 3 gates / 6 inputs

Equivalent circuits using NAND gates:

We can double negate the circuits and use De Morgan’s law to get NAND gates.

G:

module m (output G, input A,B,C,D);
// Original:
assign G = ~A & B & C | A & C | C & ~D;
// Double negation
assign G = ~~(A & B & C | A & C | C & ~D);
// De Morgan on the OR gate
// in other words pushing one bubble through OR
assign G = ~( ~(A & B & C) & ~(A & C) & ~(~C & ~D) );
endmodule

Now we have only NAND gates and inverters.

Same for F:

module m (output F, input A,B,C);
// Original:
assign F = ~A & B | B & ~C;
// Double negation and De Morgan
assign F = ~( ~(~A & B) & ~(B & ~C) );
endmodule

Let us calculate the transistor counts to compare them:

• G

  • 2x inverter: \(2 \cdot 2 = 4\)

  • 2x NAND with three inputs: \(2 \cdot 6 = 12\)

  • 2x NAND with two inputs: \(2 \cdot 4 = 8\)

  • Total: 24 (compared to 32)

• F

  • 2x inverter: \(2 \cdot 2 = 4\)

  • 3x NAND with two inputs: \(3 \cdot 4 = 12\)

  • Total: 16 (compared to 22)

Finally the gate/input counts:

• G: 4 gates / 10 inputs (compared to 4/10)

• F: 3 gates / 6 inputs (compared to 3/6)

The gate/input counts do not change but the transistor count changes significantly.

10

Simplify the following using Boolean algebra

10.1

module m (output Y, input A,B,C,D);
assign Y = (A & B & ~C & D) | (A & C) | (~C & ~D) | (A & ~B & ~C & D) | (~A & C);
end module

---

Note

& has the same precedence as | in Verilog. Source; Systemverilog 2017 – Chapter 11.3.2

module m (output Y, input A,B,C,D);
// Original
assign Y =
	(A & B & ~C & D) |
	(A & C) |
	(~C & ~D) |
	(A & ~B & ~C & D) |
	(~A & C);
// Factorize and separate (~C & D) from the first, third and fourth term
// according to the associative law and put them to the front according to the
// commutative law
assign Y =
	(~C & D) & (A & B) |
	(A & C) |
	(~C & ~D) |
	(~C & D) & (A & ~B) |
	(~A & C);
// Reverse the distribution of the multiplicative (ANDed) term (~C & D) over
// additions (ORed)
assign Y =
	(~C & D) & ( (A & B) | (A & ~B) ) |
	(A & C) |
	(~C & ~D) |
	(~A & C);
// Use the same steps to factorize C from the second and fourth term
assign Y =
	(~C & D) & ( (A & B) | (A & ~B) ) |
	C & (A | ~A) |
	(~C & ~D);
// Use complementation for OR in the second term (X OR NOT(X) is always true)
assign Y =
	(~C & D) & ( (A & B) | (A & ~B) ) |
	C & 1 |
	(~C & ~D);
// Use identity rule: (X AND 1)=X
assign Y =
	(~C & D) & ( (A & B) | (A & ~B) ) |
	C |
	(~C & ~D);
// Reverse distribution of A in the first term
assign Y =
	(~C & D) & ( A & (B | ~B) ) |
	C |
	(~C & ~D);
// Use complementation of OR and identity of AND on the same 
assign Y =
	(~C & D) & A |
	C |
	(~C & ~D);
// Factorize ~C and reverse its distribution on the first and third term
assign Y =
	~C ( (D & A) | ~D ) |
	C;
end module

10.2

\( Y = \overline{AB} + \overline{B + C} + \overline{B} \)

---

module m (output Y, input A,B,C,D);
// Original
assign Y =
	~(A & B) |
	~(B | C) |
	~B;
// De Morgan on the first and second term
assign Y = 
	(~A | ~B) |
	(~B & ~C) |
	~B;
// Getting rid of the parantheses on the first term
assign Y = 
	~A | 
	~B |
	(~B & ~C) |
	~B;
// Idempotence of OR in second and the fourth term
assign Y = 
	~A | 
	~B |
	(~B & ~C);
// Factorize ~B out of the second and the third (reverse distributive)
assign Y = 
	~A | 
	~B & (1 | ~C);
// Identity of OR in the second term
assign Y = 
	~A | 
	~B & ~C;
end module

11

Timing diagrams show circuit inputs and outputs as they change over time. In the figure below, the signals A and B come from push buttons that are pressed at different times (in the first time slice, neither A or B are pressed, in the second time slice, B is pressed but A is not, etc.).

Complete the timing diagrams to show how the various logic gates respond to their inputs.

---

• F1: NAND

• F2: NOR

• F3: NAND with ~B

• F4: OR

• F5: after bubble-pushing NOR

• F6: after bubble-pushing AND