COMPUTER ARCHITECTURE EXERCISES READING ------- Notes for lectures 1, 12 and 13 EXERCISES --------- 1. An 8-bit linear feedback shift register operates by the following rules: With bits numbered 0 through 7 from right to left, bit i gets the value of bit i-1 at each time step for i from 1 to 7, and bit 0 gets the ``exclusive or'' of bits 0 and 5. Suppose that the register initially contains the bits 1 0 1 0 1 0 1 0 . Give the contents of the register after 1000 time steps. 2. Suppose that we connect a three-bit counter to the select, input and read/write lines of a memory bit, as follows: Give the value of the output line after each tick when the counter ticks seven times, assuming everything to be initially 0. 3. Give the value of the output line after each tick when the counter of the previous exercise ticks another 8 times (the first of these ticks wraps the counter value back to 0). 4. In the circuit below, the lines are ordered from top to bottom and left to right. To use the adder to compute 2 + 2 = 4, we would put 0 0 1 0 0 0 1 0 on the adder inputs and read 0 1 0 0 on the outputs (reading top to bottom). What is the output when the inputs are all 0? 5. In the previous exercise, all but one of the inputs, when switched to 1, will cause the output to switch 0. Which one is the exception? 6. What is the effect of wiring the output of a D flip-flop to its input? 7. What is the result of computing the AND of all the output lines of a decoder? Answer the same question for OR. 8. What is the result of wiring the output of a decoder to the input of a multiplexer, using the same address lines (see diagram below)? . . . . ANSWERS TO COMPUTER ARCHITECTURE EXERCISES 1. 7 6 5 4 3 2 1 0 --------------- 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 2 1 0 1 0 1 0 1 0 . . . odd 0 1 0 1 0 1 0 1 even 1 0 1 0 1 0 1 0 The same phenomenon occurs if we replace the "bit 5" tap by any odd bit position. Exercise: what happens with the even bit positions? 2. Memory bit follows these basic rules: select 0: 0 -> output select 1 and read/write 1: input -> bit; 0 -> output select 1 and read/write 0: bit -> output I R/W S bit out 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 1 1 0 0 1 0 0 0 0 1 0 1 0 0 1 1 0 0 0 1 1 1 1 0 3. 0 0 0 1 0 0 0 1 0 1 0 1 0 0 0 0 1 1 0 0 1 0 0 0 0 1 0 1 0 0 1 1 0 0 0 1 1 1 1 0 4. The decoder output is 0 except for line 0, so the adder computes 0 0 0 0 + 0 0 0 1 = 0 0 0 1. The multiplexer input is 0, so it picks line 0, which is 1. 5. Here are the adder computations when the indicated bit is set to 1, with the multiplexer choice circled: s 0 0 0 1 + 0 0 0 0 = 0 0 0 1 t 0 0 0 0 + 0 1 0 0 = 0 1 0 0 u 0 0 0 0 + 0 0 1 0 = 0 0 1 0 v 0 0 0 0 + 0 0 0 1 = 0 0 0 1 w 0 0 0 0 + 0 0 0 1 = 0 0 0 1 6. It gets stuck at whatever the initial value of the input was. If 0, then the first clock pulse produces "reset" which keeps the input at 0. If 1, then the first clock pulse produces "set" which keeps the input at 1. 7. Exactly one of the outputs is 1, and the rest 0, so the AND is always 0 and the OR is always 1. 8. Always produces 1. The decoder produces 1 on whatever output line is addressed; the multiplexer selects that line.