Solutions for Problem Set 4

Problem 1: (10 points)

  The 90 bits of 0's and 1's should be represented by the alternative way
  because there is no repetitions longer than 8 in 90 bits. So, we need
  90
  -- * 10 = 100 bits to represent the 90 bits in the compressed representation.
   9

  For the n repetitions of the bit 0, we would get no compression at all
  if we did not apply the run-length encoding to it. So the value of n must
  be greather than 9. There are two cases:

  The value of n can be found by solving the following equation:

  _  _
 | n  |					     _ _
 |--- | * 10  + 100 <= (n + 90) * 80%, where|   | denotes ceiling. 
 |255 |
(i.e.the smallest integer greater than or equal to the number)

 Let n = 255 * k + r, where k and r are integers and 0 <= r <= 254. The
 fomular (1) can be transformed to 
 (255k + r) * 0.8 - (k+1) *10 >= 28. 

 When k >= 1, the above equation must be right.
 When k = 0, we get r >= 48.

 So, n must be greater than 48.

 (The compression rate is an increasing function of n.)

Problem 2: (10 points)

  Step 1: 0100101 (4,3,0) = 01001010100
  Step 2: 01001010100 (8,7,1) = 0100101010001010101
  Step 3: 0100101010001010101 (17,9,1) = 01001010100010101010010101001
  Step 4: 01001010100010101010010101001 (8,6,1) = 010010101000101010100101010011010101

Problem 3: (10 points)

  a. BC = 10111100
  d. 10 = 00010000

Problem 4: (10 points)
  The total number of cells is 4M. From 1M = 2 to the 20th power, we know
  4M = 2 to the 22th power. The memory address always starts from 0, so
  the largest memory address is 3FFFFF.

Problem 5: (10 points)
 (1) x + y + z

  Step 1: LOAD a register with the value of "x" from the memory.
  Step 2: LOAD another register with the value of "y" from the memory.
  Step 3: ADD the contents in the second register to the first register and
          leave the result in a third register.
  Step 4: LOAD the fourth register with the value of "z" from the memory.
  Step 5: ADD the contents in the fourth register to the third register and
          leave the result in the fifth register.
  Step 6: STORE the contents of the fifth register in memory.
  Step 7: Stop.

 (2) (2x) + y

  Step 1: LOAD a register with the value of "x" from the memory.
  Step 2: ADD the contents in the first register to itself and leave the
          result in the second register.
  Step 3: LOAD the third register with the value of "y" from the memory.
  Step 4: ADD the contents in the second register to the third register
          and leave the result in the fourth register.
  Step 5: STORE the contents in the fourth register in memory.
  Step 6: Stop.



Problem 6:

(a)
Instruction 1: 1004-- LOAD the register 0 with the contents in the memory
                      cell at address 04.
Instruction 2: 3045-- STORE the contents in the register 0 in the memory
		      cell at address 45.
Instruction 3: C000-- HALT.

(b)
When the machine halts, the bit pattern in the memory cell at the address
45 is the contents in the memory cell at the address 04.

(c)
PC is 06 when the machine halts.