It52 Itc 2marks

Marthandam College of Engineering and Technology Department of Information Technology
L.A.Anto Gracious, AP/IT IT52 Information Theory and Coding

IT 52- INFORMATION THEORY AND CODING

UNIT I

1. What is prefix coding?

Prefix coding is variable length coding algorithm. In assigns binary digits to the
messages as per their probabilities of occurrence. Prefix of the codeword means any sequence
which is initial part of the codeword. In prefix code, no codeword is the prefix of any other
codeword.

2. State the channel coding theorem for a discrete memory less channel.

Given a source of M equally likely messages, with M>>1, which is generating
information t a rate R. Given channel with capacity C. Then if,
R C
There exists a coding technique such that the output of the source may be transmitted over the
channel with probability of error in the received message which may be made arbitrarily
small.

3. Explain channel capacity theorem.

The channel capacity of the discrete memory less channel is given as maximum
average mutual information. The maximization is taken with respect to input probabilities
P(x
i
)
C = B log
2
(1+S/N) bits/sec
Here B is channel bandwidth.

4. Define channel capacity of the discrete memory less channel.

The channel capacity of the discrete memory less channel is given as maximum
average mutual information. The maximization is taken with respect to input probabilities
C = max I(X:Y)
P(xi)

5. Define mutual information.

The mutual information is defined as the amount of information transferred when x
i
is
transmitted and y
i
is received. It is represented by I (x
i
,yi) and given as,
(
)
(
)
(
)

6. State its two properties of mutual information

The mutual information is symmetric.
I(X: Y) = I(X: Y)
The mutual information is always positive
I(X: Y) 0


7. Define efficiency of the source encoder.

Efficiency of the source encoder is given as,

()
()

8. Define code redundancy.

It is the measure of redundancy of bits in the encoded message sequence. It is given
as,
Redundancy = 1 code efficiency
= 1
It should be as low as possible.

9. Define rate of information transmission across the channel.

Rate of information transmission across the channel is given as,
Dt = [H(X) H(X/Y)]r bits/sec
Here H(X) is the entropy of the source.
H(X/Y) is the conditional entropy.

10. Define bandwidth efficiency.

The ratio of channel capacity to bandwidth is called bandwidth efficiency

()
()

11. What is the capacity of the channel having infinite bandwidth?

The capacity of such channel is given as,
C = 1.44 (S/N
0
)
Here S/N
0
is signal to noise ratio

12. Define a discrete memory less channel.

For the discrete memory less channels, input and output, both are discrete random
variables. The current output depends only upon current input for such channel.

13. Find entropy of a source emitting symbols x, y, z with probabilities of 1/5, 1/2, 1/3
respectively.


14. An alphabet set contains 3 letters A, B, C transmitted with probabilities of 1/3, ,
1/4. Find entropy.

15. Define information

Amount of information: I
k
= log
2
(1/p
k
)

16. Write the properties of information

If there is more uncertainty about the message, information carried is also more.
If receiver knows the message being transmitted, the amount of information carried is
zero.
If I1 is the information carried by message m1, and I2 is the information carried by
m2, then amount of information carried compontely due to m1 and m2 is I1+I2

17. Calculate the amount of information if p
k
=

18. What is entropy?

Average information is represented by entropy. It is represented by H.

19. Properties of entropy:

Entropy is zero if the event is sure or it is impossible
H = 0 if p
k
= 0 or 1
When p
k
= 1/M for all the M symbols, then the symbols are equally likely for such
source entropy is given as H = log
2
M
Upper bound on entropy is given as,
H
max
= log
2
M

20. Define code variance

Variance is the measure of variability in codeword lengths. It should be as small as
possible.

Here variance code
p
k
probability of K
th
symbol

n
k
no. of bits assigned to K
th
symbol
N avg. codeword length

UNIT-II

1. Define Nyquist rate.

Let the signal be band limited to W Hz. Then Nyquist rate is given as,
Nyquist rate = 2W samples/sec
Aliasing will not take place if sampling rate is greater than Nyquist rate.

2. What is meant by aliasing effect?

