Error Detection Methods (Cambridge (CIE) O Level Computer Science)

Parity Check

What is a parity check?

• A parity check 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

• Parity checks are quick and easy to implement but fail to detect bit swaps that cause the parity to remain the same

Parity Byte & Block Check

What are parity byte & block checks?

• Parity blocks and parity bytes can be used to check an error has occurred and where the error is located

• Parity checks on their own do not pinpoint where errors in data exist, only that an error has occurred

• 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, 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

Checksum

What is a checksum?

• 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

What is an echo check?

• An 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

• If an error does occur the sender will retransmit the data