In a multiple-antenna relay channel, the full-duplex cut-set capacity upper bound and decode-and-forward rate are formulated as convex optimization problems. For half-duplex relaying, bandwidth allocation and transmit signals are optimized jointly. Moreover, achievable rates based on the compress-and-forward strategy are presented using rate-distortion and Wyner-Ziv compression schemes.

We consider a flat fading multiantenna downlink system with a large number of users where the objective is to deliver equal rates to nonoutage users with a low complexity. We show that in the limit of a large number of users, a zero-forcing beamforming strategy combined with a low complexity user grouping algorithm based on a semi-orthogonal user selection achieves asymptotically optimal performance, with respect to an upper bound that can be achieved when no interference is present among users.

We compare the performance of half-duplex relays in downlink cellular system against a baseline system without relays. We simulate the performance of (i) a collaborative power addition scheme, where the relay boosts the received power (P-CPA) at the mobile locations, and (ii) a CPA scheme with power control (PC-CPA) at the base station and relays. Evaluations are done in the context of a 19-cell, 57-sector set-up in which each of the served users must be delivered a message. The user messages are taken to have the same size and 90% of users in the network must be served. Improvements over the baseline due to relay deployments are measured in terms of increase in common rate of users as well as power savings in terms of reduction in peak or average power transmitted by base stations. In the CPA schemes with base stations and relays transmitting at full power, the peak power saving is 1.46 dB, alternately, the throughput improvement over a 1 bit/sec/Hz baseline rate is 21%. In the PC-CPA scheme, the peak power saving is 2.6 dB and the average total power in the system can be reduced by 3 dB.

It has been demonstrated that base station cooperation can reduce co-channel interference (CCI) and increase cellular system capacity. In this work we consider another approach by dividing the system into microcells through denser base station deployment. We adopt the criterion to maximize the minimum spectral efficiency of served users with a certain user outage constraint. In a two-dimensional hexagon array with homogeneous microcell structure, under the proposed propagation model denser base station deployment outperforms suboptimal cooperation schemes (zero-forcing) when the density increases beyond 3 - 12 base stations per km2, the exact value depending on the rules of outage user selection. However, close- to-optimal cooperation schemes (zero-forcing with dirty-paper- coding) are always superior to denser deployment. Performance of a hierarchial cellular structure mixed with both macrocells and microcells is also evaluated.

We investigate optimum zero-forcing beamforming in multiple antenna broadcast channels with per-antenna power constraints. We show that standard zero-forcing techniques, such as the Moore-Penrose pseudo-inverse, considered mainly in the context of sum-power constrained systems are suboptimal when there are per-antenna power constraints. We formulate convex optimization problems to find the optimum zero-forcing beamforming vectors. Our results indicate that optimizing the antenna outputs based on the per-antenna constraints may improve the rate considerably when the number of transmit antennas is larger the number of receive antennas. Having more transmit antennas gives rise to additional signal space dimensions that may be exploited effectively to reduce transmit power at particular antennas with limited power budget.

We quantify the ultimate performance limits of inter-cell coordinatation in a cellular downlink network. The goal is to achieve fairness by maximizing the minimum rate in the network subject to per base power constraints. We first solve the max-min rate problem for a particular zero-forcing dirty paper coding scheme so as to obtain an achievable max-min rate, which serves as a lower bound on the ultimate limit. We then obtain a simple upper bound on the max-min rate of any scheme, and show that the rate achievable by the zero-forcing dirty paper coding scheme is close to this upper bound. We also extend our analysis to coordinated networks with multiple antennas.

Multiple-access interference is one of the major impediments in the reverse link of code-division multiple-access (CDMA) systems, due to the synergy of the users' spreading codes, transmission delays, and the channel characteristics. A space-time dynamic signature-assignment (DSA) algorithm was briefly described by the authors in a previous paper. In this paper, we further elaborate on the space-time DSA approach and its receiver structure for the reverse link of direct-sequence (DS)-CDMA systems using multiple antennas at the receiver. The space-time DSA dynamically assigns the users' spreading codes and transmission delays, i.e., to assign the user signatures, in order to minimize mutual crosscorrelations. In assigning the signatures, the DSA adopts a low-complexity iterative algorithm which utilizes channel information and aims to maximize the signal-to-interference-plus-noise ratio of the poorest performing user at the base station. Analytic results as well as further simulation results are provided to support our arguments.

