Chapter 2 - Homework Solutions

My solutions to the homework exercises appear in these boxes below the problem. 

Enjoy... yow, bill

1. Complete problem 1 on page 113. Hint: nano-seconds are 10^-9 seconds, and MIPS are 10^6 instructions per second 

Execution of a single instruction will take:
    5 ns (loading registers)
 + 10 ns (ALU processing)
 +  5 ns (write back result)
   -----
   20 ns/instr

With the time per instruction, take the inverse to get the instructions per second (adjusting units to MIPS):

    20 ns/instr
  = 20 * 10^-9 sec/instr
  = 2 * 10^-8 sec/instr
Now, get inverse for instr/sec
 
    1/2 * 10^8 instr/sec
  = 0.5 * 10^8 instr/sec
  = 50 * 10^6 instr/sec
  = 50 MIPS

 

2. Complete problem 11 on page 114

The "trick" to these problems is recognizing that an n-bit memory address allows 2^n cells. It is not "possible" to address more cells than this and it's not "reasonable" to waste address bits and address fewer cells. The cell size has no relationship to the number of bits in the address.

a. 10 bit address, 1024 cells, 8 bit cell size

Reasonable.

The 10 bit address can reach 2^10 (1024) cells.

b. 10 bit address, 1024 cells, 12 bit cell size

Reasonable.

The 10 bit address can reach 2^10 (1024) cells. The different cell size has no impact.

c. 9 bit address, 1024 cells, 10 bit cell size

Not possible.

A 9 bit address can only access 2^9 (512) cells.

d. 11 bit address, 1024 cells, 10 bit cell size

Not reasonable.

An 11 bit address can access 2^11 (2048) cells, so one bit of the address would be wasted.

e. 10 bit address, 10 cells, 1024 bit cell size

Not reasonable.

A 10 bit address can access 2^10 (1024) cells, so most of your address bits would be wasted in this scheme. 10 cells would only require 4 address bits.

f. 1024 bit address, 10 cells, 10 bit cell size

Not reasonable.

A 1024 bit address can access 2^1024 (a very large number) cells, so most of your address bits would be wasted in this scheme.

3. Complete problem 13 on page 115

Memory amounts are typically powers of 2 because an n-bit address can access 2^n cells.

Of course, memory/computer manufacturers aren't dumb, and the powers of 2 have been rounded to their closest decimal value:

  • 10 address bits gives 2^10 1 byte cells = 1KB (kilo-byte)
  • 20 address bits gives 2^20 1 byte cells = 1MB (mega-byte)
  • 28 address bits gives 2^8 * 2^20 1 byte cells = 256 MB
  • 30 address bits gives 2^30 1 byte cells = 1GB (giga-byte)

4. Complete problem 29 on page 116

Even though a bit map terminal can display 2^24 different colors, it can only display 2^8 (256) different colors at one time. The choice of these colors is made using a color palette which is an index that maps each 8 bit color number to a 24 bit RGB (yes, 8 bits for each color: red, green, blue) value. Get it?

BTW, this method is also used by the GIF image file format that is prominently used on the web.

5. Complete a Hamming code for 4 data bits using the Venn diagram approach on page 63. This should require 3 check bits.

Yes, peek at the Venn diagrams on page 63. It has 7 regions. The A, B and C regions will be used as the 3 parity bits that comprise the code. The 4 intersection regions (AB, ABC, AC, BC) will map onto the 4 bits of the data value: bit 1 is AB, bit 2 is ABC, bit 3 is AC, bit 4 is BC. This mapping is arbitrary; you just need to be consistent once you chose what bits are assigned where.

With this mapping, the 3 code bit for each 4 bit data value can be determined. Each parity bit is assign 0 if there are an even number of 1's in its region and 1 if there are an odd number of ones. Let's try a couple:

  • Data = 0000. This is easy. With zeros in AB, ABC, AC, and BC all parity values (A, B, C) will be 0 because there are no 1's present. So, the code bits for 0000 are 000.
  • Data = 0001. With a 1 in the BC region, the A region has no 1's and gets a value of 0. The B region has one 1, and is assigned 1... same for the C region. So, the code bits for 0001 are 011.

Continue is the same fashion for the rest of the data values. The result of this is shown in the table below:

Data Code
0000 000
0001 011
0010 101
0011 110
0100 111
0101 100
0110 010
0111 001
1000 110
1001 101
1010 011
1011 000
1100 001
1101 010
1110 100
1111 111

Now, let's see if this puppy works. If the original data word is 0000 and, through some error, a value of 0001 is received, then:

Received: 0001 000

This is not a value codeword, using the table above. Search for the nearest code that matches this.

  • 0000 000 is 1 bit away
  • 0001 011 is 2 bits away
  • 0010 101 is 3 bits away
  • and so on...

Since, 0000 000 is the closest codeword, then the data value of 0001 would be corrected to 0000.

One more try. If the original data word is 1111, and a value of 0111 is actually received, then:

Received: 0111 111

This is not a value codeword, using the table above. Search for the nearest code that matches this.

  • 1111 111 is 1 bit away
  • 0100 111 is 2 bits away
  • and so on...

Since, 1111 111 is the closest codeword, then the data value of 0111 would be corrected to 1111.