GATE IT 2006 | Question: 65

Question

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?

• A. $14$
• B. $16$
• C. $18$
• D. $20$

Comments

$0$    $1$    $0/1$    $1$    $0$   $=2\ ways$

$0$    $1$    $0/1$    $0/1$    $1$ $=4\ ways$

$1$    $0/1$    $0/1$    $1$    $0$ $=4\ ways$

$1$    $0/1$    $0/1$    $0/1$    $1$ $=8\ ways$

$Total = 18\ ways$

---

 

23. gate 2006 question on 4B/5B scheme - YouTube

https://www.youtube.com › watch

 

---

This question is talking about 4B/5b encoding , now in this encoding we cant have leading more than 1 zero and trailing more than two zero , which is different from the question given, also we cant have continuous three zeroes in 4b/5b encoding but here it is considering it. why??

Answer 1

there are 4 possible ways.

01 _ 10 we will have 2 ways.(2 ways for each blank)

01 _ _ 1  we will have 4 ways

1 _ _ 10  we will have 4 ways

1_ _ _ 1  we will have 8 ways

so total 18.

Answer 2

8 Encoding of  1 x 2 x 2 x 2 x 1 (numbers here represent the possible ways we can fil each place ).

4 Encoding of  1 x 2 x 2 x 1 x 0 (last is filled with zero so 2nd last has got 1 choice only)

4 Encoding of  0 x 2 x 2 x 1 x 1 (first is filled with zero so 2nd  has got 1 choice only)

2 Encoding of  0 x 1 x 2 x 1 x 0 (first and last has 0 in that case we will have 2 options only 01110 and 01010).

 

8+4+4+2 = 18 hence the answer.

Another naive way is to write all 32 numbers then job is easy just remove the ones which has more than 1 trailling and leading zeroes..that would give 18 possible strings..