2.2 Methods of error detection

### 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
- Network could be infected with malware
### **Parity Checks**
- It uses the number of 1-bits in a byte
- Type Types -
  - Even - Even number of 1-bits
  - Odd - Odd numbers of 1-bits
- Example (Even Parity) -

| 0    | **1** | **0** | **1** | **1** | **0** |
| ---- | ----- | ----- | ----- | ----- | ----- |

- The LSB (Left-Most Bit) is the parity bit. As the number of 1s is even, the parity bit would be set to even.

#### 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 // blocks of 7 bytes
- Sender counts the number of 1s/0s in each group/byte
- Each group/byte is assigned a parity bit to match the parity
- Receiving device recounts the number of 1s/0s in each group/byte
- ...and compares to parity used/odd/even and if it does not match the parity, an error is reported/identified (in block check) the location of the error(s) can be identified/estimated at the intersection
#### Explain how the odd parity check detects errors
- The number of 1 s are counted
- A parity bit is added to each 7 bits before transmission
- … to make the **sum** of the 1s 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
#### Explain how the even parity check detects errors
- The number of 1 s are counted
- A parity bit is added to each 7 bits before transmission
- … to make the **sum** of the 1s in each byte **even**
- After transmission, if the number is **odd** an error is detected
- After transmission, if the number is **even** no error is detected
#### Limitations with Parity Checks
- Two bits may change during transmission; therefore error is not found
- Even though the parity checks would reveal the errors, the bit(s) changed wouldn’t be identified
#### Why a parity check may not detect transmission errors
- Transposition error // bits are interchanged
- Even number of errors has occurred
- 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

• The system could use odd or even parity
• A parity bit is added
• The data is checked to see if it has incorrect/correct parity
### **Parity Blocks**
- To overcome the limitations of parity bits, Parity blocks would be used.
- Any changes in bits would be identified through the rows and columns

