In previous work, we presented rules for defining overloaded functions that ensure type safety under symmetric multiple dispatch in an object-oriented language with multiple inheritance, and we showed how to check these rules without requiring the entire type hierarchy to be known, thus supporting modularity and extensibility. In this work, we extend these rules to a language that supports parametric polymorphism on both classes and functions.

The non-blocking work-stealing algorithm of Arora, Blumofe, and Plaxton (henceforth ABP work-stealing) is on its way to becoming the multiprocessor load balancing technology of choice in both industry and academia. This highly efficient scheme is based on a collection of array-based double-ended queues (deques) with low cost synchronization among local and stealing processes. Unfortunately, the algorithm's synchronization protocol is strongly based on the use of fixed size arrays, which are prone to overflows, especially in the multiprogrammed environments for which they are designed. We present a work-stealing deque that does not have the overflow problem.The only ABP-style work-stealing algorithm that eliminates the overflow problem is the list-based one presented by Hendler, Lev and Shavit. Their algorithm indeed deals with the overflow problem, but it is complicated, and introduces a trade-off between the space and time complexity, due to the extra work required to maintain the list.Our new algorithm presents a simple lock-free work-stealing deque, which stores the elements in a cyclic array that can grow when it overflows. The algorithm has no limit other than integer overflow (and the system's memory size) on the number of elements that may be on the deque, and the total memory required is linear in the number of elements in the deque.

Programs that manipulate physical quantities typically represent these quantities as raw numbers corresponding to the quantities' measurements in particular units (e.g., a length represented as a number of meters). This approach eliminates the possibility of catching errors resulting from adding or comparing quantities expressed in different units (as in the Mars Climate Orbiter error [11]), and does not support the safe comparison and addition of quantities of the same dimension. We show how to formulate dimensions and units as classes in a nominally typed object-oriented language through the use of statically typed metaclasses. Our formulation allows both parametric and inheritance poly-morphism with respect to both dimension and unit types. It also allows for integration of encapsulated measurement systems, dynamic conversion factors, declarations of scales (including nonlinear scales) with defined zeros, and nonconstant exponents on dimension types. We also show how to encapsulate most of the "magic machinery" that handles the algebraic nature of dimensions and units in a single meta-class that allows us to treat select static types as generators of a free abelian group.

A hardware subsystem is described which, in conjunction with an IBM PC, facilitates the development of various types of vector-quantization (VQ)-based speech coders and also serves as a powerful general-purpose DSP (digital-signal-processor) development system. Each iteration of the usual VQ codebook-design algorithm can be performed by playing, in real-time, an analog cassette tape of recorded speech into the hardware. The hardware is based on the TMS320C25 processor and a semicustom VLSI coprocessor used for VQ codebook searching. The architecture of the system is described and some of the most useful applications that it supports are outlined.>

It is well known that if the data rate is chosen below the available channel capacity, error-free communication is possible. Furthermore, numerous practical error-correction coding techniques exist which can be chosen to meet the user's reliability constraints. However, a basic problem in designing a reliable digital communication system is still the choice of the actual code rate. While the popular rate-1/2 code rate is a reasonable, but not optimum, choice for additive Gaussian noise channels, its selection is far from optimum for channels where a high percentage of the transmitted bits are destroyed by interference. Code combining represents a technique of matching the code rate to the prevailing channel conditions. Information is transmitted in packet formats which are encoded with a relatively high-rate code, e.g., rate 1/2, which can be repeated to Obtain reliable communications when the redundancy in a rate-1/2 code is not sufficient to overcome the channel interference. The receiver combines noisy packets (code combining) to obtain a packet with a code rate which is low enough such that reliable communication is possible even for channels with extremely high error rates. By combining the minimum number of packets needed to overcome the channel conditions, the receiver optimizes the code rate and minimizes the delay required to decode a given packet. Thus, the receiver adapts to the actual jammer-to-signal(J/S)ratio which is critical when the level of interferenceJis not known a priori.

Capacity limits are obtained when binary codes are used for communications over channels in the presence of high levels of interference. The ideal additive Gaussian noise channel and the Rayleigh fading channel are considered. For each channel, the performance of four types of decoders are considered. Both binary and channel measurement (soft decision) decoding are considered; for each of these cases, performance results are obtained when interference can and cannot be detected before decoding. Thus, capacity limits for the minimum achievableE_{b}/N_{o}as a function of the code rateRare obtained for eight different channel models of interest.

