H.W

Problem 1: Error Control Coding and Detection [25 Points] Suppose a (transmitter, receiver) pair have agreed to use the generator polynomial 𝐺𝐺(𝑥𝑥) = 𝑥𝑥2 + 1 for error control coding and detection. Let 𝑃𝑃, the transmitted bit stream after error control coding, be 1100110. Due to channel imperfections, the receiver receives the polynomial 𝑃𝑃′(𝑥𝑥), 𝑃𝑃′(𝑥𝑥) ≠ 𝑃𝑃(𝑥𝑥). However, the degree of 𝑃𝑃′(𝑥𝑥) is equal to the degree of 𝑃𝑃(𝑥𝑥).

a) Find an example for 𝑃𝑃′(𝑥𝑥) which will go undetected by the receiver. [10 points] b) Find the Hamming distance between 𝑃𝑃(𝑥𝑥) and the 𝑃𝑃′(𝑥𝑥) you found in (a). [5 points] c) Suppose that the probability of bit error is independent and identical for all bits, and is

equal to 10−2. Find the probability that 𝑃𝑃′(𝑥𝑥) (the specific 𝑃𝑃′(𝑥𝑥) you found in (a)) is received when 𝑃𝑃(𝑥𝑥) is transmitted. Based on your computed probability, how likely do you think it is that the receiver will receive 𝑃𝑃′(𝑥𝑥) when 𝑃𝑃(𝑥𝑥) is transmitted? [10 points]

Problem 2: Stop and Wait Protocol [20 Points] Consider a conventional Stop-and-Wait protocol (i.e., if frame 0 is received correctly, the receiver responds with ‘ACK 1’) where host A has two frames (numbered 0 and 1) to be sent to host B. Host B only responds with a properly numbered ACK when it receives something from A; i.e., it does not have any data of its own to send to A. The following sequence of events happened during the transmission process: (i) host A’s first transmission of frame 0 got lost, (ii) host A’s second transmission of frame 0 was successful, (iii) host A’s first transmission of frame 1 as well as the first retransmission attempt were corrupted, followed by a success. Construct a timeline diagram (as shown in class notes) to illustrate the above scenario. Make sure transmissions are properly identified with sequence numbers. Key (Problems 2 and 3)

 Use this symbol to represent a failed transmission on your diagram

 Use this symbol to represent a corrupted transmission.

Problem 3: Stop and Wait Protocol [15 Points] In a conventional Stop-and-Wait protocol (i.e., if frame 0 is received correctly, the receiver responds with ‘ACK 1’), the transmitter has only one frame to send (numbered frame 0). Of course, the receiver does not know that. For some reason, it receives two frames numbered 0 from the transmitter, in succession. Explain what could have triggered it. Illustrate your answer with timeline diagrams. Think carefully, there might be more than one reason (provide all of them if more than one).

Problem 4: Time Taken to Transmit [15 Points] A data frame of 1500 Mb is to be transmitted over a 100 Mbps Ethernet link. The transmitter and the receiver are physically separated by a 10 km long copper cable. Waves travel through copper at a speed of 2×108m/s. The frame is received correctly, and in response, the receiver immediately sends a short ACK frame of 1 Kb which is also received correctly by the transmitter. Compute the end-to-end delay (i.e., the time elapsed between when the transmitter starts to upload the data frame till the time it has completely received the ACK frame). You can ignore processing delays. It will help if you can draw a diagram as shown in your class notes

Problem 5: Error Detection and Correction [10 Points] The possible codewords in a dictionary are 000000 (representing character a), 010101(representing character b), 101010 (representing character c) and 111111 (representing character d). The receiver receives the data vector 110011. If it decides to correct the received data, which character should it map the vector back to?

Problem 6: Generator Matrix [15 Points] In a data communications scheme, three parity check bits are appended to every five data bits, denoted by 𝑑𝑑1, 𝑑𝑑2, 𝑑𝑑3, 𝑑𝑑4 𝑎𝑎𝑎𝑎𝑑𝑑 𝑑𝑑5. Let the check bits be denoted by 𝑐𝑐1, 𝑐𝑐2 𝑎𝑎𝑎𝑎𝑑𝑑 𝑐𝑐3, and computed as follows: 𝑐𝑐1 = 𝑑𝑑1 ⊕ 𝑑𝑑3 ⊕ 𝑑𝑑5, 𝑐𝑐2 = 𝑑𝑑2 ⊕ 𝑑𝑑4, 𝑐𝑐3 = 𝑑𝑑1 ⊕ 𝑑𝑑2 ⊕ 𝑑𝑑3 ⊕ 𝑑𝑑4 ⊕ 𝑑𝑑5, where ‘⊕’ is an exclusive-OR (XOR). Suppose the message vector to be transmitted is [10101].

a) Determine the generator matrix for this communications scheme [5 points]. b) Determine the parity check matrix used by the receiver for this communications scheme.

[5 points] c) Determine the syndrome vector when the channel does not make any error. [5

points]