Aliasing effect takes place when sampling frequency is less than nyquist rate. Under
such condition, the spectrum of the sampled signal overlaps with itself. Hence higher
frequencies take the form of lower frequencies. This interference of the frequency
components is called aliasing effect.

3. What is PWM refers.

PWM is basically pulse width modulation. Width of the pulse changes according to
amplitude of the modulating signal; it is also referred as pulse duration modulation or PDM.

4. State sampling theorem.

Sampling theorem states that, a band limited signal of finite energy, which has no
frequency components higher than W Hz, is completely described by specifying the values of
the signal at instants of time separated by 1/2W seconds and , A band limited signal of finite
energy, which has no frequency components higher than W Hz, may be completely recovered
from the knowledge of its samples taken at the rate of 2W samples per second.

5. Mention two merits of DPCM.

Bandwidth requirement of DPCM is less compared to PCM.
Quantization error is reduced because of perdition filter.

6. What is the main difference in DPCM and DM?

DM encodes the input sample by only one bit. It sends the information about + or -,
ie. Step rise or fall. DPCM can have more than one bit for encoding the sample, it sends the
information about difference between actual sample value and predicted sample value.

7. How the message can be recovered from PAM?

The message can be recovered from PAM by passing the PAM signal through
reconstruction filter. The reconstruction filter integrates amplitudes of PAM pulses.
Amplitude smoothing of the reconstructed signal is done to remove amplitude discontinuities
due to pulses.


8. Write an expressing for bandwidth of binary PCM with N message each with a
maximum frequency of fm Hz.

If v number of bits are used to code each input sample, then bandwidth of PCM is
given as,
BT N. v . fm
Here v. fm is the bandwidth required by one message.

9. How is PDM wave converted into PPM systems?

The PDM signal is given as a clock signal to monostable multivibrator. The
multivibrator triggers on falling edge. Hence a PPM pulse of fixed width is produced after
falling edge of PDM pulse. PDM represents the input signal amplitude in the form of width
of the pulse. A PPM pulse is produced after this width of PDM pulse. In other words, the
position of the PPM pulse depends upon input signal amplitude.

10. Mention the use of adaptive quantizer in adaptive digital waveform coding schemes.

Adaptive quantizer changes its step size accordion to variance of the input signal.
Hence quantization error is significantly reduces due to adaptive quantization. ADPCM uses
adaptive quantization. The bit rate of such schemes is reduces due to adaptive quantization.

11. What do you understand from adaptive coding?

In adaptive coding, the quantization step size and prediction filter coefficients are
changed as per properties of input signal. This reduces the quantization error and number of
bits used to represent the sample value. Adaptive coding is used for speech coding at low bit
rates.

12. What is meant by quantization?

While converting the signal value from analog to digital, quantization is performed.
The analog value is assigned to the nearest digital level. This is called quantization. The
quantized value is then converted to equivalent binary value. The quantization levels are
fixed depending upon the number of bits. Quantization is performed in every analog to digital
conversion.

13. The signal to quantization noise ratio in a PCM system depends on

The signal to quantization noise ratio in PCM is given as,
(S/N)dB (4.8+6v) dB
Here v is the number of bits used to represent samples in PCM. Hence signal to quantization
noise ration in PCM depends upon number of bits or quantization levels.

14. For the transmission of normal speech signal in the PCM channel needs the B.W.
of..

Speech signals have the maximum frequency of 3.4 kHz. Normally 8 bits PCM is
used for speed. The transmission bandwidth of PCM is given as,
BT vW

8 x 3.4 kHz
27.2 kHz.

15. It is required to transmit speech over PCM channel with 8-bit accuracy. Assume the
speech in baseband limited to 3.6 kHz. Determine the bit rate?

The signaling rate in PCM is given as,
R= v f
s

Here v number of bits ie. 8
The maximum signal frequency is W= 3.6 kHz. Hence minimum sampling frequency will be,
f
s
= 2W
= 2 x3.6 kHz
= 7.2 kHz.
R = 8x7.2x103
= 57.6 kbits/sec

16. What is meant by adaptive delta modulation?

In adaptive delta modulation, the step size is adjusted as per the slope of the input
signal. Step size is made high if slope of the input signal is high. This avoids slope overload
distortion.

17. Delta modulation of delta modulation over pulse modulation schemes?

