The reliability function of a channel is the maximum achievable exponential rate of decay of the error probability as a function of the transmission rate. In this work, we derive bounds on the reliability function of discrete memoryless multiple-access channels (MAC) with noiseless feedback. We show that our bounds are tight for a variety of MACs, such as m-ary additive and two independent point-to-point channels. The bounds are expressed in terms of a new information measure called “variable-length directed information”. The outer bound is proved by analyzing stochastic processes defined based on the entropy of the message, given the past channel’s outputs. Our method relies on tools from the theory of martingales, variable-length information measures, and a new technique called time pruning. We further propose a variable-length achievable scheme consisting of three phases: (i) data transmission, (ii) hybrid data-confirmation, and (iii) full confirmation. We show that two-phase-type schemes are strictly suboptimal in achieving the MAC’s reliability function. Moreover, we study the shape of the lower-bound and show that it increases linearly with respect to a specific Euclidean distance measure defined between the transmission rate pair and the capacity boundary. As side results, we derive an outer bound on the capacity of MAC with noiseless feedback and study a new problem involving a hybrid of hypothesis testing and data transmission.

Although feedback cannot increase the channel capacity of memoryless channels, it can enhance the error rate performance and/or shorten the codeword length for the target performance. This work is based on an early work by Viterbi in 1965 that utilizes instantaneous feedback for reliable uncoded communications. We build on this work by incorporating convolutional codes as a new variable-symbol-length digital communication scheme using instantaneous feedback. In the proposed system, called Opportunistic Symbol Length Adaptation (OSLA), the symbol length opportunistically adapts to the noise realization observed within a sub-symbol interval to minimize the packet/codeword error rate. It is shown that the proposed OSLA scheme combined with tail-biting convolutional codes or turbo codes outperforms state-of-the-art non-feedback codes as well as a deep learning-based feedback scheme with up to 1.5 dB gain in noiseless and noisy feedback channels.

As a class of state-dependent channels, Markov channels have been long studied in information theory for characterizing the feedback capacity and error exponent. This paper studies a more general variant of such channels where the state evolves via a general stochastic process, not necessarily Markov or ergodic. The states are assumed to be unknown to the transmitter and the receiver, but the underlying probability distributions are known. For this setup, we derive an upper bound on the feedback error exponent and the feedback capacity with variable length codes (VLCs). The bounds are expressed in terms of the directed mutual information and directed relative entropy. The bounds on the error exponent reduce to Burnashev’s expression for discrete memoryless channels. Our method relies on tools from the theory of martingales to analyze a stochastic process defined based on the entropy of the message given the past channel’s outputs.

It is well known that although feedback cannot increase the channel capacity of memoryless channels, it can enhance reliability or shorten codeword length. This work is based on an early result by Viterbi in 1965 that utilizes instantaneous feedback for reliable communications. We build on this work by incorporating (tail-biting) convolutional codes and designing a system where the decoder interacts with the transmitter by sending feedback during the decoding process. The proposed system is called Opportunistic Symbol Length Adaptation (OSLA), in which the symbol length opportunistically adapts to noise realization of each symbol to ensure that the target reliability is achieved. It is shown that, combined with tail-biting convolutional codes, the proposed scheme outperforms state-of-the-art non-feedback codes, as well as a recently proposed deep learning-based feedback scheme with up to 1.5 dB gain in noise-less and noisy feedback channels.

We consider the problem of decentralized sequential active hypothesis testing (DSAHT), where two transmitting agents, each possessing a private message, are actively helping a third agent-and each other-to learn the message pair over a discrete memoryless multiple access channel (DM-MAC). The third agent (receiver) observes the noisy channel output, which is also available to the transmitting agents via noiseless feedback. We formulate this problem as a decentralized dynamic team, show that optimal transmission policies have a time-invariant domain, and characterize the solution through a dynamic program. Several alternative formulations are discussed involving time-homogenous cost functions and/or variable-length codes, resulting in solutions described through fixed-point, Bellman-type equations. Subsequently, we make connections with the problem of simplifying the multi-letter capacity expressions for the noiseless feedback capacity of the DM-MAC. We show that restricting attention to distributions induced by optimal transmission schemes for the DSAHT problem, without loss of optimality, transforms the capacity expression, so that it can be thought of as the average reward received by an appropriately defined stochastic dynamical system with time-invariant state space.

We derive a lower and upper bounds on the reliability function of discrete memoryless multiple-access channel (MAC) with noiseless feedback and variable-length codes (VLCs). For the upper-bound, we use proof techniques of Burnashev for the point-to-point case. Also, we adopt the techniques used to prove the converse for the feedback-capacity of MAC. For the lower-bound on the error exponent, we present a coding scheme consisting of a data and a confirmation stage. In the data stage, any arbitrary feedback capacity-achieving code is used. In the confirmation stage, each transmitter sends one bit of information to the receiver using a pair of codebooks of size two, one for each transmitter. The codewords at this stage are selected randomly according to an appropriately optimized joint probability distribution. The bounds increase linearly with respect to a specific Euclidean distance measure defined between the transmission rate pair and the capacity boundary. The lower and upper bounds match for a class of MACs.

The reliability function of memoryless channels with noiseless feedback and variable-length coding has been found to be a linear function of the average rate in the classic work of Burnashev. In this work we consider unifilar channels with noiseless feedback and study specific transmission schemes, the performance of which provides lower bounds for the channel reliability function. In unifilar channels the channel state evolves in a deterministic fashion based on the previous state, input, and output, and is known to the transmitter but is unknown to the receiver. We consider a two-stage transmission scheme. In the first stage, both transmitter and receiver summarize their common information in an M-dimensional vector with elements in the state space of the unifilar channel and an M-dimensional probability mass function, with M being the number of messages. The second stage, which is entered when one of the messages is sufficiently reliable, is resolving a binary hypothesis testing problem. The analysis assumes the presence of some common randomness shared by the transmitter and receiver, and is based on the study of the log-likelihood ratio of the transmitted message posterior belief, and in particular on the study of its multistep drift. Simulation results confirm that the bounds are tight compared to the upper bounds derived in a companion paper.

