I couldn't figure out how to answer the following question: Suppose we want to transmit a string of 3 ASCII characters, and in order to be able to detect or correct the message, we append the sum of the chars at the end of the binary string. e.g.:

encode("abc") == `110000111000101100011100100110`

what is the distance of such code? what is the distance of the same code with an additional parity check bit at the end?

all I could figure out so far is that the code is in the form of (30,21,d) and if one bit flips, it's of course detectable, thus 'd' is at least 2, and we cannot correct errors. But when two bits flip (or more), I can't grasp it. It seems to me like the parity check version doesn't do a lot, and I'm not quite sure how can I make a case (if any) to maximize 'd'.

I understand the classic (7,4,3) examples, but this one had me all confused due to the number of possible strings. How should I approach it?

  • $\begingroup$ Try solving this for an alphabet of size 1, then an alphabet of size 2, then 4, and so on. $\endgroup$ – Yuval Filmus Feb 4 '18 at 22:00
  • $\begingroup$ @YuvalFilmus I assume the key for solving this is to reduce to the case where two legal messages (strings) differ in 1 bit (consecutive strings like "ddd" and "dde", I could have worked with the first ASCII values for even more simplicity), so the sum also differ in 1 bit and that is a sufficient example that d=2. As for the parity bit version, there should be two legal strings with distance 2 between them - but with an even number of 1's, right?. So d=2 for this version as well. Am I correct? If so, was that the best way to answer that? $\endgroup$ – gbi1977 Feb 5 '18 at 21:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.