Information Coding Techniques

DEPARTMENT OF INFORMATION TECHNOLOGY

QUESTION BANK
Subject Name: Information Coding Techniques Year /Sem: II / IV

PART A (2 MARKS) 1. 2. 3. 4. 5. 6.

What is uncertainty? What is prefix coding? State the channel coding theorem for a discrete memory less channel Define a discrete memory less channel State channel capacity theorem Probability 0.25, 0.20, 0.15, 0.15, 0.10, 0.05 For the above given data, Calculate the entropy by encoding it using Shannon fano technique 7. Compare Huffman coding and Shannon fano coding 8. What are the advantages of Lempel Ziv encoding algorithms over Huffman coding? 9. Find entropy of a source emitting symbols X,Y,Z with the probabilities of 1/5,1/2,1/3 respectively 10. State source coding theorem 11. Define capacity 12. Define information 13. Define Entropy 14. List the properties of information 15. Define information rate 16. Give the upper bound and lower bound for entropy 17. Define discrete memory less source 18. What is the entropy of an extended discrete memory less source? 19. Calculate the primary source entropy and the entropy of third extension of binary source with probabilities P0 = , P1 = 20. What are the two functional requirements needed in the development of an efficient source encoder? 21. What is Lmin ? How it is determined? 22. Find the entropy of second order extension of a source whose alphabet x = {x0, x1, x2} with probability 23. What are uniquely decipherable codes?

aa

na va

N.

co m

UNIT I INFORMATION ENTROPY FUNDAMENTALS

Information Coding Techniques 24. What is data Compaction? 25. State Lempel-Ziv coding 26. If the probability of getting a head is by tossing a coin, find the information associated with it? PART B (16 MARKS) 1. (i) How will you calculate channel capacity? (ii)Write channel coding theorem and channel capacity theorem (iii)Calculate the entropy for the given sample data AAABBBCCD (iv)Prove Shannon information capacity theorem (2) (5) (3) (6)

2.

3.

4.

(i)Use differential entropy to compare the randomness of random variables (4) (ii)A four symbol alphabet has following probabilities Pr(a0) =1/2 Pr(a0) = 1/4 Pr(a0) = 1/8 Pr(a0) = 1/8 and an entropy of 1.75 bits. Find a codebook for this four letter alphabet that satisfies source coding theorem (4) (iii)Write the entropy for a binary symmetric source (4) (iv)Write down the channel capacity for a binary channel (4) (a) A discrete memory less source has an alphabet of five symbols whose probabilities of occurrence are as described here Symbols: X1 X2 X3 X4 X5 Probability: 0.2 0.2 0.1 0.1 0.4 Compare the Huffman code for this source .Also calculates the efficiency of the source encoder (8) (b) A voice grade channel of telephone network has a bandwidth of 3.4 kHz Calculate (i) The information capacity of the telephone channel for a signal to noise ratio of 30 dB and (ii) The min signal to noise ratio required to support information transmission through the telephone channel at the rate of 9.6Kb/s (8) A discrete memory less source has an alphabet of seven symbols whose probabilities of occurrence are as described below

aa
s0 s1
: 0.25 0.25

na va
s2 s3 s4
0.125 0.0625 0.0625

Symbol:
Prob

(i) Compute the Huffman code for this source moving a combined symbols as high as

possible

N.
s5
0.125

co m
s6
0.125

(10)
(4) (2)

(ii) Calculate the coding efficiency (iii) Why the computed source has a efficiency of 100%

Information Coding Techniques

P(X, Y)

Apply Huffman coding procedure to following massage ensemble and determine Average length of encoded message also. Determine the coding efficiency. Use coding alphabet D=4.there are 10 symbols. X = [x1, x2, x3x10] P[X] = [0.18,.0.17,0.16,0.15,0.1,0.08,0.05, 0.05,0.04,0.2] (16)

aa

Calculate the entropies H(X), H(Y), H(X/Y), and H (Y/X)

na va
3/40 1/40 1/40 1/20 3/20 1/20 3/8 1/8 1/8

