Error Detection - Concept Review

Block Coding
Hamming Distance
Parity check
Cyclic redundancy check
Checksum
Hamming Code

Review Questions

How does a single-bit error differ from a burst error?

Discuss the concept of redundancy in error detection and correction.

Distinguish between forward error correction versus error correction by retransmission.

If we want to detect two-bit errors, what should be the minimum Hamming distance?

In CRC, show the relationship between the following entities (size means the number of bits):

The size of the dataword and the size of the codeword
The size of the divisor and the remainder

What kind of arithmetic is used to add data items in checksum calculation?

What kind of error is undetectable by the checksum?

Can the value of a checksum be all 0s (in binary)? Defend your answer. Can the value be all 1s (in binary)? Defend your answer.

Assume we are sending data items of 16-bit length. If two data items are swapped during transmission, can the traditional checksum detect this error? Explain.

Problems

Note:

ps: 10^-12 s

ns: 10^-9 s

$\mu$ s: 10^-6 s

ms: 10^-3 s

KB : 10^3 B

MB : 10^6 B

GB : 10^9 B

TB : 10^12 B

Burst of noise : $2 \times 10^{-3}$ s

$\text{Vulunerable bits} = \text{data rate} \times \text{burst duration}$

(a) 1500 bps (typo in the question)

Vulunerable bits = $1500bps \times 2 \times 10^{-3}s = 3$ bits

(b) 12 kbps = $12 \times 10^3$ bps

Vulunerable bits = $12 \times 10^3bps \times 2 \times 10^{-3}s = 24$ bits

© 100 kbps = $100 \times 10^3$ bps

Vulunerable bits = $100 \times 10^3 bps \times 2 \times 10^{-3}s = 200$ bits

(d) 100 Mbps = $100 \times 10^6$ bps

Vulunerable bits = $100 \times 10^6 \times 2 \times 10^{-3} = 200000$ bits

(a) 1001011

Number of 1s : 4 (Even)

No need to add 1.

Therefore Parity bit is 0

(b) 0001100

Number of 1s: 2 (Even)

No need to add 1.

Therefore Parity bit is 0

© 1000000

Number of 1s: 1 (Odd)

Need to add 1.

Therefore Parity bit is 1

(d) 1110111

Number of 1s: 6 (Even)

Need to add 1.

Therefore Parity bit is 0

(a)

Hamming pairwise distances:

00000 10101 01010

00000 / 3 2

10101 3 / 2

01010 2 5 /

Hence, the minimum Hamming distance is 2.

(b)

000000 010101 101010 110110

000000 / 3 3 4

010101 3 / 6 3

101010 3 6 / 3

110110 4 3 3 /

Hence, the minimum Hamming distance is 3.

	00000	10101	01010
00000	/	3	2
10101	3	/	2
01010	2	5	/

	000000	010101	101010	110110
000000	/	3	3	4
010101	3	/	6	3
101010	3	6	/	3
110110	4	3	3	/

The inlcusion of a party bit extends the message length

So more bits can be in error.

Sometimes It can even be the parity bit is in error but no error in the data bits.

Therefore the inclusion of a parity bit with each character would change the probability of receiving a correct message.

(a)

Pr[single bit in error] = $10^{-3}$

Pr[single bit not in error] = $1 - 10^{-3} = 0.999$

Pr[8 bits not in error] = $0.999^8 = 0.992$

Pr[at least 1 error in frame] $= 1 - 0.992 = 0.008$

(b)

After Adding a parity bit to each character, 2 parity bits are added.

Pr[10 bits not in error] = $0.999^10 = 0.990$

Pr[at least 1 error in frame] $= 1 - 0.990 = 0.01$

For Generator (Sender):

Setup a long division of (Dataword + extra 0s)

The divisor in a cyclic code is normally called the generator polynomial or simply the generator

the number of extra 0s is equal to (number of bits of divisor -1)

Then XOR operation and get the Remainder(CRC)

Codeword = Dataword + Remainder(CRC)

For Checker (Reciever)

