Mixing
![What is the slope of this line? [closed]](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhZCTB4-bb-s-32SAm6ytjzFOU06cH9o8q-a_wq_UnH6lcd8hvws23CmBWHM6g256LzTX9yK1EiCCzTC1NSgtxlNk_J9hdr9bA3tD0Nqntbl521j4bLAm_uXPANuWLBhcCKTKzns2gaUodx/s72-c/1.jpg)
Why or why not use an irreducible polynomial for a cyclic redundancy check?
Clash Royale CLAN TAG#URR8PPP
up vote
5
down vote
favorite
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?
finite-fields irreducible-polynomials cyclic-groups
edited Aug 6 at 8:07
TheSimpliFire
9,69261952
asked Aug 6 at 7:41
penguin359
1283
 |Â
show 5 more comments
up vote
5
down vote
favorite
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?
finite-fields irreducible-polynomials cyclic-groups
edited Aug 6 at 8:07
TheSimpliFire
9,69261952
asked Aug 6 at 7:41
penguin359
1283
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
– awkward
Aug 6 at 13:53
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."
– penguin359
Aug 6 at 15:37
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).
– Jyrki Lahtonen
Aug 8 at 4:54
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!
– Jyrki Lahtonen
Aug 8 at 5:03
@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.
– penguin359
Aug 8 at 19:25
 |Â
show 5 more comments
up vote
5
down vote
favorite
up vote
5
down vote
favorite
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?
finite-fields irreducible-polynomials cyclic-groups
edited Aug 6 at 8:07
TheSimpliFire
9,69261952
asked Aug 6 at 7:41
penguin359
1283
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?
finite-fields irreducible-polynomials cyclic-groups
edited Aug 6 at 8:07
TheSimpliFire
9,69261952
asked Aug 6 at 7:41
penguin359
1283
edited Aug 6 at 8:07
TheSimpliFire
9,69261952
edited Aug 6 at 8:07
TheSimpliFire
9,69261952
edited Aug 6 at 8:07
TheSimpliFire
9,69261952
9,69261952
asked Aug 6 at 7:41
penguin359
1283
asked Aug 6 at 7:41
penguin359
1283
asked Aug 6 at 7:41
penguin359
1283
1283
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
– awkward
Aug 6 at 13:53
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."
– penguin359
Aug 6 at 15:37
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).
– Jyrki Lahtonen
Aug 8 at 4:54
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!
– Jyrki Lahtonen
Aug 8 at 5:03
@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.
– penguin359
Aug 8 at 19:25
 |Â
show 5 more comments
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
– awkward
Aug 6 at 13:53
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."
– penguin359
Aug 6 at 15:37
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).
– Jyrki Lahtonen
Aug 8 at 4:54
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!
– Jyrki Lahtonen
Aug 8 at 5:03
@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.
– penguin359
Aug 8 at 19:25
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
– awkward
Aug 6 at 13:53
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
– awkward
Aug 6 at 13:53
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."
– penguin359
Aug 6 at 15:37
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."
– penguin359
Aug 6 at 15:37
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).
– Jyrki Lahtonen
Aug 8 at 4:54
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).
– Jyrki Lahtonen
Aug 8 at 4:54
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!
– Jyrki Lahtonen
Aug 8 at 5:03
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!
– Jyrki Lahtonen
Aug 8 at 5:03
@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.
– penguin359
Aug 8 at 19:25
@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.
– penguin359
Aug 8 at 19:25
 |Â
show 5 more comments
1 Answer
1
active
oldest
votes
up vote
1
down vote
accepted
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.
answered Aug 6 at 14:06
SBareS
3,1511026
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
1
down vote
accepted
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.
answered Aug 6 at 14:06
SBareS
3,1511026
add a comment |Â
up vote
1
down vote
accepted
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.
answered Aug 6 at 14:06
SBareS
3,1511026
add a comment |Â
up vote
1
down vote
accepted
up vote
1
down vote
accepted
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.
answered Aug 6 at 14:06
SBareS
3,1511026
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.
answered Aug 6 at 14:06
SBareS
3,1511026
answered Aug 6 at 14:06
SBareS
3,1511026
answered Aug 6 at 14:06
SBareS
3,1511026
answered Aug 6 at 14:06
SBareS
3,1511026
3,1511026
add a comment |Â
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2873671%2fwhy-or-why-not-use-an-irreducible-polynomial-for-a-cyclic-redundancy-check%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
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
– awkward
Aug 6 at 13:53
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."
– penguin359
Aug 6 at 15:37
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).
– Jyrki Lahtonen
Aug 8 at 4:54
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!
– Jyrki Lahtonen
Aug 8 at 5:03
@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.
– penguin359
Aug 8 at 19:25