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.
