The Gateway to Computer Science Excellence
+22 votes
3k views

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?

  1. $14$
  2. $16$
  3. $18$
  4. $20$
in Computer Networks by Boss (16.3k points)
edited by | 3k views
0
Someone plz explain this
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 =25 = 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

5 Answers

+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$

by Loyal (7.8k points)
edited by
+1
I didn't get why first two bits and last two bits should not have consecutive zero's
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
There should be one more condition

11x01

11x10

So total 4

 

32-14-4=14
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

by Active (2k points)
+6 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 

by (399 points)
+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. 

by Boss (13.3k points)
0 votes
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.
by Junior (729 points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,648 questions
56,422 answers
195,194 comments
99,823 users