'

Source Coding

1. Source symbols encoded in binary 2. The average codelength must be reduced 3. Remove redundancy reduces bit-rate Consider a discrete memoryless source on the alphabet S = {s0 , s1 , , sk } Let the corresponding probabilities be {p0 , p1 , , pk } and codelengths be {l0 , l1 , , lk }. Then, the average codelength(average number of bits per symbol) of the source is dened as & %

' L=

K1

$ pk ll

k=0

If Lmin is the minimum possible value of L, then the coding eciency of the source is given by .

Lmin = L For an ecient code approaches unity. The question: What is smallest average codelength that is possible? The Answer: Shannons source coding theorem Given a discrete memoryless source of entropy H(s), the average codeword length L for any distortionless source encoding scheme is bounded by &

'

L H(s)

Since, H(s) is the fundamental limit on the average number of bits/symbol, we can say Lmin H(s) H(s) = = L Data Compaction: 1. Removal of redundant information prior to transmission. 2. Lossless data compaction no information is lost. 3. A source code which represents the output of a discrete memoryless source should be uniquely decodable. & %

'

Source Coding Schemes for Data Compaction

Prex Coding 1. The Prex Code is variable length source coding scheme where no code is the prex of any other code. 2. The prex code is a uniquely decodable code. 3. But, the converse is not true i.e., all uniquely decodable codes may not be prex codes.

&

'

Table 1: Illustrating the denition of prex code [Link] Occurrence 0.5 0.25 0.125 0.125 Code I 0 1 00 11 Code II 0 10 110 111 Code III 0 01 011 0111

Symbol s0 s1 s2 s3

Table 2: Table is reproduced from [Link] book on Communication Systems From 1 we see that Code I is not a prex code. Code II is a prex code. Code III is also uniquely decodable but not a prex code. Prex codes also satises Kraft-McMillan inequality which is given by & %

'

K1

$ 2lk 1

k=0

Kraft-McMillan inequality maps codewords to a binary tree as shown is Figure 1.

s 0 Initial State 1 0 1 s 0 s
2 1 0

1 s
3

Figure 1: Decision tree for Code II Given a discrete memoryless source of entropy H(s), a prex code can be constructed with an average code-word length which is l, & %

' bounded as follows:

H(s) < H(s) + 1 (L)

(1)

The left hand side of the above equation, the equality is satised owing to the condition that, any symbol sk is emitted with the probability

pk = 2lk

(2)

where, lk is the length of the codeword assigned to the symbol sk . Hence, from Eq. 2, we have & %

'
K1 K1

2lk =
k=0 k=0

pk = 1

(3)

With this condition, the Kraft-McMillan inequality tells that a prex code can be constructed such that the length of the codeword assigned to source symbol sk is log2 pk . Therefore, the average codeword length is given by

K1

L=
k=0

lk 2lk

(4)

and the corresponding entropy is given by & %

'

K1

H(s) =
k=0 K1

1 2lk lk 2lk

log2 (2lk ) (5)

=
k=0

Hence, from Eq. 5, the equality condition on the leftside of Eq. 1, L = H(s) is satised. To prove the inequality condition we will proceed as follows: Let Ln denote the average codeword length of the extended prex code. For a uniquely decodable code, Ln is the smallest possible. & %

'

Human Coding

1. Human code is a prex code 2. The length of codeword for each symbol is roughly equal to the amount of information conveyed. 3. The code need not be unique (see Figure 3) A Human tree is constructed as shown in Figure. 3, (a) and (b) represents two forms of Human trees. We see that both schemes have same average length but dierent variances. Variance is a measure of the variability in codeword lengths of a source code. It is dened as follows:
K1

2 = &
k=0

pk (lk L)2

(6) %

'

where, pk is the probability of kth symbol. lk is the codeword length of kth symbol and L is the average codeword length. It is reasonable to choose the human tree which gives greater variace.

&

'
(a)

s0

s1 0

s2 1

s3 0 1

s4

Symbol s0 s1

code 10 00 01 110 111

Average length, L = .2.2 Variance = 0.160

s2 s3

0 1 s0 s1 s2 0 0 0 1 (b) 1 1 s3 0 (b) Average length, L = .2.2 Variance = 1.036 s4 1

s4

Symbol s

code 0 10 110 1110 1111

s1 s2 s3 s4

&

Figure 2: Human tree

'

Drawbacks: 1. Requires proper statistics. 2. Cannot exploit relationships between words, phrases etc., 3. Does not consider redundancy of the language.

&

'

Lempel-Ziv Coding
1. Overcomes the drawbacks of Human coding 2. It is an adaptive and simple encoding scheme. 3. When applied to English text it achieves 55% in contrast to Human coding which achieves only 43%.

4. Encodes patterns in the text This algorithm is accomplished by parsing the source data stream into segments that are the shortest subsequences not encountered previously. (see Figure 3 the example is reproduced from [Link] book on Communication Systems.) & %

'

Let the input sequence be 000101110010100101......... We assume that 0 and 1 are known and stored in codebook subsequences stored : 0, 1 Data to be parsed: 000101110010100101......... The shortest subsequence of the data stream encountered for the first time and not seen before is 00 subsequences stored: 0, 1, 00 Data to be parsed: 0101110010100101......... The second shortest subsequence not seen before is 01; accordingly, we go on to write Subsequences stored: 0, 1, 00, 01 Data to be parsed: 01110010100101......... We continue in the manner described here until the given data stream has been completely parsed. The code book is shown below:

Numerical positions: 1 subsequences: Numerical Repre sentations: Binary encoded blocks: 0

2 1

3 00 11

4 01 12

5 011 42

6 10 21

7 010 41

8 100 61

9 101 62

0010

0011

1001

0100

1000

1100

1101

&

Figure 3: Lempel-Ziv Encoding