Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR02-029 | 3rd June 2002 00:00

Parallel Construction of Minimum Redundancy Length-Limited Codes

RSS-Feed

Abstract:

This paper presents new results on parallel constructions 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 for $L$ the
maximal codeword length.
We also describe an algorithm for a construction of {\it 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.



ISSN 1433-8092 | Imprint