Optimization Online


An Approximation Algorithm for Constructing Error Detecting Prefix Codes

Artur Pessoa (artur***at***producao.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/2006
Entry Accepted: 09/04/2006
Entry Last Modified: 09/02/2006

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society