Generalized information measure and some source coding theorems

Introduction

where the convention 0log (0) = 0 is adapted, (see Shannon) [23] .

Throughout this paper,  will stand for  x x x X be encoded using alphabet of D symbols, then it is shown in Feinstein [5] that there is a uniquely decipherable code with lengths 1,

where D is the size of code alphabet. Kraft's [13] inequality which is uniquely determined by the condition for unique decipherability and plays an important role in proving a noiseless coding theorem without dependent on the probabilities or utilities. This inequality cannot be modified just to prove noiseless coding theorems as it will not give uniquely decipherable codes but will provide codes with a different structure. To prove some noiseless coding theorems we have made use of Kraft's inequality in original. Furthermore, if

is the average codeword length, then for a code satisfying (1.2), the inequality

is also fulfilled and equality,

), ( = P H L holds if and only if

then by suitable encoding of long input sequences, the average number of code letters per input symbol can be made arbitrarily close to   P H (see Feinstein) [5] . This is Shannon's noiseless coding theorem. A coding theorem analogous to Shannon's noiseless coding theorem has been established by Campbell [2] , in terms of Renyi's entropy [21] :

Kieffer [11] defined class rules and showed

is the best decision rule for deciding which of the two sources can be coded with least expected cost of sequences of length n when   n

, where the cost of encoding a sequence is assumed to be a function of length only. Further, in Jelinek [9] it is shown that coding with respect to Campbell's mean length is useful in minimizing the problem of buffer overflow which occurs when the source symbol is produced at a fixed rate and the code words are stored temporarily in a finite buffer. Concerning Campbell's mean length the reader can consult Campbell [2] . Longo [16] developed lower bound for useful mean codeword length in terms of weighted entropy introduced by Belis and Guiasu [2] . Guiasu and Picard [6] proved a noiseless coding theorem by obtaining lower bounds for another useful mean codeword length. Gurdial and Pessoa [7] extended the theorem by finding lower bounds for useful mean codeword length of order . Chapeau-Blondeau et al. [3] have presented an extension to source coding theorem traditionally based upon Shannon's entropy and later generalized to Renyi's entropy. Chapeau-Blondeau et al. [4] have described a practical problem of source coding and investigated an important relation stressing that Renyi's entropy emerges at an order a differing from the traditional Shannon's entropy. Some new lower and upper bounds for compression rate of binary prefix codes optimized over memoryless sources have been provided by Baer [1] . Singh et al. [26] have provided the application of weighted measures of entropy to the field of coding theory. Ramamoorthy [20] considered the problem of transmitting multiple compressible sources over a network at minimum cost with the objective to find the optimal rates at which the sources should be compressed. Tu et al. [28] have presented a new scheme based on variable length coding, capable of providing reliable resolutions for flow media data transmission in spatial communication. Some interesting work for the construction of information theoretic source network coding in the presence of eavesdroppers has been presented by Luo et al. [17] . Wu et al. [29] have constructed a space trellis and design a low-complexity joint decoding algorithm with a variable length symbol-a posteriori probability algorithm in resource constrained deep space communication networks. The applications of coding theory to the field of marketing have been provided by Neill [19] . Some other related work concerned with the coding theory have been provided by Sharma and Raina [24] and Koski and Persson [12] , etc. The mean length of a noiseless uniquely decodable code for a discrete random variable satisfies

is the Shannon's entropy [23] of the random variable . Shannon's restriction of coding of to prefix codes is highly justified by the implicit assumption that the description will be concatenated and thus must be uniquely decordable and instantaneous codes, cf. [1,2] , the expected codeword length is the same for both the set of codes. There are some communication situations in which a random variable is being transmitted rather than a sequence of random variables. For this context Leung-Yang-Cheong and Cover [15] considered one to one codes i.e., codes which assign a distinct binary code to each outcome of the random variable without regard to the condition that concatenations of the descriptions must be uniquely decipherable. The authors showed by Lagrange multiplier arguments that the minimum length of the best 1:1 binary code satisfy the inequality

denotes the smallest integer greater than or equal to , is the first order approximation to minimal expected length of 1:1 codes and logarithms are taken to the base 2. It has also been proved in [15]

(1.10) where in (1.9) is the number of values that the random variable can take on, while in (1.10), is allowed to have countably many values. Rissanen [22] improved the lower bound (1.8) (1.13) The inequality (1.11) is strictly better than (1.8) because it was shown by Rissanen [22] that , 2

For every . In Section 2, we have introduced the new generalized information measure and consequently proved two new coding theorems. Some fascinating relations between entropy and the best 1:1 codeword lengths have been developed, the findings of which are presented in Section 3.

Coding Theorems

, then the information measure H is given by the formula

It is also studied by Kumar and Choudhary [14] . Where are positive integers so that . 1

L reduces to Nath [18] average code word length,

, then it reduces to Cambell's Codeword Length,

Proof

By Shisha [25] Holder's inequality, we have ,

where we used (2.3), too. This implies however that In the following theorem, we give an upper bound for

It is easy to see that the sequence

1,2,..., = , } { thus defined, satisfies (2.5). Now, from the right inequality of (2.12), we have

, to both sides of (2.13), we have



, follows on similar case (i). Remark 1. Huffman [8] introduced a procedure for designing a variable length source code which achieves performance close to Shannon's entropy bound. For individual codeword lengths , the average length

p n of Huffman code is always within one unit of Shannon's measure of entropy, that is,

is the Shannon's measure of entropy. Huffman coding scheme can also be applied to codeword length   L i.e., for individual codeword lengths n , the average length

as numerically shown in following Table 1.

N denotes the length of the code word assigned to tuple s and , denotes the average code length, then

s entropy is finitely additive, by using (2.7) and (2.12) we get

Thus, we have proved the following theorem. L of order and type is less than Renyi's entropy order .

We remark that the last part of the above theorem needs no explanation as it is obvious from Theorem 2.1 and Theorem 2.2. In the next section, we have developed the relation between entropy and best 1:1 codeword length.

Codeword Length for the best 1:1 code and its Lower bound

In the above section, we have proved in Theorem 2.1 and Theorem 2.2 that new codeword length

for all uniquely decipherable codes. We consider this codeword length for the best 1:1 code and find its lower bound. Let X be a random variable taking on a finite number of values ) ,..., , ( [15] , where ]

