2006/02/17 by Michael B. Baer, Baer, Michael B.
Biochemistry, Genetics and Molecular Biology · Computer Science · Mathematics · #Algorithms and Data Compression #DNA and Biological Computing #Data Structures and Algorithms (cs.DS) #E.4 #Error Correcting Code Techniques #FOS: Computer and information sciences #H.1.1 #Information Theory (cs.IT) #cs.DS #cs.IT #math.IT
paper · pdf · doi:10.48550/arxiv.cs/0602067
5 pages, 1 figure, accepted to ISIT 2006
openalex publication_date 2006/02/17 · arxiv created 2006/05/22 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A novel lossless source coding paradigm applies to problems of unreliable lossless channels with low bit rates, in which a vital message needs to be transmitted prior to termination of communications. This paradigm can be applied to Alfred Renyi's secondhand account of an ancient siege in which a spy was sent to scout the enemy but was captured. After escaping, the spy returned to his base in no condition to speak and unable to write. His commander asked him questions that he could answer by nodding or shaking his head, and the fortress was defended with this information. Renyi told this story with reference to prefix coding, but maximizing probability of survival in the siege scenario is distinct from yet related to the traditional source coding objective of minimizing expected codeword length. Rather than finding a code minimizing expected codeword length ∑i=1n p(i) l(i), the siege problem involves maximizing ∑i=1n p(i) θl(i) for a known θ∈ (0,1). When there are no restrictions on codewords, this problem can be solve using a known generalization of Huffman coding. The optimal solution has coding bounds which are functions of Renyi entropy; in addition to known bounds, new bounds are derived here. The alphabetically constrained version of this problem has applications in search trees and diagnostic testing. A novel dynamic programming algorithm -- based upon the oldest known algorithm for the traditional alphabetic problem -- optimizes this problem in O(n3) time and O(n2) space, whereas two novel approximation algorithms can find a suboptimal solution faster: one in linear time, the other in O(n log n). Coding bounds for the alphabetic version of this problem are also presented.