2.

Information Theory and Source Coding

2.1 What is Information
2.2 Information Content
2.3 Types of Source Coding
2.4 Design of Source Codes
2.5 Coding for Analog Sources

3/5/2026 1
2.1 What is Information

 Information sources may be analog or discrete or digital

 Analog sources: Audio or video
 Discrete sources: Computers, storage devices such as magnetic or
optical devices
 Whatever the nature of the information sources, digital
communication systems are designed to transmit
information in digital form
 Thus, the output of sources must be converted into a format
that can be transmitted digitally

3/5/2026 2
Source Coding …
 This conversion is generally performed by the source encoder,
 Whose output may generally be assumed to be a sequence
of binary digits
 Encoding is based on
 Mathematical models of information sources and
 The quantitative measure of information emitted by a source
 We shall first develop mathematical models for information
sources

3/5/2026 3
Mathematical Models for Information Sources
 Any information source produces an output that is random
and which can be characterized in statistical terms
 A simple discrete source emits a sequence of letters from a
finite alphabet
 Example:
 A binary source produces a binary sequence such as
1011000101100; alphabet: {0,1}
 Generally, a discrete information with an alphabet of L possible letters
produces a sequence of letters selected from this alphabet

 Assume that each letter of the alphabet has a probability of

occurrence pk such that
pk =P{X = xk}, 1≤ k ≤ L; and
∑ pk = 1
3/5/2026 4
Two Source Models
1. Discrete Sources
• Discrete Memoryless source (DMS): Output sequences from the
source are statistically independent
• Current output does not depend on any of the past outputs

• Stationary source: The discrete source outputs are statistically

dependent but statistically stationary
• That is, two sequences of length n, (a1, a2, …..an) and (a1+m, a2+m,
…..an+m) each have joint probabilities that are identical for all n  1 and
for all shifts m

2. Analog sources
• Has an output waveform x(t) that is a sample function of a stochastic
process X(t),

• Where we assume X(t) is a stationary process with autocorrelation

Rxx(τ) and power spectral density Φxx(f)
3/5/2026 5
Mathematical Models …
 When X(t) is band limited stochastic process such that
