(not their purpose)
In: Mathematics
All (computer) data can be represented by 0s and 1s, _binary_. One special operation one can do is forming the **XOR** (_(bitwise) exclusive-or_) of two binary sequences:
A: 10010110011
B: 1101101
XOR: 01001100011
What we did here is, at each position, write down a “0” if the corresponding digits of A and B are the same (so both a 0 or both a 1), and we write a “1” if the digits are different.
This forms the basis for CRC:
**The algorithm**
For each specific CRC version comes with a fixed binary sequence, the _pattern_. Lets for example take **1011**.
Now given any binary data, say 101011001110, we find the left-most “1” and starting there **XOR** with the pattern:
A: 101011001110
P: 1011
XOR: 000111001110
Remove the leftmost 0s, then rinse and repeat with the result:
111001110
P: 1011
XOR: 010101110
And again!
10101110
P: 1011
XOR: 00011110
…
11110
P: 1011
XOR: 01000
And finally
1000
P: 1011
XOR: 0011
We stop when the result is shorter than the pattern. In this case we ended up with **11**. This is the CRC.
**What it means (advanced)**
A _binary polynomial_ is a sum of different powers of a variable “x” such as x^^7 + x^^5 + x^^4 + x^^2 + x + 1. We can save lots of time and space by just noting in binary if the exponent is there (“1”) or missing (“0”); so in this case 10110111, where the leftmost 1 is for the x^^7, the following 0 is for the lack of x^^6 and so on.
What then happens under the hood is _polynomial division_: we try to divide one polynomial by another and maybe get a remainder. If you never worked with polynomials, then next closest thing would be integer division. For example 17:5 = **3** R _2_, because 17 fits the 5 fully **3** times, but a remaining _2_ is left over.
The algorithm efficiently calculates this remainder but for binary polynomials in binary arithmetic. But instead of ever writing polynomials it always keeps things in binary format.
In math terms it’s a polynomial division with a constant divisor, and then just keeping the remainder. So your data is a binary number N and you divide it for example by x^3 +x+1.
In practical terms this is equivalent to just executing a moving XOR operation with your data and the coefficients or the polynom.
The coefficients are 1101 So the algorithm goes as follows:
Take fhe first 4 bits of your data, calculate the XOR operation on them with 1101, then remove the first bit of the result and add the 5th bit of the data. Repeat until you arrive at the end. XOR in case you don’t know is “exclusive OR” wich basically flips your data bits whenever there is a 1 in your polynomial
Latest Answers