Received 8 September 2015; accepted 8 November 2015; published 11 November 2015

ABSTRACT

The present communication offers a method to determine an unknown discrete probability distribution with specified Tsallis entropy close to uniform distribution. The relative error of the distribution obtained has been compared with the distribution obtained with the help of mathematica software. The applications of the proposed algorithm with respect to Tsallis source coding, Huffman coding and cross entropy optimization principles have been provided.

Keywords:

Entropy, Source Coding, Kraft’s Inequality, Huffman Code, Mean Codeword Length, Uniquely Decipherable Code

1. Introduction

After the publication of his first paper “A mathematical theory of communication”, Shannon [1] made a remarkable discovery of entropy theory which immediately caught the interest of engineers, mathematicians and other scientists from various disciplines. Naturally one had speculated before Shannon about the nature of information but at the qualitative level but it was Shannon who for the first time introduced the following quantitative measure of information in a statistical framework:

(1)

with the convention.

Shannon’s main focus was related with the type of communication problems related with engineering sciences but as the field of information theory progressed, it became clear that Shannon ’s entropy was not the only feasible information measure. Indeed, many modern communication processes, including signals, images and coding systems, often operate in complex environments dominated by conditions that do not match the basic tenets of Shannon ’s communication theory. For instance, coding can have a non-trivial cost functions, codes might have variable lengths, sources and channels may exhibit memory or losses, etc. Post-Shannon developments of non-parametric entropy, it was realized that generalized parametric measures of entropy can play a significant role to deal with the prevailing situations, since these measures introduce flexibility in the system and also helpful towards maximization problems.

An extension to the Shannon entropy proposed by Renyi [2] , is given by

(2)

The Renyi entropy offers a parametric family of measures, from which the Shannon entropy is accessible as a special case when.

Another information theorist Tsallis [3] introduced his measure of entropy, given by

(3)

When q → 1, the Tsallis entropy recovers the Shannon entropy for any probability distribution. The Tsallis [4] entropy has been postulated to form the ground of a nonextensive generalization to statistical mechanics. Tsallis pioneering work has stimulated the exploration of the properties of other generalized or alternative information measures [5] [6] . Oikonomou and Bagci [7] maximized the Tsallis entropy based on complete deformed functions to show that the escort distributions are redundant. Bercher [8] showed that Tsallis distributions can be derived from the standard (Shannon) maximum entropy setting, by incorporating a constraint on the divergence between the distribution and another distribution imagined as its tail.

Information theory provides a fundamental performance limits pertaining to certain tasks of information pro- cessing, such as data compression, error-correction coding, encryption, data hiding, prediction, and estimation of signals or parameters from noisy observations. Shannon [1] provided an operational meaning to his entropy through a source coding theorem by establishing the limits to possible data compression. Bercher [9] discussed the interest of escort distributions and Rényi entropy in the context of source coding whereas Parkash and Kakkar [10] developed new mean codeword lengths and proved source coding theorems. Huffman [11] introduced a procedure for designing a variable length source code which achieves performance close to Shannon’s entropy bound. Baer [12] provided new lower and upper bounds for the compression rate of binary prefix codes optimized over memoryless sources. Mohajer et al. [13] studied the redundancy of Huffman codes whereas Walder et al. [14] provided algorithms for fast decoding of variable length codes.

In Section 2, we have provided an algorithm to find a discrete distribution closer to uniform distribution with specified Tsallis [3] entropy. We have proved the acceptability of the algorithm by comparing the relative error of the probability distribution generated through algorithm with the probability distribution generated through Mathematica software through an example. Section 3 provides the brief introduction to source coding and the study of source coding with the Tsallis entropy. Also, we have extended the applications of the algorithm with respect to Tsallis source coding, Huffman coding and cross entropy optimization principles.

2. Generating Probability Distribution Closer to Uniform Distribution with Known Entropy

Tsallis introduced the generalized q-logarithm function is defined as

(4)

which for, becomes the common natural logarithm. Its inverse is the generalized q-exponential function, given by

(5)

which becomes the exponential function for.

The q-logarithm satisfies the following pseudo additive law

(6)

It is to be noted that the classical power and the additive laws for the logarithm and exponential do no longer hold for (4) and (6). Except for, in general

The Tsallis entropy (3) can be written as an expectation of the generalized q-logarithm as

Let us suppose that there are probabilities to be found. Separating the probability and renaming it, that is, , we have

Multiplying and dividing by (assuming, that is,) yields

Defining, the above expression can be written as

(7)

Since form a full set of probabilities, we have.Thus, the above expression (7) becomes

(8)

where is the expression for Tsallis entropy of the -ary vector r and is the binary entropy function

Rearranging the terms in Equation (8) gives

(9)

Thus,

(10)

where

The maximum value of Tsallis entropy subject to natural constraint, that is, is given by

which is obtained at uniform distribution.

So, we have

In a similar way, , being the entropy of variables with the probability vector r must satisfy

Hence, must satisfy the requirements

(11)

(12)

The objective of present paper is to find subject to conditions (11) and (12) so as to obtain next stage entropy, that is,. It is to be noted that the next iteration’s entropy, may be larger or

smaller than. The procedure may be iterated until only two variables remain, and. The remaining

entropy for these normalized variables, satisfies the usual binary entropy function

(13)

To finish the selection of the, take and as one of the two solutions of (13). The set of scaled values through is obtained at the end. Swaszek and Wali [15] made use of Shannon’s entropy and to find the probability distribution for the same, provided the following relation between’s and’s after recursing through the sequential definitions of r vectors.

(14)

We also use relation (14) to find probability distribution for Tsallis entropy which is close to uniform distribution.

2.1. Method A

1) For given, find the solutions of the following equation

2) Pick the solution that lies in.

3) Generate the random number in the interval for which.

