Networks Assignment - Due in 4 hours

3589385_50150937_MIDTERM_1.pdf

Home >Engineering homework help >Electrical Engineering homework help >Networks Assignment - Due in 4 hours

Midterm 1, due by 10.00 am, Wednesday 07.25.18 (This is an individual test, worth 150 points. You may consult any printed/web-based resource you want, but

you may not discuss this test with anybody.)

July 23, 2018

1. [worth 40 points total] 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. (2 points)

(b) Find D(x). (2 points)

(d) Let A(x) = D(x) xβ. Find A(x). (2 points)

(e) Let A be the bit-domain representation of A(x). What is A? (2 points)

(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). (5 + 5 = 10 points)

(g) Let Q and R be the equivalent bit-domain representations of Q(x) and R(x) re- spectively. Find Q and R. (2 + 2 = 4 points)

(h) Let P(x) = A(x) R(x), where ‘ ’ denotes subtraction using modulo 2 arithmetic. Find P(x). (2 points)

(i) Let P be the bit domain representation of P(x). This is the transmitted frame after error control coding. What is P? (2 points)

(j) The received polynomial P ′(x) can be written as the sum of the transmitted poly- nomial P(x) and an error polynomial E(x). That is:

P ′(x) = P(x) + E(x)

Suppose E(x) = x5 + x4 + x3 + x + 1. Will this error pattern be detected by the receiver? (12 points)

2. [worth 20 points total] A 8-bit checksum is to be appended to the following sequence of four 8-bit words [11011000, 10001111, 00010010, 10101001, checksum].

(a) Compute the checksum (in binary form). You must show all steps leading to your answer, as shown on slide 41 of Part-1 of Chapter-3 notes. (5 points)

(b) Suppose the channel flips the 13th and 16th bits of the transmitted frame (i.e., the fifth and eighth bits of the second 8-bit word). Will the receiver be able to detect this error? Explain your answer. (5 points)

(c) Suppose the channel flips the 1st, 2nd, 5th, 7th, 17th, 18th, 21st, and 23rd bits of the transmitted frame. Will the receiver be able to detect this error? Explain your answer. (5 points)

(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. (5 points)

3. [worth 20 points total] Suppose the English alphabet only contained the vowels 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. Assume that there is no parity check bit.

(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)? (12 points)

(b) What is the Hamming Distance of your dictionary? (4 points)

(c) How many total characters can you have in your dictionary (properly mapped to codewords) so that you could correct 1-bit errors, assuming that each character is still represented by 4 bits? (4 points)

4. [worth 30 points] Two hosts A and B are connected by a 200 km. long 100 Kbps link. Assume that the transmission medium is a copper cable (speed of light through copper is roughly 2×108 m/s). The hosts have adopted a Stop-and-Wait DLC protocol. Host A is the transmitter (sends data frames) and host B is the receiver (sends only ACK frames). The following additional parameters are given:

• all data frames sent by host A are 1000 bits each • all ACK frames sent by host B are 100 bits each • processing delays at both hosts are negligible.

(a) Suppose host A has 10 data frames to send to B. The transmission process starts at time t = 0. At what time can the communication process be considered complete, as- suming that the channel does not make any error? You must show all intermediate work which leads up to your answer. (20 points)

(b) Repeat part (a), except, consider that each frame has a probability of error of Pf = 0.1. That is, what is the expected time at which the communication process can be considered complete? (10 points)

5. [worth 20 points total] Suppose you have a 5×5 data array which you have planned to protect with row and column odd parity bits (which means that the receiver is expecting odd parity checks), as shown in eqn. (1). You are processing the array row by row, starting with the first row and computing the check bit c16, then the second row and computing the bit c26, etc. While computing the sixth row of check bits, you inadvertently make an error in your code (or involuntarily suffer from a lapse in concentration if you prefer hand calculations) and, instead of providing odd parity on the columns, you implement even parity, including the sixth column.

0 0 0 0 0 c16 0 1 0 1 0 c26 0 1 1 1 0 c36 1 0 1 0 1 c36 1 1 1 1 1 c46 c61 c62 c63 c64 c56 c66

(1)

(a) Compute all the check bits. (5 points)

(b) How will the receiver behave if it gets the frame correctly? Of course, the receiver does not know about the goof-up at the transmitter end. (5 points)

(c) Find an example of an error pattern which will maintain odd parity along both dimensions. You can assume that the check bits are also susceptible to errors, but you cannot alter the sixth row of the array you computed in part(a) above. Be sure to put a box around the errored bits so that I can clearly identify your error pattern. (10 points)

6. [worth 20 points total] In class, we talked about bit stuffing when the flag is the special bit stream 0160 (zero, then six ones, then zero). Instead of 0160, suppose we use the flag 1061 (one, then six zeros, then one).

(a) What would be the stuffing rule at the transmitting DLC? (5 points)

(b) Suppose the payload field is 100000110000011. Show the payload field after stuffing, using the stuffing rule of (a). Be sure to put a box around the stuffed bits so that I can clearly identify those. (10 points)