Preprint on CoRR archive: arXiv cs/0605099; last updated 28 March 2009.
ISSN/ISBN: Not available at this time. DOI: Not available at this time.
Abstract: A novel lossless source coding paradigm applies to problems in which a vital message needs to be transmitted prior to termination of communications, as in Alfred Rényi's secondhand account of an ancient siege in which information was obtained to prevent the fall of a fortress. Rényi told this story with reference to traditional prefix coding, in which the objective is minimization of expected codeword length. The goal of maximizing probability of survival in the siege scenario is distinct from yet related to this traditional objective. Rather than finding a code minimizing ∑i=1n p(i) l(i), this variant involves maximizing ∑i=1n p(i) θl(i) for a given θ ∈ (0,1). A known generalization of Huffman coding solves this, and, for nontrivial θ ( θ ∈ (0.5,1)), the optimal solution has coding bounds which are functions of Rényi's α-entropy for α = 1/log2 2θ > 1. A new improvement on known bounds is derived here. When alphabetically constrained, as in search trees and in diagnostic testing of sequential systems, a dynamic programming algorithm finds the optimal solution in O(n3) time and O(n2) space, whereas two novel approximation algorithms can find a suboptimal solution in linear time (for one) or O(n log n) time (for the other). These approximation algorithms, along with simple associated coding bounds, apply to both the siege scenario and a complementary problem.
Bibtex:
@article{,
author = {Michael B. Baer},
title = {Prefix Coding under Siege},
journal = {CoRR},
volume = {abs/cs/0605099},
year = {2006},
url = {http://arxiv.org/abs/cs/0605099},
archivePrefix = {arXiv},
eprint = {cs/0605099},
note = {last updated March 28, 2009},
}
Reference Type: Preprint
Subject Area(s): Computer Science