Chapter 2:

Source coding
Prof. Abhishek Dixit
Dept. of Electrical Engineering
IIT Delhi

Prof. Abhishek Dixit

Digital Communication System
Transmitter

Binary Channel

Channel
Information Source Coder Modulator
Analog/Digital Bit Coder Bit Waveform
Waveform Stream Stream

Channel

Source Channel
Information Demodulator
Analog/Digital Decoder Bit Decoder Bit Waveform
Stream Stream
Waveform

Receiver
Prof. Abhishek Dixit
Source Coder/Decoder

r1 r2 …. rn d1 d2 …. dn 10 11 …. 01

Input Sampling and Discrete

Quantization
Waveform normalization Analog Symbol Encoder Binary Interface
Sequence Sequence
Binary
Channel

Output Analog Discrete

Table lookup Decoder
Waveform Filter Analog Symbol Binary Interface
Sequence Sequence

Prof. Abhishek Dixit

 Discrete Source Encoding
Prof. Abhishek Dixit
Dept. of Electrical Engineering
IIT Delhi

Prof. Abhishek Dixit

Discrete-source encoding
• Objective: Maps sequence of symbols into binary sequence with unique
decodability

Prof. Abhishek Dixit

Discrete-source encoding
• Objective: Maps sequence of symbols into binary sequence with unique
decodability
• Simplest approach:
• Map each source symbol into an L binary digits.
• For an alphabet of size 𝑀, require 2𝐿 ≥ 𝑀.
• To avoid wasting bits, choose 𝐿 as smallest integer satisfying
2𝐿 ≥ 𝑀, i.e.,
log 2 𝑀 ≤ 𝐿 < log 2 𝑀 + 1; 𝐿 = log 2 𝑀

Prof. Abhishek Dixit

Example:
•For alphabet {red, green, b lu e, ye l l o w, w h i te } :
• r e d → 000
• green → 001
• b l u e → 010
• y e l l o w → 011
• w h i t e → 100

• This can be easily decoded.

• These are called fixed length codes.
• Example: The ASCII code maps everything (letters, numbers, etc.) into
binary 8-tuples (bytes).

Prof. Abhishek Dixit

General fixed length code
• We have alphabet of size 𝑀 and form blocks of size 𝑛.
• How many tuples?

Prof. Abhishek Dixit

General fixed length code
• We have alphabet of size 𝑀 and form blocks of size 𝑛.
• How many tuples?
• Example:
• X = {𝑎, 𝑏}, and 𝑛 = 1
• (𝑎), (𝑏)
• X = {𝑎, 𝑏}, and 𝑛 = 2
• (𝑎, 𝑎), (𝑎, 𝑏), (𝑏, 𝑎), 𝑏, 𝑏
• X = {𝑎, 𝑏}, and 𝑛 = 3
• {𝑎, 𝑎, 𝑎}, {𝑎, 𝑎, 𝑏}, {𝑎, 𝑏, 𝑎}, {𝑎, 𝑏, 𝑏}, {𝑏, 𝑎, 𝑎}, {𝑏, 𝑎, 𝑏}, {𝑏, 𝑏, 𝑎}, {𝑏, 𝑏, 𝑏}
• There are 𝑀 𝑛 tuples of source letters.

Prof. Abhishek Dixit

General fixed length code
• We have alphabet of size 𝑀 and form blocks of size 𝑛.
• There are 𝑀 𝑛 tuples of source letters.
• Fixed-length source coding on 𝑀 𝑛 -tuples requires
𝐿 = log 2 𝑀𝑛

• Rate 𝐿 = 𝐿 / 𝑛 bits per source symbol (bpss)

yields 1
𝑛𝑙𝑜𝑔2 𝑀 ≤ 𝐿 < 𝑛 log 2 𝑀 + 1 log 2 𝑀 ≤ 𝐿 < log 2 𝑀 +
𝑛

• For large 𝑛, 𝐿 approaches log 2 𝑀

• Fixed-length coding requires log 2 𝑀 bpss.
Prof. Abhishek Dixit
Variable length source code
• Motivation: Probable symbols should have shorter codewords than
improbable to reduce bpss.
• A variable-length source code 𝐶 encodes each symbol 𝑥 in source
alphabet 𝑋 to a binary codeword 𝐶 (𝑥 ) of length 𝑙 (𝑥 ).
• For example, for X = {a, b, c}
• 𝐶(𝑎) = 0
• 𝐶(𝑏) = 10
• 𝐶(𝑐) = 11

Prof. Abhishek Dixit

Variable length source code
• Successive codewords of a variable-length code are transmitted
as a continuing sequence of bits.
• There are no commas; decoder must parse the received
sequence.

• Buffering might be a problem here.

•Requires unique decodability i.e., encoded bit stream must be

uniquely parsed and source sequence recovered.

• Assume initial synchronization.

Prof. Abhishek Dixit

Unique decodability
• A code 𝐶 for a discrete source is uniquely decodable if, for any string of source
symbols, say 𝑥1 , 𝑥2 , … , 𝑥𝑛 , the concatenation of the corresponding codewords,
𝐶 𝑥1 𝐶 𝑥2 … 𝐶 𝑥𝑛 , differs from the concatenation of the codewords
𝐶 𝑥1′ 𝐶 𝑥2′ … 𝐶 𝑥𝑚 ′ for any other string 𝑥 ′ , 𝑥 ′ , … , 𝑥 ′ of source symbols.
1 2 𝑚

Prof. Abhishek Dixit

Unique decodability
• A code 𝐶 for a discrete source is uniquely decodable if, for any string of source
symbols, say 𝑥1 , 𝑥2 , … , 𝑥𝑛 , the concatenation of the corresponding codewords,
𝐶 𝑥1 𝐶 𝑥2 … 𝐶 𝑥𝑛 , differs from the concatenation of the codewords
𝐶 𝑥1′ 𝐶 𝑥2′ … 𝐶 𝑥𝑚 ′ for any other string 𝑥 ′ , 𝑥 ′ , … , 𝑥 ′ of source symbols.
1 2 𝑚

• All concatenation of codewords are distinct.

Prof. Abhishek Dixit

Unique decodability
• A code 𝐶 for a discrete source is uniquely decodable if, for any string of source
symbols, say 𝑥1 , 𝑥2 , … , 𝑥𝑛 , the concatenation of the corresponding codewords,
𝐶 𝑥1 𝐶 𝑥2 … 𝐶 𝑥𝑛 , differs from the concatenation of the codewords
𝐶 𝑥1′ 𝐶 𝑥2′ … 𝐶 𝑥𝑚 ′ for any other string 𝑥 ′ , 𝑥 ′ , … , 𝑥 ′ of source symbols.
1 2 𝑚

• All concatenation of codewords are distinct.

• 𝑛 is different from 𝑚

Prof. Abhishek Dixit

Unique decodability
• A code 𝐶 for a discrete source is uniquely decodable if, for any string of source
symbols, say 𝑥1 , 𝑥2 , … , 𝑥𝑛 , the concatenation of the corresponding codewords,
𝐶 𝑥1 𝐶 𝑥2 … 𝐶 𝑥𝑛 , differs from the concatenation of the codewords
𝐶 𝑥1′ 𝐶 𝑥2′ … 𝐶 𝑥𝑚 ′ for any other string 𝑥 ′ , 𝑥 ′ , … , 𝑥 ′ of source symbols.
1 2 𝑚

• All concatenation of codewords are distinct.

• 𝑛 is different from 𝑚
• No commas between the codewords

Prof. Abhishek Dixit

Unique decodability
• A code 𝐶 for a discrete source is uniquely decodable if, for any string of source
symbols, say 𝑥1 , 𝑥2 , … , 𝑥𝑛 , the concatenation of the corresponding codewords,
𝐶 𝑥1 𝐶 𝑥2 … 𝐶 𝑥𝑛 , differs from the concatenation of the codewords
𝐶 𝑥1′ 𝐶 𝑥2′ … 𝐶 𝑥𝑚 ′ for any other string 𝑥 ′ , 𝑥 ′ , … , 𝑥 ′ of source symbols.
1 2 𝑚

• All concatenation of codewords are distinct.

• 𝑛 is different from 𝑚
• No commas between the codewords
• If there were commas, we will get ternary interface. Very complicated !

Prof. Abhishek Dixit

Unique decodability
• A code 𝐶 for a discrete source is uniquely decodable if, for any string of source
symbols, say 𝑥1 , 𝑥2 , … , 𝑥𝑛 , the concatenation of the corresponding codewords,
𝐶 𝑥1 𝐶 𝑥2 … 𝐶 𝑥𝑛 , differs from the concatenation of the codewords
𝐶 𝑥1′ 𝐶 𝑥2′ … 𝐶 𝑥𝑚 ′ for any other string 𝑥 ′ , 𝑥 ′ , … , 𝑥 ′ of source symbols.
1 2 𝑚

• All concatenation of codewords are distinct.

• 𝑛 is different from 𝑚
• No commas between the codewords
• If there were commas, we will get ternary interface. Very complicated !
• Example: 𝐶 𝑎 = 0, 𝐶 𝑏 = 1, 𝐶 𝑐 = 01, then 𝐶 𝑎 𝐶 𝑏 = 𝐶(𝑐).

Prof. Abhishek Dixit

Uniquely decodable codes

Uniquely
decodable

All other codes Prefix

Free
Codes

Prof. Abhishek Dixit

Uniquely decodable codes

Uniquely
decodable

Easy to construct
Optimum
All other codes Prefix
Instantaneous
Free
Codes

Prof. Abhishek Dixit

Uniquely decodable codes

Uniquely
decodable

Easy to construct
Optimum
All other codes Prefix
Instantaneous
Free
Codes Not practical

Prof. Abhishek Dixit

Prefix-free codes
• Simple class of uniquely decodable codes are prefix-free codes.
• A code is prefix-free if no codeword is a prefix of any other codeword

Prof. Abhishek Dixit

Prefix-free codes
• Simple class of uniquely decodable codes are prefix-free codes.
• A code is prefix-free if no codeword is a prefix of any other codeword.
• A prefix-free code 𝐶 can be represented by a binary code tree which
grows from a root on the left to leaves on the right representing
codewords. a
0
0 1 0 c

1 1
b

Prof. Abhishek Dixit

