Computer Science – Information Theory
Scientific paper
2007-01-03
Computer Science
Information Theory
5 pages, 2 figures (with 3 illustrations total), accepted to ISIT 2007
Scientific paper
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, $\beta$-exponential means, those of the form $\log_a \sum_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 problem of maximizing the chance of message receipt in single-shot communications ($a<1$) and a 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. Both are extended to minimizing maximum pointwise redundancy.
No associations
LandOfFree
Infinite-Alphabet Prefix Codes Optimal for $β$-Exponential Penalties does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Infinite-Alphabet Prefix Codes Optimal for $β$-Exponential Penalties, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Infinite-Alphabet Prefix Codes Optimal for $β$-Exponential Penalties will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-563640