N.

6.A discrete memory less source has an alphabet of five symbols with their probabilities for its output as given here [X] = [x1 x2 x3 x4 x5 ] P[X] = [0.45 0.15 0.15 0.10 0.15] Compute two different Huffman codes for this source .for these two codes .Find (i) Average code word length (ii) Variance of the average code word length over the ensemble of source symbols (16) 7. A discrete memory less source X has five symbols x1,x2,x3,x4 and x5 with probabilities p(x1) 0.4, p(x2) = 0.19, p(x3) = 0.16, p(x4) = 0.15 and p(x5) = 0.1 (i) Construct a Shannon Fano code for X,and Calculate the efficiency of the code (7) (ii) Repeat for the Huffman code and Compare the results (9) (iii) 8. Consider that two sources S1 and S2 emit message x1, x2, x3 and y1, y2,y3 with joint probability P(X,Y) as shown in the matrix form.

co m

(16)

Information Coding Techniques

UNIT II - DATA AND VOICE CODING PART A(2 MARKS) 1. 2. 3. 4. 5. 6. 7. 8. 9. Define Pulse Code Modulation (PCM.) Give the basic operations performed in transmitter and receiver of PCM system List the basic elements of a PCM system. Define sampling List the two different types of quantization. List the different types of line codes Give the block diagram of regenerative repeater. List the- three 'basic functions performed by a regenerative repeater A television signal with a bandwidth of 4.2 MHz. is transmitted using binary PCM.' The number of quantization levels is 512. Calculate the code word length 10. Briefly explain slope overloading 11. What are the advantages of coding speech at low bit rates? 12. Briefly explain sub band coding for speech signal 13. List the differences between delta modulation and adaptive delta modulation 14. Draw the block diagram for differential pulse code modulator 15. Draw the block diagram of DPCM signal encoder 16. Give the various pulse modulation techniques, pulse code modulation techniques available .How do they differ from each other? 17. Define Delta modulation 18. List the disadvantages of Delta modulation 19. Define Quantization 20. Define Quantization error

1.

(i) (ii) (iii) (iv)

aa

Compare and contrast DPCM and ADPCM Define pitch, period and loudness What is decibel? What is the purpose of DFT?

na va

PART B (16 MARKS) (6) (6) (2) (2) (6) (6) (4)

2.

i. ii. iii.

Explain delta modulation with examples Explain sub-band adaptive differential pulse code modulation What will happen if speech is coded at low bit rates

3. With the block diagram explain DPCM system. Compare DPCM with PCM & DM systems (16) 4. i. Explain DM systems with block diagram (8)

ii Consider a sine wave of frequency fm and amplitude Am, which is applied to a delta modulator of step size .Show that the slope overload distortion will occur

N.

co m

Information Coding Techniques

if

Am > / ( 2fmTs)

Where Ts sampling. What is the maximum power that may be transmitted without slope overload distortion? (8)
5. Explain adaptive quantization and prediction with backward estimation in ADPCM

system with block diagram

(16)

7.

What is modulation? Explain how the adaptive delta modulator works with different algorithms? Compare delta modulation with adaptive delta modulation (16) 8. Explain pulse code modulation and differential pulse code modulation (16) UNIT III - ERROR CONTROL CODING PART A (2 MARKS)

1. What is a generator polynomial? Give some standard generator polynomials 2. What is hamming distance in error control coding? 3. Why cyclic codes are extremely well suited for error detection? 4. What is syndrome? 5. Define dual code 6. What is hamming code? 7. List the properties of generator polynomial of cyclic codes 8. Write the syndrome properties of linear block codes 9. Give the steps in encoding (n, k) cyclic codes 10. What are cyclic codes? Why they are called sub class of block codes 11. List the conditions satisfied by Hamming codes 12. Define convolution codes 13. Define linear block codes 14. Define constraint length of convolution code 15. What is the difference between systematic codes and non systematic codes 16. What is the use of syndromes? Explain syndrome decoding 17. Draw the block diagram of syndrome calculator 18. Draw the block diagram for an encoder of (7,4) Hamming code 19. Define minimum distance between code vectors 20. Define Hamming Weight 21. Define code rate 22. List the types of errors 23. List the types of codes 24. What is error control coding? Which are the functional blocks of a communication system that accomplish this?