Prefix-free codes
• Simple class of uniquely decodable codes are prefix-free codes.
• A code is prefix-free if no codeword is a prefix of any other codeword.
• A prefix-free code 𝐶 can be represented by a binary code tree which
grows from a root on the left to leaves on the right representing
codewords. a
0
0 1 0 c

1 1
b

Prof. Abhishek Dixit

Prefix-free codes
• Simple class of uniquely decodable codes are prefix-free codes.
• A code is prefix-free if no codeword is a prefix of any other codeword.
• A prefix-free code 𝐶 can be represented by a binary code tree which
grows from a root on the left to leaves on the right representing
codewords. a
0
0 1 0 c

1 1
b

Prof. Abhishek Dixit

Prefix-free codes
• Simple class of uniquely decodable codes are prefix-free codes.
• A code is prefix-free if no codeword is a prefix of any other codeword.
• A prefix-free code 𝐶 can be represented by a binary code tree which
grows from a root on the left to leaves on the right representing
codewords. a
0
0 1 0 c

1 1
b

Prof. Abhishek Dixit

Prefix-free codes
• Simple class of uniquely decodable codes are prefix-free codes.
• A code is prefix-free if no codeword is a prefix of any other codeword.
• A prefix-free code 𝐶 can be represented by a binary code tree which
grows from a root on the left to leaves on the right representing
codewords. a
0
0 1 0 c

1 1
b

Prof. Abhishek Dixit

Prefix-free codes
• Simple class of uniquely decodable codes are prefix-free codes.
• A code is prefix-free if no codeword is a prefix of any other codeword.
• A prefix-free code 𝐶 can be represented by a binary code tree which
grows from a root on the left to leaves on the right representing
codewords. a
0
0 1 0 c

1 1
b d

Prof. Abhishek Dixit

Prefix-free codes
• Simple class of uniquely decodable codes are prefix-free codes.
• A code is prefix-free if no codeword is a prefix of any other codeword.
• A prefix-free code 𝐶 can be represented by a binary code tree which
grows from a root on the left to leaves on the right representing
codewords. a
0
0 1 0 c 𝑎 = 00
𝑏=1
1 1
b 𝑐 = 010

Prof. Abhishek Dixit

Prefix-free codes
• Simple class of uniquely decodable codes are prefix-free codes.
• A code is prefix-free if no codeword is a prefix of any other codeword.
• A prefix-free code 𝐶 can be represented by a binary code tree which
grows from a root on the left to leaves on the right representing
codewords. a
0
0 1 𝑎 = 00
c 𝑏=1
1
b 𝑐 = 01

Prof. Abhishek Dixit

Prefix-free codes
• Simple class of uniquely decodable codes are prefix-free codes.
• A code is prefix-free if no codeword is a prefix of any other codeword.
• A prefix-free code 𝐶 can be represented by a binary code tree which
grows from a root on the left to leaves on the right representing
codewords. a
0
0 1 𝑎 = 00
c 𝑏=1
1
b 𝑐 = 01

A full tree has no empty leaves.

Prof. Abhishek Dixit

Prefix-free codes
• Prefix-free codes are uniquely decodable

a ca
0 0
0 1 0 1

c
1 cc
1
b cb

Prof. Abhishek Dixit

Prefix-free codes
• Prefix-free codes are uniquely decodable
aa
0
ac
0 1
a
1 ca
0 0
ab
0 1 0 1
c
1 cc
1
b cb

Prof. Abhishek Dixit

Kraft Inequality
• Every prefix-free code for an alphabet 𝑋 with lengths 𝑙(𝑥) satisfies

෍ 2−𝑙(𝑥) ≤ 1
𝑥∈𝑋

Prof. Abhishek Dixit

Kraft Inequality
• Every prefix-free code for an alphabet 𝑋 with lengths 𝑙(𝑥) satisfies

෍ 2−𝑙(𝑥) ≤ 1
𝑥∈𝑋
• Converse is also true.
• Full prefix-free code satisfies the equation with equality.
• Nonfull prefix-free code satisfies this with strict inequality.

Prof. Abhishek Dixit

Kraft Inequality
• Every prefix-free code for an alphabet 𝑋 with lengths 𝑙(𝑥) satisfies

෍ 2−𝑙(𝑥) ≤ 1
𝑥∈𝑋
• Converse is also true.
• Full prefix-free code satisfies the equation with equality.
• Nonfull prefix-free code satisfies this with strict inequality.
• This equation is also true for uniquely decodable codes
• If a code satisfies this equation, it does not mean, it is prefix-free or uniquely
decodable.

Prof. Abhishek Dixit

Proof of Kraft Inequality
Associate codewords with binary base 2 expansion.

Represent binary codewords 𝑦1 , 𝑦2 , … , 𝑦𝑚 as

𝑦1 𝑦2 𝑦𝑚
. 𝑦1 𝑦2 … 𝑦𝑚 = + + ⋯ + 𝑚
2 4 2

1
1
Interval [2 , 1)

