Description

Department of Computer Science and Engineering
Computer Organization Laboratory (CS39001)
Full marks: 40 Time: 90 minutes
Credit: 40%

INSTRUCTIONS: This is an OPEN-BOOK, OPEN-NOTES test. The questions are such that they require either numerical answers or short answers (including logic diagrams). Please write ONLY THE ANSWERS on sheets of paper, scan them (or take photos), and submit the images of the solution sheets on Moodle (submit a single zipped folder if you have multiple files). DO NOT
FORGET TO WRITE YOUR NAME AND ROLL NUMBER AT THE TOP OF YOUR ANSWER

Figure 1: An n-bit logic unit.
1. Consider the logic diagram of an n-bit logic unit, as shown in Fig. 1 above, which can be used to realize all sixteen two-variable functions.
(a) Write the logic expression for Z. [2]
(b) Write the functions realized for: (a) S = 0110 and (b) S = 0011. [1 + 1 = 2]
(c) What value of S is required to realize: (a) XOR function, and (b) OR function? [1 + 1 = 2]

2. The four-variable AOI function is defined as: AOI(a,b,c,d) = (a ∧ b) ∨ (c ∧ d). Define the ITE operator on v,g,h as: ITE(v,g,h) = vg + v0h. Derive the AOI function using the ITE operator, and hence, draw the logic diagram of an 2:1 multiplexer based implementation of the AOI function. Your logic diagram should exactly match the expression you have derived. [4 + 2 = 6]
3. Provide a derivation for the numerical value of the 2’s complement of a binary number X, in terms of the value of X, where X is a n-bit unsigned binary number with a leading 0. [3]
1
4. Does Booth’s multiplication offer a speed advantage over shift-and-add multiplication? If so, under what situation? [2]
5. Consider the following Verilog code segment:
module incomp_state_spec (curr_state, flag); input [0:1] curr_state; output reg [0:1] flag;
always @ (curr_state) case (curr_state)
0, 1 : flag = 2;
3 : flag = 0;
endcase endmodule
Draw the logic diagram of the circuit corresponding to this code segment that would be inferred during the logic synthesis process. [5]
6. Consider the implementation of a Full Adder (FA) of with two Half Adders (HA). HAs are implemented with
XOR and NAND gates only. Write the expressions for the worst-case delay of an n-bit Ripple Carry Adder
(RCA), in terms of the delay of an XOR gate (tXOR) and an NAND gate (tNAND). [4]
7. Consider an n-bit adder capable of adding two operands represented as X = xn−1xn−2 …x0 and Y = yn−1yn−2 …y0. The production of the i-th sum bit Si can be decomposed into two parts: (i) obtaining the i-th carry-in bit Ci, followed by (ii) computing the sum bit Si. Consider the following three signals:
• Propagate: pi = xi ⊕ yi
• Generate: gi = xi · yi

• Kill: ki = xi + yi
Answer the following:
(a) Give the expression for the carry-out (Ci+1) in terms of gi, pi and the carry-in (Ci), for the i-th bit slice.
[2]
(b) Give the expression for the complement of the carry-out ( ) in terms of ki, pi and complement of the carry-in (Ci0), for the i-th bit slice. [2]
(c) Give the general expression for the carry-out (Ci+1) in terms of gi, pi and the input carry-in (C0), for any 0 ≤ i ≤ n − 1. [3]
(d) (Fill in the blanks) The AND-OR realization of Ci+1 requires: (a) one OR gate with inputs, and, (b) AND gates in total (irrespective of the number of inputs). [2 + 2 = 4]
(e) Assume that the delay of an n-input AND gate is tAND,n and that of an n-input OR gate is tOR,n. Write an expression for the worst-case delay of a 4-bit Carry Lookahead Adder (CLA), denoted by tCLA−4, in terms of tAND,n and tOR,n. [3]
2