# Which algorithm to detect errors in 32bit data with 8bit parity

I want to transmit a 32bit message in eight groups of 5bit each. This leaves me with 8bits to use for error checking.

Overall, a group is likely transmitted without error, but when there is an error transmitting a group, there are probably multiple bits wrong.

If I use one parity bit per group, I have a 50% chance to detect a wrong group. But I don't need to know which group of a message is wrong, I want to check the entire message.

I want 100% chance of detecting if one group of the message is incorrect, regardless of how many bits are flipped in that group. If possible, I also want to be able to check wheather two neighboring groups have been switched.

Which algorithm should I use for error checking / How should I code the data?

• Can you make your error model more precise? What guarantee should your code have? – Yuval Filmus Sep 5 '19 at 11:51
• @YuvalFilmus I added a bit more detail, although I'm not sure how much error checking I can expect – Cephalopod Sep 5 '19 at 20:16
• I'd look for a code, not an algorithm. But for two neighboring groups have been switched, this looks like the standard case for a block code. Two groups switched can be viewed as a burst error of twice the length of a group (eight or ten bits, depending how you look at it) - $n$-bit burst error-correcting code with $n$ check bits doesn't look promising. – greybeard Sep 5 '19 at 21:03
• Given the errors you're interested in, it might be better to think of your message as 8 symbols from an alphabet of size 32. It is a pity that 5 doesn't divide 32 – otherwise you could have used a linear code over a field of size 32. – Yuval Filmus Sep 5 '19 at 21:07
• The fact that the numbers just agree leads me to wonder where this question came from. – Yuval Filmus Sep 5 '19 at 21:12

Think of your message as seven 5-bit numbers $$x_2,\ldots,x_8 \in \{0,\ldots,30\}$$. This gives you $$7\log_2 31 \approx 34.68$$ message bits. Calculate $$x_1 = -\sum_{i=2}^8 ix_i \bmod{31}$$, so that $$\sum_{i=1}^8 ix_i \equiv 0 \pmod{31}.$$
It is easy to check that every single symbol error is detected, since $$31$$ is prime.
Now suppose that $$x_i$$ and $$x_j$$ are switched, but the equation above still holds. Then $$ix_i + jx_j \equiv ix_j + jx_i$$, and so $$(i-j)(x_i - x_j) \equiv 0$$, implying that either $$i = j$$ or $$x_i = x_j$$.