Mechanism design for incentivizing strategic agents to maximize their sum of utilities (SoU) is a well-studied problem in the context of resource allocation in networks. There are, however, a number of network resource allocation problems of interest where a designer may have a different objective than maximization of the SoU. The obvious reason for seeking a different objective is that this notion of efficiency does not account for fairness of allocation. A second, more subtle, reason for demanding fairer allocation is that it indirectly implies less variation in taxes paid by agents. This is desirable in a situation where implicit individual agent budgetary constraints make payment of large taxes unrealistic. In this paper, we study a family of social utilities that provide fair allocation (with SoU being subsumed as an extreme case) and derive conditions under which Bayesian and dominant strategy implementation is possible. Furthermore, it is shown how a modification of the above-mentioned mechanism by adding just one message per agent can guarantee full Bayesian implementation, i.e., no extraneous equilibria. We consider the problem of demand-side management in smart grids as a specific motivating application, and through numerical analysis, it is demonstrated that in this application, the proposed method can result in significant gains in fairness of allocation and a reduction in tax variation among agents.

The trapdoor channel is a binary input/output/state channel with state changing deterministically as the modulo-2 sum of the current input, output and state. At each state, it behaves as one of two Z channels, each with crossover probability 1/2. Permuter et al. formulated the problem of finding the capacity of the trapdoor channel with feedback as a stochastic control problem. By solving the corresponding Bellman fixed-point equation, they showed that the capacity equals equation. In this paper, we consider the chemical channel, which is a generalization of the trapdoor channel, whereby at each state the corresponding Z channel has crossover probability p. We characterize the capacity of this problem as the solution of a Bellman fixed-point equation corresponding to a Markov decision process (MDP). Numerical solution of this fixed-point equation reveals an unexpected behavior, that is, for a range of crossover probabilities, the capacity seems to be constant. Our main contribution is to formalize and prove this observation. In particular, by explicitly solving the Bellman equation, we show the existence of an interval [0.5, p*] over which the capacity remains constant. To the authors' knowledge, this is the only known channel for which such behavior is observed.

Shayevitz and Feder proposed a capacity-achieving sequential transmission scheme for memoryless channels called posterior matching (PM). The proof of capacity achievability of PM is involved and requires invertibility of the PM kernel (also referred to as one-step invertibility). Recent work by the same authors provided a simpler proof but still requires PM kernel invertibility.

In this paper we consider the scenario of unicast service on the Internet where a network operator wishes to allocate rates among strategic users in a way that maximizes overall user satisfaction while respecting capacity constraints on every link in the network. In particular, we construct two mechanisms that fully implement social welfare maximizing allocation in Nash equilibria (NE) for the above scenario when agents' utilities are their private information. The emphasis of this work is on full implementation, which means that all NE of the induced game result in the optimal allocation of the centralized allocation problem, and thus no extraneous/ unwanted equilibria are created, as is the case in general mechanism design. The constructed mechanisms are amenable to learning, an essential requirement when using NE as a solution concept. This is achieved by ensuring that they result in feasible allocations on and off equilibrium and are budget balanced.

The problem of bounding the reliability function of a multiple access channel (MAC) is studied. Two new upper bounds on the error exponent of a two-user discrete memoryless (DM)-MAC are derived. The first bound (sphere packing) is an upper bound on the exponent of the average probability of error and is the first bound of this type that is zero outside the capacity region and thus results in a tighter sphere-packing exponent when compared with the tightest known exponent derived by Haroutunian. The second bound (minimum distance) is an upper bound on the exponent of the maximal (as opposed to average) probability of error. To obtain this bound, first, an upper bound on the minimum Bhattacharyya distance between codeword pairs is derived. For a certain class of two-user DM-MACs, an upper bound on the exponent of maximal probability of error is derived as a consequence of the upper bound on the minimum Bhattacharyya distance. We analytically evaluate the sphere packing bound for uniform composition codes for an additive and nonsymmetric channel and show that it is tight near the boundary of the capacity region, i.e., equal to the random coding lower bound.

For the discrete memoryless (DM) multiple access channel (MAC) with noiseless feedback Cover and Leung (CL) provided an achievable region that was later shown by Willems to be the capacity region for a special class of channels.

This paper studies node cooperation in a wireless network from the MAC layer perspective. A simple relay channel with a source, a relay, and a destination node is considered where the source can transmit a packet directly to the destination or transmit through the relay. The tradeoff between average energy and delay is studied by posing the problem as a stochastic dynamical optimization problem. The following two cases are considered: 1) nodes are cooperative and information is decentralized, and 2) nodes are strategic and information is centralized. With decentralized information and cooperative nodes, a structural result is proven that the optimal policy is the solution of a Bellman-type fixed-point equation over a time invariant state space. For specific cost functions reflecting transmission energy consumption and average delay, numerical results are presented showing that a policy found by solving this fixed-point equation outperforms conventionally used time-division multiple access (TDMA) and random access (RA) policies. When nodes are strategic and information is common knowledge, it is shown that cooperation can be induced by exchange of payments between the nodes, imposed by the network designer such that the socially optimal Markov policy corresponding to the centralized solution is the unique subgame perfect equilibrium of the resulting dynamic game.

