Introduction

In an ordinary computer, information is stored in a collection of tiny circuits each of which is designed to have two stable and easily distinguishable configurations: each represents a bit. In our study of quantum cryptography, we have seen how it can be useful to express information not in ordinary bits but in qubits. Whereas a bit can have only two values, say 0 and 1, a qubit can be in any quantum superposition of ∣0〉 and ∣1〉. Moreover, a qubit can be entangled with other qubits. Thus one might wonder whether a quantum computer, in which the basic elements for storing and processing information are qubits, can outperform an ordinary (classical) computer in certain ways. This question was addressed by researchers starting in the 1980s. In terms of practical consequences, perhaps the most dramatic answer has been given by Peter Shor in his 1994 factoring algorithm for a quantum computer, an algorithm that is exponentially faster than any known classical algorithm. As we have seen in Chapter 1, the difficulty of factoring a product of two large primes is the basis of the security of the RSA cryptosystem. So if one could build a large enough quantum computer – and there is no reason in principle why this could not be done – the RSA system would be rendered ineffective. In this chapter we present the basics of quantum computation and then focus on Shor's factoring algorithm.

Fields

Fields are important algebraic structures used in almost all branches of mathematics. Here we only cover the definitions and theorems needed for the purposes of this book.

Definition. A field F is a set along with two operations (denoted with addition and multiplication notation) on pairs of elements of F such that the following properties are satisfied.

1. For all a and b in F, we have that a + b ∈ F.

2. For all a, b, and c in F, we have that (a + b) + c = a + (b + c).

3. There exists an element 0 in F satisfying a + 0 = a for all a ∈ F.

4. For every a ∈ F there exists a b in F such that a + b = 0.

5. For all a and b in F we have that a + b = b + a.

6. For all a and b in F we have that ab ∈ F.

7. For all a, b, and c in F we have that (ab)c = a(bc).

8. There is an element 1 in F satisfying 1a = a for all a ∈ F.

9. For every a ∈ F with a ≠ = 0, there exists a b ∈ F such that ab = 1.

10. For every a and b in F we have that ab = ba.

11. For every a, b, and c in F we have that a(b + c) = ab + ac.

Introduction

Multiple antenna techniques (beyond two receive antennas at the base station) have now achieved a level of technical maturity that allows their implementation in commercial cellular systems. Specifically, multiple antenna technologies have been integrated into Third Generation (3G) cellular systems, and will soon be part of the 802.11n standard. In this chapter, we examine commercial implementations of multiple antenna techniques. While multiple antennas can be used at either the transmitter or the receiver, commercial standard specifications primarily focus on application at the transmitter. Multiple antenna techniques that are applied at the receiver are not specified by the standard and are vendor specific. As a result, while some of the techniques discussed in this chapter (e.g., transmit diversity) are defined by the 3G standards, others (e.g., receive beamforming) can be used in 3G systems, but are not specifically defined by standards-based technical specifications. Further, there are techniques that are under investigation in 3G standards bodies, e.g., spatial multiplexing, which requires multiple antennas at both the receiver and transmitter, often referred to as multiple input and multiple output (MIMO). We will describe techniques that fall into these categories, and will be careful to distinguish those techniques that are specified by the standard, that are under investigation by a specific standards group, or that are allowed by the standard. Section 25.2 presents the system model used throughout the chapter. Transmit diversity techniques are specified by both of the major 3G standards, and are discussed in detail in Section 25.3.

Focusing on challenging propagation channels, this chapter discusses spacetime coding techniques utilizing multiple antennas to facilitate high transmission rates, enhanced capacity, and robust system performance in mobile and fading environments.

Multipath and Doppler diversity

High rates come with broadband frequency-selective multipath propagation, while high mobility gives rise to Doppler-induced time-selective fading effects. The combined time-frequency selectivity of the underlying channel induces multipath-Doppler fading, which affects critically communication performance. Capturing multidimensional fading effects (over time, frequency, and space) requires many parameters, making it necessary for the resultant models to cope with the “curse of dimensionality.” Our motivation in this chapter is, at a high-level, to turn this “curse” into a “blessing” by designing multiantenna systems capable of collecting the embedded joint multipath- Doppler-spatial diversity gains. But before tackling this design goal, it is important to understand and quantify these diversity gains emerging from time- and frequency-selective propagation.

