Lab 4 Pre-Work

exercises
lab
computer-systems
digital-logic
combinational-logic
boolean-algebra

Question 1

Draw a circuit schematic diagram for a 2-to-1 multiplexer that uses only 2-input NAND gates. The data inputs should be connected to push buttons. The select input should be connected to a switch. The output should be connected to an LED.

Hint: Do the truth table (or a function table) for a 2-to-1 multiplexer, obtain the logic expression, then draw a logic circuit and convert it to the NAND equivalent circuit by replacing each gate with its NAND version. If you use Logisim, do not use the MUX module.

1. Function Table

\(S_0\) \(D_0\) \(D_1\) \(F\)
0 0 0 0
0 0 1 0
0 1 0 1
0 1 1 1
1 0 0 0
1 0 1 1
1 1 0 0
1 1 1 1

2. Sum of Products & Simplification

Deriving the unsimplified Sum of Products from the true outputs in the table:

  • \(S_0 = 0\), \(D_0 = 1\), \(D_1 = 0 \rightarrow \bar{S_0} \cdot D_0 \cdot \bar{D_1}\)
  • \(S_0 = 0\), \(D_0 = 1\), \(D_1 = 1 \rightarrow \bar{S_0} \cdot D_0 \cdot D_1\)
  • \(S_0 = 1\), \(D_0 = 0\), \(D_1 = 1 \rightarrow S_0 \cdot \bar{D_0} \cdot D_1\)
  • \(S_0 = 1\), \(D_0 = 1\), \(D_1 = 1 \rightarrow S_0 \cdot D_0 \cdot D_1\)

Using Boolean algebra, we can simplify this expression:

\[ \begin{aligned} F &= \bar{S_0} D_0 \bar{D_1} + \bar{S_0} D_0 D_1 + S_0 \bar{D_0} D_1 + S_0 D_0 D_1 \\ &= \bar{S_0} D_0 (\bar{D_1} + D_1) + S_0 D_1 (\bar{D_0} + D_0) \\ &= \bar{S_0} D_0 (1) + S_0 D_1 (1) \\ &= \bar{S_0} D_0 + S_0 D_1 \end{aligned} \]

3. NAND Equivalent Conversion

To implement this circuit using only 2-input NAND gates, we must convert the simplified AND-OR expression into a NAND-NAND expression. We can achieve this by applying double negation and De Morgan’s Laws:

\[ \begin{aligned} F &= \overline{\overline{\bar{S_0} D_0 + S_0 D_1}} \\ &= \overline{(\overline{\bar{S_0} D_0}) \cdot (\overline{S_0 D_1})} \end{aligned} \]

4. Circuit Schematic

Based on the final NAND logic expression, the circuit requires exactly four 2-input NAND gates: 1. One NAND gate to act as an inverter for \(S_0\) (by wiring \(S_0\) to both inputs) to create \(\bar{S_0}\). 2. One NAND gate to compute \(\overline{\bar{S_0} D_0}\). 3. One NAND gate to compute \(\overline{S_0 D_1}\). 4. One final NAND gate to combine the outputs of gates 2 and 3.

All four gates fit on a single 74HCT00 (quad 2-input NAND — see device-pinouts). Using circuit-schematics labelling conventions, gates 1–4 above become U1:A–U1:D, wired as:

  • U1:A: inputs 1, 2 tied together to \(S_0\) (switch) → pin 3 = \(\bar{S_0}\)
  • U1:B: inputs 4 = \(\bar{S_0}\) (U1:A pin 3), 5 = \(D_0\) (push button) → pin 6 = \(\overline{\bar{S_0} D_0}\)
  • U1:C: inputs 9 = \(S_0\) (switch), 10 = \(D_1\) (push button) → pin 8 = \(\overline{S_0 D_1}\)
  • U1:D: inputs 12 = U1:B pin 6, 13 = U1:C pin 8 → pin 11 = \(F\) (LED)

VCC (pin 14) and GND (pin 7) are shown once for U1.

Question 2

Circuit 2
Draw a circuit schematic diagram for a 2-to-4 decoder - using whichever logic gates you prefer (from those available in the CSSE2010/CSSE7201 lab). The two inputs should be connected to switches. The outputs should be connected to LEDs.

A 2-to-4 decoder has the following truth table (inputs A1, A0 and outputs X0, X1, X2, X3):

A1 A0   X0 X1 X2 X3
0 0 1 0 0 0
0 1 0 1 0 0
1 0 0 0 1 0
1 1 0 0 0 1

1. Boolean Expressions

Since \(A_1, A_0\) can only take four combinations, each output’s truth-table row is already a single minterm — no Boolean simplification is needed, just one 2-input AND term per output:

  • \(X_0 = \bar{A_1} \cdot \bar{A_0}\)
  • \(X_1 = \bar{A_1} \cdot A_0\)
  • \(X_2 = A_1 \cdot \bar{A_0}\)
  • \(X_3 = A_1 \cdot A_0\)

2. Circuit Schematic