aa

na va

N.

co m

6. (i) Explain delta modulation systems with block diagrams (8) (ii) What is slope overload distortion and granular noise and how it is overcome in adaptive delta modulation (8)

Information Coding Techniques 25. List the properties of syndromes

UNIT IV - COMPRESSION TECHNIQUES PART B(16 MARKS) 1. Consider a hamming code C which is determined by the parity check matrix 1 1 0 1 1 0 0 1 0 1 1 0 1 0 0 1 1 1 0 0 1

H =

(iii) 2.

What is the length and the dimension K of the code? Why can the min Hamming distance dmin not be larger than three? (4)

3.

a. Consider the generator of a (7,4) cyclic code by generator polynomial g(x) 1+x+x3.Calculate the code word for the message sequence 1001 and Construct systematic generator matrix G. (8) b. Draw the diagram of encoder and syndrome calculator generated by polynomial g(x)? (8)

aa

(i) Define linear block codes (2) (ii)How to find the parity check matrix? (4) (iii)Give the syndrome decoding algorithm (4) (iv)Design a linear block code with dmin 3 for some block length n= 2m-1 (6)

na va

(iii) Calculate the syndromes for all possible error vectors e with Hamming weight <=1 and list them in a table. How can this be used to correct a single bit error in an arbitrary position? (4)

N.

(i) Show that the two vectors C1= (0010011) and C2 = (0001111) are code words of C and Calculate the hamming distance between them (4) (ii) Assume that a code word C was transmitted and that a vector r = c + e is received. Show that the syndrome S = r. H T only depends on error vector e. (4)

co m

Information Coding Techniques

4.

For the convolution encoder shown below encode the message sequence (10011). also prepare the code tree for this encoder (16) Path 1
+

FF

FF

Msg Bits
+

Output

Path 2

5. (i)

6. Verify whether g(x) = 1+x+x2+x3+x4 is a valid generator polynomial for generating a cyclic code for message [111] (16) 7. A convolution encoder is defined by the following generator polynomials: g0(x) = 1+x+x2+x3+x4 g1(x) = 1+x+x3+x4 g2(x) = 1+x2+x4 (i) What is the constraint length of this code? (4) (ii) How many states are in the trellis diagram of this code ( 8) (iii) What is the code rate of this code? (4) 8. Construct a convolution encoder for the following specifications: rate efficiency =1/2 Constraint length =4.the connections from the shift to modulo 2 adders are described by following equations

g1(x) = 1+x g2(x) = x Determine the output codeword for the input message [1110]

aa

na va

Find a (7,4) cyclic code to encode the message sequence (10111) using generator matrix g(x) = 1+x+x3 (8) 3. (ii) Calculate the systematic generator matrix to the polynomial g(x) = 1+x+x Also draw the encoder diagram (8)

N.

co m
(16)

Information Coding Techniques

UNIT IV -COMPRESSION TECHNIQUES

PART A(16 MARKS) 1. Calculate the bit rate for a 16 bit per sample stereophonic music whose sampling rate is 44.1 KSPS. 2. Draw the Huffman code tree and find out the codes for the given data AAABBCDAB 3. What type of encoding technique is applied to AC and DC co-efficient in JPEG? 4. State the main applications of Graphics Interchange Format (GIF) 5. Explain run length encoding 6. Explain the Source Intermediate Format(SIF) 7. Why differential encoding is carried out only for DC co efficient in JPEG? 8. What do you understand by frequency masking? 9. What are make up codes and termination codes in digitization of documents? 10. What do you understand by GIFF interlaced mode? 11. Explain in brief Spatial frequency with the aid of a diagram 12. How arithmetic coding is advantages over Huffman coding for text compression? 13. What are Make up Codes and Termination codes in digitization of documents? 14. Define Compression 15. What is the need for text and image compression? 16. What are the principles and types of compression? 17. Differentiate the loss less and lossy compression 18. What is arithmetic coding? 19. What is JPEG standards?

