Chap 2.
2 - Error-Checking Method
Reason error may occur when data is transmitted
- Interference
- Crosstalk
Explain how the data might have errors after transmission
- Data could be lost
- Data could be gained/added
- Data could be changed
- Bits could be reassembled in the wrong order
- Interference could occur
- Crosstalk could occur
- Data collisions could occur
- Data packets could time out/reach their hop count
Describe how an error can occur in the data during transmission [2]
It can suffer Interference/crosstalk.
• … that could have caused data loss/gained/chang
1. Parity Check
Definition:
- A parity bit is transmitted with each byte of data.
- Odd or even parity can be used.
- Count number of 1’s.
- If parity is incorrect, error is detected
Explain how the odd parity check detects errors.
- The number of 1 s/0 s are counted
- A parity bit is added to each byte before transmission to make the sum of the bits in each byte odd
- After transmission, if the number is odd no error is detected
- After transmission, if the number is even an error is detected
Describe how an even parity check detects an error.
- A parity bit is added to each byte to make the number of 1s/0s even
- The number of 1s/0s in each byte is counted after transmission.
- If any bytes have an odd number of 1s/0s an error is detected
Describe how the parity bits are used to detect errors
- Parity can be set to odd or even
- Sender and receiver agree on parity to use
- Data is split into bytes
- Sender counts the number of 1s or 0s byte
- Each byte is assigned a parity bit to match the parity
- Receiving device recounts the number of 1s byte and compares to parity used
- if it does not match the parity, an error is reported
Example:
The system uses even parity and column 1 is the parity bit. The eight bytes of data are sent together with a
ninth parity byte:
Parity Column Column Column Column Column Column Column
Bit 2 3 4 5 6 7 8
Byte 1 1 0 0 0 0 1 0 0
Byte 2 1 1 1 1 0 0 1 1
Byte 3 0 1 0 0 1 0 0 0
Byte 4 0 1 1 1 0 0 0 1
Byte 5 1 0 0 0 1 1 1 1
Byte 6 0 0 0 0 0 0 0 0
Byte 7 1 1 1 0 1 0 0 0
Byte 8 1 0 0 0 1 1 1 0
Parity
1 0 1 1 0 1 1 1
byte
(i) One of the bits has been transmitted incorrectly. (2)
Byte: 5 Column: 4
(ii) Explain how the corrupted bit was found. (2)
- Column 4 has an odd number of 1s
- Byte 5 has an odd number of 1s
- Intersection of column 4 and byte 5 indicate the incorrect bit
Q: A parity check may not identify that a bit has been transmitted incorrectly. Describe one situation in
which this could occur. (1)
- bits are interchanged (e.g. 1 → 0 and 0 → 1) that won’t change parity value
- Bits still add up to even number
- There is a transposition of bits
- it does not check the order of the bits (just the sum of 1s/0s)
- even number of bits change
- incorrect bits still add up to correct parity
Parity Block
Q: A parity block check can be used instead of a parity byte check. Explain how a parity block check might
detect an error in transmission that would not be detected by a parity byte check.
- In parity check, interchange of bits will not be detected
- In parity block the position of all changes will be highlighted
2. Automatic Repeat Request (ARQ)
- Uses acknowledgement and timeout
- Sender starts a timer when data is transmitted
- Receiver uses an error checking method to check whether the data has been received accurately
- If no error detected a positive acknowledgement is returned to sender
- If error detected negative acknowledgement is returned to sender
- If sender gets no acknowledgement within the set time it resends the data
OR
- Timer is started when sending device transmits a data packet to receiver
- Receiving device checks the data packet for errors
- Once the receiving device knows the packet is error free it sends an acknowledgement back to the sending
device and the next packet is sent
- If the sending device does not receive an acknowledgement before the timer ends a timeout occurs
- the data packet is resent until acknowledgement received
Q: The error detection system uses an odd parity check and a positive automatic repeat query (ARQ).
Describe how the error detection system operates to check for errors.
Parity Check
- The 1s are counted in each byte
- Each byte has a parity bit
- If the number of 1s are odd the parity bit is 0
Positive ARQ
- Data is sent and a timer is started
- The receiving device counts the number of 1s (in each byte)
- If the number of 1s are odd an acknowledgement is sent to say the data is error free
- The sender then sends the next packet of data and the timer is restarted
- If the number of 1s is even an acknowledgement is not sent
- If no acknowledgement is received before timeout, the data packet is resent
3. Echo check
- A copy of the data is sent back to the sender
- The sender compares the data sent to the data received back
- If the original and the copy do not match, an error has occurred
4. Checksum
Describe how a checksum can be used to check that the data has been transmitted correctly
- A value is calculated from the data
- The value is calculated using an algorithm
- The value is transmitted with the data
- The value is recalculated after transmission
- If the checksum values do not match, an error is detected
- A request for data to be resent if there is an error.
Q: In the checksum error detection method, two values are compared after transmission. If the values do not
match, an error is detected. Explain why the values not matching would show an error has occurred.
- The checksum is calculated from the data using the same algorithm
- So, if the values are different the data must be different
5. Check Digit
- Validation method
- Used to check data entry
- Digit is calculated from data
- Digit is added to data
- Digit is recalculated when data has been input
- Digits are compared
- If digits are different, error is detected // If digits match, no error is detected
Q: Explain how the barcode scanning system operates to check for errors.
- A check digit is calculated using the barcode data using an algorithm and added to the barcode
- When the barcode is scanned the check digit is recalculated using the same algorithm
- If the check digits match no error has occurred when scanning the barcode
Similarities between the check digit and checksum methods
- They both calculate a value from the data
- They both append the calculated value to the data
- They both recalculate the value
- They both report an error if they don’t match