tr>
Microsoft PowerPoint - 01d Source coding 1
D.1
Source Coding
·
Source coding reduces redundancy and hence reduces
bandwidth requirement.
For the source encoder to be efficient, we require the
knowledge of the statistics of the source.
Example: If some source symbols are known to be more
probable than others, shorter codewords should be assigned
to these symbols
Source
Encoder
Channel
Encoder
Digital
Source
Source
Entropy
Symbols
Binary
sequence
Modulator
D.2
Efficient Source Encoding
Need to know statistics of source
For exam ple :
1) Frequent sym bols
assign short code word
2) Rare sym bols
assign long code word
Variable-length Code
(M orse Code)
Sym bols occur with different
probability
(eg. Alphabet in the English
Language)
Use Variable length
Code
Sym bols are equally probable
to happen and/or statistically
independent
Use Code word with
fixed block length
ie. 4 sym bols A B C D
A 00
B 01
C 10
D 11
Code according to the probability of
occurrence of the source sym bols

ENTRO PY CO DING 2
D.3
Shannons source coding theorem
Given a discrete memoryless source of entropy H(X), the
average codeword length L
av
for any distortionless source
coding scheme is bounded as
According to this theorem, the source entropy
represents a fundamental limit on the average number of bits
per source symbol necessary to represent a discrete
memoryless source in that it can be made as small as, but no
smaller than the source entropy.
)
(X
H
L
av )
(X
H
D.4
Source Efficiency
Source efficiency
At the receiver,
Note: Symbol to Sequence or Sequence to Symbol is a one
to one mapping
av
L
X
H
/
)
(
= 1
Symbols
Channel
Decoder
Binary
sequence 3
D.5
Example 1
H(X) = 1.71 bits/symbol
The symbols are coded in 3 different ways using variable-
length code as below.
Source symbols
Discrete
Memory
Source
(DMS)
A, B, C, D
8
/
1
)
(
8
/
1
)
(
4
/
1
)
(
/2
1
)
(
=
=
=
=
D
P
C
P
B
P
A
P
D.6
Example 1
Source
Symbol
Probability
of Occurence
Code I
Code II Code III
A
1/2
1
0
0
B
1/4
00
10
01
C
1/8
01
110
011
D
1/8
10
111
111
L
av
H(X)=1.71
1.5
1.75
1.75 4
D.7
Code I
There is a problem in this decoding process.
Suppose we have 001001..
Is this B,A,B,A, or B,D,C,?
Code I is not uniquely decodable.
Sometimes this ambiguity can be resolved by waiting for
additional bits. But then the decoding is not instantaneous
and not desirable in practice.
D.8
Code II
Uniquely decodable and instantaneous.
1
C
1
1
B
A
D
0
0
0
Initial state
Code tree for
code II 5
D.9
Code III
Uniquely decodable but not instantaneously decodable.
A
B
C
D
1
1
1
1
1
0
Code tree for code III
D.10
Instantaneously decodable
Question: How can we have codes that are instantaneously
decodable?
Answer: No code word in the code is a prefix of another code
word.
For a given code word of length k,

is a prefix of
Prefix condition requires that for any code word , there
is no other code having the same l elements
.
k
C
[
]
k
k
b
b
b
b
C
=
3
2
1
[
]
l
l
b
b
b
b
C
=
3
2
1
k
C
k
l
<
k
C
l
C
[
]
l
b
b
b
b
3
2
1 6
D.11
Kraft inequality
A prefix code always satisfy the Kraft inequality
where
are the lengths of the
codewords.
Note: Kraft inequality does not tell us that a source code is a
prefix code. Rather, it is merely a condition on the codeword
lengths of the code and not on the code words themselves.
L
n
n
n
n
...
3
2
1
1
2
1
= L
k
n
k
D.12
Example
Code I violates the Kraft inequality; it cannot be a prefix
code.
Kraft inequality is satisfied by both codes II and III; but only
code II is a prefix code. 7
D.13
Average code word length
In the limit, as n approaches infinity, we have
Therefore, the average codeword length of an extended prefix
code can be make as small as the entropy of the source.
However, the price we have to pay for decreasing the
average code-word length is incrased decoding complexity.
n
X
H
L
X
H
X
nH
L
X
nH
X
H
L
X
H
X
H
L
X
H
n
av
n
av
n
n
av
n
av
/
1
)
(
)
(
1
)
(
)
(
1
)
(
)
(
1
)
(
)
(
+ + + +
)
(
1
lim
X
H
L
n
n
av
n
=
D.14
Shannon-Fano Encoding
Variable-length encoding scheme proposed by Shannon and
Fano and the algorithm is simply stated as below.
For M possible messages with probability
and N symbols per message, a unique binary codeword of
length for message i can be generated such that the
average number of bits per symbol is closer to where


as before
M
P
P
P
,...,
,
2
2
i
C
i
l
N
av
L
N
G
)
(
log
)
(
1
2
i
i
i
N
m
P
m
P
N
G
= 8
D.15
In other words ,
where

might or might not be the same.
High probability messages will have short codewords. Each
message has a unique codeword and can be decoded
uniquely.
N
M
i
i
i
av
G
P
l
N
L = =1
1
1 X X X.X
2 X X X.X
.
.
.
M X X X.X
Encoding
C
1
(length l
1
)
C
2
(length l
2
)
.
.
.
C
M
(length l
M
)
M possible
message of
N symbols long
M
l
l
l
,...
,
2
1
D.16
The average number of bits per symbol (entropy) is bounded
by
Encoder rate efficiency e is

H: Source Entropy
N
G
L
G
N
av
N
/
1
+
< av
L
H
=
9
D.17
Coding: Step 1
Arrange the N messages in order of decreasing probability
and let
with
i.e.
=
=
1
1
i
k
k
i
P
F
0
1
=
F
N
N
F
F
F
P
P
P
:
:
2
1
2
1 D.18
Step 2
Calculate the number of bits required for message i by the
following equation
For example,
,

and
i
l
i
i
i
P
l
P
2
2
log
1
log <
5
/
1
=
i
P
32
.
2
)
5
/
1
(
log
2
= 32
.
3
)
5
/
1
(
log
1
2
= 3
= i
l 10
D.19
Step 3-4
Convert into a binary fraction. The binary fraction
satisfies the following equality
For example,

Step 4
The code word for message i is the truncated version of the
fraction F
i
and has length .
i
F
k
k
k
b
b
b
b
b
b
b
2
...
2
2
2
2
1
3
2
1
+
+
+
=
0011011
2
1
2
1
2
0
2
1
2
1
2
0
2
0
128
1
64
1
32
0
16
1
8
1
4
0
2
0
128
27
7
6
5
4
3
2 +
+
+
+
+
+
=
+
+
+
+
+
+
=
i
l
D.20
Example 2
i
Message
i
P
i
F
i
l
Binary
i
F
Codeword
1 AAA
128
27
0
3
0000000
000
2 BBB
128
27
128
27
3
0011011
001
3 CAA
128
9
128
54
4
0110110
0110 11
D.21
Example 3
Consider a Markov source encoder with N =2 symbols per
message per message. The encoding operation is
i
Symbols
i
P
i
l
Codeword
i
F
Binary
i
F
1 AA
32
9
2
00
2 BB
32
9
2
01
3 AC
32
9
4
1001
4 CB
32
3
4
1010
5 BC
32
3
4
1100
6 CA
32
3
4
1101
7 CC
32
2
4
1111
D.22
Example 3
The decoding is accomplished by
matching the incoming data with
the codewords having the least
number of bits until there is no
match. The incoming data is the
matched with the codewords
having the second smallest
number o bits, then so on.
symbol
bit
H
N
/
44
.
1
=
Source
Encoder
CA,AA,BB,BC
1101,00,01,1100
For example,

1101 00 10 1100
No Match
CA
AA 12
D.23
Huffman encoding
Variable-length scheme for the encoding of symbols. Arrange the source symbols in descending order of
probability Create a new source with one less symbol by combining
(adding) the two symbols having the lowest probability. Repeat step 1 and 2 until a single -symbol source is
achieved. Associate '1' and a '0' with each pair of probabilities so
combined. Encode each original source symbol into binary sequence
generated by the various combinations, with the first
combination as the least significant digit in thee sequence.
D.24
Example 4
Source symbols
A,B,C,D,E
and probabilities are P(
A
)=0.4,
P(
B
) =0.2, P(
C
) =0.2, P(
D
)=0.1, P(
E
)=0.1
A
encodes into 1
B
encodes into 01
C
encodes into 000
D
encodes into 0010
E
encodes into 0011
A
B
C
D
E
0.4
0.2
0.2
0.1
0.1
0.4
0.2
0.2
0.2
0.4
0.4
0.2
0.6
0.4
1.0
1
0
0
0
0
1
1
1 13
D.25
Note that the Huffman's encoding rule is uniquely
decodable; i.e. a stream of encoded symbols can decoded
without the need for synchronization or forming pulses
between the binary sequences representing each symbol. The
tree diagram confirms this property, since no encoded
sequence is a prefix to another/any other valid sequence.
Example:
The encoded sequence for symbol
C
is not a prefix of any
other valid sequence.
Example 4
D.26
Source Entropy

Example 4
0
0
0
0
1
1
1
1
A
B
C
D
E
Tree Diagram
Initial state
)
(
log
)
(
2
1
i
m
i
i
P
P
X
H = =
[
] [
]
1
.
0
log
1
.
0
2
2
.
0
log
2
.
0
2
4
.
0
log
4
.
0
2
2
2 =
l
bits/symbo

12
.
2
= 14
D.27
Example 4
If P(
A
) = P(
B
) = P(
C
) = P(
D
) = P(
E
),

Source efficiency before encoding =
= 0.913
max
)
(
)
(
X
H
X
H
=
[
]
l
bits/symbo

322
.
2


2
.
0
log
2
.
0
5
)
(
2
max
= = X
H
MAX
X
H
X
H
)
(
)
(
D.28
Example 4
The average number
L
av
of digits used to encode each source
symbol after encoding is
0.4(1) + 0.2(2) + 0.2(3) +0.1(4)+0.1(4) = 2.2 bit/symbol
Source efficiency after encoding is =
H
(
X
)/
L
av
=0.964
1- : defined as the source redundancy.
M
: number of binary digits required to represent the source
without any source coding
L
av
/
M
: compression ratio
CR
.
In our example,
M
=3 and
CR
= 2.2/3 = 0.73
CR
indicates the proportion by which the bandwidth
required to transmit the source over a binary channel can be
reduced. 15
D.29
Run-length Coding
Run length coding technique is particularly suitable for
binary sources where one of the symbols (the '1' say) occurs
very much less often