what is average codeword length definition formula ? average codeword length definition ?

**THE SOURCE CODING **

**(i) Definition**

** **A conversion of the output of a discrete memoryless source (DMS) into symbols (i.e., binary code word) is called source coding. The device that performs this conversion is called the source encoder. Figure 3.15 shows a source encoder.

**diagram**

**figure 9.15 ***Block diagram for source Coding.*

**(ii) Objective of Source Coding **

An objective of source coding is to minimize the average bit rate required for representation of the source by reducing the redundancy of the information source.

**9.19.1. Few Terms related to Source Coding Process**

** **In this sub section, let us study the following terms which are related to source coding process :

(i) Codeword length

(ii) Average codeword length

(iii) Code efficiency

(iv) Code Redundancy

**(i) Codeword Length**

** **Let X be a DMS with finite entropy H(X) and an alphabet {x_{1}, …. x* _{m}*} with corresponding probabilities of occurrence P(x

_{i})(i = 1,…,

*m*). Let the binary codeword assigned to symbol x

*by the encoder have length n*

_{i}*, measured in bits. The length of a codeword is the number of binary digits in the codeword.*

_{i}**(ii) Average Codeword Length**

**The average codeword length**

*L*, per source symbol is given by

**equation**

The parameter

*L*represents the average number of bits per source symbol used in the source coding Process.

**(iii) Code Efficiency**

**The code efficiency Ƞ is defined as under :**

Ƞ = …(9.52)

where L

_{min}is the minimum possible value of

*L*. When 1 approaches unity, the code is said to be efficient.

**(iv) Code Redundancy**

**The code redundancy is defined as**

=1 – Ƞ …(9.53)

**9.19.2. The Source Coding Theorem**

**The source coding theorem states that for a DMS X, with entropy H(X), the average codeword length**

*L*per symbol is bounded as

L ≥ H(X) …(9.54)

DO YOU KNOW? |

By increasing the redundancy of the encoding, we can make the probability of error approach zero. |

and further, *L* can be made as close to H(X) as desired for some suitably chosen code.

Thus, with L_{min} = H(X), the code efficiency can be rewritten as

…(9.55)

**9.19.3. Classification of Codes**

** **Classification of codes is best illustrated by an example. Let us consider Table 9.2 where a source of size 4 has encoded in binary codes with symbol 0 and 1.

**Table 9.2. Binary Codes**

x_{i} |
Code 1 |
Code 2 |
Code 3 |
Code 4 |
Code 5 |
Code 6 |

1_{i}x _{2}x _{3}x _{4} |
00 01 00 11 |
00 01 10 11 |
0 1 00 11 |
0 10 110 111 |
0 01 011 0111 |
1 01 001 0001 |

**9.19.3.1. Fixed-Length Codes**

** **A fixed-length code is one whose codeword length is fixed. Code 1 and code 2 of Table 9.2 are fixed-length with length 2.

**9.19.3.2. Variable-Length Codes**

A variable-length code is one whose codeword length is not fixed. All codes of Table 9.2 except codes 1 and 2 are variable-length codes.

**9.19.3.3. Distinct codes**

** **A code is distinct if each codeword is distinguishable from other codewords. All codes of Table (9.2) except code 1 are distinct codes — notice the codes for x_{1} and x_{3}.

**9.19.3.4. Prefix-Free Codes**

** **A code in which no codeword can be formed by adding code symbols to another codeword is called a prefix-free code. Thus, in a prefix-free code, no codeword is a prefix of another. Codes 2, 4, and 6 of Table 9.2 are prefix-free codes.

**9.19.3.5. Uniquely Decodable Codes**

** **A distinct code uniquely decodable if the original source sequence can be reconstructed perfectly from the encoded binary sequence. Note that code 3 of Table 9.2 is not a uniquely decodable code. For, example, the binary sequence 1001 may correspond to the source sequences x_{2}x_{3}x_{2} x_{2}x_{1}x_{1}x_{2}, A sufficient condition to ensure that a code is uniquely decodable is that no code woid is a prefix of another. Thus, the prefix-free codes 2, 4, and 6 are uniquely decodable codes. Note that the prefix free condition is not a necessary condition for unique decodability. For example, code 5 of Table 9.