{{pfw:banner.png}} ====== CRC - The Mathematics of Cyclic Redundance Checks ====== The idea of validating messages using cyclic redundancy checks (CRCs) goes back to an invention of W. Wesley Petersen in 1961((W. W. Peterson: Cyclic Codes for Error Detection. In: Proceedings of the IRE, Vol. 49, No. 1, 1961, S. 228–235 )).\\ It is based on cyclic codes which themselves are based on polynomial ring arithmetic. Let's see what this is all about. ===== Polynomials and their arithmetic ===== Mathematians define entities with operations on them and then study the general properties of the resulting structures. For example, they do this extensively with natural numbers in number theory where the existence of prime numbers and the representation of any number as a unique product of prime numbers is an important result that has applications e.g. in todays cryptography. Among the structures mathematians study are //fields//, //groups// and //rings//. Here we will look at rings. ===== Contributions =====
(1) 0001 0000 0010 0001 = $1021
16 1 1 1 98 7654 3210
5 2 1
Similar to paper and pencil division with numbers we divide by the generator polynomial by subtraction according to place. As the coefficients are from W2 adding and subtracting can be implemented by the bit-wise-xor-operation.
The bits of the message are inspected one after the other and if possible the generator polynomial is subtracted at the inspected position.
At the end of this procedure we gain the remainder of the division by the generator polynomial encoded as a 16-bit-number.
//DISCUSS THE CONCRETE ALGORITHM AND THE EXAMPLE CALCULATION//
uh 2022-05-16