A unified approach is presented for the derivation of reliability function lower bounds for the two-user discrete memoryless (DM) multiple-access channel (MAC). In particular, three lower bounds are presented. The first one (random coding) is identical to the best known lower bound on the reliability function of DM-MACs. It is shown that the random coding bound characterizes the performance of the average code in the constant-type code ensemble. The second bound (typical random coding) characterizes the typical performance (the performance of a high probability subset of the ensemble) of the constant-type code ensemble. To derive the third bound (expurgated), we eliminate some of the codewords from each of the codebooks. This is the first bound of this type that explicitly uses the method of expurgation for DM-MACs. It is shown that the exponent of the typical random coding and the expurgated bounds are greater than or equal to the exponent of the known random coding bounds for all rate pairs. Moreover, an example is given where the exponent of the expurgated bound is strictly larger for a certain input distribution. Each of the presented bounds is universal in the sense that there exists a code that attains the bound for all channels with given input and output alphabets. The approach presented for the DM-MAC is first demonstrated for the point-to-point discrete memoryless channel (DMC), by rederiving the random coding and expurgated exponents, and deriving a bound that characterizes the typical performance of the constant-type code ensemble.

In this paper, we study different schemes to parallelize trellis algorithms for efficient implementation on a GPU. We consider parallelization schemes at the packet-level, subblock-level and trellis-level to increase the number of threads in a GPU implementation. At the trellis-level, we consider state-level, forward-backward traversal and branch-metric parallelism. To evaluate the performance of the different schemes, an LTE uplink Turbo decoder is implemented on an NVIDIA GTX470 GPU. Tradeoffs between throughput, latency and bit error rate are presented. Our most balanced configuration is simultaneously processing multiple subblocks in a packet in conjunction with recovery schemes and trellis-level parallelism, which can achieve a throughput of 19.65 Mbps with a latency of 0.56 ms at bit error rate of 10-5for 1.3 dB channel SNR. We also show how different combinations of parallelization schemes can be used to satisfy systems with widely varying requirements of throughput, latency and bit error rate.

We consider the problem of communication over a multiple access channel (MAC) with noiseless feedback. A single-letter characterization of the capacity of this channel is not currently known in general. We formulate the MAC with feedback capacity problem as a stochastic control problem for a special class of channels for which the capacity is known to be the single-letter expression given by Cover and Leung. This approach has been recently successful in finding channel capacity for point-to-point channels with noiseless feedback but has not yet been fruitful in the study of multi-user communication systems. Our interpretation provides an understanding of the role of auxiliary random variables and can also hint at on-line capacity-achieving transmission schemes.

The capacity of unifilar finite-state channels with feedback has been recently derived in the form of a single-letter expression and it has been evaluated analytically for a number of channels of interest, such as the trapdoor channel and the Ising channel with feedback. In this paper, we investigate transmission schemes for this class of channels. These schemes are inspired by the posterior matching scheme (PMS) introduced for memoryless channels with feedback. The transmission scheme is proven to achieve zero rate and is conjectured to achieve channel capacity.

In wireless communication systems, users with heterogeneous information content constrain the network by having different reliability requirements. In this paper an information-theoretic framework is proposed to study communication systems which provide heterogeneous reliabilities for the users. This is done by defining individual probabilities of error for the users in the network and obtaining their fundamental tradeoffs. Using this framework, a system can be realized, which can provide a tradeoff of reliabilities among the users for a fixed vector of users' rates. This adds a completely new dimension to the performance tradeoff in such networks, which is beyond what is given by the conventional performance versus rate tradeoff in single-user systems. Although this is a very general concept and can be applied to any multi-terminal communication system, in this paper we consider multiple-input multiple-output (MIMO) fading broadcast channel. In particular, we quantify the reliability tradeoff by introducing the notion of diversity gain region (DGR), which specifies the set of diversity gain vectors that are simultaneously achievable by the users for a fixed vector of users' multiplexing gains. We show the existence of a tradeoff among the users' diversity gains by deriving inner and outer bounds for the DGR.

For a memoryless channel, although feedback cannot increase capacity, it can reduce the complexity and/or improve the error performance of a communication system. Recently, Shayevitz and Feder proposed the posterior matching scheme (PMS) which is a simple recursive transmission scheme that achieves the capacity of memoryless channels with feedback. Furthermore, Coleman provided a Lyapunov function approach to prove capacity achievability of the PMS. In this paper, we investigate a capacity-achieving PMS for the case of finite-state channels (FSCs). We first derive a single-letter expression for the capacity of the FSC with delayed output and state feedback by formulating the problem in a stochastic control framework. The resulting capacity expression can be evaluated using dynamic programming. We then propose a simple recursive PMS-like transmission scheme. To prove capacity achievability of the proposed PMS, we identify an appropriate Markov chain induced by the PMS.

Let X and Y be finite alphabets and PXYa joint distribution over them, with PXand PYrepresenting the marginals. For any ϵ > 0, the set of n-length sequences xnand ynthat are jointly typical according to PXYcan be represented on a bipartite graph. We present a formal definition of such a graph, known as a typicality graph, and study some of its properties. These properties arise in the study of several multiuser communication problems.