1 → .1 1 1
Interval [4 , 2ቁ
01 → .01 1
Interval [0, 4ቁ
00 → .00

Prof. Abhishek Dixit

Proof of Kraft Inequality
Associate codewords with binary base 2 expansion.

Represent binary codewords 𝑦1 , 𝑦2 , … , 𝑦𝑚 as

𝑦1 𝑦2 𝑦𝑚
. 𝑦1 𝑦2 … 𝑦𝑚 = + + ⋯ + 𝑚
2 4 2

1
1
Interval [2 , 1)

1 → .1 1 1
Interval [4 , 2ቁ
𝑙 𝑙
01 → .01 1
Interval [0, 4ቁ ቎ ෍ 𝑦𝑚 2−𝑚 , ෍ 𝑦𝑚 2−𝑚 + 2−l ቍ
00 → .00 𝑚=1 𝑚=1

Prof. Abhishek Dixit

Proof of Kraft Inequality
Represent binary codewords 𝑦1 , 𝑦2 , … , 𝑦𝑚 as
𝑦1 𝑦2 𝑦𝑚
. 𝑦1 𝑦2 … 𝑦𝑚 = + + ⋯ + 𝑚
2 4 2

1 1
1 1
Interval [2 , 1) Interval [2 , 1)

1 → .1 1 1 1 → .1 1 1
Interval [4 , 2ቁ Interval [4 , 2ቁ
01 → .01 1 01 → .01 3 1
Interval [0, 4ቁ Interval [8 , 2ቁ
00 → .00 011 → .011

A code 𝐶(𝑎𝑗 ) is prefix of 𝐶(𝑎𝑖 ) if and only if the expansion of 𝐶(𝑎𝑖 ) contains the
expansion of 𝐶(𝑎𝑖 ) in its approximate interval.

Prof. Abhishek Dixit

Proof of Kraft Inequality
1 1
1 1
Interval [2 , 1) Interval [2 , 1)

1 → .1 1 1 1 → .1 1 1
Interval [ 4 , 2ቁ Interval [4 , 2ቁ
01 → .01 1 01 → .01 3 1
Interval [0, 4ቁ Interval [8 , 2ቁ
00 → .00 011 → .011

A code 𝐶(𝑎𝑗 ) is prefix of 𝐶(𝑎𝑖 ) if and only if the expansion of 𝐶(𝑎𝑖 ) contains the
expansion of 𝐶(𝑎𝑖 ) in its approximate interval.

Thus, a code is prefix-free, iff the approximate intervals are disjoint.

Prof. Abhishek Dixit

Proof of Kraft Inequality
1 1
1 1
Interval [2 , 1) Interval [2 , 1)

1 → .1 1 1 1 → .1 1 1
Interval [ 4 , 2ቁ Interval [4 , 2ቁ
01 → .01 1 01 → .01 3 1
Interval [0, 4ቁ Interval [8 , 2ቁ
00 → .00 011 → .011

A code 𝐶(𝑎𝑗 ) is prefix of 𝐶(𝑎𝑖 ) if and only if the expansion of 𝐶(𝑎𝑖 ) contains the
expansion of 𝐶(𝑎𝑖 ) in its approximate interval.

Thus, a code is prefix-free, iff the approximate intervals are disjoint.

The sum of disjoint intervals is at most 1.

Prof. Abhishek Dixit

Probability models for discrete sources
• Why do we need probability models?
• Probability models to understand the expected number of coded bits per source symbol

Prof. Abhishek Dixit

Probability models for discrete sources
• Why do we need probability models?
• Probability models to understand the expected number of coded bits per source symbol
• How do we get the model?
• Discrete sources in real life have very complicated statistics.
• Example, for English language, ℎ is often preceded by 𝑡, and 𝑞 is followed by 𝑢

Prof. Abhishek Dixit

Probability models for discrete sources
• Why do we need probability models?
• Probability models to understand the expected number of coded bits per source symbol
• How do we get the model?
• Discrete sources in real life have very complicated statistics.
• Example, for English language, ℎ is often preceded by 𝑡, and 𝑞 is followed by 𝑢
• Should we go for probabilistic model of a real-world source?
• No !

Prof. Abhishek Dixit

Probability models for discrete sources
• Why do we need probability models?
• Probability models to understand the expected number of coded bits per source symbol
• How do we get the model?
• Discrete sources in real life have very complicated statistics.
• Example, for English language, ℎ is often preceded by 𝑡, and 𝑞 is followed by 𝑢
• Should we go for probabilistic model of a real-world source?
• No !
• What should we do then?
• Toy model !
• Get insight from the toy model, and may be include then one or two generalizations.

Prof. Abhishek Dixit

Discrete memoryless source
• Properties:
• 1) Unending: Unending sequence of 𝑋1 , 𝑋2 , 𝑋3 ,… of randomly selected symbols
from a finite set of 𝑋 = {𝑎1 , 𝑎2 , … , 𝑎𝑛 } called the source alphabet.

Prof. Abhishek Dixit

Discrete memoryless source
• Properties:
• 1) Unending: Unending sequence of 𝑋1 , 𝑋2 , 𝑋3 ,… of randomly selected symbols
from a finite set of 𝑋 = {𝑎1 , 𝑎2 , … , 𝑎𝑛 } called the source alphabet
• 2) Same PMF: Each source output 𝑋1 , 𝑋2 , 𝑋3 ,… is selected from 𝑋 using the
same probability mass function (pmf) {𝑝𝑋 𝑎1 , … , 𝑝𝑋 (𝑎𝑛 )}.
• Example: 𝑋 = {𝑎, 𝑏, 𝑐}, and their pmf ={0.2,0.5,0.3}. Then we can create a bag with the
following elements: [𝑎, 𝑎, 𝑏, 𝑏, 𝑏, 𝑐, 𝑐, 𝑐]. Select one element from the bag randomly.

Prof. Abhishek Dixit

Discrete memoryless source
• Properties:
• 1) Unending: Unending sequence of 𝑋1 , 𝑋2 , 𝑋3 ,… of randomly selected symbols
from a finite set of 𝑋 = {𝑎1 , 𝑎2 , … , 𝑎𝑛 } called the source alphabet
• 2) Same PMF: Each source output 𝑋1 , 𝑋2 , 𝑋3 ,… is selected from 𝑋 using the
same probability mass function (pmf) {𝑝𝑋 𝑎1 , … , 𝑝𝑋 (𝑎𝑛 )}.
• Example: 𝑋 = {𝑎, 𝑏, 𝑐}, and their pmf ={0.2,0.5,0.3}. Then we can create a bag with the
following elements: [𝑎, 𝑎, 𝑏, 𝑏, 𝑏, 𝑐, 𝑐, 𝑐]. Select one element from the bag randomly.
• 3) Statistically independent: Each source output 𝑋𝑘 is statistically independent of
the previous outputs 𝑋1 , …, 𝑋𝑘−1
• Every time, we start with the same bag, having the same number of elements (look at the
element and put it back!)

Prof. Abhishek Dixit

Discrete memoryless source
• Properties:

DMS IID

Prof. Abhishek Dixit

Minimizing 𝐿ത
• 𝐿ത : Bits per source symbol

𝐿ത = 𝐸 𝐿 = ෍ 𝑙 𝑎𝑗 𝑝𝑋 (𝑎𝑗 )
𝑗

Prof. Abhishek Dixit

Minimizing 𝐿ത
• 𝐿ത : Bits per source symbol

𝐿ത = 𝐸 𝐿 = ෍ 𝑙 𝑎𝑗 𝑝𝑋 (𝑎𝑗 )
𝑗
• Another notation

𝐿ത = 𝐸 𝐿 = ෍ 𝑙𝑗 𝑝𝑗
𝑗

Prof. Abhishek Dixit

Minimizing 𝐿ത
• 𝐿ത : Bits per source symbol

𝐿ത = 𝐸 𝐿 = ෍ 𝑙 𝑎𝑗 𝑝𝑋 (𝑎𝑗 )
𝑗
• Another notation

𝐿ത = 𝐸 𝐿 = ෍ 𝑙𝑗 𝑝𝑗
𝑗
• Minimizing 𝐿ത
𝑀

𝐿ത 𝑚𝑖𝑛 = min −𝑙 ෍ 𝑙𝑗 𝑝𝑗
𝑙1 …𝑙𝑚 :σ𝑗 2 𝑗 ≤1
𝑗

Prof. Abhishek Dixit

Minimizing 𝐿ത
• Minimizing 𝐿ത
𝑀

𝐿ത 𝑚𝑖𝑛 = min −𝑙 ෍ 𝑙𝑗 𝑝𝑗
𝑙1 …𝑙𝑚 :σ𝑗 2 𝑗 ≤1
𝑗
• Hard problem as 𝑙1 … 𝑙𝑚 all have to be positive integers.

Prof. Abhishek Dixit

Minimizing 𝐿ത
• Minimizing 𝐿ത
𝑀

𝐿ത 𝑚𝑖𝑛 = min −𝑙 ෍ 𝑙𝑗 𝑝𝑗
𝑙1 …𝑙𝑚 :σ𝑗 2 𝑗 ≤1
𝑗
• Hard problem as 𝑙1 … 𝑙𝑚 all have to be positive integers.

• Minimizing 𝐿ത
𝑀

𝐿ത 𝑚𝑖𝑛 = min −𝑙 ෍ 𝑙𝑗 𝑝𝑗
𝑙1 …𝑙𝑚 :σ𝑗 2 𝑗 ≤1
𝑗
• Relax 𝑙1 … 𝑙𝑚 to be real numbers.
• Provides a lower bound.

Prof. Abhishek Dixit

Minimizing 𝐿ത (Lagrange multiplier)
• Minimizing 𝐿ത
𝑀

𝐿ത 𝑚𝑖𝑛 = min −𝑙 ෍ 𝑙𝑗 𝑝𝑗
𝑙1 …𝑙𝑚 :σ𝑗 2 𝑗 =1
𝑗
• Relax 𝑙1 … 𝑙𝑚 to be real numbers.
• Provides a lower bound.

Prof. Abhishek Dixit

Minimizing 𝐿ത (Lagrange multiplier)
• Minimizing 𝐿ത
𝑀

𝐿ത 𝑚𝑖𝑛 = min −𝑙 ෍ 𝑙𝑗 𝑝𝑗
𝑙1 …𝑙𝑚 :σ𝑗 2 𝑗 =1
𝑗
• Relax 𝑙1 … 𝑙𝑚 to be real numbers.
• Provides a lower bound.

• Langrage multipler:
𝑀

෍ 𝑙𝑗 𝑝𝑗 + λ ෍ 2−𝑙𝑗
𝑗 𝑗

Prof. Abhishek Dixit

Minimizing 𝐿ത (Lagrange multiplier)
• Minimizing 𝐿ത
𝑀

𝐿ത 𝑚𝑖𝑛 = min −𝑙 ෍ 𝑙𝑗 𝑝𝑗
𝑙1 …𝑙𝑚 :σ𝑗 2 𝑗 =1
𝑗
• Relax 𝑙1 … 𝑙𝑚 to be real numbers.
• Provides a lower bound.

• Langrage multipler:
𝑙𝑗 𝑝𝑗 + λ2−𝑙𝑗

Prof. Abhishek Dixit

Minimizing 𝐿ത (Lagrange multiplier)
• Minimizing 𝐿ത
𝑀

𝐿ത 𝑚𝑖𝑛 = min −𝑙 ෍ 𝑙𝑗 𝑝𝑗
𝑙1 …𝑙𝑚 :σ𝑗 2 𝑗 =1
𝑗
• Relax 𝑙1 … 𝑙𝑚 to be real numbers.
• Provides a lower bound.

• Langrage multipler:
𝑙𝑗 𝑝𝑗 + λ2−𝑙𝑗
𝑑
𝑙𝑗 𝑝𝑗 + λ2−𝑙𝑗 = 𝑝𝑗 + λ(− ln 2)2−𝑙𝑗
𝑑𝑙𝑗

Prof. Abhishek Dixit

Minimizing 𝐿ത (Lagrange multiplier)
• Minimizing 𝐿ത
𝑀

𝐿ത 𝑚𝑖𝑛 = min −𝑙 ෍ 𝑙𝑗 𝑝𝑗
𝑙1 …𝑙𝑚 :σ𝑗 2 𝑗 =1
𝑗
• Relax 𝑙1 … 𝑙𝑚 to be real numbers.
• Provides a lower bound.

• Langrage multipler:
𝑙𝑗 𝑝𝑗 + λ2−𝑙𝑗
𝑑
𝑙𝑗 𝑝𝑗 + λ2−𝑙𝑗 = 𝑝𝑗 + λ(− ln 2)2−𝑙𝑗
𝑑𝑙𝑗

෍ 𝑝𝑗 + λ(− ln 2)2−𝑙𝑗 = 0
𝑗
1 − λ ln 2 = 0 or λ = 1/ ln 2

Prof. Abhishek Dixit

Minimizing 𝐿ത (Lagrange multiplier)
• Minimizing 𝐿ത
𝑀

𝐿ത 𝑚𝑖𝑛 = min −𝑙 ෍ 𝑙𝑗 𝑝𝑗
𝑙1 …𝑙𝑚 :σ𝑗 2 𝑗 =1
𝑗
• Relax 𝑙1 … 𝑙𝑚 to be real numbers.
• Provides a lower bound.

• Langrage multipler:
𝑙𝑗 𝑝𝑗 + λ2−𝑙𝑗
𝑑
𝑙𝑗 𝑝𝑗 + λ2−𝑙𝑗 = 𝑝𝑗 + λ(− ln 2)2−𝑙𝑗
𝑑𝑙𝑗

෍ 𝑝𝑗 + λ(− ln 2)2−𝑙𝑗 = 0
𝑗
𝑝𝑗 = 2−𝑙𝑗 or 𝑙𝑗 = − l𝑜𝑔 𝑝𝑗

Prof. Abhishek Dixit

Minimizing 𝐿ത (Lagrange multiplier)
• Minimizing 𝐿ത
𝑀 𝑀

𝐿ത 𝑚𝑖𝑛 = min −𝑙 ෍ 𝑙𝑗 𝑝𝑗 = − ෍ 𝑝𝑗 l𝑜𝑔 𝑝𝑗

𝑙1 …𝑙𝑚 :σ𝑗 2 𝑗 =1
𝑗 𝑗
• Known as entropy.

Prof. Abhishek Dixit

Theorems
• Theorem: 𝐻 𝑋 ≤ 𝐿𝑚𝑖𝑛 < 𝐻 𝑋 + 1 (for prefix-free codes)
• Proving LHS of the equation:
1 1
• 𝐻 𝑋 − 𝐿𝑚𝑖𝑛 = σ𝑗 𝑝𝑗 log − σ𝑗 𝑝𝑗 𝑙𝑗 = σ𝑗 𝑝𝑗 log + σ𝑗 𝑝𝑗 log 2−𝑙𝑗
𝑝𝑗 𝑝𝑗
−𝑙
2 𝑗
•= σ𝑗 𝑝𝑗 log
𝑝𝑗

Prof. Abhishek Dixit

Theorems
• Theorem: 𝐻 𝑋 ≤ 𝐿𝑚𝑖𝑛 < 𝐻 𝑋 + 1 (for prefix-free codes)
• Proving LHS of the equation:
1 1
• 𝐻 𝑋 − 𝐿𝑚𝑖𝑛 = σ𝑗 𝑝𝑗 log − σ𝑗 𝑝𝑗 𝑙𝑗 = σ𝑗 𝑝𝑗 log + σ𝑗 𝑝𝑗 log 2−𝑙𝑗
𝑝𝑗 𝑝𝑗
−𝑙 −𝑙
2 𝑗 2 𝑗
•= σ𝑗 𝑝𝑗 log ≤ σ𝑗 𝑝𝑗 log 𝑒 − 1 = log 𝑒 σ𝑗 2−𝑙𝑗 − 1 = 0
𝑝𝑗 𝑝𝑗
• 𝐻 𝑋 − 𝐿𝑚𝑖𝑛 ≤ 0

Prof. Abhishek Dixit

Theorems
• Theorem: 𝐻 𝑋 ≤ 𝐿𝑚𝑖𝑛 < 𝐻 𝑋 + 1 (for prefix-free codes)
• Proving LHS of the equation:
1 1
• 𝐻 𝑋 − 𝐿𝑚𝑖𝑛 = σ𝑗 𝑝𝑗 log − σ𝑗 𝑝𝑗 𝑙𝑗 = σ𝑗 𝑝𝑗 log + σ𝑗 𝑝𝑗 log 2−𝑙𝑗
𝑝𝑗 𝑝𝑗
−𝑙 −𝑙
2 𝑗 2 𝑗
•= σ𝑗 𝑝𝑗 log ≤ σ𝑗 𝑝𝑗 log 𝑒 − 1 = log 𝑒 σ𝑗 2−𝑙𝑗 − 1 = 0
𝑝𝑗 𝑝𝑗
• 𝐻 𝑋 − 𝐿𝑚𝑖𝑛 ≤ 0

• When is 𝐿𝑚𝑖𝑛 = H(X)?

Prof. Abhishek Dixit

Theorems
• Theorem: 𝐻 𝑋 ≤ 𝐿𝑚𝑖𝑛 < 𝐻 𝑋 + 1 (for prefix-free codes)
• Proving LHS of the equation:
1 1
• 𝐻 𝑋 − 𝐿𝑚𝑖𝑛 = σ𝑗 𝑝𝑗 log − σ𝑗 𝑝𝑗 𝑙𝑗 = σ𝑗 𝑝𝑗 log + σ𝑗 𝑝𝑗 log 2−𝑙𝑗
𝑝𝑗 𝑝𝑗
−𝑙 −𝑙
2 𝑗 2 𝑗
•= σ𝑗 𝑝𝑗 log ≤ σ𝑗 𝑝𝑗 log 𝑒 − 1 = log 𝑒 σ𝑗 2−𝑙𝑗 − 1 = 0
𝑝𝑗 𝑝𝑗
• 𝐻 𝑋 − 𝐿𝑚𝑖𝑛 ≤ 0

• When is 𝐿𝑚𝑖𝑛 = H(X)?

1
• If log is an integer, because ln 𝑢 = 𝑢 − 1 at 𝑢 = 1
𝑝𝑗

Prof. Abhishek Dixit

Theorems
• Theorem: 𝐻 𝑋 ≤ 𝐿𝑚𝑖𝑛 < 𝐻 𝑋 + 1 (for prefix-free codes)
• Proving RHS of the equation:
1 1
• 𝐿𝑚𝑖𝑛 − 𝐻(𝑋) ≤ σ𝑗 𝑝𝑗 log − 𝐻(𝑋) < σ𝑗 𝑝𝑗 log +1 −𝐻 𝑋 =1
𝑝𝑗 𝑝𝑗
• 𝐿𝑚𝑖𝑛 − 𝐻(𝑋) < 1

Prof. Abhishek Dixit

Huffman coding
• How to chose codes such that 𝑙𝑗 ≈ − log 𝑝𝑗 ?

Prof. Abhishek Dixit

Huffman coding
• How to chose codes such that 𝑙𝑗 ≈ − log 𝑝𝑗 ?

a a
0 0
0 1 0 c 0 1 0 c

1 1 1 1
b b

Other researchers Huffman

Prof. Abhishek Dixit

Huffman coding
• Lemma 1: Optimal codes have the property that 𝑝𝑖 > 𝑝𝑗 , then 𝑙𝑖 ≤ 𝑙𝑗 .

Prof. Abhishek Dixit

Huffman coding
• Lemma 1: Optimal codes have the property that 𝑝𝑖 > 𝑝𝑗 , then 𝑙𝑖 ≤ 𝑙𝑗 .
• Proof: Assume that the code on the contrary has 𝑝𝑖 > 𝑝𝑗 , and 𝑙𝑖 > 𝑙𝑗 . The terms
in 𝐿ത involving symbols 𝑖 and 𝑗 are:
𝑝𝑖 𝑙𝑖 + 𝑝𝑗 𝑙𝑗 .
If the two codewords are interchanged then the sum decreases, i.e.,
𝑝𝑖 𝑙𝑗 + 𝑝𝑗 𝑙𝑖 .
Thus, the given code is not optimal.

Prof. Abhishek Dixit

Huffman coding
• Lemma 2: Optimal prefix free codes are full codes
• Proof: If the tree is not full, then a codeword length can be reduced.

Prof. Abhishek Dixit

Huffman coding
• Siblings:
Sibling of a codeword is a binary string that differs from the codeword in only the
final digit.

a
0
0 1 0 c

1 1
b d

Prof. Abhishek Dixit

Huffman coding
• Lemma 3:
The siblings of a maximal length codeword is another codeword.

a
0
0 1 0 c

1 1
b d

Prof. Abhishek Dixit

Huffman coding
• Lemma 4:
Let 𝑋 be a random symbol with a pmf satisfying 𝑝1 ≥ 𝑝2 ≥ ⋯ ≥ 𝑝𝑀 . There is an
optimal prefix-free code for 𝑋 in which the codewords for 𝑀 − 1 and 𝑀 are
siblings and have maximal length within the code.

Prof. Abhishek Dixit

Huffman coding
𝒑𝒋 symbol
0.4 1
0.2 2
0.15 3
0.15 4
0.1 5

Prof. Abhishek Dixit

Huffman coding
𝒑𝒋 symbol
0.4 1
0.2 2
0.15 3
0.15 4
0.1 5

0
4

1
Prof. Abhishek Dixit 5
Huffman coding
𝒑𝒋 symbol
0.4 1
0.25 {4,5}
0.2 2
0.15 3

0 2

1
3
0
4

1
Prof. Abhishek Dixit 5
Huffman coding
𝒑𝒋 symbol
0.4 1
0.35 {2,3}
0.25 {4,5}

0 2
0

1
3
0
1 4

1
Prof. Abhishek Dixit 5
Huffman coding
𝒑𝒋 symbol
0.6 {{4,5}, {2,3}}
0.4 1

0 2
0

0 1
3
0
1 4
1
1 1
Prof. Abhishek Dixit 5
Huffman coding
𝒑𝒋 symbol Binary representation
0.4 1 1
0.2 2 000
0.15 3 001
0.15 4 010
0.1 5 011

𝐻 𝑋 = 2.15 bpss

𝐿ത = 2.2 bpss

Prof. Abhishek Dixit

Optimality of Huffman coding
𝐿ത = 𝐿ഥ′ + 𝑝𝑀−1 + 𝑝𝑀

0 2
0

0 1
3
0
1 4
1

1 1
5

Optimal code for the reduced set leads to the optimal code for the original set
Prof. Abhishek Dixit
Optimality of Huffman coding

𝒑𝒋 symbol
0.4 1
0.2 2
0.15 3
0
0.25 0.15 4
0.1 5
1

Prof. Abhishek Dixit

Properties of Entropy
• 𝐻 𝑋 = − σ𝑗 𝑝𝑗 log 𝑝𝑗

Properties of entropy
1) 𝐻(𝑋) ≥ 0
Proof: Because − log 𝑝𝑗 are all positives.
Equality is satisfied when 𝑋 is deterministic or 𝑝𝑗 is 1.

Prof. Abhishek Dixit

Properties of Entropy
• 𝐻 𝑋 = − σ𝑗 𝑝𝑗 log 𝑝𝑗

Properties of entropy
1) 𝐻 𝑋 ≥ 0
2) 𝐻(𝑋) ≤ log 𝑀

Prof. Abhishek Dixit

Properties of Entropy
• 𝐻 𝑋 = − σ𝑗 𝑝𝑗 log 𝑝𝑗

Properties of entropy
1) 𝐻 𝑋 ≥ 0
2) 𝐻(𝑋) ≤ log 𝑀
1
𝐻 𝑋 − log 𝑀 = ෍ 𝑝𝑗 log − log 𝑀
𝑝𝑗
1 1
= ෍ 𝑝𝑗 log ≤ log 𝑒 ෍ 𝑝𝑗 −1 =0
𝑀𝑝𝑗 𝑀𝑝𝑗
𝑗

Prof. Abhishek Dixit

Properties of Entropy
• 𝐻 𝑋 = − σ𝑗 𝑝𝑗 log 𝑝𝑗

Properties of entropy
1) 𝐻 𝑋 ≥ 0
2) 𝐻 𝑋 ≤ log 𝑀
3) 𝐻 𝑋𝑌 = 𝐻 𝑋 + 𝐻(𝑌) If 𝑋 and 𝑌 are independent random variables

Prof. Abhishek Dixit

Properties of Entropy
• 𝐻 𝑋 = − σ𝑗 𝑝𝑗 log 𝑝𝑗

Properties of entropy
1) 𝐻 𝑋 ≥ 0
2) 𝐻 𝑋 ≤ log 𝑀
3) 𝐻 𝑋𝑌 = 𝐻 𝑋 + 𝐻 𝑌
4) 𝐻 𝑋 𝑛 = 𝑛𝐻(𝑋)