Frequency-selective channels and multipath diversity In their wireless propagation, the emitted signal waveforms may be reflected or diffracted, before reaching the receiver through different paths–a manifestation of what is known as multipath propagation. Due to the finite speed of light, the multiple paths conveying the information content travel variable distances and arrive at the receiver at different times. This causes time dispersion of the transmitted waveforms, which is known as delay spread. As a result, each symbol spills over adjacent symbols and gives rise to so-called intersymbol interference (ISI). In this case, we say that the channel exhibits frequency selectivity.

Precoding versus coding

A pivotal function of the physical transmission layer is that of making available a linear space of functions that meet transmission constraints. Each dimension of the coordinate system used in this space is called one degree of freedom. Except when orthogonal waveforms are used, the number of modulation waveforms is greater than the number of degrees of freedom. The transmission of a signature waveform colinear with one dimension is what is commonly referred to as one channel use. The constraints in designing modulation signals for MIMO systems are the classic ones: the transmit power is limited and the signals used should have their energy concentrated in a predefined window in time and frequency. The latter pair of constraints are coupled and the number of orthogonal signals with finite bandwidth-time product (WT) that can be constructed is ≤ WT. The formal statement of this fact is generally attributed to Gabor (1946).

Ideally, the selection of the signal space should be in continuous time and space. In practice, the digital to analog converters and antenna arrays and the RF propagation channel transduce the digital stream into signals with undesired properties. The transceivers' frontends can transform digitally the coordinate into a more suitable system of coordinates compared with that determined by the physical transducers. The linear mapping that establishes the new set of coordinates is referred to as linear precoding and its design can be carried out in discrete time (see Section 9.2 and Scaglione et al., 1999).

Introduction: high throughput short range systems–from SISO solutions to new MIMO standards

Until recently, wireless local area network (WLAN) devices, heavily constrained in cost and size, have fulfilled short range communication needs with very simple spatial diversity schemes at the access points (AP) realized, in general, with two antennas. Now WLAN AP products embedding phased array antenna designs have been designed with the objective of extending the range of the WLAN coverage, especially outdoors. However, with the demand for increasing bit rate, and the limited amount of spectrum available, the application of multiple-input multiple-output (MIMO) techniques to WLAN has been identified as a key enabler for high throughput WLAN; as a consequence, for instance, all the proposals made to the IEEE 802.11n task group, created in 2004 with the objective of devising next generation WLAN, include MIMO processing of the data.

The objective of this chapter is to present a design methodology for WLAN air interfaces relying on multiantenna signal processing solutions, and meeting feasibility requirements in terms of bit rate, bandwidth, and complexity. Here, we limit ourselves to a design compatible with the requirements set by the IEEE 802.11n task group: the aim is to provide a peak throughput of at least 100 Mbps at the medium access control (MAC) data service access point (SAP). Thus, with an overall MAC efficiency of 80%, thanks to a carefully optimized MAC, the peak physical (PHY) data rate of the designed WLAN systems should be at least of 125 Mbps.

Signal parameter estimation, and specifically direction of arrival (DOA) estimation for sensor array data is encountered in a number of applications ranging from electronic surveillance to wireless communications. Subspace-based methods have shown to provide computationally as well as statistically efficient algorithms for DOA estimation. Estimator performance is ultimately limited by model disturbances like measurement noise and model errors. Herein, we review a recently proposed framework that allows the derivation of optimal subspace methods, taking both finite sample effects (noise) and model errors into account. We show how this generic estimator reduces to well-known techniques for cases when one disturbance completely dominates the other.

Introduction

Subspace-based techniques have been shown to be powerful tools in many signal processing applications where the observed data consist of low-rank signals in noise. Some examples include sensor array signal processing, harmonic retrieval, factor analysis, timing estimation, frequency offset estimation, image processing, system identification, and blind channel identification. By appropriate use of the underlying low-rank data model and the associated signal and noise characteristics, subspace estimation techniques can often be made computationally and/or statistically efficient.

