Homework #2

SC700 -- Internet Information Protocols

Boston University


Assigned:  October 9

DUE:  October 29 at the beginning of class
SPECIAL NOTE:  Problems 3 and 4 must be done individually (i.e. without consultations with any other person).


1.  [20 points]  Fast Ethernet transmits packets of length 46-1500 bytes, depending on the amount of data encoded.  Each packet includes a 32-bit CRC checksum, which safeguards its contents.  Assuming an ARQ protocol is used for error-detection and that the transmission medium can be modeled as a Binary Symmetric Channel.  Assume further that the average packet length is 300 bytes.

What is the crossover probability of the BSC at which severe failure occurs, specifically the probability of retransmission is 50%?  Note:  You will have to approximate this.  For example, you should assume that the CRC checksum practically catches all errors on the channel.

2.  [30 points] You are to design a 21 bit counter with the following features:

a) it is encoded in between 4 and 6 bytes (inclusive);

b) if any 8-bit byte is incorrect, it can be detected and corrected;

c) incrementing the counter should modify 3 bytes or less.

Ideally, your counter should require as little hardware to implement as possible.

This problem was initially presented by Myron Loewen at Microchip.com based on their need for a robust and efficient EEPROM counter.

3.  [30 points] You have been hired by an internet firm to design the error-correction protocol for MPEG delivery over a noisy T1 line.  Specifically, the company delivers full MPEG video and audio (i.e. roughly 5.8 Kbytes/frame) at 15 frames/sec.

Through careful experiments, you have determined that the T1 line typically exhibits at most one error every 10 bits.  Moreover, you are allotted enough memory in the protocol for at most 8 trellis states (at any time) in your decoding.  Your job is to design an error-correcting code to fit these constraints.

a)Give the generator matrix for your code.

b)Draw the trellis corresponding to your generator matrix that meets the stated requirements.

4.  [20 points] Construct a 3-regular graph with girth 5 using as few vertices as you can.  Simulate (in any environment you wish) the sum-product algorithm on this graph over a binary symmetric channel with crossover probability p, and plot the probability of correct decoding versus p.