Question 1. Let D be the bitstream received by the DLC layer from the IP layer. The bitstream D maps to the equivalent polynomial D(x) and vice versa; D ↔ D(x). Also, let G(x) be the generator polynomial of a CRC code and G its equivalent bit-domain representation; G ↔ G(x).
Suppose G(x) = x4 + x3 + x2 + 1 and D = 1000001
(a) Find G.
(b) Find D(x).
(c) Let β be the degree of G(x). What is β?
(d) Let A(x) = D(x) xβ . Find A(x).
(e) Let A be the bit-domain representation of A(x). What is A?
(f) Let Q(x) be the quotient when A(x) is divided by G(x) modulo 2 and R(x) the remainder. Find Q(x) and R(x).
(g) Let Q and R be the equivalent bit-domain representations of Q(x) and R(x) re- spectively. Find Q and R.
(h) Let P (x) = A(x) g R(x), where ‘g' denotes subtraction using modulo 2 arithmetic. Find P (x).
(i) Let P be the bit domain representation of P (x). This is the transmitted frame after error control coding. What is P ?
(j) Find an example of an error pattern (i.e., instead of receiving P , the receiver receives the bitstream P t) which would go undetected. Also explain in detail why that error pattern will go undetected.
Question 2. A 6-bit checksum is to be appended to the following sequence of four 6-bit words [110110, 100011, 000100, 101010, checksum].
(a) Write down the checksum (in binary form).
(b) Suppose the channel flips the 13th and 16th bits of the transmitted frame (i.e., the first and fourth bits of the third 6-bit word). Will the receiver be able to detect this error? Explain your answer.
(c) Suppose the channel flips the 20th, 21st, 22nd, 26th, 27th and 28th bits of the trans- mitted frame (i.e., the 2nd, 3rd and 4th bits of the fourth and fifth words). Will the receiver be able to detect this error? Explain your answer.
(d) Suppose the channel flips the first bit of the transmitted frame. Will the receiver be able to correct this error? Provide proper explanation if your answer is yes. If your answer is no, you can provide a counterexample to prove your point. Of course, you can assume that the receiver does not know how many errors the channel made.
Question 3. Suppose the English alphabet only con- tained the characters a, e, i, o, and u. All possible messages can use only these 5 characters. You want to map each of these characters to 4-bit codewords (there's no parity check bit) such that the Hamming Distance of the dictionary is max- imized (i.e, you want to separate out these three characters in bit space as much as possible).
(a) How would you map the five alphabets to 4-bit codewords such that the Hamming Distance of the dictionary is maximized (i.e, you want to separate out the five characters in Hamming distance space as much as possible)?
(b) What is the Hamming Distance of your dictionary?
(c) How many total characters can you have in your dictionary (properly mapped to codewords) so that you could correct 2-bit errors, assuming that each character is still represented by 4 bits?
Question 4. A (tx, rx) pair is using Go-back N protocol at the DLC layer with N = 4. The transmitter has only four data frames to send to the receiver, starting with frame number 0. The figure below shows certain events. The lightning bolt symbol denotes a frame error and the cross symbol denotes a lost frame. ACK's are cumulative and implicit.
(a) Fill in the data frame numbers (i.e., from tx to rx).
(b) Fill in the ACK numbers (i.e., from rx to tx)
(c) The timeline starts from t = 0, as shown. Fill in the missing time instant values at the transmitter (indicated by ‘?') assuming that each data frame is 1 Kb and the link data rate is 2 Kbps.
(d) For each of the ‘t' values, write down the window at the transmitter (indicated by [ ])
(e) Explain what's going on at the tx in time zones 1 and 2. Why is the tx behaving as it is during these time zones?
Question 5. Suppose node A sends a message which is split up into four frames to node B, where each frame is ten bytes long. Assume that the probability that the channel flips any bit, independently of others, is 0.001.
(a) Compute the probability that any frame is received correctly by node B.
(b) Compute the probability that the message is received correctly by node B.
(c) What is the probability that the last three bits in the first frame sent by node A are in error?
(d) What is the probability that the last three bits in the last frame sent by node A are in error?
(e) What is the probability that any three bits in the first frame sent by node A are in error?
(f) What is the probability that any three bits in the last frame sent by node A are in error?
(g) Suppose node B has no error correction capability. For even a single bit error, it requests a retransmit from node A. Based on your answer in part (b), how many frames do you think node A will need to transmit, on an average, before the message gets through correctly?
(h) Find the probability that the last two frames sent by node A are in error.
(i) Find the probability that any two frames sent by node A are in error.