Delta modulation encodes one bit per sample. Hence signaling rate is reduced in DM.

18. What should be the minimum bandwidth required to transmit a PCM channel?

The minimum transmission bandwidth in PCM is given as,
B
T
= vW
Here v is number of bits used to represent on pulse.
W is the maximum signal frequency.

19. What is the advantage of delta modulation over PCM?

Delta modulation uses one bit to encode one bit to encode one sample. Hence bit rate
of delta modulation is low compared to PCM.

20. How distortions are overcome in AXM?

The slope overload and granular noise occur mainly because of fixed step size in delta
modulator.
Step size is more for fast amplitude changes and step size is less for slowly varying
amplitude.
The step size is varied according to amplitude variations of input signal



UNIT III Error Control Coding

1. What is hamming distance?

The hamming distance between the two code vectors is equal to the number of
elements in which they differ. For example, let the two code words be,
X = (101) and Y = (110)
These two code words differ in second and third bits. Therefore the banning distance between
X and Y is two.

2. Define code efficiency?

The code efficiency is the ratio of message bits in a block to the transmitted bits for
that block by the encoder ie.

3. What is meant by systematic and non systematic codes?

In a systematic block code, message bits appear first and then check bits. In the
nonsystematic code, message and check bits cannot be identified in the code vector.

4. What is meant by linear code?

A code is linear if modulo-2 sum of any two code vectors produces another code
vector. This means any code vector can be expressed as linear combination of other code
vectors.

5. What are the error detection and correction capabilities of Hamming codes?

The minimum distance (d
min
) of Hamming codes is 3. Hence it can be used to detect
double errors or correct single errors. Hamming codes are basically linear block codes with
d
min
= 3

6. What is meant by cyclic code?

Cyclic codes are the subclass of linear block codes. They have the properly that a
cyclic shift of one codeword produces another code word. For example consider the
codeword.

Let us shift above code vector to left cyclically,

Above code vector is also a valid code vector.

7. How syndrome is calculated in Hamming codes and cyclic codes?
In Hamming codes the syndrome is calculated as,
S = YH
T

Here Y is the received and HT is the transpose of parity check matrix.
In cyclic code, the syndrome vector polynomial is given as.

S(p) = rem [Y(p)/G(p)]
Here Y(p) is received vector polynomial and G(p) is generator polynomial.

8. What is BCH code?

BCH codes are most extensive and powerful error correcting cyclic codes. The
decoding of BCH codes is comparatively simples. For any positive integer m and t, there
exists a BCH code with following parameters:
Block length: n = 2
m
-1
Number of parity check bits: n-k mt
Minimum distance: d
min
2t + 1

9. What is RS code?

These are non binary BCH codes. The encoder for RS codes operates on multiple bits
simultaneously. The (n, k) RS code takes the groups of m-bit symbols of the incoming binary
data stream. It takes such k number of symbols in one block. Then the encoder adds (n-k)
redundant symbols to form the code word of n symbols.

RS code has:
Block length: n = 2
m
-1
Message size: k symbols
Number of parity check bits: n-k= 2t
Minimum distance: d
min
= 2t + 1

10. What is the difference between block codes and convolutional codes?

Block codes take k number of message bit simultaneously and form n bit code
vector is also called block. Convolutional code takes one message bit at a time and generates
two or more encoded bits. Thus convolutional codes generate a string.

11. Define constraint length in convolutional codes.

Constraint length is the number of shifts over which the single message bit can
influence the encoder output. It is expressed in terms of message bits.

12. Define free distance and coding gain.

Free distance is the minimum distance between code vectors. It is also equal to
minimum weight of the code vectors.

Coding gain is used as a basis of comparison for different coding methods. To achieve
the same bit error rate the coding gain is defined as,



13. Why cyclic codes are extremely well suited for error detection?

They are easy to encode
They have well defined mathematical structure. Therefore efficient decoding schemes
are available.

14. What is syndrome?

Syndrome gives an indication of errors present in received vector Y. If YH
T
= 0,
then there are no errors in Y and it is valid code vector. The non-zero value of YH
T
is
called syndrome. Its non-zero value indicates that Y is not a valid code vector and it
contains errors.

