Description

Problem 1: Write a program (in any language) that generates an n − bit frame for transmission from a k − bit data block D and a (n − k +1) bit CRC pattern P.
Instruction to compile the code:
g++ -o CRC code.cpp ./CRC
• The code will ask for data size and the pattern.
• It generates the data randomly of size = data size given above.
• It then generates the CRC frame.
• It then generates a random error pattern and infects the CRC data with it and then checks for presence of a error (Accept or Discarded).
Problem 2: In the Go-back-N ARQ mechanism using k − bit sequence numbers, why is the window size limited to 2k −1 and not 2k ?
The reason for limiting the window size to 2k − 1 in k bit sequence number is so that the transmitter upon receiving of a acknowledgment can distinguish between the following cases:
• Is the acknowledgment a cumulative acknowledgment for all the sent frames.
• Or does the acknowledgment mean that hat all sent frames were damaged or lost in transit, and the receiving station is repeating its previous RR.
For eg:
• Consider case of 3− bit sequence number (i.e. sequence number space is 8)
• Suppose sender sends frame 0 and gets back an RR 1.
• Then sender sends frames 1,2,3,4,5,6,7,0 and gets another RR1.
• This could mean that all eight frames were received correctly and the RR1 is a cumulative acknowledgment.
• It could also mean that all eight frames were damaged or lost in transit, and the receiving station is repeating its previous RR1.
This problem could be solved by limiting the window size to 2k −1.
Problem 3: What is the maximum window size that can be used in the Selective-Reject ARQ mechanism that uses k−bit sequence numbers? Explain your answer.
• Consider the case of a 3-bit sequence number size for selective-reject
• Sender sends frames 0 through 6.
• Receiver receives all seven frames and cumulatively acknowledges with RR7.
• Because of a noise, the RR7 acknowledgment is lost.
• Sender undergoes a timeout and again re-transmits frame 0 because the sender has not yet received any acknowledgment.
• Since the receiver has already acknowledged previous 7 frames(from 0 to 6), its receiving window is currently 7,0,1,2,3,4 and 5.
• On receiving the re-transmitted frame 0, the receiver thinks that it a new frame 0 and that the frame 7 has been lost. Hence it accepts frame 0 and sends SREJ7 to sender.
Problem 4: A channel has a data rate of 4kbps and a propagation delay of 20ms. For what range of frame sizes does stop-and-wait give an efficiency of at least 50%?
Solution:

Let us assume that the frame size is x kb.

For efficiency of atleast 50%,

Hence the minimum frame size should be 160 bits for efficiency of atleast 50%.
Problem 5: Consider a frame consists of one character of 4 bits. Assume that the probability of bit error is 10−3 and that it is independent in each bit.

The bit errro probability is independent for each bit.
(a) What is the probability that the received frame contains no errors?
Solution:

(b) What is the probability that the received frame contains at least oneerror?
Solution:

(c) Now assume that one parity bit is added. What is the probability thatthe frame is received with errors that are not detected?
Solution: One Parity bit is added. We need to calculate probability of frame received with error but not detected.
• Case 1: Parity bit is correct in received frame
In this case there can be even number of bits that can be flipped for the error to remain undetected.

• Case 2: Parity bit is incorrect in received frame
In this case there can be odd number of bits that can be flipped for the error to remain undetected.

So finally,

Problem6: For P = 110011 and M = 11100011, find the CRC.
Solution:

Figure 1: CRC Derivation from Modulo 2 Method
Problem7: (a) In a CRC error-detecting scheme, choose P(x) = X4+X+1.
Encode the bits 10010011011.

Figure 2: CRC Derivation from Polynomial Method
Problem 7: (b) Suppose the channel introduces an error pattern 100010000000000 (i.e., a flip from 1 to 0 or from 0 to 1 in position 1 and 5). What is received?
Can the error be detected?

Figure 3: Error Detection
Problem 7: (c). Repeat part (b) with error pattern 100110000000000.

Figure 4: Error Detection