This paper presents generalized channel coding theorems for a time-slotted distributed communication system where a transmitter-receiver pair is communicating in parallel with other transmitters. Assume that the channel code of each transmitter is chosen arbitrarily in each time slot. The coding choice of a transmitter is denoted by a code index parameter, which is known neither to other transmitters nor to the receiver. Fundamental performance limitation of the system is characterized using an achievable region defined in the space of the code index vectors. As the codeword length is taken to infinity, for all code index vectors inside the region, the receiver will decode the message reliably, while for all code index vectors outside the region, the receiver will report a collision reliably. A generalized system error performance measure is defined as the weighted sum of probabilities of different types of communication error events. Assume that the receiver chooses an “operation region” and intends to decode the message if the code index vector is inside the operation region. Achievable bounds on the tradeoff between the operation region and the generalized error performance measure are obtained under the assumption of a finite codeword length.

This paper extends linear-complexity concatenated coding schemes to fountain communication over the discrete-time memoryless channel. Achievable fountain error exponents for one-level and multi-level concatenated fountain codes are derived. Several important properties of the concatenated coding schemes in multi-user fountain communication scenarios are demonstrated.

This paper applies information theoretic analysis to packet-based random multiple access communication systems. A new channel coding approach is proposed for coding within each data packet with built-in support for bursty traffic properties, such as message underflow, and for random access properties, such as packet collision detection. The coding approach does not require joint communication rate determination either among the transmitters or between the transmitters and the receiver. Its performance limitation is characterized by an achievable region defined in terms of communication rates, such that reliable packet recovery is supported for all rates inside the region and reliable collision detection is supported for all rates outside the region. For random access communication over a discrete-time memoryless channel, it is shown that the achievable rate region of the introduced coding approach equals the Shannon information rate region without a convex hull operation. Further connections between the achievable rate region and the Shannon information rate region are developed and explained.

A new channel coding approach was proposed by Luo and Ephremides for random multiple-access communication over the discrete-time memoryless channel. The coding approach allows users to choose their communication rates independently without sharing the rate information among each other or with the receiver. The receiver will either decode the messages or report a collision depending on whether reliable message recovery is possible. It was shown that, asymptotically as the codeword length goes to infinity, the set of communication rates supporting reliable message recovery can be characterized by an achievable region which equals Shannon's information rate region without a convex hull operation. In this paper, we derive achievable bounds on error probabilities, including the decoding error probability and the collision miss detection probability, of random multiple-access systems with a finite codeword length. Achievable error exponents are obtained by taking the codeword length to infinity.

Random access communication is used in practical systems to deliver bursty short messages. Because users only transmit occasionally, it is often difficult for the receiver to keep track of the time varying wireless channel states. Under this motivation, we develop channel coding theorems for random multiple access communication over compound channels with finite codeword length. Error performance bound and asymptotic error probability scaling laws are derived. We found that the results also help in deriving error performance bounds for the random multiple access system where the receiver is only interested in decoding messages from a user subset.

We extend Information Theoretic analysis to time-slotted packet random access communication with bursty sources. A new channel coding approach for coding within each packet is proposed with built-in support for bursty sources phenomena, such as message underflow, and for random access mechanisms, such as packet collision detection. The coding approach does not require joint communication rate determination either between the transmitters or between the transmitters and the receiver. Its performance limitation is characterized by an achievable region defined in terms of communication rates, such that reliable packet recovery is supported for all rates within the region and reliable collision detection is supported for all rates outside the region. For random access communication over a discrete-time memoryless channel using a class of random coding schemes, it is shown that the maximum achievable rate region of the introduced coding approach equals the Shannon information rate region without a convex hull operation.

A class of wireless multicast utility optimization problems are considered. Assume network utility is only a function of link throughput and nodes' transmission power. Under a set of physical layer assumptions, the impact of physical and data-link layer configurations to the upper layers in a wireless network can be characterized using a configuration graph. Network layer utility optimization can consequently be carried out via iterations that optimize network layer algorithms over the configuration graph and revise physical, data-link layer configurations to improve the configuration graph. For a class of wireless multicast networks with optimal network coding, the number of point-to-multipoint links involved in network utility optimization is only polynomial, as opposed to exponential, in the number of nodes. This leads to a reduced complexity in exhaustive searching algorithms, such as optimal utility maximization. Consequently, simulations of these algorithms for moderate-sized networks become feasible.

