20.01.2005

In this paper we present new results on sequential and parallel construction of optimal and almost-optimal length-restricted prefix-free codes. We show that length-restricted prefix-free codes with error 1/n^k for any k > 0 can be constructed in O(n log n) time or in O(log n) time with n CREW processors. A length-restricted code with error 1/n^k for any k ≤ L log_Φn, where Φ = (1 + \sqrt{5})/2, can be constructed in O(log n) time with n/log n CREW processors. We also describe an algorithm for the construction of optimal length-restricted codes with maximum codeword length L that works in O(L) time with n CREW processors.