In this paper, the existence of capacity-achieving codes for memoryless binary-input output-symmetric (MBIOS) channels under maximum-likelihood (ML) decoding with bounded graphical complexity is investigated. Graphical complexity of a code is defined as the number of edges in the graphical representation of the code per information bit and is proportional to the decoding complexity per information bit per iteration under iterative decoding. Irregular repeat-accumulate (IRA) codes are studied first. Utilizing the asymptotic average weight distribution (AAWD) of these codes and invoking Divsalar's bound on the binary-input additive white Gaussian noise (BIAWGN) channel, it is shown that simple nonsystematic IRA ensembles outperform systematic IRA and regular low-density parity-check (LDPC) ensembles with the same graphical complexity, and are at most 0.124 dB away from the Shannon limit. However, a conclusive result as to whether these nonsystematic IRA codes can really achieve capacity cannot be reached. Motivated by this inconclusive result, a new family of codes is proposed, called low-density parity-check and generator matrix (LDPC-GM) codes, which are serially concatenated codes with an outer LDPC code and an inner low-density generator matrix (LDGM) code. It is shown that these codes can achieve capacity on any MBIOS channel using ML decoding and also achieve capacity on any BEC using belief propagation (BP) decoding, both with bounded graphical complexity. Moreover, it is shown that, under certain conditions, these capacity-achieving codes have linearly increasing minimum distances and achieve the asymptotic Gilbert–Varshamov bound for all rates.

Codes on sparse graphs have been shown to achieve remarkable performance in point-to-point channels with low decoding complexity. Most of the results in this area are based on experimental evidence and/or approximate analysis. The question of whether codes on sparse graphs can achieve the capacity of noisy channels with iterative decoding is still open, and has only been conclusively and positively answered for the binary erasure channel. On the other hand, codes on sparse graphs have been proven to achieve the capacity of memoryless, binary-input, output-symmetric channels with finite graphical complexity per information bit when maximum likelihood (ML) decoding is performed. In this paper, we consider transmission over finite-state channels (FSCs). We derive upper bounds on the average error probability of code ensembles with ML decoding. Based on these bounds we show that codes on sparse graphs can achieve the symmetric information rate (SIR) of FSCs, which is the maximum achievable rate with independently and uniformly distributed input sequences. In order to achieve rates beyond the SIR, we consider a simple quantization scheme that when applied to ensembles of codes on sparse graphs induces a Markov distribution on the transmitted sequence. By deriving average error probability bounds for these quantized code ensembles, we prove that they can achieve the information rates corresponding to the induced Markov distribution, and thus approach the FSC capacity.

The problem of bounding the reliability function of a multiple-access channel (MAC) is studied. An upper bound on the minimum Bhattacharyya distance between codeword pairs is derived. For a certain large class of two-user discrete memoryless (DM) MAC, a lower bound on the maximal probability of decoding error is derived as a consequence of the upper bound on Bhattacharyya distance. Further, an upper bound on the average probability of decoding error is studied. It is shown that the corresponding upper and lower bounds have a similar structure. Using a conjecture about the structure of the multi-user code, a tighter lower bound for the maximal probability of decoding error is derived and is shown to be tight at zero rates.

Codes on sparse graphs have been shown to achieve remarkable performance in point-to-point channels with low decoding complexity. Most of the results in this area are based on experimental evidence and/or approximate analysis. The question of whether codes on sparse graphs can achieve the capacity of noisy channels with iterative decoding is still open, and has only been conclusively and positively answered for the binary erasure channel. On the other hand, codes on sparse graphs have been proven to achieve the capacity of memoryless, binary-input, output-symmetric channels with finite graphical complexity per information bit when maximum likelihood (ML) decoding is performed. In this paper, we consider transmission over finite-state channels (FSCs). We derive upper bounds on the average error probability of code ensembles with ML decoding. Based on these bounds we show that codes on sparse graphs can achieve the symmetric information rate (SIR) of FSCs, which is the maximum achievable rate with independently and uniformly distributed input sequences. In order to achieve rates beyond the SIR, we consider a simple quantization scheme that when applied to ensembles of codes on sparse graphs induces a Markov distribution on the transmitted sequence. By deriving average error probability bounds for these quantized code ensembles, we prove that they can achieve the information rates corresponding to the induced Markov distribution, and thus approach the FSC capacity.

Automatic repeat request (ARQ) protocols are utilized as a flexible way to adapt data transmission to channel variations whenever a feedback channel is available. The transmitter encodes the information into a packet and the receiver attempts to decode it. If decoding is not successful, the receiver signals the transmitter to either resend the same information or send additional information about the data. In this paper we consider ARQ protocols where the transmitter controls the amount of error correction capability introduced in the information sequence to minimize the expected delay. We formulate this problem as a stochastic control problem and study two cases of interest depending on whether or not the receiver feeds back information about the channel state. Some of the benefits of this formulation are an expression for the optimal packet size and delay as a solution of a fixed point equation and a unified treatment for channels with Markov statistics and for receivers with memory.

In this work, a new lower bound for the maximal error probability of a two-user discrete memoryless (DM) multiple-access channel (MAC) is derived. This is the first bound of this type that explicitly imposes independence of the userspsila input distributions (conditioned on the time-sharing auxiliary variable) and thus results in a tighter sphere-packing exponent when compared to the tightest known exponent derived by Haroutunian.

The performance of punctured low-definition parity-check (LDPC) codes under maximum-likelihood (ML) decoding is studied in this correspondence via deriving and analyzing their average weight distributions (AWDs) and the corresponding asymptotic growth rate of the AWDs. In particular, it is proved that capacity-achieving codes of any rate and for any memoryless binary-input output-symmetric (MBIOS) channel under ML decoding can be constructed by puncturing some original LDPC code with small enough rate. Moreover, it is shown that the gap to capacity of all the punctured codes can be the same as the original code with a small enough rate. Conditions under which puncturing results in no rate loss with asymptotically high probability are also given in the process. These results show high potential for puncturing to be used in designing capacity-achieving codes, and in rate-compatible coding under any MBIOS channel.

In modern communication systems, different users have different requirements for quality of service (QoS). In this work, QoS refers to the average codeword error probability experienced by the users in the network. Although several practical schemes (collectively referred to as unequal error protection schemes) have been studied in the literature and are implemented in existing systems, the corresponding performance limits have not been studied in an information-theoretic framework.