Prof. Abhishek Dixit

Fixed-to-variable length codes
• Segment input into 𝑛 blocks 𝑋 𝑛 = 𝑋1 𝑋2 … 𝑋𝑛
• 𝐻 𝑋 𝑛 = 𝑛𝐻(𝑋)
• 𝐻 𝑋 𝑛 ≤ 𝐸 𝐿(𝑋 𝑛 ) < 𝐻 𝑋 𝑛 + 1
• 𝑛𝐻(𝑋) ≤ 𝐸 𝐿(𝑋 𝑛 ) < 𝑛𝐻 𝑋 + 1
1 1
• 𝐻(𝑋) ≤ 𝐸 𝐿(𝑋 𝑛 ) <𝐻 𝑋 +
𝑛 𝑛
1
• Defining 𝐿 = 𝐸 𝐿(𝑋 𝑛 ) , 𝐿ത → 𝐻(𝑋) as 𝑛 → ∞
ത
𝑛

Prof. Abhishek Dixit

Fixed to Fixed length
1
ത
• log 𝑀 ≤ 𝐿𝑚𝑖𝑛 < log 𝑀 +
𝑛

Prof. Abhishek Dixit

Variable length codes
• Kraft Inequality:
• σ𝑖 2𝑙𝑖 ≤ 1 (Prefix-free codes)
• DMS source, probabilities 𝑝𝑖
• Minimize 𝐿ത 𝑚𝑖𝑛 = min −𝑙 σ𝑀
𝑗 𝑙𝑗 𝑝𝑗
𝑙1 …𝑙𝑚 :σ𝑗 2 𝑗 =1
• Analytically, 𝐻 𝑋 = − σ𝑀 𝑗 𝑝𝑗 l𝑜𝑔 𝑝𝑗
(without integer constraints) (known as entropy)
• Algorithmically, Huffmann algorithm
• Fixed-to-variable length coding
• 𝐿ത 𝑚𝑖𝑛 → 𝐻 𝑋