Φxx(f) = 0 for │f│≥ W; by the sampling theorem
n
 s i n ( 2  W (t  )
n
X (t)   X (
2w
)
n
2W
n
2  W (t  )
2W

 Where {X(n/2W} denote the samples of the process at the

sampling rate (Nyquist rate) of fs = 2W samples/s

 Thus, applying the sampling theorem, we may convert the

output of an analog source into an equivalent discrete-
time source

3/5/2026 6
Mathematical Models …
 The output is statistically characterized by the joint pdf
p(x1, x2 , …xm) for m ≥ 1 where xn=X(n/2W); 1≤ n ≤m, are
the random variables corresponding to the samples of
X(t)
 Note that the samples {X(n/2W} are in general
continuous and cannot be represented digitally without
loss of precision
 Quantization may be used such that each sample is a
discrete value, but it introduces distortion
 Called quantization error or quantization noise

3/5/2026 7
2.2 Information Content
 Consider two discrete random variables X and Y such that
X = {x1, x2,……xn} and Y = {y1,y2,…….ym}
 Suppose we observe Y = yj and wish to determine,
quantitatively, the amount of information Y = yj provides
about the event
X = xi , i = 1,2,…..n
 Note that if X and Y are statistically independent Y = yj
provides no information about the occurrence of X = xi
 If they are fully dependent Y = yj determines the
occurrence of X = xi
 The information content is simply that provided by X = xi

3/5/2026 8
Logarithmic Measure of Information …
 A suitable measure that satisfies these conditions is the
logarithm of the ratio of the conditional probabilities
P{X = xi│Y = yj} = P{xi│yj} and P{X = xi} = p(xi)
 Information content provided by the occurrence of Y =
yj about the event X = xi is defined as
P ( xi / y j )
I (xi , y j )  log
P( xi )

 I(xi , yj) is called the mutual information between xi and yj

 Unit of the information measure is the nat(s) if the natural
logarithm is used and bit(s) if base 2 is used
 Note that ln a = ln 2. log2a = 0.69315 log2a

3/5/2026 9
Logarithmic Measure of Information …
 If X and Y are independent I(xi , yj) = 0
 If the occurrence of Y = yj uniquely determines the
occurrence of X = xi ,
I(xi , yj) = log (1/ p(xi))
 i.e., I(xi , yj) = -log p(xi) = I(xi) – Self information of the event X
 Note that a high probability event conveys less information
than a low probability event
 For a single event x where p(x) = 1, I(x) = 0 the occurrence
of a sure event does not convey any information
 If p(x) ≈ 0, I(x) ≈ ∞ the occurrence of a null event does
convey much information

3/5/2026 10
Logarithmic Measure of Information …
Example
1. A binary source emits either 0 or 1 every τs seconds with
equal probability.
• Information content of each output is then given by
I(xi) = -log2 p = -log2 1/2 = 1 bit, xi = 0,1
2. Suppose successive outputs are statistically
independent (DMS) and consider a block of binary digits
from the source in time interval kτs.
• Possible number of k-bit block = 2k = M, each of
which is equally probable with probability 1/M = 2-k
I(xi) = -log22-k. = k bits in kτs sec
(Note the additive property)
3/5/2026 11
Logarithmic Measure of Information …
 Now consider the following relationships

p( xi y j ) p(xi y j )p(yj ) p(xi , y j )

I(xi , y j )  log  log  log
p( xi ) p(xi )p(y j ) p(xi )p(y j )
 and since p(xi , y j )
p(y j xi ) 
p(x j)
p(yj x)
i
I(xi ,yj ) I(yj ,xi )
p(yj )

 Information provided by yj about xi is the same as that

provided by xi about Y = yj.

3/5/2026 12
 Logarithmic Measure of Information …
• Using the same procedure as before we can also define
conditional self- information as
1
I(xi y j )  log 2   log 2 p (xi y j )
p (xi y j )
 Now consider the following relationships
 p( xi y j ) p( x i ) 
log    I ( xi , y j )  I ( xi )
 p( x i ) 
 Which leads to I(xi,yj )  I(xi )I(xi yj )
 Note that I(xi yj ) is self information about X = xi after having
observed the event Y = yj

3/5/2026 13
Logarithmic Measure of Information …
 Further, note that I (xi )  0 I(xi y j )0 and thus
and I ( x i , y j )  0 w h e n I (xi )  I (xi y j )

 Indicating that the mutual information between two events

can either be positive or negative

3/5/2026 14
 Average Mutual Information
 Average mutual information between X and Y is given by
n m n m p(xi , y j )
I(X; Y)   p(x i , y j ) I(x i , y j )   p(xi , y j )log 2 0
i1 j1 i1 j1 p(xi ) p( y j )

 Similarly, average self-information is given by

H (X)  p(xi )I (xi )    p(xi ) log 2 p(xi )

 Where X represents the alphabet of possible output letters

from a source
 H(X) represents the average self information per source
letter and is called the entropy of the source
3/5/2026 15
Average Mutual Information …
 If p(xi) = 1/n for all i, then the entropy of the source
becomes 1 1
H (X)    log
2
 log n
2
n n

 In general, H(X) ≤ log n for any given set of source letter

probabilities
 Thus, the entropy of a discrete source is maximum when the output
letters are all equally probable

3/5/2026 16
Average Mutual Information …
 Consider a binary source where the letters {0,1} are independent
with probabilities
p(x0=0)=q or 1, p(x1=1)=1-q
 Then the entropy of the source is given by
H(X)= -q log2q – (1-q) log2(1-q) = H(q)
 whose plot as a function of q is shown below
Binary Entropy Function

3/5/2026 17
 Average Mutual Information …
 In a similar manner as above, we can define conditional
self-information or conditional entropy as follows
n m
1
H(X / Y)   p(xi , y j ) log
i1 j1 p(xi / y j )
 Conditional entropy is the information or uncertainty in X
after Y is observed
 From the definition of average mutual information one can
show that
n
I(X, Y)  
m
 
p( x i , y j ) log p( x i / y j )  log p( x i )
i 1 j 1

  H (X/Y)  H ( X )

3/5/2026 18
Average Mutual Information …
 Thus I(X,Y) = H(X) – H(X/Y) and H(X) ≥ H(X|Y), with
equality when X and Y are independent.
 H(X/Y) is called the equivocation
 It is interpreted as the amount of average uncertainty
remaining in X after observation of Y

3/5/2026 19
Average Mutual Information …
 H(x) – Average uncertainty prior to observation
 I(X;Y) – Average information provided about the set X
by the observation of the set Y
 The above results can be generalized for more than
two random variable
 Suppose we have a block of k random variables
x1,x2,…..xk with joint probability P(x1,x2,…..xk); the
entropy of the block will then be given by
n1 n2 nk

H(X) .. P(xj1,xj2......xjk ) log P(xj1,xj2......xjk )

j1 j2 jk

3/5/2026 20
Continuous Random Variables - Information Measure

 The concept of self information does not exactly carry over to

continuous random variables
 Since these would require infinite number of binary digits to
exactly represent them and thus making their entropies infinite
 If X and Y be continuous random variables with joint pdf
f (x,y) and marginal pdf’s f (x) and f (y) the average Mutual
information between X and Y is defined as
 
f (y / x) f (x)
I (X,Y )   f (x) f (y / x) log dxdy
  f (x) f (y)

3/5/2026 21
 Continuous Random Variables …
 We can however define differential entropy for continuous
random variable as


H(x)  -  f (x) log f (x)dx



 And the average conditional entropy as

 

H(X /Y) -  f (x, y)log f (x|y)dxdy



 Average mutual information is then given by I(X,Y)= H(X) -

H(X/Y) or I(X,Y) = H(Y) - H(Y/X)

3/5/2026 22
 Continuous Random Variables …
 If X is discrete and Y is continuous, the density of Y is
expressed as n
f ( y)   f ( y / xi ) p(x i )
i1

 The mutual information about X = xi provided by the

occurrence of the event Y = y is given by
f (y/ xi )p(xi ) f (y/ xi )
I(xi ;Y)log log
f (y)p(xi ) f (y)
 The average mutual information between X and Y is
n 
f ( y / xi )
I ( X ;Y)   f ( y / xi ) p(x i )log
i1  f ( y)

3/5/2026 23
2.3 Types of Source Coding
 We have seen that:
 Entropy H(X) of a source represents the average amount of
information emitted by the source
 Coding is the processes of representing the source output by a
sequence of binary digits

 Knowledge of H(X) does not directly help us in the design

of a coding algorithm
 However, it provides a measure of efficiency of a source-
encoding method by comparing the average number of binary
digits per source letter to the entropy of the source

3/5/2026 24
Coding for Discrete Sources …
 Encoding is simplified when the source is assumed to be
discrete memoryless source (DMS),
 i.e., symbols from the source are statistically
independent and each symbol is encoded separately

 Few sources closely fit this idealized model

 We will see:
1. Fixed-length vs. variable length encoding
2. Blocks of symbols vs. Symbol-by-symbol encoding

 It will be shown that it is always efficient to encode blocks

of symbols instead of each symbol separately

3/5/2026 25
Coding for DMS
 A DMS produces an output letter or symbol every s sec.
 Each letter is selected from an alphabet of symbols xi,
i=1,2,…..L, occurring with probabilities p(xi)
 Entropy of the DMS
L
H (X )    p( x i ) log 2 p(x i )  log 2 L
i1

 Where equality holds when the symbols are equally

probable
 The average number of source letters is H(X) and the
source rate is defined as
H (X )
s

3/5/2026 26
Coding for DMS - Fixed-Length Code Words
 Consider a block encoding scheme where a unique set of
R binary digits is assigned to each symbol or letter
 R defines the code rate in bits/symbol
 If there are L symbols, the number of binary digits per
source symbol required for unique encoding is given by

Rlog2 L, When L is a power of 2

OR
R log2 L 1, When L is not a power 2 and X denotes the largest integer
less than X

 Since H(X) ≤ log2 L, it follows that the code rate R

bits/symbol is greater than average entropy H(X)
 Thus H(X) is the lower bound of the rate R

3/5/2026 27
Coding for DMS - Fixed-Length Code Words …
 The efficiency of encoding is the ratio H(x)/R
 Note that:
1. If L is a power of 2 and the source letters are equally probable
R = H(X) and the code is 100% efficient
2. However, if L is not a power of 2 but the source letters are still
equi-probable, R differs from H(X) by at most 1 bit per symbol

 When L is large, the efficiency can be high

 On the other hand, when L is small the encoding efficiency
of fixed-length code can be increased by encoding a
sequence of J letters at a time which requires LJ unique
code words

3/5/2026 28
Coding for DMS - Fixed-Length Code Words …
 Using a sequence of N binary digits, we can encode 2N
possible source symbols uniquely
 N must be selected such that:
 N ≥ J log2L or
 N = J log2L +1 depending on whether L is a power of 2 or not

 The average number of bits per source symbol is N/J = R

 Hence, the inefficiency is reduced by approximately a
factor of 1/J relative to the symbol-by-symbol encoding
 By making J sufficiently large the encoding efficiency
measured by JH(X)/N can be made as close to unity as
desired

3/5/2026 29
Coding for DMS - Fixed-Length Code Words …
 Such encoding does not introduce any distortion since the
encoding of source symbols or blocks of symbols into
code words is unique
 Such encoding is referred to as noiseless
 Suppose we reduce the code rate R by relaxing the
condition that the encoding process be unique
 This results in decoding failure

3/5/2026 30
Source Coding Theorem I (Shannon, 1948)
 Let X be ensemble of letters from a DMS with entropy H(x)
 Consider blocks of symbols are encoded into code words
of length N from a binary alphabets
 For ε > 0 the probability of error pe of a block decoding
failure can be made arbitrarily small if
N
R  H (X )  and J is sufficiently large
J

 Conversely if
R  H(X)

 Then pe becomes arbitrarily close to one as J is made

sufficiently large

3/5/2026 31
Variable Length Code Words
 When source symbols are not equally probable, a more
efficient coding method is to use variable length code
words
 Motivation for variable-length codes is the ability to
achieve data compression by representing more probable
symbols by shorter bit sequences

3/5/2026 32
Variable Length Code Words …
 Variable-length source code C maps each source letter or
symbol to a binary sequence C(x) with code word length l(x)
 Code words are transmitted as a continuous sequence of
bits with no demarcation of code word boundaries
 The decoder, once given the starting point, must determine
where the code word boundaries are (Parsing)
 The system requires buffers at the input and output sides of
the synchronous channel and there are possibilities of
buffer overflow
 Thus, unique decodability requires initial synchronization and
the condition that C(x) C(x,, ) for each x different from x’

3/5/2026 33
Variable Length Code Words …
 For any source symbols x1, x2, …..xn, the concatenation of
code words C(x1) C(x2)……C(xn) differs from the
concatenation of the code words C(x1’)C(x2’)…….C(xn’) for
any other string x1’, x2’…..xn’
 (Note that there are no commas in between the encoded bit
sequences!)

3/5/2026 34
 Variable Length Code Words …
 Consider the following to see
certain characteristics of such
codes
 Consider the alphabet X = {a,b,c} Letter P(xk) Code I Code II Code III
that may coded as C(a) = 0, C(b)
a1 0.500 1 0 0
= 1, and C(c) = 01
 This code is not uniquely a2 0.250 00 10 01
decodable since the string 01
may be decoded as (a,b) or (c) a3 0.125 01 110 011
 Note that in the above code, the
code for (a) is a prefix of the
code for (c) and the code is said a4 0.125 10 111 111
to be NOT prefix free
 Now consider the variable-length
codes shown next for a four-
symbol source

3/5/2026 35
Variable Length Code Words …
 Code I is a variable length code that has a basic defect
 Consider the sequence 001001
 This can be decoded as a2a4a3 or a2a1a2a1
 It is not uniquely decodable

 This might be decoded uniquely if we have more bits

which will involve delay and render the code not
instantaneously decodable
 On the other hand, code II is uniquely and
instantaneously decodable
 0 indicates end of a code word for the first three code
words and no code is longer than three bits

3/5/2026 36
Variable Length Code Words …
 Not also that it satisfies the prefix-free condition;
 That is for a code Ck = (x1, x2, ….xk) there is no other code
word Cl(x) = (x1,x2,…..Xl) for 1 ≤ l ≤ k-1
 Code III is neither uniquely decodable nor instantaneously
decodable

3/5/2026 37
 c
a
a→0 a→0
b → 11 b → 11
c → 101 c → 10
 The prefix-free condition ensures that each code word
corresponds to a leaf node, since any intermediate node
represent a prefix of any leaf stemming from it
 Note the first code tree is not full since the string 100 does
not represent a code word
 This can be shortened without destroying the prefix-free
property as in the second tree diagram, which is full

3/5/2026 38
Variable Length Code Words …
 A prefix-free code can be decoded by simply reading a
string or a sequence from left to right and following the
corresponding path in the code tree until it reaches a leaf,
which represents a code word by the prefix free property
 Proceed after stripping off the first code word
 Consider decoding the string or sequence 1010011 using
the second code above: 10 → c;10 → c; 0 → a; 11 → b
 Thus, the sequence is decoded into ccab and there cannot
be any other set of letters into which the sequence can be
decoded
 Further, note that the code can be decoded essentially
without delay

3/5/2026 39
Variable Length Code Words …
 Devise a systematic procedure for constructing uniquely
decodable variable length codes that are efficient in the
sense that the average number of bits per source symbol
or letter, given as
 L
R   nk p (a k )
k 1

 is minimized
 Note that nk is length of the code word k
 The condition for the existence of such a code, that is
prefix-free, is given by the Kraft inequality and is presented
below

3/5/2026 40
Kraft Inequality
 A necessary and sufficient condition for the existence of a
binary code with code words having lengths n1 ≤ n2 ≤
n3…….≤ nL that satisfy the prefix (free) condition is
L
 2 n k

 1
k 1

 Alternatively, every prefix-free code with code word

lengths n1 ≤ n2 ≤ n3…….≤ nL satisfies the above
inequality
 And conversely, if the above inequality is satisfied, then
a prefix-free code with code lengths nk exists

3/5/2026 41
Kraft Inequality …
 In addition, every full prefix-free code satisfies the above
condition with equality whereas every non-full prefix-free
code satisfies it with strict inequality (see proof in the text)
 Note that the Kraft inequality tells us whether it is possible
to construct a prefix-free code for a given source alphabet
with a set of code word length, nk
 Example: A full prefix-free code for an alphabet size 3 with
code word lengths {1, 2, 2} exists, but there is no prefix-
free code with code word lengths {1, 1, 2} since this does
not satisfy the Kraft inequality

3/5/2026 42
2.4 Design of Source Codes
 Let X be ensemble of letters from a DMS with entropy H(x)
 It is possible to construct a code that satisfies the prefix
condition and has an average length that satisfies the
inequalities
_
H ( X )  R  H ( X ) 1

 For lower bound consider code words of length nk, 1 ≤ k ≤ L

_
1
H ( X )  R   p k log  n k p k
k pk k

2 n k
 p k log 2 and using ln x  x  1
k pk
_ 2 n k
H ( X )  R ( log 2 e )  pk ( 1) ( log 2 e )  (2 n k 1)  0
k pk k

3/5/2026 Called Source Coding Theorem 43

Huffman Encoding Algorithm

• The source symbols are listed in order of decreasing

probability.
• The two source symbols of lowest probability are assigned a 0
and a 1.
• These two source symbols are regarded as being combined
into a new source symbol with probability equal to the sum of
the two original probabilities.
• The probability of the new symbol is placed in the list in
accordance with its value.
• The procedure is repeated until we are left with a final list of
source statistics of only two for which a 0 and a 1 are assigned.
• The code for each (original) source symbol is found by working
backward and tracing the sequence of 0s and 1s assigned to
that symbol as well as its successors.

3/5/2026 44
Huffman Coding Algorithm
 The Huffman algorithm is a variable-length coding scheme
based on the source letter probabilities (pk), k = 1, 2,…..L
 The coding algorithm is optimum in the sense that the
average number of binary digits required to represent the
source letters is minimum
 This is subject to the constraint that they satisfy the prefix
condition and the sequence of code words are uniquely and
instantaneously decodable
 We shall illustrate the coding scheme using examples
 Example 1: Given seven source letters x1, x2, …..x7 with
probabilities 0.35, 0.30, 0.20, 0.10,0.04,0.005, 0.005,
respectively

3/5/2026 45
Huffman Coding Algorithm …
 An example of variable-length source encoding for a DMS
 Order the symbols in decreasing order of probabilities

3/5/2026 46
Huffman Coding Algorithm …
Letter Prob. I(x) Code
x1 0.35 1.5146 00
x2 0.30 1.7370 01
x3 0.20 2.3219 10
x4 0.10 3.3219 110
x5 0.04 4.6439 1110
x6 0.005 7.6439 11110
x7 0.005 7.6439 11111

H(X) = ∑p(xi)I(xi) = 2.11 R = ∑ p(xk) nk = 2.21

H(X ) 2.11
Efficiency   _  100%  95%
R 2.21

3/5/2026 47
Huffman Coding Algorithm …
 The above code is not necessarily
unique. We can devise an
alternative code as shown in the
following for the same source as
above
X1 0
X2 10
X3 110
X4 1110
X5 11110
X6 111110
X7 111111

An alternative code for the

 The average code word length is
the same as above (show?) DMS in the above example

3/5/2026 48
Huffman Coding Algorithm …
 Note that the assignment of 0 to the upper branch and 1 to
the lower branch is arbitrary and by reversing this we
obtain an equally efficient code that satisfies the prefix
condition
 The above procedure always results in a prefix free
variable length code that satisfy the bounds on the
average length code word R
 However, as discussed earlier, an efficient procedure is to
encode J letters or symbols at a time

3/5/2026 49
Huffman Coding Algorithm …
 As an illustration consider the following example
 Example: Let the output of a DMS consist of x1, x2 and x3
with probabilities 0.45, 0.35, 0.2, respectively
 Entropy of the source
3
H ( X )    p(xk ) log 2 p(xk ) 1.55 bits/symbol
K 1

 If these are encoded individually

 Using Huffman encoding procedure: x1--0, x2--10,and x3--11 with
an average code word length of 1.518 and an efficiency of 97.7%

3/5/2026 50
Huffman Coding Algorithm …
 If pairs of symbols are Letter Prob. I(X) Code
encoded using the pairs
Huffman algorithm, one x1 x1 0.2025 2.312 10
possible variable length
x1 x2 0.1575 2.676 001
code can be as given next
x2 x1 0.1575 2.676 010
 2H(x) = 3.036; R2 = x2 x2 0.1225 3.039 011
3.0675 and the efficiency
x1 x3 0.090 3.486 111
η =(3.036/3.0675) 100%
= 99%
x3 x1 0.090 3.486 0000
x2 x3 0.07 3.850 0001
x3 x2 0.07 3.850 1100
x3 x3 0.04 4.660 1101

3/5/2026 51
 2.5 Coding for Analog Sources - Quantization
 An analog source emits a waveform x(t) that is a sample function of
bandlimited, stationary stochastic process X(t)
 As per the sampling theorem, X(t) can be represented as a sequence of
uniform samples taken at the Nyquist rate
 An analog waveform x(t) is sampled every T seconds resulting in a
discrete-time sequence x(T), x(2T), x(3T), ………. of analog values
 These analog values are then quantized into elements from a discrete
alphabet
 The resulting discrete sequence can then be encoded using the various
methods we have seen earlier such that
x(T), x(2T), x(3T)……. → x1, x2, x3…..
 In sample-and-hold operation, a switch and storage mechanism form a
sequence of samples of the continuous input waveform.
 The output of the sampling process is called pulse amplitude modulation
(PAM).
3/5/2026 52
 Coding for Analog Sources – Quantization …
 Assume the random variables x1, x2, x3….. are i.i.d with some given
density function f(x)
 Quantization inherently involves loss of information about the analog
values being quantized that is referred to as distortion
 Results in loss of signal fidelity
 Quantizing finely reduces distortion; but if the analog is a RV represented
by some probability density function the distortion cannot be reduced to
zero

3/5/2026 53
 Coding for Analog Sources – Quantization …
 Distortion is measured in the mean square sense
 Quantize X into a discrete RV Y
 Distortion D = E{(X - Y)2}
 Note: this measure of distortion has disadvantage in speech coding; in speech
coding one can allow larger quantization errors when the signal is loud than when it
is soft

 There are two kinds of quantization

 Scalar quantization: An analog term in a sequence is quantized independently of
the other terms
 Vector quantization: The sequence is first segmented into blocks of n terms and
each term is quantized as unit

3/5/2026 54
Coding for Analog Sources – Quantization …
 Two approaches in both scalar and vector quantization
 Minimize mean square distortion subject to a constraint on the size of the
quantization alphabet
 Minimize mean square distortion subject to a constraint on the
entropy of the quantized output

3/5/2026 55
 Scalar Quantization
 A scalar quantizer partitions the set of real numbers into M subsets R1,
R2 …… RM called quantization regions or levels
 The quantization region is an interval and each region Rj is represented by
a representation level aj
 When the source produces x in Rj, then that quantity is quantized as aj

3/5/2026 56
 Scalar Quantization …
 Question: For a given value of M, how can one choose the regions and
levels to minimize the mean square error?
 This can be explored through the following two questions
 Given a set of representation levels { aj }, how do we choose the interval { Rj }?
 Given a set of intervals { Rj }, how do we choose the levels { aj }?

 For the first question given x, the square error to aj, (x – aj)2 is minimized
by representing x by the closest representation level aj
 If x is between aj and aj+1, it is mapped into the closer of the two; bj lies
midway between aj and aj+1 (1 ≤ j ≤ M -1)
 Note that this method does not depend on the probabilistic model of X1,
X2 ……..

3/5/2026 57
 Scalar Quantization …
 For the second question, the probabilistic model of X1, X2
…. is important
 Suppose RV’s {Xk } are i.i.d, continuous-valued with pdf f(x)
 For a given set of levels {aj }, V(x) maps each sample value x into aj
 Then the mean square distortion (MSE) is given by
 M
MSE E{(X V(x))   f (x)(xv(x)) dx   f (x)(xa j )2dx
2 2
 Rj
j1

 The above equation can be minimized over {aj } by separate

minimization over each region Rj

3/5/2026 58
 Scalar Quantization …
 Let fj (x) denote the conditional pdf of x, that is

 f x ( x)
x Rj
f j ( x)   Q j
 0 otherwise
Where Qj = Prob(X Є Rj ). Then for the interval Rj

 f (x)(x  a )2dx  Q  f
j j j (x)(x  a j )2dx

Rj Rj

 This is minimized by the mean of the RV X with pdf fj (x)

since for RV Y and any real number a
E{(Y  a) 2 }  E{Y 2 }  2aE{Y}  a 2
which is minimized over a when a  E{Y}

3/5/2026 59
Scalar Quantization …

 Thus bj – mid-point between aj and aj+1 b  2 


j
a j  aj1 

aj = the mean (expected value) of RV Xj with probability

density function fj (x) or aj is the conditional mean of X
conditioned on X Є Rj
 These conditions are necessary to minimize the MSE for a
given M quantization levels but not sufficient, even though
in practice it suffices

3/5/2026 60
 Scalar Quantization …
 Lloyd-Max Algorithm
 Assuming that M quantization level and fx (x) are known and given
the algorithm proceeds as follows
1. Choose an arbitrary set of M levels a1 < a2 <……< aM
2. For 1 ≤ j ≤ M, set bj =0.5(aj + aj+1)
3. For 1 ≤ j ≤ M, set aj equal to the conditional mean of X given x Є (bj-1
+ bj) where b0 and aM are taken to be - ∞ and + ∞ respectively
4. Repeat steps (2) and (3) until further improvement in MSE is negligible; then
stop

3/5/2026 61
 Vector Quantization
 Consider quantizing n source variables at a time
 This is referred to as vector quantization since a string of n RV’s may
be a vector RV in n dimensional vector space
 Consider the case of the 2D quantizer where n=2
 Quantize each independently with a scalar (1D)
 This results in a hexagonal quantization region as shown below

3/5/2026 62
 Vector Quantization …
 The MSE per dimension will be the same as for the scalar quantizer
 To construct MSE 2D quantizer, let (X, X’) be two random variables to
be quantized
 Choose M 2-dimens. representation point (aj , a’j); 1≤ j≤ M
 The mapping (x, x’) into (aj , a’j) generates a squared error equal to (x –
aj )2 + (x' – a’j )2

 We need to choose the point (aj , a’j) which is closest to (x, x’) in
Euclidean distance; that is regions {Rj } are minimum distance regions
commonly called Voronoi regions for the given representation regions
 As in the scalar case, given the Voronoi regions, choosing the
representation points will be the conditional means within the regions;
that is, a two-dimension version of the Lloyd-Max algorithm can be used

3/5/2026 63
 Entropy-Coded Quantization
 Consider the following block diagram

x1 , x2 , x3 ….. y1,y2 , y3……

Quanq
tizer

 Entropy of the output of the quantizer H[Y] is determined by the

probabilities of the quantization regions
 Given the regions, the representation points should still be the
conditional mean
 However, the region should not necessarily be chosen as the
minimum distance region between the representation points

3/5/2026 64
 Entropy-Coded Quantization …
 Example: With the constraint that H[Y] ≤ 0.5 and Gaussian pdf for X, a
reasonable choice will three regions, the center with high probability 1-2p
and the outer ones having probability p such that H[Y]=0.5

 Example: Compare MSE quantizer using a constraint on the number of

levels M to that of using a constraint on the entropy
 Let the pdf fx(x) be as shown in the figure below over the interval of
length L1+ L2

3/5/2026 65
 Entropy-Coded Quantization …

fx(x)
f1
L1 f2
L2
x
1 2

 fx(x) takes only two positive values f1 and f2 in the indicated

intervals and zero otherwise
 ∆1‘ s and ∆2‘s lie entirely in L1 and L2 respectively (Assume
large)

3/5/2026 66
 Entropy-Coded Quantization …
 Let M1 and M2 are the number of quantization regions in the two
intervals
 The representation points are in the middle of each quantization
interval
 The MSE condition on being the region ∆i is the MSE of a uniform
distribution over an interval length ∆i ,which can easily be computed to be
 2i
 That is 12

i 2 3
1  i  1  i  i  2i
E{ X i  i }   x 
i  2 
 dx  x
3 i  2 

0

12
0

3/5/2026 67
Mini Project

3/5/2026 68