1. (i)Discuss the various stages in JPEG standard (9) (ii)Differentiate loss less and lossy compression technique and give one example for each (4) (iii)State the prefix property of Huffman code (3) 2. Write the following symbols and probabilities of occurrence, encode the Message went# using arithmetic coding algorithms. Compare arithmetic coding with Huffman coding principles (16) Symbols: e n t w # Prob : 0.3 0.3 0.2 0.1 0.1 3. (a) Draw the JPEG encoder schematic and explain (10)

aa

na va

PART B (16 MARKS)

N.

co m

Information Coding Techniques (b) Assuming a quantization threshold value of 16, derive the resulting quantization error for each of the following DCT coefficients 127, 72, 64, 56,-56,-64,-72,-128. (6) 4. (i) Explain arithmetic coding with suitable example (12) (ii) Compare arithmetic coding algorithm with Huffman coding (4) 5. 6 (i) Draw JPEG encoder block diagram and explain each block (ii) Why DC and AC coefficients are encoded separately in JPEG (14) (2)

(a) Discuss in brief ,the principles of compression (12) (b) in the context of compression for Text ,Image ,audio and Video which of the compression techniques discussed above are suitable and Why? (4) (i) Investigate on the block preparation and quantization phases of JPEG compression process with diagrams wherever necessary (8) (ii) Elucidate on the GIFF and TIFF image compression formats (8)

PART A (2 MARKS) 1. Explain CELP principles 2. What is significance of D- frames in video coding? 3. Find the average compression ratio of the GOP (Group of pictures) which has a frame sequence IBBPBBPBBPBB where the individual compression ratios of I,P and B are 10:1, 20:1 ,50:1 respectively 4. What is the need of MIDI standard? What is its application? 5. What is Dolby AC 1? 6. What is the need of Midi standard? 7. What is Dolby AC -1 ? 8. Define the terms GOP and Prediction Span with reference to video compression 9. Define the terms processing delay and algorithmic delay with respect to speech coders 10. What do you understand by frequency masking? 11. What is perceptual coding? 12. What are the applications of MPEG standards? 13. What is code excited LPC? Compare it with LPC 14. List the features of Perception 15. Define Pitch and period 16. List the applications of LPC 17. List the four international standards based on CELP 18. What is mean by temporal Masking? 19. What is MPEG? 20. Draw the frame format in MPEG audio encoder

aa

na va

N.

UNIT V - AUDIO AND VIDEO CODING

co m

Information Coding Techniques

PART B (16 MARKS) 1. (i) Explain the principles of perceptual coding (ii) Why LPC is not suitable to encode music signal? (14) (2)

2. (i)Explain the encoding procedure of I,P and B frames in video encoding with suitable diagrams (14) (ii) What are the special features of MPEG -4 standards (2)

4. Explain the encoding procedure of I,P and B frames in video compression techniques, State intended application of the following video coding standard MPEG -1 , MPEG -2, MPEG -3 , MPEG -4 (16) 5. (i) What are macro blocks and GOBs? (4) (ii) On what factors does the quantization threshold depend in H.261 standards? (3) (iii)Discuss the MPEG compression techniques (9) (i) Discuss about the various Dolby audio coders (ii) Discuss about any two audio coding techniques used in MPEG

6.

na va

N.

co m

3. Explain the Linear Predictive Coding (LPC) model of analysis and synthesis of speech signal. State the advantages of coding speech signal at low bit rates (16)

(8) (8)

7. (a) Discuss in brief, the following audio coders: (iv) MPEG audio coders (8) (v) DOLPY audio coders (8) (vi) 8. (i) Explain the Motion estimation and Motion Compensation phases of P and B frame encoding process with diagrams wherever necessary (12) (ii) Write a short note on the Macro Block format of H.261 compression standard (4)

aa

*************************