Parity check
- The parity checking protocol determines whether bits in a transmission have been corrupted
- Every byte transmitted has one of its bits allocated as a parity bit
- The sender and receiver must agree before transmission whether they are using odd or even parity
- If odd parity is used then there must be an odd number of 1’s in the byte, including the parity bit
- If even parity is used then there must be an even number of 1’s in the byte, including the parity bit
- The value of the parity bit is determined by counting the number of 1’s in the byte, including the parity bit
- If the number of 1’s does not match the agreed parity then an error has occurred
- Parity checks only check that an error has occurred, they do not reveal where the error(s) occurred
Even parity
- Below is an arbitrary binary string
| EVEN Parity bit | Byte | ||||||
| 0 | 1 | 0 | 1 | 1 | 0 | 1 | 0 |
- If an even parity bit is used then all bits in the byte, including the parity bit, must add up to an even number
- There are four 1’s in the byte. This means the parity bit must be 0 otherwise the whole byte, including the parity bit, would add up to five which is an odd number
Odd parity
- Below is an arbitrary binary string
| ODD Parity bit | Byte | ||||||
| 1 | 1 | 0 | 1 | 1 | 0 | 1 | 0 |
- If an odd parity bit is used then all bits in the byte, including the parity bit, must add up to an odd number
- There are four 1’s in the byte. This means the parity bit must be a 1 otherwise the whole byte, including the parity bit, would add up to four which is an even number
- The table below shows a number of examples of the agreed parity between a sender and receiver and the parity bit used for each byte
| Example # | Agreed parity | Parity bit | Main bit string | Total number of 1’s | ||||||
| #1 | ODD | 0 | 1 | 1 | 0 | 1 | 0 | 1 | 1 | 5 |
| #2 | EVEN | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 2 |
| #3 | EVEN | 1 | 0 | 1 | 0 | 1 | 1 | 1 | 1 | 6 |
| #4 | ODD | 1 | 0 | 1 | 1 | 1 | 0 | 0 | 1 | 5 |
| #5 | ODD | 1 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 5 |
| #6 | EVEN | 0 | 1 | 0 | 0 | 1 | 1 | 1 | 0 | 4 |
- Example #1: The agreed parity is odd. All of the 1’s in the main bit string are added (5). As this number is odd already the parity bit is set to 0 so the whole byte stays odd
- Example #2: The agreed parity is even. All of the 1’s in the main bit string are added (1). As this number is odd the parity bit is set to 1 to make the total number of 1’s even (2)
- Example #6: The agreed parity is even. All of the 1’s in the main bit string are added (4). As this number is even already the parity bit is set to 0 so the whole byte stays even
How do errors occur?
- When using parity bits, an error occurs when the number of total bits does not match the agreed parity
- Bits can be flipped or changed due to interference on a wire or wirelessly due to weather or other signals
| Example # | Agreed parity | Parity bit | Main bit string | Total number of 1’s | Error | ||||||
| #1 | ODD | 1 | 1 | 1 | 0 | 1 | 0 | 1 | 1 | 6 | Error |
| #2 | EVEN | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 2 | No error |
| #3 | EVEN | 1 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 7 | Error |
| #4 | ODD | 1 | 0 | 1 | 1 | 1 | 0 | 0 | 1 | 5 | No error |
| #5 | ODD | 1 | 1 | 0 | 1 | 0 | 1 | 1 | 1 | 6 | Error |
| #6 | EVEN | 0 | 1 | 0 | 0 | 0 | 1 | 1 | 0 | 3 | Error |
- Example #1: The agreed parity is odd but the total number of 1’s is even (6). An error has occurred somewhere
- Example #2: The agreed parity is even and the total number of 1’s is even (2). No error has occurred here
- Example #3: The agreed parity is even but the total number of 1’s is odd (7). An error has occurred somewhere
- Parity checks are quick and easy to implement but fail to detect bit swaps that cause the parity to remain the same
- Below is an arbitrary binary string. The agreed parity is odd and the total number of 1’s is five (odd)
| Agreed parity | Parity bit | Total number of 1’s | Error | |||||||
| ODD | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 1 | 5 | No error |
| Agreed parity | Parity bit | Total number of 1’s | Error | |||||||
| ODD | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 3 | No error |
Parity bytes and parity blocks
- Parity checks do not pinpoint errors in data, only that an error has occurred
- Parity blocks and parity bytes can be used to check an error has occurred and where the error is located
- A parity block consists of a block of data with the number of 1’s totalled horizontally and vertically
- A parity byte is also sent with the data which contains the parity bits from the vertical parity calculation
- Below is a parity block with a parity byte at the bottom and a parity bit column in the second column
| ODD | Parity bit | Bit 2 | Bit 3 | Bit 4 | Bit 5 | Bit 6 | Bit 7 | Bit 8 |
| Byte 1 | 0 | 1 | 1 | 0 | 1 | 0 | 1 | 1 |
| Byte 2 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 |
| Byte 3 | 1 | 0 | 1 | 0 | 1 | 1 | 1 | 1 |
| Byte 4 | 1 | 0 | 1 | 1 | 1 | 0 | 0 | 1 |
| Byte 5 | 1 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
| Byte 6 | 1 | 1 | 0 | 0 | 1 | 1 | 1 | 0 |
| Byte 7 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 0 |
| Byte 8 | 0 | 1 | 0 | 1 | 1 | 0 | 0 | 0 |
| Parity byte | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
- The above table uses odd parity
- Each byte row calculates the horizontal parity as a parity bit as normal
- Each bit column calculates the vertical parity for each row. This is the parity byte. It is calculated before transmission and sent with the parity block
- Each parity bit tracks if a flip error occurred in a byte while the parity byte calculates if an error occurred in a bit column
- By cross referencing both horizontal and vertical parity values the error can be pinpointed
- In the above example the byte 3 / bit 5 cell is the error and should be a 0 instead
- The error could be fixed automatically or a retransmission request could be sent to the sender
Checksums
- Checksums determine if data has been corrupted but do not reveal where
- Data is sent in blocks and an additional checksum value is added at the end of the block
- Checksums are custom user-created algorithms that perform mathematical calculations on data
- An example of a custom checksum algorithm in computer science is:
- A checksum byte is defined as a value between 1 and 255 which is stored in 8 bits. 8 bits are collectively known as a byte
- If the sum of all of the bytes of a transmitted block of data is <= 255 then the checksum value is the sum of all of the bytes
- If the sum of all of the bytes is > 255 then the checksum is calculated with an algorithm:
- X = sum of all of the bytes
- Y = X / 256
- Round down Y to nearest whole number
- Z = Y * 256
- Checksum = X – Z
Custom Checksum Walkthrough
- If X = 1496
- Y = 1496 / 256 = 5.84
- Rounded down Y = 5
- Z = 5 * 256 = 1280
- Checksum = 1496 – 1280 = 216
- The checksum value in this example would be 216
Echo check
- Echo checks involve transmitting the received data back to the sender. The sender then checks the data to see if any errors occurred during transmission
- This method isn’t reliable as an error could have occurred when the sender transmits the data or when the receiver transmits the data. Neither will know when the error occurred.
- If an error does occur the sender will retransmit the data
Check Digits
- Check Digits to determine if data has been corrupted but do not reveal where
- Data is sent in blocks and an additional check digit value is added at the end of the block
- Check Digits are custom user-created algorithms that perform mathematical calculations on data
- An example of a check digit is the ISBN value on books:
- Each book has a unique ISBN number that identifies the book
- A standard ISBN number may be ten digits, for example, 965-448-765-9
- The check digit value is the final digit (9 in this example). This number is chosen specifically so that when the algorithm is completed the result is a whole number (an integer) with no remainder parts
- A check digit algorithm is performed on the ISBN number. If the result is a whole number then the ISBN is valid
ISBN Check Digit Walkthrough
-
- To calculate an ISBN check digit the following algorithm is performed on 965-448-765-9:
- Multiply each ISBN digit by 1 to 10 and add them all up:
- 9×1 + 6×2 + 5×3 + 4×4 + 4×5 + 8×6 + 7×7 + 6×8 + 5×9 + 9×10 = 352
- Take the total number and divide it by 11: 352/11 = 32. 32 is a whole number with no remainder so the ISBN is valid
- Multiply each ISBN digit by 1 to 10 and add them all up:
- To calculate an ISBN check digit the following algorithm is performed on 965-448-765-9:
- Another example of a check digit is barcodes on purchasable items:
- Barcodes consist of black and white lines which can be scanned using barcode scanners. Barcode scanners shine a laser on the black and white lines which reflect light into the scanner. The scanner reads the distance between these lines as numbers and can identify the item
- Barcodes also use a set of digits to uniquely identify each item. The number of digits varies from code to code. An example would be 9780201379624
- The final digit on a barcode is usually the check digit. Like an ISBN this can be used to validate and authenticate an item
Barcode Check Digit Walkthrough
- To calculate a barcode check digit we can perform the following example algorithm on 9780201379624 (the final digit is the check digit):
- Multiply each digit by 1 or 3, alternating between these two values and add them all up
- 9×1 + 7×3 + 8×1 + 0x3 + 2×1 + 0x3 + 1×1 + 3×3 + 7×1 + 9×3 + 6×1 + 2×3 = 96
- The check digit (the final digit) should be the difference between the sum and the closest multiple of 10 that is larger or equal to the sum
- 96 rounded to the nearest 10 = 100
- 100-96 = 4
- The check digit is therefore 4 which matches our original barcode number
- Multiply each digit by 1 or 3, alternating between these two values and add them all up
Custom Check Digit Walkthrough
- If X = 1496
- Y = 1496 / 256 = 5.84
- Rounded down Y = 5
- Z = 5 * 256 = 1280
- Check digit = 1496 – 1280 = 216
- The check digit value in this example would be 216
