Error Detection & Error Correction

Error Detection & Error Correction

Introduction:
In this blog post, I will be explaining the different types of error detection and error correction and identify what they are used for. I will also provide examples and identify suitable limitations whereas possible. The error detections and error corrections are:

• Parity Check (Good)
• Checksums (Better)
• Cyclic Redundancy Check (Best)

Overall, the different types of error detection and error correction are techniques for identifying whether the data file is corrupted or not whilst data is being sent across a network. It checks the quality of the data and this may help solve the issue depending on which method used.

Parity Check:

Parity checking is the most basic technique for error detection and error correction and uses mainly the 8^th bit for checking within the data packet. Before it performs the check to each individual bit in the packet, a protocol must be in place to decide whether it performs odd parity check or even parity check (assume the recipient device has the protocol check set to odd) - This method checks whether the amount of bits are even or odd in the packet.

In this example for when the data is sent, it will recheck the whole data packet to see if it has got an odd or an even amount of bits. In the end, if the total amount of bits are odd to begin with (which fits with the protocol), it will allow and accept the data to be received by the device. However, if it is even instead (somehow data corruption must of occurred midway its journey whilst sending) then error is detected because there is an even amount of 1’s. To correct this, the recipient device will reject the packet as a whole and will signal another request to the original device to resend – this process then repeats until the data is set correctly.

However, despite this effective procedure there is a big limitation that weakens this technique from the rest – data can bypass this protocol if there are two or more interferences to the bits within the packet. For example, the parity check is expecting there to be five 1’s and three 0’s but data got corrupted and ended up with seven 1’s and one 0. The amount of binary 1’s are still odd but the amount is incorrect, however parity checking does not correct this and thus allows the data to be passed (a limitation). As a result, the data will be accepted but the file will have some corruption in some areas. This can make it unreliable as the chance of this occurring in a large file transfer is higher, (see parity check table example below).

Parity Check Table Example:

Step 1: Packet example (protocol parity check is set odd, does not include the 8^th bit).

1

1

0

0

1

1

1

1

Step 2: The bit in the packet becomes corrupted.
Step 3: The 8^th bit at the end is used and is turned into a 0 because the number of odds does not correspond with the validation as it is even.

Data Received	1	1	0	1	1	1	1	1
Parity Checks	1	1	0	1	1	1	1	0

Step 4: The data is not odd as the 8^th bit is changed, checksum here is taken place.

Step 5: Recipient device requests the data packet to be resent.
Step 6: Packet is resent (Error Correction).

Data Received	1	1	0	0	1	1	1	1
Parity Checks	1	1	0	0	1	1	1	1

Step 6: Data is correct because it is odd. Data passes.

Limitation of Parity Check:

Step 1: The limitation is that the data can still pass through the parity check even if there are two errors with two bits as it has changed/corrupted.

Original Data	1	1	0	1	0	1	1	1
Data Received	1	1	0	0	1	1	1	1
Parity Checks	1	1	0	1	0	1	1	1

Step 2: The data is incorrect, but it still passes through because it fits the odd binary protocol.

Checksums:

Checksum is another technique for error detection and error correction that provides a more quality check for data transmission along a network (more complicated). How this works is that it firstly adds up the total amount of bits for a data packet and is then divided by a fixed divisor (number) often set by the network server. Usually this calculation is very precise and therefore will always result in a sum (known as quotient and are not used much after as the remainder is what makes checksum unique) and a remainder; this remainder will be taken and sent along with the packet data to the recipient device.

Furthermore, on the other end where the device receives this data, it will perform checksum and redo the previous sum to identify whether the remainder is identical. If the remainder is identical then this proves that there is no data corruption. However, if the remainder is different, then error has been detected and will therefore be corrected as it will request a signal back for the sender device to resend the packet again, (see below for example).

Checksum Example:

Total Amount of Bits/Data = 22.
Fixed Divisor = 4.

Calculation: 22 divided by 4.
Quotient = 5.
Remainder = 2 (uses and checks remainder).

Moreover, the limitations for this are that “checksum is the older of the two programs” (www.differentbetween.net/, 2014) comparing to CRC, this is because checksum was first created and therefore have become outdated when it was surpassed by CRC. Another limitation is that checksum can only use its technique on data packets that has approximately 8 bytes maximum and thus only being able to identify errors to individual bits rather than multiple at one time.

Cyclic Redundancy Check (CRC):

Cyclic Redundancy Check is essentially a combination of both parity check and checksum as explained above. However, the only difference to checksums is that it uses the polynomial formula (similar to the checksum example). This allows CRC to perform a more complicated and thorough check “based on 16- or 32-bit” (www.differencebetween.net/, 2014) meaning that this technique was created to identify a larger amount of data errors at one time as it covers more bits. This makes it more reliable than checksum as a result for larger files. One limitation can be speed because CRC may require more time to thoroughly perform error detection and error correction.

Harvard Referencing: (In order of reference)
- Anderson, K. Atkinson-Beaumont, D.Kaye, A. Lawson, J. McGill, R. Phillips, J and Richardson, D. 2011. Information Technology Level 3 Book 1 BTEC National. Harlow: Pearson Education Limited.
- differencebetween, 2014. Differences Between CRC and Checksum. [Online] Available at:  <http://www.differencebetween.net/technology/software-technology/differences-between-crc-and-checksum/> [Accessed 01 February 2015].