In, a new channel coding approach was proposed for random multiple access communication over the discrete-time memoryless channel. The coding approach allows users to choose their communication rates distributively without sharing the rate information with each other and the receiver. The receiver makes decoding and collision report decisions depending on whether reliable message recovery is possible. It was shown that, asymptotically as codeword length goes to infinity, the set of communication rates supporting reliable message recovery can be characterized by an achievable region which equals Shannon's information rate region without a convex hull operation. In this paper, we derive stronger versions of the coding theorems in by characterizing how system error probability, defined as the maximum of decoding error probability and collision miss detection probability, approaches zero with respect to the codeword length.

This paper studies the Gaussian multiaccess channel with multiantenna basestation in the low signal to noise ratio (SNR) regime. We compare the spectral efficiencies of the optimal superposition channel sharing scheme and two simple alternatives: the time division multiaccess (TDMA) scheme and superposition multiaccess with single-user decoding (SSD). Due to the fact that SSD, but not TDMA, exploits the multiuser multiplexing gain, the relative spectral efficiency of SSD over TDMA grows drastically as the number of antennas at the basestation increases. The results suggest that, in the low SNR regime with multiple antenna basestation, TDMA's suboptimality can no longer be offset by its simplicity since SSD can achieve much higher spectral efficiency while the simplicities of the two channel sharing schemes are similar.

This paper investigates fountain communication over discrete-time memoryless channels. Fountain error exponent achievable by linear complexity concatenated fountain codes is derived.

This paper shows that, under certain conditions, a wireless network can bemodeled by a directed configuration graph with possible hyperarc links if the transmission schedule is given. Assume single multicast session. The maximum achievable multicast throughput equals the max-flow min-cut bound of the configuration graph. An optimization framework is proposed to maximize the multicast throughput via iterative updates of the transmission schedule. It is demonstrated that the optimal multicast throughput can be obtained without exploring either a large number of hyperarc links or a large number of cuts, although efficient suboptimal algorithm is needed to avoid searching link combinations and to reduce the complexity further to polynomial in the number of nodes. It is also shown that, when the configuration graph has hyperarc links, the minimum cut can no longer be obtained using the well-known flow augmenting path algorithm. An alternative algorithm is proposed.

This letter considers the average complexity of maximum-likelihood (ML) decoding of convolutional codes. ML decoding can be modeled as finding the most probable path taken through a Markov graph. Integrated with the Viterbi algorithm (VA), complexity reduction methods often use the sum log likelihood (SLL) of a Markov path as a bound to disprove the optimality of other Markov path sets and to consequently avoid exhaustive path search. In this letter, it is shown that SLL-based optimality tests are inefficient if one fixes the coding memory and takes the codeword length to infinity. Alternatively, optimality of a source symbol at a given time index can be testified using bounds derived from log likelihoods of the neighboring symbols. It is demonstrated that such neighboring log likelihood (NLL)-based optimality tests, whose efficiency does not depend on the codeword length, can bring significant complexity reduction. The results are generalized to ML sequence detection in a class of discrete-time hidden Markov systems.

We consider the communication system that transmits a sequence of binary vector symbols over a vector intersymbol interference (ISI) channels subject to additive white Gaussian noise. Conventionally, maximum likelihood (ML) sequence is computed using the Viterbi algorithm (VA), whose complexity scales exponentially in both the symbol vector length and the number of ISI channel taps. We show that, as the signal to noise ratio (SNR) goes to infinity, the ML sequence can be obtained with an asymptotic complexity scaling linearly in the number of channel taps and quadratically in the symbol vector length.

Theory and applications of model-based fault diagnosis have progressed significantly in the last four decades. In addition, there has been increased use of model-based design and testing in the automotive industry to reduce design errors, perform rapid prototyping, and hardware-in-the-loop simulation (HILS). This paper presents a new model-based diagnostic development process for automotive engine control systems. This process seamlessly employs a graph-based dependency model and mathematical models for online/offline diagnosis. The hybrid method improves the diagnostic system's accuracy and consistency, utilizes existing validated knowledge on empirical models, enables remote diagnosis, and responds to the challenges of increased system complexity. The development platform consists of an engine electronic control unit (ECU) rapid prototyping system and HILS equipment—the air intake subsystem (AIS). The diagnostic strategy is tested and validated using the HILS platform.

