Uttar Pradesh Technical University (UPTU) 2007 B.E Computer Science data compression - Question Paper
data compression
CS - 054
* V - 1 0 5 1 *
Printed Pages : 4
(Following Paper ID and Roll No. to be filled in your Answer Book)
PAPER ID : 1051
Roll No. | | | | | | | | | 1 | B. Tech.
(SEM. VIII) EXAMINATION, 2006-07 DATA COMPRESSION
Time : 3 Hours] [Total Marks : 100
Note : Attempt all questions. All questions carry equal marks.
1 Attempt any four parts of the following : 5x4=20
(a) What do you mean by lossless compression? Compare lossless compression with lossy compression.
(b) Explain Modeling and coding with the help of suitable examples.
(c) Suppose X is a random variable that takes on values from M. letter alphabet show that
0 < H(x) < log2 M
(d) What do you understand by information and entropy ? Find the first order entropy over an alphabet A = {a1,a2,a3,a4} where
p (ax) = p (a2) = p (a3) = p (a4) = 1/4
(e) What do you understand by Prefix code ?
(f) The joint probabilities of the transmitted and received messenges of a communication system is given as
| ||||||||||||||||||||||||||||||
|
Calculate H(x) and H(y) |
Attempt any four parts of the following :
5x4=20
(a) What are two observations on which Hyffman procedure is based regarding optimum prefix code ?
(b) What are the various applications of Huffman Coding?
(c) What is Redundency of code? How can we define and calculate it?
(d) Consider source alphabet of A,B,C...G,H having probabilities P (x given as P (x = 1/2, 1/4, 1/16, 1/16, 1/32, 1/32, 1/32, 1/32
Design the Huffman code. Also calculate average length of codewords and code efficiency.
(e) For an Alphabet A = {a1 a2 a3}with probabilities P (a = 0.7, P (a) = 0.2, P(a3)
= 0.1
Design a 3-bit Tunstall Code.
(f) Write short notes on the following :
(i) Golomb Code
(ii) Non binary Huffman Code.
Attempt any four parts of the following : 5x4=20
(a) What do you mean by Binary Code? Compare Binary code with Huffman Code.
(b) Where we use the dictionary techniques of Encoding? Also explain various types of dictionary techniques.
(c) Explain the Run-Length Coding with the help of suitable example.
(d) A sequence is encoded using LZW algorithm and the initial dictionary shown in table
Index Entry
1 a
2 b
3 r
4 t
The output of LZW encoder is the following sequence
3,1,4,6,8,4,2,1,2,5,10,6,11,13,6
Decode this sequence.
(e) Find the real valued tag for the sequence a1a1a3a2a3a1 over letter {af a2 a3} with probabilities {0.2, 0.3, 0.5}
(f) Write short notes on the following :
(i) Dynamic Markov Compression
(ii) Graphic Interchange Format.
Attempt any two parts of the following : 10x2=20
(a) What do you understand by Adaptive quantization? Explain the various approaches to adapting the quantizer parameters.
(b) What is conditional entropy and Mutual Information and Average Mutual Information?
For two Random variables X and Y show that
(a) H (x/y) < H(x)
(b) I (x;y) = I (y;x)
(c) What is Rate distortion theory? Drive the Rate distortion function for the
(i) Binary Source
(ii) Gaussian Source.
5 Attempt any two parts of the following : 10x2=20
(a) What do you understand by vector quantization?
Also explain the procedure of vector quantization.
(b) What is tree-structured vector quantization? Explain the design process of tree-structured vector quantizer. What is prunning? How it helps to improve the rate distortion performance?
(c) Explain the following quantization techniques in detail :
(a) Structured vector quantization
(b) Pyramid vector quantization.
V-1051] 4 [ 6825 ]
|
Attachment: |
| Earning: Approval pending. |
