Correcting two-bit error using a CRC

Question

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.

Answer 1

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.