Logic Synthesis

1. The truth table of the CMOS circuit contains 16 lines since there are 16 possible input combinations and 1 possible output bit:
$$\begin{matrix} A & B & C & D & F \\ \hline 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 1 & 1 \\ 0 & 1 & 0 & 0 & 1 \\ 0 & 1 & 0 & 1 & 1 \\ 0 & 1 & 1 & 0 & 1 \\ 0 & 1 & 1 & 1 & 1 \\ 1 & 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 1 & 0 \\ 1 & 1 & 0 & 0 & 1 \\ 1 & 1 & 0 & 1 & 0 \\ 1 & 1 & 1 & 0 & 1 \\ 1 & 1 & 1 & 1 & 0 \\ \hline \end{matrix}$$

2. The final boolean expression is: $$F = \overline{A(B+C)D}$$

1. The truth table for H is as follows: $$\begin{matrix} A & B & H \\ \hline 0 & 0 & 1\\ 0 & 1 & 1 \\ 1 & 0 & 0 \\ 1 & 1 & 1\\ \hline \end{matrix} $$


2. We begin by finding the expression of the topmost two circuits and applying de Morgan's law: $$\overline{A + \overline{B}} = \overline{A}B$$
   
   Then, we find the expression of the next pair, which is: $$AB$$ We combine this with the above using a NOR gate and reduce the result, $$\overline{\overline{A}B + AB} = \overline{B}$$
   
   Finally, we find the expression for the bottom two pairs, which is simply: $$A+B$$ Combining this with the above expression, we reduce and apply de Morgan's law: $$\begin{aligned} \overline{(A+B)\overline{B}} &= \overline{A \overline{B} + B \overline{B}} = \overline{A\overline{B}} = \overline{A} + B\\ \end{aligned}$$


3. The **contamination** delay is the path (from any input to any output) that results in the **shortest** time: `NOR2` + `NOR2` + `NAND2` = 5 + 5 + 5 = 15ns. The **propagation** delay is the path (from any input to any output) that results in the **longest** time: `AND2` + `NOR2` + `NAND2` = 50 + 30 + 30 = 110ns.

(a), (b), and (c) are all equivalent and represents the truth table.

$$Y = \bar{A}\bar{B}\bar{C} + \bar{A}BC + A \bar{B} C+ AB\bar{C}$$ This expression can be computed easily after you create a truth table first out of the ROM.

**ROM [3]** represents half-adder functionality.

`Y`'s output shows a `XOR(A,B)` while `Z`'s output shows an `AND(A,B`). Hence this make `Y` to be the adder's **SUM** output and **Z** to be the adder's **CARRY** output.

1. The output for the pullup circuitry is the inversion of the output of the pulldown circuitry: $$\overline{(A+B) C + D} = (\overline{A} \text{ }\overline{B} + \overline{C}) \overline{D}$$ We don't need to add inverter in the inputs. Convince yourself that this is true by tracing some input combinations to the output terminal.
   


2. From the pulldown diagram, it seems like the output is 0 if D is 1, or A and C is 1, or B and C is 1. Therefore, the output for the gate is the inverse of the expression of the pulldown circuitry, which is the output of the pullup circuitry above: $$\overline{(A+B) C + D} = (\overline{A} \text{ }\overline{B} + \overline{C}) \overline{D}$$


3. The voltage of the output terminal at `0` steady state is `0` (GND). The voltage of the output terminal at `1` steady state is VDD's voltage.

The final simplified form is $$Y = AB + CD + \bar{B}C$$ The steps are as follows: $$\begin{aligned} Y &= AB \bar{C} \bar{D} + AB \bar{C}D + \bar{A} \bar{B}CD + \bar{A}BCD + ABCD \\ & + A\bar{B}CD + \bar{A}\bar{B}C \bar{D} + ABC \bar{D} + A\bar{B}C \bar{D}\\ &= AB\bar{C} + \bar{A}CD + ACD + \bar{B}C\bar{D} + ABC\bar{D}\\ &= CD + AB\bar{C} + \bar{B}C\bar{D} + ABC\bar{D}\\ &= C(D + \bar{B} \bar{D}) + AB(\bar{C} + C\bar{D} )\\ &= C(D + \bar{B} ) + AB(\bar{C} + \bar{D} )\\ &=CD + C\bar{B} + AB(\overline{CD} )\\ &= CD + C\bar{B} + AB \end{aligned}$$
Convince yourself that the simplified form allows you to make a cheaper and smaller combinational logic device (because we use less number of gates). If you have your own method and can't seem to reconcile between the given answer and your answer, apply consensus theorem (scroll to the said theorem). You can also use online truth table tools to confirm that the truth table of your boolean expression and the above boolean expression is equivalent.

