 ECE4253 Digital Communications Department of Electrical and Computer Engineering - University of New Brunswick, Fredericton, NB, Canada

# Error Detection with the CRC

The Cyclic Redundancy Check (CRC) involves appending a number of extra bits to a binary message to achieve error detection for a variety of possible bit errors.

While the use of a single parity bit allows detection of single bit errors, a second error will go undetected, as will any even number of bit errors. Unless the probability of a error is very low and a message is very short (the case when a parity bit is added to a 7-bit ASCII character) the chances of some error event going undetected may be high. In contrast, by using many extra bits the CRC can potentially detect multiple bit errors.

## Systematic Block Code (n,k)

In general, use of parity bits or the CRC are both examples of systematic block codes, where a block of k input bits is taken to create an n-bit codeword known as an (n,k) code. The number of extra bits is p = n-k. By this definition, the use of 7-bits plus parity describes an (8,7) code for which p= (8 - 7) =1. The code is systematic in that the extra bits are appended to unmodified data bits. In the case of CRC, the block size k is often variable, while the constant p depends on the degree of a defining polynomial P(x). Like the systematic ISBN or LUHN-10 algorithms, the CRC algorithm computes the modulus of a known constant (polynomial) that is often prime. Upon reception a zero remainder after division indicates no error has been detected.

# The Cyclic Redundancy Check (CRC)

Consider a message having many data bits which are to be transmitted reliably by appending several check bits as shown below.

 message bits check bits

The exact number of extra bits and their makeup depends on a generating polynomial. For example, one such polynomial is:

x16 + x12 + x5 + 1
A Standard Generating Polynomial - CRC(CCITT)

The number of CRC bits corresponds to the degree of the generating polynomial. The above polynomial of degree 16 generates a 16-bit CRC. Typically, the CRC bits are used for error detection only.

# CRC Computation

Consider a message represented by some polynomial M(x), and a generating polynomial P(x).

In this example, let M(x) represent the binary message 110010, and let P(x) = x3 + x2 + 1 = (1101).

The polynomial P(x) will be used to generate three check bits called CRC(x) which will be appended to M(x). Note that this P(x) is prime.

 110010 CRC

The polyomial P(x) defines the CRC bits for a given message.

The check bits will be chosen such that the entire message+crc will be an exact multiple of P(x). The steps to achieving this goal are shown below.

Step 1 - Multiply the message M(x) by x3, where 3 is the number of bits in the CRC.

Add 3 three zeros to the binary M(x).

Step 2 - Divide the product M(x) x3 by the generating polynomial P(x).

We wish to find "the remainder, modulo P(x)"

Compute the following:

```
100100  (ignore this quotient)
------------
1101 ) 110010000
1101
----
1100
1101
----
100   = remainder = R(x)

```
Observe that if R(x) were in place of the appended zeros, the remainder would become 000.

Let CRC(x) = R(x).

Check the math with the online polynomial calculator.

Consider the decimal number x=41 and the divisor y=13.

Q: What can be done to make x divisible by y?

A: If 41 ≡ 2 mod 13, then (41-2) ≡ 0 mod 13.

In general, if the division x/y gives remainder z, then (x-z)/y gives remainder zero.

Step 3 - Add the remainder CRC(x) to the product M(x) x3 to give the code message polynomial C(x):

C(x) = M(x) x3 + CRC(x)

Put the remainder CRC(x)=100 in place of the three zeros added in Step 1.

 110010 100

The message may now be transmitted

The transmission C(x) = (110010100) is now an exact multiple of P(x) = (1101); division C(x)/P(x) gives zero remainder, or C(x) ≡ 0 mod P(x). Upon reception, it is expected that an errored message will no longer be a multiple of P(x).

# MATLAB Example

The above result can be found directly using the MATLAB Communications Toolbox as:
```>> Hgen = comm.CRCGenerator([1 1 0 1]);  % specify polynomial as [1 1 0 1] or [3 2 0]
>> M = [1 1 0 0 1 0];                    % M(x) = message bits
>> C = step(Hgen, M');                   % supply message bits as a column vector
>> disp( C' );                           % C(x) = codeword returned as column vector

1  1  0  0  1  0  1  0  0
```
The output C(x) includes three CRC bits appended (highlighted). This codeword may now be transmitted.

# CRC Error Checking - No Errors

Upon reception, an entire received codeword R(x) = "message + crc" can be checked simply by dividing R(x)/P(x) using the same generating polynomial. If the remainder after division equals zero, then no error was found.

```
100100  (ignore this quotient)
------------
1101 ) 110010100
1101
----
1101
1101
----
000   = remainder (no error)
```

Check the math with the online polynomial calculator.

# MATLAB Example

The above result with no error can be checked as:
```>> Hdet = comm.CRCDetector([1 1 0 1]);  % specify polynomial as [1 1 0 1] or [3 2 0]
>> R = C;                               % R(x) = received data = the (unerrored) codeword
>> [data,error] = step(Hdet, R );       % check the received data R(x) with no error
>> disp( error );

0
```
The zero result indicates no error was found. A result equal to 1 would indicate a detected error.

