edited by
9,948 views
35 votes
35 votes

In the $\text{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?

  1. $14$
  2. $16$
  3. $18$
  4. $20$
edited by

6 Answers

Best answer
64 votes
64 votes

The answer is (C)

It says we have a $\textbf{5-bit}$ codeword such that "it can't have two consecutive zeros.
In a first and second bit" and also" can't have two consecutive zeros in the 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$

edited by
43 votes
43 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

8 votes
8 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. 

5 votes
5 votes

Total possible codewords - 32 (25)

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 

Answer:

Related questions

53 votes
53 votes
5 answers
2