15. Define dual code.

Let there be (n, k) block code. It satisfies HGT = 0. Then the (n,n-k) i.e. (n,q) block
code is called dual code. For every (n, k) block code, there exists a dual code of size (n, q).

16. Write syndrome properties of liner block codes.

Syndrome is obtained by S = YH
T
.
If Y = X, then S = 0 ie. No error in output.
If Y X, then S 0 ie. There is an error in output.
Syndrome depends upon the error pattern only, ie. S = EHT

17. What is Hamming code? Write its conditions

Hamming codes are (n, k) liner block codes with following conditions:
Number of check bits q 3
Block length n = 2q 1
Number of message bits k = n q
Minimum distance d
min
= 3

18. List the properties of generator polynomial of cyclic codes.

Generator polynomial is a factor x(p) and (p
n
+1)
Code polynomial, message polynomial and generator polynomial are related by, X(p)
= M(p) G(p)
Generator polynomial is of degree q

19. What is hadamard code?

The hadamard code is derived form hadamard matrix. The hadamard matrix is the n x
n square matrix. Rows of this hadamard matrix represent code vectors. Thus an n x n
hadamard matrix represents n codes vector of n bits each. If the block of message vector
contains k bits, then
N = 2
k



20. Write the advantage of extended code

This code can detect more number of errors compared to normal (n, k) block code.
But it cannot use in error correction.

UNIT IV

1. State the main application of Graphics Interchange Format (GIF)

The GIF format is used mainly with internet to represent and compress graphical
images. GIF images can be transmitted and stored over the network in interlaced mode, this is
very useful when images are transmitted over low bit rate channels.

2. Explain Run length encoding.

The run length encoding is simplest lossless encoding techniques. It is mainly used to
compress text or digitized documents. Binary data strings are better compressed by run length
encoding. Consider the binary data string
1111110000011111.
If we apply run length coding to above data string, we get,
7,1; 6,0; 5,1; 3,0
Thus there are seven binary 1s, followed by six binary 0s followed by five binary 1s and
so on.

3. What is JPEG standard?

JPEG stands for joint photographic exports group. This has developed a standard for
compression of monochrome/color still photographs and images. This compression standard
is known as JPEG standard. It is also known as ISO standard 10918. It provides the
compression ratios up to 100:1.

4. Why differential encoding is carried out only for DC coefficient in JPEG?

The DC coefficient represents average color/luminance/ chrominance in the
corresponding block. Therefore it is the largest coefficient in the block.
Very small physical area is covered by each block. Hence the DC suitable
compressions for DC coefficients do not vary much from one block to next block.
The DC coefficients vary slowly. Hence differential encoding is best suitable
compression for DC coefficients. It encodes the difference between each pair of
values rather than their absolute values.

5. What do you understand by GIF interlaced node.

The image data can be stored and transferred over the network in an interlaced mode.
The data is stored in such a way that the decompressed image is built up in progressive way.



6. Explain in brief spatial frequency with the aid of a diagram.

The rate of change of pixel magnitude along the scanning line is called spatial frequency.

7. Write the advantages of Data compression

Huge amount of data is generated in text, images, audio, speech and video.
Because of compression, transmission data rate is reduced.
Storage becomes less due to compression. Due to video compression, it is possible to
store one complete movie on two CDs.
Transportation of the data is easier due to compression.

8. Write the drawbacks of Data compression

Due to compression, some of the data is lost.
Compression and decompression increases complexity of the transmitter and receiver.
Coding time is increased due to compression and decompression.

9. Compare lossless and lossy compression 0

Sl.No. Lossless compression Lossy compression
1. No information is lost Some information is lost
2. Completely reversible It is not reversible
3. Used for text and data Used for speed and video
4. Compression ratio is less High compression ratio
5. Compression is independent of
human response
Compression depends upon sensitivity of
human ear, eyes

10. Compare static coding and dynamic coding

Sl.No. Static coding Dynamic coding
1. Codewords are fixed throughout
compression
Codewords change dynamically during
compression
2. Statistical characteristics of the data
are known
Statistical characteristics of the data are not
known
3. Receiver knows the set of codewords Receiver dynamically calculates the
codewords