In this paper the tradeoff between energy and delay for wireless networks is studied. A network using a request-to-send (RTS) and clear-to-send (CTS) type medium access control (MAC) protocol is considered. A generic framework is developed that allows us to obtain the joint statistics of energy and delay through their joint generating function, when the effects of an imperfect channel are incorporated in the model. Several energy and delay tradeoffs are studied using the joint generating function. These include the average energy vs. average delay, average delay with energy constraint, etc. The proposed analytical method is verified through simulations.

Asymptotic analysis of low-density parity-check (LDPC) code weight and stopping-set enumerators, for codewords and stopping sets which grow linearly with codelength, has aided in designing codes with linear minimum distance and low error floors. However, the analysis cannot capture the behavior of codewords and stopping sets that grow sublinearly with codelength. Thus, it is unclear how well the analysis describes behavior for finite codelengths, particularly for short codes. In this paper, we provide another perspective on protograph-based and standard LDPC ensemble enumerators, based on analysis of stopping sets with sublinear growth, which brings new insight into sublinear stopping-set behavior, protograph structure, and preceding. Using approximations to the stopping-set enumerators, we show that for stopping sets that grow at most logarithmically with codelength, the enumerators follow a polynomial relationship with codelength, unlike the exponential relationship for linearly- growing stopping sets. Further, we analyze for what stopping-set sizes and codelengths the approximations apply.

In this paper, we present an overview on the design of algorithms for iterative detection over channels with memory. The starting point for all the algorithms is the implementation of soft-input soft-ouput maximum a posteriori (MAP) symbol detection strategies for transmissions over channels encompassing unknown parameters, either stochastic or deterministic. The proposed solutions represent effective ways to reach this goal. The described algorithms are grouped into three categories: i) we first introduce algorithms for adaptive iterative detection, where the unknown channel parameters are explicitly estimated; ii) then, we consider finite-memory iterative detection algorithms, based on ad hoc truncation of the channel memory and often interpretable as based on an implicit estimation of the channel parameters; and iii) finally, we present a general detection-theoretic approach to derive optimal detection algorithms with polynomial complexity. A few illustrative numerical results are also presented.

The problem of sequence detection in frequency-nonselective/time-selective fading channels, when channel state information (CSI) is not available at the transmitter and receiver, is considered in this paper. The traditional belief is that exact maximum-likelihood sequence detection (MLSD) of an uncoded sequence over this channel has exponential complexity in the channel coherence time. Thus, for slowly varying channels, i.e., channels having coherence time on the order of the sequence length, the complexity appears to be exponential in the sequence length. In the first part of this work, it is shown that exact MLSD can be computed with only polynomial worst case complexity in the sequence length regardless of the operating signal-to-noise ratio (SNR) for equal-energy signal constellations. By establishing a relationship between the aforementioned complexity and the rank of the correlation matrix of the fading process, an understanding of how complexity of the optimal MLSD receiver varies as the channel dynamics change is provided. In the second part of this paper, the problem of decoding turbo-like codes in frequency-nonselective/time-selective fading channels without receiver CSI is examined. Using arguments similar to the ones used for the MLSD case, it is shown that the exact symbol-by-symbol soft-decision metrics (SbSSDMs) implied by the min-sum algorithm can be evaluated with polynomial worst case complexity in the sequence length regardless of SNR for equal-energy signal constellations. Finally, by simplifying some key steps in the polynomial-complexity algorithm, a family of fast, approximate algorithms is derived, which yield near-optimal performance

In this paper, the average input-parity weight enumerator (AIPWE) of regular/irregular repeat-accumulate (RA) ensembles is derived, by viewing an RA code as a serial concatenation of an outer low-density generator matrix (LDGM) code and an inner accumulator. The exact average weight distribution (AWD) of the systematic and nonsystematic versions of the RA ensembles are then obtained from their AIPWE's. We further derive the asymptotic growth exponent of the AWD's, which are then used to bound the ensemble performance under maximum likelihood (ML) decoding. It is shown that simple nonsystematic regular RA ensembles outperform systematic regular RA and regular low-density parity-check (LDPC) ensembles and have distance spectrum which closely resembles that of the random ensemble.

The problem of joint data detection and frequency/phase estimation is considered in this paper. The traditional belief regarding exact generalized-likelihood-based joint detection and estimation is that its complexity is exponential in the sequence length N. This belief is justified due to the memory imposed on the transmitted sequence by the lack of knowledge of the auxiliary channel parameters. In this paper, we show that the exact solution can be performed with O(N/sup 4/) worst case complexity regardless of the operating signal-to-noise ratio. The concepts used in the proof of the polynomial complexity result are also utilized to evaluate tight performance bounds on the exact and a family of approximate algorithms.

This paper deals with the design of coding/modulation and demodulation/decoding schemes for single- or multiple-antenna systems with focus on fast-fading channels, where channel state information (CSI) is not available at the transmitter and the receiver. We explore two possible solutions for this channel with increasing degree of sophistication. The first one utilizes pilots at the transmitter and a simple and explicit noniterative channel estimation algorithm at the receiver. We show that this pilot-assisted system is exactly equivalent, in terms of performance analysis and design, to an appropriately "degraded" system having perfect CSI at the receiver. The second scheme utilizes pilots and a family of well-justified and simple suboptimal iterative detection/estimation algorithms. It is shown that when turbo-like codes are considered in conjunction with this pilot-assisted transmission scheme and the proposed receiver algorithm, the unitary constellations investigated in the literature are inferior to simple pilot-assisted constellations in both complexity and performance. Specific instances of the proposed systems (that use optimized irregular low-density parity-check outer codes) are designed. The design examples provided show that the proposed systems can achieve a good tradeoff between complexity and performance and can be used to bridge the gap between the high complexity/high-performance optimal scheme and low-complexity/mediocre performance noniterative estimation/coherent detection scheme.

