We study a problem where wireless service providers compete for heterogenous wireless users. The users differ in their utility functions as well as in the perceived quality of service of individual providers. We model the interaction of an arbitrary number of providers and users as a two-stage multi-leader-follower game. We prove existence and uniqueness of the subgame perfect Nash equilibrium for a generic channel model and a wide class of users' utility functions. We show that the competition of resource providers leads to a globally optimal outcome under mild technical conditions. Most users will purchase the resource from only one provider at the unique subgame perfect equilibrium. The number of users who connect to multiple providers at the equilibrium is always smaller than the number of providers. We also present a decentralized algorithm that globally converges to the unique system equilibrium with only local information under mild conditions on the update rates.

Digital video broadcasting (DVB-C2) and other modern communication standards increase diversity by means of a symbol-level interleaver that spans over several codewords. De-interleaving at the receiver requires a large memory, which has a significant impact on the implementation cost. In this paper, we propose a technique that reduces the de-interleaver memory size. By quantizing log-likelihood ratios with bit-specific quantizers and compressing the quantized output, we can significantly reduce the memory size with a negligible increase in computational complexity. Both the quantizer and compressor are designed via a GMI-based maximization procedure. For a typical DVB-C2 scenario, numerical results show that the proposed solution enables a memory saving up to 30%.

The asynchronous capacity region of memoryless multiple-access channels is the union of certain polytopes. It is well known that vertices of such polytopes may be approached via a technique called successive decoding. It is also known that an extension of successive decoding applies to the dominant face of such polytopes. The extension consists of forming groups of users in such a way that users within a group are decoded jointly whereas groups are decoded successively. This paper goes one step further. It is shown that successive decoding extends to every face of the aforementioned polytopes. The group composition as well as the decoding order for all rates on a face of interest is obtained from a label assigned to that face. From the label, one can extract a number of structural properties, such as the dimension of the corresponding face and whether or not two faces intersect. Expressions for the number of faces of any given dimension are also derived from the labels.

An analog source is to be transmitted across a Gaussian channel in more than one channel use per source symbol. This paper derives a lower bound on the asymptotic mean squared error for a strategy that consists of repeatedly quantizing the source, transmitting the quantizer outputs in the first channel uses, and sending the remaining quantization error uncoded in the last channel use. The bound coincides with the performance achieved by a suboptimal decoder studied by the authors in a previous paper, thereby establishing that the bound is tight.

We present and analyze a joint source-channel coding strategy for the transmission of a Gaussian source across a Gaussian channel in n channel uses per source symbol. Among all such strategies, the scheme presented here has the following properties: i) the resulting mean-squared error scales optimally with the signal-to-noise ratio, and ii) the scheme is easy to implement and the incurred delay is minimal, in the sense that a single source symbol is encoded at a time.

We consider source coding with a fidelity criterion, channel coding with a channel input constraint, and the combined problem of reproducing a source across a noisy channel. All three cases face a similar tradeoff between resource and performance, and the operating point with the highest performance per resource is of particular interest. In the case of channel coding, channel input cost is traded for rate, and the optimal tradeoff corresponds to the capacity per unit cost. We define equivalent notions for the other two cases and show how they relate. For each case we give necessary and sufficient conditions for the optimal tradeoff to be achieved.

In a remarkable paper published in 1976, Burnashev determined the reliability function of variable-length block codes over discrete memoryless channels (DMCs) with feedback. Subsequently, an alternativeachievabilityproof was obtained by Yamamoto and Itoh via a particularly simple and instructive scheme. Their idea is to alternate between a communication and a confirmation phase until the receiver detects the codeword used by the sender to acknowledge that the message is correct. We provide aconversethat parallels the Yamamoto-Itoh achievability construction. Besides being simpler than the original, the proposed converse suggests that a communication and a confirmation phase are implicit in any scheme for which the probability of error decreases with the largest possible exponent. The proposed converse also makes it intuitively clear why the terms that appear in Burnashev's exponent are necessary.