# CRC Error Checking - Single Bit Error

A single bit error in bit position K in a message C(x) can be represented by adding the term E(x) = xK, (binary 1 followed by K-zeros).

 ``` sent: 110010100 = C(x) error: 000001000 = E(x) = x3 --------- received: 110011100 = C(x) + E(x) (error in bit 3) ```

The above error is detected when the CRC division gives a non-zero remainder:

```
100101  (ignore this quotient)
------------
1101 ) 110011100  = C(x) + E(x)
1101
----
1111
1101
----
1000
1101
----
101   = remainder (error!)
```

Check the math with the online polynomial calculator.

## An Important Observation

Dividing the received C(x)+E(X) by P(x) revealed the error. On the other hand, since C(x)/P(x) ≡ 0 mod P(x) by definition, the remainder is a function only of the error. An error in this same bit would give the same non-zero remainder regardless of the message bits C(x).

 ``` C(x) + E(x) C(x) E(x) E(x) ----------- = ----- + ----- = ----- P(x) P(x) P(x) P(x) ``` The remainder is a function only of the errored bits E(x).

It follows that the error control performance can be fully explored by examining only the possible errors E(x) independently of any message bits.

For example, the above result is the same if only the error E(x) is checked using P(x):

```
1  (ignore this quotient)
------------
1101 ) 000001000   = E(x) alone
1101
----
101   = remainder (error!)
```

Check the math with the online polynomial calculator.

The general performance of the CRC for all possible single bit errors E(x) may now be stated. Since E(x) = xK has no factors other than x, a single bit error will never produce a term exactly divisible by P(x). All single bit errors will be detected.

# CRC Error Checking - Double Bit Error

If E(x) = xK + xK+1, the error pattern includes two adjacent bits (e.g. E(x) = (000011000) for K=3).

Since this E(x) has no factors other than (x+1) and x, any adjacent bit errors will never produce a term exactly divisible by P(x). All double bit (adjacent-bit) errors will be detected

# CRC Error Checking - Simply Parity

Observe that a CRC calculation based on the polynomial P(x) = x + 1 leaves a one-bit remainer and is a simple parity generator (even).

# CRC Error Checking - Choice of P(x)

While the choice of a primitive polynomial for P(x) can be advantageous (see below) a compound polynomial that is a multiple of (11) such as P(x)=(11101)=(11)(1011) is also useful; in this case, codewords will be multiples of both (11) and (1011). In particular, the factor (11) ensures that transmitted codewords are necessarily multiples of (11); in other words, all have even parity and any error E(x) having an odd number of 1's will be detected.

Two Bit Errors

The general two-bit error E(x)=xN+xM is not detected if E(x) is a multiple of P(x). In particular, the E(x)=(10000001) having two bad bits 7-bits apart would not be detected for P(x) = (1101) because (10000001)=(11)(1011)(1101). (Check the math)

The allowable separation between two bad bits is related to the choice of P(x) and will be maximum for an primitive polynomial P(x). For example, the prime P(x)=(11111) is not primitive and the two bit error E(x)=(100001) would not be detected since it is an exact multiple of P(x). By instead choosing the primitive P(x)=(11001) of the same degree, all two bit errors up to E(x) = (1000000000000001) will be detected.

# MATLAB Example

The above example of an undetected error can be confirmed as:
```>> Hdet = comm.CRCDetector([1 1 0 1]);   % specify polynomial P(x) as [1 1 0 1] or [3 2 0]
>> E = [ 1 0 0 0 0 0 0 1 ];              % This E(x) will be undetected for this P(x)
>> [data,error] = step(Hdet, E');        % Check the error pattern E(x) alone.
>> disp( error );

0
```
The two bit error E(x) = (1 0 0 0 0 0 0 1) was not detected. Any error E(x) that is a multiple of P(x) would not be detected.

# CRC Error Checking - Undetected Errors

From the above discussion, any bit error term E(x) which is an exact multiple of P(x) will not be detected.

In general, bit errors and bursts up to N-bits long will be detected for a P(x) of degree N. For arbitrary bit errors longer than N-bits, the odds are one in 2N than a totally false bit pattern will nonetheless lead to a zero remainder.

In essence, 100% detection is assured for all errors E(x) not an exact multiple of P(x). For a 16-bit CRC using a primitive P(x) this means:

• 100% detection of single-bit errors;
• 100% detection of all adjacent double-bit errors;
• 100% detection of any errors spanning up to 16-bits;
• 100% detection of all two-bit errors not separated by exactly 216-1 bits (this means all two bit errors in practice!);
• For arbitrary multiple errors spanning more than 16 bits, at worst 1 in 216 failures, which is nonetheless over 99.995% detection rate.

Ultimately, the CRC bits are expected to ensure a minimum Hamming distance between all possible transmitted codewords; consequently, the error detection performance of a given P(x) depends on the codeword length. Given a known codeword size and a sufficently large Hamming distance, error correction is also possible.

 Thu Aug 22 21:21:49 ADT 2019 Last Updated: 24 JAN 2016 Richard Tervo [ tervo@unb.ca ]