setup a long division of Codeword (or Errored Codeword)

use the same divisor

don’t add any extra 0s this time since we are decoding

Then XOR operation and get the Remainder

If Remainder = 0, Dataword can be accepted

It means No bit is corrupted

Some bits are corrupted, but the decoder failed to detect them

Otherwise Dataword is discarded because error found

one or more bits is corrupted

For sender(Checksum creation)

Break message into into ‘k’ number of blocks with ‘n’ bits in each block

Sum all the ‘k’ data blocks, add the carry to the sum if any

Apply 1’s complement to the sum (invert all bits)

You get the checksum

Therefore:

a.

P[1-bit error in 8-bit unit] = $C(8,1)(0.2)^1 (0.8)^7 = 0.34$

b.

P[3-bit error in 16-bit unit] = $C(16,3)(0.3)^3 (0.7)^13 = 0.34$

c.

P[10-bit error in 32-bit unit] = $C(8,1)(0.2)^1 (0.8)^7 = 0.34$

To do this type of questions:

List the recieved message

Locate the Parity bits, which is 2^n position

Find the "1"s position of recieved message

put all the position numbers of “1” into xor operation

If the result is 0000, it is correct. Otherwise error

Recieved message : 001101100100

Parity bits = 0000

Flow and Error Control - Concept Review

Review Questions

Describe the services provided by the data link layer.

Define frame and the reason for the need.

Compare and contrast flow control and error control.

Explain the reason for moving from the stop-and-wait ARQ protocol to Go-Back-N ARQ protocol.

Compare and contrast the Go-Back-N ARQ protocol with Selective-Repeat ARQ.

Define Piggybacking and its usefulness.

In the stop-and-wait protocol, assume that the sender has only one slot in which to keep the frame to send or the copy of the sent frame. What happens if the network layer delivers a packet to the data-link layer at this moment?

Is a negative acknowledgement (REJ) necessary in the stop-and-wait ARQ protocol?

Problems

Note:

ps: 10^-12 s

ns: 10^-9 s

$\mu$ s: 10^-6 s

ms: 10^-3 s

KB : 10^3 B

MB : 10^6 B

GB : 10^9 B

TB : 10^12 B

A five-bit sequence number can create sequence numbers from 0 to 31.

If the sequence number starts at 0, the sequence number in the Nth packet is (N-1 mod 32)

101th packet has the sequence number ((101-1) mod 32) = 4

We need to send 1000 frames.We ignore the overhead due to the header and trailer.

Data frame propagation time = $5000km / (2 \times 10^8 m/s) = 25ms$

Data frame transmission time = $1000 bits / 1 \times 10^6 = 1ms$

The time for one transmission cycle (1 frame) = $t_{frame} + 2t_{prop} = 51ms$

We are sending 1million bits: 1000000/1000 = 1000 frames

Total delay = $10000 \times 51ms = 51s$

We need to send 1000 frames.

1 Window has 7 frame

1000/7 = 142.8 = 143 Windows

Data frame propagation time = $5000km / (2 \times 10^8 m/s) = 25ms$

Data frame transmission time = $1000 bits / 1 \times 10^6 = 1ms$

The time for the first ack arrives = $t_{frame} + 2t_{prop} = 51ms$

The time for sending 1 window (7 frames) = $7 (t_{frame}) = 7ms$

So the utilization is not 1 and the server has to wait. In this case, each window transmission takes 51ms.

We ignore the overhead due to the header and trailer.

Time delay for one window = 51 ms

For the last windows, it will only send 6 frames and we need to wait for the acknowledgement of the last frame, so

Total delay = $142 \times 51 ms + 6 t_{frame} + 2t_{prop} = 7.298s$

We need to send 1000 frames.

1 Window has 4 frames

1000/4 = 250 Windows

Data frame propagation time = $5000km / (2 \times 10^8 m/s) = 25ms$

Data frame transmission time = $1000 bits / 1 \times 10^6 = 1ms$

The time for the first ack arrives = $t_{frame} + 2t_{prop} = 51ms$

