328 views
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 _________.
| 328 views
0
is it 16
0
hmm, getting 16. But took more than 10 minutes to solve yet not sure :(
0
Any of you provide the solution ?
0
answer is 16 but process is very long. is there any short cut?
0
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
0

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

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

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

0

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

+1
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.
0
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;

as what we can se that

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

hope u all got it; correct me if i am wrong
+1
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.

+1 vote

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

by Active (3.4k points)
selected by