This paper studies multiple access channels with additive Gaussian noise in the low signal to noise ratio (SNR) regime. We compare the spectral efficiencies of the optimal superposition channel sharing scheme and two simple alternatives: the time division multiple access (TDMA) scheme and the parallel multiple access scheme with single user decoding (PMAS). We consider the situation when the receiver has multiple receive antennas while each transmitter only has single antenna. We show that, due to TDMA's inefficiency in exploiting the multiuser multiplex gain, the relative spectral efficiency of PMAS over TDMA grows drastically as the number of receive antennas increase. The relative spectral efficiency of PMAS over the optimal scheme is approximately 1/2, irrespective of the number of receive antennas. Since the simplicities of PMAS and TDMA are similar, our results suggest that PMAS is a better alternative to TDMA for multiple access system in the low SNR regime

This paper studies finite-terminal random multiple access over the standard multipacket reception (MPR) channel. We characterize the relations among the throughput region of random multiple access, the capacity region of multiple access without code synchronization, and the stability region of ALOHA protocol. In the first part of the paper, we show that if the MPR channel is standard, the throughput region of random multiple access is coordinate convex. We then study the information capacity region of multiple access without code synchronization and feedback. Inner and outer bounds to the capacity region are derived. We show that both the inner and the outer bounds converge asymptotically to the throughput region. In the second part of the paper, we study the stability region of finite-terminal ALOHA multiple access. For a class of packet arrival distributions, we demonstrate that the stationary distribution of the queues possesses positive and strong positive correlation properties, which consequently yield an outer bound to the stability region. We also show the major challenge in obtaining the closure of the stability region is due to the lack of sensitivity analysis results with respect to the transmission probabilities. Particularly, if a conjectured "sensitivity monotonicity" property held for the stationary distribution of the queues, then equivalence between the closure of the stability region and the throughput region follows as a direct consequence, irrespective of the packet arrival distributions.

This paper extends our earlier results. We assume that the receiver has the capability of capturing multiple packets so long as the signal-to-interference-plus-noise ratio (SINR) of each packet is above a designed threshold T throughout its transmission period. We prove that, compared with a multiple-power-level system, the single-power-level system in which all nodes transmit at the maximum allowable power level achieves optimal throughput, under a condition that T exceeds the value 3.33. Given a minimum throughput requirement, under the same condition on T, the single-power-level system also achieves the maximum average packet capture probability as well as the optimum energy usage efficiency. If the multiple-power-level systems are constrained such that higher power levels always have shorter packet lengths, then the above results hold for T greater than 2.

This paper studies finite-terminal random multiple access over a standard multi-packet reception (MPR) channel. In the first part of the paper, we show that if the MPR channel is standard, the throughput region of random multiple access is co-ordinate convex. We then study the information capacity region of multiple access without code synchronization and feedback. We show that the asymptotic capacity region is identical to the throughput region. In the second part of the paper, we study the stability region of ALOHA multiple access. For a class of packet arrival distributions, we show that the stationary distribution of the queues possesses the positive and strong positive correlation properties; and this consequently gives an outer bound to the stability region. We also show that if a conjectured "sensitivity monotonicity" property can be shown for the stationary distribution of the queues, then the equivalence between the closure of the stability region and the throughput region follows as a direct consequence, irrespective of the packet arrival distributions

