- | ||||
|
![]()
|
An Approximation Algorithm for Constructing Error Detecting Prefix Codes
Artur Pessoa (artur 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/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 | |
![]() |