In this paper, we discuss some of the most basic architectural superstructures for wireless links with multiple antennas: M at the transmit site and N at the receive site. Toward leveraging the gains of the last half century of coding theory, we emphasize those structures that can be composed using spatially one dimensional coders and decoders. These structures are investigated primarily under a probability of outage constraint. The random matrix channel is assumed to hold steady for such a large number of M-dimensional vector symbol transmission times, that an infinite time horizon Shannon analysis provides useful insights. The resulting extraordinary capacities are contrasted for architectures that differ in the way that they manage self-interference in the presence of additive receiver noise. A universally optimal architecture with a diagonal space-time layering is treated, as is an architecture with horizontal space-time layering and an architecture with a single outer code. Some capacity asymptotes for large numbers of antennas are also included. Some results for frequency selective channels are presented: It is only necessary to feedback M rates, one per transmit antenna, to attain capacity. Also, capacity of an (M,N) link is, in a certain sense, invariant with respect to signaling format.

The design of space-time codes that are capable of approaching the capacity of multiple-input-single-output (MISO) antenna systems is a challenging problem, yet one of high practical importance. While a remarkably simple scheme of Alamouti (1998) is capable of attaining the channel capacity in the case of two-transmitter and one-receiver antennas (2,1), no such schemes are known for the case of more than two transmitter antennas. We propose a family of space-time codes that are especially designed for the case of four-transmitter antennas and that are shown to allow the attainment of a significant fraction of the open-loop Shannon capacity of the (4,1) channel.

Multielement system capacities are usually thought of as limited only by correlations between elements. It is shown here that degenerate channel phenomena called "keyholes" may arise under realistic assumptions which have zero correlation between the entries of the channel matrix H and yet only a single degree of freedom. Canonical physical examples of keyholes are presented. For outdoor environments, it is shown that roof edge diffraction is perceived as a "keyhole" by a vertical base array that may be avoided by employing instead a horizontal base array.

The ever growing need for higher capacity in wireless systems has fueled the interest in exploiting the spatial dimension-through the use of antennas arrays-to improve the utilization of the available radio spectrum. As a result, a large number of space-time techniques have been proposed wherein arrays are used to mitigate interference and enhance signal levels. More recently, information theory has shown that, with spatial data multiplexing, very large spectral efficiencies can be attained in multipath channels using transmit and receive antenna arrays. In this paper, the system benefit of using transmit and receive arrays in multicell scenarios is evaluated as a function of both the propagation environment and the number of antennas. Our results confirm the potential for very large system spectral efficiencies associated with the use of transmit and receive arrays, in particular in interference-limited rich-multipath conditions wherein the ability to perform interference mitigation-leading to tighter spectral reuse-and spatial data multiplexing grows with the number of antennas. In environments free of multipath, the potential is smaller but still very significant, associated with interference mitigation and signal enhancement only, since spatial data multiplexing is no longer possible.

Providing wireless high-speed packet data services for Web browsing and streaming multimedia applications will be a key feature in future code-division multiple-access (CDMA) systems. We study down-link CDMA schemes for providing such services using multiple antennas at the transmitter and receiver. We propose a generalization of the point-to-point narrowband Bell Labs layered space-time (BLAST) system to a wideband multiple access system which simultaneously supports multiple users through code spreading. We discuss transmission options for achieving transmit diversity and spatial separation and introduce a generalization of the vertical BLAST detector for CDMA signals. Using link level simulations, we determine the bit-error rates versus signal-to-interference ratio of the various transmitter options. We then describe a novel technique for determining the system spectral efficiency (measured in bits per second per Hertz per cell sector) by incorporating the link level results with system level outage simulations. Using four antennas at the transmitter and eight antennas at each receiver, the system can support multiple receivers at 16 times the voice rate, resulting in a system spectral efficiency an order magnitude higher than a conventional single-antenna voice system.

We propose a novel transmit diversity scheme for the downlink of communication systems that employ four transmit antennas. The scheme can be seen as a simplified transmission architecture admitting an entire family of space-time codes. It can be also seen as an extension of previously proposed techniques (such as those presented in Alamouti (1998), Tarokh et al. (1998), and Hochwald et al. (2001)) to the case of four transmit antennas with complex input data symbols. Our technique has a number of appealing features, namely, it enables a significant portion of the open-loop channel capacity, it requires simple receiver processing (involving typically 2/spl times/2 matrix operations in conjunction with single-user or 2-user decoding) and it admits single-user encoding in an overlay fashion.

