# Problem Set 2
Source: [DL_P2.pdf](https://www.realdigital.org/downloads/aff2137e860009b66fec577fa2d37cee.pdf) Revision: 2/3/19
```{warning}
[The overline symbol (A̅) may be hidden in Firefox if the default zoom level is used](https://bugzilla.mozilla.org/show_bug.cgi?id=1741887). 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 |
(ps02.2)=
## 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](https://en.wikipedia.org/wiki/NAND_gate#Implementations). Most likely the author means the number of transistor required in CMOS technology.
```
(ps02.4.1)=
### 4.1
---
When we push the bubbles to the output, we get a `NOR`:
```{image} https://upload.wikimedia.org/wikipedia/commons/6/6c/NOR_ANSI.svg
:alt: ANSI Symbol for an NOR Gate
:target: https://commons.wikimedia.org/wiki/File:NOR_ANSI.svg
```
```{image} https://upload.wikimedia.org/wikipedia/commons/6/6d/NOR_IEC.svg
:alt: IEC Symbol for a NOR Gate
:target: https://commons.wikimedia.org/wiki/File:NOR_IEC.svg
```
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
```{image} https://upload.wikimedia.org/wikipedia/commons/4/42/OR_IEC.svg
:alt: IEC Symbol for an OR Gate
:target: https://commons.wikimedia.org/wiki/File:OR_IEC.svg
```
---
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.
(ps02.4.3)=
### 4.3
---
Three input `NAND`. We need six transistors.
In {ref}`ps02.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
```{image} https://upload.wikimedia.org/wikipedia/commons/b/bc/NOT_ANSI.svg
:alt: ANSI Symbol for a NOT Gate
:target: https://commons.wikimedia.org/wiki/File:NOT_ANSI.svg
```
```{image} https://upload.wikimedia.org/wikipedia/commons/e/ef/NOT_IEC.svg
:alt: IEC Symbol for a NOT Gate
:target: https://commons.wikimedia.org/wiki/File:NOT_IEC.svg
```
---
This is a `NOT`. As discussed in {ref}`ps02.4.1` we need two transistors.
### 4.5
```{image} https://upload.wikimedia.org/wikipedia/commons/6/6c/NOR_ANSI.svg
:alt: ANSI Symbol for an NOR Gate
:target: https://commons.wikimedia.org/wiki/File:NOR_ANSI.svg
```
```{image} https://upload.wikimedia.org/wikipedia/commons/6/6d/NOR_IEC.svg
:alt: IEC Symbol for a NOR Gate
:target: https://commons.wikimedia.org/wiki/File:NOR_IEC.svg
```
---
This is a two input `NOR`, we need four transistors. Same as {ref}`ps02.4.1`.
### 4.6
---
After bubble-pushing we get a three input `NAND`. We need six transistors, similar to `ps02.4.3`.
## 5
```verilog
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
$
---
```verilog
module m (output F, input A,B,C);
assign F = ~A & B & C | A & ~B & ~C | ~A & C;
endmodule
```
CMOS circuit:
```{image} problem-set-02.6.1_cmos_circuit.svg
:width: 1000
:height: 2000
:alt: handwritten solution
```
### 6.2
$ F =
\overline{ \overline{A} \cdot B \cdot \overline{C} } +
\overline{ A + B }
$
---
```verilog
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} }
$
---
```verilog
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`)
```verilog
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.
```verilog
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
1. `AND`: 9
1. `NOR`: 2
1. `OR`: 15
1. `XOR`: 6
1. `XNOR`: 10
[ANSI, IEC and DIN circuit symbols](https://commons.wikimedia.org/wiki/Logic_gates_unified_symbols)
We discussed the following in the exercises {ref}`why_16_logic_functions` and {ref}`how_many_functions_if_three_inputs`:
- 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 `AND`s must output `0`. `AND`s output `0` if their inputs are not `1`, so we get the following statements for the three `AND`s 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`?
```
(ps02p9_total_transistor_count)=
## 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:
```verilog
module m (output G, input A,B,C,D);
assign G = ~A & B & C | A & C | C & ~D;
endmodule
```
F:
```verilog
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:
```verilog
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:
```verilog
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
```verilog
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](https://ieeexplore.ieee.org/stampPDF/getPDF.jsp?tp=&arnumber=8299595#G16.1144877)
```
```verilog
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} $
---
```verilog
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`
![](problem-set-02.11_timing_diagram.svg)