In an energy-efficient wireless communication system, transmit powers are minimized subject to predetermined signal-to-interference ratio (SIR) requirements. In this paper, a general framework for distributed stochastic power control (PC) algorithms is proposed, where the transmit powers are updated based on stochastic approximations. The proposed algorithms are distributed in the sense that no global information is needed in the power updates. Interference to each user is estimated locally via noisy observations. Two types of stochastic PC algorithms are studied: standard stochastic PC algorithms where the interference estimator is unbiased, and quasi-standard stochastic PC algorithms where the interference estimator is biased. The conditions under which the stochastic PC algorithms converge to the unique optimal solution are identified. Corresponding to two classes of iteration step-size sequences, two types of convergence, the probability one convergence and convergence in probability, are shown for both algorithms based on recent results in the stochastic approximation literature. Based on the theoretical results, some well-known stochastic PC algorithms, such as stochastic PC with matched filter receivers, and joint stochastic PC with blind minimum mean-squared error (MMSE) interference suppression, are revisited; several new stochastic PC algorithms, such as stochastic PC with minimum-power base-station assignment, and stochastic PC with limited diversity, are proposed. It is shown that these algorithms fall into either the standard or the quasi-standard stochastic PC framework. Simulation results are given to illustrate the performance of the proposed algorithms in practical systems.

The optimal signature sequences that maximize the sum capacity of a direct sequence code-division multiple-access (CDMA) system are characterized in the general case of symbol delay profile and user power constraints. It is shown that the optimal sum capacity of the symbol asynchronous system equals that of the symbol synchronous system with the same user power constraints. With the optimal signature sequence set, the maximum sum capacity is achieved with white Gaussian input signals. The existence of the optimal signature sequence set is proved by the proposal of an explicit construction method for arbitrary user delay profiles and power constraints.

The optimal signature sequences that maximize the sum capacity of a direct sequence CDMA system are characterized in the general case of symbol delay profile and user power constraints. It is shown that the optimal sum capacity of the symbol asynchronous system equals that of the symbol synchronous system with the same user power constraints. With the optimal signature sequence set, the maximum sum capacity is achieved with white Gaussian input signals. The existence of the optimal signature sequence set is proved by the proposal of an explicit construction method for arbitrary user delay profiles and power constraints.

The probabilistic data association (PDA) method for multiuser detection (MUD) over synchronous CDMA channels is extended to the signal detection problem in V-BLAST systems. Computer simulations show that the algorithm has an error probability that is significantly lower than that of the V-BLAST optimal order detector and has a computational complexity that is cubic in the number of transmit antennas.

A complex sphere decoding algorithm is presented for signal detection in V-BLAST systems, which has a computational cost that is significantly lower than that of the original complex sphere decoder (SD) for a wide range of SNRs. Simulation results on a 64-QAM system with 23 transmit and 23 receive antennas at an SNR per bit of 24 dB show that the new sphere decoding algorithm obtains the ML solution with an average cost that is at least 6 times lower than that of the original complex SD. Further, the new algorithm also shows robustness with respect to the initial choice of sphere radius.

In this letter, we compare the complexity and efficiency of several methods used for multiuser detection in a synchronous code-division multiple-access system. Various methods are discussed, including decision-feedback (DF) detection, group decision-feedback (GDF) detection, coordinate descent, quadratic programming with constraints, space-alternating generalized EM (SAGE) detection, Tabu search, a Boltzmann machine detector, semidefinite relaxation, probabilistic data association (PDA), branch and bound (BBD), and the sphere decoding (SD) method. The efficiencies of the algorithms, defined as the probability of group detection error divided by the number of floating point computations, are compared under various situations. Of particular interest is the appearance of an "efficient frontier" of algorithms, primarily composed of DF detector, GDF detector, PDA detector, the BBD optimal algorithm, and the SD method. The efficient frontier is the convex hull of algorithms as plotted on probability of error versus computational demands axes: algorithms not on this efficient frontier can be considered dominated by those that are.

A fast optimal algorithm based on the branch-and-bound (BBD) method is proposed for the joint detection of binary symbols of K users in a synchronous code-division multiple-access channel with Gaussian noise. Relationships between the proposed algorithms (depth-first BBD and fast BBD) and both the decorrelating decision-feedback (DF) detector and sphere-decoding algorithm are clearly drawn. It turns out that decorrelating DF detector corresponds to a "one-pass" depth-first BBD; sphere decoding is, in fact, a type of depth-first BBD, but one that can be improved considerably via tight upper bounds and user ordering, as in the fast BBD. A fast "any-time" suboptimal algorithm is also available by simply picking the "current-best" solution in the BBD method. Theoretical results are given on the computational complexity and the performance of the "current-best" suboptimal solution.

