debugMinor
Correcting two-bit error using a CRC
Viewed 0 times
errorbitcrccorrectingtwousing
Problem
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:
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.
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
- Otherwise, there has been two errors and there exists $i$ and $j$ with $0\le i<j
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.
Solution
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.
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.
Context
StackExchange Computer Science Q#55353, answer score: 4
Revisions (0)
No revisions yet.