Prof. Abhishek Dixit

Weak Law of Large Numbers (WLLN)
• Let 𝑌1 , 𝑌2 , … , 𝑌𝑛 be a sequence of rv’s with mean 𝑌ത and variance σ2𝑌
• The sum 𝑆 = 𝑌1 + 𝑌2 + ⋯ + 𝑌𝑛 has mean 𝑛𝑌ത and variance 𝑛σ2𝑌
• The sample average of 𝑌1 , 𝑌2 , … , 𝑌𝑛 is
𝑛
𝑆 𝑌1 + 𝑌2 + ⋯ + 𝑌𝑛
𝐴𝑌 = =
𝑛 𝑛
2
σ
• It has mean 𝐸 𝐴𝑛𝑌 = 𝑌ത and variance 𝑉𝐴𝑅 𝐴𝑛𝑌 = 𝑌
𝑛
• Note that lim 𝑉𝐴𝑅 𝑆 = ∞ lim 𝑉𝐴𝑅 𝐴𝑛𝑌 = 0
𝑛→∞ 𝑛→∞

Prof. Abhishek Dixit

Weak Law of Large Numbers (WLLN)

ത clustering more closely as 𝑛 → ∞

The distribution of 𝐴𝑛𝑌 clusters around 𝑌,
σ2𝑌
Chebyshev: for ε > 0, Pr{|𝐴𝑛𝑌 ത > ε} ≤
− 𝑌| Proof in 2.3
𝑛ε2

For ε, δ > 0, large enough 𝑛 ,

