CS1200 Assignment 2 Solved

Question 0. Submission instructions 
(a)      You have named your file with your student number, i.e., AxxxxxxxY.pdf.       (1 mark)

(b)     You have submitted your assignment as a single PDF file and no multiple copies, i.e. there should only be ONE file in your submission folder. (1 mark)

(c)      Your assignment submission has your tutorial group number, student number and name at the top of the first page of your file. (All three items must be present.) (1 mark) uestion 1. Datapath 

[Past-year’s exam question] Consider the MIPS datapath with the values of the registers shown below. All values are in hexadecimal.

R0  (r0) = 0x00000000 | R1  (at) = 0x00002000 

R2  (v0) = 0x00000001 | R3  (v1) = 0x0000000a 

R4  (a0) = 0x00000005 | R5  (a1) = 0x7ffff000 

R6  (a2) = 0x7ffff004 | R7  (a3) = 0x000000b0 

R8  (t0) = 0x00000001 | R9  (t1) = 0x00000c00 

R10 (t2) = 0x0000c000 | R11 (t3) = 0xfffffff0 

R12 (t4) = 0xf0000000 | R13 (t5) = 0x00000fff 

R14 (t6) = 0x00006200 | R15 (t7) = 0x00000e00 

R16 (s0) = 0x00300000 | R17 (s1) = 0x00000c00 

R18 (s2) = 0x00040200 | R19 (s3) = 0x00011000 

R20 (s4) = 0x00030200 | R21 (s5) = 0x10000000 

R22 (s6) = 0x00055000 | R23 (s7) = 0xf0000000 

R24 (t8) = 0x00000005 | R25 (t9) = 0x0000d000 

R26 (k0) = 0x00000000 | R27 (k1) = 0x00000000 

R28 (gp) = 0x10008000 | R29 (sp) = 0x7fffeff4 

R30 (s8) = 0x1000000f | R31 (ra) = 0x00400018 
 

 

 

uestion 1. (continue…) 

The current PC value is 200 and the instruction being executed is:

lw $t6, -24($sp) 

Fill in the values of the fields in the table below.                                                               

For the 8th data row onwards in the table below, if your value is not in base ten, make sure you write the prefix (eg: 0x123) or subscript (eg: 12316) to specify the base. Values without prefix or subscript will be treated as if they are in base ten by default.

Field 
Value 
RegDst 
 
MemRead 
 
Branch 
 
MemtoReg 
 
MemWrite 
 
ALUSrc 
 
RegWrite 
 
Instruction[31-26] 
 
Instruction[25-21] 
 
Instruction[20-16] 
 
Instruction[15-11] 
 
Œ 
 
 
 
Ž 
 
 
 
 
 
 

             

uestion 2. Simplification (12 marks)
(a) Simplify the following Boolean expression into its simplest SOP expression, showing each step with justification (i.e. citing the law/theorem used). Marks will be deducted if a step is not justified or wrongly justified.   [4 marks]

                          AB'EL'OP'T'WH' + AL + AL'T' 
 You may skip obvious steps, such as (AB')' straight to (A'+B) [De Morgan’s theorem] instead of first to (A'+(B')') [De Morgan’s] then to (A'+B) [involution]; or (A'B + A) straight to (A+B) [absorption theorem 2] instead of first to (A + A'B) [commutative law] then to (A+B) [absorption theorem 2].

    Recall that the AND operator  must be present. Writing AB instead of AB will incur penalty.

 

For each of the Boolean functions in parts (b) and (c) below, write (i) the number of PIs (prime implicants) in the K-map of the function, (ii) the number of EPIs (essential prime implicants) in the K-map of the function, (iii) its simplest SOP expression, and (iv) its simplest POS expression. If there are more than one simplest SOP/POS expression, you need to give only one.

You may show your K-maps but they won’t be graded. Your K-maps may be useful for us to locate the mistakes you made. If you are drawing the K-maps, please use the following layout. You may use X for don’t cares.


(b) F(A,B,C,D) = m(0,1,2,13) + X(4,9,12,14).  

 
[4 marks]
(c) G(A,B,C,D) = M(3,4,5,6,11,15)  X(0,2,8,10).  
[4 marks]
 

 

             

 

Question 3. Circuit Analysis (4 marks)
The following circuit diagram is taken from the data sheet of an IC chip. Identify the circuit below, which takes in C0, A1, A2, A3, A4, B1, B2, B3 and B4 as inputs and generates V, W, X, Y and Z as the outputs. Give the name of this circuit and describe what it does by relating the outputs with the inputs.

 

Question 4. Circuit Design (7 marks)
A combinational circuit takes in a 5-bit input ABCDE which is a value in excess 8 representation, and generates an output P such that P=1 if ABCDE represents a prime number, or P=0 otherwise.

For example, if ABCDE=10001, then P=0; if ABCDE=11001, then P=1.  

You may assume that negative values will not be supplied to this circuit.

(a)      Draw a 5-variable K-map for P (draw one K-map with A=0 and another with A=1). [2 marks]

(b)     Write out the simplified SOP expression for P.   [3 marks]

(c)      Let V(A,B,C,D,E) be the validity function, that is, V returns 1 if the input is valid, or 0 otherwise. Implement V using the fewest number of gates with the fewest number of inputs.

         Draw your circuit for V.                                                                                                [2 marks]

 

Question 5. Block-level design (6 marks)
Note:   

▪ Boolean constants (0 and 1) are always available; ▪ Complemented literals are not available.

(a)    Implement the following Boolean function using a single 2-bit magnitude comparator with no additional logic gates.

                                          G(A,B,C,D) = m(1, 4, 5, 6, 7, 13)

       The block diagram of a 2-bit magnitude comparator is shown below.                       [3 marks]

 

(b)   A circuit takes in a 5-bit code ABCDE and generates P, the parity bit for the code, assuming even parity scheme, which means that the total number of 1s in ABCDE and P must be even. For example, if ABCDE = 00110, then P=0; if ABCDE = 10101, then P=1.

Implement the above circuit using the fewest number of half adders (HA) and 2-bit parallel adders, and no other logic gates. The block diagrams for a half adder and a 2-bit parallel adder are shown below. You are not allowed to change the block diagrams. [3 marks]