Title :
Algorithms for construction of optimal and almost-optimal length-restricted codes
Author :
Karpinski, Marek ; Nekrich, Yakov
Author_Institution :
Dept. of Comput. Sci., Bonn Univ., Germany
Abstract :
Summary form only given. We present a parallel algorithm for the construction of minimum redundancy length-restricted codes that is based on the package-merge algorithm of Larmore and Hirschberg (1990). Our algorithm constructs a length-restricted code in O(L) time with n processors on a CREW PRAM. Thus our algorithm has the same time-processor product as the sequential algorithm of (1990). We also consider the problem of constructing the almost-optimal length-restricted codes.
Keywords :
optimisation; parallel algorithms; redundancy; runlength codes; CREW PRAM; almost-optimal codes; length-restricted codes; minimum redundancy codes; package-merge algorithm; parallel algorithm; sequential algorithm; time-processor product; Computer science; Data compression; Packaging; Parallel algorithms; Phase change random access memory; Redundancy;
Conference_Titel :
Data Compression Conference, 2005. Proceedings. DCC 2005
Print_ISBN :
0-7695-2309-9
DOI :
10.1109/DCC.2005.12
