Uttar Pradesh Technical University (UPTU) 2009-7th Sem B.Tech Information Technology - ester- Data Compression - Question Paper

B.Tech
(VII semester) odd semester theory exam
Data Compression

;e) Discuss two probability models commonly used in design and analysis of lossv compression system ('I Wh.il is Rice eode ¹ i low ii is different liom liolomb eode

4 'Nik'nipt ;in\ <ivo of tlie folloumu    10'22H

l.t) What do you iimler stand In uniform quami/er Mow uniform quantization of a uniformly distributed source and uniform quantization of non uniform sources is done ⁷

fb) Discuss the steps involved in Basic algorithm for Prediction with Partial Match (PPM).

(c) Describe tree structured vector quantizers.

Attempt any two of the following :    10x2=20

(a)    Discuss the Linde-Buze-Gray algorithm in detail.

(b)    what is quantization ⁰ Explain additive noise , model of a quantizer. Differentiate between scalar quantization and vector quantization.

Discuss the advantages of vector quantization over scalar quantization.

(c)    What do you understand by predictive coding ? Discuss multi resolution approaches.

(Following Paper ID ;ind Roll V>. to he filled m vour -Vn*wer Bonkl Roll No.___ ___ _ " _

H. l och

(SKM Ml) 01)11 SKMKSHIK l'HKOK't KWMIWHON n vi'v antm ssiON

iuih Hours I    I iota! \laik<. 100

Note : (/) Attempt all cfiiest/ons.

(it) All questions curry cc/rtul marks.

(iii)    Assume data wherever nut provided.

(iv)    Be precise in your answer.

v

A¹ tempt any four of the following :    5x4=20

(a) Explain compression and reconstruction with the help of block diagram (I t Determine whether the following codes are uniquely decodable :

(I) {0, 10, 110, 111}

(ii) (1, 10, 110, 111}

ft.) Given an alphabet = a₂. a₃, a₍₁| find the first order entropy in the following cases :

(i)    P(a_x) = P(a₂) = P(a₃) = P(a_x) = ~

(ii)    P(a,) = i. P(Oj).,i. P(ri₃> = P(,,) = i

&    4    a

JJ-Ol'lK] [lllHIlillll 1    IContd...

> ; - t ' 1

(d)    Comment upon the statement "Compression is still largely an art and to gain proficiency in an art you need to get a feel for the process.

(e)    DitYerentiate between static length and variable length coding schemes.

(0 What is zero frequency model in Markov models in text compression ⁹

2 Attempt any four of the following .

(a)    How Ric code can be viewed ? Explain the implementation of the rice code in the recommendation for loss less compression from the consultive committee on space data standard

(b)    Design a Golomb code for m = 5 where values ol it arc 0. I, .....10.

(c)    Generate Hulfman code tor a source

.4     3 >  tig , J with

probability model

7(0,)-P(a₃) = P(a₄) = 0.2,

P(a₂) 0.25, P(a₅) = 0.05 and

P(V-o.i

JJ-0108J llllllll! II III Mil (III 2

I    I

(d)    Explain adaptive Huffman coding. How is it different from conventional Huffman'coding ?

(e)    Explain self information defined by Shannon.

(f)    What do you understand by information and entropy ? Discuss the relationship between them.

Attempt any four of the following :

(a)    What is facsimile encoding ? Explain run length coding technique used earlier for facsimile.

(b)    How LZ 77 algorithm works ? What are the problems with LZ 77 ? Explain with an example,

(c)    A sequence is encoded using LZW algorithm and the initial dictionary shown in the table :

Index Entry

1    a

2    b

3    r

4    t

The output of LZW encoder is following sequence 3, I, 4, 6, 8, 4, 2, I, 2, 5, 10,

6, 11, 13, 6 decode this sequence.

(d)    What are adaptive compression schemes ? What is the basic difference between adaptive and statistical compression scheme ? Discuss with the model of adaptive compression.

JJ-0108] 111111111.111 l lll || || 3

J i * 1 I 9 I

[Contd..

Attachment: uttar-pradesh-technical-university--uptu--2009-b-tech-information-technology-20759-1.pdf

Earning:   Approval pending.