Two chip types cover this: a 74HCT04 (hex inverter) to generate \(\bar{A_1}\) and \(\bar{A_0}\) once each, and a 74HCT08 (quad 2-input AND — see device-pinouts) for the four output terms. Using circuit-schematics conventions:

  • U1 (74HCT04): U1:A (pin 1 → 2): \(A_1\) (switch) → \(\bar{A_1}\). U1:B (pin 3 → 4): \(A_0\) (switch) → \(\bar{A_0}\).
  • U2 (74HCT08):
    • U2:A (in 1, 2 → out 3): \(\bar{A_1}\) (U1:A pin 2), \(\bar{A_0}\) (U1:B pin 4) → \(X_0\) (LED)
    • U2:B (in 4, 5 → out 6): \(\bar{A_1}\) (U1:A pin 2), \(A_0\) (switch) → \(X_1\) (LED)
    • U2:C (in 9, 10 → out 8): \(A_1\) (switch), \(\bar{A_0}\) (U1:B pin 4) → \(X_2\) (LED)
    • U2:D (in 12, 13 → out 11): \(A_1\) (switch), \(A_0\) (switch) → \(X_3\) (LED)

VCC/GND (pin 14/7 on both chips) are shown once per chip type.

Circuit 3
Using a 74HCT04, 74HCT157 and a 74HCT283, draw a circuit schematic diagram for a circuit which can act as a 4-bit two’s complement adder or subtractor. The output (4-bits from the 74HCT283, which should be shown on LEDs) will have the value A+B or A-B (where A and B are the 4-bit inputs which are taken from switches).

A push button input (M, mode) will determine whether the circuit performs addition or subtraction - if the value is 0, addition will be performed; if the value is 1, subtraction will be performed by calculating A+(-B).

The circuit is similar to that shown in week3-lecture 4-slide 7 except the selection of the “B” input bits as B or not(B) is to be performed using multiplexers instead of XOR gates. (The 74HCT157 is a quad 2-to-1 multiplexer with a shared select input.) The carry output should be shown on a LED also.

1. Circuit Design Reasoning

In two’s complement, \(-B = \bar{B} + 1\), so subtraction can be built from the same adder used for addition: \(A - B = A + \bar{B} + 1\). This means mode input \(M\) needs to do two things at once:

  • Select whether the adder’s B input is \(B\) (add) or \(\bar{B}\) (subtract) — done with the 74HCT157 MUX.
  • Inject the “+1” that turns one’s complement into two’s complement — done by wiring \(M\) straight into the adder’s carry-in, since \(C_0 = 0\) for addition (no extra bit needed) and \(C_0 = 1\) for subtraction (adds the required 1).

So \(M\) is wired to both the 74HCT157’s select line and the 74HCT283’s \(C_0\) pin — no separate control logic needed.

2. Circuit Schematic

Three chips (see device-pinouts for exact pins), following circuit-schematics conventions:

  • U1 (74HCT04, hex inverter) — generates \(\bar{B_0}\)–\(\bar{B_3}\) for the MUX’s B-channel:
    • U1:A (1→2): \(B_0\) (switch) → \(\bar{B_0}\)
    • U1:B (3→4): \(B_1\) (switch) → \(\bar{B_1}\)
    • U1:C (5→6): \(B_2\) (switch) → \(\bar{B_2}\)
    • U1:D (9→8): \(B_3\) (switch) → \(\bar{B_3}\)
  • U2 (74HCT157, quad 2-to-1 MUX) — selects \(B_i\) (channel A, \(M=0\)) or \(\bar{B_i}\) (channel B, \(M=1\)) per bit. SEL (pin 1) = \(M\) (push button); ENABLE (pin 15) tied to GND (always active):
    • Channel 0: A0 (pin 2) = \(B_0\) switch, B0 (pin 3) = \(\bar{B_0}\) (U1:A pin 2), Y0 (pin 4) → adder B0
    • Channel 1: A1 (pin 5) = \(B_1\) switch, B1 (pin 6) = \(\bar{B_1}\) (U1:B pin 4), Y1 (pin 7) → adder B1
    • Channel 2: A2 (pin 11) = \(B_2\) switch, B2 (pin 10) = \(\bar{B_2}\) (U1:C pin 6), Y2 (pin 9) → adder B2
    • Channel 3: A3 (pin 14) = \(B_3\) switch, B3 (pin 13) = \(\bar{B_3}\) (U1:D pin 8), Y3 (pin 12) → adder B3
  • U3 (74HCT283, 4-bit adder) — sums \(A\) with the MUX’s selected \(B\)/\(\bar{B}\), carry-in doubling as the mode’s “+1”:
    • A0–A3 (pins 5, 3, 14, 12) = \(A_0\)–\(A_3\) switches (unchanged by mode)
    • B0–B3 (pins 6, 2, 15, 11) = U2 Y0–Y3
    • C0 (pin 7, carry-in) = \(M\) (same signal as U2’s SEL)
    • S0–S3 (pins 4, 1, 13, 10) → LEDs (result)
    • C4 (pin 9, carry-out) → LED

VCC/GND are shown once per chip type.