# Finding the overhead and distance of an unknown code based on message making algorithm

for an information word M with m bits that is coded as following:

• M is coded into a word A using an unknown code that allows detection of not more than one error.
• the code word is the word obtained by a concatenation of A to itself. so A becomes AA and etc..

1)is it possible to know the overhead in the given code?

2)is it possible to know the distance of the code?

my attempt:

after thinking on it again and rereading the text, i began to realize(hopefully i am right now) that the question is about parity bit and not hamming. so if it can detect not more than one error, there's a parity bit, i think. based on that thought i tried to solve it:

1)I began to realize it's not about hamming code. if we can only detect not more than one error, then it's about the parity bit. so i think that if we add a bit to each byte of message, then the overhead will be 9 bytes total. so it can be calculated, i think.

2)since this sub problem is about the concatenation of A to itself, then like @YuvalFilmus said, the minimal distance should be twice now.

thank you very much

• Not sure about "detection of not more than one error" -- did you mean "correction"? Apr 7, 2019 at 13:58
• actually no, it says detection of up to one error. doesn't talk about the correction. i thought it's about hamming because of this detail Apr 7, 2019 at 15:29
• A parity bit would suffice then. Apr 7, 2019 at 15:36
• the problem is that none of these details are given. because it allows detection of not more than one bit, maybe they mean CRC and not hamming? i am really unsure and i don't know how to calculate the overhead or distance with the given details. is there a trick here? Apr 7, 2019 at 15:41
• @oldfart what information is missing in order to calculate or obtain the overhead? Apr 8, 2019 at 9:50

The question is still pretty unclear, but I will provide a few hints and hope that they point you in the right direction.

The only code I'm aware of that can detect only one error and do nothing else is the repetition code $$\R_2\$$. This code takes a data bit $$\b\$$ and produces the codeword $$\bb\$$.

(Note that adding a parity bit can do more than detecting one error; it can detect any odd number of errors).

Now, by producing a code word that is a concatenation of $$\A\$$ with itself, all you're doing is using the same $$\R_2\$$ code again.

In summary, the mistery code is $$\R_2\$$, and the second code (which duplicates the word $$\A\$$) is just $$\R_2\$$ again.

The concatenation of two $$\R_2\$$ codes is equivalent to an $$\R_4\$$, where each bit is repeated four times; in other words, if the input is $$\b\$$, the output is $$\bbbb\$$. This code has distance $$\4\$$, can correct one error, and it can detect up to three errors.

Its code rate is $$\1/4\$$; it transmits four code bits per every data bit. The overhead then is $$\3/4\$$, or $$\75\%\$$.

• this is not "school work", and i am stuck on it too much time without no idea how to solve it, so the most beneficial thing is just to learn how to correctly solve it and learn from my mistakes so i can better apply it for the next problems i will encounter. i don't have any clue on how to calculate the overhead in such conditions Apr 11, 2019 at 17:00
• @hps13 I've provided more details in my answer.
– MBaz
Apr 11, 2019 at 21:41
• thank you very much. i am trying to find more resources to learn this subject better and more throughly and then reread your answer. do you happen to know any good place to do so? and thank you again for explaining, it helps me a lot to learn from your explanations and the way you approach and solve it Apr 14, 2019 at 17:38
• @hps13 You're very welcome. I'd recommend reading the first two or three chapters of David MacKay's "Information Theory, Inference, and Learning Algorithms" -- it's available online for free from the author.
– MBaz
Apr 14, 2019 at 18:48