Communication over the noncoherent additive white Gaussian noise (AWGN) channel is considered, where the transmitted signal undergoes a phase rotation, unknown to the transmitter and the receiver. The effects of phase dynamics are explicitly taken into account by considering a block-independent model for the phase process: the unknown phase is constant for a block of N complex symbols and independent from block to block. In the first part of the paper, the capacity-achieving input distribution is characterized. In particular, it is shown that the maximizing density has circular symmetry, is discrete in amplitude with infinite number of mass points, and always has a mass point at zero. Furthermore, asymptotic expressions and bounds for the capacity are derived. Based on these results, the capacity is evaluated through numerical optimizations for unconstrained and modulation-constrained input distributions. In the second part of this paper, inspired by the capacity results, two classes of coding and modulation schemes are proposed for fast and moderate phase dynamics. In the case of fast phase dynamics (i.e., small N), optimized modulation alphabets are designed having exponential complexity with N at the demodulator. In the case of moderate phase dynamics (i.e., moderate values of N), specially designed modulation alphabets are utilized that have linear complexity with N. These alphabets are used together with optimized irregular low-density parity-check (LDPC) codes. Simulation results show that these codes can achieve close-to-capacity performance with moderate complexity, and outperform the best known codes so far.

Pilot-symbol-assisted (PSA) low-density parity-check (LDPC) codes are analyzed using density evolution techniques for a frequency-nonselective, time-selective fading channel where the fading affects both the amplitude and the phase of the transmitted signal. The performance of several message-passing estimation/decoding receivers is investigated, and the optimal energy allocation between pilot and coded symbols is evaluated. Several message-passing estimation/decoding receivers are shown to fall under a single unifying description which leads to significant simplification of the analysis and design of the PSA LDPC codes and receivers. The immediate surprising result is that for the described class of receivers, the best codes for the case of perfect channel state information (CSI) at the receiver are also the best codes when no CSI is available at the receiver, regardless of the channel dynamics. A class of more elaborate receivers that perform iterative joint decoding/estimation is also presented and it is shown that codes designed specifically for these receivers provide an additional performance gain.

In this work, we investigate the tradeoff between energy and delay for wireless networks utilizing the IEEE 802.11 standard for medium access control. The proposed analysis provides the joint distribution of the energy and delay of a transmitted data packet, which is then used to evaluate the corresponding average values. Our analysis takes into account the effect of the channel noise on the transmission of the RTS, CTS, data, and ACK packets. Furthermore, channel coding is incorporated in the analysis by estimating the packet error probability using error-exponent-based bounds under a memoryless channel. Using these analysis tools, the code rate and the signal-to-noise ratio per dimension are optimized to achieve minimum average delay per information bit.

The problem of joint data detection and frequency/phase estimation is considered in this work. The traditional belief regarding exact generalized-likelihood-based joint detection and estimation is that its complexity is exponential in the sequence length N. This belief is justified due to the memory imposed on the transmitted sequence by the lack of knowledge of the auxiliary channel parameters. In this paper, we show that the exact solution can be performed with O(N/sup 5/) worst-case complexity regardless of the operating signal-to-noise ratio. In addition, based on the exact solution, we propose an approximate algorithm with O(N/sup 3/) complexity and demonstrate its performance through simulations.

The problem of optimal decoding of a trellis coded sequence transmitted over a frequency nonselective, time-selective fading channel is considered in this paper. In particular, the case where the channel state information (CSI) is unknown to the receiver, thus Viterbi's algorithm (VA) can not be employed to find the maximum a posteriori probability sequence detection (MAPSqD) solution with linear complexity in sequence length N. It is proved that for two-state trellis, the exact solution can indeed be obtained with only polynomial complexity in N for any signal-to-noise ratio.

In this paper, we derive an inner bound (achievable region) and an outer bound for the error exponent region of a Gaussian multiple access channels (GMAC). We define a probability of error for each user, which, in general may be different for different users. Therefore, there are multiple error exponents, one for each user, for a given multiuser channel.

In this work, we introduce the notion of the diversity gain region for a multiuser channel. This region specifies the set of diversity-gain vectors that are simultaneously achievable by all users in the multiuser channel. This is done by associating different probabilities of error for different users, contrary to the traditional approach where a single probability of system error is considered. We derive an inner bound (achievable region) and an outer bound for the diversity gain region of a MIMO fading broadcast channel.

Transmission over the noncoherent additive white Gaussian noise channel is considered, where the transmitted signal undergoes a phase rotation, unknown to the transmitter and the receiver. The effects of phase dynamics are explicitly taken into account by considering a block-independent model for the phase process: the unknown phase is constant for a block of N complex symbols and independent from block to block. In the first part of the paper, a summary of the analytic results on related work regarding the capacity achieving input distribution is presented, followed by some numerical and asymptotic results. In the second part of this paper, inspired by the capacity results, two classes of coding and modulation schemes are proposed for fast and moderate phase dynamics. Due to the complexity issues, these two cases are treated separately. In the first case, serially concatenated turbo codes are utilized, while in the second, irregular low-density parity-check codes are used in conjunction with channel-matched modulation schemes. Simulation results show that these codes can achieve close-to-capacity performance with moderate complexity, and outperform the best known codes so far.

