0% found this document useful (0 votes)
68 views74 pagesData Compression1
Uploaded by
harshrajput9560224610Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF or read online on Scribd
0% found this document useful (0 votes)
68 views74 pagesData Compression1
Uploaded by
harshrajput9560224610Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF or read online on Scribd
/ 74
www.askbooks.net
*AKTU Quantums *Toppers Notes *Books
Practical Files *Projects *lITJEE Books
www.askbooks.net
All AKTU QUANTUMS are available
ee
o ae complete engineering ret
5
Pert cet meet cd ai can also donate ebooks/study materials.
2. We don't intend to infringe any copyrighted material.
3. If you have any issues with any material on this
Pua Dae rat neck hues
PWS nue ee kU es PUBLISHED BY: Apram Singh
a CONTENTS
Quantum Publications”
(A Unit of Quantum Page Pvt. Ltd.)
Plot No. 59/2/7, Site - 4, Industr
* Sahibabad, Ghaziabad-201 010 = RCS 087 : DATA COMPRESSIO
Phone :0120-4160879
UNIT- : INTRODUCTION
: Email : pagequantum@gmail.com — Websi
Delhi Office : 1/6590, Bast Rohtas Na
(ap—27D)
Compression Techniques: Loss Test compression, Lossy Compression,
Siuninsofpertormarce Mosctiygand cating Mathematical Prctiminarice
Joc Lanse compreston, Abr! nth ton tinormatin theory, Mel
Physical most, Prebatlity motels, Nurkow moxels, composite Source
fruaie Conng unsguely decodable coxes, Prof codes
© Ati Ricits Resenven
fs part of this publication may be reproduced or transmitted, UNIT-2 : HUFFMAN CODING (28 D—61D)
in any form or by any means, without permission. The H
coding algorithm: Minimum variance Huffy
[ tnformation contained in this work is derived from sources | compre:
tho where Fey aches macs | a a
accuracy, however neither the publisher nor the authors ‘Coding a sequence, Generating a binary code, Comparison of Binary and
travis secure comple ay formation | isles Binsin agama
Fred ovina vr be phe othe es | Sarees Saget Coane canrae eaten ees
Sri nt of un of Wea
compress, Image Compression: The Graphics interchange Format (
Compression over Modems V 42 bits, Predictive Coding: Prediction with
Partial mateh (pp: The Z
oo crereaie tear eae peal gr Tbs ie CARE SVMBOL frat
‘Markoy Compression
4 Edition + 2014-15
5% Edition : 2015-16
UNIT: MATHEMATICAL PRELIMINARIES FOR LOSSY CODING
(107 D—135 D)
Distortion rites, Models Scalar Quantization: The Quantization problem,
6" Edition : 2016-17 inform Quantizer, Adaptive Quantization, Non uniform Qhinntisation
7» Edition + 2017-18 UNITS : VECTOR QUANTIZATION
(136 D—146 D)
8 Edition : 2018-19 Advantages of Vector Quantization over Seal
9 Edition : 2019-20 Base
uantization, The Linde
red Vector Quantizets, Strnetured
Price: Rs, 110/- only SHORT QUESTIONS
(147 D165 D)
ee SOLVED PAPERS (2011.12 TO 2018.19)
Printe
‘at Bala
(166 D176 D) Introduction
«SD - 10D)
Compression Techniques Lossless Compression and Lossy Compress
Measures of Performance
‘Modeling and Coding
A. Concept Outline : Part-1 : “5D
B. Long and Medium Answer Type Questions 5D
Part.2.. es 10D - 22D)
[ Mathematical Preliminaries for Lossless Compression = A Brief
Introduction to Information Theory
Models = Physical Models
* Probability Models
Markov Model
Composite Souree Model
A, Concept Outline : Part-2 . : nD
B. Long and Medium Answer Type Questions uD
Part-3 = (22p - 27D)
f Codinis: Uniquely Decodable Codes
| Prefix Codes
A. Concept Outline : Part-2 : svn 22D
B. Long and Medium Answer Type Questions sworn, 22D
s(CSA'T-8) D
Data Compression Sicsirg)p
PART-1
Compression Techniques : Lossless Compression and Lossy
Compression, Measures of Performance, Modeling and Coding,
[ CONCEPT OUTLINE : PART-1
‘+ Data compression is an art of science of representing information
| ina compact form.
+ Lossless compression involves no loss of information,
+ Lossy compression involves some loss of information and data
cannot be reconstructed exactly same as original,
‘+ Modeling and coding are the two phases for the development of
any data compression algorithm for a variety of data,
Questions-Answers
|__Long Answer Type and Medium Answer Type Questions
Que 1.1, ] What is data compression and why we need it? Explain
compression and reconstruction with the help of block diagram.
UPTU 2013-14 Marks 05
UPTU 2016-16, Marks 02
UPTU 2015-16, Marks 10
Angwer
1. In computer science and information theory, data compression is the
process of encoding information using fewer bits than a decoded
representation would use through use of specific encoding schemes.
It is the art or science of representing information in a compact form
‘This compaction of information is done by identifying the structure that
exists in the data
3. Compressed data communication only works when both the sender and
the receiver of the information understand the encoding scheme
4 For example, any text makes sense only if the receiver understands
that itis intended tobe interpreted as characters representing nls
languags
5. Similarly, the compressed data can only be understood if the decoding
method is known by the receiver. 6 (csars)D Introduction
Need of data compression :
1. Compression is needed hecause it helps to reduce the consumption of
expensive resources such as alhard disk space or transmission bandwidth,
[Asan uncompressed text or multimedia (speech, image or video) data
requires a huge amount of bits to represent them and thus require large
bandwidth, this storage space and bandwidth requirement can be
decreased by applying proper encoding scheme for compression.
3. Thedesign of data compression schemes involves trade off among verious
factors including the degree of compression, the amount of distortion,
introduced and the computational resources required to compress and
decompress the data.
Compression and reconstruction :
1. Acompression teclanique or compression algorithm refers two algorithms
.e., compression algorithm and reconstruction algorithm.
2 The compression algorithm takes an input X and generates a
representation X, that requires fewer bits, and the reconstruction
algorithm operates on the compressed representation X, to generate
the reconstruction Y. These operations are shown in Fig. 1.1.1
aa ie Taconstract
QacTS. | What do you mean by data compression ? Explain its
UPTU 2011-12, Marks 05
5D, Unit-1
application areas.
Data compression : Refer Q. 1.1, Poue
Applications of data compression
1 Audio
sn bandwidth and
‘8. Audio data compression reduces the transmission band
storage requirements of audio data,
Data Compression 7(CSAT-8) D
b. Audio compression algorithms are implemented in software as audio
codec:
© Lossy audio compression algorithms provide higher compression at
the cost of fidelity and are used in numerous audio applications.
4d. ‘These algorithms rely on psychoacousties to eliminate or reduce
fidelity ofless audible sounds, thereby reducing the space required
to store or transmit them.
2 Video!
4. Video compression uses medera coding techniques to reduce
redundancy in video data.
b. Most video compression algorithms and codees combine spatial image
compression and temporal motion compensation.
& _ Video compression is a practical implementation of source coding in
information theory.
3. Geneties : Geneties compression algorithms are the latest generation
of lossless algorithms that compress data using both conventional
compression algorithms and genetic algorithms adapted to the specific
datatype.
4. Emulation :
4. In order to emulate CD-based consoles such as the Playstation 2,
data compression is desirable to reduce huge amounts of disk space
used by ISOs,
b. For example, Final Fantasy XII (Computer Game) is normally 2.9
sigabytes, With proper compression, itis reduced to around 90% of
Ge What do you understand by los:
compression ?
What do you mean by Jossl
compression with lossy compre:
ion, [UPTO 2011-12, Marks 05,
UPTU 2015-16, Marks 02
ewe]
Lossless compression
1. In lossless compression, the redundai
data is removed,
int information contained in the
Due to removal of auch information, there is na loss
interest. Hence it is called as lossless compressior ‘ ee 'SIT-8) D Introduction
3. Lossless compression is also known as data compaction
4, Lossless compression techniques, as their nam
of information,
5. Ifdatahave been losslessly compre:
exactly from the compressed data,
plies, involve no loss
1, the original data can be recovered
6 Lossless compression is generally used for applications that cannot
tolerate any difference between the original and reconstructed data.
‘Text compression is an important area for lossless compression.
8. Itisvery important that the reconstruetion is identical to the text original,
as very small differences ean result in statements with very different
meanings.
Lossy compression
1. Inthis type of compression, there is a loss of information in a controlled
2. ‘The lossy compression is therefore not completely reversible,
3. But the advantage of this type is higher compression ratios than the
lossless compre: “ion.
‘he losons compression i we frthe gal date
Sree pny applications, the loey eomprosson is prefered doe tit
ea regu a siifcan oe of mportantniormation
ean cel ato and video applications weneed standard compresin
gorithm
eee
eee tNcumpression techniques fvotve sone 1s of
eo oe ag unng ony techniques eeneraly Be
date Ch pa cconatruted exact)
Fee ere ee ing aie ditartion ithe reconstruction, we ca
* generally obtain much ‘higher compression ratios than is possible with
foticoacomprenion
QUeTAL | What is data compression and why we need it? Describe
'y compression technique is necessary
we applications where 158
= ‘UPTU 2014-15, Marks 10
for data compression
‘Answer
Data compression and its nee ee 8D.
lossy compression iS
lefer Q. 1.1, Page 5D, Unit
sary for
Applications where
‘compression s, to inerease
4 cam
sion ean be used in di
picture quality
1 Lossy imate oe ith minimal degradation
storage capacities with mi
Data Compression 9.CsIT-8)D
2, In lossy audio compres
remove non-audible (
methorls of psychoacoustics are used to
« less audible) components of the audio signal,
Que LS. | What is data compression and why we need it? Explain
compression and reconstruction with the help of block diagram.
What are the measures of performance of data compression
UPTU 2012-18, Marks 10
algorithms ?
oR,
What are the measures of performance of data compres:
UPTU 2018-14, Marks 05
algorithms ?
UPTU 2018-16, Marks 10
‘Answer
Data compression and its need : Refer Q. 1.1, Page 6D, Unit-1
Compression and reconstruction : Refer Q. 1.1, Page 6D, Unit-1
‘Measures of performance of data compression :
1. A compression algorithm can be evaluated in a number of different
2. Wecould measure the relative complexity of the algorithm, the memory
required to implement the algorithm, how fast the algorithm performs
ona given machine, the amount of compression, and how closely the
reconstruction resembles the original.
3, A very logical way of measuring how well a compression algorithm
compresses a given set of data is to look at the ratio of the number of its
required to represent the data before compression to the number of bits
required to represent the data after compression. This ratio isealled the
‘compression ratio,
4. Another way of reporting compression performance is to provide the
average number of bits required to represent a single sample.
5, ‘This is generally referred to as the rate.
6. _ In lossy compression, the reconstruction differs from the original dats
‘Therefore, in order to determine the efficiency of a compression
algorithm, we have to have some way of quantifying the difference
& The difference between the original and the reconstruction is efter
called the distortion.
9. Lossy techniques are generally used for the compre
ich as speech and video.
sion of data that
rnalog signals:
to. Incompression of speech and video, the final arbiter of quality sam? 10(CS1T-8) D
a.
Introduction
Secause human responses are difficult to model mathematically, many
approximate measures of distortion are used to determine the quality of
the reconstructed waveforms,
Other terms that are also used ab
ut differences between the
reconstruction and the original are fidelity and quality,
When the fidelity or quality, of a reconstruction is high, the difference
between the reconstruction and the original is small,
Que 16. | Explain modeling and coding with the help of suitable
example.
penn
‘UPTU 2013-14, Marks 05
‘The development of any data compression algorithm for a variety of data can
be divided into two phases : Modeling and Coding,
a
Modeling
a. Inthis phase, we try to extract information about any redundancy.
or similarity that exist in the data and describe the redundancy of
data in the form of model.
‘This model act as the basis of any data compression algorithm and
‘the performance of any algorithms will depend on how well the
model is being formed,
Coding:
8. This is the second phase. It is the description of the model and a
description of how the data different from the model are encoded,
generally encoding is done using binary digits.
Example
Consider the following sequence of number
‘9, 10, 11, 12, 13
By examining and exploiting the structure of data in a graph paper
it seems to be a straight line, so we modeled it with the equation,
xant9 | n=0,1,2.0
PART-2 .
Mathematical Preliminaries for Lossless Compression : A Brief
Introduction to Information Theory, Models : Physical Models,
Probability Models, Markov Models, Composite Source Model.
Data Compression
11(csar-s) D
CONCEPT OUTLINE : PART-2
‘A fundamental limit to lossless data compression is called entropy
rate.
Entropy is the measure of the uncertainty associated with a
random variable,
Physical model, probability mode! and Markov model are the
three approaches for building mathematical model,
ae
Long Answer Type and Medium Answer Type Questions
Que LF, | Explain entropy or entropy rate as given by Shannon.
1
In information theory, entropy is the measure of the uncertainty
associated with arandom variable.
tis usually refer to as Shannon entropy, which quant
of an expected value, the
tunits such as bit
's,in the sense
formation contained in a message usually in
Shannon entropy isa measure of the average information content ie,
fhe average nutber af binary symbol needed to code the outpat of the
Shannon entropy represents an absolute imiton the best possible lossless
Compression of ny communication ander cotain consents eating
tmestage to be encoded au'a sequence of independent and idontica
distributed random variable. i a
‘The entropy rate ofa source it number which depends only on the
statistical nature of the source. Consider an arbitrary couree
X= KX Ky Xd
Following are various modus
1. Zeroorder model: The characters are statistically independent o
each other and every letter of alphabet are equally teas tocceen
Let m be the size of the alphabet, In this ease, the entrope tat
given by . peeses
H = log, m bitveharacter
For example, if the alphabet size fs m
would be
27 then the entropy rate
H «tog, 12(CSAT-8) D
Introduction
fi First order model : The character are statistically independent
Pee be the size of the alphabet and let Pis the prebabiliey ofthe
# letter in the alphabet. The entropy rate
H= ~)' Flog, P bits/character
Hi. Second order thodel: Let P,,,be the conditional probability that
the present character is the * fetter in the alphabet given that the
Previous character is the "letter, The entropy rates
H= PSP, log, Py bitscharactor
iv. Third order model : Let P,.., be the conditional probability that
the present character is the "letter in the alphabet given that the
previous character is the letter and the one hefore that is the”
letter. The entropy rate is,
He DPZ Fy 6, Pay. bitscharacter
General model : Let B, represents the first n characters. The
entropy rate in the general ease is given by,
H = “tim PU jog, PC, bittcharacter
Que 1.8. ] 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.
=a
m a
Pa a
1 oe
2 s 16
21 204
p= 21 at
“ 16° 8 168
204 21
12 20d poe 22
oa 168 168
21 1
pve 222 Pao
i6"s is
H= -DPWlog, PO
Data Compression 13 (CS'T-8) D.
ee ia 4)
2 tog, +] +6) 21
[sista eee
3.25 bits
Que 1.9. | What do you understand by information and entropy ?
Find the first order entropy over alphabet A = (a,.a,,ay a,) where
Pla,)= Pla.) =Pla,) = Pla) = V4. UPTU 2018-14, Marks 05
“Answer
Information :
1
2
‘The amount of information conveyed by a message increases as the
amount of uncertainity regarding the message becomes greater,
‘The more it is known about the message a source will produce. the less
the uncertainity, and less the information conveyed.
The entropy of communication theory is a measure of this uncertainity
conveyed by a message from a source.
‘The starting point of information theory is the concept of uncertainity.
Let us define an event as an occurrence which ean result in one of the
many possible outcomes.
‘The outcome of the event is known only after it has occurred, and
before its occurrence we do not know which one of the several possible
outcomes will actually result.
We are thus uncertain with regard to the outcome before the occurrence
of the event.
After the event has occurred, we are no longer uncertain about it.
If we know or can assign a probability to each one of the outcomes, then
We will have some information as to which one of the outcomes is most
likely to oceur,
Entropy : Refer Q. 1.7, Page IID, Unit-1
Numerical
First order entropy is given by,
He Sri, Po 14(CSAT-8) D Introduction
Que 110, | Prove that the average codeword length ! of an optimal
code for a source $ is greater than or equal to entropy H(S).
1. According to Kraft- McMillan, if we have uniquely decodable code C with
‘k codeword then the following inequality holds
é
De" et «1.10.1
2 It states that if we have a sequence of positive integers (ify whieh
satisfy equation (1.10.1). Consider a source S with alphabet A
"a, and probability model {Pta,), PCa,),
average codeword length is given by
&
7 = Ptah
3, Therefore, the difference between entropy of the source H(S) and the
average length as,
= les yy
{Pla ie the
» &
— E Pea ogs Play ¥ Pra,
Hs) ~
= Ee ora eas |-4)
A. f 1 sip)
. Sreo{ teal as logat2! 1}
* 2h
= Sreptoes| 25] « toy
a i * lity, which states
last inequality is obtained using Jensen's inequality,
“That ffi i's concave function, then BYUO] = /UELXD, The lg function
ieaconeave function,
AAs the code is an optimal code
hence
itted and received
Que 111, ] The joint probabilities of the transmitted and
message of a communication system is given as
Data Compression 15 (CST) D
y, eee le
ee On aio =e
Px! xX, ° ua 0 20
x ° o 010
= oot
bs ° ° m0
Calculate HOD and HG).
a
iit
xiat efoto
Ae
2) 0 | 0 |asio|is20
| 0 fasa0 [0° Jarte
ele | o ira
Given:
= PUK, Togs (UPS PX, log, [UP
"SPO, Tog, LUP LX Ie POE) tow, EPOX
273) logs LPO
= 0.36 og, (70.35) + 0:2 10g, (103) "F Oab i,
70.15) 0.8 lg, U0.) + 0.08 tog 0.008
= 0.5201 so.5211'r 04105 + 0.4105 + 82164
1100) = 2.0883 Vitamensaye
PY) = Varo's 00205 0.25
PY) 04 U4 sos no rOc 08
RY) =Vi0-r0+ 110+0-r0202
PUD = 0+ 17202 1202 10+ 180 = 0.25
HG) = PLY, og, (UP s PUY) Togs VAY.)
* POP) tog, LU pte PEE) Yous PLY
= 0.25 log, (/0.25) + 0.3 log, (10.3) + 02 log, *
(0/02) * 0.25 log, (110.25) *
8.5000 + 0.5211 0.4644» 0.500
BC = 1.9855 hitstmensage * °5000
Que TAZ] What do you understand by inform:
Give an alphabet A =a,
following eases :
i Pla) = 12, Pla, = V4, Pra,
Similarly,
ion and entropy ?
14 @y@,). find the first-order « -tropy in the
2) = Pla,
vs vxtuetion
16(CSAT-8) D
Hi. P(a,) =0.505, Pla,) = 1/4, Pla.) = V8and Pla,) = 0.12.
And also differentiate between static length and variable length
coding schemes. Explain with the help of examples.
UPTU 2012-18, Marks 10)
oR
Differentiate between static length and variable length coding
scheme. Explain with the help of an example.
UPTU 201-12, Marks 05
UPTU 2015-16, Marks 10
“Answer
Information and entropy : Refer Q. 1.7, Page 11D, Unit-1
irst-order entropy is given by,
fa Lioe by Log E 1
p= hog, jogs ++ tog, 4+ tog, +
dee alae aides eee s
1 1 1 1
Jiog.2+ + hog. 8+} to, 8
log, 2+ blog, 4+ Slog. 8+ 5
et
bits
+34
5
& Pa,) = 0.505, Pia,)= 2, Pia) 1 and Pa,)=0.12
q 3
I Lge, 1H igg, 2
[0.505 og, 0.505 +1 tog, } + ¥ tog, 4+ 0.12 log, 0.12
1 -[0805 10g, 0.805 + Fog, 4 + toa $+ 0.12 0g, 0.12]
= 10.505(- 0.985684) + 0.25(-2)
Fongse2) +0. 3.00)
*Lodo776~0.5-0.375~0,266) = 1.79875
Difference between static length and variable length coding
ochemes
Static length codes:
1. Static length codes are also known as fixed length codes. A fixed length
tod is one whose codeword length is fed
2 The ASCITcode forthe letter‘ i= 1000011 and forthe letter ‘Ais coded
1000001
Here, it should be notice thatthe ASCII code uses the same numberof
bitsto represent cach symbel, Such codes are called static or Mae length
codes.
Variable length codes
1. A variable tength code i © codeword length is not fixed.
2 For example, consider a table given bel
Data Compression wesars)D
Z| Gedet [Coded [Codes
7 0 0 °
ra oL 1 10
ra 10, 00 110
= it nt hi
In this table, code 1 is fixed length code and code 2 and code 3 are variable
Tength codes.
Que 115. ] What is average information ? What are the properties
used in measure of average information ? [UPTU 2011-12, Marks 05)
UPTU 2015-16, Marks10
al
Average information :
1. Average information is also called as entropy,
2. Ifwe havea set of independent events A,, which are the set of outcomes
of some experiments S, such that
Uses
where S is the sample space, then the average self-information associated
with the random experiment is given by,
H = SP(A) i(A,) = -2P\A) log, PA)
8. ‘The quantity is called the entropy associated with the experiment.
4. One of the many contributions of Shannon was that he showed that if
the experiment is a source that puts out symbol A, from a set A, then the
entropy is a measure of the average number of binary symbols needed
to code the output of the souree.
5. Shannon showed that the best that a lossless compression scheme can
do is to encode the output of a source with an average number of bits
‘equal to the entropy of the source.
Given a set of independent events A,, Ay, .... A, with probability
P, = PIA), the following properties are used in the measure of average
information H:
1. We want / to be a continuous function of the probabilities p,. That is, a
small change in p, should only cause a small change in the average
information
Ifall events are equally likely, that is, p,= Vn for all i, then H should be
4 monotonically inereasing function of n. The more possible outeomes
there are, the more information should be contained in the occurrence
of any particular outcome. 18 (CSAT-8) D
Introduction
3. Suppose we divide the possible outcomes into a number of groups. We
indicate the occurrence of a particular event by first indicating the group
it belongs to, then indicating which particular member of the group it is,
4
‘Thus, we get some information first by knowing which group the event
belongs to and then we get additional information by learning which
particular event (from the events in the group) has occurred. ‘The
information associated with indicating the outcome in a single stage,
TETRA] explain ditterent approaches for building mathematical
model also define two state Markov model for
inary images.
UPTU 2014-15, Marko
[UPTUB011-13; Marks 05
UPTU 2015-16, Marks 10]
There are several approaches to building mathematical models
Physical models
1 In speech-related applications, knowledge about the physics of speech
production canbe weed to construct a mathematical model for the sampled
Speech process, Sampled speech can then be encoded using this model
2. Modelsfor certain telemetry data can also be obtained through knowledge
ofthe underiving process
2. Forexample,ifresidential electrical meter readings at hourly intervals
were to be coded, knowledge about the living habits of the populace
Could be used to determine when electricity ssage would be high and
‘when the usage would be low. Then instead of the actaal readings, the
difference (residual) between the actual readings and those predicted
by the model could be coded.
Probability models : seven
1. The simplest statistical model for the source is te assume that exc
letter that is generated by the source le independent of every other
letter, and each occurs with the same probability
2 We could call this the ignorance model, a it would generally be useful
only when we know nothing. about the source. The next step up in
Comple-ity i to Keep the dere" -” axsumption, but remove the
equal probability assur salty of occurrence to
cach letter in the alphabet
3. For asource that generates letters from an alphabet A = lay. 4g) sh
wecan have a probability model P = [Pa,). Pa, ).... Play
4. Given a probability model (and the independence assumption). we can
compute the entropy of the source using equation 1.14.1)
Data Compression 19 (CSAT-8) D
H(s) = ~SP(X,) log PUX,) oALA4D)
5. We canalso construct some very efficient codes to represent the letters
ina.
6. Ofcourse, these codes are only efficient if our mathematical assumptions
are in accord with reality,
Markov models :
L
One of the most popular ways of representing dependence in the data is
through the use of Markov models,
2 Formodels used in lossless compression, we use a specific type of Markov
process called a discrete time Markov chain,
3. Let (x,) bea sequence of observations. This sequence is said to follow a
order Markov model if
Pyle yes act) Pg Lg pee pgp eed 1142)
4
In other words, knowledge of the past £ symbols is equivalent to the
knowledge of the entire past history of the process.
5. he values taken on by the set (x, ,,... x, 4) are called the states of the
process. Ifthe size of the source alphabet is, then the number of states
isl
‘The most commonly used Markov model isthe first-order Markov model,
for which
Pe, |x,..) = Poe, |,
Equations (1.14.2) and (1.14.3)
between samples.
not Baa gy oo)
44a)
) indicate the existence of dependence
8. However, they do not describe the form of the dependence. We can
develop different first-order Markov models depending on oar
assumption about the form of the dependence between samples
we assumed that the dependence was introduced in a linear manner,
we could view the data sequence as the outputofa linear i
woeould vie - put of alinear filter driven by
10, The output of such a filter can be given by the difference equation,
x7 Or te,
where ©, is a white noise process. This mod.
developing coding algorithen
Jl doe ni ree the asp near
12. Forexample, : a *
& Consider a binary ima
b. The image has only two types of pixel
a es of pixels, white pixel
Sand black 2018-8) D
© We know that the appearance of a white pixel as the next
observation depends, to some extent, on whether the current pixel
is white or black,
‘Therefore, we ean model the pixel process as a discrete time Markov
chain,
©. Define two states S, and S, (S, would correspond to the ease where
the current pixel is a white pixel, and S, corresponds to the ease
‘where the current pixel is a black pixel).
f. We define the transition probabilities Puo/b) and Ptbiw), and the
probability of being in each state P(S,) and AS,), The Markov
‘model can then be represented by thé state diagram shown in
Fig. LULL
The entropy of a finite state process with states S, is simply the
average value of the entropy at each state
a= SpsyHs)
roi (2) CY) mow
Fer
Fig. L241A fio state Markov made! for binary ime)
h. For our particular example ofa binary image
HS.) = —Plbhe) log Ptb fu) ~ Plulw) log Pele)
Pho) = 1- Ptblw). HIS,) can be calculated ina similar
caaasy
PEblw)
where
Composite source model
sions, it isnot easy to use a single model to describe the
1 Inmany applic
In auch cases, we can define a composite source, whiehcan be viewed aa
7 a combination or composition of several sources, with only one source.
Eng active at any given time
8. Acomposite source can be represented as a number afindividual sources,
teach with its own model Mand a switeh that selects a source S, with
probability P,(as shown in Fig, 1.14.2).
21 (CSAT-8)
Data Compression
Source 1
aoe
Source2 fe
Source n [—*
Fig. 1.14.2, A composite sovree.
4. This is an exceptionally rich model and ean be used to deseribe some
very complicated processes.
Que TAS: | What is zero frequency model in Markov models in text
compression ?
UPTU 2013-14 Marks 05
UPTU 2015-16, Marks 05)
‘Answer
As expected, Markov models are particularly useful in text compression,
where the probability of the next letter is heavily influenced by the
preceding letters,
2 Ineurrent text compression literature, the kth-order Markov models
are more widely known as finite context models.
3. Consider the word preceding.
4
Suppose we have already processed preceding and are going t enode
the next letter, : fons
5. Itwetake no account of
the probability of the lett
{fwe use a first-order Markov model or single-letter context (that is, we
look at the probability model given n), we ean see that the probability of
@ would increase substantially.
‘As we increase the cont
probability of the al
results in lower entr:
the context and treat each letter as a surprise,
fer g occurring is relatively low.
text size (go from n to in to din and so on), the
Iphabet becomes more and more skewed, which
py.
‘The longer the context, the better its predictive value.
Itwe were to store the
a given length, the nut
the length of context.
Consider a context model ofo
last four symbols)
probability model with respect to all contexts of
imber of contexts would grow exponentially with
yrder four (the contextis determined by the
If we take an alphabet size of 95, the possible number of contexts is 95
(more than 81 milli 22 (CS1T-#) D Introduction
12, Context modeling in text compression schemes tends to be an adaptive
strategy in which the probabilities for different symbols in the different
contexts are updated as they are encountered,
13. However, this means that we will often encounter symbols that have
not been encountered before for any of the given contexts (this is known
as the zero Frequeney problem),
14. The larger the context, the more often this will happen.
15. This problem could be resolved by sending a code to indicate that the
following symbol was being encountered for the first time, followed by a
prearranged code for that symbol
16. This would significantly increase the length of the eode for the symbol,
onits first occurrence
17. However, ifthis situation did not occur too often, the overhead associated
with such occurrences would be small compared to the total number of
bits used to encode the output of the source.
18. Unfortunately. in context-based encoding, the zero frequency problem
is encountered often enough for overhead to be a problem, especially
for longer contexts.
ares
Cain : Unite BBG Cle Pres Coen
CONCEPT OUTLINE : PART-2
> Acode is uniquely decodable ifthe mapping C= A,"—>A,"is one
| tone, that is, v, and’ in A,*, x#x'=> C2) 2 Cx).
+ A code C is a prefix code if no codeword w, is the prefix to
‘another codeword w, (rj).
LL yond
“Long Answer Type and Medium Answer Type Questions
Que 116. | Write a short note on coding. What do you understand
by uniquely decodable codes ?
|
1. Coding means the assignment of binary sequences to elements of an
alphabet
2. The set of binary sequences is ealled a code, and the individual members
ofthe set are called codewords.
3, Analphabet is a collection of symbols called letter,
Data Compression 25 (CST) D
4, The ASCTT code uses the same number of its to represent each symbol.
5. Such a code is ealled a fixed-length code,
6. If we want to reduce the number of bits required to represent different
messages, we need to use a different number ofits to represent different
symbols.
7. If we use fewer bits to represent symbols that occur more often, om the
average we would use fewer bits per symbol.
8, The average number of bits per symbol is often called the rate of the
code.
‘Uniquely decodable codes
1, -Acode is uniquely decodable ifthe mapping C":A", +A”, is one to one,
that is, \y sands! in t,x 2272 C' (e) eC’).
2. Suppose we have two binary codeword a and 6 where a is’ bit longand
b is'm bit long, / Pla,), then
4, Sly where jis the number of bits in the codeword for a,
b. Condition 2: The two least probable letters have codewords with
the same maximum length /,
© Condition 3 : In the tree corresponding to the optimum code,
there must be two branches stemming from each intermediate
node.
If there were any intermediate node with only one branch coming
from that node, we could remove it without affecting the
decipherability of the code while reducing its average length,
4 Condition 4 : Suppose we change an intermediate node into aleaf
node by combining all the leaves descending from it into a composite
word ofa reducing alphabet. Then, if the original tree was optimal
for the original alphabet, the reduced tree is optimal for the reduced
alphabet.
QESRET] Write u short note on non-binary Huffman code.
1. The binary Huffman coding procedure can be easily extended to the
non-binary case where the code elements come from an m-ary alphabet,
‘mis not equal to two,
2 We obtained the Huffman algorithm based on the observations that in
an optimum binary prefix code and the requirement that the two symbols
with the lowest probability differ only in the last position.
8. Symbols that occur more frequently (have a higher probability of
occurrence) will have shorter codewords than symbols that occur
less frequently, and
b. The two symbols that occur Ic ast frequently will have the same
length,
8, We can obtain a non-binary Huffman code in almost exactly the same
Data Compression
4. ‘The obvious thing to do would be to modify
read : “The m symt
length,” and also modify
Eee
Step 1 :Sort all symbols according to their probabilities :
B
01
Step 2: Build the tree.
a. Pick two symbols with the lowest.
oot as the sum of the two and m:
A
016
D
oa
child and the other as right child of root.
b. Here two smallest nodes are C and E
respectively,
© Again arrange it into the ori
original list.
B
051
CE
0.20
oO) Xen)
Repeating step 2, we get,
raking lowest fre
the second observation
bol that occur least frequently will have the sex
the additional requirement to read "Then |
symbols with the lowest probability differ only in the last position
Que 27] Consider the source
probabilities P(A) = 0.16, P(B) =0.51, P©
Design the Huffman code.
Iphabet A, B, C, D,
B
out
frequency count and form atree with
quency symbol as ale
with probabilities 0.09 and 0.11
iginal list and delete the children from the pao) Huffman Coding.
B CEDA
ost 0.47
Step 3: Label left branches of the tree with 0 and right branche:
with 1
ofthe tree
Data Compression 99 (CSAT-8) D
Step 4 : Create Huffman code by traversing from the root to leaf.
Srmbal a
. B 1
fa
: ae
7 oa
: od
Considering the following source alphabet and their
frequencies. Create the Huffman trev and calculate the avereee
lengths of tho sade
Tee]
Applying Huffman algorithm, tree formed is : 40 (CSITT-8) D
Huffman Coding.
PART-2 |
CONCEPT OUTLINE
* Adaptive Huffman coding : In adaptive Huffman coding
procedure, neither transmitter nor receiver kriows anything
about statistic of the source sequenee at the start of transmission,
‘+ Update procedure : The update procedure requires that the
nodes be in a fixed order. This ordering is preserved by
numbering the nodes.
Questions-Answers
‘Long Answer Type and Medium Answer Type Questions
ive Huffman coding.
Data Compression
Answer
10
4,
13,
M4,
Hultnan coding requires knowledge of the probabilities ofthe sar
sequence. ”
1f this knowledge is not available, Huffian coding becomes two
Procedure: the stasis are collected in the fist pasando
encoded in the second pass. |
In order to convert this algorithm into a one-pass procedure, Faller an |
Gallaher independently developed adaptive algorithms to construc hg
Huffman code based on the statistics of the first symbule alcagy |
encountered. |
‘Theoretically, if we wanted to encode the (k + 1th symbol using the
statistics of the first # symbols, we could recompute the code usin the
Huffman coding procedure each time a symbol is transmitted,
However, this would not be a very practical approach due to the large
‘amount of computation involved—hence, the adaptive Huffman coding
procedure.
In order to describe how the adaptive Huffman code works, we add two
other parameters to the binary tree : the weight of each leaf, which
written as a number inside the node, and a node number.
‘The weight of each external node is simply the number of times the
symbol corresponding to the leaf has been encountered.
‘The weight of each internal node is the sumof the weights ofits offspring
‘The node number y, is a unique number assigned to each internal and
external node.
If'we have an alphabet of size n, then the 2n — 1 internal and external
node can be numbered as yy)... 5 ¥oq- Such that if x, is the weight of
node yp we have x,