4. Ex: Static Huffman coding Ex: Dynamic Huffman coding

11. Write the principle of static Huffman coding

In static Huffman coding, the character string to be transmitted is analyzed. The
frequency of occurrence of each character is determined. The variable length codewords are
then assigned to each character. The coding operation creates an unbalanced tree. It is also
called Huffman coding tree.

12. How arithmetic coding is advantages over Huffman coding for text compression?

Sl.No. arithmetic coding Huffman coding
1. Codes for the characters are derived. Coding is done for messages of short
lengths
2. Shannons rate is achieved only if
character probabilities are all integer
powers of 1/2
Shannons rate is always achieved
irrespective of probabilities of characters
3. Precision of the computer does not affect
coding
Precision of the computer determine
length of the character string that can by
encoded
4. Huffman coding is the simple technique Arithmetic coding is complicated

13. Define compression

Large amount of data is generated in the form of text, images, audio, speech and
video.

14. What is the principle of data compression?

15. What are the types of compression?

The compression can be of two types:
Lossless compression and lossy compression

Lossless compression:
In compression, no part of the original information is lost during compression.
Decompression produces original information exactly

Lossy compression:
In lossy compression some information is lost duration compression. Hence
decompression does not produce original information exactly.


16. What are make-up codes and termination codes in digitization of documents?

Make-up codes and termination codes gives codeword for contiguous white and black
pels along the scanned line.

Termination code:
There codes give codewords for black and white run lengths from 0 to 63 in steps of
1 pel.

Make-up codes:
These codes give codewords for black and white run lengths that are multiples of 64
pels.

17. What are JPEG standards?

The JPEG stand for Joints Photographic Exports Group(JPEG). This group is working
on international compression standard for color and monochrome continuous tone still
images, photographs etc. this group came up with a compression standard, which is widely
known as JPEG standard. It is also known as ISO standard 10918.

18. What are the types of JPEG ALGORITHMS?

There are two types of JPEG algorithms.

Baseline JPEG:
During decoding, this algorithm draws line until complete image is shown.

Progressive JPEG:
During decoding, this JPEG algorithm draws the whole image at once, but in very
poor quality. Then another layer of data is added over the previous image to improve its
quality. Progressive JPEG is used for images on the web. The used can make out the image
before it is fully downloaded.

19. Draw the block diagram of JPEG encoder

20. What type of encoding techniques is applied to AC and DC coefficient in JPEG?

The DC coefficients have normally large amplitudes. They vary slowly from block to
block. Differential encoding becomes very efficient for such data. It encodes only the
difference among the coefficients.
The AC coefficients are remaining 63 coefficients in each block. They are fast
varying. Hence run length encoding proves to be efficient for such data.


UNIT V

1. What is Dolby AC-1?

Dolby AC-1 is used for audio coding. It is MPEG audio coding standard. It uses
psychoacoustic model at the encoder and has fixed bit allocations to each sub band.

2. What is the need of MIDI standard?

The MIDI stands for musical instrument digital interface (MIDI). It normally specifies
the details of digital interface of various musical instruments to micro-computer. It is
essential to access, record or store the music generated from musical instruments.

3. What is perceptual coding?

In perceptual coding only perceptual feature of the sound are stored. This gives high
degree of compression. Human ear is not sensitive to all frequencies equally. Similarly
masking of weaker signal takes place when louder signal to present nearby. These parameters
are used in perceptual coding.

4. Explain CELP principles.

CELP uses more sophisticated model of vocal tract.
Standard audio segments are stored as waveform templates. Encoder and decoder both
have same set of templates. It is called codebook.
Every digitized segment is compared with waveform templates in code book.
The matching template is differentially encoded and transmitted.
At the receiver, the differentially encoded codeword selects the matching template
from codebook.

5. What is significance of D- frames in video coding?
The D frames are inserted at regular intervals in the encoded sequence of frames.
These are highly compressed and they are ignored during decoding p and B
frames.
The D- frames consists of only DC coefficients and hence they generate low
resolution picture.
The low resolution pictures generated by D frames are useful in fast forward and
rewind applications.

6. Define the terms GOP and Prediction span with reference to video compression.

