4.5.5.3 Error checking and correction Flashcards
How does the even parity system work?
The total is calculated before transmission ;
0 or 1 bit is added (to the 7-bit code) ;
So that, the total number of 1 bits must compute to an even number ;
The number of one bits is re-calculated after received ;
An odd number of 1 bits indicates an error
What is a check digit?
A digit at the end of the code is used to check the code is valid. It is calculated from performing an operation with the other digits.
How does majority voting work?
Each bit is transmitted three times, if the bit is not the same then majority vote will decide what value it should be.
Describe how the receiver can detect and correct a single-bit error using Hamming code.
Recalculate the values for the parity bits using the data bits received (and compare these values with the parity bits received);
Add up the bit positions of the calculated parity bits that are different to those received;
The bit position of where the error has occurred is indicated;
What are the disadvantages of parity bits?
Can’t detect all errors, only when an odd / even number of errors have occurred
the parity bit could be changed during transmission
doesn’t show where the error occurred
Hamming code uses multiple parity bits - this allows it to correct some errors that can occur during transmission.
What are the disadvantages of majority voting?
If the bit is transmitted incorrectly twice, the computer will read it as the wrong value.
Significantly increases length of transmission, increasing processing time
How does hamming code check for errors?
Checking for errors:
Number the column headings
Highlight the column headings that are powers of 2 (1,2,4,8, etc.), these are the parity bits
Insert your data and highlight the parity bits
Starting from the right, check 1 bit, ignore the next bit, and so on, then count the number of 1s for odd or even parity
Do the same for 2^1, 2^2, 2^3.. (the column headings)
(see wikibooks)
How does hamming code detect / correct errors?
Do the normal process, and highlight all the error data
Add the column numbers for when the error occurs
e.g if on check 4 skip 4 there is the wrong parity - column number = 4 therefore swap the fourth bit from the right
(see wikibooks)
What is a checksum?
The outcome of running an algorithm, called a hash function, on a piece of data. Comparing the checksum that you generate from your version of the data, with the one provided by the data, helps ensure that your copy is genuine and error free.