The time for sending 1 window (7 frames) = $4 (t_{frame}) = 4ms$

So the utilization is not 1 and the server has to wait. In this case, each window transmission takes 51ms. We ignore the overhead due to the header and trailer.

Time delay for one window = 51 ms

For the last windows, we need to wait for the acknowledgement of the last frame, so

Total dela = $249 \times 51 + 4t_{frame} + 2t_{prop} = 12.753s$

Round Trip Time means the Time Travel to and from.

Round Trip Time = 2(Propagation Time)

$RTT = 2 \times (10,000 Km) / (2 \times 10^8) = 100ms$

Frame transmission time $t_{frame} = 100,000 bits / 100 Mbps = 1ms$

Too achieve 100% utilization, we have

Since $W\space t_{frame} > t_{frame} + 2t_{prop}$

$W \space t_{frame} = t_{frame}$

$(W-1) t_{frame} = RTT$

W - 1 = RTT

W - 1 = 100

Therefore W = 101

Hence, the send window size is 101 and the receive window size is 1.

$2^m > 101$

m = 7

The number of bits in the sequence number field (m) is 7 and the sequence number is from 0 to 127. The time out value should be greater than RTT to avoid early retransmission of the frame.

Keypoint : Last ACK is 0

HDLC - Concept Review

HDLC Frame Structure
Point-to-Point Protocol (PPP)

Review Questions

What are the configurations in HDLC?

What are the transfer modes in HDLC?

Why bit stuffing is required in HDLC?

What are the functions of N(S) and N® fields in HDLC frames?

What are the basic operations of HDLC?

Compare and contrast byte-oriented and bit-oriented protocols.

Define piggybacking and its benefit.

In PPP, we normally talk about user and system instead of sending and receiving nodes; explain the reason.

In the frame structure of PPP, explain why we need only one address field. Explain why the address is set to the predefined value of (11111111)?

Compare and contrast HDLC and PPP.

Problems

Note:

ps: 10^-12 s

ns: 10^-9 s

$\mu$ s: 10^-6 s

ms: 10^-3 s

KB : 10^3 B

MB : 10^6 B

GB : 10^9 B

TB : 10^12 B

Frame transmission time = 1024 / 1Mbps = 1.024ms

Propagation delay = 270ms (given)

The transmitting station can send 7 frames without an acknowledgment. From the beginning of the transmission of the first frame, the time to receive the acknowledgment of that frame is:

t = 1.024ms + 2(270ms) = 541.024ms

Within this time, 7 frames are sent.

Header = 48 bits (given)

Data per frame = 1024 - 48 = 976 bits

Throughput = 7(976 bits ) / 541.024ms = 12.6 kbps

a)

When a flag is used as both an ending and starting flag (that is, one 8-bit pattern serves to mark the end of one frame and the beginning of the next), then a single-bit error in that flag alters the bit pattern so that the receiver does not recognize the flag. Accordingly, the received assumes that this is a single frame.

b)

If a bit error somewhere in a frame between its two flags results in the pattern 01111110, then this octet is recognized as a flag that delimits the end of one frame and the start of the next frame.

Just add an “0” after every 5 "1"s.

01 are Start of the header

02 are Start of Text

03 are End of Text

So starting from 02 will be the data.

A1 A2 A3 A4 A5

05 04 03 02 01 (10 is escape character, discarded after destuffing)

03 10 03

10 10 03 01 02 A1

N® = 2 (010). This is the number of the next frame that the secondary station expects to receive.

a)

2 frames for link-layer establishment

2 frames for network connection

10 frames for data transfer

2 frames for termination

only 16 frames are exchanged:

b)

2 frames for link-layer establishment

2 frames for network connection

2 frames for PAP (request and ack)

10 frames for data transfer

2 frames for termination

18 frames are exchanged.

c)

2 frames for link-layer establishment

2 frames for network connection

3 frames for CHAP (challenge, response, and success)

10 frames for data transfer

2 frames for termination

19 frames are exchanged.

CHAP is a 3-way handshake.