Department of Computer Science
 
Chair V

 
University of Bonn -> Department of Computer Science -> Chair V
CS-Reports 2005 Copyright 2005 University of Bonn, Department of Computer Science, Abt. V
85263

20.01.2005

Algorithms for Construction of Optimal and Almost-Optimal Length-Restricted Codes
Marek Karpinski and Yakov Nekrich
[Download PostScript] [Download PDF]

In this paper we present new results on sequential and parallel construction of optimal and almost-optimal length-restricted prefix-free codes. We show that length-restricted prefix-free codes with error 1/nk for any k > 0 can be constructed in O(n log n) time or in O(log n) time with n CREW processors. A length-restricted code with error 1/nk for any kL logΦn, where Φ = (1 + \sqrt{5})/2, can be constructed in O(log n) time with n/log n CREW processors. We also describe an algorithm for the construction of optimal length-restricted codes with maximum codeword length L that works in O(L) time with n CREW processors.

Last Change: 01/20/05 at 16:33:24
 Deutsch
University of Bonn -> Department of Computer Science -> Chair V