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?

  • $\begingroup$ Can you make your error model more precise? What guarantee should your code have? $\endgroup$ – Yuval Filmus Sep 5 at 11:51
  • $\begingroup$ @YuvalFilmus I added a bit more detail, although I'm not sure how much error checking I can expect $\endgroup$ – Cephalopod Sep 5 at 20:16
  • 1
    $\begingroup$ 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. $\endgroup$ – greybeard Sep 5 at 21:03
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Sep 5 at 21:07
  • 1
    $\begingroup$ The fact that the numbers just agree leads me to wonder where this question came from. $\endgroup$ – Yuval Filmus Sep 5 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$.


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.