5
$\begingroup$

What algorithm can be used to correct a two-bit error in a message protected by a 32-bit CRC, assuming the CRC polynomial allows that? I'm seeking something for 480-bit payload, able to detect uncorrectable errors, fast in the worst case, and compact.

Because I have hardware support for that, I'm most interested in the CRC-32 IEEE 802.3 primitive polynomial (allowing two-bit error correction for payloads up to 2974 bits), $$x^{32}+x^{26}+x^{23}+x^{22}+x^{16}+x^{12}+x^{11}+x^{10}+x^8+x^7+x^5+x^4+x^2+x+1$$ but the question is of theoretical interest for others, such as the CRC-32K polynomial proposed by Koopman (allowing two-bit error correction for payloads up to 16360 bits) $$(x+1)(x^3+x^2+1)(x^{28}+x^{22}+x^{20}+x^{19}+x^{16}+x^{14}+x^{12}+x^9+x^8+x^6+1)$$


Assume payload data of $b$ bits (assimilated to the coefficients of a binary polynomial $B(x)$ of degree less than $b$), to which is appended a CRC computed with binary polynomial $P(x)$ of degree $c=32$, as $C(x)=(B(x)\;x^c)\bmod P(x)$. It is then stored in memory $b+c$ bits of $B(x)\;x^c+C(x)$. On reading is it computed the syndrome $S(x)=(B'(x)\;x^c+C'(x))\bmod P(x)$. Assuming there has been at most two bits in error, and $b$ is small enough:

  • If $S(x)=0$, then there has been no error.
  • Otherwise, if there exists $i$ with $0\le i<b+c$ such that $S(x)=x^i\bmod P(x)$, then there has been a single error, and $i$ tells where, allowing correction.
  • Otherwise, there has been two errors and there exists $i$ and $j$ with $0\le i<j<b+c$ such that $S(x)=(x^j+x^i)\bmod P(x)$; again finding $(i,j)$ allows correction.

The case of a single bit in error is relatively easy; that's a discrete logarithm problem, with an easy size versus speed compromise: we can have a precomputed table allowing solving in a single lookup for $i$ multiple of $k$, and use that $k$ times. But I'm stuck with the case of two bits where I have nothing much better than trying all $j$ and doing as for a single bit in error.

$\endgroup$
5
$\begingroup$

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

The running time is proportional to the maximum length of the message. I'd imagine that in a real deployment, two-bit errors will be rare enough that this running time is affordable. (If two-bit errors are common, then three-bit errors will have non-negligible probability, which is a problem of its own.)

If you want to reduce space complexity, instead of storing the entire precomputed table and looking up $S-T_i$ in the table, compute the discrete log of $S-T_i$ for each $i$ using whatever method you prefer (such as the one you listed in your question).

I don't know if there are smarter methods that exploit the structure of $\mathbb{F}_2^{32}$ in a more intelligent manner.

$\endgroup$
  • $\begingroup$ Your answer tells me there's no well-known trick beating "running time is proportional to the maximum length of the message". My application would have $b+c=512$ or so, thus large errors would be missed with odds about $2^{-15}$, and I can live with that; but I need fast worst-case response, and can't use large precomputed tables in that sub-\$ embedded CPU. $\endgroup$ – fgrieu Apr 3 '16 at 9:07

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.