GOP (Group of Picture):
The number of fames or pictures between two successive I-frames is called group of
picture or GOP. Typical value of GOP varies from 3 to 12.

Prediction Span:
The number of frames between a P-frame and the immediately preceding I or P frame
is called prediction span. The typical value of prediction span lies from 1 to 3.


7. Define the terms processing delay and algorithmic delay with respect to speech
codes.

Processing delay:
It is the combined time required for (i) analyzing each block of digitalized samples at
encoder and (ii) reconstruction of speech at decoder.

Algorithmic delay:
It is the time required to accumulate each block of samples in the memory.

8. What do you understand by frequency masking?

The strong signal reduces level of sensitivity of human ear to other signals which are
near to it in frequency. This effect is called frequency masking.

9. Find the average compression ratio of the GOP which has a frame sequence
IBBPBBPBBPBB where the individual compression ratios of I, P and B are 10: 1, 20: 1,
50: 1 respectively.

There are total 12 frames of which I-frames are 1, P-frames are 3 and B-frames are 8.
Hence average compression ratio will be,

10. What is perceptual coding?

In perceptual coding, the limitations of human ear are exploited. We know that human
ear can listen very small sound when there is complete silence. But if other big sounds are
present, then human ear cannot listen very small sounds. These characteristics of human ear
are used in perceptual coding. The strong signal reduces level of sensitivity of the ear to other
signals which are near to it in frequency. This effect is called frequency masking.

11. What is code excited LPC?

The code excited LPC uses more sophisticated model of a vocal tract. Therefore the
generated sound is more nature. The sophisticated version of vocal ract is known as code
excited linear prediction (CELP) model.

12. Define pitch and period.

Pitch:
The pitch of the signal gives information about fundamental frequency. Pitch of every
person is different. However it is in the similar range for males and some another rage for
females.

Period:
This is the time duration of the signal. It is also one of the important features.


13. List the application of LPC.

Since the generated sound is very synthetic, it is used mainly for military purposes.
LPC synthesis is used in applications which require very small bandwidth.

14. List the four international standards based on CELP.

They are ITU-T recommendations G.728, G.729, G.729 (A) and G.723.1

15. What is meant by temporal masking?

When ear hears the loud sound, certain time has to be passed before it hears quieter
sound. This is called temporal masking.

16. What is MPEG?

MPEG stands for Motion Pictures Expert Group(MPEG). It was formed by ISO.
MPEG has developed the standards for compression of video with audio. MPEG audio coders
are used for compression of audio. This compression mainly uses perceptual coding.

17. Draw the frame format in MPEG audio encoder.

18. Write the advantages and applications of Dolby AC-1.

Advantages:
Simple encoding scheme due to fixed bit allocations
Reduced compressed bit rate since frames does not include bit allocations. The typical
compressed bit rate is 512 kbps for two channel stereo signal.

Applications:
It is used in satellites for FM radio.
It is also used for compression of sound associated with TV programs.

19. Write the advantages and disadvantages of Dolby AC-2

Advantages:
Hit allocations are not transmitted in the frame.
Bit rate of encoded audio is higher than MPEG audio coding.

Disadvantages:
Complexity is more since psychoacoustic model and spectral envelope
encoder/decoders and used.
Sub band samples are encoded and transmitted in the frame. Hence bit rate of
compressed data is slightly reduced.
It cannot be used for broadcast applications since encoder and decoder both contain
psychoacoustic model. Therefore encoder cannot be modifier easily.

20. Define I, P and B frames.

I-frames:
It is also known as intracoded frame. It is normally the first frame in the new scene.

P-frames:
It is also known as predictive frame. It basically predicts the movement of objects
with respect to I-frame.

B-frame:
It is also known as bidirectional frame. These frames relate the motion of the objects
in preceding as well as succeeding frames.

It52 Itc 2marks

Uploaded by

Copyright:

Available Formats

It52 Itc 2marks

Uploaded by

Document Information

Original Description:

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

It52 Itc 2marks

Uploaded by

Copyright:

Available Formats

Marthandam College of Engineering and Technology Department of Information Technology

L.A.Anto Gracious, AP/IT IT52 Information Theory and Coding

You might also like