The related problems of maximum likelihood sequence detection (MLSD) and symbol-by-symbol soft-decision metric (SbSSDM) generation in complex Gaussian flat-fading channels are considered in this paper. Traditional methods for the exact solution of these problems have exponential complexity with respect to the sequence length. In this paper, it is shown that both these problems can be solved in polynomial complexity with respect to the sequence length. Furthermore, motivated by the polynomial-complexity exact algorithm, an approximate fast algorithm is also derived. Simulation results for a low-density parity-check (LDPC) code transmitted on the aforementioned channel show that the performance of the approximate algorithm is very close to the exact sum-product algorithm.

A commonly used lower bound on the probability of error of joint detection and estimation (JDE) algorithms is derived under the assumption that estimation is performed using the transmitted sequence, in a genie-aided fashion. Although it seems reasonable that this genie-aided receiver performs better than the original receiver, a proof of this fact is not available in the literature. In this letter, the validity of this bound is established for a general class of JDE algorithms, as well as for an important special case when the maximum-likelihood sequence detection criterion is used. The results are then extended to a well-known suboptimal JDE algorithm, namely, the T-algorithm. It is shown, however, that the technique used to prove this bound is not sufficient for establishing the validity of the bound for the M-algorithm and the per-survivor processing algorithm.

The problem of generating symbol-by-symbol soft decision metrics (SbSSDMs) in the presence of unknown channel parameters is considered. The motivation for this work lies in its application to iterative decoding of high-performance turbo-like codes, transmitted over channels that introduce unknown parameters in addition to Gaussian noise. Traditional methods for the exact evaluation of SbSSDMs involve exponential complexity in the sequence length. A class of problems is identified for which the SbSSDMs can be exactly evaluated with only polynomial complexity with respect to the sequence length. Utilizing the close connection between symbol-by-symbol and sequence detection, it is also shown that for the aforementioned class of problems, detection of an uncoded data sequence in the presence of unknown parameters can be performed with polynomial complexity. The applicability of this technique is demonstrated by considering the problem of iterative detection of low-density parity-check codes in the presence of unknown and time-varying carrier-phase offset. Finally, based on the proposed exact schemes, an ultra-fast approximate algorithm for performing joint iterative decoding and phase estimation is derived that is well suited for hardware implementation.

In this paper, pilot-symbol-assisted transmission in conjunction with high-performance coding over the block-independent noncoherent additive white Gaussian noise channel is investigated. Several approximate iterative receivers are proposed, which either perform carrier-phase estimation separately from detection, or joint carrier-phase estimation/decoding in an iterative fashion. The performance of the proposed receivers is analyzed using density evolution. The power allocation to the pilot symbol is quantified, and it is shown that an optimal allocation scheme exists that minimizes the overall information bit signal-to-noise ratio required for error-free communication. This optimal power allocation, which could be utilized in code design, is found to be sensitive to the channel coherence interval, as well as to the particular receiver used. In addition, a simple upper bound on the performance of any receiver that performs joint iterative carrier-phase estimation and detection, is derived. The obtained results are compared with the simulated performance of the proposed receivers.

The paper investigates the design and robustness of rotationally invariant (RI) codes. First, RI codes are extended to the case of serially concatenated (SC) trellis-coded modulation (TCM) and several high-rate powerful RI-SCTCM codes are designed over 8-phase-shift keying and 16-quadrature amplitude modulation alphabets. The investigation continues by considering more realistic channels that introduce cycle slips during phase estimation, and thus rotate only part of the transmitted codeword. It is proven that RI codes with small state space are robust in these channels, even when traditional coherent decoders are utilized. Furthermore, it is demonstrated through simulations that the addition of a simple stopping criterion to the coherent iterative decoding algorithm is sufficient for robustness of the more powerful RI-SCTCM codes when partial codeword rotations are considered. Finally, it is investigated whether RI codes are useful for transmission in the noncoherent channel. It is proved that RI codes are as good as any other good codes for this channel when the phase dynamics are low, and optimal decoding is performed. However, it is shown that for a certain class of receivers, RI codes are also robust to partial phase rotations in this channel.

In this paper we consider iterative detection over bandpass channels which introduce an unknown phase rotation in the transmitted signal. We first introduce a unified formulation of adaptive forward-backward algorithms for channels with parametric uncertainty, including both recursive and non-recursive estimation strategies, and then apply this framework to a phase noncoherent channel. Two main classes of adaptive forward-backward algorithms are then considered and compared: closed-loop algorithms, which use explicit recursive phase estimation, and open-loop algorithms, which use implicit non-recursive phase estimation. We consider schemes with combined detection and decoding. Pilot symbols are inserted in order to cope with the unknown time-varying channel phase.

Low-density parity-check (LDPC) codes are analyzed using density evolution techniques for a frequency-nonselective, time-selective fading channel where the fading affects both the amplitude and the phase of the transmitted signal. To aid the channel estimation process, pilot symbols are transmitted periodically. The performance of several message-passing estimation/decoding algorithms is investigated, and the optimal energy allocation between the pilot and coded symbols is evaluated. The results show that optimal power allocation can improve the performance by more than 1 dB for moderate channel dynamics. Finally, necessary and sufficient conditions for the convergence to error-free transmission are derived that take into account the channel coherence time.

Iterative decoding in the presence of unknown channel parameters requires the generation of symbol-by-symbol soft-decision metrics (SbSSDMs), jointly with parameter estimation. Traditional methods for the exact evaluation of these metrics have exponential complexity with the length of the data sequence. In this paper, a class of problems is identified, for which the exact SbSSDMs can be obtained with only polynomial complexity with the data sequence length. The applicability of this technique is demonstrated by considering the problem of iterative detection of low-density parity-check codes in the presence of unknown and time-varying carrier-phase offset.

