5
$\begingroup$

I understand the need for using an irreducible polynomial for a prime power finite field when doing multiplication with numbers in those fields. For certain applications, such as the Q parity bytes used in RAID6, a non-zero number should have a multiplicative inverse which might fail if it can be multiplied by another non-zero number in that field and yield zero. However, I don't fully understand its importance in its use with cyclic redundancy checks. This seems to be a bit different scenario because instead of working with numbers inside the field, your taking a message that represents a number that's generally much, much larger than the field and dividing it down to fit in the field. After that, your pretty close to been done with the CRC with maybe a an XOR to complete the job.

As a counter example, I discovered that the polynomial used for the CRC32 on CD-ROM is composed of two smaller polynomial: $(x^{16} + x^{15} + x^2 + 1) \cdot (x^{16} + x^2 + x + 1)$.

Maybe the a question I need to ask is a why would they use a reducible polynomial in this case rather than a known irreducible one?

$\endgroup$
  • $\begingroup$ The Wikipedia article on cyclic redundancy checks seems to discuss this issue in the section titled "Designing Polynomials". en.wikipedia.org/wiki/Cyclic_redundancy_check $\endgroup$ – awkward Aug 6 '18 at 13:53
  • $\begingroup$ Interesting, a quote from that article gives an interesting hint to the answer of my question: "A common misconception is that the "best" CRC polynomials are derived from either irreducible polynomials or irreducible polynomials times the factor 1 + x, which adds to the code the ability to detect all errors affecting an odd number of bits.[7] In reality, all the factors described above should enter into the selection of the polynomial and may lead to a reducible polynomial." $\endgroup$ – penguin359 Aug 6 '18 at 15:37
  • $\begingroup$ I don't claim to understand the finer points of CRC-polynomial selection but in your example I am actually a bit worried about the presence of that double zero $x=1$ (a root of both factors). $\endgroup$ – Jyrki Lahtonen Aug 8 '18 at 4:54
  • $\begingroup$ See here for a bit more. I think you can relatively safely just skim my answer (while I do know some coding theory and cyclic codes in particular, CRC-polynomial selection also has criteria beyond just minimum Hamming weight of a non-catchable error). Do check out the links! $\endgroup$ – Jyrki Lahtonen Aug 8 '18 at 5:03
  • $\begingroup$ @Jyrki My example isn't just a polynomial I picked, it's what's specified in the ECMA-300 standard for encoding data sectors on a CD. I would assume it was well picked for that purpose, but I don't fully understand why. I think it's partly due to catching certain categories of burst errors and that the data being is only 16384 bits (2048 bytes) which is within the range of a 16-bit CRC's limit. $\endgroup$ – penguin359 Aug 8 '18 at 19:25
1
$\begingroup$

Say you want to transmit a polynomial $M(x)$, but the recipient receives a slightly different polynomial $M'(x)$. We can define the "error polynomial":

$$E(x)=M'(x)-M(x)$$

Call the CRC-polyomial $P$. Then an error will go undetected iff $P$ divides $E$, or in other words if every divisor of $P$ is also a divisor of $E$. We can therefore guarantee that certain kinds of errors get caught by analysing the divisors of $P$ and $E$. Here are a few simple examples:

$E(x)=x^{n+m}+x^{n+m-1}+...+x^n=x^n(x^m+x^{m-1}+...+1)$, a burst error, ie. $m+1$ flipped bits in a row. This will be caught if $P$ has nonzero constant term (so it has no common divisors with $x^n$) and is of degree greater than $m$ (since it then cannot divide a polynomial of degree $m$).

$E(1)=1$, ie. an odd number of flipped bits. This will be caught if $x+1$ divides $P(x)$, since then $P(1)=0$.

$E(x) = x^{n+m} + x^m=x^n(x^m+1)$, ie. two flipped bits $m$ bits appart. This will be caught if $P$ is a multiple of a primitive polynomial of order greater than $m$. So a primitive polynomial of degree $d$ will catch two errors if they are less than $2^d-1$ bits appart.

So in short, using a reducible polynomial may indeed be desirable if you want to guarantee certain kinds of errors get caught.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.