We study the behavior of users in a classical Additive White Gaussian Noise Multiple Access Channel. We model users as rational entities whose only interest is to maximize their own communication rate, and we model their interaction as a noncooperative one-shot game. The Nash equilibria of the two-user game are found, and the relation between the pure-strategy and mixed-strategy Nash equilibria is discussed. As in most games, the absence of cooperation and coordination leads to inefficiencies.We then extend our setting using evolutionary game theory, which we use to model a large population of users playing the MAC game over time. A unique evolutionary stable strategy is found for this case, corresponding to the strategy achieving the Nash equilibrium in a simplified one-shot game. Finally, we investigate what happens to the distribution of strategies in a population when we assume that the number of offsprings of a user is equal to the payoff of this user in a one-shot game. We find that the system converges to a state in which the average strategy of the population is the evolutionary stable strategy.

Feedback coupled with variable-length codes can substantially increase the reliability of a discrete memoryless channel (DMC). Burnashev, in a remarkable paper published in 1976, derived an asymptotically achievable lower bound to the average blocklength needed for a system that communicates at a specified rate and achieves a given error probability. We offer an alternative proof of the lower bound. Our proof is simpler than the original, and clarifies the roles of the quantites that appear in the bound by relating one to uncertainty reduction and the other to binary hypothesis testing. In addition, our derivation of the lower bound closely parallels a derivation of an upper bound by Yamamoto and Itoh.

A joint source channel coding scheme for binary (non necessarily symmetric) sources and binary symmetric channels with feedback is proposed and analyzed. IS is shown that the scheme performs optimally in the sense that the average number of channel uses per source symbol approaches the source entropy divided by the channel capacity. By taking advantage of obvious approximations, the scheme is implementable at low complexity and moderate latency. Simulation results show strong agreement between the performance of the analyzed optimal system and that of the low complexity implementation

This paper presents the implementation of a multiple antenna communication system using low-density parity-check (LDPC) codes on the software-defined radio (SDR) platform developed at EPFL's Mobile Communications Laboratory. After briefly presenting the general structure and the main capabilities of our SR platform, we describe the methods and algorithms used for designing, encoding and decoding the LDPC codes for MIMO (multiple input multiple output) systems. We have implemented MIMO LDPC systems with up to four transmit and four receive antennas and performed on-the-air measurements which show strong agreement with the theory.

It is well-known that the capacity region of an M-user Gaussian multiple access channel is an M-dimensional polytope and the capacity region of a general discrete memoryless multiple-access channel contains a union of such polytopes. An expression for the number of vertices, edges, and more generally faces of any dimension D, of the capacity region of a Gaussian multiple access channel is derived in this paper.

Feedback may greatly simplify the coding techniques needed to achieve the (information-theoretically) optimum performance. This is true both for the capacity problem and for the joint source-channel coding problem. We are interested in the latter. Gaussian examples involving feedback have appeared in the literature (Cruise, T.J., 1967; Kailath, T., 1967; Schalkwijk, J.P.M. and Bluestein, L.I., 1967). We present a general matching condition for source-channel communication with feedback, extending our previous results for the case without feedback (Gastpar, M. et al., Proc. IEEE Int. Symp. Inf. Theory, p.236, 2000; IEEE Trans. Inf. Theory, 2003). This condition permits, for example, the characterizing of instances of source/channel pairs for which very simple yet optimal feedback coding strategies exist, and leads to an understanding of the potential offered by feedback, and how to exploit it.

What makes a source-channel communication system optimal? It is shown that in order to achieve an optimal cost-distortion tradeoff, the source and the channel have to be matched in a probabilistic sense. The match (or lack of it) involves the source distribution, the distortion measure, the channel conditional distribution, and the channel input cost function. Closed-form necessary and sufficient expressions relating the above entities are given. This generalizes both the separation-based approach as well as the two well-known examples of optimal uncoded communication. The condition of probabilistic matching is extended to certain nonergodic and multiuser scenarios. This leads to a result on optimal single-source broadcast communication.

