Department of Computer Science
 
Chair V

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

Apr 8, 2002

Parallel Construction of the Minimum Redundancy Length-Limited Codes
Marek Karpinski and Yakov Nekrich
[Download PostScript] [Download PDF]

This paper presents new results on the construction of the length-limited prefix-free codes with the minimum redundancy. We describe an algorithm for the construction of length-limited codes that works in O(L) time with n processors, where L is the maximal codeword length. We also describe an algorithm for the construction of almost optimal length-limited codes that works in O(log n) time with n processors. This is an optimal parallelization of the best known up to date sequential algorithm.

Last Change: 04/08/02 at 08:11:14
 Deutsch 		University of Bonn -> Department of Computer Science -> Chair V