# Tag Info

Accepted

• 162k
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$ ...
• 162k
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 ...
• 168

### 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 ...
• 20.7k

### 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 ...
• 190
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 ...
• 162k

### 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.$$
• 278k

### 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 ...
• 364
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$, ...
• 278k
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 ...
• 30.6k

### 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 ...
• 1,435

### 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 "...
• 627

### 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 ....
• 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 ...
• 168
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/...
• 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)$ ...
• 278k
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: ...
• 168
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/...
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 ...
• 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 ...
• 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 >...
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$.
• 278k

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