On information theory parameters of infinite anti-uniform sources

Access Full Text

On information theory parameters of infinite anti-uniform sources

For access to this article, please select a purchase option:

Buy article PDF
£12.50
(plus tax if applicable)
Add to cart
Buy Knowledge Pack
10 articles for £75.00
(plus taxes if applicable)
Add to cart

IET members benefit from discounts to all IET publications and free access to E&T Magazine. If you are an IET member, log in to your account and the discounts will automatically be applied.

Learn more about IET membership 

Recommend Title Publication to library

You must fill out fields marked with: *

Librarian details
Name:*
Email:*
Your details
Name:*
Email:*
Department:*
Why are you recommending this title?
Select reason:
 
 
 
 
 
IET Communications — Recommend this title to your library

Thank you

Your recommendation has been sent to your librarian.

© The Institution of Engineering and Technology
Published

A source ={s1, s2, …} having a binary Huffman code with code-word lengths satisfying l1=1, l2=2, … is called an anti-uniform source. If l1=1, l2=2, … , li=i, then the source is called an i-level partially anti-uniform source. The redundancy, expected codeword length and entropy of anti-uniform sources are dealt here. A tight upper bound is derived for the expected codeword length L of anti-uniform sources. It is shown that L does not exceed $\surd{5}+3/2$. For each $1\lt L\le \lpar \surd{5}+3\rpar /2$, an anti-uniform distribution achieving maximum entropy H(P)max=L log L−(L−1)log(L−1) is introduced. This shows that the maximum entropy achieved by anti-uniform distributions does not exceed 2.512. It is shown that the range of redundancy values for i-level partially anti-uniform sources with distribution {pi} is an interval of length ∑j=i+1pj. This results in a realistic approximation for the redundancy of these sources.

Inspec keywords: Huffman codes; maximum entropy methods; binary codes; statistical distributions; source coding

Other keywords: information theory; codeword length; maximum entropy; infinite anti-uniform source; binary Huffman code; probability distribution

Subjects: Codes; Other topics in statistics

References

    1. 1)
      • M. Esmaeili . (2007) On the weakly superincreasing distributions and the fibonacci-hessenberg matrices, ARS Combinatoria.
    2. 2)
      • T.M. Cover , J.A. Thomas . (2006) Elements of information theory.
    3. 3)
      • R.G. Gallager , D.C. Van Voorhis . Optimal source codes for geometrically distributed integer alphabets. IEEE Trans. Inf. Theory , 21 , 228 - 230
    4. 4)
      • A. Kato , T.S. Han , H. Nagaoka . Huffman coding with an infinite alphabet. IEEE Trans. Inf. Theory , 42 , 977 - 984
    5. 5)
      • E. Norwood . The number of different possible compact codes. IEEE Trans. Inf. Theory , 613 - 616
    6. 6)
      • R.G. Gallager . Variations on a theme by Huffman. IEEE Trans. Inf. Theory , 24 , 668 - 674
    7. 7)
      • S.W. Golomb , R.E. Peile , R.A. Scholtz . (1994) Basic concepts in information theory and coding.
    8. 8)
      • P.A. Humblet . Optimal source coding for a class of integer alphabets. IEEE Trans. Inf. Theory , 24 , 110 - 112
    9. 9)
      • G.O.H. Katona , T.O.H. Nemetz . Huffman codes and self-information. IEEE Trans. Inf. Theory , 22 , 337 - 340
    10. 10)
      • T. Linder , V. Tarokh , K. Zeger . Existence of optimal prefix codes for infinite source alphabets. IEEE Trans. Inf. Theory , 43 , 2026 - 2028
    11. 11)
      • O. Johnsen . On the redundancy of binary Huffman codes. IEEE Trans. Inf. Theory , 26 , 220 - 222
    12. 12)
      • D.A. Huffman . A method for the construction of minimum-redundancy codes. Proc. Inst. Elect. Radio Eng. , 40 , 1098 - 1101
    13. 13)
      • M. Khosravifard , M. Esmaeili , H. Saidi , T.A. Gulliver . A tree based algorithm for generating all possible binary compact codes with N codewords. IEICE Trans. Fundam. Electron. Commun. Computer Sci. , 2510 - 2516
    14. 14)
      • R.M. Capocelli , A. De Santis . A note on D-ary Huffman codes. IEEE Trans. Inf. Theory , 37 , 174 - 179
http://iet.metastore.ingenta.com/content/journals/10.1049/iet-com_20070076
Loading

Related content

content/journals/10.1049/iet-com_20070076
pub_keyword,iet_inspecKeyword,pub_concept
6
6
Loading