The Gateway to Computer Science Excellence

+22 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 are such codewords possible?

- $14$
- $16$
- $18$
- $20$

0

this is simple probability problem with permutation and combination,

the first 2 bit positions are occupied by 0 as defined by the condition & each leading x represents two possibilities for either replacement by by 0 or 1. therefore computing to x * x * x = 2^3 = 8 possibilities for the first case,

Similarly 2 raise to power 3 equal to 8 in second case also and 2 in the third case.

We know the formula the code word with the first OR last two bits 0 = code words with first 2 bits 0 + code words with the last 2 bits 0 - code words with first AND last 2 bits 0

and finally then subtracting from total 5 bit codewords over binary bits. i.e. 2^5 =32

we get, 32-14 =18 remaining possible codewords

+5

Total possible combinations with 5 bits =2^{5 }= 32

We will solve this with inclusion and exclusion,

Let A be the set of bits with two consecutive 00 at the beginning

B be the set of bits with two consecutive 00 at the end

for A,

**00xxx**

Hence total possible combinations **8** (2 x 2 x 2)

for B,

**xxx00**

Hence total possible combinations **8** (2 x 2 x 2)

for A$\cap$B

**00x00**

only 2 combinations are possible hence,

A$\cup$B = 8 + 8 - 2 = 14 //we have count of combinations which are not allowed

Total possible codewords = 32 - 14 = **18**

+41 votes

Best answer

**Answer is (C)**

It says we have **5 bit **codeword such that "it can't have two consecutive zeros

in first and second bit" and also" can't have two consecutive zeros in last two bits.

Code word with first two bits zero** **$= 0|0|x|x|x| =8$

Code word with last two bits zero** **$= |x|x|x|0|0| =8$

Code word with first and last two bits zero $= 0|0|x|0|0|=2$

Code word with first OR last two bits zero** **$=8+8-2=14$

Therefore possible codewords** **$=32-14 =18$

0

Does atmost 1 leading and atmost 1 trailing zero mean that if there is a 0, then there can be atmost one zero following it and also the trailing zero should have atmost one 0 leading it??

0

The format is like

$\text{Y | X | Y}$

where, the condition is given as **at most 1 trailing AND at most 1 leading. **

which means, for each $Y$, we have only $3$ choices out of $4$ i.e. $\{ 01, 10, 11\}$**, **since $00$ is not allowed because it will be two leading/trailing zeros which is invalid.

for $X$ we have two choices $\{0,1\}$.

Hence, total number of possibilities $ = 3 \times 2 \times 3 = 18$

Thus, **option (C)**

+30 votes

The codeword is of 5 bits with the condition that there should be at most 1 leading and at most 1 trailing zero. So we can either have

- no Zero in the MSB and LSB
- 1 Zero in either MSB or LSB or both

The first case will look like: **1 _ _ _ 1** ( Since we cannot have 0 in MSB and LSB).

The second case will look like: **0 _ _ _ 1** *(one 0 in MSB)*, **1 _ _ _ 0** *(One 0 in LSB)*, **0 _ _ _ 0** *(Both MSB and LSB is 0)*.

Let me the number the position of bits as 0 through 4 from LSB to MSB.

In the first case, the remaining 3 positions in **1 _ _ _ 1** can be filled in 2 ways each, i.e., each position can be either 0 or 1. So total no of such codes = 2x2x2=**8 codewords**.

In the second case:

in **0 _ _ _ 1, **3rd position bit can be filled with 1 only and not 0 because if the 3rd bit gets 0 then we will end up having two leading 0s in 4th and 3rd position. However, 2nd and 1st bit can be filled with 1 or 0 each. So for 3rd position, we have 1 choice, for 2nd and 1st position we have 2 choices each. So total no. of such codes=1x2x2=**4 codewords.**

Similarly, in **1 _ _ _ 0, **the 1st position can be filled with 1 only because if the 1st position gets 0 then we will end up having two trailing zeroes in 1st and 0th position.Now the 2nd and 3rd position can be filled in two ways each, i,e, with 0 or 1. So total no of such codes=2x2x1=**4 codewords**.

On similar grounds, in the case of **0 _ _ _ 0, **the 1st and 3rd position bits can be only 1 and not 0 to avoid having two leading and trailing zeroes. But the 2nd position can be 0 or 1, so 2 choices. Total no of such codes=1x2x1=**2 codewords**.

Total possible codewords=8+4+4+2=**18 codewords** => **Option C**

+6 votes

Total possible codewords - 32 (2^{5})

we don't have restriction for starting with 1, so 16 possibilities

but we should have at most 1 zero at both extremes, which means **0_ _ _ 0, **condition also** **forces it neighbors to be 1,** **

**so 0 1 _ 1 0, **in the blank space, we could either fill with** 0 or 1,** so here we have **two more possible codewords** along with **16**

**16 + 2 = 18 **

+5 votes

Brute force method. 0 00000 1 00001 2 00010 3 00011 4 00100 5 00101 6 00110 7 00111 8 01000 9 01001 10 01010 11 01011 12 01100 13 01101 14 01110 15 01111 16 10000 17 10001 18 10010 19 10011 20 10100 21 10101 22 10110 23 10111 24 11000 25 11001 26 11010 27 11011 28 11100 29 11101 30 11110 31 11111

Only 18 are valid answer is (C) Part.

- 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,648 questions

56,422 answers

195,194 comments

99,823 users