For a general class of constant-energy trellis-coded modulation (TCM) schemes with 2/sup /spl nu// states, necessary and sufficient conditions to guarantee that a maximum-likelihood sequence estimator (MSLE) can decode each symbol with a fixed delay of /spl nu/ symbols are derived. Additive white Gaussian noise (AWGN) is assumed. Minimum shift keying (MSK) is a special case that belongs to the family of modulation schemes with /spl nu/=1. It is shown that when these conditions are met, the minimum squared Euclidean distance is upper-bounded by 4E/sub s/, where E/sub s/ is the signal's energy per interval. Necessary and sufficient conditions to achieve the upper bound are given and it is shown that these conditions are met if and only if the TCM scheme can be implemented as pulse amplitude modulation (PAM) using a pulse that extends over /spl nu/+1 symbols. Signals that achieve this upper bound and maximize the power within a given bandwidth are found. The bandwidth efficiency of such schemes is significantly higher than that of MSK.

We consider multiple antenna systems in which a large number of antennas occupy a given physical volume. In this regime the assumptions of the standard models of multiple antennas systems become questionable. We show that for such spatially dense multiple antenna systems one should expect the behavior of the capacity to be qualitatively different than what the standard multiple antenna models predict.

It is shown that the iterative decoding algorithm proposed to decode "turbo codes" has fixed points regardless of the specific constituent codes and regardless of the noise variance of the additive white Gaussian noise (AWGN) channel.

It is shown that the encoding/decoding problem for any asynchronous M-user discrete memoryless multiple-access channel can be reduced to corresponding problems for at most 2M-1 single-user discrete memoryless channels. This result, which extends a similar result for Gaussian channels, reduces the seemingly hard task of finding good multiple-access codes to the much better understood task of finding good codes for single-user channels. As a by-product, some interesting properties of the capacity region of M-user asynchronous discrete memoryless channels are derived.

It is shown that the encoding/decoding problem for any asynchronous M-user memoryless multiple-access channel (MAC) can be reduced to corresponding problems for at most 2M-1 single-user memoryless channels. This is done via a method called generalized time sharing that is closely related to a previously developed method called rate-splitting multiple access. These methods reduce the seemingly hard task of finding good multiple-access codes and implementable decoders for such codes to the much better understood task of finding codes and decoders for single-user channels. As a by-product, some interesting properties of the capacity region of M-user asynchronous discrete memoryless channels are derived.

We investigate the problem of maximizing the capacity of multi-antenna Gaussian channels when one has the freedom of moving the transmit/receive antennas so as to modify individual singular values of the transfer matrix (subject to an overall energy conservation constraint). We solve this maximization problem and make some interesting observations. Namely that with n transmit and n receive antennas, when the signal-to-noise ratio is sufficiently large, the optimal solution corresponds to creating n parallel channels, all of which have the same strength. On the other extreme, when the signal-to-noise ratio is sufficiently small, the optimal solution boils down to creating a single channel. This is done by using the transmit and receive antennas to create focused beams. Perhaps the most interesting lesson is that beamforming is optimal only in the low signal-to-noise regime.

We consider the problem of recognizing CAD models at arbitrary orientations observed via the projective transformation on an imaging sensor with noise. Bounds on codebook size are established through the rate-distortion curve for a distortion measure derived from the Hilbert-Schmidt norm for elements of the orthogonal group.

It is shown that lattice codes can achieve capacity on the additive white Gaussian noise channel. More precisely, for any rate R less than capacity and e>0, there exists a lattice code with rate no less than R and average error probability upper-bounded by e. These lattice codes include all points of the (translated) lattice within the spherical bounding region (not just the ones inside a thin spherical shell).

It is shown that any point in the capacity region of a Gaussian multiple-access channel is achievable by single-user coding without requiring synchronization among users, provided that each user "splits" data and signal into two parts. Based on this result, a new multiple-access technique called rate-splitting multiple accessing (RSMA) is proposed. RSMA is a code-division multiple-access scheme for the M-user Gaussian multiple-access channel for which the effort of finding the codes for the M users, of encoding, and of decoding is that of at most 2M-1 independent point-to-point Gaussian channels. The effects of bursty sources, multipath fading, and inter-cell interference are discussed and directions for further research are indicated.

