Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR02-029 | 3rd June 2002 00:00

#### Parallel Construction of Minimum Redundancy Length-Limited Codes

TR02-029
Authors: Marek Karpinski, Yakov Nekrich
Publication: 5th June 2002 09:02
Keywords:

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