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/2006
Entry Accepted: 09/04/2006
Entry Last Modified: 09/02/2006

Modify/Update this entry