4) Repeat the above three steps for.

5) For, solve Equation (13) for getting and.

6) Take and.

7) Use equation (14) to get probability distribution closer to uniform distriburtion.

Note: Before specifying the value of parameter q and entropy, make sure to choose that value of q for which value given entropy is less than or equal to its maximum value which is obtained at uniform distribution, that is,

.

2.2. Numerical

Let. Applying above method gives and. Proceeding on similar lines, we obtain remaining probabilities as depicted in the following Table 1.

Note that the values and do not lie in the neighbourhood of because they are exact solutions of

equation of (13) and hence is the case for the values and. With this exception, the other values, that is, are very close to the uniform distribution and the associated entropy is 4.5 bits.

2.3. Use of Mathematica Software

The above mentioned problem is also solved using the Mathematica software by using the same input. NMinimize command is used for this purpose which has several inbuilt optimization methods available. Since the problem is to find the discrete distribution having a specific Tsallis entropy closer to the

discrete uniform distribution, therefore the optimization problem becomes:

Minimize subject to constraints

The solution obtained is for.

2.4. Relative Errors

The relative error is calculated using the formula. It is found that relative error in case of probabi-

lity distribution found by mathematica software is whereas it is in case of method A. This implies that method A provides an acceptable discrete distribution and hence the method itself is acceptable.

3. Source Coding

In source coding, one considers a set of symbols and a source that produces symbols

from X with probabilities where. The aim of source coding is to encode the source using an al-

phabet of size D, that is to map each symbol to a codeword of length expressed using the D letters of the alphabet. It is known that if the set of lengths satisfies the Kraft’s [16] inequality

, (15)

then there exists a uniquely decodable code with these lengths, which means that any sequence can be decoded unambiguously into a sequence of symbols Furthermore, any uniquely decodable code satisfies the Kraft’s inequality (15).

The Shannon [1] source coding theorem indicates that the mean codeword length

(16)

is bounded below by the entropy of the source, that is, Shannon’s entropy, and that the best uniquely decodable code satisfies

where the logarithm in the definition of the Shannon entropy is taken in base D. This result indicates that the Shannon entropy is the fundamental limit on the minimum average length for any code constructed for the source. The lengths of the individual codewords, are given by

. (17)

The characteristic of these optimum codes is that they assign the shorter codewords to the most likely symbols and the longer codewords to unlikely symbols.

Source Coding with Campbell Measure of Length

Implicit in the use of average codeword length (16) as a criteria of performance is the assumption that cost varies linearly with code length. But this is not always the case. Campbell [17] introduced the mean codeword length which implies that cost is an exponential function of code length. The cost of encoding the source is expressed by the exponential average

(18)

where is some parameter related to cost.

Minimizing the cost is equivalent to minimizing the monotonic increasing function of defined as

So, is the exponentiated mean codeword length given by Campbell [12] which approaches to L as.

Campbell proved that Renyi [2] entropy forms a lower bound to the exponentiated codeword length as

(19)

where or equivalently

(20)

subject to Kraft’s inequality (15) with optimal lengths given by

(21)

By choosing a smaller value of, the individual lengths can be made smaller than the Shannon lengths, specially for small.

Similar approach is applied to provide an operational significane to Tsallis [3] entropy through a source coding problem.

From Renyi’s entropy of order where logarithm is taken to the base D, we have

(22)

Substituting (22) in (3) where parameter q is replaced by gives

or equivalently

(23)

Equation (23) establishes a relation between Renyi’s entropy and Tsallis entropy.

From (20), we have

where

Case-I Now, when

(24)

Case-II when

(25)

From (24) and (25), it is observed that Tsallis entropy forms a lower bound to which is nothing but the new generalized length and is a monotonic increasing function of. It reduces to mean codeword length L

when. The optimal codeword lengths are given by which is similar as in case of Campbell’s mean codeword length. is not an average of the type as introduced by Kolmogorov [18] and Nagumo [19] but is a simple expression of the q-deformed logarithm.

4. Application of Method A

1) Huffman [11] introduced a method for designing variable length source code in which he showed that the average length of a Huffman code is always within one unit of source entropy, that is, where L is defined by (16) and is defined by (1). By using method A as mentioned in Section 2, different sets of probability distributions can be generated which are closer to uniform distribution and which has same Tsallis entropy. The probability distributions thus generated can be used to develop Huffman code and to see that whether the lengths of Huffman codewords satisfies relation (24) or (25) where the Tsallis entropy forms a lower bound to generalized length. Thus, performance of Huffman algorithm can be judged in case of source coding with Tsallis entropy.

In the following example, Huffman code is constructed using the probability distribution obtained in Table 1. Let be an array of symbols with probabilities in decreasing order as shown below where Huffman method is employed to construct an optimal code.

Optimal code is obtained as follows

Hence the optimal code is and the lengths of the codewords are.

So, using the probability distribution generated in Table 1 along with known value of and above mentioned codeword lengths, value of is obtained as 6.2327 which is greater that Tsallis entropy (=4.5 bits), thus satisfies relation (24).

2) The problem of determining an unknown discrete distribution closer to uniform distribution with known Tsallis entropy as discussed in Section 2 can be looked upon as minimum cross entropy principle which states that given any priori distribution, we should choose that distribution which satisfies the given constraints and which is closest to priori distribution. So, cross entropy optimization principles offer a relevant context for the application of method A.

Acknowledgements

The authors are thankful to University Grants Commission and Council of Scientific and Industrial Research, New Delhi, for providing the financial assistance for the preparation of the manuscript.

Cite this paper

OmParkash,PriyankaKakkar, (2015) An Algorithm to Generate Probabilities with Specified Entropy. Applied Mathematics,06,1968-1976. doi: 10.4236/am.2015.612174

References