Error checking

July 2015

Error checking

Binary encoding is very practical for use in electronic devices such as computers, in which information can be encoded based on whether an electrical signal is present or not.

However, this electrical signal may suffer disturbances (such as distortion or noise), especially when data is transported over long distances. For this reason, being able to check to validity of the data is a must for certain uses (including for professionals, banks, industrial uses, and confidential or security-related information)

This is why mechanisms exist for ensuring a certain level of data integrity, meaning confirmation for the recipient that the data received is indeed similar to that transmitted. There are two ways to protect data transfers from errors:

  • by installing a more reliable transmission medium, i.e. a physical layer of protection. A conventional connection typically has an error rate between 10-5 and 10-7.
  • or by implementing logical mechanisms for detecting and correcting errors.

Most logic-based error control systems are based around adding information (this is called "redundancy") in order to check the validity of the data. This additional information is called a checksum.

Error correction

Better error detection systems have been perfected, using codes called:

  • Self-correcting codes
  • Self-checking codes

Parity check

Parity check (sometimes called VRC, for Vertical Redundancy Check or Vertical Redundancy Checking) is one of the simplest checking mechanisms. It involves adding an additional bit (called a parity bit) to a certain number of bits of data called a code word (generally 7 bits, so as to form a byte when combined with the parity bit) whose value (0 or 1) is such that the total number of 1 bits are even. To be more straightforward, 1 if the number of bits in the code word is odd, 0 otherwise.

Take the following example:

In this example, the number of 1 data bits is even, so the parity bit is set to 0. By contrast, in the example below, the data bits are odd, so the parity bit becomes 1:

Let's pretend that after being transmitted, the lowest-weighted bit of the previous byte (the one on the far right) had fallen victim to interference:

The parity bit, in this case, no longer corresponds to the byte's parity: an error has been detected.

However, if two bits (or an even number of bits) had simulatenously changed as the signal was being sent, no error would have been detected.

As the parity control system can only detect an odd number of errors, it can only detect 50% of all errors. This error-detection mechanism also has the major downside of being unable to correct the errors it finds (the only way to fix it is to request that the erroneous byte be retransmitted)

Longitudinal redundancy check

A longitudinal redundancy check (LRC for short; also called a horizontal redundancy check or cross-parity check) involves checking not the integrity of the data representing a single character, but the bit parity integrity of a group of characters.

Let "HELLO" be the message transmitted, using standard ASCII. Here is the data as it will be transmitted with longitudinal redundancy check codes:

LetterASCII Code
(7-bit)
Parity bit
(LRC)
H10010000
E10001011
L10011001
L10011001
010011111
VRC10000100

Cyclic Redundancy Check

A cyclic redundancy check (or CRC for short) is a powerful, easy-to-implement data integrity control method. It is the primary method of error detection used in telecommunications.

Concept

Cyclic redundancy checking involves protecting data in blocks, called frames. Each frame is assigned a segment of data, called a control code (occasionally FCS for Frame Check Sequence in the case of a 32-bit sequence, and sometimes erroneously labelled a CRC). The CRC code contains data redundant with the frame, so that errors can be not merely detected, but fixed.

Cyclic redundancy check (CRC)

The concept of CRC involves treating binary sequences as binary polynomials, meaning polynomials whose coefficients correspond to the binary sequence. For example, the binary sequence 0110101001 may be represented as a polynomial as shown here:

0*X9 + 1*X8 + 1*X7 + 0*X6 + 1*X5 + 0*X4 + 1*X3 + 0*X2 + 0*X1 + 1*X0
which is
X8 + X7 + X5 + X3 + X0
or
X8 + X7 + X5 + X3 + 1

In this way, the lowest-weight bit in the sequence (the one furthest to the right) represents degree 0 of the polynomial (X0 = 1), the 4th bit from the right represents degree 3 of the polynomial (X3), and so on. An n-bit sequence, then, forms a polynomial of a maximum degree of n-1. All polynomial expressions are then manipulated using modulo 2.

In this error-detection process, a predefined polynomial (called the generator polynomial and shortened to G(X)) is known to both the sender and the recipient. The sender, to start the error detection mechanism, runs an algorithm on the frame bits in order to generate a CRC, and then transmits these two elements to the recipient. The recipient then performs the same calculation in order to check that the CRC is valid.