Rate 1/2 convolutional codes over the ring of integers modulo M are combined with M-ary continuous phase modulation (CPM) schemes whose modulation indices are of the form h=1/M. An M-ary CPM scheme with h=1/M can be modeled by a continuous-phase encoder (CPE) followed by a memoryless modulator (MM), where the CPE is linear over the ring of integers modulo M. The fact that the convolutional code and the CPE are over the same algebra allows the state of the CPE to be fed back and used by the convolutional encoder. A modified Euclidean distance function that substantially simplifies the search for good codes has been derived and used to find new codes. Numerical results show that this approach consistently improves the performance as compared to coded schemes using binary convolutional codes with the same decoding complexity.

Let R(/spl middot/) be the rate-distortion function. Assume that we want to describe a source with distortion no larger than /spl Delta//sub 1/. From the rate-distortion theory we know that we need to do so at a rate R/sub 1/ no smaller than R(/spl Delta//sub 1/) /spl lsqb/bits/symbol/spl rsqb/. If it turns out that a more accurate description at distortion /spl Delta//sub 2/, /spl Delta//sub 2/>

Continuous phase modulation (CPM) schemes are bandwidth and energy efficient constant-envelope modulation schemes that can be viewed as a continuous-phase encoder (CPE) followed by a memoryless modulator (MM), where the CPE is of convolutional type. It is observed that CPM schemes can be catastrophic in the sense that pairs of input sequences that differ in an infinite number of positions can be mapped into pairs of signals with finite Euclidean distance. This can happen in spite of the fact that the CPE is never catastrophic when considered as a stand alone convolutional encoder. The necessary and sufficient condition for a general CPM scheme to be catastrophic is given. Each member of the two major families of CPM schemes, namely the LREC and the LRC, has been classified as a catastrophic or noncatastrophic scheme. For the catastrophic schemes, the probability that a catastrophic event occurs is determined. A canonical precoder which transforms each scheme of both families into an equivalent noncatastrophic scheme is derived. The equivalent noncatastrophic scheme has the same number of states as the original one. Moreover, it has the property that if two input sequences differ in the ith position, the corresponding output signals have nonzero Euclidean distance in the ith interval.>

The exact expression for the minimum-squared Euclidean distance of continuous-phase frequency-shift keying (CPFSK) with modulation index h>

Consideration is given to the problems related to the design of M-ary continuous-phase frequency-shift keying (CPFSK) systems with modulation index h=J/M, combined with eternal rate r binary convolution encoders. The following questions are raised and answered: (1) how should different encoder-modulator systems be compared and how can comparable systems be recognized from the system parameters, i.e. M, h, and r?; (2) what are the limits on the information rate per unit bandwidth, versus signal-to-noise ratio, when reliable transmission is required?; (3) how does one choose the system parameters M, h, and r when the overall system has to achieve a specified performance?; and (4) how does one design the external rate r binary convolutional encoder to put in front of the M-ary CPFSK modulation system with h=J/M? A simple approximation for the bandwidth of a CPFSK signal is given and shown to be sufficiently accurate for system design purposes. The design of the external convolutional encoder is carried out in a novel way that leads to fewer states in the combined encoder-modulator system and thus yields improved performance for a given demodulation-decoding complexity compared to previous approaches for the design of coded CPFSK systems.>

It is shown that any continuous-phase-modulation (CPM) system can be decomposed into a continuous-phase encoder and a memoryless modulator in such a way that the former is a linear (modulo some integer P) time-invariant sequential circuit and the latter is also time invariant. This decomposition is exploited to obtain alternative realizations of the continuous-phase encoder (and hence of CPM) and also to obtain alternative forms of the optimum decoding algorithm. When P is a prime p so that the encoder is linear over the finite field GF(p), it is shown that cascading it with an outside convolutional encoder is equivalent to a single convolutional encoder. It is pointed out that the cascade of the modulator, the waveform channel (which it is assumed is characterized by additive white Gaussian noise), and the demodulator that operates over one symbol interval yield a discrete memoryless channel that can be studied without the distractions introduced by continuous-phase encoding.>