The Gateway to Computer Science Excellence

0 votes

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 _________.

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

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

0

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.

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;

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

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

+1 vote

Best answer

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

0 votes

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.

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.3k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.1k
- Non GATE 1.5k
- Others 1.5k
- Admissions 595
- Exam Queries 576
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 17

50,645 questions

56,601 answers

195,854 comments

102,227 users