The problem of transmitting digital data reliably over a Rician channel, which is used to model the aircraft-satellite link, is treated by an integrated coding and modulation design approach. The results presented enable one to show that it is quite possible to achieve robust signaling which is fairly insensitive to the channel's surface scatter parameters, such as scatter path energy and Doppler spreads. These results illustrate that the scatter energy need not limit the effectiveness of transmitting digital data and, in fact, can improve the performance when operating in the region of low direct path SNR's. These concepts are exemplified by performance curves for frequencyshift keying (FSK) and differential phase-shift keying (DPSK) modulation formats combined with efficient channel measurement decoding algorithms. In addition, general analytical results for evaluating the bit error probability for binary and channel measurement decoders are presented.

Slowly fading channels, such as a troposcatter communication link, are characterized by multiple error bursts which may last for many thousand channel digits, as well as by random errors. It is shown that even the best random error-correcting codes cannot be effective on this type of channel unless some time delay between code letters is introduced to reduce the correlation between channel errors within the code. In addition to the conventional approach of interleaving code letters to obtain error independence, two alternative coding approaches are considered which correct random errors as well as detect and correct multiple bursts, i.e., multiple channel fades. A concatenated coding approach, based on interleaving inner code blocks but not interleaving digits within an inner block, and a new multiple-burst correction code based on generalized burst trapping codes, are shown to represent attractive alternatives to the conventional interleaver approach.

The concept of combining the design of the error-correcting-coding approach and the modulation format is treated in general terms and its effectiveness is demonstrated by a specific implementation referred to as Codem I. A new decoding algorithm is presented, which has the interesting property that the only channel measurement information utilized is the relative reliability of each received digit. The effectiveness of this decoding technique is demonstrated by computer simulation over three different channel models for dispersive channels. Comparisons of the performance of Codem I with the more conventional 16-tone (four-phase DPSK) HF modem are obtained by actual field results as well as by computer simulations. Improvement in error probability in the region of two orders of magnitude is demonstrated when both systems are operating under similar channel conditions and at equal data rates. A further improvement is demonstrated when channel measurement information is used to reject a small percentage (typically less than 3 percent) of codewords that are considered unreliable.

A class of decoding algorithms that utilizes channel measurement information, in addition to the conventional use of the algebraic properties of the code, is presented. The maximum number of errors that can, with high probability, be corrected is equal to one less thand, the minimum Hamming distance of the code. This two-fold increase over the error-correcting capability of a conventional binary decoder is achieved by using channel measurement (soft-decision) information to provide a measure of the relative reliability of each of the received binary digits. An upper bound on these decoding algorithms is derived, which is proportional to the probability of an error fordth order diversity, an expression that has been evaluated for a wide range of communication channels and modulation techniques. With the aid of a lower bound on these algorithms, which is also a lower bound on a correlation (maximum-likelihood) decoder, we show for both the Gaussian and Rayleigh fading channels, that as the signal-to-noise ratio (SNR) increases, the asymptotic behavior of these decoding algorithms cannot be improved. Computer simulations indicate that even for !ow SNR the performance of a correlation decoder can be approached by relatively simple decoding procedures. In addition, we study the effect on the performance of these decoding algorithms when a threshold is used to simplify the decoding process.

Capacity and error bounds are derived for a memoryless binary symmetric channel with the receiver having no a priori information as to the starting time of the code words. The channel capacity is the same as the capacity of the synchronized channel. For all rates below capacity, the minimum probability of error for the nonsynchronized channel decreases exponentially with the code-block length. For rates near channel capacity, the exponent in the upper bound on the probability of error for the nonsynchronized channel is the same as the corresponding exponent for the synchronized channel. For low rates, the largest exponent obtained for the nonsynchronized channel with conventional block coding is inferior to the exponent obtained for the synchronized channel. Stronger results are obtained for a new form of coding that allows for a Markov dependency between successive code words. Bounds on the minimum probability of error are obtained for unconstrained binary codes and for several classes of parity-check codes and are used to obtain asymptotic distance properties for various classes of binary codes. At certain rates there exist codes whose minimum distance, in the comma-free sense, is not only greater than one, but is proportional to the block length.