A fast optimal algorithm based on the branch and bound (BBD) method is proposed for the joint detection of binary symbols of K users in a synchronous code-division multiple access (CDMA) channel with Gaussian noise. Relationships between the proposed algorithms (depth-first BBD and fast BBD) and both the decorrelating decision feedback (DF) detector and sphere decoding (SD) algorithm are clearly drawn. It turns out that decorrelating DF detector corresponds to a "one-pass" depth-first BBD; sphere decoding is in fact a type of depth-first BBD, but one that can be improved considerably via tight upper bounds and user ordering as in our fast BBD.

The probabilistic data association (PDA) method is extended to multiuser detection over symbol-asynchronous code-division multiple access (CDMA) communication channels. A direct extension as well as a sliding window processing method are introduced. While achieving near-optimal performance with O(K/sup 3/) computational complexity in synchronous CDMA, K being the number of users, it is shown that, in asynchronous CDMA, the probability of group detection error of the proposed PDA method is very close to the performance lower bound provided by an ideal clairvoyant optimal detector, and the computational complexity is only marginally increased to O([h/s]K/sup 3/) per symbol, where h and s are the width and the sliding rate of the processing window, respectively. Due to the outstanding performance of the PDA detector in heavily overloaded asynchronous systems, it is observed that an optimally designed synchronous system can be easily outperformed by an arbitrarily designed asynchronous system. Hence, it is proposed to use asynchronous transmission deliberately, even when synchronous transmission is possible - asynchronous is better than synchronous!.

A strategy of user ordering and time labeling for a decision feedback (DF) detector in asynchronous code-division multiple-access communications is proposed and is proved to be optimal for the ideal DF detector. The proposed algorithm requires O(K/sup 4/) offline operations, where K is the number of users. Although error propagation complicates the analysis of the actual DF detector, computer simulations show that, with the proposed user ordering and time labeling, the performance of an actual DF detector overlays the theoretical bound in most cases.

The group decision feedback (GDF) detector is studied in this letter. Given the maximum group size, a grouping algorithm is proposed. It is shown that the proposed grouping algorithm maximizes the symmetric energy of the multiuser detection system. Furthermore, based on a set of lower bounds on asymptotic group effective energy (AGEE) of the GDF detector, it is shown that the proposed grouping algorithm, in fact, maximizes the AGEE lower bound for every group of users. The theoretical analysis of the grouping algorithm enables the offline estimation of the computational cost and the performance of a GDF detector. The computational complexity of a GDF detector is exponential in the largest size of the groups. Simulation results are presented to verify the theoretical conclusions. The results from this letter can be applied to the decision feedback detector by setting the maximum group size to one.

A strategy for user ordering and time labeling for a decision feedback (DF) detector in asynchronous Code-Division Multiple Access (CDMA) communications is discussed. Ordering and labeling would at first appear to be of a complexity exponential in K, the number of users. Surprisingly, optimal sequencing requires only O(K4) operations, and is needed only once per packet: it is thus a cheap way to obtain an often marked improvement in performance, compared to power-ordering and chronological labeling.

This paper presents a design methodology for synthesizing organizations to execute complex missions efficiently. It focuses on devising mission planning strategies to optimally achieve mission goals while optimally utilizing organization's resources. Effective planning is often the key to successful completion of the mission, and conversely, mission failure can often be traced back to poor planning. Details on subsequent phases of the design process to construct the mission-driven human organizations are discussed in a companion paper.

For pt.I. see ibid., p. 346-59. This paper presents a multiobjective structural optimization process of designing an organization to execute a specific mission. We provide mathematical formulations for optimization problems arising in Phases II and III of our organizational design process and polynomial algorithms to solve the corresponding problems. Our organizational design methodology applies specific optimization techniques at different phases of the design, efficiently matching the structure of a mission (in particular, the one defined by the courses of action obtained from mission planning) to that of an organization. It allows an analyst to obtain an acceptable tradeoff among multiple mission and design objectives, as well as between computational complexity and solution efficiency (desired degree of suboptimality).

