Problem I (Multiplication, 8 pts)

1.   Use the Shift-and-Add algorithm to multiply the following numbers, given in two’s complement: -45 and - 18 (4 pts)

2.   Compute the minimum cost (in term of number of additions/subtractions) of multiplying the two positive numbers 11101110 and 101010100 using the following algorithms:

a.   Shift-and-Add Algorithm (2 pts)

b.   Booth’s Multiplication Algorithm (2 pts)

Problem II (Memory, 10 pts)

Assume that we have only 4x4 ROM memory modules available in our RTL component library. Using the available memory components, sketch the internal design of an 8x6 ROM that stores the following values:

Unspecified addresses are don’t cares.

Problem III (Adder Components, 8 pts):

We want to implement a 64-bit adder using a library that contains 4-bit, 8-bit and 16-bit carry lookahead adder components.

Your design must be uniform, i.e., you can only use all 4-bit adders, all 8-bit adders, OR all 16-bit adders.

Provide the architecture of the adder with:

a.  The minimum cost (in number of gates) (3 pts)

b.  The minimum delay, assuming all gates have the same propagation delays pd

(3 pts)

c.   Can your design achieve minimal cost and delay simultaneously? (2 pts)

Problem IV (Control Path and Data Path Design, 22 pts)

Provide the architecture of a processor, specifically tailored to compute the following pseudocode algorithm: Assume that the 4-bit data inputs (A and B) and outputs (C) are directly connected to the data path through  three different buses, IN_BUS_A, IN_BUS_B and OUT_BUS.

A computation starts with A and B placed on IN_BUS_A and IN_BUS_B and a start signal s set 1. The    controller will then process and set a done signal to 1 upon completion. Additionally, the controller will not move back to the initial state until s = 0. Because the values on the input bus may change during the       computation, they need to be loaded into registers before starting.

a.   Identify the data path components and their interconnections (5 pts)

Do not worry about the interior construction of the components themselves. State any assumptions you make about your components.

b.   Show the block diagram (control path + data path), showing all control and status signals between the two, as well as any inputs and outputs to the system as a whole. (2 pts)

c. Design your controller as Moore automaton and show the implementation as microprogrammed unit. (15 pts)

Problem V (MIPS Processor, 18 pts)

Given the single-cycle MIPS processor below, show the data value at the following annotated points A-F after the execution of the block of code in order

The contents of register file, the data memory, and the instruction memory is as follows:

Initial state of the program. All values are in decimal.