
	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:

x³²+x²⁶+x²³+x²²+x¹⁶+x¹²+x¹¹+x¹⁰+x⁸+x⁷+x⁵+x⁴+x²+x+1
A Standard Generating Polynomial - (IEEE 802.3)

The number of CRC bits corresponds to the degree of the generating polynomial. The above polynomial of degree 32 generates a 32-bit CRC that is used in computer networking. 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) = x³ + x² + 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 x³, where 3 is the number of bits in the CRC as given by the degree of P(x).

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

Step 2 - Divide the product M(x) x³ 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) x³ to give the code message polynomial C(x):

C(x) = M(x) x³ + 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) = x^K, (binary 1 followed by K-zeros).

        
          sent: 110010100  =  C(x)
         error: 000001000  =  E(x) = x³           
                --------- 
      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) = x^K 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) = x^K + x^K+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)=x^N+x^M 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 a primitive P(x). For example, the degree 4 irreducible P(x)=(11111) is not primitive and the two bit error E(x)=(100001) would not be detected since E(x)=(100001)=(11)(11111) 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) = x¹⁵ + 1 = (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 2^N 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 all burst errors spanning up to 16-bits;
100% detection of all two-bit errors not separated by exactly 2¹⁶-1 bits (this means all two bit errors in practice!);
For arbitrary multiple errors spanning more than 16 bits, at worst 1 in 2¹⁶ 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.


Fri Apr 19 12:03:14 ADT 2024 Last Updated: 24 JAN 2016	Richard Tervo [ tervo@unb.ca ]	Back to the course homepage...