ത > ε} ≤ δ
Pr{|𝐴𝑛𝑌 − 𝑌|
Prof. Abhishek Dixit
Weak Law of Large Numbers (WLLN)

ത clustering more closely as 𝑛 → ∞

The distribution of 𝐴𝑛𝑌 clusters around 𝑌,
σ2𝑌
Chebyshev: for ε > 0, Pr{|𝐴𝑛𝑌 ത > ε} ≤
− 𝑌| Typically, ε → 0
𝑛ε2 Note that after fixing ε, we choose 𝑛 such that 𝑛ε2 → ∞
For ε, δ > 0, large enough 𝑛 ,
ത > ε} ≤ δ
Pr{|𝐴𝑛𝑌 − 𝑌|
Prof. Abhishek Dixit
Asymptotic equipartition property (AEP)
• It is simply WLLN applied to source coding

Prof. Abhishek Dixit

Asymptotic equipartition property (AEP)
• It is simply WLLN applied to source coding
• Let 𝑋1 , 𝑋2 ,…,𝑋𝑛 be output from DMS
• Define log pmf as w x = − log 𝑝𝑋 (𝑥)
𝑤(𝑥) maps source symbols into real numbers
• For each 𝑗, 𝑊(𝑋𝑗 ) is a rv; takes sample value 𝑤(𝑥) for 𝑋𝑗 = 𝑥.
• Note that 𝐸 𝑊 𝑋𝑗 = σ𝑥 −𝑝𝑋 (𝑥) log 𝑝𝑋 (𝑥) = 𝐻 𝑋
• 𝑊 𝑋1 𝑊 𝑋2 … 𝑊(𝑋𝑛 ) be a sequence of iid rvs

Prof. Abhishek Dixit

Asymptotic equipartition property (AEP)
• For 𝑋1 = 𝑥1 and 𝑋2 = 𝑥2 , the outcome for 𝑊 𝑋1 + 𝑊 𝑋2 is
𝑤 𝑥1 + 𝑤 𝑥2 = − log 𝑝𝑋 𝑥1 − log 𝑝𝑋 𝑥2
= − log 𝑝𝑋 𝑥1 𝑝𝑋 𝑥2
= − log 𝑝𝑋1 ,𝑋2 𝑥1 , 𝑥2 = 𝑤(𝑥1 𝑥2 )
where 𝑤(𝑥1 𝑥2 ) is –log pmf of 𝑋1 𝑋2 = 𝑥1 𝑥2
• 𝑊 𝑋1 𝑋2 = 𝑊 𝑋1 + 𝑊 𝑋2
𝑋1 𝑋2 is a random signal in its own right (takes values 𝑥1 𝑥2 ).
• Probabilities multiplies and log pmfs add.

Prof. Abhishek Dixit

Asymptotic equipartition property (AEP)
• For 𝑋 𝑛 = 𝑥 𝑛 ; 𝑥 𝑛 = (𝑥1 𝑥2 …𝑛𝑥𝑛 ), the outcome
𝑛
for 𝑊 𝑋1 + 𝑊 𝑋2 + ⋯ + 𝑊(𝑋𝑛 ) is
෍ 𝑤 𝑥𝑗 = ෍ − log 𝑝𝑋 (𝑥𝑗 ) = − log 𝑝𝑋 𝑛 (𝑥 𝑛 )
𝑗=1 𝑗=1

• Sample average of log pmf’s is

𝑊 𝑋 + 𝑊 𝑋 + ⋯ + 𝑊(𝑋 ) − log 𝑝 𝑛
𝑛 (𝑥 )
1 2 𝑛 𝑋
𝐴𝑛𝑊 = =
𝑛 𝑛

• WLLN applies and is

2
σ 𝑊
Pr{|𝐴𝑛𝑊 − 𝐸[𝑊 𝑋 ]| > ε} ≤ 2
𝑛ε

− log 𝑝𝑋 𝑛 (𝑥 𝑛 ) σ2𝑊
Pr −𝐻 𝑋 >ε ≤ 2
𝑛 𝑛ε

Prof. Abhishek Dixit

Typical set
• Define typical set 𝑇ε𝑛 as
− log 𝑝𝑋𝑛 𝑥 𝑛
• 𝑇ε𝑛 = 𝑥 𝑛 : −𝐻 𝑋 <ε
𝑛

σ2𝑊
Pr 𝑋 𝑛 𝜖𝑇ε𝑛 ≥1− 2 As 𝑛 → ∞, typical set approaches probability 1
𝑛ε
Prof. Abhishek Dixit
Typical set
− log 𝑝𝑋𝑛 𝑥 𝑛
• 𝑇ε𝑛 = 𝑥 𝑛 : −𝐻 𝑋 <ε
𝑛
• 𝑇ε𝑛 = 𝑥 𝑛 : 𝑛 𝐻 𝑋 − ε < − log 𝑝𝑋 𝑛 𝑥 𝑛 < 𝑛 𝐻 𝑋 + ε
− log 𝑝𝑋𝑛 𝑥 𝑛
• 𝑇ε𝑛 = 𝑥 𝑛 : 2𝑛 𝐻 𝑋 −ε <2 < 2𝑛 𝐻 𝑋 +ε

log 𝑝𝑋𝑛 𝑥 𝑛
• 𝑇ε𝑛 = 𝑥 𝑛 : 2−𝑛 𝐻 𝑋 −ε >2 > 2−𝑛 𝐻 𝑋 +ε

• 𝑇ε𝑛 = 𝑥 𝑛 : 2−𝑛 𝐻 𝑋 +ε < 𝑝𝑋 𝑛 𝑥 𝑛 < 2−𝑛 𝐻 𝑋 −ε

Prof. Abhishek Dixit

Typical set
− log 𝑝𝑋𝑛 𝑥 𝑛
• 𝑇ε𝑛 = 𝑥 𝑛 : −𝐻 𝑋 <ε
𝑛

Prof. Abhishek Dixit

Typical set
− log 𝑝𝑋𝑛 𝑥 𝑛
• 𝑇ε𝑛 = 𝑥 𝑛 : −𝐻 𝑋 <ε
𝑛
• 𝑇ε𝑛 = 𝑥 𝑛 : 𝑛 𝐻 𝑋 − ε < − log 𝑝𝑋 𝑛 𝑥 𝑛 < 𝑛 𝐻 𝑋 + ε
• 𝑇ε𝑛 = 𝑥 𝑛 : 2−𝑛 𝐻 𝑋 +ε < 𝑝𝑋 𝑛 𝑥 𝑛 < 2−𝑛 𝐻 𝑋 −ε

Prof. Abhishek Dixit

Typical set
− log 𝑝𝑋𝑛 𝑥 𝑛
• 𝑇ε𝑛 = 𝑥 𝑛 : −𝐻 𝑋 <ε
𝑛
• 𝑇ε𝑛 = 𝑥 𝑛 : 𝑛 𝐻 𝑋 − ε < − log 𝑝𝑋 𝑛 𝑥 𝑛 < 𝑛 𝐻 𝑋 + ε
• 𝑇ε𝑛 = 𝑥 𝑛 : 2−𝑛 𝐻 𝑋 +ε < 𝑝𝑋 𝑛 𝑥 𝑛 < 2−𝑛 𝐻 𝑋 −ε

Typical elements are approximately equiprobable in the strange sense above.

The complementary, atypical set of strings, satisfy

σ2𝑊
Pr 𝑋 𝑛 𝜖 𝑇ε𝑛 𝑐 ≤ 2
𝑛ε
For ε, δ > 0, large enough 𝑛 ,
Pr{𝑋 𝑛 𝜖 𝑇ε𝑛 𝑐 } ≤ δ
Prof. Abhishek Dixit
Typical set (Find lower & Upper bound)

Prof. Abhishek Dixit

Typical set
• For all 𝑥 𝑛 ∈ 𝑇ε𝑛
𝑝𝑋 𝑛 𝑥 𝑛 > 2−𝑛 𝐻 𝑋 +ε

1 ≥ ෍ 𝑝𝑋 𝑛 𝑥 𝑛 > 𝑇ε𝑛 2−𝑛 𝐻 𝑋 +ε

𝑥 𝑛 ∈𝑇ε𝑛
𝑇ε𝑛 < 2𝑛 𝐻 𝑋 +ε

• Lower bound

1 − δ ≤ ෍ 𝑝𝑋 𝑛 𝑥 𝑛 < 𝑇ε𝑛 2−𝑛 𝐻 𝑋 −ε

𝑥 𝑛 ∈𝑇ε𝑛
𝑇ε𝑛 > 1 − δ 2𝑛 𝐻 𝑋 −ε

• Summary: 𝑇ε𝑛 ≈ 2𝑛𝐻 𝑋 𝑝𝑋 𝑛 𝑥 𝑛 ≈ 2−𝑛𝐻 𝑋

Prof. Abhishek Dixit
Example:
1
• Consider binary DMS with 𝑃𝑟 𝑋 = 1 = 𝑝 <
2
• 𝐻 𝑋 = −𝑝log 𝑝 − 1 − 𝑝 log(1 − 𝑝)
• 𝑛𝐻 𝑋 = −𝑛𝑝log 𝑝 − 𝑛 1 − 𝑝 log(1 − 𝑝)
• 𝑛𝐻 𝑋 = − log 𝑝𝑛𝑝 − log 1 − 𝑝 𝑛 1−𝑝 = − log 𝑝𝑛𝑝 1 − 𝑝 𝑛 1−𝑝

• 2−𝑛𝐻 𝑋 = 𝑝𝑛𝑝 1 − 𝑝 𝑛 1−𝑝

• 𝑇ε 𝑛 : 𝑥 𝑛 : 𝑝𝑋 𝑛 (𝑥 𝑛 ) ≈ 𝑝𝑛𝑝 1 − 𝑝 𝑛 1−𝑝
• Typical set is one where out of 𝑛 bits, 𝑛𝑝 bits are 1 and 𝑛(1 − 𝑝) bits are zeros.

Prof. Abhishek Dixit

Example:
1
• Consider binary DMS with 𝑃𝑟 𝑋 = 1 = 𝑝 <
2
• How many typical sequences?
𝑛!
• ≈ 2𝑛𝐻 𝑋
𝑛𝑝! 𝑛 1−𝑝 !

• Ratio of typical sequences to all-sequences:

Prof. Abhishek Dixit

Example:
1
• Consider binary DMS with 𝑃𝑟 𝑋 = 1 = 𝑝 <
2
• How many typical sequences?
𝑛!
• ≈ 2𝑛𝐻 𝑋
𝑛𝑝! 𝑛 1−𝑝 !

• Ratio of typical sequences to all-sequences:

2𝑛𝐻 𝑋 2𝑛𝐻 𝑋
• = log 𝑀𝑛 = 2−𝑛(log 𝑀−𝐻 𝑋 )
𝑀𝑛 2
• Number of typical sequences are not that many, but there probability is close to 1.
• Probability of a Typical set
• A typical sequence may not even have the highest probability.
• All zero sequence has the highest probability but there are not enough of them.

Prof. Abhishek Dixit

Fixed-to-fixed length source code
• For any ε, δ > 0, large enough 𝑛, assign fixed length codeword to each 𝑥 𝑛 ∈ 𝑇ε 𝑛
• Since 𝑇ε𝑛 < 2𝑛 𝐻 𝑋 +ε ,
1
𝐿ത ≤ 𝐻 𝑋 + ε +
𝑛
𝑃𝑟 {𝑓𝑎𝑖𝑙𝑢𝑟𝑒} ≤ δ

Prof. Abhishek Dixit

Fixed-to-fixed length source code
• For any ε, δ > 0, large enough 𝑛, assign fixed length codeword to each 𝑥 𝑛 ∈ 𝑇ε 𝑛
• Since 𝑇ε𝑛 < 2𝑛 𝐻 𝑋 +ε ,
1
𝐿ത ≤ 𝐻 𝑋 + ε +
𝑛
𝑃𝑟 {𝑓𝑎𝑖𝑙𝑢𝑟𝑒} ≤ δ
• Is failure accepted?
• Prefix-free codes will fail also due to buffer overflows

Prof. Abhishek Dixit

Fixed-to-fixed length source code
• For any ε, δ > 0, large enough 𝑛, assign fixed length codeword to each 𝑥 𝑛 ∈ 𝑇ε 𝑛
• Since 𝑇ε𝑛 < 2𝑛 𝐻 𝑋 +ε ,
1
𝐿ത ≤ 𝐻 𝑋 + ε +
𝑛
𝑃𝑟 {𝑓𝑎𝑖𝑙𝑢𝑟𝑒} ≤ δ
• Conversely, take 𝐿ത ≤ 𝐻 𝑋 − 2ε and large 𝑛
• 𝑃𝑟 {𝑓𝑎𝑖𝑙𝑢𝑟𝑒} will be almost 1.

Prof. Abhishek Dixit

Fixed-to-fixed length source code
• If 𝐿ത = 𝐻 𝑋 − 2ε
• Total number of codewords: 2𝑛𝐻 𝑋 −2ε𝑛
• Number of typical 𝑛 tuples > 1 − δ 2𝑛𝐻 𝑋 −ε𝑛
2−ε𝑛
• Aggregate probability of typical sequences assigned codeword <
1−δ
𝑛 1−δ−2−ε𝑛
• 𝑃𝑟 {𝐹/𝑇ε }> 𝑃𝑟 {𝑇ε𝑛 }> 1 − δ
1−δ
• 𝑃𝑟 {𝐹}> 1 − δ − 2−ε𝑛
• 𝑃𝑟 {𝐹} → 1

Prof. Abhishek Dixit

Advantages/disadvantages of fixed-to-fixed length source
code
• Buffering issues of prefix-free codes are minimized
• But not at all a practical code.
• 𝑛 is very large, latency will be huge
• Only used for conceptual understanding

Prof. Abhishek Dixit

Kraft Inequality for uniquely decodable codes
• σ𝑖 2−𝑙𝑖 = 𝑏 𝑏 > 1
1 −𝑙
• 𝑝𝑖 = 2 𝑖
𝑏
1 −𝑙
• 𝐻 𝑋 = σ𝑖 −𝑝𝑖 log 𝑝𝑖 = σ𝑖 −𝑝𝑖 log 2 𝑖 = σ𝑖 𝑝𝑖 log 𝑏 + σ𝑖 𝑝𝑖 𝑙𝑖
𝑏
• 𝐻 𝑋 = log 𝑏 + 𝐿ത
• 𝐿ത = 𝐻 𝑋 − log 𝑏

Prof. Abhishek Dixit

Kraft Inequality for uniquely decodable codes
• σ𝑖 2−𝑙𝑖 = 𝑏 𝑏 > 1
1 −𝑙
• 𝑝𝑖 = 2 𝑖
𝑏
1 −𝑙
• 𝐻 𝑋 = σ𝑖 −𝑝𝑖 log 𝑝𝑖 = σ𝑖 −𝑝𝑖 log 2 𝑖 = σ𝑖 𝑝𝑖 log 𝑏 + σ𝑖 𝑝𝑖 𝑙𝑖
𝑏
• 𝐻 𝑋 = log 𝑏 + 𝐿ത
• 𝐿ത = 𝐻 𝑋 − log 𝑏
• Consider a string of 𝑛 source letters. Concatenation of code words has length
less than 𝑛 𝐻 𝑋 − log 𝑏 + ε with high probability. Thus, fixed length code of
this length has low failure probability. Contradiction.

Prof. Abhishek Dixit

Markov sources
• Takes into account dependence
• Def: Markov sources are defined in terms of finite-state Markov chains.

Prof. Abhishek Dixit

Markov chains
• Example: Binary source (not interesting but simple)
• Binary source has outputs 𝑋1 , 𝑋2 ,…
• Suppose the probability that we transmit 𝑋𝑘 depends upon 𝑋𝑘−1 and 𝑋𝑘−2
• We can denote state 𝑆𝑘−1 = {𝑋𝑘−2 , 𝑋𝑘−1 }
• Thus, how many different states?

Prof. Abhishek Dixit

Markov chains
• Example: Binary source (not interesting but simple)
• Binary source has outputs 𝑋1 , 𝑋2 ,…
• Suppose the probability that we transmit 𝑋𝑘 depends upon 𝑋𝑘−1 and 𝑋𝑘−2
• We can denote state 𝑆𝑘−1 = {𝑋𝑘−2 , 𝑋𝑘−1 }
• Thus, how many different states?

00 01

10 11

Prof. Abhishek Dixit

Markov chains
• Example: Binary source (not interesting but simple)
• Binary source has outputs 𝑋1 , 𝑋2 ,…
• Suppose the probability that we transmit 𝑋𝑘 depends upon 𝑋𝑘−1 and 𝑋𝑘−2
• We can denote state 𝑆𝑘−1 = {𝑋𝑘−2 , 𝑋𝑘−1 }
• Thus, how many different states?
{o,n} {o,n}
00 01

{o,n} {o,n}
10 11

Prof. Abhishek Dixit

Markov chains
• Example: Binary source (not interesting but simple)
• Binary source has outputs 𝑋1 , 𝑋2 ,…
• Suppose the probability that we transmit 𝑋𝑘 depends upon 𝑋𝑘−1 and 𝑋𝑘−2
• We can denote state 𝑆𝑘−1 = {𝑋𝑘−2 , 𝑋𝑘−1 }
• Thus, how many different states?
{o,n} {o,n}
1
00 01

{o,n} {o,n}
10 11

Prof. Abhishek Dixit

Markov chains
• Example: Binary source (not interesting but simple)
• Binary source has outputs 𝑋1 , 𝑋2 ,…
• Suppose the probability that we transmit 𝑋𝑘 depends upon 𝑋𝑘−1 and 𝑋𝑘−2
• We can denote state 𝑆𝑘−1 = {𝑋𝑘−2 , 𝑋𝑘−1 }
• Thus, how many different states?
{o,n} {o,n}
1
00 01

{o,n} {o,n}
10 11

Prof. Abhishek Dixit

Markov chains
• Example: Binary source (not interesting but simple)
• Binary source has outputs 𝑋1 , 𝑋2 ,…
• Suppose the probability that we transmit 𝑋𝑘 depends upon 𝑋𝑘−1 and 𝑋𝑘−2
• We can denote state 𝑆𝑘−1 = {𝑋𝑘−2 , 𝑋𝑘−1 }
• Thus, how many different states?
{o,n} {o,n}
1
00 01

{o,n} {o,n}
10 11 1

Prof. Abhishek Dixit

Markov chains
• Example: Binary source (not interesting but simple)
• Binary source has outputs 𝑋1 , 𝑋2 ,…
• Suppose the probability that we transmit 𝑋𝑘 depends upon 𝑋𝑘−1 and 𝑋𝑘−2
• We can denote state 𝑆𝑘−1 = {𝑋𝑘−2 , 𝑋𝑘−1 }
• Thus, how many different states?
0 {o,n} {o,n}
1
00 01

1
0 1
0
{o,n} {o,n}
10 11 1
0

Prof. Abhishek Dixit

Markov chains
0 {o,n} {o,n}
1
00 01

1
0 1
0
{o,n} {o,n}
10 11 1
0

State transitions {00} [(00),(01),(10),(00),(00),(01),(11),(11),(11),(10),(01)]

Output {00} [(0), (1), (0), (0), (0), (1), (1), (1), (1), (0), (1)]

Prof. Abhishek Dixit

Markov chains
0 {o,n} {o,n}
1
00 01

1
0 1
0
{o,n} {o,n}
10 11 1
0

State transitions {00} [(00),(01),(10),(00),(00),(01),(11),(11),(11),(10),(01)]

Output {00} [(0), (1), (0), (0), (0), (1), (1), (1), (1), (0), (1)]

State transitions ≡ Output

Prof. Abhishek Dixit

Markov chains
0; 0.9 {o,n} {o,n}
1; 0.1
00 01

1; 0.5
0; 0.5 1; 0.5
0; 0.5
{o,n} {o,n}
10 11 1; 0.9
0; 0.1

State transitions {00} [(00),(01),(10),(00),(00),(01),(11),(11),(11),(10),(01)]

Output {00} [(0), (1), (0), (0), (0), (1), (1), (1), (1), (0), (1)]

State transitions ≡ Output

Prof. Abhishek Dixit

Markov chain
• Definition: A finite-state Markov chain is a sequence 𝑆0 , 𝑆1 , … of discrete random
symbols from a finite alphabet, 𝕊. There is a pmf 𝑞0 (𝑠), 𝑠 ∈ 𝕊 on 𝑆0 , and there is
a conditional pmf 𝑄(𝑠|𝑠 ′ ) such that, for all 𝑘 ≥ 1, all 𝑠 ∈ 𝕊, and all 𝑠 ′ ∈ 𝕊,
𝑃𝑟 𝑆𝑘 = 𝑠|𝑆𝑘−1 = 𝑠 ′ = 𝑃𝑟 𝑆𝑘 = 𝑠|𝑆𝑘−1 = 𝑠 ′ … . 𝑆0 = 𝑠0 = 𝑄(𝑠|𝑠 ′ ).

Prof. Abhishek Dixit

Markov chain
• Definition: A finite-state Markov chain is a sequence 𝑆0 , 𝑆1 , … of discrete random
symbols from a finite alphabet, 𝕊. There is a pmf 𝑞0 (𝑠), 𝑠 ∈ 𝕊 on 𝑆0 , and there is
a conditional pmf 𝑄(𝑠|𝑠 ′ ) such that, for all 𝑘 ≥ 1, all 𝑠 ∈ 𝕊, and all 𝑠 ′ ∈ 𝕊,
𝑃𝑟 𝑆𝑘 = 𝑠|𝑆𝑘−1 = 𝑠 ′ = 𝑃𝑟 𝑆𝑘 = 𝑠|𝑆𝑘−1 = 𝑠 ′ … . 𝑆0 = 𝑠0 = 𝑄(𝑠|𝑠 ′ ).

• Interpretation

Prof. Abhishek Dixit

Markov chain
• Definition: A finite-state Markov chain is a sequence 𝑆0 , 𝑆1 , … of discrete random
symbols from a finite alphabet, 𝕊. There is a pmf 𝑞0 (𝑠), 𝑠 ∈ 𝕊 on 𝑆0 , and there is
a conditional pmf 𝑄(𝑠|𝑠 ′ ) such that, for all 𝑘 ≥ 1, all 𝑠 ∈ 𝕊, and all 𝑠 ′ ∈ 𝕊,
𝑃𝑟 𝑆𝑘 = 𝑠|𝑆𝑘−1 = 𝑠 ′ = 𝑃𝑟 𝑆𝑘 = 𝑠|𝑆𝑘−1 = 𝑠 ′ … . 𝑆0 = 𝑠0 = 𝑄(𝑠|𝑠 ′ ).

• Interpretation
• Probability of transition depends only upon the previous state.
• The transition probabilities do not change with time.

Prof. Abhishek Dixit

Markov source
• A Markov source is a sequence of discrete random symbols 𝕏1 , 𝕏2 , … with a
common alphabet 𝕏 which is based on a finite-state Markov chain 𝑆0 , 𝑆1 , ….
Each transition 𝑠 ′ → 𝑠 in the Markov chain is labelled with a symbol from 𝕏:
each symbol from 𝕏 can appear on at most one outgoing transition from each
state.

Prof. Abhishek Dixit

Markov source
• A Markov source is a sequence of discrete random symbols 𝕏1 , 𝕏2 , … with a
common alphabet 𝕏 which is based on a finite-state Markov chain 𝑆0 , 𝑆1 , ….
Each transition 𝑠 ′ → 𝑠 in the Markov chain is labelled with a symbol from 𝕏:
each symbol from 𝕏 can appear on at most one outgoing transition from each
state.
• Why we differentiate between source outputs and states?

Prof. Abhishek Dixit

Markov source
• A Markov source is a sequence of discrete random symbols 𝕏1 , 𝕏2 , … with a
common alphabet 𝕏 which is based on a finite-state Markov chain 𝑆0 , 𝑆1 , ….
Each transition 𝑠 ′ → 𝑠 in the Markov chain is labelled with a symbol from 𝕏:
each symbol from 𝕏 can appear on at most one outgoing transition from each
state.
• Why we differentiate between source outputs and states?
• State represents a combination of past events rather than just the previous source output.
• Markov source provide reasonable models for surprising complex forms of memory.

Prof. Abhishek Dixit

Period of a state
0 1
00 01

1
0 1
0

10 11 1
0

Prof. Abhishek Dixit

Period of a state
0 1
00 01

1
0 1
0

10 11 1
0

Prof. Abhishek Dixit

Period of a state
0 1
00 01

1
0 1
0

10 11 1
0

Number of transitions = 1

Prof. Abhishek Dixit

Period of a state
0 1
00 01

1
0 1
0

10 11 1
0

Number of transitions = 1

Number of transitions = 3

Prof. Abhishek Dixit

Period of a state
0 1
00 01

1
0 1
0

10 11 1
0

Number of transitions = 1

Number of transitions = 3

Number of transitions = 4

Prof. Abhishek Dixit

Period of a state
0 1
00 01

1
0 1
0

10 11 1
0

Number of transitions = 1

Number of transitions = 3 Period = gcd 1,3,4 = 1

Number of transitions = 4

Prof. Abhishek Dixit

Period of a state
0 1
00 01

1
0 1
0

10 11 1
0

Number of transitions = 1

Number of transitions = 3 Period = gcd 1,3,4 = 1

Number of transitions = 4 If period is 1, then the state is aperiodic

Prof. Abhishek Dixit

Ergodic Markov chain
0 1
00 01

1
0 1
0

10 11 1
0

Ergodic Markov chain is the one where all states are aperiodic and are accessible
from one another.

Prof. Abhishek Dixit

Ergodic Markov chain
0 1
00 01

1
0 1
0

10 11 1
0

Ergodic Markov chain have steady state probabilities.

Prof. Abhishek Dixit

Ergodic Markov chain
0 1
00 01

1
0 1
0

10 11 1
0

Ergodic Markov chain have steady state probabilities.

𝑞 𝑠 = σ𝑠′ 𝑞 𝑠 ′ 𝑄(𝑠|𝑠 ′ ) & σ𝑠 𝑞 𝑠 = 1

lim 𝑃𝑟 𝑆𝑘 = 𝑠 𝑆0 = 𝑠 ′ = 𝑞(𝑠)
𝑘→∞

Prof. Abhishek Dixit

Coding for Markov sources
• Use prefix-free code for each state in the Markov chain.
• Then, we get
• 𝐻 𝑋|𝑠 ≤ 𝐿ത 𝑚𝑖𝑛 𝑠 < 𝐻 𝑋|𝑠 + 1
• where 𝐻 𝑋|𝑠 = σ𝑥 −𝑝𝑋 𝑥|𝑠 log 𝑝𝑋 𝑥|𝑠

• σ𝑠 𝑞 𝑠 𝐻 𝑋|𝑠 ≤ σ𝑠 𝑞(𝑠) 𝐿ത 𝑚𝑖𝑛 𝑠 < σ𝑠 𝑞(𝑠) 𝐻 𝑋|𝑠 + σ𝑠 𝑞(𝑠)

Prof. Abhishek Dixit

Coding for Markov sources
• σ𝑠 𝑞 𝑠 𝐻 𝑋|𝑠 ≤ σ𝑠 𝑞(𝑠) 𝐿ത 𝑚𝑖𝑛 𝑠 < σ𝑠 𝑞(𝑠) 𝐻 𝑋|𝑠 + σ𝑠 𝑞(𝑠)

• Let us define
• 𝐿ത 𝑚𝑖𝑛 ≝ σ𝑠 𝑞(𝑠) 𝐿ത 𝑚𝑖𝑛 𝑠
• 𝐻 𝑋|𝑆 ≝ σ𝑠 𝑞(𝑠) 𝐻 𝑋|𝑠

• 𝐻 𝑋|𝑆 ≤ 𝐿ത 𝑚𝑖𝑛 < 𝐻 𝑋|𝑆 + 1

• In Markov chain, we get new lower bound of 𝐻 𝑋|𝑆

Prof. Abhishek Dixit

Coding for Markov sources
• σ𝑠 𝑞 𝑠 𝐻 𝑋|𝑠 ≤ σ𝑠 𝑞(𝑠) 𝐿ത 𝑚𝑖𝑛 𝑠 < σ𝑠 𝑞(𝑠) 𝐻 𝑋|𝑠 + σ𝑠 𝑞(𝑠)

• Let us define
• 𝐿ത 𝑚𝑖𝑛 ≝ σ𝑠 𝑞(𝑠) 𝐿ത 𝑚𝑖𝑛 𝑠
• 𝐻 𝑋|𝑆 ≝ σ𝑠 𝑞(𝑠) 𝐻 𝑋|𝑠

• 𝐻 𝑋|𝑆 ≤ 𝐿ത 𝑚𝑖𝑛 < 𝐻 𝑋|𝑆 + 1

• In Markov chain, we get new lower bound of 𝐻 𝑋|𝑆
• 𝐻 𝑋|𝑆 ≤ 𝐻 𝑋 : This shows that dependency is better !

Prof. Abhishek Dixit

The LZ77 universal algorithm
• Problems with conventional encoder and decoder?

Prof. Abhishek Dixit

The LZ77 universal algorithm
• Problems with conventional encoder and decoder?
• You need to spend (all the time in your life) to learn about the source statistics
• You need to do this for each and every source
• Things are not universal !

Prof. Abhishek Dixit

The LZ77 universal algorithm
• A universal data compressor operates without source statistics. We describe a
standard string matching algorithm for this due to Ziv and Lempel (LZ77).
• In principle, a universal algorithm attempts to model the source and to encode it
simultaneously.
• With instantaneous decoding, the decoder knows the past also, and thus can
track the encoder.

Prof. Abhishek Dixit

The LZ77 universal algorithm
• Objective:
• Given the output from a given probability model (say a Markov source);
• 𝐿ത should be almost as small as for an algorithm designed for that model.
• Also the algorithm should compress well in the absence of any ordinary kind
of statistical structure.
• It should deal with gradually changing statistics.

Prof. Abhishek Dixit

The LZ77 universal algorithm
• The Lempel-Ziv algorithm matches the longest string of yet uncoded symbols with strings
starting in the window
• 𝑤 is typically power of 2 and ranges between 210 to 220 .
• Complexity and performance increases with 𝑤.
𝑤 = 𝑤𝑖𝑛𝑑𝑜𝑤 P 𝑛=3
match
𝑎𝑐 𝑑 𝑏𝑐 𝑑𝑎 𝑐𝑏 𝑎𝑏𝑎𝑐 𝑑 𝑏𝑐 𝑎𝑏 𝑎𝑏𝑑 𝑐 𝑎…
𝑢=7

Prof. Abhishek Dixit

The LZ77 universal algorithm
The compression algorithm:
1) Encode the first 𝑤 symbols without compression, using log 𝑀 binary digits
per symbol.
(𝑤 log 𝑀 gets amortized over the sequence so we do not care about it).
2) Set the pointer 𝑃 = 𝑤.
(As the algorithm runs, 𝑥1𝑃 (𝑥1 , 𝑥2 , … , 𝑥𝑃 ) is the already encoded string of
source symbols and 𝑥𝑃+1 is the first new symbol to be encoded).

