GATE2006-IT-65

4.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$

edited
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

8

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

3

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

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$

edited
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
3

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)

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

0
nice exp....... thanks...
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.

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

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

Related questions

1
4k views
A subnetted Class $B$ network has the following broadcast address: $144.16.95.255$ Its subnet mask is necessarily $255.255.224.0$ is necessarily $255.255.240.0$ is necessarily $255.255.248.0$ could be any one of $255.255.224.0$, $255.255.240.0$,$255.255.248.0$
A program on machine $X$ attempts to open a $UDP$ connection to port $5376$ on a machine $Y$, and a $TCP$ connection to port $8632$ on machine $Z$. However, there are no applications listening at the corresponding ports on $Y$ and $Z$. An $ICMP$ Port Unreachable error will be generated by $Y$ but not $Z$ $Z$ but not $Y$ Neither $Y$ nor $Z$ Both $Y$ and $Z$
On a wireless link, the probability of packet error is $0.2$. A stop-and-wait protocol is used to transfer data across the link. The channel condition is assumed to be independent of transmission to transmission. What is the average number of transmission attempts required to transfer $100$ packets? $100$ $125$ $150$ $200$
A link of capacity $100$ $\text{Mbps}$ is carrying traffic from a number of sources. Each source generates an on-off traffic stream; when the source is on, the rate of traffic is $10$ $\text{Mbps}$, and when the source is off, the rate of traffic is zero. The duty cycle, which is the ratio of ... , $10$ $\text{and}$ $30$ $12$ $\text{and}$ $25$ $5$ $\text{and}$ $33$ $15$ $\text{and}$ $22$