Ezio Biglieri, Politecnico di Torino
Title: Coding for Multiple Antennas with Linear and Nonlinear (BLAST) Interfaces
We compare suboptimum linear and nonlinear interfaces to be used for decoding space-time codes transmitted over a multiple-antenna Rayleigh fading channel with perfect channel-state information available at the receiver. The performance of Vertical BLAST and that of linear receiver interfaces are examined with codes obtained by apportioning evenly among the transmit antennas the symbols of off-the-shelf convolutional codes. We first observe how the introduction of an interleaver can be beneficial here. Next, we introduce a new simple iterative linear interface, based on hard Viterbi decoding and offering a performance considerably improved with respect to noniterative receivers. Numerical results show how a performance close to optimum (maximum-likelihood) detection can be achieved with simpler receiver interfaces.
Giuseppe Caire, Institut Eurecom, France
Title: Writing on Dirty Paper with LDPC Codes
Capacity and coding strategies for state-dependent channels with state sequence known to the transmitter but unknown to the receiver is a classical problem in information theory that dates back to Shannon (causal knowledge of the state sequence) and to Gel'fand and Pinsker (non-causal knowledge of the state sequence). In the case of additive interference and additive Gaussian noise channels, a remarkable result by Costa shows that capacity is the same as if interference was not present. From the appealing title of Costa's paper (Writing on dirty paper), the whole class of codes for known channel states goes under the name of ``Dirty paper coding''. Historically, coding for states known to the transmitter was motivated by problems like storage in defective computer memories. Recently, dirty paper coding gained renewed attention because it arises as the main tool in several important settings, the most relevant of which are:
Driven by the above motivations, several generalizations of Shannon, Gel'fand-Pinsker and Costa results appeared in the recent information theoretic literature. In particular, for the additive interference case a recent work by Shamai, Erez and Zamir provides a lattice-precoding strategy that can be applied when the transmitter has knowledge of k samples of the interference signal, where k = 1 CORRESPONDS TO the causal case (Shannon setting, nicknamed ``dirty-tape'' to parallel dirty-paper) and k = n (the whole code block length) is the non-causal case (Costa setting).
Despite the many information theoretic results on achievable rates and guidelines for constructing dirty-paper (or dirty-tape) codes, explicit constructions of codes able to approach within a fraction of dB the information theoretic limits at all SNRs are still lacking in /the/ current literature.
This talk is organized into two sections. In the first part, we shall cover in a semi-tutorial fashion the various aspects of dirty-paper coding and its applications in the problems listed above. In the second part, we shall focus on explicit code construction techniques based on Low-Density Parity-Check codes and high-order modulation alphabets able to approach within a fraction of dB the dirty-tape limit (causal interference knowledge). Finally, we shall POINT OUT SOME INTERESTING ASPECTS EMERGING in the generalization of our coding approach to the dirty-paper problem with given anticipation k.
Gerard Foschini, Bell Labs
Title: Dirty Paper Coding: Neighborhood Of The Infinite Dimensional Lattice Limit
Motivated by its potential role in reducing the need for orthogonal use of wireless communication resources in downlink signalling, we focus here on so called Dirty Paper Coding (DPC). DPC can immunize a link against interference when the erstwhile interferer is launched from the same transmit site. This promotes reuse of space4spectral communication resources even at the same base station since would be interferers can be made phantoms (invisible interferencewise) to communicators on the same resource.
For best performance, DPC signals uses special high dimensional lattices. We derive a means of perturbing off of the infinite-dimensional limit to estimate Shannon capacities in very high dimensions. At the opposite extreme, we look at simple to use 1-D lattices. A wide range of SNRs are of interest. Use of higher dimensional lattices is important at low SNRs. For both high and low dimensions we emphasize the importance of DPC's "noise cooling" feature. At 0dB, where the Shannon capacity is 1 bps/Hz, a 1-D lattice requires an extra 4.5 dB. However, with proper cooling, it requires an additional 2.5dB. A 48-D lattice, with optimally cooled noise, is estimated to require only an extra 0.5 dB.
The standard DPC assumption is that both transmitter and receiver know the channel. If there are M transmitter antennas, and N receiver antennas, the channel matrix, H, is, of course, described by MN complex numbers (so 2MN reals). DPC communication takes place over each of the individual spatial eigenmodes of H?H. When the transmitter relies on receiver channel measurements, we find that the least number of reals that must be fedback is min(M,N) 4[2M -min(M,N)].
Andrea Goldsmith, Stanford University
Title: Duality, Dirty Paper Coding, and Capacity for Multiuser Wireless Channels
We discuss several techniques that shed new light on the capacity regions and optimal transmission strategies of multiuser wireless channels. We first present a duality relationship between broadcast and multiple access channels. This relationship can be used to obtain the capacity region and the corresponding optimal transmission strategy for one channel based on the capacity region and optimal transmission strategy of the dual channel. This is a powerful result since in many cases the capacity region of one channel is known and easy to compute while the capacity region of its dual has not been solved directly or is difficult to compute. Duality is applicable to additive Gaussian noise channels and to fading channels for several different notions of fading channel capacity, including ergodic capacity, outage capacity, and minimum rate capacity. We present some examples of using duality to solve for previously unknown capacity regions. In particular, we consider broadcast channels with multiple antennas at both the transmitter and at each receiver (the MIMO BC). Since this channel is in general non-degraded, there is no direct solution for its capacity region. However, an achievable rate region can be obtained by Costa's ``dirty-paper'' coding. We will discuss the dirty paper region for the MIMO BC and establish a duality between this region and the capacity region of the MIMO multiple-access channel (MAC) under a sum-power constraint. This MAC region is well-known and easy to compute. Thus, by exploiting the duality of these regions we obtain a simple method to compute the dirty paper region of the MIMO BC, which lower bounds the capacity region. We also show that the dirty paper region achieves the sum-rate capacity of the MIMO BC by extending Sato's upper bound to include worst-case noise correlation. We conclude with some interesting results on the complete capacity region of the MIMO BC and its relationship to the dirty paper achievable region.
Hao Xu, Bell-labs
Title: Broadband MIMO Spacetime Propagation Model For Realistic Capacity Evaluation
This paper presents a generalized multiple-input-multiple-output (MIMO) channel modeling approach for link level and system level simulations. The model provides channel transfer matrices based on the superposition of plane waves. The spatial, temporal and frequency dispersions of the MIMO channels are implicitly modeled based on any given statistics. The validity of the model is verified through both simulation and experiment.
Babak Hassibi, California Institute of Technology
Title: On the Expected Complexity of Integer-Least-Squares Problems
The problem of finding the least-squares solution to a system of linear equations where the unknown vector is comprised of integers, but the matrix coefficient and given vector are comprised of real numbers, arises in many applications: communications, cryptography, GPS, to name a few. The problem is equivalent to finding the closest lattice point to a given point and is known to be NP-hard.
In most applications, however, the given vector is not arbitrary, but rather is an unknown lattice point that has been perturbed by an additive noise vector whose statistical properties are known. Therefore in this talk, rather than dwell on the worst-case complexity of the integer-least-squares problem, we study its expected complexity, averaged over the noise and over the lattice. For a specific algorithm, referred to as ``sphere decoding'', we find a closed-form expression for the expected complexity and show that for a wide range of noise variances the expected complexity is polynomial-time, in fact often sub-cubic. Since many communications systems operate at noise levels for which the expected complexity turns out to be polynomial-time, this suggests that maximum-likelihood decoding, which was hitherto thought to be computationally intractable, can in fact be implemented in real-time---a result with many practical implications.
Our derivation has interesting connections with some classical work of Jacobi, Ramanujan and Hardy-Littlewood, which I will discuss. I will also point out a connection between computational complexity and Shannon capacity which our results seem to suggest. This is joint work with H. Vikalo.
Bertrand Hochwald, Lucent Technologies
Title: Multi-Antenna Channel Hardening and Its Implications for Rate Feedback and Scheduling
Wireless data traffic is expected to grow over the next few years and the technologies that will provide data services are still being debated. One possibility is to use multiple antennas at basestations and terminals to get very high spectral efficiencies in rich scattering environments. Such multiple-input multiple-output (MIMO) channels can then be used in conjunction with scheduling and rate-feedback algorithms to further increase channel throughput. This talk provides an analysis of the expected gains due to scheduling and bits needed for rate feedback.
Our analysis requires an accurate approximation of the distribution of the MIMO channel capacity. Because the exact distribution of the instantaneous channel capacity in a Rayleigh fading environment is difficult to analyze, we prove a central limit theorem for MIMO channels with a large number of antennas. While the growth in average (or ergodic) capacity of a MIMO channel with the number of antennas is well understood, it turns out that the variance of the instantaneous capacity can grow very slowly or even shrink as the number of antennas grows. We discuss implications of this "channel-hardening" result for data and voice services, scheduling and rate feedback. We also briefly discuss the implications when shadow fading effects are included.
Brian Hughes, North Carolina State University
Title: Optimal Space-Time Spreading for CDMA with Multiple Transmit Antennas
We consider a synchronous code-division multiple-access (CDMA) system with multiple transmit antennas and a single receive antenna in the presence of frequency-flat Rayleigh fading. For large user populations with random signature sequences, we characterize those space-time spreading methods that maximize the spectral efficiency (capacity per chip) of the resulting system, as a function of the transmit array size and the number of spreading sequences per user. The optimal space-time spreading methods turn out to be closely related to orthogonal designs; however, the signal components detected at the receiver are structured so as to be orthogonal in the fading path gains rather than the data.
Angel Lozano, Lucent Technologies
Title: Multi-Antenna Capacity in the Low-power Regime
This paper provides analytical characterizations of the impact on multi-antenna capacity of several important features that fall outside the standard multi-antenna model, namely, (i) antenna correlation, (ii) Ricean factors, and (iii) polarization diversity, all in the regime of low signal-to-noise ratio. The interplay of rate, bandwidth and power is analyzed in the region of energy per bit close to its minimum value. The analysis yields practical design lessons for arbitrary number of antennas in the transmit and receive arrays.
Narayan Mandayam, WINLAB, Rutgers University
Title: Pilot Assisted Estimation of MIMO Fading Channel Response and Achievable Data Rates
In this paper we analyze the effects of pilot assisted channel estimation error of a frequency-flat time-varying channel on achievable data rates. We consider multiple-input multiple-output (MIMO) wireless systems and emphasize differences with respect to single-input single-output (SISO) systems. The analysis connects results of information theory with practical wireless communication systems. Using a block-fading channel model, where the block length corresponds to the channel coherence time, we consider two pilot based approaches for the estimation. Per transmit antenna, the first approach uses a single pilot symbol per block with different power than data symbols, while the second approach uses more than one pilot symbol per block with same power as data symbols. In the MIMO case, the orthogonality between the pilots assigned to different transmit antennas is assumed. The effects of the estimation error are evaluated in the case of the estimates being available at the receiver only (open loop), and in the case when the estimates are fed back to the transmitter allowing water pouring transmitter optimization (closed loop). The presented analysis is a study of mismatched receiver and transmitter algorithms in MIMO systems.
Ivana Maric, WINLAB, Rutgers University
Title: Efficient Multihop Broadcast for Wideband Systems
In this paper we address the minimum-energy broadcast problem. To increase the energy efficiency, we allow nodes that are out of the transmission range of a transmitter to collect the energy of unreliably received overheard signals. As a message is forwarded through the network, a node will have multiple opportunities to reliably receive the message by collecting energy during each retransmission. We refer to this strategy as accumulative broadcast. Under the assumption that the nodes reliably forward messages, we formulate the minimum-energy accumulative broadcast problem. We present a solution employing two subproblems. First, we identify the ordering in which nodes should transmit. Second, we determine the optimum power levels for that ordering. While the second subproblem can be solved by means of linear programming, the ordering subproblem is shown to be NP-complete. We devise a heuristic algorithm to find a good ordering and evaluate the performance of the algorithm. Preliminary results show the performance of the heuristic algorithm is generally close to the optimum solution. Results also show a significant improvement compared to the well known BIP algorithm for constructing an energy-efficient broadcast tree.
Aris Moustakas, Bell Labs, Lucent Technologies
Title: MIMO Capacity Through Correlated Channels in the Presence of Correlated Interferers and Noise: A (not so) Large N Analysis
The use of multi-antenna arrays in both transmission and reception promises huge increases in the throughput of wireless communication systems. It is therefore important to analyze the capacities of such systems in realistic situations, including correlated channels and correlated noise, as well as correlated interferers with known channel. Here we present an approach that provides analytic expressions for the statistics, i.e. the moments of the distribution of the mutual information of multi-antenna systems with arbitrary correlations, interferers and noise. Although this method is valid formally for large antenna numbers, it produces extremely accurate results even for arrays with two or three antennas. We also develop a method to calculate analytic closed-loop capacities with covariance feedback. We show that this closed-loop capacity is quite close to the full closed loop capacity in which the transmitter has full channel knowledge. We apply this analytic approach to a number of important examples and also compare to simulations to establish its validity. This analytic approach provides a simple tool to analyze the statistics of throughput for arrays of any size.
Christopher Rose, WINLAB, Rutgers University
Title: Interference Avoidance in Wireless Systems
Interference Avoidance is a method intended for distributed use by uplink users of an unlicensed wireless system who greedily adjust their codewords in response to interference. Under most circumstances the result is, surprisingly, optimum utilization of the available spectrum, even though individual users seek only to maximize their own performance. We will describe interference avoidance in its various flavors, its applicability to a variety of wireless scenarios, and ideas about possible uniform transceiver structures. We will also contrast interference avoidance with recently discovered iterative waterfilling methods since there has been some confusion about the relationship between the two.
Mathini Sellathurai, Communications Research Centre and Gerard J. Foschini, Bell Labs
Title: A Stratified Diagonal Layered Spacetime Architecture: Information Theoretic and Communications Aspects
Consider an (M, N) wireless link, (M transmit antennas, N receive antennas), impaired by AWGN. The transmitter, which is subject to a power constraint, does not know the outcome of the random matrix channel which has a static, flat frequency characteristic. It does know the statistics of the channel which must be operated under a probability of outage constraint. We stress capacity considerations and spacetime structures aimed at realizing a significant portion of capacity. The Bell Labs Layered SpaceTime (BLAST) architectures are multi-element antenna systems using building blocks of separately coded/decoded 1-Dim (1-dimensional) subsystems and interference-cancellation receivers. Despite the M-Dim transmit signal, these structures avoid the explosion of processing complexity in the spatial domain with substantial spectral efficiency.
The diagonal layered spacetime architecture, Diagonal-BLAST (D-BLAST) uses successive imaginary "diagonals". Importantly, these diagonals offer a way to mute mutual interference, while enabling 1-Dim coding/decoding. In principle, the D-BLAST transmitter does not require channel outcome knowledge. However, D-BLAST is unsuitable for short packets due to boundary spacetime wastage. In V-BLAST, the first practical system demonstrated, every antenna can transmit an independently encoded horizontal-layer. However, the capacity achieved by V-BLAST for cases M > N is substantially lower.
We introduce an alternative communication means drawing on a more refined view of spacetime when M > N. We call this structure Stratified Diagonal BLAST (SD-BLAST). SD-BLAST involves cycling spatially 1-Dim coded/modulated signal constituents periodically over the M transmit antennas. In contrast to the successive diagonals layering in D-BLAST, in SD-BLAST the layering is done with M-stratified helices perfectly winding around and covering all spacetime so that no spacetime edge wastage is encountered. In effect a stratified helical layer has replaced a long diagonal. The method uses a stratified helical-layer composed of a number of encoded data streams called strata. Interference is muted with onion peeling using a 1-Dim decoder stripping off each helical-layer stratum by stratum.
When the transmitter knows only the statistics of the matrix channel, determining optimal stratum rates is a concern. For an SD-BLAST message to be successfully received with sufficiently high probability, it is crucial that each stratum be appropriately encoded. We discuss the selection of the per strata rates. Using Monte-Carlo generation of random channels, examples in important downlink categories show that the message architecture can be extremely efficient. Particularly:
Steven Simon, Lcent Technologies, Bell Labs
Title: Optimality of Beamforming and Other Exact Results
We consider narrowband point-to-point MIMO systems where the receiver knows the channel, but the transmitter has only statistical knowledge of the channel. We examine two canonical channel models representing mean channel feedback and channel covariance feedback (gaussian random matrices with either nonzero channel mean or nontrivial covariance). The transmitter is assumed to know the mean and covariance of the channel, although not the channel itself. We wish to optimize the transmission covariance so as to maximize either the (ergodic) average capacity, or some outage capacity. In some cases, the optimal transmission covariance corresponds to beamforming (transmission covariance of rank 1). For either channel model, we can derive a necessary and sufficient condition to determine when beamforming is optimal for maximizing the ergodic capacity for general N by M (N transmit antennas, M receive antennas) systems. For the outage capacity we only derive a necessary condition. For the case of N by 1 antenna systems and 2 by N antenna systems, we further examine the optimal transmission covariance when beamforming is not optimal. We find in the case of outage capacity the optimal transmission covariance can change discontinuously as the statistical properties of the channel model are changed smoothly
Vahid Tarokh, Harvard University
Title: Variable rate space-time block codes
We consider a multiple antenna system when combined array processing with space-time coding is used. We present variable rate space-time block codes for two, three, and four transmit antennas and optimize the transmit power so that the average BER is minimized. Numerical results show that this optimum power allocation scheme provides significant gain over the equal power allocation scheme. We then classify all the variable rate space-time block codes having the same code rates and identify the unique code that achieves the lowest BER. We explicitly compute the performance of the variable rate codes over a Rayleigh fading channel. The proposed variable rate space-time block codes are useful for unequal error protection in multiple transmit antenna systems.
Sekhar Tatikonda, Yale University
Title: Capacity and Coding for Feedback Channels
We present a framework for characterizing the capacity of a large variety of channels with memory, side-information, and feedback. The use of feedback and side-information can increase the capacity of a noisy channel, decrease the complexity of the encoder and decoder, and reduce latency. For a class of Markov channels we show that one can formulate the capacity optimization problem as a dynamic program and compute the capacity using tools from approximate dynamic programming.
David Tse, U.C. Berkeley
Title: Multiple Antennas: A Network View
In a point-to-point link, multiple antennas provide both a diversity gain and a spatial multiplexing gain. In recent work, we characterized the fundamental tradeoff between these two types of performance gains. In a network setting, multiple antennas in addition provide multiple acess and interference suppression ability. We extend the diversity-multiplexing tradeoff to such a setting to help us understand the capabilities of multiple antennas in the context of a wireless network.
Pramod Viswanath, University of Illinois at Urbana-Champaign
Title: Sum Capacity of the Multiple Antenna Broadcast Channel
We characterize the sum capacity of the multiple antenna broadcast channel by showing that the existing outer bound of Sato and the existing inner bound of Marton are tight for this channel. We exploit an intimate 4-way relationship between the broadcast channel, the corresponding point-point channel (where the receivers cooperate), the multiple access channel (where the role of transmitters and receivers cooperate) and the corresponding point-point channel (where the transmitters cooperate).
Harish Viswanathan, Bell Labs
Title: Downlink Capacity Evaluation of Cellular Networks with Known Interference Cancellation
Recently the capacity region of a multi-input multi-output (MIMO) Gaussian broadcast channel, with Gaussian codebooks and known-interference cancellation through dirty paper coding (DPC), was shown to equal the union of the capacity regions of a collection of MIMO multiple access channels (MAC). We use this duality result to evaluate the system capacity achievable in a cellular wireless network with multiple antennas at the base station and multiple antennas at each terminal. Some fundamental properties of the rate region are exhibited, and algorithms for determining the optimum weighted rate sum and the optimal covariance matrices for achieving a given rate vector on the boundary of the rate region are presented. These algorithms are then used in a simulation study to determine potential capacity enhancements to a cellular system through known-interference cancellation. We study both the circuit data scenario in which each user requires a constant data rate in every frame, and the packet data scenario in which users can be assigned a variable rate in each frame so as to maximize the long-term average throughput. In the case of circuit data, the outage probability as a function of the number of active users served at a given rate is determined through simulations. For the packet data case, long term average throughputs that can be achieved using the proportionally fair scheduling algorithm are determined. We generalize the zero-forcing beam-forming technique to the multiple receive antennas case and use this as the baseline for the packet data throughput evaluation.
Next: Call for Participation
Workshop Index
DIMACS Homepage