Prof. Abhishek Dixit

The LZ77 universal algorithm
𝑃+𝑛 𝑃−𝑢+𝑛
3) Find the largest 𝑛 ≥ 2 such that 𝑥𝑃+1 = 𝑥𝑃−𝑢+1 for some 𝑢, 1 ≤ 𝑢 ≤ 𝑤. Set
𝑛 = 1 otherwise.
𝑤 = 𝑤𝑖𝑛𝑑𝑜𝑤 P 𝑛=3
match
𝑎𝑐 𝑑 𝑏𝑐 𝑑 𝑎 𝑐 𝑏 𝑎𝑏𝑎𝑐 𝑑 𝑏𝑐 𝑎𝑏 𝑎𝑏𝑑 𝑐 𝑎…
𝑢=7

𝑤 = 𝑤𝑖𝑛𝑑𝑜𝑤 P 𝑛=4
match
𝑎𝑐 𝑑 𝑏 𝑐 𝑑 𝑎𝑐 𝑏 𝑎𝑏𝑎𝑐 𝑑 𝑎𝑏𝑎𝑏 𝑎𝑏𝑑 𝑐 𝑎…
𝑢=2

Prof. Abhishek Dixit

Unary-binary code
4) Encode the match size 𝑛 into a codeword from the so-called unary-binary code.
The positive integer 𝑛 is encoded into the binary representation of 𝑛, preceded by
a prefix of log 𝑛 zeroes; i.e.,

