Ebook: Multiple Access Channels

While multiple-access communication dates back to systems invented in the 1870's to transmit simultaneous data through a single wire, the foundation of the discipline now known as “multiuser information theory” was laid in 1961, when Claude E. Shannon published his paper [1] on two-way channels. Since then, multiuser information theory has been an extremely active research area, and has seen a large number of fundamental contributions, covering, besides the two-way channel studied in [1], multiple access, interference, broadcast, and wiretap channels (see [2] for a brief historical account of the development of this theory up to 1998). However, several key canonical problems have defied many efforts [3].

The NATO Advanced Study Institute on Coding and Analysis of Multiple Access Channels was organized in the Europa Congress Center, Budapest from August 26 to September 5, 2006, in the form of an advanced course on multiple access channels, during which leading experts working in the fields of information theory, coding theory, multiple user communications, discrete mathematics, etc., surveyed recent and general results on multiple-access channels (rate regions, rate splitting, etc.), and gave an overview of the problems of current CDMA solutions (fading channels, multi-user detection, multiple-antenna systems, iterative joint decoding, OFDMA, etc.). The lecturers investigated the information-theoretic bounds of the most important deterministic channels, too (OR channel, adder channel, collision channel, slow frequency hopping, random access, Euclidean channel), together with some efficient code constructions for both synchronous and asynchronous access. The slides of the lectures are available at: http://www.szit.bme.hu/natoasi/program.html.

This volume includes 16 contributions that were prepared in the occasion of the Institute, organized in three parts.

The first part includes chapters devoted to the information-theoretical aspects of multiple-access communication. The first chapter, coauthored by Imre Csiszár and András György, focuses on the basic coding theorems for multiple-access channels, with special focus on a system with two senders and one receiver. The next contribution, by Bixio Rimoldi, is devoted to rate-splitting multiple access. This theory shows how the problem of coding/decoding for multiple-access channels can be reduced to that of coding/decoding for point-to-point channels. The two following chapters, coauthored by Danyo Danev, Zoltan Füredi, Bálint Laczay, and Miklós Ruszinkó, discuss the signature coding problem of multiple-access adder and Euclidean channels. In one further chapter, Edward C. van der Meulen, surveys the most representative results on the relay channel obtained in the period 1968–2006, and discusses the recent topic of relay-without-delay channels. The chapter of Jack K. Wolf reviews noiseless coding with side information, as well as some recent results on noisy source coding. This part is concluded by a chapter on coding for channels with constrained and unconstrained side information, authored by Yossef Steinberg.

The second part, devoted to multiple-access techniques, is opened by the chapter by Ezio Biglieri, which examines, through a simple—but by no means trivial—case, a wireless channel endowed with multiple transmit and receive antennas. The chapter focuses on capacity limits, receiver design, and code choices. Martin Bossert's contribution focuses on orthogonal frequency-division modulation in wireless environment, and in particular on coding schemes suitable for that technique. Braided code-division multiple access (CDMA) is covered in the subsequent chapter by Kamil Sh. Zigangirov and Marcos B. S. Tavares, where a novel CDMA technique, based on braided codes, is described. Next chapter, by László Györfi, Sándor Győri, and James L. Massey, covers the stability and instability of random-access systems with feedback, based on the fact that such systems are generally well-modelled by homogeneous Markov chains. This part is concluded by a chapter on random-access channels with the feedback of collision's multiplicity, authored by Bálint Laczay and Miklós Ruszinkó.

The third part of this volume covers coding techniques. A. J. Han Vinck describes the construction of codes that approach or achieve the capacity by focusing on two specific models, the 2-adder and the switching channel, respectively, with and without feedback. In his chapter, Anthony Ephremides introduces what is now known as “network information theory,” focusing on the study of the multi-access channel from the perspective of a network, with special emphasis on stability issues and network coding. László Györfi and Sándor Győri describe some bounds and code constructions for multiple-access collision channels without feedback and for slow frequency hopping with asynchronous access. Finally, Ernst Gabidulin reviews the metrics that can be chosen as cost functions for the optimization of codes for general channels.