[x denotes the smallest integer greater than or equal to .

We will now prove the following theorem, which gives a lower bound on .

Applying Holder's inequality to (3.5), we obtain

Which proves (3.3). Theorem 3.2. For as given in (1.12), we have the following inequality

 

References

1. Baer MB. Redundancy-related bounds for generalized Huffman codes. IEEE Trans. Inf. Theory. 2011; 57:2278-2290.
2. Campbell LL. A coding theorem and Renyi's entropy. Information and Control. 1965; 8:423-429.
3. Chapeau-Blondeau F, Delahaies A, Rousseau D. Source coding with Tsallis entropy. Electron. Lett., 2011; 47:187-188.
4. Chapeau-Blondeau F, Rousseau D, Delahaies A. Renyi entropy measure of noise aided information transmission in a binary channel. Phys. Rev. E, 2010; 81:051112(1)-051112(10).
5. Feinstein A. Foundation of Information Theory. McGraw Hill, New York, 1956.
6. Guiasu S, Picard CF. Borne infericutre de la Longuerur utile de certain codes. C.R. Acad. Sci. Paris. 1971; 273(A):248-251.
7. Gurdial, Pessoa F. On useful information of order . J. Combut. Inf. Syst. Sci., 1977; 2:158-162.
8. Huffman DA. A method for the construction of minimum redundancy codes. In: Proceedings of the IRE. 1952; 40:10981101.
9. Jelinek F. Buffer overflow in variable lengths coding of fixed rate sources. IEEE, 1980; 3:490-501.
10. Kapur JN. Entropy and Coding. MSTS, New Delhi, 1998.
11. Kieffer JC. Variable lengths source coding with a cost depending only on the codeword length. Information and Control. 1979; 41:136-146.
12. Koski T, Persson LE. Some properties of generalized exponential entropies with applications to data compression. Inform. Sci., 1992; 62:103-132.
13. Kraft LG. A Device for Quantizing Grouping and Coding Amplitude Modulated Pulses. M.S. Thesis, Electrical Engineering Department, MIT, 1949.
14.  P Asian Journal of Applied Sciences. 2011; 4(6):649-656.
15. Leung-Yan-Cheong SK, Cover T. Some equivalence between Shannon entropy and Kolmogrov complexity. IEEE Trans. On Inform. Theory. 1978; 24:331-338.
16. Longo G. A noiseless coding theorem for sources having utilities. SIAM J. Appl. Math. 1976; 30:739-748.
17. Luo MX, Yang YX, Wang LC, Niu XX. Secure network coding in the presence of eavesdroppers. Sci. China Inform. Sci. 2011; 53:648-658.
18. Nath P. An axiomatic characterization of inaccuracy for discrete generalized probability distribution. Opsearch. 1970; 7:115133.
19. Neill WDO. An application of Shannon's coding theorem to information transmission in economic markets. Inform. Sci. 1987; 41:171-185.
20. Ramamoorthy A. Minimum cost distributed source coding over a network. IEEE Trans. Inf. Theory. 2011; 57:461-475.
21. Renyi A. On Measure of entropy and information. Proc. 4th Berkeley Symp. Maths. Stat. Prob., 1961; 1:547-561.
22. Rissanen J. Tight lower bounds for optimum code length. IEEE Trans. Inf. Theory, 1982; 28:348-349.
23. Shannon CE. A Mathematical Theory of Communication. Bell System Tech. J. 1948; 27:379-423, 623-656.
24. Sharma BD, Raina N. Coding theorem for partial received information. Inform. Sci. 1980; 20:181-189.
25. Shisha O. Inequalities. Academic Press, New York, 1967.
26. Singh RP, Kumar R, Tuteja RK. Applications of holder's inequality in information theory. Inform. Sci. 2003; 152:145-154.
27. Taneja IJ. A short note on exponentiated mean codeword length for the best 1:1 code, Computational and Applied Mathematics. 1984; 3:199-204.
28. Tu GF, Liu JJ, Zhang C, Gao SS, Li SD. Studies and advances on joint source-channel encoding/decoding techniques in flow media communication. Sci. China Inform. Sci., 2011; 54:1883-1894.
29. Wu WR, Tu J, Tu GF, Gao SS, Zhang C. Joint source channel VL coding/decoding for deep space communication networks based on a space trellis. Sci. China Inform. Sci., 2010; 53:1-17.
30. Garg D, Kumar S. Parametric R-norm directed-divergence convex function, Infinite Dimensional Analysis, Quantum Probability and Related Topics, World Science Journals. 2010; 19(2), 2016, DOI: 10.1142/S0219025716500144
31. Garg D, Kumar S. An application of generalized Tsalli's-Havrda-Charvat entropy in coding theory through a generalization of Kraft inequality, International Journal of Applied Research. 2016; 1(4):01-05, ISSN: 2394-5869.
32. Garg D, Kumar S. Some Remarks On 'Useful' Renyi's Entropy of Order α in International Journal of trends in Mathematics and Statistics (IJTIMS). 2015; 4(10):178-183, ISSN: 2279-0318.