Systematic and Standard CRC Simulator Help

Introduction:

An error-detection technique used widely in today’s computer networks and data storage devices is based on Cyclic Redundancy Check (CRC) codes.

In this simulator, we are implementing two different types of CRC codes: one is the Systematic CRC code and the other is the standard CRC code. The Systematic CRC code is also called “Separable” CRC because data word can be located and retrieved from encoded word before the decoding process takes place. The standard CRC, on the other hand, is called “Non-Separable” CRC code because the data word cannot be separated from encoded word before it goes through a decoding process.

The basic idea of CRC coding is to generate an encoded word of length n bits by using a k-bit data word and an (n-k+1)-bit generator polynomial whose degree is (n-k).

An (n,k) CRC code is capable of detecting all single bit errors and all burst of adjacent bit errors with length less than or equal to the degree of the generator polynomial (i.e. up to n-k bits).

How to select a Generator Polynomial?

Not all polynomials are considered CRC generator polynomials. For a polynomial to be a valid CRC generator polynomial to detects errors as expected, it has to be irreducible and divides Xn+1 where n is the length of the encoded word. A polynomial is irreducible if it cannot be factored into non-trivial polynomials. To find a valid generator polynomial, we apply the following theorem: “G(x) is the generator polynomial for a linear cyclic code of length n if and only if G(x) divides Xn+1 (so Xn+1 = H(x).G(x)).

To pick a suitable generator polynomial, check this table that lists Xn+1, for n=3...15, factored to its irreducible polynomials.

Example:

Assume that we want to generate encoded words of length 6 bits using a generator polynomial whose degree is 3. As the encoded word is of length 6 bits, then Xn+1 will be X6+1. We find the irreducible factors of X6+1:

X6+1 = (X+1)2.(X2+X+1)2.

Using the obtained factors, a valid generator polynomial with degree 3 would be (X+1)(X2+X+1) = X3+1.

Since the coefficients of CRC polynomials are based on modulo 2, i.e. their values are 1 or 0,
X3+1 = X3 + 0X2 + 0X + 1 = 1001 in binary representation.

Note: When entering a code generator (polynomial) into the simulator, it will be validated according to the above rule once you click "Encode" button. If the code generator is invalid, simulator will issue a warning but will let you continue so you can also experiment on invalid code generators.

Description of Simulator Functions:

Systematic CRC Encoder:

This module takes the two binary inputs, data word and generator polynomial, and carries out the necessary calculation to produce the encoded word. The calculation is done according to following expression:

Xn-k D(x) = Q(x) G(x) + R(x),

Where D(x) is the data word of length k bits, G(x) is the generator polynomial of length (n-k+1) bits, Xn-k is the (n-k) term of G(x), Q(x) is the quotient and R(x) is the remainder.

The above expression can be written as:

Xn-k D(x) - R(x) = Q(x) G(x).

And since we will be using modulo-2 arithmetic, addition and subtraction are the same, and this gives:

Xn-k D(x) + R(x) = Q(x) G(x) = E(x), which is the encoded word.

This means that the encoded word E(x) the Systematic Encoder produces is obtained by first left-shifting the data word n-k bits (identical to multiplying it by Xn-k), and second by dividing the product by G(x) to get the remainder R(x). That remainder is then added to the left-shifted data word {Xn-k D(x)} and the result will be the encoded word E(x). Note that all divisions and additions are done using modulo-2 arithmetic.

Example:

Let data word polynomial D(x) = X2 + X, which represents data word (110) in binary.
Let the code generator polynomial G(x) = X4 + X3 + X2 + 1 = 11101.
This gives, X4. D(x) = X6 + X5 = 1100000,
and R(x) = X4. D(x) mod G(x) = 1100000 mod 11101 = 1001.
And finally, the generated encoded word is E(x) = X4 . D(x) + R(x) = 1100000 + 1001 = 1101001.

Note that the data bits are located in the leftmost k bits of the encoded word. This enables the receiver of the encoded word to separate and retrieve data word before doing the decoding. That explains why Systematic CRC code is also called “Separable”.

Systematic CRC Decoder

This module works by getting the input encoded word E(x), which might contain errors, and dividing it by the generator polynomial G(x) to get the remainder R(x). I.e. calculating E(x) mod G(x). If remainder of division R(x) is zero then the encoded word has no errors, otherwise error is detected with a non-zero remainder.

Standard CRC Encoder:

The standard CRC encoder is different from the Systematic CRC encoder in the way the encoded word is calculated. As will be noticed, the data bits cannot be separated from encoded word before decoding takes place. The encoding in the standard (n,k) CRC codes is done using the following expression:

Encoded word E(x) = D(x) . G(x)

Where D(x) is the data word of length k bits and G(x) is the generator polynomial of length (n-k+1) bits and degree of (n-k). The result of this multiplication is the encoded word E(x) with length of n bits.

Example:

Let D(x) = X2 + X = 110, G(x) = X4 + X3 + X2 + 1 = 11101.
Then, E(x) = D(x) . G(x) = (110) (11101) = 1001110, using modulo-2 multiplication.

As seen above, data bits cannot be separated from encoded word before decoding.

Standard CRC Decoder:

The decoding process includes dividing the received encoded word E(x) by the generator polynomial G(x) to get remainder R(x). If remainder of division is zero then the received encoded word has no errors, otherwise error is detected with a non-zero remainder.