# WBUT Question Papers EC

## Coding And Information Theory B Tech Sixth Sem 2011-12

Time Allotted : 3 Hours

Full Marks : 70

The figures in the margin indicatefu.ll marks.

Candidates are required to give their answers in their own words

as far as practicable.

GROUP – A ( Multiple Choice Type Questions )

1. Choose the correct alternatives for any ten of the following :

10 x 1 = 10

– i) A ( 7, 4 ) linear block code has a code rate of a) 7

b) 4

c) 1-75                                d) 0-571.

P

ii) Entropy represents

a)             amount of information

b)            rate of information

c)             measure of uncertainty

d)            probability of message.

iii)        The channel capacity is a measure of

a)           entropy rate

b)           maximum rate of information a channel can handle

c)           information contents of messages transmitted m a channel

■                                                          ■                                                                                                     4

d)          none of these.

 iv) The Hamming distance between V = 1100001011 and W = 1001101001 is

v)           An encoder for a ( 4, 3, 5 ) convolution code has a memory order of

b)           2 d) 5.

CS/B.TECH(ECE)’/SEM-7/EC-703/2011-12

vi)         Which of the following expressions is incorrect ?

a)           H ( y/x) – H { x, y ) – H { x)

b)           I(x,y) = H(x)-H{y/x)

c)           II ( x/ y )= H { x, y ) + H { y )

d)          I { x. y ) = H [ y ) – II { y/x ).

vii)       A polynomial is called monic if

a)           odd terms are unity

b)           even terms are unity

% ‘ . ,

viii)     Which of the following techniques is used for Viterbi algorithm for decoding ?

a)     Code tree  t>) Trellis

c)  State diagram  d) Parity generator.

ix)           The generator polynomial of a cyclic code is a factor of

b) x n + 1 +

received vector r = ( 001110 ). Then the syndrome is given by

 a) (110) c) (111)
 b) ( 100 ) d) ( 101 ).

xi)         For a ( 7, 4 ) cyclic code generated by

g { X) = 1 + X + X 3 the syndrome for the error pattern e [ X) =fX 3 is

a)           101

d)          Oil.

xii)       The number of undetectable errors for a ( ri, k ) linear code is

 a) 2 n ~k c) 2 n– 2 k
 b) 2n d) 2k.

GROUP -B ( Short Answer Type Questions )

Answer any three of the following. 3×5= 15

1. a) Differentiate between block cipher and stream cipher. 2
2. b) What do you mean by symmetric key and asymmetric
3. key cryptography ? What is ‘Man-in-the middle’ attack ?
1. A ( 8, 4 ) cyclic code is generated by g ( X ) = 1 + X + X 4. Find the generator and parity-check matrix in systematic form.       3 + 2
2. a) What is the systematic structure of a code word ?

b)  What is syndrome and what is its significance ? Draw

the syndrome circuit for a ( 7, 4 ) linear block code with

10 0 10 11 0 10 1110 0 0 10 111

1. For a ( 2, 1, 3 ) convolutional encoder the generator sequences are g 0 = ( 1000 ) and g = ( 1101 ).
2. Determine the generator polynomial of a double error correcting BCM code of block length, n = 15.

GROUP -C { Long Answer Type Questions )

Answer any three of the following. 3 x 15- 45

1. Consider a systematic ( 8, 4 } code with parity check equations

v0 = u0 + ul + u 2 vl = ul + u2 + u3

2 = U o + U j + U 3

v 3 = U 0 + U 2 + U 3

where U 0 , U x , U 2 and U 3 are message, V Q , V 1 , V 2 and

V  o are parity check digit

i)             Find the generator matrix and the parity check matrix for this code.

ii)          Find the minimum weight for this code.

iii)    Find the error detecting and the error correcting

capability of this code.

iv)         Show through an example that the code can detect three errors in code word.                                                6 + 4 + 4 + 1

1. a) State and prove the Shannon-Hartley law of channel capacity,                                                                                   1+5

b)           A Gaussian channel has a 1 MHz bandwidth. 11 the signal power-to-noise power spectral density

| = 10 5 Hz, calculate the channel capacity C and the maximum information transfer rate.                                                 5

c) Show that H ( X, Y) .= H t XJ Y) + H ( Y).                           4

1. a) Show that C = { OOOO, 1100, 0011, 1111 } is a linear code. What is its minimum distance ?                                 4+1

b)          A ( 7, 3 ) linear code has the following generator matrix : G =

Determine a systematic form of G. Hence find the parity-check matrix H for the code.                                                 3 + 2

c)  Design the encoder circuit for the above code.                                            5

1. a) Write down the advantages of Huffman coding over

Shannon-Fano coding.

b)          A discrete memoryless source has seven symbols x i, x 2, x 3, x 4, x 5, x 6 and x 7 with probabilities of

occurrence P(x }) = 0 05, P(x2) = 015, P(x3) = 0-2, P(x4) = 0-05, P ( x 5 ) = 0* 15, P ( x 6 ) = 0-3 and P(xy) = 01.

Construct the Huffman code and determine

i)            Entropy

ii)          Average code length

iii)         Code efficiency.                               3 + 5 + S + 3+ 1

1. a) What are the functions of P~box and S-box in case of

DES algorithm ?

b)           Explain the Diffy-Heilman key exchange algorithm.

c)   What do you mean by Quantum Glyptography ? 4 + 9 + 2

12. Write short notes on any three of the following :

a)                  Shannon-Fano algorithm