Error Detection Methods (CIE IGCSE Computer Science)

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

• 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

• 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 #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 #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)

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

• 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 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
• When a block of data is to be transmitted, the checksum is first calculated and then transmitted with the rest of the data
• When the data is received the checksum value is calculated based on the received data and compared to the checksum value received. If they are the same then the data does not contain any errors
• If an error does occur then a resend request is sent and the data is retransmitted

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