Narrow Results

We present an algorithm for parallel construction of Huffman codes in time with p processors, where p>1, improving the previous result of Levcopoulos and Przytycka. We also show, that a greedy Huffman tree can be constructed in time with n processors.

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 , 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.

The authors present a simple technique to combine source coding, channel coding and modulation. This technique employs the Huffman code for source coding, Generalized Array Codes (GAC) for channel coding and Phase/Frequency (BFSK/MPSK) for modulation. The combined scheme has the advantage of reducing the redundancy, providing error protection and simultaneously optimizing on channel bandwidth. It is shown the combined system gives the same performance as its separate counterparts but has lower complexity. The algorithm used to construct the combined trellis decoder employing phase/frequency for a given source text file is designed and implemented in software. The error performances for the combined schemes using BFSK/MPSK modulation are compared with those employing coded as well as Uncoded MPSK modulation. Such a Block Coded Modulation (BCM) scheme is suitable for both information storage and digital transmission systems.