Parallel Construction of the Minimum Redundancy Length-Limited Codes

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 lengthlimited 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