exam
Bob_Usher
Exam2-TakeHome.docx
EENG 415 (Introduction to Computer Networks)
Summer 2019
Exam 2
Take Home
Individual work is expected on this exam. If it is determined that collaborative effort took place all of the individuals involved will be assigned the lowest score earned by one or more of those involved and that lowest score will be divided by the number of people involved. In other words if 3 people are determined to have collaborated on the exam they will all be assigned the lowest score earned by one the three and that score will be divided by 3.
I am available to answer any questions you might have about the exam.
Name:____________________________________________________
Problem 1: Framing Methods [10 points]
a) For the bit stream below, name an appropriate framing method that would allow the receiver to identify the start of new frames.
1 1 1 0 0 1 1 1 1 1 1 1 010111111111000011110111111
b) The bit stream above represents original data. Using the method you have identified as appropriate to identify the start of new frames, modify the above bit stream for transmission i.e. encode correctly the data above using your method.
c) How does the receiver treat the encoded bit stream and prepare it for storing?
Problem 2: Hamming Codes [20 points]
Assume that the English alphabet consists of five letters: a, e, i, o, and u.You are told that all possible messages can only use these five letters.
a) How many possible ways can you map these characters/letters into a 4-bit codeword? No need to consider parity and no need to reference the ASCII table you just need 4-bits as a codeword to represent a letter.
b) How would you map the five letters to 4-bit codewords such that the Hamming Distance of the dictionary is maximized? In other words you want to separate out these five characters/letters in Hamming Distance space as much as possible
c) What is the Hamming Distance of your Dictionary?
d) How many total characters properly mapped to codewords so that you can correct 2-bit errors, can you have in your dictionary?
Problem 3: Single Parity bit [10 Points]
[11000101] is an 8-bit data codeword before appending a parity bit. Please append a parity bit to this codeword such that:
a) The resulting encoded codeword has even parity
b) The resulting encoded codeword has odd parity
c) Would all possible errors be detected when using even parity? Provide an example to support your answer.
d) Would all possible errors be detected when using odd parity? Provide an example to support your answer.
Problem 4: Multiple Parity Bits [20 Points]
Suppose our data is 4-bits [d1, d2, d3, d4] and we chose to add three check bits at the end [c1, c2, c3] so that the encoded codeword becomes [d1, d2, d3, d4, c1, c2, c3].
a) Provide all the possible values in binary that our check bits can take.
b) Given that our data is: [d1, d2, d3, d4] = [1 1 0 0] find [c1, c2, c3] and provide
c) The encoded codeword that will be transmitted.
d) Show how many errors can be corrected
Problem 5: Generator Polynomial for the Cyclic Redundancy Checksum [40 points]
Let D be the bitstream received by the Data Link Communication (LC) layer from the Internet Protocol (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 and D = 1000001
a) Find G.
b) Find D(x).
c) Let be the degree or order 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) respectively. Find Q and R.
h) Let P(x) = A(x) R(x), where `' 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 ) which would go undetected. Also explain in detail why that error pattern will go undetected.
Extra Credit Problems
Points earned on these problems constitute extra credit
Problem 6: More on Checksum Algorithm [40 Points]
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 third 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 transmitted 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.
Problem 7: Message Framing [40 Points]
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.
Problem 8: Go-Back N [20 Points]
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?