1. When: `A=0, B=1` or `A=1, B=0`, it means that there's a connection between VDD and GND. This caused the gate to short circuit, and hence its burning out.


2. Yes, when: `A=1, B=1`, then `C==0`. When `A=0, B=0`, then `C==1`. This happens when the pullup and pulldown circuit are not both `ON` (active) at the same time.


3. No. When `A=1, B=0`, then the circuit will burn out again since the pullup and pulldown will be `ON` (active), thus causing a short circuit and burning out the circuit. Also, the output is **not** defined when: `A=0, B=1`. This is because **neither** the pullup or pulldown are active.


4. Yes. It exhibits the behavior of an inverter, i.e: A and B are connected to the same `Vin`.

1. Sum-of-products expressionf or F is: $$\overline{A}\text{ }\overline{B}\text{ }\overline{C} + \overline{A}BC + A \overline{B}\text{ }\overline{C} + A \overline{B}C + ABC$$


2. The minimal sum of products is: $$\overline{B}A + \overline{B} \text{ } \overline{C} + BC$$ You can draw a combinational circuit of this by adding an input to a big OR gate for every '+', INV (where necessary for negated input) with AND gate for every *pair* of input in the minimal sum of products:
   
   To turn AND and ORs into just NANDs, we can do this in two steps. First, turn the AND into NAND and add an inverter:
   
   Then apply DeMorgan law:
   


3. If we use A and B as the select inputs for the MUX, then the four data inputs of the MUX should be tied to one of `0` (ground), `1` (VDD), `C` or `NOT C`. The following is one of the correct schematics that implement this function (there are other acceptable answers as well). Note that by changing the connections on the data inputs to the mux, we could implement any function of A, B and C. Another acceptable (and simpler) answer involves having two 4-input muxes with `A` and `B` as selector each, reflecting their values when `C==0` and `C==1` respectively, and a 2-input mux with C as its selector, and the outputs of the 4-input muxes to each of the input terminals of the 2-input mux. You're definitely not expected to come up with fancy circuitry design as the given answer below.
   


4. We can just write *sum of product* for rows that results the `0`s in the table above, and then reduce the expression into: $$\overline{F} = B \overline{C} + \overline{A} \text{ } \overline{B} C$$

The minimised boolean expression is: $$AD + \bar{B}\bar{C} + \bar{B} \bar{D}$$ They're obtained from these **three** boxes:

• on the lower right corner (row 3 and 4, with column 3 and 4),
• on the sides (row 1 and 2, with column 1 and 4), and
• on the four corners (row 1 col 1, and row 1 col 4, and row 4 col 1, and row 4 col 4).

1. Let `X = F(F1, F2, F3, F4)` be the function of four variables with the four inputs connected to node `F1-F4`, `Z = G(G1, G2, G3, G4)` be another function of four variables with the four inputs connected to node `G1-G4`, and `Y = H(C1, C2, C3)` be the function with three unrelated input variables with the three inputs connected to node `C1-C3` in the diagram above. The necessary control signals are:
   • `MA` = 1
   • `MB` = 1
   • `MC` = 0 (select `C1`)
   • `MD` = 1 (select `C2`)
   • `ME` = 2 (select `C3`)


