Homework
#2
SC700 -- Internet Information Protocols
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.