This chapter focuses on subspace techniques for direction of arrival (DOA) estimation from data collected by a sensor array. This is quite a mature field of research by now; many tutorial papers and books have been presented, some detailing specific aspects and others giving broader views (e.g., Krim and Viberg (1996), Van Trees (2002), and the references therein). We have no ambition whatsoever to give a comprehensive account of the development of the field of DOA estimation in this chapter.

Introduction

Information-theoretic analysis by Foschini (1996) and by Telatar (1999) shows that multiple antennas at the transmitter and receiver enable very high rate wireless communication. Space-time codes, introduced by Tarokh et al. (1998), improve the reliability of communication over fading channels by correlating signals across different transmit antennas. Design criteria developed for the high-SNR regime in Tarokh et al. (1998) and Guey et al. (1999) are presented in Section 7.3 from the perspective of typical error events (following the exposition by Tse and Viswanath (2005)). Techniques for multiple access and broadcast communication are described very briefly in Sections 7.9 and 7.10, where algebraic structure enables simple implementation. The emphasis throughout is on low cost, low complexity mobile receivers.

Section 7.2 provides a description of set partitioning, which was developed by Ungerboeck (1982) as the basis of code design for the additive white Gaussian noise (AWGN) channel. The importance of set partitioning to code design for the AWGN channel is that it provides a lower bound on squared Euclidean distance between signals that depends only on the binary sum of signal labels. Section 7.9 describes the importance of set partitioning to code design for wireless channels, where it provides a mechanism for translating constraints in the binary domain into lower bounds on diversity protection in the complex domain.

Section 7.4 describes space-time trellis codes, starting from simple delay diversity, and then using intuition about the product distance to realize additional coding gain.

The goal of this chapter is to expose a number of key ideas in blind and, especially, semiblind (SB) channel estimation (CE), and attract attention to various considerations that should be kept in mind in this context. As will become clear, the topic considered is vast. Due to space limitations, the inclusion and discussion of references is far from exhaustive. See also de Carvalho and Slock (2001) for an overview of semiblind single-input multiple-output (SIMO) channel estimation approaches. The use of blind information in digital communications is motivated by a desire to limit capacity loss due to training. Such capacity loss potentially increases with increasing time variation, occupied bandwidth, and number of transmitters. In other applications, blind techniques may be the only option (e.g., acoustic dereverberation). A particularity of digital communications, however, is that the sources are discrete time, white, and finite alphabet.

Signal model

In a first instance, the nonblind information considered will be provided by training or pilot information. As for terminology, the term training sequence (TS) tends to be used for a limited consecutive sequence of known symbols, whereas pilot symbols are typically isolated known symbols. A pilot signal is a continuous stream of known symbols, superimposed on the data signal.

Introduction

In digital communication systems, error correcting coding is used to combat channel impairments such as noise or fading. The discovery of an iterative “turbo” decoding strategy (Berrou et al., 1993) started a new era in error correcting coding. Turbo codes were quickly adopted for wireless cellular standards like CDMA2000 and UMTS. Basic building blocks are soft in/soft out decoders connected through interleavers. With each decoding iteration, reliability information is exchanged, and a priori knowledge is updated by new, or extrinsic informationa mechanism similar to a turbo engine.

The advance of silicon technology facilitates the implementation of more sophisticated algorithms at the receiver, enabling iterative processing not only within the channel decoder, but also over the channel interface, such as the detector of a multiple input/multiple output (MIMO) antenna communication scheme. MIMO techniques (e.g., Winters et al. (1994)) allow to increase the data rate while keeping the bandwidth unchanged, thus making better use of the scarce spectral resources. They have recently found their way into a number of wireless communication standards, like IEEE 802.11n wireless LAN and 802.16 wireless MAN.

