537 views
1 votes
1 votes

In the 4B/5B encoding scheme, every 4 bits of data are encoded in a 5-bit codeword. It is required that the codewords have at most 1 leading and at most 1 trailing zero. How many such codewords are possible?

Explain the thing in bold .
(Don't close  it, I know it is previous year gate question but I don't understand the question)

1 Answer

1 votes
1 votes

At most one leading and trailing 0 means that the number of zeroes in the beginning or the end of the string should be less than or equal to one. This is better understood with the help of an example.

01xx1 is a string of length 5 with one leading 0 and no trailing 0

1xx10 is a string of length 5 with no leading 0 but with one trailing 0

01x10 is a string of length 5  with one leading 0 and with one trailing 0

1xxx1 is a string of length 5 with neither a leading 0 nor a trailing 0

Here x indicates that the value can be either 0 or 1.

All cases other than those of the type above will be not be included in the 5 bit codeword.

Let's see such an example:

00110 here we have 2 leading 0's therefore this cannot be included in the codeword.

similarly in 11100 we have two trailing zeroes hence this cannot be included in the 5 bit codeword.

The actual answer of the question will be :

01xx1: We'll have 2 x 2=4 strings of this type

1xx10: We'll have 2 x 2=4 strings of this type

01x10: We'll have 2 strings of this type

1xxx1: We'll have 2 x 2 x 2=8 strings of this type

Therefore total no. of 5 bit codewords possible=4+4+2+8=18

Hope this clears your doubt

Related questions

0 votes
0 votes
1 answer
1
hem chandra joshi asked Oct 2, 2017
375 views
Consider the following first order logic formula in which R is a binary relation symbol.∀x∀y (R(x, y) = R(y, x))Only need to describe the question.@bikram sir.
2 votes
2 votes
0 answers
4
hem chandra joshi asked Jan 2, 2018
327 views
Let m[0]....m[4] be mutexes (binary semaphores) and P[0].......P[4] be processes. Suppose each process P[i] executes the following:wait (m[i]; wait (m(i+1) mode 4]); .......