- An Approximation Algorithm for Constructing Error Detecting Prefix Codes Artur Pessoa (arturproducao.uff.br) Abstract: A $k$-bit Hamming prefix code is a binary code with the following property: for any codeword $x$ and any prefix $y$ of another codeword, both $x$ and $y$ having the same length, the Hamming distance between $x$ and $y$ is at least $k$. Given an alphabet $A = [a_1,\ldots,a_n]$ with corresponding probabilities $[p_1,\ldots,p_n]$, the $k$-bit Hamming prefix code problem is to find a $k$-bit Hamming prefix code for $A$ with minimum average codeword length $\sum_{i=1}^n p_i \ell_i$, where $\ell_i$ is the length of the codeword assigned to $a_i$. In this paper, we propose an approximation algorithm for the 2-bit Hamming prefix code problem. Our algorithm spends $O(n \log^3 n)$ time to calculate a 2-bit Hamming prefix code with an additive error of at most $O(\log \log \log n)$ bits with respect to the entropy $H = -\sum_{i=1}^n p_i \log_2 p_i$. Keywords: approximation algorithms, error detection, prefix codes Category 1: Combinatorial Optimization (Approximation Algorithms ) Category 2: Applications -- OR and Management Sciences (Telecommunications ) Citation: Unpublished, Abstract in the Proceedings of the ISMP'06. Download: [PDF]Entry Submitted: 09/02/2006Entry Accepted: 09/04/2006Entry Last Modified: 09/02/2006Modify/Update this entry Visitors Authors More about us Links Subscribe, Unsubscribe Digest Archive Search, Browse the Repository Submit Update Policies Coordinator's Board Classification Scheme Credits Give us feedback Optimization Journals, Sites, Societies Optimization Online is supported by the Mathematical Programming Society and by the Optimization Technology Center.