  


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 2bit Hamming prefix code problem. Our algorithm spends $O(n \log^3 n)$ time to calculate a 2bit 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/2006 Modify/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  