Uttar Pradesh Technical University (UPTU) 2007 M.C.A data compression - Question Paper

data compression

MCA - 404(3)

*V-1477*

Printed Pages : 4

(Following Paper ID and Roll No. to be filled in your Answer Book)

IroII No.

M. C. A.

(SEM. IV) EXAMINATION, 2006-07 DATA COMPRESSION

Time : 3 Hours]    [Total Marks : 100

Note : (i) Attempt all questions.

(ii) Each question carries equal marks.

1 Attempt any four parts of the following : 5x4=20

(a)    What do you mean by Data compression?

Write some of the applications where it is used.

(b)    Write down some of the performance measure criterias of compression techniques. Which are the additional methods to evaluate the performance of lossy compression techniques?

(c)    What is data modelling? Give a brief description of any two mathematical models used for data modelling.

(d)    Consider the following sequence :

1, 2, 3, 2, 3, 4, 5, 4, 5, 6, 7, 8, 9, 8, 9, 10 Assuming the frequency of occurrence of each number is reflected accurately in the number of times it appears in the sequence and the sequence is independent and identically distributed, find the first order entropy of the sequence.

(e)    Determine whether the code {0,01, 11} is uniquely decodable or not.

(f)    What is the difference between a fixed length code and a variable length code. In variable length code, define the term rate of the code.

2    Attempt any four parts of the following : 5x4=20

(a)    A source emits letters from an alphabet A =

{a_v a a₃, a₄, a₅} with P (a_x) = P) = 0.4,

P(a₄) = P (a₅) = 0.1. Find the Huffman code of the source.

(b)    How a minimum variance Huffman code is different from its corresponding Huffman code? Explain with the help of an example.

(c)    Prove that the average codeword length J of an optimal code for a source S is greater than or equal to entropy H (S).

(d)    Let Huffman code of a source S with three letters {a_1? a2, a₃} is {0,11,10} respectively.

Find the extended Huffman code of the same source taking two letters at a time. Compare the average code word length in both cases.

(e)    Explain the update procedure of adaptive Huffman coding algorithm with the help of a flow chart.

(f)    Write down the application of Huffman coding in text compression and audio compression.

3    Attempt any four parts of the following : 5x4=20

(a) Given a number a in the internal [0,1] with an

n-bit binary representation (b₁ b₂....b_n), show that for any other no. b to have a binary representation with (b₁ b₂....b_n) as the prefix

1

b has to lie in the internal (a, a+

^v 2

V-1477]    2    [Contd...

(b)    Consider a three letter alphabet A = jap a₃) with P (a = 0.7, P (a2) = 0.1 and P (a₃) = 0.2. Using arithmetic coding, generate a code for the sequence a₁ a, a₃.

(c)    Explain the JBIG standard of Bi-level image compression. How arithmetic coding is applicable to it?

(d)    What do you mean by diagram coding? Given the following dictionary, encode the sequence abracadabra :

Code	Entry
000	a
001	b
010	c
Oil	d
100	r
101	ab
110	ac
111	ad

(e)    Give the LZ77 approach for adaptive dictionary based encoding.

(f)    What is Graphics Interchange Format (GIF) and where is it used?

4 Attempt any two parts of the following : 10x2=20

(a)    What is lossy data encoding? Write down the distortion measure criterias to check the fidelity of a reconstructed source sequence to the original one in such type of encoding techniques.

(b)    What is QUANTIZATION? Describe the quantization problem with the help of an example in detail.

(c) How adaptive quantization is different from uniform quantization? Explain the two approaches forward adaptive approach and backward adaptive approach for adapting the quantizer parameters.

5 Attempt any two parts of the following : 10x2=20

(a)    What is vector quantization? How is it different from scalar quantization? Write down some of the advantages of vector quantization over scalar quantization.

(b)    What do you mean by codebook of a quantizer?

What problems can be there when designing a codebook for a higher dimensional quantizer?

How Linde-Buzo-Gray algorithm is helpful here?

(c)    How the computational complexity of the code book design process in vector quantization is reduced by imposing a tree structure over it?

What is the role of pruning in such type of vector quantization?

V-1477]    4    [ 2540 ]

Attachment: uttar-pradesh-technical-university--uptu--2007-m-c-a--53411-1.pdf

Earning:   Approval pending.