Each row and column where the parity has changed from even to odd should be flagged:
![image.png](https://doc.tiegg.com/media/202512/ae1dea040bfe476aa4c981c4e9e50eac3375.png)

byte 4 (row 4) now has incorrect parity (there are five 1-bits)
bit 5 (column 5) also now has incorrect parity (there are five 1-bits).
**Explanation**
- Counted all the 1s
- An even parity has been used
- Odd number of ones in that row (byte 4) **and** column (bit 5)
### **Echo Check**

- Once the data has been sent, The receiver will send the data back to the sender for verification.
- The sender would compare the received and original data for errors.
- If the two copies do not match, an error has occurred

The only downside is that we wouldn’t know if the error occurred when sending the data or sending the data back for verification.

![image.png](https://doc.tiegg.com/media/202605/1efe535545fb47b68922efa86232ecfa8515.png)
### **Checksum**
- Sender calculates a value from the data using an agreed algorithm
- Value is appended to the data
* Value is transferred with the data
* Receiver performs same calculation to recalculate the checksum
* Values are compared after transmission, 
* If the **checksum** **values** do not match, an error is detected, request for data to be resent 
- If the **checksum** **values** match, no error is detected …

### **Check Digits**
- Digit is calculated from data
- Digit is appended / 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

- Check digits are calculated from all the other digits in the data (ex-codes). The check digit would be the last digit of the code.
- These are used to identify mistyping errors such as -
  - 6372 typed as 6379
  - 8432 typed as 842

- Data is input with check digit
- The calculated digit is compared to a stored value
- If it matches, the data entered is correct
- If it does not match, the data entered is incorrect
#### 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

Two common methods will be considered here:
_»_ ISBN 13
_»_ Modulo-11
##### Example 1: ISBN 13
The check digit in ISBN 13 is the thirteenth digit in the number. We will now consider two different calculations. The first calculation is the generation of the check digit.
The second calculation is a verification of the check digit (that is, a recalculation).

Calculation 1 – Generation of the check digit from the other 12 digits in a number
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
![ISBN (no check digit)](https://doc.tiegg.com/media/202605/7c780c10bce6406f9d08a4bd14177ab97275.png)9 + 8 + 3 + 0 + 8 + 8 = 36
3 × (7 + 0 + 4 + 9 + 3 + 2) = 75
(36 + 75)/10 = 111/10 = 11 remainder 1
10 – 1 = 9 the check digit

So we end up with the following thirteen-digit number
![image.png](https://doc.tiegg.com/media/202605/9c38079ebabd48d69ad1951451d2358a6653.png)
Calculation 2 – Re-calculation of the check digit from the thirteen-digit number (which now includes the check digit)
To check that an ISBN 13-digit code is correct, including its check digit, a similar process is followed:
1. add all the odd numbered digits together, including the check digit
2. add all the even number of digits together and multiply the result by 3
3. add the results from 1 and 2 together and divide by 10
4. the number is correct if the remainder is zero.
Using the ISBN 9 7 8 0 3 4 0 9 8 3 8 2 9 (including its check digit) :
9 + 8 + 3 + 0 + 8 + 8 + 9 = 45
3 × (7 + 0 + 4 + 9 + 3 + 2) = 75
(45 + 75)/10 = 120/10 = 12 remainder 0
remainder is 0, therefore number is correct.
##### Example 2: Modulo-11
The modulo-11 method can have varying lengths of number which makes it suitable
for many applications, such as product codes or VINs. The first calculation is the
generation of the check digit. The second calculation is a verification of the check digit
(that is, a recalculation).

Calculation 1 – Generation of the check digit from the other digits in a number
(In this example, we will assume the original number contained only 7 digits.)
The following algorithm generates the check digit from the other 7 digits:
1. each digit in the number is given a weighting of 8, 7, 6, 5, 4, 3 or 2 starting from the
left (weightings start from 8 since the number will become eight-digit when the check digit is added)
2. the digit is multiplied by its weighting and then each value is added to make a total
3. the total is divided by 11
4. the remainder is then subtracted from 11 to find the check digit (note if the remainder is 10 then the check digit ‘X’ is used).
The example to be used has the following seven-digit number:
5.

| 7-digit number:   | 4   | 1   | 5   | 6   | 7   | 1   | 0   |
| ----------------- | --- | --- | --- | --- | --- | --- | --- |
| weighting values: | 8   | 7   | 6   | 5   | 4   | 3   | 2   |

6. sum: (8 × 4) + (7 × 1) + (6 × 5) + (5 × 6) + (4 × 7) + (3 × 1) + (2 × 0)
= 32 + 7 + 30 + 30 + 28 + 3 + 0
total = 130
7. divide total by 11: 130/11 = 11 remainder 9
8. subtract remainder from 11: 11 – 9 = 2 (check digit)
So we end up with the following eight-digit: 4 1 5 6 7 1 0 2

Calculation 2 – Re-calculation of the check digit from the eight-digit number (which
now includes the check digit)
To check that the eight-digit number is correct, including its check digit, a similar
process is followed:
1. each digit in the number is given a weighting of 8, 7, 6, 5, 4, 3, 2 or 1 starting from
the left
2. the digit is multiplied by its weighting and then each value is added to make a total
3. the total is divided by 11
4. the number is correct if the remainder is zero
5.

| Using the 8-digit number: | 4   | 1   | 5   | 6   | 7   | 1   | 0   | 2   |
| ------------------------- | --- | --- | --- | --- | --- | --- | --- | --- |
| weighting values:         | 8   | 7   | 6   | 5   | 4   | 3   | 2   | 1   |

6. sum: (8 × 4) + (7 × 1) + (6 × 5) + (5 × 6) + (4 × 7) + (3 × 1) + (2 × 0) + (1 × 2) = 32 + 7 + 30 + 30 + 28 + 3 + 0 + 2
	total = 132
7. divide total by 11: 132/11 = 12 remainder 0
8. remainder is 0, therefore number is correct
### **Automatic Repeat Requests (ARQs)**

- Uses acknowledgements and timeouts to make sure the user received the data
- Check performed on received data // error is detected by e.g. parity check, check sum
- If error detected, request is sent to resend data // negative acknowledgement is used
- Resend request is repeated till data is sent correctly / requests timeout / limit is reached
- Send acknowledgement that data is received // positive acknowledgement is used
- If acknowledgement not received in set time data is resent
#### Explain how an ARQ operates using a positive acknowledgement method.
- 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 // until max number of attempts reached
#### How parity checks and ARQ operate together to detect and correct errors
- Odd or even parity is **set/agreed** for the data
- A parity bit is added to each byte of data
- … to make the number of 1s match parity
- (The first packet of) data is sent and a timer is started
- The receiving device counts the number of 1s (in each byte)
- If the number of 1s meets parity 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 does not meet parity, a negative acknowledgement is sent to the sender  that triggers the data to be resent
- When the data is sent, a timer is started
- If an acknowledgement is not received within the time set, the data is resent ...
- … until an acknowledgement is received / resend limit is reached
#### Explain why checksum and ARQ are both used.
- Checksum used to detect errors (during transmission)
- … using a calculated value
- ARQ checks if data is received
- … uses acknowledgement and timeout
- … requests data be sent again if (checksum) detects error / not received