For help with local arrangements during the NATO ASI we want to thank Sándor Győri, Gusztáv Hencsey and Mariann Kindl. We are very grateful to all people who helped making this NATO Advanced Study Institute on Coding and Analysis of Multiple Access Channels a great success. We hope that this event may further lead to setting new milestones in this fascinating area.

References

[1] C.E. Shannon, “Two-way communication channels,” in Proc. Berkeley Symp. Mathematical statistics and probability (June 20 – July 30, 1960), J. Newman, Ed. Berkeley, CA: Univ. California Press, 1961, Vol. 1, pp. 611–644.

[2] S. Verdú, “Fifty years of Shannon theory,” IEEE Trans. Inform. Theory, Vol. 44, No. 6, pp. 2057–2078, October 1998.

[3] S. Verdú, “Guest editorial,” IEEE Trans. Inform. Theory, Vol. 44, No. 6, pp. 2042–2044, October 1998.

Multiple access channels play important role in both theoretical and practical aspects of information theory. In this short tutorial paper we derive the capacity region of the multiple access channel with two senders and one receiver.

Rate-splitting multiple-access allows one to use single-user coding/decoding techniques to achieve any rate tuple that lies inside the capacity region of an asynchronous multiple-access channel. We introduce rate-splitting multiple-access for the 2-user Gaussian multiple-access channel and then consider a general 2-user discrete memoryless multiple-access channel. Both cases generalize to M-users.

In this chapter we investigate classical and new results on multiple access adder channels. These results from mathematical point of view relate to Sidon type search problems investigated by Erdős and Rényi, Lindström, etc. The so called permanent and partial activity cases will be considered.

Codes for Euclidean channels are discussed in this chapter. In case of Euclidean channels the input codewords are usually arbitrary members of the n-dimensional Euclidean space ⁿ. However, by energy constraint reasons the code-words are assumed to have Euclidean norm: one at most. This way they are closely related to spherical codes and “kissing numbers”. In addition to this some other constraints are assumed, usually with respect to the Euclidean distance of code-words or groups of codewords. Here we shall discuss the best known bounds and constructions for multiple access Euclidean channels.

A survey is given of the most representative results on the relay channel obtained in the period 1968-2006. Several cooperative relay strategies are presented and illustrated with examples. The direct-transmission, decode-and-forward, partial decode-and-forward, and compress-and forward lower bound on the capacity of the discrete memoryless relay channel are given. The classes of relay channels for which these bounds coincide with the cut-set upper bound are treated, such as the (semi-) deterministic and degraded relay channel, and the relay channel with orthogonal components. Coding schemes for deterministic relay channels are presented. Several connections with the multiple-access channel are pointed out. The Gaussian degraded relay channel, the Gaussian relay channel with orthogonal components, and the general AWGN relay channel are analyzed. The new topic of the relay-without-delay channel is also discussed.

A review of noiseless coding with side information is presented. An intuitive derivation of the main result for a pair of binary symmetric sources is given. The results are then applied to the case where there is one encoder broadcasting its output to two decoders, each of which have different side information. Finally some recently published papers by others on noisy source coding are reviewed.

State dependent channels with state information at the transmitter, receiver, or both, have received much attention in recent years, due to the wide applicability of such models in communication systems. A common assumption in many of the works on this problem, is that the channel state is readily available, or at least can be accurately estimated, at the user's site. While this may be true in some cases, in many practical systems the state information is provided to the users by a third party. This is particularly true in network environments, where data on the channel state can be collected by part of the users, and then transmitted to all the active users in the network. In such a case, system resources—bandwidth, time slots, etc.—are allocated to this purpose. This raises the question of how to compress and distribute channel state information in those cases where the active users cannot measure the state directly. This chapter surveys known results on coding for state dependent channels, with constrained (i.e., rate-limited) and unconstrained side information. Starting from the basic result of Gel'fand & Pinsker, an overview is given on coding for state dependent broadcast and multiple access channels, and some recent results on coding for single and multiuser channels with compressed state information at the encoders.

