Institut für Informatik
 
Abteilung V

 
Universität Bonn -> Institut für Informatik -> Abteilung V
CS-Reports 2002 Copyright 2002 Universität Bonn, Institut für Informatik, 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
 English
Universität Bonn -> Institut für Informatik -> Abteilung V