𝒏 Prefix Base 2 expansion Codeword

1 1 1
2 0 10 010
3 0 11 011
4 00 100 00100
5 00 101 00101
6 00 110 00110
7 00 111 00111
8 000 1000 0001000

Prof. Abhishek Dixit

The LZ77 universal algorithm
5) If 𝑛 > 1, encode the positive integer 𝑢 ≤ 𝑤 using a fixed-length code of length
log 𝑤 bits.
(At this point the decoder known 𝑛, and can simply count back by 𝑢 in the
previously decoded string to find the appropriate 𝑛-tuple, even if there is overlap
as above).
If 𝑛 = 1, encode the single letter without compression.
6) These two above cases are separated by a flag bit.
0 𝒖 (𝒍𝒐𝒈𝒘) 𝒏 (≈ 𝟐𝒍𝒐𝒈𝒏)

1 𝒖𝒏𝒄𝒐𝒎𝒑𝒓𝒆𝒔𝒔𝒆𝒅 ( 𝒍𝒐𝒈 𝑴 )

7) Set the pointer 𝑃 to 𝑃 + 𝑛 and go to step (2). (Iterate for ever).

Prof. Abhishek Dixit

Approximate Analysis of the LZ77 universal algorithm
• (AEP): For any large 𝑛, 𝑇ε𝑛 = 2𝑛𝐻(𝑋|𝑆) of length 𝑛.
• Window size:
• 𝑤 starting points → 𝑤 strings of length 𝑛
• 𝑤 ≪ 2𝑛𝐻(𝑋|𝑆) , most typical sets are not found, meaning that the match is unlikely.
• 𝑤 ≈ 𝑇ε𝑛 = 2𝑛𝐻 𝑋 𝑆
log 𝑤
• Typical match size: 𝑛 ≈
𝐻(𝑋|𝑆)
• Encode match: log 𝑤 + 2 log 𝑛 ≈ log 𝑤
𝐻(𝑋|𝑆)log 𝑤
• Bpss: = 𝐻(𝑋|𝑆)
log 𝑤

Prof. Abhishek Dixit

Appendix 1: Coding for Markov sources
• 𝐻 𝑋|𝑆 = σ𝑠 𝑞(𝑠) 𝐻 𝑋|𝑠 = σ𝑠,𝑥 −𝑞 𝑠 𝑝𝑋 (𝑥|𝑠) log 𝑝𝑋 (𝑥|𝑠)
1
• 𝐻 𝑋𝑆 = σ𝑠,𝑥 𝑞(𝑠)𝑝𝑋 (𝑥|𝑠) log
𝑞(𝑠)𝑝𝑋 (𝑥|𝑠)
1 1
• 𝐻 𝑋𝑆 = σ𝑠,𝑥 𝑞(𝑠)𝑝𝑋 (𝑥|𝑠) log + σ𝑠,𝑥 𝑞(𝑠)𝑝𝑋 (𝑥|𝑠) log
𝑞(𝑠) 𝑝𝑋 (𝑥|𝑠)
• 𝐻 𝑋𝑆 = 𝐻 𝑆 + 𝐻 𝑋|𝑆

Prof. Abhishek Dixit

Appendix 2: Conditional entropy
𝐻 𝑋𝑌 = ෍ −𝑝𝑋,𝑌 𝑥, 𝑦 log 𝑝𝑋,𝑌 𝑥, 𝑦
𝑥,𝑦

𝐻 𝑋 = ෍ −𝑝𝑋,𝑌 𝑥, 𝑦 log𝑝𝑋 𝑥 = ෍ −𝑝𝑋 𝑥 log𝑝𝑋 𝑥

𝑥,𝑦 𝑥

𝐻 𝑌 = ෍ −𝑝𝑋,𝑌 𝑥, 𝑦 log𝑝𝑌 𝑦 = ෍ −𝑝𝑌 𝑦 log 𝑝𝑌 𝑦

𝑥,𝑦 𝑦

𝐻 𝑋𝑌 − 𝐻 𝑋 − 𝐻 𝑌 = ෍ −𝑝𝑋,𝑌 𝑥, 𝑦 log 𝑝𝑋,𝑌 𝑥, 𝑦 + 𝑝𝑋,𝑌 𝑥, 𝑦 log 𝑝𝑋 𝑥 +𝑝𝑋,𝑌 𝑥, 𝑦 log 𝑝𝑌 𝑦

𝑥,𝑦
𝑝𝑋 𝑥 𝑝𝑌 𝑦
𝐻 𝑋𝑌 − 𝐻 𝑋 − 𝐻 𝑌 = ෍ 𝑝𝑋,𝑌 𝑥, 𝑦 log
𝑝𝑋,𝑌 𝑥, 𝑦
𝑥,𝑦

Prof. Abhishek Dixit

Appendix 2: Conditional entropy
𝑝𝑋 𝑥 𝑝𝑌 𝑦
𝐻 𝑋𝑌 − 𝐻 𝑋 − 𝐻 𝑌 = ෍ 𝑝𝑋,𝑌 𝑥, 𝑦 log
𝑝𝑋,𝑌 𝑥, 𝑦
𝑥,𝑦

𝑝𝑋 𝑥 𝑝𝑌 𝑦
𝐻 𝑋𝑌 − 𝐻 𝑋 − 𝐻 𝑌 ≤ ෍ 𝑝𝑋,𝑌 𝑥, 𝑦 − 1 log 𝑒 = 0
𝑝𝑋,𝑌 𝑥, 𝑦
𝑥,𝑦

𝐻 𝑋𝑌 ≤ 𝐻 𝑋 + 𝐻 𝑌

Prof. Abhishek Dixit

Appendix 3
• 𝐻 𝑋𝑆 = 𝐻 𝑆 + 𝐻 𝑋|𝑆 (Proven in Appendix 1)
• 𝐻 𝑋𝑆 ≤ 𝐻 𝑆 + 𝐻 𝑋 (Proven in Appendix 2)
• Using 1 and 2,
𝐻 𝑋|𝑆 ≤ 𝐻 𝑋

Prof. Abhishek Dixit

 Thanks for your attention &
Questions ?

Prof. Abhishek Dixit 159