Hot answers tagged

6

The CRC polynomial is very probably primitive, that is the order of $X$ modulo $G$ is $2^{32}-1$. In other words, $X$ is a generator of $GF(2^{32})^\times$. So using inputs $0,2^0,\ldots,2^{2^{32}-2}$ will result in all possible $2^{32}$ values. CRCs are hopefully always chosen with primitive polynomials, so this result is general. Even if the polynomial is ...


5

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$ such that $S = T_i + T_j$. This can be found by enumerating all $i$, and for each $i$, computing $S-T_i$ and checking whether it is present in the precomputed ...


3

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^{2^n-1} \equiv 1 \pmod{P(x)}$ (using repeated squaring to do this efficiently), and that for every prime factor $p$ of $2^n-1$, $x^{(2^n-1)/p} \not\equiv 1 \pmod{...


3

CRC is conceived as the remainder of a polynomial division. It is efficient for detecting errors, when the calculated remainder does not match. Depending on the CRC size, it can detect bursts of errors (10 bits zeroed, for example), which is great for checking communications. The "FCS" term is used sometimes for some transformed version of the CRC (Ethernet ...


2

Both CRC and the Hamming code are binary linear codes. One significant difference is that the Hamming code only works on data of some fixed size (depending on the Hamming code used), whereas CRC is a convolutional code which works for data of any size. So, are CRC and the Hamming code fundamentally different ideas? This is a philosophical rather than a ...


2

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 to deocde correctly the prefix of the message than it's suffix.


2

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 different parts of your data. In your temperature digits example, you might consider an encoding with $d=5$ Hamming distance for integer part and $d=3$ for ...


2

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 assume the problem is as follows: Given a CRC polynomial $p(x)$, determine whether there exists a $d$-bit error pattern of length $n$ that isn't detected. This is ...


2

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 $c_0,\dots,c_n$ can be viewed as the value of $c(x) \bmod p(x)$, where $p(x)$ is the CRC polynomial and $c(x) = c_n x^n + \dots + c_0$ and all arithmetic is ...


2

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. $$


1

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/air_software/media/TC-14-49.pdf in Section 5.7 we can read that: "[...] Based on the results of this study and a literature review, there is no evidence that ...


1

CRC(x) is remainder of polynomial division of x by some fixed polynomial. Here bits of x, as well as bits of result, represents polynomial with binary coefficients, f.e. 0b101 may represent polynomial 1*x^2 + 0*x + 1. So, the algorithm you have cited, is the most straightforward one - if q(x) = p(x) mod f(x), then p(x)*x mod f(x) is either just q(x)*x (if ...


1

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 you use SHA256, you will never have to worry about collisions -- for all engineering purposes, you can treat them as impossible (something that will never happen ...


1

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 >=2 , since it will not divide the error polynomial completely . Next let us see the case of odd number of errors. Notice how this is different from one bit ...


1

You should do arithmetic modulo 2. Modulo 2, $-1$ is the same as $+1$.


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