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).

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 X ^{n}+1* where

To pick a suitable generator polynomial,
* check this
table* that lists X

__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 X^{n}+1 will be X^{6}+1. We find the
irreducible factors of X^{6}+1:

X^{6}+1 = (X+1)^{2}.(X^{2}+X+1)^{2}.

Using the obtained factors, a valid generator polynomial
with degree 3 would be (X+1)(X^{2}+X+1) = X^{3}+1.

Since the coefficients of CRC polynomials are based on
modulo 2, i.e. their values are 1 or 0,

X^{3}+1 = X^{3 }+ 0X^{2}
+ 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.

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:

X^{n-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, X^{n-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:

X^{n-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:

X^{n-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 X^{n-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 {X^{n-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) = X^{2} + X, which
represents data word (110) in binary.

Let the code generator polynomial G(x) = X^{4}
+ X^{3} + X^{2} + 1 = 11101.

This gives, X^{4}. D(x) = X^{6} + X^{5}
= 1100000,

and R(x) = X^{4}. D(x) mod G(x) = 1100000 mod 11101
= 1001.

And finally, the generated encoded word is E(x) = X^{4}
. 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”.

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.

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) = X^{2} + X = 110, G(x) = X^{4} + X^{3}
+ X^{2} + 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.

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.