CSP 214 Written Homework 2 Solutions - Fall, 1997

1. According to Shannon's theorem:
  Max data rate = H*log(1+S/N)=H*log(1+10**(40/10))=H*log(10001)
    approximately 13.3H

According to Nyquist's Theorem:
  Max data rate = 2H*log(V) = 2H*log4 = 4H

Hence the maximum data rate is the minimum of the two, or 4H(bps) .


2. when the number of levels changed to 16
Shannon's limit will not change, while Nyquist' limit is now
  Max data rate = 2H*log16=8H,
Hence the maximum data rate can be as high as 8H.

So yes, we can obtain a higher data rate in 1) if a 16-level encoding
is used.

3. According to Nyquist, sampling at 1000hz, a bandwidth of 500 Hz 
of the signal can be recovered. the maximum data rate is 2*H*Log(V) =
1000*log(V). Since the channel is noiseless, we can get unlimited
data rate by increasing the number of encodings.

4. PCM was intended to cover the bandwidth of human voice carried over
voice-grade analog phone lines, about 4Khz. According to Nyquist's
theorem we need sample at 8000Hz, which means the sampling time is
once every 1/8000th of a second, = once every 125 msec.

5. channel bandwidth H = 68k-4k=64k
   Hence from Shannon's theorem: the rate limit is
      H*log(1+S/N) = 13.28H = 850Kbps
   So such a channel is able to achieve 512Kbps

6  Assume there are n nodes, and each link traversed counts as 1 hop,

	  best 	  avg	worst
   Star:   2       2       2    (i.e., all paths have the same length)
   Ring:   1       n/4     n/2
   fully:  1        1      1


7  Circuit Switched:
     T(c) = s + kd + (x/b) (Note that there are no queuing delays.)
   Packet Switched:
     T(p) = kd + (k-1)(p/b) + (x/p)(p/b)

     in T(p) above:
      kd = time is the total propagation delay experienced by first
           bit of first packet
      (k-1)(p/b) = queuing delay experienced by one packet at each
	   hop, (again, first packet will be delayed this amount)
      (x/p)(p/b) = time to send all the bits of the message (i.e.,
      transmission time. Note that after the first bit of the first
      packet arrives at the destination, we only have to wait for the
      transmission time of the remaining bits. The queuing/propagation
      delays experienced by the other packets overlap with the
      transmission time of other packets.
      
   if T(p) < T(c), then T(c)-T(p)>0, implies s>(k-1)(p/b).

8. Based on the equation T(p) in the above, we have the time to 
   transmit packet is:
     T = (x/p)(p+h)/b+ (k-1)(p+h)/b.

   To get the minimum of T, we take the erivative with respect to p
    and let the derivative be 0 we get p=sqrt(xh/(k-1)).


9. (procedure omitted here) The remainder is  001, 
   and the checksum is: 1011011 001

10. Since data link does no error control, the damage is 
   detected only after all the 10 packets have arrived.
   The probability that all 10 packets are succesfully received
   is p=0.8**10 approx. 0.1074 (i.e., not very good at all!)

   According to probability theory, the probability that 
   transmission will succeed at the nth attempt is
   P(n) = p*(1-p)**(n-1)

   the mean of attempts is E = Sum of P(n)*n where n is from 1 to
   infinity, and E=1/p = 10. 

   Note that this is just the average times that the message needs
   to be sent to achieve a success. There is no guarantee, however,
   that within a definite number of transmissions the message can
   be successfully sent.

11. 1. Hamming distance is 2 (change 110011 -> 111111)
    2. the code can detect 1 single-bit error
    3. the code cannot guarantee to correct any 1 bit error.

12.  Assuming HDLC is used, the outcome would be:
    011110 11111(0) 0 11111(0) 1110

    Note: () around inserted (bit-stuffed) 0, spaces are not
    significant (they are there for readability).