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.