# 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"? – Dave Tweed Apr 7 '19 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 – hps13 Apr 7 '19 at 15:29
• A parity bit would suffice then. – Oldfart Apr 7 '19 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? – hps13 Apr 7 '19 at 15:41
• @oldfart what information is missing in order to calculate or obtain the overhead? – hps13 Apr 8 '19 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 – hps13 Apr 11 '19 at 17:00
• @hps13 I've provided more details in my answer. – MBaz Apr 11 '19 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 – hps13 Apr 14 '19 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 '19 at 18:48