Problem Set 3

Due: September 27th, before class

Yale N. Patt, Instructor

Siddharth Balwani, Linda Bigelow, Tommy Buell, Jeremy Carrillo, Aamir Hasan,

Danny Lynch, Rustam Miftakhutdinov, Veynu Narasiman, Vishal Parikh, Basit Sheikh, TAs

You are encouraged to work on the problem set in groups and turn in one problem set for the entire group. Remember to put all your names on the solution sheet. Also remember to put the name of the TA in whose discussion section you would like the problem set turned back to you.

- (3.28)
Having designed a binary adder, you are now ready to design a 2-bit by 2-bit unsigned binary multiplier. The multiplier takes two 2-bit inputs

`A[1:0]`

and`B[1:0]`

and produces an output`Y`

which is the product of`A[1:0]`

and`B[1:0]`

. The standard notation for this is:`Y = A[1:0]⋅B[1:0]`

- What is the maximum value that can be represented in 2 bits for
`A`

(`A[1:0]`

)? - What is the maximum value that can be represented in 2 bits for
`B`

(`B[1:0]`

)? - What is the maximum possible value of
`Y`

? - What is the number of required bits to represent the maximum value of
`Y`

? - Write a truth table for the multiplier described above. You will have a four input truth table with the inputs being
`A[1]`

,`A[0]`

,`B[1]`

, and`B[0]`

. - Implement the third bit of output,
`Y[2]`

from the truth table using only`AND`

,`OR`

, and`NOT`

gates.

- What is the maximum value that can be represented in 2 bits for
- (3.33)
Using Figure 3.21, the diagram of the 4-entry, 2

^{2}-by-3-bit memory.- To read from the fourth memory location, what must the values of
`A[1:0]`

and`WE`

be? - To change the number of entries in the memory from 4 to 60, how many address lines would be needed? What would the addressability of the memory be after this change was made?
- Suppose the minimum width (in bits) of the program counter (the program counter is a special register within a CPU, and we will discuss it in detail in the next chapter) is the minimum number of bits needed to address all 60 locations in our memory from part (b). How many additional memory locations could be added to this memory without having to alter the width of the program counter?

- To read from the fourth memory location, what must the values of
- (3.41)
The IEEE campus society office sells sodas for 35 cents. Suppose they install a soda controller that only takes the following three inputs: nickel, dime, and quarter. After you put in each coin, you push a pushbutton to register the coin. If at least 35 cents has been put in the controller, it will output a soda and proper change (if applicable). Draw a finite state machine that describes the behavior of the soda controller. Each state will represent how much money has been put in (Hint: There will be seven of those states). Once enough money has been put int, the controller will go to a final state where the person will receive a soda and proper change (Hint: There are five such final states). From the final state, the next coin that is put in will start the process again.

- (3.44)
*modified*Prove that the

`NOR`

gate, by itself, is logically complete (see Section 3.3.5) by constructing a logic circuit that performs the`AND`

function, a logic circuit that performs the`NOT`

function, and a logic circuit that performs the`OR`

function. Use only`NOR`

gates in these three logic circuits. The frequency of a computer is inversely proportional to its clock cycle time. That is to say, Frequency = 1/Cycletime, e.g.: a 1GHz computer has a clock cycle time of 1 nanosecond (10

^{-9}seconds).Instructions may broadly be divided into those that access memory (loads and stores), those that perform arithmetic/logic operations(

`ADD`

,`AND`

,`OR`

etc) and other instructions such as branch and jump instructions (these determine what is known as control flow). An instruction can take multiple clock cycles to execute. Let us assume that in a particular computer memory access instructions take 12 clock cycles to execute, arithmetic instructions take 9 clock cycles to execute, while other instructions take 10 clock cycles to execute.The approximate percentages of occurrence of these instructions in a given program, on an average, are:

Type of Instruction Percentage of Occurence Memory Access instructions 40% Arithmetic and Logic instructions 40% Other Instructions 20% On a 3.2 GHz machine, assuming everything goes smoothly, estimate how long will this 650,000 instruction program take to execute?

- (4.4)
What is the word length of a computer? How does the word length of a computer affect what the computer is able to compute? That is, is it a valid argument, in light of what you learned in Chapter 1, to say that a computer with a larger word size can process more information and therefore is capable of computing more than a computer with a smaller word size?

- (4.7)
Suppose a 32-bit instruction takes the following format:

`OPCODE`

`DR`

`SR1`

`SR2`

`UNUSED`

If there are 255 opcodes and 120 registers,

- What is the minimum number of bits required to represent the
`OPCODE`

? - What is the minimum number of bits required to represent the Destination Register (
`DR`

)? - What is the maximum number of
`UNUSED`

bits in the instruction encoding?

- What is the minimum number of bits required to represent the
- (4.10)
Examples 4.1, 4.2, and 4.5 illustrate the processing of the

`ADD`

,`LDR`

, and`JMP`

instructions. The`PC`

,`IR`

,`MAR`

, and`MDR`

are written in various phases of the instruction cycle, depending on the opcode of the particular instruction. In each location of the table below, enter the opcodes which write to the corresponding register (row) during the corresponding phase (column) of the instruction cycle.Fetch Instruction Decode Evaluate Address Fetch Data Execute Store Result `PC`

`IR`

`MAR`

`MDR`

- (4.15)
If a

`HALT`

instruction can clear the`RUN`

latch, thereby stopping the instruction cycle, what instruction is needed to set the`RUN`

latch, thereby reinitiating the instruction cycle? Suppose that an instruction cycle of the LC-3 has just finished and another one is about to begin. The following table describes the values in select LC-3 registers and memory locations:

Register Value `IR`

`x3001`

`PC`

`x3003`

`R1`

`x3000`

`R2`

`x3002`

Memory Location Value `x3000`

`x62BF`

`x3001`

`x3000`

`x3002`

`x6280`

`x3003`

`x62BE`

For each phase of the new instruction cycle, specify the values that

`PC`

,`IR`

,`MAR`

,`MDR`

,`R1`

, and`R2`

will have*at the end*of the phase in the following table:`PC`

`IR`

`MAR`

`MDR`

`R1`

`R2`

Fetch Decode Evaluate Address Fetch Operands Execute Store Result Hint: Example 4.2 illustrates the

`LDR`

instruction of the LC-3. Notice that values of memory locations`x3000`

,`3002`

, and`3003`

can be interpreted as`LDR`

instructions.-
Added September 21.

We want to make a state machine for the scoreboard of the Texas vs. Oklahoma Football game. The following information is required to determine the state of the game:

Score: 0 to 99 points for each team

Down: 1, 2, 3, or 4

Yards to gain: 0 to 99

Quarter: 1, 2, 3, 4

Yardline: any number from H0 to H49, V0 to V49, 50

Possesion: H, V

Time remaining: any number from 0:00 to 15:00, where m:s (minutes, seconds)

What is the minimum number of bits that we need to use to store the state required?