Skip to main content
6 votes
Accepted

Check if a given polynomial is primitive

In order to check that a degree $n$ polynomial $P$ over $GF(2)$ is primitive, you first need to know the factorization of $2^n-1$ (you can look it up in tables, or use a CAS). Then, you test that $x^{...
Yuval Filmus's user avatar
5 votes
Accepted

Can one quickly update CRC codes based on small change and previous CRC code?

Yes, this is possible. The new CRC value can be computed very efficiently. To see how, you need to know some math and about how CRCs can be viewed as polynomials. The CRC checksum of the bit-string $...
D.W.'s user avatar
  • 162k
4 votes
Accepted

Correcting two-bit error using a CRC

One approach: Use a meet-in-the-middle algorithm. Build a precomputed table that stores $T_i = x^i \bmod P(x)$ for all $i$ up to the maximum message length. Now, given $S$, you are looking for $i,j$ ...
D.W.'s user avatar
  • 162k
3 votes
Accepted

What is the principle of multiplication of D-normalized polynomials for a CRC calculation?

For the first question, the >> 1 is multiplying the polynomial bPowX[k] by x. (The polynomials in this implementation are ...
Mark Adler's user avatar
2 votes

Protecting data unequally using Error Correction Codes

Schulman's tree code may come in handy: This is a prefix code where future symbols of the codeword give some information about the prefix up to that point. Using that code, there is better probability ...
Ran G.'s user avatar
  • 20.7k
2 votes

Protecting data unequally using Error Correction Codes

Since error correction here is essentially discrete, it might not be easy to come up with an optimal transient encoding, however you can approximate this by applying different encoding schemes for ...
Husrev's user avatar
  • 190
2 votes
Accepted

Numerically validate CRC performance

There are multiple techniques to compute the minimum Hamming distance for a given CRC polynomial. I don't know what technique they used, but here are three techniques that seem suitable. I will ...
D.W.'s user avatar
  • 162k
2 votes

How to handle generator polynomial in CRC if given in (x+1) (x^3+ x^2 +1) form?

When computing CRC, we are working over the field of two elements. In this field, 2=0. Therefore $$ (x+1)(x^3+x^2+1) = x^4+x^2+x+1. $$
Yuval Filmus's user avatar
2 votes

CRC computation speed vs polynomials features

The speed issue would depend on the hardware / processor. For CRC, what is needed is carryless multiply (CLMUL), and I assume most processors that have carryless multiplies, which date back to 2008 ...
rcgldr's user avatar
  • 364
2 votes
Accepted

Why does $x^{15}+x^{14}+1$ detect all errors at most 32768 bits apart?

Your polynomial is primitive, which means that the order of $x$ modulo your polynomial is exactly $2^{15}-1$. In particular, $x^a \not\equiv 1$ modulo your polynomial for all $1 \leq a \leq 2^{15}-2$, ...
Yuval Filmus's user avatar
2 votes
Accepted

What happens if CRC fails and errors are not detected?

Most communications is done in levels. The lowest levels must be correct before we accept the next level. You want to send an array of bytes from A to B. A added a CRC which B checked and removed. But ...
gnasher729's user avatar
  • 30.6k
2 votes

What happens if CRC fails and errors are not detected?

The CRCs used in real systems are very robust. Here is a list of some standard CRC polynomials. As an example, let us take the CRC-32 used in the Ethernet protocol. For this, the probability of ...
codeR's user avatar
  • 1,435
2 votes

What happens if CRC fails and errors are not detected?

If the CRC is the only means of error correction/detection, there is nothing one can do about this at the coding level. Higher level protocols may have other means of detecting if a message is "...
kodlu's user avatar
  • 627
2 votes

fast CRC computation

If I remember right, CRC is defined for sequences of bits, but you can take an input byte and pre-calculate what the next 8 operations would be, and what their effect would be. So with a table of 256 ....
gnasher729's user avatar
  • 30.6k
1 vote

Why does a CRC detect burst errors of longer than r+1 bits independently of burst length?

There is a dependence on the length. For an n-bit CRC and a k-bit burst error, the probability of a false positive is (2max(k – n, 0) – 1) / (2k – 1). One minus that is the probability of a k-bit ...
Mark Adler's user avatar
1 vote

Fingerprint functions for set equality checks?

A Bloom filter has this property. Use the Bloom filter itself as the fingerprint. The merge operation can be implemented as bitwise OR. For multisets, see https://crypto.stackexchange.com/q/54544/...
D.W.'s user avatar
  • 162k
1 vote
Accepted

Detecting errors changing an odd number of bits using CRC

Recall that we are working modulo $2$. Thus $E(x)$ is a polynomial whose coefficients are $0,1$, and $E(1) \in \{0,1\}$. By definition, $G(x)$ is a factor of $E(x)$ if there exists a polynomial $H(x)$ ...
Yuval Filmus's user avatar
1 vote

Understanding a CRC32 Implementation

Perhaps what you are imagining is something like this at the top of the inner loop, where the bits of b are fed one-by-one into the high bit of the CRC: ...
Mark Adler's user avatar
1 vote
Accepted

using 2 short CRC(s) VS one longer CRC

Ok, i found what i was searching in a paper "Selection of Cyclic Redundancy Code and Checksum Algorithms to Ensure Critical Data Integrity" https://www.faa.gov/aircraft/air_cert/design_approvals/...
Duccio Bertieri's user avatar
1 vote
Accepted

How to understand the CRC Algorithm from the CAN specification?

CRC(x) is remainder of polynomial division of x by some fixed polynomial. Here bits of x, as well as bits of result, represents ...
Bulat's user avatar
  • 1,898
1 vote

What is the error-detection-probability of CRC

There's nothing in your requirements that forces you to use a CRC32. You could use any checksum. If the collision probability for a CRC32seems too high, use a different checksum. For instance, if ...
D.W.'s user avatar
  • 162k
1 vote

Polynomial generator required to detect single bit error in Cyclic Redundancy Check codes

You just need to concentrate on the polynomial division here. First consider the case where we need to detect one - bit error . For this case $ e(x) = x^k $ we can choose any polynomial with terms >...
Shubham Singh rawat's user avatar
1 vote
Accepted

Cyclic Redundancy Check Codewords Finding the Original Message

You should do arithmetic modulo 2. Modulo 2, $-1$ is the same as $+1$.
Yuval Filmus's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible