COMP2421 Assignment 4

MA Mingyu (Derek) | Oct 28, 2017
derek.ma | derek.ma@connect.polyu.hk

Question 1

\(0xf0000000_{16} = 4026531840_{ten}\). The largest address that it can branch to is: \(PC+4+4\times(2^{15}-1) = 4026531840 + 4 + 131068 = 4026662912\).

The smallest address it can branch to is: \(PC+4-2^{17} = 4026531840 + 4 - 131072 = 4026400772\).

Question 2

The 32-bit jump address is formatted like this:

(PC+4)[31..28] xxx xxx xxx xxx xxx xxx xxx xxx xx 00

This format can express all \(2^{26}\) instructions whose first four bits of address is (PC+4)[31..28]. Number of all the instructions that this format can express is:

\[
2^{26} = 67 108 864 > 64 000 000
\]

So we can see if code straddles 64 000 000 instructions, which are \(4 \times 64000000 = 256 000 000\) bytes(\(256\) MB), this format can't handle it.

Question 3

With one input \(A\):
\[
NOT(A) = \overline{A} = \overline{A\cdot A} = NAND(A,A)
\]

With two inputs \(A\) and \(B\):
\[
AND(A,B) = A \cdot B = \overline{\overline{A \cdot B}} = NAND(NAND(A,B),NAND(A,B))
\]

With two inputs \(A\) and \(B\):
\[
OR(A,B) = A + B = \overline{\overline{A + B}} = \overline{\overline{A} \cdot \overline{B}} = NAND(NAND(A,A),NAND(B,B))
\]

We can conclude that \(NAND\) gate alone can implement the \(AND\), \(OR\) and \(NOT\) functions.

Question 4

The truth table:

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 0
1 1 1 1

Then F can be simplified using SOP: \( F = ABC+BC = BC\).

Question 5

a. Truth table for this circuit

\(x_1\) \(x_2\) \(x_3\) \(x_4\) \(Z_1\) \(Z_2\) \(Z_3\) \(Z_4\) \(Z_5\) \(Z_6\) \(Z_7\)
0 0 0 0 1 1 1 0 1 1 1
0 0 0 1 0 0 1 0 0 1 0
0 0 1 0 1 0 1 1 1 0 1
0 0 1 1 1 0 1 1 0 1 1
0 1 0 0 0 1 1 1 0 1 0
0 1 0 1 1 1 0 1 0 1 1
0 1 1 0 0 1 0 1 1 1 1
0 1 1 1 1 0 1 0 0 1 0
1 0 0 0 1 1 1 1 1 1 1
1 0 0 1 1 1 1 1 0 1 0
1 0 1 0 0 0 0 0 0 0 0
1 0 1 1 0 0 0 0 0 0 0
1 1 0 0 0 0 0 0 0 0 0
1 1 0 1 0 0 0 0 0 0 0
1 1 1 0 0 0 0 0 0 0 0
1 1 1 1 0 0 0 0 0 0 0

b

SOP form lists all combinations that produce an output of 1:

K-map for \(Z_1\)

row:\(x_1x_2\); col:\(x_3x_4\) 00 01 11 10
00 1 0 d 1
01 0 1 d 1
11 1 1 d d
10 1 0 d d

\(Z_1 = x_1 + x_2x_4 + \bar{x_2}\bar{x_4} + x_3x_4\)

K-map for \(Z_2\)

row:\(x_1x_2\); col:\(x_3x_4\) 00 01 11 10
00 1 1 d 1
01 0 1 d 1
11 0 0 d d
10 0 1 d d

\(Z_2 = x_1 + x_2\bar{x_3} + x_2\bar{x_4} + \bar{x_3}\bar{x_4}\)

K-map for \(Z_3\)

row:\(x_1x_2\); col:\(x_3x_4\) 00 01 11 10
00 1 1 d 1
01 1 0 d 1
11 1 1 d d
10 1 0 d d

\(Z_3 = \bar{x_2} + x_3x_4 + \bar{x_3}\bar{x_4}\)

K-map for \(Z_4\)

row:\(x_1x_2\); col:\(x_3x_4\) 00 01 11 10
00 0 1 d 1
01 0 1 d 1
11 1 0 d d
10 1 1 d d

\(Z_4 = x_1 + x_2\bar{x_3}+\bar{x_2}x_3 + x_3\bar{x_4}\)

K-map for \(Z_5\)

row:\(x_1x_2\); col:\(x_3x_4\) 00 01 11 10
00 1 0 d 1
01 0 0 d 0
11 0 0 d d
10 1 1 d d

\(Z_5 = x_3\bar{x_4} + \bar{x_2}\bar{x_4}= \bar{x_4}(x_3 + \bar{x_2})\)

K-map for \(Z_6\)

row:\(x_1x_2\); col:\(x_3x_4\) 00 01 11 10
00 1 1 d 1
01 1 1 d 1
11 1 1 d d
10 0 1 d d

\(Z_6 = x_2 + \bar{x_3} + x_4\)

K-map for \(Z_7\)

row:\(x_1x_2\); col:\(x_3x_4\) 00 01 11 10
00 1 0 d 1
01 0 1 d 0
11 1 0 d d
10 1 1 d d

\(Z_7 = \bar{x_2}x_3 + \bar{x_2}\bar{x_4} + x_3\bar{x_4} + x_2\bar{x_3}x_4= \bar{x_2}(x_3 + \bar{x_4}) + x_3\bar{x_4} + x_2\bar{x_3}x_4\)