A probabilistic data association (PDA) method is proposed in this paper for multiuser detection over synchronous code division multiple access (CDMA) communication channels. PDA models the undecided user signals as binary random variables. By approximating the interuser interference (IUI) as Gaussian noise with an appropriately elevated covariance matrix, the probability associated with each user signal is iteratively updated. Computer simulations show that the system usually converges within 3-4 iterations, and the resulting probability of error is very close to that of the optimal maximum likelihood (ML) detector. Further modifications are also presented to significantly reduce the computational cost.

The sequential group detection technique is a generalization of the decision feedback detector: in the latter, users are successively demodulated and cancelled one-by-one, while in the former this basic operation is performed simultaneously on groups of users. The computational complexity of a group decision feedback detector (GDFD) is exponential in the largest size of the groups; thus instead of using the partition of users as design parameters, choosing the "maximum group size" is more reasonable in practice. Given the maximum group size, a grouping algorithm is proposed. It is shown that the proposed grouping algorithm maximizes the asymptotic symmetric energy (ASE) of the multiuser detection system. Furthermore, based on a set of lower bounds on the asymptotic group symmetric energy (AGSE) of the GDFD, it is shown that the proposed grouping algorithm, in fact, maximizes the AGSE lower bound for every group of users. Together with a fast computational method based on branch-and-bound, the theoretical analysis of the grouping algorithm enables the offline estimation of the computational cost and the performance of GDFD. Simulation results are presented to verify the theoretical results.

We (2001) previously showed that for solutions of the binary quadratic programming problem there exists an "efficient frontier" in the performance/speed domain among the algorithms which characterizes the relative performance of each algorithm. Here, in addition to the algorithms implemented previously, the Boltzmann machine, genetic algorithm and space alternating generalized EM (SAGE) receiver are implemented and results are given for much larger scale problems. Simulation results show that these and several other of the proposed methods can significantly outperform the decision feedback detector or its group counterpart.

We (2001) previously showed that for solutions of the binary quadratic programming problem there exists an "efficient frontier" in the performance/speed domain among the algorithms which characterizes the relative performance of each algorithm. Here, in addition to the algorithms implemented previously, the Boltzmann machine, genetic algorithm and space alternating generalized EM (SAGE) receiver are implemented and results are given for much larger scale problems. Simulation results show that these and several other of the proposed methods can significantly outperform the decision feedback detector or its group counterpart.

Binary quadratic programming (BQP) problems arise frequently in digital communication systems where online solutions are required. The multiuser detection (MUD) problem in code division multiple access (CDMA) communications, studied in the paper, is one such example. Due to the NP-hard nature of the BQP problem arising in MUD, only sub-optimal methods with polynomial complexities can be realistically considered. In the paper, a suboptimal algorithm based on the idea of probabilistic data association (PDA) is proposed. By treating the detection parameters as binary random variables, and by approximating the multi-modal Gaussian mixture by a single Gaussian noise, the PDA method provides near-optimal solution with a computational complexity of O(N/sup 3/), where N is the problem size. Several other algorithms for the MUD problem are also considered and compared in terms of computational efficiency and the degree of suboptimality.

A class of coordinate descent methods is proposed for the joint detection of binary symbols of K users in a synchronous correlated waveform multiple-access (CWMA) channel with Gaussian noise. We consider the detection problem as one of optimizing a quadratic objective function with binary constraints on decision variables. The proposed coordinate descent methods, while still maintaining a low computational complexity, are shown to provide as much as two orders of magnitude improvement in the probability of error, especially in situations where the existing methods do not perform well. The paper concludes with a discussion of how the proposed methods can be further improved.

Presents a classification of the optimization problems arising in the normative design of organizations to execute specific missions. The use of specific optimization algorithms for different phases of the design process leads to an efficient matching between the mission structure and that of an organization and its resources/constraints. It allows an analyst to obtain an acceptable trade-off among multiple objectives and constraints, as well as between computational complexity and solution efficiency (desired degree of sub-optimality).

Conventional blind signal separation algorithms do not adopt any asymmetric information of the input sources, thus the convergence point of a single output is always unpredictable. However, in most of the applications, we are usually interested in only one or two of the source signals and prior information is almost always available. In this paper, a principal independent component analysis (PICA) concept is proposed.We try to extract the objective independent component directly without separating all the signals. A cumulant-based globally convergent algorithm is presented and simulation results are given to show the hopeful applicability of the PICA ideas.