Practical application

Let M be the message which corresponds to the frame bits to be sent, and let M(X) be the related polynomial. Let M' be the message transmitted, i.e. the initial message to which an n-bit CRC is to be concatenated. The CRC is such that M'(X)/G(X)=0. The CRC code, therefore, is equal to the remainder of the polynomial division of M(X) (to which n nul bits, corresponding to the length of the CRC, had previously been appended) over G(X).

For example: take the message M with the following 16 bits: 1011 0001 0010 1010 (called B1 in hexadecimal). Take G(X) = X3 + 1 (represented in binary by 1001). Given that G(X) has degree 3, the result is to add 4 nul bits to M: 10110001001010100000. The CRC is equal to the remainder of M divided by G :

10110001001010100000
1001...,..,.,.,.....
----...,..,.,.,.....
0100..,..,.,.,.....
0000..,..,.,.,.....
----..,..,.,.,.....
1000.,..,.,.,.....
0000.,..,.,.,.....
----.,..,.,.,.....
1000.,..,.,.,.....
1001,..,.,.,.....
----,..,.,.,.....
1111..,.,.,.....
1001..,.,.,.....
----..,.,.,.....
1100.,.,.,.....
1001.,.,.,.....
----.,.,.,.....
1101,.,.,.....
1001,.,.,.....
----,.,.,.....
1000.,.,.....
0000.,.,.....
----.,.,.....
10001......
1001,.,.....
----,.,.....
10000.,.....
1001.,.....
----
1111,.....
1001,.....
----,.....
1100.....
1001.....
----.....
1100....
1001....
----....
1010...
1001...
----...
0110..
0000..
----..
1100.
1001.
----.
1010
1001
----
0011

To create M', concatenate the resulting CRC to the bits of the frame to be transmitted:

M' = 1011000100101010 + 0011
M' = 10110001001010100011

Therefore, if the message's recipient divides M' by G, he or she will get a remainder of zero if the transmission took place without any errors:

10110001001010100011
1001...,..,.,.,...,,
----...,..,.,.,...,,
0100..,..,.,.,...,,
0000..,..,.,.,...,,
----..,..,.,.,...,,
1000.,..,.,.,.....
1001.,..,.,.,.....
----.,..,.,.,.....
0010,..,.,.,.....
0000,..,.,.,.....
----,..,.,.,.....
0101..,.,.,.....
0000..,.,.,.....
----..,.,.,.....
1010.,.,.,.....
1001.,.,.,.....
----.,.,.,.....
0110,.,.,.....
0000,.,.,.....
----,.,.,.....
1101.,.,.....
1001.,.,.....
----.,.,.....
1010,.,.....
1001,.,.....
----,.,.....
0111.,.....
0000.,.....
----
1110,.....
1001,.....
----,.....
1111.....
1001.....
----.....
1100....
1001....
----....
1010...
1001...
----...
0110..
0000..
----,,
1101,
1001,
----,
1001
1001
----
0

Generator polynomials

The most commonly used generator polynomials are:

  • CRC-12: X12 + X11 + X3 + X2 + X + 1
  • CRC-16: X16 + X15 + X2 + 1
  • CRC CCITT V41: X16 + X12 + X5 + 1
    (this code is used in the HDLC procedure.)
  • CRC-32 (Ethernet): = X32 + X26 + X23 + X22 + X16 + X12 + X11 + X10 + X8 + X7 + X5 + X4 + X2 + X + 1
  • CRC ARPA: X24 + X23+ X17 + X16 + X15 + X13 + X11 + X10 + X9 + X8 + X5 + X3 + 1
For unlimited offline reading, you can download this article for free in PDF format:
Error-checking .pdf

See also


Verificación de errores
Verificación de errores
Die Fehlerkontrolle
Die Fehlerkontrolle
Contrôle d'erreur (CRC)
Contrôle d'erreur (CRC)
Il controllo degli errori
Il controllo degli errori
O controlo de erros
O controlo de erros
This document entitled « Error checking » from CCM (ccm.net) is made available under the Creative Commons license. You can copy, modify copies of this page, under the conditions stipulated by the license, as this note appears clearly.