Optimal Prefix Codes for Infinite Alphabets With Nonlinear Costs

DOI10.1109/TIT.2007.915696zbMATH Open1311.94060arXivcs/0511003MaRDI QIDQ3604634FDOQ3604634

Authors: Michael B. Baer 

Publication date: 24 February 2009

Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)

Abstract: Let $P=p(i)$ be a measure of strictly positive probabilities on the set of nonnegative integers. Although the countable number of inputs prevents usage of the Huffman algorithm, there are nontrivial $P$ for which known methods find a source code that is optimal in the sense of minimizing expected codeword length. For some applications, however, a source code should instead minimize one of a family of nonlinear objective functions, $$-exponential means, those of the form $lo{g}_{a}su{m}_{i}p(i)a^{n(i)}$, where $n(i)$ is the length of the $i$th codeword and $a$ is a positive constant. Applications of such minimizations include a novel problem of maximizing the chance of message receipt in single-shot communications ($a<1$) and a previously known problem of minimizing the chance of buffer overflow in a queueing system ($a>1$). This paper introduces methods for finding codes optimal for such exponential means. One method applies to geometric distributions, while another applies to distributions with lighter tails. The latter algorithm is applied to Poisson distributions and both are extended to alphabetic codes, as well as to minimizing maximum pointwise redundancy. The aforementioned application of minimizing the chance of buffer overflow is also considered.

Full work available at URL: https://arxiv.org/abs/cs/0511003

Recommendations

• Existence of optimal prefix codes for infinite source alphabets
• Algorithms for infinite Huffman-codes
• Huffman coding with an infinite alphabet
• scientific article; zbMATH DE number 4063000
• Optimum '1'-ended binary prefix codes

Mathematics Subject Classification ID

Communication theory (94A05) Prefix, length-variable, comma-free codes (94A45)

Cited In (14)

• Bounding the inefficiency of length-restricted prefix codes
• Near-Optimal Depth-Constrained Codes
• Worst-Case Optimal Adaptive Prefix Coding
• Title not available (Why is that?)
• Alphabetic coding with exponential costs
• Tsallis entropy measure of noise-aided information transmission in a binary channel
• Optimal source coding for a class of integer alphabets (Corresp.)
• Existence of optimal prefix codes for infinite source alphabets
• Source coding with escort distributions and Rényi entropy bounds
• Optimal Prefix Codes for Pairs of Geometrically Distributed Random Variables
• On the redundancy of optimal binary prefix-condition codes for finite and infinite sources (Corresp.)
• Optimum '1'-ended binary prefix codes
• Algorithms for infinite Huffman-codes
• On One-to-One Codes for Memoryless Cost Channels

This page was built for publication: Optimal Prefix Codes for Infinite Alphabets With Nonlinear Costs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3604634)