Pilot-symbol-assisted transmission of coded data over the block independent noncoherent AWGN channel is considered in this paper. Several iterative receivers are proposed and their performance is analyzed using density evolution. Upper and lower performance bounds are derived for the receiver based on the sum-product algorithm, and the optimal allocation of power to the pilots and coded bits is investigated. It is discovered that the optimal power allocation affects considerably the achievable performance, and depends highly on the phase dynamics. These results are verified by simulating practical codes and iterative receivers.

Recently, density evolution techniques have been used to predict the performance of iterative decoders utilizing the sum-product belief propagation algorithm. We extend this analysis to the min-sum algorithm for binary codes. Using two representative applications, i.e., low-density parity-check (LDPC) codes and repeat accumulate (RA) codes, the sum-product and min-sum algorithms are compared. The results demonstrate a performance degradation of 0.27-1.03 dB for the min-sum algorithm, which confirms earlier simulation results. However, it is shown that a small modification to the min-sum algorithm results in an approximate sum-product algorithm, which performs at least as well as the original sum-product algorithm when finite message precision is considered.

This paper deals with the analysis and design of rotationally invariant (RI) serially concatenated trellis coded modulation (SCTCM) over AWGN channels. Several powerful RI-SCTCM codes are designed which are close to the capacity limit of the modulation constrained channel. Invariance to partial phase rotations is also investigated. Although it is shown that standard (i.e., non-concatenated) TCM codes are provably robust to phase rotations that only affect part of the coded sequence, this property is demonstrated for SCTCM codes only through simulations. A number of experiments were run to verify the expected performance of the designed codes. High order constellations, like 8-PSK and 16-QAM are used to obtain overall throughput on the order of 2-3 bits per channel use.

The problem of performing iterative detection (ID)-a technique originally introduced for the decoding of turbo codes-for systems having parametric uncertainty has received relatively little attention in the open literature. In this paper, the problem of adaptive ID (AID) for serial and parallel concatenated convolutional codes (SCCCs and PCCCs or turbo codes) in the presence of carrier-phase uncertainty is examined. Based on the theoretical framework of Anastasopoulos and Chugg, (see Proc. Int. Conf. Communications, p.177-181, 1999). and Colavolpe, Ferrari and Raheli (see IEEE Trans. Commun., vol.48, p.1488-98, 2000), adaptive soft inverse (ASI) algorithms are developed for two commonly used blocks in turbo codes, leading to the adaptive soft-input soft-output (A-SISO) and the adaptive soft demodulator (A-SODEM) algorithms. Based on these algorithms, practical AID receivers are presented. Several design options are proposed and compared and the impact of parametric uncertainty on previously established results for iterative detection with perfect channel state information (CSI) is assessed.

Some issues with Forney's upper and lower bounds (1972) for the symbol error probability in systems with memory (e.g., intersymbol interference channels) have been pointed out in the literature. We expound on these issues. For the upper bound, we show that, although the most commonly cited proofs are not logically consistent, the bound is true for more general conditions. The reasoning leading to the lower bound is shown to be flawed and, in general,to lead to invalid lower bounds. We suggest a lower bound based on Mazo's bound (1975) as an alternative.

Several structures for fixed-lag (FL) soft-in/soft-out (SISO) algorithms in the case of a perfectly known channel are well-known. These forward-only and bi-directional fixed-lag SISOs have been described with the bi-directional version shown to be preferred. Adaptive iterative detection using adaptive SISOs (A-SISOs) have also been demonstrated to provide significant performance gains for time-varying channels. However, these impressive results have been obtained with fixed-interval, bi-directional A-SISOs and training signals at both ends of the data packet. We combine these results to develop and compare various adaptive, fixed-lag SISOs. Among several reasonable options considered, the preferred A-SISO algorithm is found to be bi-directional with forward-only channel estimation.

The soft-input soft-output (SISO) module is the basic building block for established iterative detection (ID) algorithms for a system consisting of a network of finite state machines. The problem of performing ID for systems having parametric uncertainty has received relatively little attention in the open literature. Previously proposed adaptive SISO (A-SISO) algorithms are either based on an oversimplified channel model, or have a complexity that grows exponentially with the observation length N (or the smoothing lag D). In this paper, the exact expressions for the soft metrics in the presence of parametric uncertainty modeled as a Gauss-Markov process are derived in a novel way that enables the decoupling of complexity and observation length. Starting from these expressions, a family of suboptimal (practical) algorithms is motivated, based on forward/backward adaptive processing with linear complexity in N. Previously proposed A-SISO algorithms, as well as existing adaptive hard decision algorithms are interpreted as special cases within this framework. Using a representative application-joint iterative equalization-decoding for trellis-based codes over frequency-selective channels-several design options are compared and the impact of parametric uncertainty on previously established results for ID with perfect channel state information is assessed.

The severity of frequency-selective fading channels necessitates the combining of multiple diversity sources to achieve acceptable performance. Traditional techniques often perform the combining of different sources of diversity separately, resulting in significant performance degradation. Algorithms for the joint optimal combining were reformulated in a form suitable for practical implementation. We investigate the applicability of these algorithms for the specific problem of interleaved TCM systems in frequency-selective fading channels with or without external diversity. It is demonstrated that soft decision equalization techniques are necessary and sufficient for the application of TCM techniques over such channels. In addition, it is shown that the design trade-offs associated with the resulting TCM techniques are significantly different than those associated with memoryless channels.

The design issues and the performance evaluation of packet radio communication systems for automated highway systems (AHS) are presented. The main focus is on the analysis and interaction between the physical and the link-access layers of a packet radio system that can accommodate communication between vehicles and roadside infrastructure as well as between vehicles. We discuss the information flow requirements of AVCS (advanced vehicle control systems) and ATMIS (advanced traffic management and information systems) services and we present preliminary results from the performance evaluation of four multiple access schemes (slotted-ALOHA, reservation-ALOHA, TDMA, and CDMA).