In BLAST (Bell Labs' Layered Space Time) systems, very high spectral efficiency can be achieved by employing antenna arrays at both transmit and receive sides. Coding for these array systems is an interesting topic, as such, has seen intensive research. We study coding architectures constructed from conventional codes including convolutional codes and Reed Solomon codes. Our main interest is in the performance and complexity trade-offs involved in the design of coding/decoding and signal detection algorithms. We show that iterative detection and decoding (IDD) can significantly improve the performance of coded BLAST. In some cases, IDD allows for very simple detection algorithms to be used at the receiver front end. Therefore, it may in fact reduce the overall receiver complexity. Our results again demonstrate that coded V-BLAST (vertical-BLAST) is a promising architecture to achieve the great potential of BLAST with limited complexity.

In BLAST (Bell-Laboratories LAyered Space Time) systems, multiple transmit and receive antennas are employed to achieve very high spectral efficiencies. The ideal detection method for such systems is the maximum-likelihood (ML) algorithm. However, the ML complexity increases exponentially with the number of transmit antennas and the number of bits per modulation symbol. A reduced-complexity detection method has been suggested, using ordered successive interference cancellation. We consider two other suboptimum techniques: channel-based adaptive group detection and multistep reduced-constellation detection. The goal is to reduce the two aforementioned complexity exponentials. The algorithms efficiently combine linear processing with local ML search. We limit the complexity by maintaining small ML searching areas, while maximizing the performance under the complexity constraint by optimizing the front-end linear processing and the selection of the search areas.

Recent information-theory results have shown the enormous capacity potential of wireless techniques that use transmit and receive antenna arrays. As a result, a number of layered space-time (BLAST) architectures have been proposed wherein multiple data streams are transmitted in parallel and separated at the receiver on account of their distinct spatial signatures. While extremely promising, all analysis of BLAST to date were restricted to the context of a single-user link. In this paper, the system-level benefit of using BLAST in multicell scenarios is evaluated in comparison with other directive- and adaptive-array techniques.

We demonstrate the capacity growth of multiple-element antenna arrays (MEAs) in a realistic propagation environment using WiSE, an experimental ray tracing tool. WiSE is used to construct the channel response for MEAs operating at 1.9 GHz for two situations: (a) (16-16)-MEAs located inside an office building and (b) (4, 4)-MEAs located in an outdoor fixed wireless loop. We define effective degrees of freedom (EDOFs) as parallel spatial modes of transmission for an MEA. We quantify the increase in both the number of EDOFs and capacity with transmit power, received SNR, and antenna spacing. More EDOFs are present when receiving MEAs are physically closer to the transmitting MEA, regardless of the scattering effect.

We investigate the effects of fading correlations in multielement antenna (MEA) communication systems. Pioneering studies showed that if the fades connecting pairs of transmit and receive antenna elements are independently, identically distributed, MEAs offer a large increase in capacity compared to single-antenna systems. An MEA system can be described in terms of spatial eigenmodes, which are single-input single-output subchannels. The channel capacity of an MEA is the sum of capacities of these subchannels. We show that the fading correlation affects the MEA capacity by modifying the distributions of the gains of these subchannels. The fading correlation depends on the physical parameters of MEA and the scatterer characteristics. In this paper, to characterize the fading correlation, we employ an abstract model, which is appropriate for modeling narrow-band Rayleigh fading in fixed wireless systems.

To guarantee low correlations among user signatures in the reverse-link at the base station, we propose an adaptive algorithm to jointly update the user signatures. Making use of the wireless channel information, we iteratively reassign the spreading signature of the users with the minimum SINR (signal to interference-plus-noise ratio). As shown by simulation results, the proposed algorithm is likely to provide signatures which are orthogonal among users if the number of users is small, then multi-user detection is no longer required. When the number of users is large, the proposed algorithm still tries to maintain equal distances among user signatures, and thus improves the condition of the channel matrix and brings about an increase of capacity by up to 3-4 times, as compared to the same receivers with random codes.

The capacity of multiple input, multiple output wireless channels is computed for Ricean channels. The novelty is a geometrical (ray-tracing) interpretation of the MIMO channel capacity formula to find array geometries which greatly enhance channel capacity compared to SISO systems.

We investigate the use of multiple antennas at the transmitter and multiple antennas and multi-user decorrelating detectors at the receivers for providing high-speed data on the downlink of cellular CDMA systems. We analyze the system's spectral efficiency by combining link level bit error rate simulations with system level signal-to-interference ratio simulations. We show that using random spreading codes, a spectral efficiency of 3.8 bits/chip/sector can be achieved using 8 transmit and 12 receive antennas, compared to a spectral efficiency of 0.16 bits/chip/sector for a voice system with single transmit and receive antennas.

We investigate robust wireless communication in high-scattering propagation environments using multi-element antenna arrays (MEAs) at both transmit and receive sites. A simplified, but highly spectrally efficient space-time communication processing method is presented. The user's bit stream is mapped to a vector of independently modulated equal bit-rate signal components that are simultaneously transmitted in the same band. A detection algorithm similar to multiuser detection is employed to detect the signal components in white Gaussian noise (WGN). For a large number of antennas, a more efficient architecture can offer no more than about 40% more capacity than the simple architecture presented. A testbed that is now being completed operates at 1.9 GHz with up to 16 quadrature amplitude modulation (QAM) transmitters and 16 receive antennas. Under ideal operation at 18 dB signal-to-noise ratio (SNR), using 12 transmit antennas and 16 receive antennas (even with uncoded communication), the theoretical spectral efficiency is 36 bit/s/Hz, whereas the Shannon capacity is 71.1 bit/s/Hz. The 36 bits per vector symbol, which corresponds to over 200 billion constellation points, assumes a 5% block error rate (BLER) for 100 vector symbol bursts.

The capacity of multiple input, multiple output (MIMO) wireless channels is computed for Ricean channels. The novelty is a geometrical (ray-tracing) interpretation of the MIMO channel capacity formula to find array geometries which greatly enhance channel capacity compared to single input-single output (SISO) systems.

We determine the call blocking performance of channel-allocation algorithms where every channel is available for use in every cell and where decisions are made by mobiles/portables based only on local observations. Using a novel Erlang-B approximation method, together with simulation, we demonstrate that even the simplest algorithm, the timid, compares favorably with impractical, centrally administered fixed channel allocation. Our results suggest that an aggressive algorithm, that is, one requiring call reconfigurations, could provide a substantially reduced blocking probability. We also present some algorithms which take major steps toward achieving the excellent blocking performance of the hypothetical aggressive algorithm but having the stability of the timid algorithm.>

One important quantity in assessing the viability of local, autonomous, dynamic channel allocation for microcellular systems is user capacity, defined as the average number of users per channel per cell. Here, we determine the capacity for infinite linear and planar arrays of microcells using a very idealized environment. In particular, propagation and interference considerations are simply represented by the constraint that, if a channel is used in a given cell, it cannot be used in R-consecutive rings of cells around that cell. We investigate the elementary case where there is only a single channel available for use in the system. Using this representation, we compute the best and worst user capacities as well as the capacity achieved by random channel placement. While the environment under which these capacities are derived is highly idealized, the results are useful in two important ways. First, the best capacity and the random channel placement capacity we find here for single-channel, self-organized access are fundamental for computing the traffic characteristics of important multichannel dynamic channel allocation algorithms. Second, the random channel placement capacity is close enough to the best that can be achieved to suggest that local, autonomously implemented, dynamic channel allocation loses little capacity when compared with centrally administered fixed channel allocation.>

The question of whether multilevel signaling can improve the spectral efficiency of optical frequency division multiplexing (FDM) systems is investigated. Multilevel amplitude-shift keying (ASK) and a receiver consisting of an optical channel selection filter (specifically, a single-stage Fabry-Perot), a pin diode for direct detection, and an integrator are assumed. It is also assumed that additive noise is negligible and that the major impairments are adjacent channel interference and intersymbol interference. The analysis shows that, for such a receiver, there is no advantage to going beyond binary signaling. It is also shown that this finding holds up when additive and phase noises and alternative approaches to filtering are considered.>

The required frequency spacings between channels in an optical frequency division multiplexing (FDM) network are considered. The minimum permissible spacings consistent with meeting bit error rate (BER) objectives are derived. The assumed transmission uses on-off keying (OOK), at a data rate 1/T (in bits per second), via external modulation of a laser source having linewidth beta (in hertz). The assumed receiver consists of an optical channel selection filter followed by a p-i-n photodiode and a postdetection integrate-and-dump circuit. The analysis estimates the adjacent channel interference (ACI)-induced floor on BER for the middle of three FDM channels, as a function of frequency spacing and linewidth-to-bit rate ratio ( beta T). For BER=10/sup -9/ and beta T ranging from 0.32 to 5.12, the required channel spacing ranges from 5.2 to 27.5 bit rates. The multiplying factors associated with using (wide-deviation) frequency shift keying (FSK), coherent (heterodyne) detection, and infinitely many FDM channels, respectively, are estimated to be 2.0, at most 3.0, and at most 1.37.>

The main result is the finding of the minimum distance, d/sub min/, for m-ary signals over a class of partial responses of interest in the field of digital magnetic recording. A previously published set of results (see H.K. Thapar and A.M. Patel, 1987) on d/sub min/ for a related class of partial responses relevant to the coaxial cable channel is extended. A simple, powerful algorithm for finding d/sub min/ is employed. A secondary result is given in a table, which extends a previously published table (see G.J. Foschini, 1975), reporting a solution to the corresponding problem for coaxial cable partial responses.>

The benefits of coding for an optical communication system that employs binary on-off keying and heterodyne detection are quantified. The system is impaired by laser phase noise as well as by additive white Gaussian noise (AWGN). A receiver structure especially designed to mitigate the effects of phase noise in the presence of AWGN is assumed. This special receiver structure requires a wider-band front-end IF filter than would be required for a phase-noise-free signal. The results, computed for several different coding schemes, indicate that the benefits of coding are large and the costs are small. For a linewidth-to-bit-rate ratio ( beta T) of 0.64 (for example, 45 Mb/s and 29 MHz linewidth), a half-rate binary code that can correct 3 bit errors provides a 50% reduction in the required IF filter bandwidth (and, therefore, the required IF) and about 5 dB of reduction in required laser power. The benefits of coding are greatest under high- beta T conditions, corresponding to low bit rates where coders and decoders are most practical to implement.>

In future optical networks on frequency division multiple access (FDMA), e.g. TV distribution, optical amplifiers will be required to assure adequate reception. A key figure of merit is eta , the efficiency with which channels can be packed into a given bandwidth relative to the ideal packing of 100% corresponding to abutting channels (channel spacing=channel bandwidth). Packing can be severely limited by intermodulation distortion due to inherent amplifier nonlinearity. Assuming constant envelope signaling, the authors use a recently developed amplifier model to show that, by employing practical coding methods, eta can be greatly increased. A simple, general algebraic formula for eta is derived in terms of amplifier, receiver, and code parameters. For illustrative purposes the authors consider the packing of 50-Mb/s channels into a 1-THz optical bandwidth, assuming typical amplifier and receiver parameters.>

The author conducts a Fokker-Planck analysis of the dynamical aspects of outage protection. He analyzes systems for which the mean time to outage (not meeting a desired signal to interface ratio, rho ) is measured in years (or even decades). He also finds the dependency of mean time of outage on rho , bit rate, user population size, amount of laser phase noise and the parameter representing the degree to which the laser carrier frequencies wander with passage of time. The author interprets this relationship for the realm of nonhierarchical accommodation on the order of thousands of simultaneous users at 100 mb/s each, using semiconductor lasers. The results suggest that such networks with hundreds of gigabits of throughput are possible provided the unwanted wander can be limited to levels quantified.>

Consideration is given to the case of an optical pulse containing phase noise which is passed through either an optical filter or (following heterodyne lightwave detection) an electrical filter. Because of the phase noise, the envelope of the filter output at any instant is a random variable. An analytical method is developed for estimating the probability density function (pdf) of this envelope for different kinds of filter responses and for realistic combinations of phase noise severity and filter bandwidth. Obvious applications are to detection analyses of coherent lightwave systems, wherein finite laser linewidths constitute an important source of impairment. For each of the several types of filters considered, the envelope PDF can be accurately fitted by an exponential function approximation, where the decay constant is related in a simple way to known system parameters.>

The decision of on-off keying (OOK) and frequency-shift keying (FSK) is considered for coherent lightwave communications in which the optical pulses are corrupted by the phase noise associated with nonzero laser linewidths. Heterodyne lightwave detection is assumed, followed by intermediate frequency filtering, envelope detection, and postdetection low-pass filtering. Using analytical results published previously, theoretical minimum values of the required average power are obtained in photons/bit, for achieving a bit error rate of 10/sup -9/. Numerical results are given as functions of laser linewidth-to-bit-rate ratio for OOK, binary FSK (or 2-FSK), and 8-FSK. It is shown that heterodyne detection for lightwave signals of this kind can be made highly robust to phase noise, in contrast to the case of binary phase-shift keying.>

Ways of supporting large numbers (on the order of thousands) of simultaneous high-speed ( approximately 10 Mb/s) users on the lowest hierarchical unit of a coherent optical system are investigated. Assuming each channel uses a different optical carrier, a key impairment is laser phase noise, which causes modulated optical carriers, nominally widely separated in frequency, to not be truly spectrally disjoint. To deal with this problem in consideration of the superabundance of optical bandwidth, attention is focused on the region of low spectral utilization. For this region, formulas are derived that describe the performance of three arrangements of optical channels: equally spaced carriers, randomly placed carriers, and randomly placed carriers with spread spectrum. The formulas quantify the great superiority of equally spaced carriers over random placement, despite the highly significant benefit afforded by spread spectrum. Numerical examples are worked out to show this result.>

Waves are treated that modulate by either on-off keying (OOK) or binary frequency-shift keying (FSK) and are further impaired by additive Gaussian noise. Heterodyne detection of such a waveform produces an electronic bandpass signal, which, to ease demodulation in the presence of phase noise, is noncoherently demodulated to extract the baseband pulse stream. The treatment goes beyond previous bit error rate (BER) analyses of optical heterodyne receivers for OOK and FSK. First, there is full adherence to the standard (Brownian motion) model of phase noise. Also, the receiver structure is formulated in such a way that the probability density function of the receiver output samples can be accurately determined. This permits calculations of the additive noise and phase noise tolerable when achieving bit error rates as small as 10/sup -9/. Finally, the study is comprehensive regarding the range of parameters explored. Filtering at an intermediate frequency (IF) alone, as well as IF filtering plus postdetection low-pass filtering, is considered. When the receiver parameters decision threshold (for OOK) and IF filter bandwidth are optimized, large amounts of phase noise can be accommodated with only minor increases in required signal-to-noise ratio. This is especially important when the bit rate is moderate compared to the laser linewidth.>

The phase noise associated with single-mode semiconductor lasers must be accounted for in performance studies of lightwave communication systems. The standard phase noise model is a Brownian-motion stochastic process. Although many analyses of lightwave communication systems have been published, none, to the authors knowledge, has fully adhered to the standard model. The reason is that a proper characterization of filtered lightwave signal had not been achieved. Such a characterization, along with theoretical approaches to obtaining it, is detailed. The authors show, for example, how to generate probability density functions (PDFs) of the magnitude of a filtered laser tone (with special attention to the tail region) and how to analytically represent the characteristic function of the PDF in closed form in the small-phase-noise realm. With the characterization in place, the stage is now set for determining the bit-error rate performance of advanced detection techniques which seek to mitigate the phase noise impairment.>

Efficient design of service facilities, such as data or computer networks that meet random demands, often leads to the sharing of resources among users. Contention for the use of a resource results in queueing. The waiting room is a part of any such service facility. The number of accepted service requests per unit of time (throughput), or the fraction of the time the servers are busy (utilization), are often used as performance measures to compare designs. Most common models in queueing theory consider the design of the waiting rooms with the assumption that, although individual requests may differ from one another, they are statistically indistinguishable. However, there are several instances where available information allows us to classify the requests for service into different types. In such cases the design of the service facility not only involves the determination of an optimum size for the waiting room but also the rules of sharing it among the different types. Even with a fixed set of resources, the rules of sharing them can influence performance. In data networks (or computer networks) the "waiting room" consists of memory of one kind or another. Messages (jobs) destined for different locations (processors) sharing common storage is an important example of shared use of memory. Recently, Kleinrock and Kamoun have modeled such use of memory and computed the performance of various policies for managing the allocation of memory to several types of users. Decisions to accept or reject a demand for service were based on the number of waiting requests of each type. However, the optimal policy was not determined even in the case where there were only two types of users. We determine the structure of optimal policies for the model considered with three types of users. The optimal policy consists of limiting the number of waiting requests of each type, and reserving a part of the memory to each type.

The steady-state queueing behavior of interacting computers is basic to computer network theory. Equilibrium properties are determined for the diffusion model for the special case of a symmetrically disposed pair of communicaling computers. In the mathematical model, arrivals to the system can represent the presentation of programming jobs, and each service represents the completion of a stage of processing. The exogenous arrivals and the services during the busy period are permitted to be arbitrary renewal processes. Computer interaction arises as follows. When each stage of processing is completed, a certain probability, exists that the entire job is complete. However, with the complementary probability., the job is input to the other computer for an additional stage of processing. In the space of all systems we find an infinite set of curves whereon the joint equilibrium density reduces to a very simple form. For the general case, a direct formal infinite series representation of the joint equilibrium density, is found. Using conformal mapping the moment generating function is obtained. Rational expressions for the mean queue size (and delay) are given. The mean queue size for Poisson arrivals is interpreted. A simple expression for the tail exponent for the queue size marginal is found. The nature of the joint density, in the neighborhood of the origin is delineated. The connection to delay equilibria is mentioned. Extensions to a larger class of communicating computer pairs is indicated.

We consider the problem of optimal dynamic allocation of a limited number of processors to service the demands from different types of users. The types are differentiated by the rates at which they enter requests for service and the mean length of time they occupy a single processor. The decision to accept or reject a request for service may be based on the number of processors occupied by each type. Throughput, or utilization of processors, weighted differently for each type may be used as a performance measure. While the optimum allocation question is formulated for any finite number of customer types, our solution is limited to the case of two competing customer classes. For two types of users we show that among a large class of policies, the optimum is the easily implemented policy of restricting the maximum number of processors that one of the two types can occupy at any time. The requests from the other type are always honored as long as a processor is available for service. It is intuitively reasonable that, despite the complex interactivity permitted in some policies and the multidimensional characterization of a customer type, one of the customer types should have a relative advantage and be permitted open access while a hard limitation is enforced on the competition. The crux of the proof involves a policy space perturbation argument relying on the structure of the equilibrium density.

Diffusion theory has sometimes been successful in providing excellent approximate solutions to difficult queueing problems. Here we explore whether such methods can be used to analyze a basic dynamic routing strategy associated with a single idealized node in a data network. We analyze a dynamic routing policy where messages, or packets, that arrive at a certain node are routed to leave the node on the link having the shorter queue. In the model, message or packet arrivals are Poisson and the service time is exponentially distributed. We explore a heavy traffic diffusion method and we also discuss the limitations of an ad hoc approach to applying diffusion. For a node withKoutgoing queues we find, under the assumption of heavy traffic, the optimum dynamic strategy, in the sense of minimizing the average delay. When this optimum dynamic strategy is compared to a static strategy where the outgoing traffic is split among theKqueues, we find that the average delay for the dynamic system is better by a factor ofK.

In the detection ofm-level pulse-amplitude modulation (PAM) signals transmitted over a noisy linear\nu-symbol memory channel, maximum likelihood sequence detection (MLSD) is asymptotically optimum in the sense that the exponent of the probability of symbol error in the limit of small noise is the largest that can be achieved by any detector. A reduced state detection (RSD) is developed with the aim of mitigating the computational complexity of MLSD while attaining the same error exponent as MLSD. In RSD, for each baud, the recent received signal levels delineate a certain list of the most probable of them^{nu}possible states. Retention of only the paths threading through these most probable states is the key to success of RSD. Suppose it is required that the number of states retained at any time not exceed\psi. When\psiis less than the number of states required for RSD, it is shown how to modify RSD so that no more than\psistates are retained and how to assess the degradation of the error exponent.

The degree of complexity of a digital signal processor is closely related to the precision with which samples of an incoming analog waveform are represented. There is considerable interest in determining how coarse this representation can be without seriously degrading performance from that of an ideal processor of unquantized samples. This question is examined for a receiver of noisy, linearly distorted pulse amplitude modulation (PAM) signals. An optimum [maximum likelihood (ML)] detector, analogous to the Viterbi detector for unquantized samples, is derived for the case of a quantized sample sequence. Performance is evaluated under the assumption of high signal-to-noise ratio (SNR), and the resultant error probability is a good approximation for coarse quantization, and an upper bound for any degree of quantization. For a specified error probability, the degree of quantization suggested by this approach is conservative. Since receiver complexity is closely associated with the length of the digital representation of an input sample, an upper bound on receiver complexity is also suggested. Numerical evaluation of the error probability is quite tedious for an arbitrary channel; however, system performance may be readily evaluated for partial-response (PR) signaling. For the PR channels

The minimum distanced_{\text{min}}is the fundamental performance parameter for modems using maximum likelihood sequence estimation (MLSE). This paper provides a procedure for finding the minimum distance for classes of systems of moderate complexity, e.g., with a few hundred states. This is done by applying various rules which reduce the set of error sequences that have to be considered to a small number. Nulls in the channel's frequency spectrum reduce the number of critical error sequences still further. Examples using the procedure are given for many classes of responses of interest. It is also noted that the optimum transmitter design problem is a convex programming problem.

Maximum-likelihood sequence estimation (MLSE) of data sequences is considered as an approach to increasing data rates over band-limited channels, such as exist in analog telephone facilities. Analytical prediction of the efficacy of MLSE for specific channels had been viewed as intractable until Forney gave a formula for an asymptotic upper bound on the probability of symbol errorp. Forney's bound involved an infinite series, and letting the noise power No --} 0, he chose the asymptotically largest series term as an asymptotic bound onp, ignoring a very basic perplexing open question: How do we know the bounding series is not identically infinity for allN_0 \rightarrow 0?We show that under very general conditions Forney's bounding series converges for a nontrivial intervalN_0 > 0. As a corollary, we prove Forney's aforementioned asymptotic formula forp. The analysis includes the class of channels with spectral nulls, since band edge nulls can be associated with telephone channels that are pulsed at high rates.

Digital data systems are considered in which reception is based on the principle of maximum-likelihood sequence estimation (MLSE) and in which the channel has the coaxial cable power transfer characteristice^{-\alpha \mid \omega \mid ^{1/2} }. When only the average transmitter output power and the response memory (\nu) are constrained, it is shown that, as\alphaincreases, the optimal overall system impulse response tends to a partial response for which the corresponding frequency characteristic is proportional to the unique normalized trigonometric polynomial having\nuth order zeros at the Nyquist bandlimits. These same partial responses result if\alphais fixed and the band rate is increased. This observation helps explain a recent numerical study by Fredricsson that has stirred wide-spread interest. The minimum distance associated with such an optimal response is tabulated for various values of\nuand various numbers of levels.

A considerable amount of literature exists on the problem of selecting an efficient set ofNdigital signals with in-phase and quadrature components for use in a suppressed carrier data transmission system. However, the signal constellation which minimizes the probability of error in Gaussian noise, under an average power constraint, has not been determined when the number of signals is greater than two. In this paper an asymptotic (large signal-to-noise ratio) expression, of the minimum distance type, is derived for the error rate. Using this expression, a gradient-search procedure, which is initiated from several randomly chosenN-point arrays, converges in each case to a locally optimum constellation. The algorithm incorporates a radial contraction technique to meet the average signal power constraint. The best solutions are described for several values ofNand compared with well-known signal formats. As an example, the best locally optimum 16-point constellation shows an advantage of about 0.5 dB in signal-signal-to-noise ratio over quadrature amplitude modulation. The locally optimum constellations are the vertices of a trellis of (almost) equilateral triangles. AsN \rightarrow \infty, it is rigorously proved in the Appendix that the optimum constellations tend toward an equilateral structure, and become uniformly distributed in a circle.

In PCM transmission systems, ensuring repeater timing and regenerative capabilities requires monitored enforcement of the ones density of the line waveform. One possible corrective monitor action is to pre-empt information bits and insert ones when necessary, and thus introduce errors into the pulse stream. The analysis of the resultant error rates for classes of digital and analog implementations of a PCM monitor is accomplished via theoretical consideration of certain stationary Markov processes.