A note on the construction of error detecting/correcting prefix codes

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=[a1,…,an] with corresponding probabilities [p1,…,pn], the k-bit Hamming prefix code problem is to find a k-bit Hamming prefix code for A with minimum average codeword length , where ℓi is the length of the codeword assigned to ai. In this paper, we propose a general approximation algorithm for the k-bit Hamming prefix code problem. Let αk be an O(rk(n))-time algorithm for calculating fixed-length codes with Hamming distances k whose codewords are dk(n) bits longer than ⌈log2n⌉. Our algorithm uses αk to calculate a k-bit Hamming prefix code in O(rk(n)+nlogn) time with an additive error of at most O(dk(n)+log∗n) bits with respect to the optimal prefix code for A, under reasonable assumptions on the function dk.