average codeword length definition | what is average codeword length definition formula

By   August 4, 2020

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 {x1, …. xm} with corresponding probabilities of occurrence P(xi)(i = 1,…,m). Let the binary codeword assigned to symbol xi by the encoder have length ni, measured in bits. The length of a codeword is the number of binary digits in the codeword.
(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 Lmin 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 Lmin = 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

xi Code 1 Code 2 Code 3 Code 4 Code 5 Code 6
1i
x2
x3
x4
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 x1 and x3.
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 x2x3x2 x2x1x1x2, 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.

Leave a Reply

Your email address will not be published. Required fields are marked *