Error detection and correction

Question 1

How do errors occur?

Answer 1

Errors will occur on links when a bit flips

Question 2

What is the trade off with regards to error control?

Answer 2

There is a trade off between error control and link utilisation when there is limited link capacity.

Question 3

What is the issue when there is no error control and an error occurs?

Answer 3

Every string of bits is an allowed message so the receiver doesn’t know there is an error and accepts any data.

Question 4

What are some methods of error control?

Answer 4

Reduce the set of allowed messages

Question 5

What is the benefit of reducing the number of allowed messages?

Answer 5

If a disallowed string is received then it will be discarded. This means that that not every string of bits is allowed.

Question 6

What are allowed messages called?

Answer 6

Codewords

Question 7

What are disallowed messages called?

Answer 7

Space

Question 8

What is the problem with reducing the number of allowed messages?

Answer 8

It reduces the messages we can send and we want to send any message

Question 9

What is two-repetition code?

Answer 9

> The transmitter repeats every bit once after each bit (e.g. 0011001111)
The receiver decodes the message (e.g. 01011)
If there is a single bit error then it can be detected and the message can be resent.
If there is a two bit error then we cannot detect it as the error has jumped over the space between code words.
[IMAGE]

Question 10

What is hamming distance?

Answer 10

This is a measure of the minimum number of bit flips to change one codeword into another.

Question 11

What is the hamming distance for two-repetition code?

Answer 11

2

00⇒01 or 10⇒11

Question 12

What is the symbol for minimum hamming distance?

Answer 12

dmin

Question 13

How many errors can we detect?

Answer 13

Errors = dmin - 1

Question 14

How does a receiver decode error correcting codes?

Answer 14

1. Match the received bits to code words

2. Map codeword to source bits

Question 15

How can a receiver correct errors in error correcting codes?

Answer 15

A receiver choses the closest codeword to the received bits.

Question 16

Explain how a receiver decides how to correct a three-repetition code

Answer 16

If there is an error detected. The receiver will correct the identified error with the codeword that shares the most bits as the error.
e.g. 001 ⇒ 000
e.g. 101 ⇒ 111
[IMAGE]

Question 17

How many bit flips can be corrected with three-repetition code?

Answer 17

1 bit flip

Question 18

What is the issue with repetition code bit flip correction?

Answer 18

We cannot correct across a decision boundary

Question 19

What is code rate?What is the equation?

Answer 19

It is a fraction between 0 and 1 and defines how much excess data an error detecting code produces.
R = k/n
R = Rate
k = Message length (k < n)
n = Codeword length

Question 20

What is the trade off with regards to code rate?

Answer 20

High-rate codes (R ⇒ 1) correct fewer errors but add less overhead
Lower-rate codes (R ⇒ 0) correct more errors bit add more overhead

Question 21

What is a parity bit?

Answer 21

This is an additional bit added to the end of a message that is equal to the XOR of the data bits:
P = D1⊕D2⊕D3⊕D4…

Question 22

What is even parity?

Answer 22

The parity bit is picked so that the total number of 1s in the code word (including the parity bit) is even.

Question 23

What is odd parity?

Answer 23

The parity bit is picked so that the total number of 1s in the code word (including the parity bit) is odd

Question 24

How does a receiver decide if there is an error when parity is used?

Answer 24

For even parity:
It counts the number of 1s received and if there is an odd number than an error is detected.
For odd parity:
It counts the number of 1s received and if there is an even number than an error is detected.

Question 25

What is the minimum hamming distance for parity? what does this mean about the number of bit errors and correcting errors

Answer 25

dmin = 2

Detects 1 bit error, Corrects 0

Question 26

What is two dimensional parity?

Answer 26

> Break the data into multiple rows
Add a parity bit to each row at the end.
Add a parity bit to each column
Add a parity bit for the row parity bits and add this to the end of the bottom row parities.
[IMAGE]

Question 27

What is the minimum hamming distance for 2D parity? How many errors can it detect?

Answer 27

dmin = 4

Detects ≤ 3 bit errors

Question 28

What happens in 2D parity when:

a. 1 bit flips
b. 2 bits flip
c. 3 bits flip
d. 4 bits flip

Answer 28

a. 1 bit flip = 3 parity bits flip
b. 2 bits flip = ≥2 parity bits flip
c. 3 bits flip = ≥ 3 parity bits flip
d. 4 bits flip = This can often be detected but it is not guaranteed.

Question 29

What is (n,k) block code?

Answer 29

This is when there are k data bits followed by n-k parity bits where the whole codeword is n bits

Question 30

What does UDP use to validate if a message has erros?

Answer 30

Uses checksum

Question 31

What happens if UDP detects an error?

Answer 31

It discards the transmitted message. It does not ask for it to be resent

Question 32

How is the UDP checksum calculated?

Answer 32

Split the message into bit-words (often 16 bits) and sum them.
Invert the total and this is the checksum

Question 33

How does the receiver calculate if the message has error when checksum is used.

Answer 33

Sum all of the bitwords including the checksum and the total should be all 1s