This chapter describes the main features of multiple-antenna (MIMO) wireless communication. We focus on the special, but by no means trivial, case of a channel with 2 transmit and 2 receive antennas. We aim at providing a simple introduction to more general MIMO channels, as an entry to the literature whose essential bibliography is also provided.

The basic techniques for Orthogonal Frequency Division Multiple Access (OFDMA) in wireless environments are presented. After introducing the main properties of wireless channels, strategies to make use of the multipath propagations are explained. Different methods for channel estimation are described. After-wards, the use of forward error correction coding is motivated and different code classes are considered. Finally, multiple access schemes as well as the use of multiple antennas are discussed.

We present a novel multiple access technique that is based on braided codes (BCs) [1,2,3,4,5]. We called this new orthogonal frequency division multiple access (OFDMA) concept braided code division multiple access (BCDMA). The principle behind the BCDMA concept is characterized for combining in one single scheme a very powerful channel coding technique, sub-carrier interleaving for frequency diversity exploitation and, simultaneously, a multiple access method for a large number of users.

A consistent approach is given to the stability of random-access systems with feedback based on the fact that such systems are generally well modelled by homogeneous Markov chains. The random-access system is stable or unstable according as the Markov chain is stable (ergodic) or unstable (not ergodic). Markov-chain theory, in particular Foster's theorem and Kaplan's converses thereto, provide conditions for stability and instability. Following this approach, it is shown that non-adaptive ALOHA-type algorithms such as pure ALOHA and slotted ALOHA are always unstable. Two important random-access systems based on conflict-resolution protocols, the basic stack algorithm with blocked access and the frugal stack algorithm with blocked access, are analyzed for stability, first in a rudimentary way, then in a precise manner based on a novel solution of the functional recursion describing the system. The precise analysis, while rigorous, employs only elementary mathematics. A by-product of the analysis herein is the formulation of a condition for a homogeneous Markov chain to be unstable that is well adapted for application in random-access systems.

Unlikely to the collision channels with ternary feedback (0 for idle slot, 1 for a slot where exactly one packet was successfully transmitted, and the collision symbol * is for a slot where more then one packets were transmitted and they collided), if the feedback is the multiplicity of the collisions, then the channel can be asymptotically fully utilized. This surprising fact was shown by Pippenger [1] in a probabilistic way. In [2] Ruszinkó and Vanroose gave an explicit algorithm which reaches this optimum. In this chapter we try to pay the attention of the reader how combining results from different branches, e.g., number theory, search theory, probability theory could relatively easily solve this long standing open problem.

We consider some examples of two-user access channels that play a role in information theory. We concentrate on two non-trivial models, the 2-adder and the switching channel model, respectively. For these channel models we discuss the capacity for the feedback and feedback free situation. We also give examples of coding methods that approach or achieve the capacity.

In this presentation, we focus on the study of the multi-access channel from the perspective of a network. Viewed in the context of a wireless network, the multi-access channel exhibits complex behavior with facets that have not been considered before. Specifically, we focus on the issue of delay “stability”, on the distinction between “bits” and “packets”, and on the fact that the notion of a network link is a fuzzy concept that is basically a component of the multi-access channel. We address these issues first in a single-receiver, classic model and then in more general models. We pay special attention to the relay channel model and we introduce the substantial and substantive role played by network coding in a wireless environment.

The collision channel and the slow frequency hopping channel is considered, when the packet communication is done by protocol sequences and hopping sequences. For asynchronous access, tight upper and lower bounds on the best possible sum rates are given. Some code constructions for protocol sequences and hopping sequences are shown.

The Hamming metric is well known in Coding theory. Huge amount of papers are devoted to it. Communication theory needs nevertheless other metrics. In this paper, we describe connections between channels and metrics and give many examples of useful metrics. Construction codes for many of them, invention of fast decoding algorithms are open problems interesting both from theoretical and practical point of view.