2. Let `Y = F(A1, A2, A3, A4, A5)`, where `A1` to `A5` are the five input variables which we can **map** to the input nodes in the diagram above. Let input `A1-A4` be connected to node `F1-F4` and `G1-G4` (they're connected to the same 4 inputs) and A5 be connected to node `C1`. This can be implemented using both 4-input logic functions, and selecting between the two outputs with the 3-input logic function.
   • `Z = f(A1, A2, A3, A4, 0)`,
   • `X = f(A1, A2, A3, A4, 1)`,
   • `Y = Z` if `A5=0`, else `Y = X`
   So `Z` calculates `F` for the case when `A5 = 0`, `X` calculates `F` for the case when `A5 = 1`, and `Y` is **selecting** between `X` and `Z` with a multiplexer function.
   
   The necessary control signals are:
   • `MA` = 0
   • `MB` = 0
   • `MC` = X (value doesn't matter)
   • `MD` = X (value doesn't matter)
   • `ME` = 0 (select C1)


3. Let `Z = G(G1, G2, G3, G4)` be the function of the 4 variables, so the four inputs are connected directly to node `G1-G4`. Then, let `X = F(F1, F2, F3, F4)` and let `Y = H(C1, C2, X) = H(C1, C2, F(F1, F2, F3, F4))`. The functions of six variables which can be implemented (along with the 4-variable function) are all those functions that can be **re-written** (decomposable) as the function H with 3 variables. The inputs to this function of three variables must be 2 of the original variables (plugged at nodes `C1`, `C2`) and some function of the remaining four variables (plugged at nodes `G1-G4`).The necessary control signals are:
   • `MA` = 0
   • `MB` = 1
   • `MC` = X (value doesn't matter)
   • `MD` = 0 (select C1)
   • `ME` = 1 (select C2)
   
   An example of decomposable function in this case is `H = (C1 XOR C2) AND (F1 OR F2 OR F3 OR F4)`. There's no complex interaction between `C` and `F` variables. On the other hand, the following function is not decomposable to fit the structure of `H` required above: `H = (F1 XOR F2) AND (F3 OR C1) AND (NOT F4 OR C2)`. This function intertwines the C variables with the F variables in a way that their outputs are dependent on each other's values. For example, the outcome of the operation `F3 OR C1` depends on both `F3` and `C1`, which means that the value of `C1` directly influences how `F3` contributes to the overall function and thus creating dependency between them. It won't be possible to encapsulate these two variables separately as either purely `C1`, `C2` inputs or as `F(F1, F2, F3, F4)` output in `H`.


4. Let: `X = F(F1, F2, F3, F4)`, `Z = G(G1, G2, G3, G4)`, `Y = H(C1, X, Z) = H(C1, F(F1, F2, F3, F4), G(G1, G2, G3, G4))`. The 9 inputs are connected to node `F1-F4`, `G1-G4`, and `C1`. The functions of nine variables that can be implemented are all those functions that can be re-written as the function `H` consisted of these 3 variables: `C1`, `F`, and `G`. The inputs to this three-variable function will be **one** of the original variables, plus **two** separate functions of 4 variables `F1-F4`, `G1-G4` (these two 4-variable functions will have the remaining 8 original variables as inputs).
   • `MA` = 0
   • `MB` = 0
   • `MC` = X (value doesn't matter)
   • `MD` = X (value doesn't matter)
   • `ME` = 0 (select C1)


5. The functions of 6 variables which we can implement must be of the form: `Y = C(C1, C2, F(F1,F2,F3,F4))` or the form of `Y = C(C1,F(F1, F2, F3, F4), G(G1, G2, G3, G4))`. This second function will have some **overlap** between `C1`, `F1-4`, and `G1-4`; that is some variables will be connected to **multiple** inputs.
   
   Essentially, the functions we are able to implement are only those for which we can factor a set of 4 variables out of the equation. For example, the following function cannot be implemented by the CLB: `Y = A1A2A3A4A5 + A1A2A3A4A6 + A1A2A3A5A6 + A1A2A4A5A6 + A1A3A4A5A6 + A2A3A4A5A6` (Y is `1` only if there is one `0` in the input). This function cannot be broken down into either of the forms mentioned above.
   
   This function says that `Y` is `1` if and only if these inputs are given as `A1-A6`: `111110`, or `111101`, or `111011`, or `110111`, or `101111`, or `011111`, or `111111`. However suppose `A3-A6` are plugged as `F1-F4`, and `A1, A2` are plugged into `C1, C2` in the FPGA. If you supply `A3-A6` as `0111`, it should output a `1` as the output of `F` due to the clause: `A1A2A4A5A6`. Then, if you supply `C1=0, C2=1`, it will output a `1` as well at `Y` due to the clause: `A2A3A4A5A6`. This effectively means `010111` gives a `1` which violates the condition for `Y`, which turns `1` only if there exist one `0` in the input. Hence the FPGA cannot implement this particular 6-variable function.