In this chapter, we apply turbo processing to the detection and decoding of signals transmitted over MIMO channels. We first outline several variants of coding over space and time, and determine the ultimate capacity limits of MIMO channels. We then study the properties of iterative processing structures, explain the exchange of reliability information and discuss the convergence behavior of iterative decoding in the MIMO context.

Introduction

The main impairment in wireless channels is fading or random fluctuation of the signal level. This signal fluctuation happens across time, frequency, and space. Diversity techniques provide the receiver with multiple independent looks at the signal to improve reception. Each one of those independent looks is considered a diversity branch. The probability that all diversity branches will fade at the same time goes down as the number of branches increases. Hence, with a high probability, there will be at least one branch or link with a good signal such that the transmitted data can be detected reliably.

Wireless channels are, in general, characterized by frequency-selective multipath propagation, Doppler-induced time-selective fading, and spaceselective fading. An emitted signal propagating through the wireless channel is reflected and scattered from a large number of scatterers, thereby arriving at the receiver through different paths and hence arriving at different times. This results in the time dispersion of the transmitted signal. A measure of this dispersion is called the channel delay spread Tmax. The coherence bandwidth of the channel Bc ≈ l/Tmax measures the frequency bandwidth over which the propagation channel remains correlated. Therefore, a propagation channel with a small delay spread will have a large coherence bandwidth, i.e., the channel frequency response will remain correlated over a large bandwidth, and vice versa.

In addition, transmitter and receiver mobility as well as changes in the propagation medium induce time variations in the propagation channel.

Introduction

The growth in wireless communication over the past decade has been fueled by the demand for high-speed wireless data, in addition to the basic cellular telephony service that is now an indispensable part of our lives. Cellular operators are upgrading their networks to support higher data rates, and the imminent completion of the 802.16 and 802.20 standards is precipitating the move toward ubiquitous broadband wireless access. Increasing the capacity of current wireless links is perhaps the most essential step in realizing the vision of high-speed wireless data on demand, and adding multiple antennas at both the transmitter and the receiver is known to dramatically increase capacity. In this chapter, we explore the role of channel knowledge at the transmitter in multiple-input multiple-output (MIMO) systems. While feedback produces marginal gains in single-antenna communication, even partial channel knowledge at the transmitter is known to produce large performance gains in MIMO systems. We also consider the benefits of partial channel knowledge at the receiver in noncoherent systems.

For indoor wireless local area network (WLAN) systems with MIMO capabilities, such as the BLAST prototype, and emerging 802.11n standards efforts, the system bandwidth is typically smaller than the channel coherence bandwidth, which is large because of small indoor delay spreads. On the other hand, emerging high-speed outdoor wireless metropolitan area network (WMAN) communication systems, such as 802.16 and 802.20, can easily span a band that is several times the channel coherence bandwidth, which is smaller due to larger delay spreads in outdoor channels.

Introduction

The broadcast channel (BC) first introduced by Cover (1972) is now a standard channel model in information theory (Cover and Thomas, 1991), which has attracted massive attention, and yet the capacity region is not known in general. The BC models downlink communications, where a central hub (cellsite, for example) transmits to potentially multiple users. Multiple-input multiple-output (MIMO) channels have been identified as a central factor in significantly amplifying the capability of wireless communications (Goldsmith et al., 2003; Tse and Viswanath, 2005). Motivated by practical high reliable rate demands of future wireless and wireline systems, well modeled by the MIMO Gaussian broadcast channel (MIMO GBC), such as cellular systems, wireless local area networks, and xDSL links, the ultimate potential of the MIMO GBC has been identified as a theoretical challenge, which carries evident practical implications.

The central information-theoretic hardship arises in the general MIMO GBC setting, even if all channel state information (CSI) is available at every node (transmitter as well as receivers). This is due to loss of degradation ordering in the general MIMO case, directly leading to the general BC, for which the capacity region is yet unknown. Evidently one may resort to bounding techniques, such as the well known Marton region (Marton, 1979), which constituted for decades the best achievable rate region for the general BC. Different upper bounds are also available, and some of the most interesting are the Marton–Körner (Marton, 1979) and Sato (Sato, 1978) outer bounds.