DIT11022 - Computer Systems and Architectures
Assignment 01 Solutions
Question 1: Odd Ones & Prime Number Combinational Logic
a. Complete Truth Table
| Decimal | A | B | C | D | Y1 (Odd 1s) | Y2 (Prime) |
|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 1 | 1 | 0 |
| 2 | 0 | 0 | 1 | 0 | 1 | 1 |
| 3 | 0 | 0 | 1 | 1 | 0 | 1 |
| 4 | 0 | 1 | 0 | 0 | 1 | 0 |
| 5 | 0 | 1 | 0 | 1 | 0 | 1 |
| 6 | 0 | 1 | 1 | 0 | 0 | 0 |
| 7 | 0 | 1 | 1 | 1 | 1 | 1 |
| 8 | 1 | 0 | 0 | 0 | 1 | 0 |
| 9 | 1 | 0 | 0 | 1 | 0 | 0 |
| 10 | 1 | 0 | 1 | 0 | 0 | 0 |
| 11 | 1 | 0 | 1 | 1 | 1 | 1 |
| 12 | 1 | 1 | 0 | 0 | 0 | 0 |
| 13 | 1 | 1 | 0 | 1 | 1 | 1 |
| 14 | 1 | 1 | 1 | 0 | 1 | 0 |
| 15 | 1 | 1 | 1 | 1 | 0 | 0 |
b. K-Maps and Simplified Boolean Expressions (SOP)
K-Map for Y1 (Odd number of ones):
| AB \ CD | 00 | 01 | 11 | 10 |
|---|
| 00 | 0 | 1 | 0 | 1 |
|---|
| 01 | 1 | 0 | 1 | 0 |
|---|
| 11 | 0 | 1 | 0 | 1 |
|---|
| 10 | 1 | 0 | 1 | 0 |
|---|
Observation: This forms a checkerboard pattern. No 1s can be grouped. We write the full SOP:
Y1 = A'B'C'D + A'B'CD' + A'BC'D' + A'BCD + AB'C'D' + AB'CD + ABC'D + ABCD'
K-Map for Y2 (Prime Numbers):
| AB \ CD | 00 | 01 | 11 | 10 |
|---|
| 00 | 0 | 0 | 1 | 1 |
|---|
| 01 | 0 | 1 | 1 | 0 |
|---|
| 11 | 0 | 1 | 0 | 0 |
|---|
| 10 | 0 | 0 | 1 | 0 |
|---|
Groups for Y2: Pair(m2,m3) = A'B'C, Pair(m3,m11) = B'CD, Pair(m5,m13) = BC'D, Pair(m5,m7) = A'BD.
Y2 = A'B'C + B'CD + BC'D + A'BD
c. Logic Gate Diagram Guide
Universal Gates (NAND only): Apply De Morgan's Law to Y2.
Y2 = ( (A'B'C)' • (B'CD)' • (BC'D)' • (A'BD)' )'
Draw a 2-level NAND-NAND circuit using the inverted inputs. For Y1, it can be drawn as a 4-input XOR gate if allowed, otherwise, it requires a very large NAND equivalent.
Question 2: BCD to Excess-3 Converter
a. Complete Truth Table
| BCD Input | Excess-3 Output (Add 3) |
|---|
| A | B | C | D | W | X | Y | Z |
|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 |
| 0 | 0 | 0 | 1 | 0 | 1 | 0 | 0 |
| 0 | 0 | 1 | 0 | 0 | 1 | 0 | 1 |
| 0 | 0 | 1 | 1 | 0 | 1 | 1 | 0 |
| 0 | 1 | 0 | 0 | 0 | 1 | 1 | 1 |
| 0 | 1 | 0 | 1 | 1 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 | 1 | 0 | 0 | 1 |
| 0 | 1 | 1 | 1 | 1 | 0 | 1 | 0 |
| 1 | 0 | 0 | 0 | 1 | 0 | 1 | 1 |
| 1 | 0 | 0 | 1 | 1 | 1 | 0 | 0 |
| 1 | 0 | 1 | 0 | X | X | X | X |
| 1 | 0 | 1 | 1 | X | X | X | X |
| 1 | 1 | 0 | 0 | X | X | X | X |
| 1 | 1 | 0 | 1 | X | X | X | X |
| 1 | 1 | 1 | 0 | X | X | X | X |
| 1 | 1 | 1 | 1 | X | X | X | X |
b. K-Maps and Simplified Boolean Expressions
K-Map for W:
| AB \ CD | 00 | 01 | 11 | 10 |
|---|
| 00 | 0 | 0 | 0 | 0 |
|---|
| 01 | 0 | 1 | 1 | 1 |
|---|
| 11 | X | X | X | X |
|---|
| 10 | 1 | 1 | X | X |
|---|
W = A + BC + BD
K-Map for X:
| AB \ CD | 00 | 01 | 11 | 10 |
|---|
| 00 | 0 | 1 | 1 | 1 |
|---|
| 01 | 1 | 0 | 0 | 0 |
|---|
| 11 | X | X | X | X |
|---|
| 10 | 0 | 1 | X | X |
|---|
X = B'C + B'D + BC'D'
K-Map for Y:
| AB \ CD | 00 | 01 | 11 | 10 |
|---|
| 00 | 1 | 0 | 1 | 0 |
|---|
| 01 | 1 | 0 | 1 | 0 |
|---|
| 11 | X | X | X | X |
|---|
| 10 | 1 | 0 | X | X |
|---|
Y = C'D' + CD
K-Map for Z:
| AB \ CD | 00 | 01 | 11 | 10 |
|---|
| 00 | 1 | 0 | 0 | 1 |
|---|
| 01 | 1 | 0 | 0 | 1 |
|---|
| 11 | X | X | X | X |
|---|
| 10 | 1 | 0 | X | X |
|---|
Z = D'
c. Logic Gate Diagram Guide
Instruction: Use basic gates (AND, OR, NOT). Draw 4 input lines A, B, C, D and their NOT inverted lines. Build the product terms with AND gates, and sum them using OR gates for each output W, X, Y, Z based on the above equations.
Question 3: Add 1 to a 4-bit Binary Number
Truth Table
| Input | Output (+1) |
|---|
| A3 | A2 | A1 | A0 | S4 | S3 | S2 | S1 | S0 |
|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 |
| 0 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 0 |
| 0 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 1 |
| 0 | 0 | 1 | 1 | 0 | 0 | 1 | 0 | 0 |
| 0 | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 1 |
| 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 |
| 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 1 |
| 0 | 1 | 1 | 1 | 0 | 1 | 1 | 0 | 0 |
| 1 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 1 |
| 1 | 0 | 0 | 1 | 0 | 1 | 0 | 1 | 0 |
| 1 | 0 | 1 | 0 | 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 1 | 1 | 0 | 1 | 1 | 0 | 0 |
| 1 | 1 | 0 | 0 | 0 | 1 | 1 | 0 | 1 |
| 1 | 1 | 0 | 1 | 0 | 1 | 1 | 1 | 0 |
| 1 | 1 | 1 | 0 | 0 | 1 | 1 | 1 | 1 |
| 1 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 |
K-Maps and Simplified SOP Expressions
K-Map for S0:
| A3A2 \ A1A0 | 00 | 01 | 11 | 10 |
|---|
| 00 | 1 | 0 | 0 | 1 |
|---|
| 01 | 1 | 0 | 0 | 1 |
|---|
| 11 | 1 | 0 | 0 | 1 |
|---|
| 10 | 1 | 0 | 0 | 1 |
|---|
S0 = A0'
K-Map for S1:
| A3A2 \ A1A0 | 00 | 01 | 11 | 10 |
|---|
| 00 | 0 | 1 | 0 | 1 |
|---|
| 01 | 0 | 1 | 0 | 1 |
|---|
| 11 | 0 | 1 | 0 | 1 |
|---|
| 10 | 0 | 1 | 0 | 1 |
|---|
S1 = A1'A0 + A1A0'
K-Map for S2:
| A3A2 \ A1A0 | 00 | 01 | 11 | 10 |
|---|
| 00 | 0 | 0 | 1 | 1 |
|---|
| 01 | 1 | 1 | 0 | 0 |
|---|
| 11 | 1 | 1 | 0 | 0 |
|---|
| 10 | 0 | 0 | 1 | 1 |
|---|
S2 = A2A1' + A2A0' + A2'A1A0
K-Map for S3:
| A3A2 \ A1A0 | 00 | 01 | 11 | 10 |
|---|
| 00 | 0 | 0 | 0 | 0 |
|---|
| 01 | 0 | 0 | 1 | 0 |
|---|
| 11 | 1 | 1 | 0 | 1 |
|---|
| 10 | 1 | 1 | 1 | 1 |
|---|
S3 = A3A2' + A3A1' + A3A0' + A3'A2A1A0
K-Map for S4:
| A3A2 \ A1A0 | 00 | 01 | 11 | 10 |
|---|
| 00 | 0 | 0 | 0 | 0 |
|---|
| 01 | 0 | 0 | 0 | 0 |
|---|
| 11 | 0 | 0 | 1 | 0 |
|---|
| 10 | 0 | 0 | 0 | 0 |
|---|
S4 = A3A2A1A0
Question 4: Design using Four Half-Adders
Explanation for Diagram:
Using the block diagram in the assignment, cascade 4 Half Adders (HA).
- HA0: Input A = A0, Input B = 1. Sum = S0, Carry = C0.
- HA1: Input A = A1, Input B = C0. Sum = S1, Carry = C1.
- HA2: Input A = A2, Input B = C1. Sum = S2, Carry = C2.
- HA3: Input A = A3, Input B = C2. Sum = S3, Carry = S4.
Please draw this exactly as given in your assignment paper.
Question 5: 2-Bit Binary Adder
Truth Table
| X1 | X0 | Y1 | Y0 | C | S1 | S0 |
|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 1 | 0 | 0 | 1 |
| 0 | 0 | 1 | 0 | 0 | 1 | 0 |
| 0 | 0 | 1 | 1 | 0 | 1 | 1 |
| 0 | 1 | 0 | 0 | 0 | 0 | 1 |
| 0 | 1 | 0 | 1 | 0 | 1 | 0 |
| 0 | 1 | 1 | 0 | 0 | 1 | 1 |
| 0 | 1 | 1 | 1 | 1 | 0 | 0 |
| 1 | 0 | 0 | 0 | 0 | 1 | 0 |
| 1 | 0 | 0 | 1 | 0 | 1 | 1 |
| 1 | 0 | 1 | 0 | 1 | 0 | 0 |
| 1 | 0 | 1 | 1 | 1 | 0 | 1 |
| 1 | 1 | 0 | 0 | 0 | 1 | 1 |
| 1 | 1 | 0 | 1 | 1 | 0 | 0 |
| 1 | 1 | 1 | 0 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 | 1 | 1 | 0 |
K-Maps and SOP Expressions
K-Map for C (Carry):
| X1X0 \ Y1Y0 | 00 | 01 | 11 | 10 |
|---|
| 00 | 0 | 0 | 0 | 0 |
|---|
| 01 | 0 | 0 | 1 | 0 |
|---|
| 11 | 0 | 1 | 1 | 1 |
|---|
| 10 | 0 | 0 | 1 | 1 |
|---|
C = X1Y1 + X1X0Y0 + X0Y1Y0
K-Map for S1:
| X1X0 \ Y1Y0 | 00 | 01 | 11 | 10 |
|---|
| 00 | 0 | 0 | 1 | 1 |
|---|
| 01 | 0 | 1 | 0 | 1 |
|---|
| 11 | 1 | 0 | 1 | 0 |
|---|
| 10 | 1 | 1 | 0 | 0 |
|---|
S1 = X1'X0'Y1 + X1'Y1Y0' + X1Y1'Y0' + X1X0'Y1' + X1'X0Y1'Y0 + X1X0Y1Y0
K-Map for S0:
| X1X0 \ Y1Y0 | 00 | 01 | 11 | 10 |
|---|
| 00 | 0 | 1 | 0 | 1 |
|---|
| 01 | 1 | 0 | 1 | 0 |
|---|
| 11 | 1 | 0 | 1 | 0 |
|---|
| 10 | 0 | 1 | 0 | 1 |
|---|
S0 = X0'Y0 + X0Y0'
Question 6: Design using Two Full Adders
Explanation for Diagram:
Use two Full Adders (FA) connected in series.
- FA0: Inputs = X0, Y0. Carry-in = 0. Outputs = S0 and Carry out.
- FA1: Inputs = X1, Y1. Carry-in = Carry out from FA0. Outputs = S1 and C (Final Carry).
Please draw this exactly as given in your assignment paper.
Question 7: Even Number and >3 Logic
a. Truth Table
| A | B | C | Decimal | Y1 (Even) | Y2 (> 3) |
|---|
| 0 | 0 | 0 | 0 | 1 | 0 |
| 0 | 0 | 1 | 1 | 0 | 0 |
| 0 | 1 | 0 | 2 | 1 | 0 |
| 0 | 1 | 1 | 3 | 0 | 0 |
| 1 | 0 | 0 | 4 | 1 | 1 |
| 1 | 0 | 1 | 5 | 0 | 1 |
| 1 | 1 | 0 | 6 | 1 | 1 |
| 1 | 1 | 1 | 7 | 0 | 1 |
b. K-Maps and Simplified SOP Expressions
K-Map for Y1 (Even Numbers):
| A \ BC | 00 | 01 | 11 | 10 |
|---|
| 0 | 1 | 0 | 0 | 1 |
|---|
| 1 | 1 | 0 | 0 | 1 |
|---|
Group of 4 cells at col 00 and col 10.
Y1 = C'
K-Map for Y2 (Greater than 3):
| A \ BC | 00 | 01 | 11 | 10 |
|---|
| 0 | 0 | 0 | 0 | 0 |
|---|
| 1 | 1 | 1 | 1 | 1 |
|---|
Group of 4 cells representing row A=1.
Y2 = A
c. Logic Gate Diagram Guide
Instruction to Draw:
- Draw 3 input lines: A, B, and C.
- Y1: Take a wire from C, pass it through a NOT gate. This is Y1.
- Y2: Take a wire directly from A. This is Y2.
- Input B remains unconnected to any output.