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

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.