GATE-ECE-2018

Question

Consider a binary channel code in which each codeword has a fixed length of 5 bits. The Hamming distance between any pair of distinct codewords in this code is at least 2. The maximum number of codewords such a code can contain is _________.

Comments

is it 16

---

hmm, getting 16. But took more than 10 minutes to solve yet not sure :(

---

Any of you provide the solution ?

---

answer is 16 but process is very long. is there any short cut?

---

code word is of 5 bits so total pairs possible 2^5 = 32 ....

now we want min. distance of 2 and they want max code words just divide 32 /2=16

---

So Deepanshu if they are asking for min hamming dist 5, by your logic it would be 32/5 correct?

---

yess i think just add upper bound .......

---

Can you tell all the codewords for min hamming distance 5??Deepanshu

---

Utkarsh Joshi

lets we discuss about smaller ones .......i create above method by unconventional methods okk lets see.....

take code of length 3 .....means 000,001 etc  means 3 length code

 now see hamming distance of 1------

hamming distance of 2 ------ i get only 4 as 000,011,101,110   8/2

hamming distance of 3 -------- i get like only 2 000,111....... it is 8/3 lowe bound  i cant create any code more from this code starting ...

so i create above method by my own........but now i think it is lower bound ....

 

maybe i am wrong  and i didnt read this formula anywhere .... i just create it on spot ....but this is best we can do in these questions ....

see code length 2 ...then hamming distance of 2 i.e.00,11 so it is 4/2

code length 1 we get 4/1 and codes are 00,01,10,11

---

We have to consider gray codes of length 5 bits which differ by only 1 bit.

For eg:

00000
00001
00011
00010
00110
00111
00101
00100

and so on.

Now selecting every alternate code from the gray code will provide us the codewords which are 2 bits apart.

For eg :

00000
00011
00110
00101
and so on.

---

what i thought was

 their are 5 bits total theirfore total 32 codewords.

case 1:now lets consider 00000 is a codeword then any 5 bit number with 4 zeros and 1 one will not be a codeword.

case 2:next we consider codeword with 3 zero and 2 one then these codeword have minimum hamming distance of 2 with 00000 total such combination are 5c2=10;

case 3: next we cosider code word with 2 zero and 3 one these will not be codeword as they have only one hamming distance with case 2;

case 4 :one zero and 4 one this will 2 hamming distance with case 2 and 4 hamming distance with case 1; total combination are 5c4=5;

11111 cannot be codeword with same reason as of case 3;

 

 i started with 00000 one can start with 11111

as what we can se that

5c0+5c2+5c4=5c5+5c3+5c1

hope u all got it; correct me if i am wrong

---

Yes, @sayan that's how I also tried.

@deepanshu For 5 bit codes, only 2 codes can have hamming distance 5 - 00000 and 11111

32/5 is not 2.

Answer 1

for any code C(n,k,d), d <= n-k+1

      where, d=minimum hamming distance.

                  k=dataword length

                 n=codeword length

d=2,n=5  =>  2<=5-k+1

solving it, k=4

so, maximum number of codewords possible is $2^{4}$=16.

note: this equation, i've written above is singleton bound equation. i don't think it's important or is even in our syllabus. nevertheless, if you want, you can refer here. https://www.cse.iitm.ac.in/~jayalal/teaching/CS6845/2012/lecture-B04.pdf

Answer 2

Consider 5 bit grey code where each consecutive code word differs by one bit.Considering this code , we have to choose maximum number of codes among these 32 codes ,such that no two are consecutive, hence if we choose 17 or greater number of codewords ,atleast two words are consecutive. So we can choose 16 codewords leaving one space between each of them.