Error detection and correction Flashcards
How do errors occur?
Errors will occur on links when a bit flips
What is the trade off with regards to error control?
There is a trade off between error control and link utilisation when there is limited link capacity.
What is the issue when there is no error control and an error occurs?
Every string of bits is an allowed message so the receiver doesn’t know there is an error and accepts any data.
What are some methods of error control?
Reduce the set of allowed messages
What is the benefit of reducing the number of allowed messages?
If a disallowed string is received then it will be discarded. This means that that not every string of bits is allowed.
What are allowed messages called?
Codewords
What are disallowed messages called?
Space
What is the problem with reducing the number of allowed messages?
It reduces the messages we can send and we want to send any message
What is two-repetition code?
> 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]
What is hamming distance?
This is a measure of the minimum number of bit flips to change one codeword into another.
What is the hamming distance for two-repetition code?
2
00⇒01 or 10⇒11
What is the symbol for minimum hamming distance?
dmin
How many errors can we detect?
Errors = dmin - 1
How does a receiver decode error correcting codes?
- Match the received bits to code words
2. Map codeword to source bits
How can a receiver correct errors in error correcting codes?
A receiver choses the closest codeword to the received bits.
Explain how a receiver decides how to correct a three-repetition code
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]
How many bit flips can be corrected with three-repetition code?
1 bit flip
What is the issue with repetition code bit flip correction?
We cannot correct across a decision boundary
What is code rate?What is the equation?
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
What is the trade off with regards to code rate?
High-rate codes (R ⇒ 1) correct fewer errors but add less overhead
Lower-rate codes (R ⇒ 0) correct more errors bit add more overhead
What is a parity bit?
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…
What is even parity?
The parity bit is picked so that the total number of 1s in the code word (including the parity bit) is even.
What is odd parity?
The parity bit is picked so that the total number of 1s in the code word (including the parity bit) is odd
How does a receiver decide if there is an error when parity is used?
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.
What is the minimum hamming distance for parity? what does this mean about the number of bit errors and correcting errors
dmin = 2
Detects 1 bit error, Corrects 0
What is two dimensional parity?
> 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]
What is the minimum hamming distance for 2D parity? How many errors can it detect?
dmin = 4
Detects ≤ 3 bit errors
What happens in 2D parity when:
a. 1 bit flips
b. 2 bits flip
c. 3 bits flip
d. 4 bits flip
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.
What is (n,k) block code?
This is when there are k data bits followed by n-k parity bits where the whole codeword is n bits
What does UDP use to validate if a message has erros?
Uses checksum
What happens if UDP detects an error?
It discards the transmitted message. It does not ask for it to be resent
How is the UDP checksum calculated?
Split the message into bit-words (often 16 bits) and sum them.
Invert the total and this is the checksum
How does the receiver calculate if the message has error when checksum is used.
Sum all of the bitwords including the checksum and the total should be all 1s
