Error Detection and correction
• Errors can occur during data transmission due to :
Interference : all types of cable can suffer from electrical
interference, which can cause data to be corrupted or even lost
Problems during packet switching : this can lead to data loss –
or it is even possible to gain data!
Skewing of data : this occurs during parallel data transmission
and can cause data corruption if the bits arrive out of
synchronisation
Error detection in data transmission
• There are several error detection methods that can be
used, these include:
1. Check sum
2. Parity check
3. Check digit
4. Echo check
Parity check
• A Parity check can use an odd or even method
• Each byte of data has 7 bits and 1 extra bit that is called parity bit.
• The parity bit is normally the first or last bit of data.
1 0 0 1 0 0 0 1
Parity bit 7 bits of data
The parity can be either called
EVEN (that is, an even number of 1-bits in the byte) or
ODD (that is, an odd number of 1-bits in the byte).
One of the bits in the byte (usually the most significant bit or left-most bit) is
reserved for a parity bit.
The parity bit is set according to whether the parity being used is even or odd.
Parity check
• In this example, if the byte is using even parity, then the parity bit
needs to be set to 0, since there is already an even number of 1-bits
in the byte (four 1-bits). We thus get:
In this example, if the byte is using odd parity, then the parity bit needs to
be
set to 1, since we need to have an odd number of 1-bits in the byte. We
thus get:
Parity check
Check sum
• A checksum uses a calculated value to check for errors.
• The number of bits being transmitted is counted up and this
numeric count is transmitted with the data.
• The receiver can then see if the same number of bits has arrived.
• lf the counts match then the receiver knows a full
transmission of the data has been received.
Echo check
• In this type of error detection method a copy of
transmitted data sends back to the sender to be
compared with the original data sent.
Automatic repeat request (ARQ)
An Automatic Repeat Request (ARQ) used to
check data following data transmission.
» ARQ uses
1. positive and negative acknowledgements :
messages sent to the receiver indicating that data
has/has not been received correctly.
2. timeout : this is the time interval allowed to
elapse before an acknowledgement is received)
positive and negative
acknowledgements
• the receiving device receives an error detection code as part of
the data transmission (this is typically a Cyclic Redundancy
Check)
• this is used to detect whether the received data contains any
transmission errors
• if no error is detected, a positive acknowledgement is sent back
to the
sending device
• however, if an error is detected, the receiving device now sends a
negative acknowledgement to the sending device and requests
re-transmission of the data
time-out
• a time-out is used by the sending device by waiting a pre-
determined amount of time ….
• ... and if no acknowledgement of any type has been received by
the sending device within this time limit, it automatically re-sends
the data until a positive acknowledgement is received ….
• ... or until a pre-determined number of re-transmissions has taken
place
ARQ is often used by mobile phone networks to guarantee data
integrity.
Check digit
• A method is necessary to check for errors with data entry and this method
is called check digit. This is how a check digit operates:
• A check digit value is previously calculated from the data that will be
entered at some point, for example, a barcode number or an ISBN number.
This number is stored with the data.
• When the data is entered, for example, the barcode is scanned, the check
digit is recalculated from the data entered.
• If the previously calculated check digit and the stored check digit match.
the data entered is correct.
• If the previously calculated check digit and the stored check digit do not
match, the data entered is incorrect.
• Although the process is similar, you should not confuse the operation of a
check digit and a checksum.
Check digit
• Calculation – Generation of the check digit from the other 12 digits
in a ISBN
The following algorithm generates the check digit from the 12 other digits:
1 add all the odd numbered digits together
2 add all the even numbered digits together and multiply the result by 3
3 add the results from 1 and 2 together and divide by 10
4 take the remainder, if it is zero then use this value, otherwise subtract the
remainder from 10 to find the check digit.
Using the ISBN 9 7 8 0 3 4 0 9 8 3 8 2
1. 9 + 8 + 3 + 0 + 8 + 8 = 36
2. 3 × (7 + 0 + 4 + 9 + 3 + 2) = 75
3. (36 + 75)/10 = 111/10 = 11 remainder 1
4. 10 – 1 = 9 the check digit
