A  B  C  D  E  F  G  H  I  J  K  L  M  N  O  P  Q  R  S  T  U  V  W  X  Y  Z  

  Subjects -> ELECTRONICS (Total: 207 journals)
The end of the list has been reached or no journals were found for your choice.
Similar Journals
Journal Cover
Foundations and Trends® in Communications and Information Theory
Journal Prestige (SJR): 2.848
Citation Impact (citeScore): 10
Number of Followers: 6  
 
  Full-text available via subscription Subscription journal
ISSN (Print) 1567-2190 - ISSN (Online) 1567-2328
Published by Now Publishers Inc Homepage  [28 journals]
  • Codes in the Sum-Rank Metric: Fundamentals and Applications

    • Free pre-print version: Loading...

      Abstract: AbstractCodes in the sum-rank metric have attracted significant attention for their applications in distributed storage systems, multishot network coding, streaming over erasure channels, and multi-antenna wireless communication. This monograph provides a tutorial introduction to the theory and applications of sum-rank metric codes over finite fields. At the heart of the monograph is the construction of linearized Reed–Solomon codes, a general construction of maximum sum-rank distance (MSRD) codes with polynomial field sizes. Linearized Reed–Solomon codes specialize to classical Reed– Solomon and Gabidulin code constructions in the Hamming and rank metrics, respectively, and they admit an efficient Welch–Berlekamp decoding algorithm. Applications of these codes in distributed storage systems, network coding, and multi-antenna communication are developed. Other families of codes in the sum-rank metric, including convolutional codes and subfield subcodes are described, and recent results in the general theory of codes in the sum-rank metric are surveyed.Suggested CitationUmberto Martínez-Peñas, Mohannad Shehadeh and Frank R. Kschischang (2022), "Codes in the Sum-Rank Metric: Fundamentals and Applications", Foundations and Trends® in Communications and Information Theory: Vol. 19: No. 5, pp 814-1031. http://dx.doi.org/10.1561/0100000120
      PubDate: Tue, 31 May 2022 00:00:00 +020
       
  • Codes for Distributed Storage

    • Free pre-print version: Loading...

      Abstract: AbstractIn distributed data storage, information pertaining to a given data file is stored across multiple storage units or nodes in redundant fashion to protect against the principal concern, namely, the possibility of data loss arising from the failure of individual nodes. The simplest form of such protection is replication. The explosive growth in the amount of data generated on a daily basis brought up a second major concern, namely minimization of the overhead associated with such redundant storage. This concern led to the adoption by the storage industry of erasure-recovery codes such as Reed- Solomon (RS) codes and more generally, maximum distance separable codes, as these codes offer the lowest-possible storage overhead for a given level of reliability.In the setting of a large data center, where the amount of stored data can run into several exabytes, a third concern arises, namely the need for efficient recovery from a commonplace occurrence, the failure of a single storage unit. One measure of efficiency in node repair is how small one can make the amount of data download needed to repair a failed unit, termed the repair bandwidth. This was the subject of the seminal paper by Dimakis et al. [50] in which an entirely new class of codes called regenerating codes was introduced, that within a certain repair framework, had the minimum-possible repair bandwidth. A second measure relates to the number of helper nodes contacted for node repair, termed the repair degree. A low repair degree is desirable as this means that a smaller number of nodes are impacted by the failure of a given node. The landmark paper by Gopalan et al. [72] focuses on this second measure, leading to the development of the theory of locally recoverable codes. The two events also led to the creation of a third class of codes known as locally regenerating codes, where the aim is to simultaneously achieve reduced repair bandwidth and low repair degree. Research in a different direction led researchers to take a fresh look at the challenge of efficient RS-code repair, and led to the identification of improved repair schemes for RS codes that have significantly reduced repair bandwidth.This monograph introduces the reader to these different approaches towards efficient node repair and presents many of the fundamental bounds and code constructions that have since emerged. Several open problems are identified, and many of the sections have a notes subsection at the end that provides additional background.Suggested CitationVinayak Ramkumar, S. B. Balaji, Birenjith Sasidharan, Myna Vajha, M. Nikhil Krishnan and P. Vijay Kumar (2022), "Codes for Distributed Storage", Foundations and Trends® in Communications and Information Theory: Vol. 19: No. 4, pp 547-813. http://dx.doi.org/10.1561/0100000115
      PubDate: Mon, 30 May 2022 00:00:00 +020
       
  • Rank-Metric Codes and Their Applications

    • Free pre-print version: Loading...

      Abstract: AbstractThe rank metric measures the distance between two matrices by the rank of their difference. Codes designed for the rank metric have attracted considerable attention in recent years, reinforced by network coding and further motivated by a variety of applications. In code-based cryptography, the hardness of the corresponding generic decoding problem can lead to systems with reduced public-key size. In distributed data storage, codes in the rank metric have been used repeatedly to construct codes with locality, and in coded caching, they have been employed for the placement of coded symbols. This survey gives a general introduction to rank-metric codes, explains their most important applications, and highlights their relevance to these areas of research.Suggested CitationHannes Bartz, Lukas Holzbaur, Hedongliang Liu, Sven Puchinger, Julian Renner and Antonia Wachter-Zeh (2022), "Rank-Metric Codes and Their Applications", Foundations and Trends® in Communications and Information Theory: Vol. 19: No. 3, pp 390-546. http://dx.doi.org/10.1561/0100000119
      PubDate: Mon, 02 May 2022 00:00:00 +020
       
  • Common Information, Noise Stability, and Their Extensions

    • Free pre-print version: Loading...

      Abstract: AbstractCommon information is ubiquitous in information theory and related areas such as theoretical computer science and discrete probability. However, because there are multiple notions of common information, a unified understanding of the deep interconnections between them is lacking. This monograph seeks to fill this gap by leveraging a small set of mathematical techniques that are applicable across seemingly disparate problems.In Part I, we review the operational tasks and properties associated with Wyner’s and Gács–Körner–Witsenhausen’s (GKW’s) common information. In Part II, we discuss extensions of the former from the perspective of distributed source simulation. This includes the Rényi common information which forms a bridge between Wyner’s common information and the exact common information. Via a surprising equivalence between the Rényi common information of order ∞ and the exact common information, we demonstrate the existence of a joint source in which the exact common information strictly exceeds Wyner’s common information. Other closely related topics discussed in Part II include the channel synthesis problem and the connection of Wyner’s and exact common information to the nonnegative rank of matrices.In Part III, recognizing that GKW’s common information is zero for most non-degenerate sources, we examine it with a more refined lens via the Non-Interactive Correlation Distillation (NICD) problem in which we quantify the agreement probability of extracted bits from a bivariate source. We extend this to the noise stability problem which includes as special cases the k-user NICD and q-stability problems. This allows us to seamlessly transition to discussing their connections to various conjectures in information theory and discrete probability, such as the Courtade–Kumar, Li– Médard and Mossell–O’Donnell conjectures. Finally, we consider functional inequalities (e.g., the hypercontractivity and Brascamp–Lieb inequalities), which constitute a further generalization of the noise stability problem in which the Boolean functions therein are replaced by nonnnegative functions. We demonstrate that the key ideas behind the proofs in Part III can be presented in a pedagogically coherent manner and unified via information-theoretic and Fourier-analytic methods.Suggested CitationLei Yu and Vincent Y. F. Tan (2022), "Common Information, Noise Stability, and Their Extensions", Foundations and Trends® in Communications and Information Theory: Vol. 19: No. 2, pp 107-389. http://dx.doi.org/10.1561/0100000122
      PubDate: Thu, 28 Apr 2022 00:00:00 +020
       
  • Information-Theoretic Foundations of DNA Data Storage

    • Free pre-print version: Loading...

      Abstract: AbstractDue to its longevity and enormous information density, DNA is an attractive medium for archival data storage. Natural DNA more than 700.000 years old has been recovered, and about 5 grams of DNA can in principle hold a Zetabyte of digital information, orders of magnitude more than what is achieved on conventional storage media. Thanks to rapid technological advances, DNA storage is becoming practically feasible, as demonstrated by a number of experimental storage systems, making it a promising solution for our society’s increasing need of data storage.While in living things, DNA molecules can consist of millions of nucleotides, due to technological constraints, in practice, data is stored on many short DNA molecules, which are preserved in a DNA pool and cannot be spatially ordered. Moreover, imperfections in sequencing, synthesis, and handling, as well as DNA decay during storage, introduce random noise into the system, making the task of reliably storing and retrieving information in DNA challenging.This unique setup raises a natural information-theoretic question: how much information can be reliably stored on and reconstructed from millions of short noisy sequences' The goal of this monograph is to address this question by discussing the fundamental limits of storing information on DNA. Motivated by current technological constraints on DNA synthesis and sequencing, we propose a probabilistic channel model that captures three key distinctive aspects of the DNA storage systems: (1) the data is written onto many short DNA molecules that are stored in an unordered fashion; (2) the molecules are corrupted by noise and (3) the data is read by randomly sampling from the DNA pool. Our goal is to investigate the impact of each of these key aspects on the capacity of the DNA storage system. Rather than focusing on coding-theoretic considerations and computationally efficient encoding and decoding, we aim to build an information-theoretic foundation for the analysis of these channels, developing tools for achievability and converse arguments.Suggested CitationIlan Shomorony and Reinhard Heckel (2022), "Information-Theoretic Foundations of DNA Data Storage", Foundations and Trends® in Communications and Information Theory: Vol. 19: No. 1, pp 1-106. http://dx.doi.org/10.1561/0100000117
      PubDate: Thu, 24 Feb 2022 00:00:00 +010
       
  • Asymptotic Frame Theory for Analog Coding

    • Free pre-print version: Loading...

      Abstract: AbstractOver-complete systems of vectors, or in short, frames, play the role of analog codes in many areas of communication and signal processing. To name a few, spreading sequences for code-division multiple access (CDMA), over-complete representations for multiple-description (MD) source coding, space-time codes, sensing matrices for compressed sensing (CS), and more recently, codes for unreliable distributed computation. In this survey paper we observe an informationtheoretic random-like behavior of frame subsets. Such subframes arise in setups involving erasures (communication), random user activity (multiple access), or sparsity (signal processing), in addition to channel or quantization noise. The goodness of a frame as an analog code is a function of the eigenvalues of a sub-frame, averaged over all subframes (e.g., harmonic mean of the eigenvalues relates to least-square estimation error, while geometric mean to the Shannon transform, and condition number to the restricted isometry property).Within the highly symmetric class of Equiangular Tight Frames (ETF), as well as other “near ETF” families, we show a universal behavior of the empirical eigenvalue distribution (ESD) of a randomly-selected sub-frame: (i) the ESD is asymptotically indistinguishable from Wachter’s MANOVA distribution; and (ii) it exhibits a convergence rate to this limit that is indistinguishable from that of a matrix sequence drawn from MANOVA (Jacobi) ensembles of corresponding dimensions. Some of these results follow from careful statistical analysis of empirical evidence, and some are proved analytically using random matrix theory arguments of independent interest. The goodness measures of the MANOVA limit distribution are better, in a concrete formal sense, than those of the Marchenko–Pastur distribution at the same aspect ratio, implying that deterministic analog codes are better than random (i.i.d.) analog codes. We further give evidence that the ETF (and near ETF) family is in fact superior to any other frame family in terms of its typical sub-frame goodness.Suggested CitationMarina Haikin, Matan Gavish, Dustin G. Mixon and Ram Zamir (2021), "Asymptotic Frame Theory for Analog Coding", Foundations and Trends® in Communications and Information Theory: Vol. 18: No. 4, pp 526-645. http://dx.doi.org/10.1561/0100000125
      PubDate: Thu, 18 Nov 2021 00:00:00 +010
       
  • Modeling and Optimization of Latency in Erasure-coded Storage Systems

    • Free pre-print version: Loading...

      Abstract: AbstractAs consumers are increasingly engaged in social networking and E-commerce activities, businesses grow to rely on Big Data analytics for intelligence, and traditional IT infrastructures continue to migrate to the cloud and edge, these trends cause distributed data storage demand to rise at an unprecedented speed. Erasure coding has seen itself quickly emerged as a promising technique to reduce storage cost while providing similar reliability as replicated systems, widely adopted by companies like Facebook, Microsoft and Google. However, it also brings new challenges in characterizing and optimizing the access latency when data objects are erasure coded in distributed storage. The aim of this monograph is to provide a review of recent progress (both theoretical and practical) on systems that employ erasure codes for distributed storage.In this monograph, we will first identify the key challenges and taxonomy of the research problems and then give an overview of different models and approaches that have been developed to quantify latency of erasure-coded storage. This includes recent work leveraging MDS-Reservation, Fork-Join, Probabilistic, and Delayed-Relaunch scheduling policies, as well as their applications to characterizing access latency (e.g., mean, tail, and asymptotic latency) of erasure-coded distributed storage systems. We will also extend the discussions to video streaming from erasure-coded distributed storage systems. Next, we will bridge the gap between theory and practice, and discuss lessons learned from prototype implementations. In particular, we will discuss exemplary implementations of erasure-coded storage, illuminate key design degrees of freedom and tradeoffs, and summarize remaining challenges in real-world storage systems such as in content delivery and caching. Open problems for future research are discussed at the end of each chapter.Suggested CitationVaneet Aggarwal and Tian Lan (2021), "Modeling and Optimization of Latency in Erasure-coded Storage Systems", Foundations and Trends® in Communications and Information Theory: Vol. 18: No. 3, pp 380-525. http://dx.doi.org/10.1561/0100000108
      PubDate: Wed, 07 Jul 2021 00:00:00 +020
       
  • Redundancy of Lossless Data Compression for Known Sources by Analytic
           Methods

    • Free pre-print version: Loading...

      Abstract: AbstractLossless data compression is a facet of source coding and a well studiedproblem of information theory. Its goal is to find a shortest possiblecode that can be unambiguously recovered. Here, we focus onrigorous analysis of code redundancy for known sources. The redundancyrate problem determines by how much the actual code lengthexceeds the optimal code length. We present precise analyses of threetypes of lossless data compression schemes, namely fixed-to-variable(FV) length codes, variable-to-fixed (VF) length codes, and variableto-variable (VV) length codes. In particular, we investigate the averageredundancy of Shannon, Huffman, Tunstall, Khodak and Bonceletcodes. These codes have succinct representations as trees, either ascoding or parsing trees, and we analyze here some of their parameters(e.g., the average path from the root to a leaf). Such trees areprecisely analyzed by analytic methods, known also as analytic combinatorics,in which complex analysis plays decisive role. These toolsinclude generating functions, Mellin transform, Fourier series, saddlepoint method, analytic poissonization and depoissonization, Tauberiantheorems, and singularity analysis. The term analytic information the-ory has been coined to describe problems of information theory studiedby analytic tools. This approach lies on the crossroad of informationtheory, analysis of algorithms, and combinatorics.Suggested CitationMichael Drmota and Wojciech Szpankowski (2017), "Redundancy of Lossless Data Compression for Known Sources by Analytic Methods", Foundations and Trends® in Communications and Information Theory: Vol. 13: No. 4, pp 277-417. http://dx.doi.org/10.1561/0100000090
      PubDate: Wed, 24 May 2017 00:00:00 +020
       
  • Multiterminal Secrecy by Public Discussion

    • Free pre-print version: Loading...

      Abstract: AbstractThis monograph describes principles of information theoretic secrecygeneration by legitimate parties with public discussion in the presenceof an eavesdropper. The parties are guaranteed secrecy in the form ofindependence from the eavesdropper’s observation of the communication.Part I develops basic technical tools for secrecy generation, many ofwhich are potentially of independent interest beyond secrecy settings.Various information theoretic and cryptographic notions of secrecy arecompared. Emphasis is placed on central themes of interactive communicationand common randomness as well as on core methods ofbalanced coloring and leftover hash for extracting secret uniform randomness.Achievability and converse results are shown to emerge from“single shot” incarnations that serve to explain essential structure.Part II applies the methods of Part I to secrecy generation in twosettings: a multiterminal source model and a multiterminal channelmodel, in both of which the legitimate parties are afforded privilegedaccess to correlated observations of which the eavesdropper has onlypartial knowledge. Characterizations of secret key capacity bring outinherent connections to the data compression concept of omniscienceand, for a specialized source model, to a combinatorial problem of maximalspanning tree packing in a multigraph. Interactive common informationis seen to govern the minimum rate of communication needed toachieve secret key capacity in the two-terminal source model. Furthermore,necessary and sufficient conditions are analyzed for the securecomputation of a given function in the multiterminal source model.Based largely on known recent results, this self-contained monographalso includes new formulations with associated new proofs. Supplementingeach chapter in Part II are descriptions of several openproblems.Suggested CitationPrakash Narayan and Himanshu Tyagi (2016), "Multiterminal Secrecy by Public Discussion", Foundations and Trends® in Communications and Information Theory: Vol. 13: No. 2-3, pp 129-275. http://dx.doi.org/10.1561/0100000072
      PubDate: Wed, 28 Sep 2016 00:00:00 +020
       
  • Channel Coding Methods for Non-Volatile Memories

    • Free pre-print version: Loading...

      Abstract: AbstractNon-volatile memories (NVMs) have emerged as the primary replacement of hard-disk drives for a variety of storage applications, including personal electronics, mobile computing, intelligent vehicles, enterprise storage, data warehousing, and data-intensive computing systems. Channel coding schemes are a necessary tool for ensuring target reliability and performance of NVMs. However, due to operational asymmetries in NVMs, conventional coding approaches – commonly based on designing for the Hamming metric – no longer apply. Given the immediate need for practical solutions and the shortfalls of existing methods, the fast-growing discipline of coding for NVMs has resulted in several key innovations that not only answer the needs of modern storage systems but also directly contribute to the analytical toolbox of coding theory at large. This monograph discusses recent advances in coding for NVMs, covering topics such as error correction coding based on novel algebraic and graph-based methods, rank modulation, rewriting codes, and constrained coding. Our goal for this work is multifold: to illuminate the advantages – as well as challenges – associated with modern NVMs, to present a succinct overview of several exciting recent developments in coding for memories, and, by presenting numerous potential research directions, to inspire other researchers to contribute to this timely and thriving discipline.Suggested CitationLara Dolecek and Frederic Sala (2016), "Channel Coding Methods for Non-Volatile Memories", Foundations and Trends® in Communications and Information Theory: Vol. 13: No. 1, pp 1-128. http://dx.doi.org/10.1561/0100000084
      PubDate: Thu, 25 Feb 2016 00:00:00 +010
       
  • Multi-way Communications: An Information Theoretic Perspective

    • Free pre-print version: Loading...

      Abstract: AbstractMulti-way communication is a means to significantly improve the spectralefficiency of wireless networks. For instance, in a bi-directional (ortwo-way) communication channel, two users can simultaneously usethe transmission medium to exchange information, thus achieving upto twice the rate that would be achieved had each user transmittedseparately. Multi-way communications provides an overview on the developmentsin this research area since it has been initiated by Shannon.The basic two-way communication channel is considered first, followedby the two-way relay channel obtained by the deployment of an additionalcooperative relay node to improve the overall communicationperformance. This basic setup is then extended to multi-user systems.For all these setups, fundamental limits on the achievable rates are reviewed,thereby making use of a linear high-SNR deterministic channelmodel to provide valuable insights which are helpful when discussingthe coding schemes for Gaussian channel models in detail. Several toolsand communication strategies are used in the process, including (butnot limited to) computation, signal-space alignment, and nested-latticecodes. Finally, extensions of multi-way communication channels to multipleantenna settings are discussed.Suggested CitationAnas Chaaban and Aydin Sezgin (2015), "Multi-way Communications: An Information Theoretic Perspective", Foundations and Trends® in Communications and Information Theory: Vol. 12: No. 3-4, pp 185-371. http://dx.doi.org/10.1561/0100000081
      PubDate: Tue, 15 Sep 2015 00:00:00 +020
       
  • An Approximation Approach to Network Information Theory

    • Free pre-print version: Loading...

      Abstract: AbstractThis monograph illustrates a novel approach, which is based on changing the focus to seek approximate solutions accompanied by universal guarantees on the gap to optimality, in order to enable progress on several key open problems in network information theory. We seek universal guarantees that are independent of problem parameters, but perhaps dependent on the problem structure. At the heart of this approach is the development of simple, deterministic models that capture the main features of information sources and communication channels, and are utilized to approximate more complex models. The program advocated in this monograph is to use first seek solutions for the simplified deterministic model and use the insights and the solution of the simplified model to connect it to the original problem. The goal of this deterministic-approximation approach is to obtain universal approximate characterizations of the original channel capacity region and source coding rate regions. The translation of the insights from the deterministic framework to the original problem might need non-trivial steps either in the coding scheme or in the outer bounds. The applications of this deterministic approximation approach are demonstrated in four central problems, namely unicast/multicast relay networks, interference channels, multiple descriptions source coding, and joint source-channel coding over networks. For each of these problems, it is illustrated how the proposed approach can be utilized to approximate the solution and draw engineering insights. Throughout the monograph, many extensions and future directions are addressed, and several open problems are presented in each chapter. The monograph is concluded by illustrating other deterministic models that can be utilized to obtain tighter approximation results, and discussing some recent developments on utilization of deterministic models in multi-flow multi-hop wireless networks.Suggested CitationA. Salman Avestimehr, Suhas N. Diggavi, Chao Tian and David N. C. Tse (2015), "An Approximation Approach to Network Information Theory", Foundations and Trends® in Communications and Information Theory: Vol. 12: No. 1-2, pp 1-183. http://dx.doi.org/10.1561/0100000042
      PubDate: Fri, 04 Sep 2015 00:00:00 +020
       
  • Energy Efficiency in Wireless Networks via Fractional Programming Theory

    • Free pre-print version: Loading...

      Abstract: AbstractThis monograph presents a unified framework for energy efficiency maximization in wireless networks via fractional programming theory. The definition of energy efficiency is introduced, with reference to single-user and multi-user wireless networks, and it is observed how the problem of resource allocation for energy efficiency optimization is naturally cast as a fractional program. An extensive review of the state-of-the-art in energy efficiency optimization by fractional programming is provided, with reference to centralized and distributed resource allocation schemes. A solid background on fractional programming theory is provided. The key-notion of generalized concavity is presented and its strong connection with fractional functions described. A taxonomy of fractional problems is introduced, and for each class of fractional problem, general solution algorithms are described, discussing their complexity and convergence properties. The described theoretical and algorithmic framework is applied to solve energy efficiency maximization problems in practical wireless networks. A general system and signal model is developed which encompasses many relevant special cases, such as one-hop and two-hop heterogeneous networks, multi-cell networks, small-cell networks, device-to-device systems, cognitive radio systems, and hardware-impaired networks, wherein multiple-antennas and multiple subcarriers are (possibly) employed. Energy-efficient resource allocation algorithms are developed, considering both centralized, cooperative schemes, as well as distributed approaches for self-organizing networks. Finally, some remarks on future lines of research are given, stating some open problems that remain to be studied. It is shown how the described framework is general enough to be extended in these directions, proving useful in tackling future challenges that may arise in the design of energy-efficient future wireless networks.Suggested CitationAlessio Zappone and Eduard Jorswieck (2015), "Energy Efficiency in Wireless Networks via Fractional Programming Theory", Foundations and Trends® in Communications and Information Theory: Vol. 11: No. 3-4, pp 185-396. http://dx.doi.org/10.1561/0100000088
      PubDate: Thu, 11 Jun 2015 00:00:00 +020
       
  • Asymptotic Estimates in Information Theory with Non-Vanishing Error
           Probabilities

    • Free pre-print version: Loading...

      Abstract: AbstractThis monograph presents a unified treatment of single- and multi-user problems in Shannon’s information theory where we depart from the requirement that the error probability decays asymptotically in the blocklength. Instead, the error probabilities for various problems are bounded above by a non-vanishing constant and the spotlight is shone on achievable coding rates as functions of the growing blocklengths. This represents the study of asymptotic estimates with non-vanishing error probabilities.In Part I, after reviewing the fundamentals of information theory, we discuss Strassen’s seminal result for binary hypothesis testing where the type-I error probability is non-vanishing and the rate of decay of the type-II error probability with growing number of independent observations is characterized. In Part II, we use this basic hypothesis testing result to develop second- and sometimes, even third-order asymptotic expansions for point-to-point communication. Finally in Part III, we consider network information theory problems for which the second order asymptotics are known. These problems include some classes of channels with random state, the multiple-encoder distributed lossless source coding (Slepian-Wolf) problem and special cases of the Gaussian interference and multiple-access channels. Finally, we discuss avenues for further research.Suggested CitationVincent Y. F. Tan (2014), "Asymptotic Estimates in Information Theory with Non-Vanishing Error Probabilities", Foundations and Trends® in Communications and Information Theory: Vol. 11: No. 1-2, pp 1-184. http://dx.doi.org/10.1561/0100000086
      PubDate: Tue, 23 Sep 2014 00:00:00 +020
       
  • Rate Distortion Bounds for Voice and Video

    • Free pre-print version: Loading...

      Abstract: AbstractNumerous voice, still image, audio, and video compression standards have been developed over the last 25 years, and significant advances in the state of the art have been achieved. However, in the more than 50 years since Shannon’s seminal 1959 paper, no rate distortion bounds for voice and video have been forthcoming. In this volume, we present the first rate distortion bounds for voice and video that actually lower bound the operational rate distortion performance of the best-performing voice and video codecs. The bounds indicate that improvements in rate distortion performance of approximately 50% over the best-performing voice and video codecs are possible. Research directions to improve the new bounds are discussed.Suggested CitationJerry D. Gibson and Jing Hu (2014), "Rate Distortion Bounds for Voice and Video", Foundations and Trends® in Communications and Information Theory: Vol. 10: No. 4, pp 379-514. http://dx.doi.org/10.1561/0100000061
      PubDate: Tue, 18 Feb 2014 00:00:00 +010
       
  • Two-User Gaussian Interference Channels: An Information Theoretic Point of
           View

    • Free pre-print version: Loading...

      Abstract: AbstractThe purpose of this monograph is to introduce both classic and recent capacity theorems for the two-user Gaussian interference channel including both the single-antenna case and the multiple-antenna case.This monograph starts with the single antenna case and introduces the Han and Kobayashi achievable rate region and its various subregions. Several capacity outer bounds are then presented, which, together with the achievable rate region, yields several capacity results for thesingle-antenna Gaussian interference channel, including the capacity region for strong interference and the sum-rate capacity for Z interference, noisy interference, mixed interference and degraded interference.For the more complex multiple-antenna case, the interference state is no longer determined solely by the interference strength as in the single-antenna case. Instead, the structure of the interference in different multi-dimensional subspaces plays an equally important role. As a result of this multiple-dimensional signaling, new interference states including generally strong, generally noisy and generally mixed interference are introduced to obtain capacity theorems that generalize those for the single-antenna case.Suggested CitationXiaohu Shang and Biao Chen (2013), "Two-User Gaussian Interference Channels: An Information Theoretic Point of View", Foundations and Trends® in Communications and Information Theory: Vol. 10: No. 3, pp 247-378. http://dx.doi.org/10.1561/0100000071
      PubDate: Thu, 19 Dec 2013 00:00:00 +010
       
  • Concentration of Measure Inequalities in Information Theory,
           Communications, and Coding

    • Free pre-print version: Loading...

      Abstract: AbstractConcentration inequalities have been the subject of exciting developments during the last two decades, and have been intensively studied and used as a powerful tool in various areas. These include convex geometry, functional analysis, statistical physics, mathematical statistics, pure and applied probability theory (e.g., concentration of measure phenomena in random graphs, random matrices, and percolation), information theory, theoretical computer science, learning theory, and dynamical systems.This monograph focuses on some of the key modern mathematical tools that are used for the derivation of concentration inequalities, on their links to information theory, and on their various applications to communications and coding. In addition to being a survey, this monograph also includes various new recent results derived by the authors.The first part of the monograph introduces classical concentration inequalities for martingales, aswell as some recent refinements and extensions. The power and versatility of the martingale approach is exemplified in the context of codes defined on graphs and iterative decoding algorithms, as well as codes for wireless communication.The second part of the monograph introduces the entropy method, an information-theoretic technique for deriving concentration inequalities for functions of many independent random variables. The basic ingredients of the entropy method are discussed first in conjunction with the closely related topic of logarithmic Sobolev inequalities, which are typical of the so-called functional approach to studying the concentration of measure phenomenon. The discussion on logarithmic Sobolev inequalities is complemented by a related viewpoint based on probability in metric spaces. This viewpoint centers around the so-called transportation-cost inequalities, whose roots are in information theory. Some representative results on concentration for dependent random variables are briefly summarized, with emphasis on their connections to the entropy method. Finally, we discuss several applications of the entropy method and related information-theoretic tools to problems in communications and coding. These include strong converses, empirical distributions of good channel codes with non-vanishing error probability, and an information-theoretic converse for concentration of measure.Suggested CitationMaxim Raginsky and Igal Sason (2013), "Concentration of Measure Inequalities in Information Theory, Communications, and Coding", Foundations and Trends® in Communications and Information Theory: Vol. 10: No. 1-2, pp 1-246. http://dx.doi.org/10.1561/0100000064
      PubDate: Wed, 23 Oct 2013 00:00:00 +020
       
  • Coding Techniques for Repairability in Networked Distributed Storage
           Systems

    • Free pre-print version: Loading...

      Abstract: AbstractThis survey comprises a tutorial on traditional erasure codes and their applications to networked distributed storage systems (NDSS), followed by a survey of novel code families tailor made for better repairability in NDSS.Suggested CitationFrédérique Oggier and Anwitaman Datta (2013), "Coding Techniques for Repairability in Networked Distributed Storage Systems", Foundations and Trends® in Communications and Information Theory: Vol. 9: No. 4, pp 383-466. http://dx.doi.org/10.1561/0100000068
      PubDate: Thu, 06 Jun 2013 00:00:00 +020
       
  • Optimal Resource Allocation in Coordinated Multi-Cell Systems

    • Free pre-print version: Loading...

      Abstract: AbstractThe use of multiple antennas at base stations is a key component in the design of cellular communication systems that can meet high-capacity demands in the downlink. Under ideal conditions, the gain of employing multiple antennas is well-recognized: the data throughput increases linearly with the number of transmit antennas if the spatial dimension is utilized to serve many users in parallel. The practical performance of multi-cell systems is, however, limited by a variety of nonidealities, such as insufficient channel knowledge, high computational complexity, heterogeneous user conditions, limited backhaul capacity, transceiver impairments, and the constrained level of coordination between base stations.This tutorial presents a general framework for modeling different multi-cell scenarios, including clustered joint transmission, coordinated beamforming, interference channels, cognitive radio, and spectrum sharing between operators. The framework enables joint analysis and insights that are both scenario independent and dependent.The performance of multi-cell systems depends on the resource allocation; that is, how the time, power, frequency, and spatial resources are divided among users. A comprehensive characterization of resource allocation problem categories is provided, along with the signal processing algorithms that solve them. The inherent difficulties are revealed: (a) the overwhelming spatial degrees-of-freedom created by the multitude of transmit antennas; and (b) the fundamental tradeoff between maximizing aggregate system throughput and maintaining user fairness. The tutorial provides a pragmatic foundation for resource allocation where the system utility metric can be selected to achieve practical feasibility. The structure of optimal resource allocation is also derived, in terms of beamforming parameterizations and optimal operating points.This tutorial provides a solid ground and understanding for optimization of practical multi-cell systems, including the impact of the nonidealities mentioned above. The Matlab code is available online for some of the examples and algorithms in this tutorial.Suggested CitationEmil Björnson and Eduard Jorswieck (2013), "Optimal Resource Allocation in Coordinated Multi-Cell Systems", Foundations and Trends® in Communications and Information Theory: Vol. 9: No. 2–3, pp 113-381. http://dx.doi.org/10.1561/0100000069
      PubDate: Mon, 28 Jan 2013 00:00:00 +010
       
  • Fundamental Performance Limits in Cross-layer Wireless Optimization:
           Throughput, Delay, and Energy

    • Free pre-print version: Loading...

      Abstract: AbstractIn recent years, one of the most significant developments in both the theory and practice of communication and networking has been the closer coupling between the design of physical-layer functionalities such as coding and modulation, and the design of higher-layer functionalities such as contention resolution and scheduling. This closer coupling is characteristic of the cross-layer paradigm. It is the objective of the present survey to spell out some of the basic challenges, key communication settings, and crucial results, relevant to cross-layer analysis and design for wireless systems. This work focuses primarily on communication settings relevant to wireless cellular communications, where cross-layer design principles have arguably had the greatest impact on practical systems. In order to explore the fundamental performance limits of wireless systems operating under the cross-layer paradigm, the survey shows how information theory and network theory can be leveraged to study issues such as channel modeling, coding, source burstiness, throughput, delay, multi-user interference, multi-path fading, and energy constraints in a more coherent overall analytical and design framework.The survey first examines multiaccess communication channels, the simplest example of a network setting where multiple users share a communication medium. It reviews some of the pioneering work in extending information theory to incorporate source burstiness and queueing. It then examines cross-layer design approaches for multiaccess (uplink) fading channels in wireless communications. The key concepts of stability region, throughput optimality, and delay optimality are introduced. Optimal algorithms which maximize throughput and minimize delay for multiaccess fading channels with random arrivals and queueing are characterized. Next, the survey focuses on a similar setting for communication over broadcast (downlink) fading channels, and introduce relevant results. Finally, it examines the fundamental performance tradeoffs between power and delay in single-user and multi-user communication over wireless channels with energy constraints.Suggested CitationEdmund M. Yeh (2012), "Fundamental Performance Limits in Cross-layer Wireless Optimization: Throughput, Delay, and Energy", Foundations and Trends® in Communications and Information Theory: Vol. 9: No. 1, pp 1-112. http://dx.doi.org/10.1561/0100000014
      PubDate: Mon, 17 Dec 2012 00:00:00 +010
       
  • Polarization and Polar Codes

    • Free pre-print version: Loading...

      Abstract: AbstractThis tutorial treats the fundamentals of polarization theory and polar coding. Arıkan's original results on binary source and channel polarization methods are studied. Error probability and complexity analyses are offered. The original results are generalized in several directions. Early developments in the field are discussed, pointers to some of the important work omitted from this tutorial are given.Suggested CitationEren Şaşoğlu (2012), "Polarization and Polar Codes", Foundations and Trends® in Communications and Information Theory: Vol. 8: No. 4, pp 259-381. http://dx.doi.org/10.1561/0100000041
      PubDate: Thu, 18 Oct 2012 00:00:00 +020
       
  • Block Toeplitz Matrices: Asymptotic Results and Applications

    • Free pre-print version: Loading...

      Abstract: AbstractThe present monograph studies the asymptotic behaviour of eigenvalues, products and functions of block Toeplitz matrices generated by the Fourier coefficients of a continuous matrix-valued function. This study is based on the concept of asymptotically equivalent sequences of non-square matrices. The asymptotic results on block Toeplitz matrices obtained are applied to vector asymptotically wide sense stationary processes. Therefore, this monograph is a generalization to block Toeplitz matrices of the Gray monograph entitled "Toeplitz and circulant matrices: A review", which was published in the second volume of Foundations and Trends in Communications and Information Theory, and which is the simplest and most famous introduction to the asymptotic theory on Toeplitz matrices.Suggested CitationJesús Gutiérrez-Gutiérrez and Pedro M. Crespo (2012), "Block Toeplitz Matrices: Asymptotic Results and Applications", Foundations and Trends® in Communications and Information Theory: Vol. 8: No. 3, pp 179-257. http://dx.doi.org/10.1561/0100000066
      PubDate: Mon, 15 Oct 2012 00:00:00 +020
       
  • Cooperative Wireless Cellular Systems: An Information-Theoretic View

    • Free pre-print version: Loading...

      Abstract: AbstractIn this monograph, the impact of cooperation on the performance of wireless cellular systems is studied from an information-theoretic standpoint, focusing on simple formulations typically referred to as Wynertype models. Following ongoing research and standardization efforts, the text covers two main classes of cooperation strategies. The first class is cooperation at the base station (BS) level, which is also known as Multi-Cell Processing (MCP), network Multiple-Input Multiple-Output (MIMO), or Coordinated Multi-Point transmission/reception (CoMP). With MCP, cooperative decoding, for the uplink, or encoding, for the downlink, is enabled at the BSs. MCP is made possible by the presence of an architecture of, typically wired, backhaul links connecting individual BSs to a central processor (CP) or to one another. The second class of cooperative strategies allows cooperation in the form of relaying for conveying data between Mobile Stations (MSs) and BSs in either the uplink or the downlink. Relaying can be enabled by two possible architectures. A first option is to deploy dedicated Relay Stations (RSs) that are tasked with forwarding uplink or downlink traffic. The second option is for the MSs to act as RSs for other MSs.MCP is first studied under ideal conditions on the backhaul links, namely by assuming that all BSs are connected to a CP with unlimited-capacity links. Both Gaussian (nonfading) and flat-fading channels are analyzed, for the uplink and the downlink, and analytical insights are drawn into the performance advantages of MCP in different relevant operating regimes. Performance comparison is performed with standard Single-Cell Processing (SCP) techniques, whereby each BS decodes, in the uplink, or encodes, in the downlink, independently, as implemented with different spatial reuse factors. Then, practical constraints on the backhaul architecture enabling MCP are introduced. Specifically, three common settings are studied. In the first, all the BSs are connected to a CP via finite-capacity links. In the second, only BSs in adjacent cells are connected via (finite-capacity) backhaul links. In the third, only a subset of BSs is connected to a CP for joint encoding/decoding (clustered cooperation). Achievable rates for the three settings are studied and compared for both the uplink and the downlink.The performance advantages of relaying are analyzed for cellular systems with dedicated RSs and with cooperative MSs. Different techniques are reviewed that require varying degrees of information about system parameters at the MSs, RSs, and BSs. Performance is investigated with both MCP and SCP, revealing a profound interplay between cooperation at the BS level and relaying. Finally, various open problems are pointed out.Suggested CitationOsvaldo Simeone, Nathan Levy, Amichai Sanderovich, Oren Somekh, Benjamin M. Zaidel, H. Vincent Poor and Shlomo Shamai (Shitz) (2012), "Cooperative Wireless Cellular Systems: An Information-Theoretic View", Foundations and Trends® in Communications and Information Theory: Vol. 8: No. 1-2, pp 1-177. http://dx.doi.org/10.1561/0100000048
      PubDate: Fri, 17 Aug 2012 00:00:00 +020
       
  • Random-Set Theory and Wireless Communications

    • Free pre-print version: Loading...

      Abstract: AbstractThis monograph is devoted to random-set theory, which allows unordered collections of random elements, drawn from an arbitrary space, to be handled. After illustrating its foundations, we focus on Random Finite Sets, i.e., unordered collections of random cardinality of points from an arbitrary space, and show how this theory can be applied to a number of problems arising in wireless communication systems. Three of these problems are: (1) neighbor discovery in wireless networks, (2) multiuser detection in which the number of active users is unknown and time-varying, and (3) estimation of multipath channels where the number of paths is not known a priori and which are possibly time-varying. Standard solutions to these problems are intrinsically suboptimum as they proceed either by assuming a fixed number of vector components, or by first estimating this number and then the values taken on by the components. It is shown how random-set theory provides optimum solutions to all these problems. The complexity issue is also examined, and suboptimum solutions are presented and discussed.Suggested CitationEzio Biglieri, Emanuele Grossi and Marco Lops (2012), "Random-Set Theory and Wireless Communications", Foundations and Trends® in Communications and Information Theory: Vol. 7: No. 4, pp 317-462. http://dx.doi.org/10.1561/0100000054
      PubDate: Fri, 17 Aug 2012 00:00:00 +020
       
  • Biometric Security from an Information-Theoretical Perspective

    • Free pre-print version: Loading...

      Abstract: AbstractIn this review, biometric systems are studied from an information theoretical point of view. In the first part biometric authentication systems are studied. The objective of these systems is, observing correlated enrollment and authentication biometric sequences, to generate or convey as large as possible secret keys by interchanging a public message, while minimizing privacy leakage. Here privacy leakage is defined as the amount of information that this public message contains about the biometric enrollment sequence. In this setting also the secrecy leakage, that is, the amount of information the public message leaks about the secret key, should be negligible. Next identification biometric systems are investigated. These systems should be able to identify as many individuals as possible while being able to assign as large as possible secret keys to each individual and again minimize the privacy leakage. To realize these systems public reference data are stored in the database. Leakage is defined with respect to these reference data. For all these biometric systems fundamental limits are determined in the current work. Finally, a popular practical construction for biometric systems, fuzzy commitment, is analyzed with respect to both its theoretical performance and performance related to the code choice.Suggested CitationTanya Ignatenko and Frans M.J. Willems (2012), "Biometric Security from an Information-Theoretical Perspective", Foundations and Trends® in Communications and Information Theory: Vol. 7: No. 2–3, pp 135-316. http://dx.doi.org/10.1561/0100000051
      PubDate: Wed, 15 Feb 2012 00:00:00 +010
       
  • Interference Alignment — A New Look at Signal Dimensions in a
           Communication Network

    • Free pre-print version: Loading...

      Abstract: AbstractThis monograph introduces to the reader the idea of interference alignment, traces its origins, reviews a variety of interference alignment schemes, summarizes the diverse settings where the idea of interference alignment is applicable and highlights the common principles that cut across these diverse applications. The focus is on theoretical aspects.Suggested CitationSyed A. Jafar (2011), "Interference Alignment — A New Look at Signal Dimensions in a Communication Network", Foundations and Trends® in Communications and Information Theory: Vol. 7: No. 1, pp 1-134. http://dx.doi.org/10.1561/0100000047
      PubDate: Thu, 30 Jun 2011 00:00:00 +020
       
  • Raptor Codes

    • Free pre-print version: Loading...

      Abstract: AbstractThis monograph describes the theory behind Raptor codes, and elucidates elements of the processes behind the design of two of the most prominent members of this class of codes: R10 and RaptorQ (RQ). R10 has already been adopted by a number of standards' bodies, and RQ is in the process of entering various standards at the time of writing of this monograph.The monograph starts with the description of some of the transmission problems, which inspired the invention of Fountain codes. Thereafter, Luby transform codes (LT codes) and Raptor codes are introduced and insights are provided into their design. These codes are currently the most efficient realizations of Fountain codes. Different algorithms are introduced for encoding and decoding various versions of these codes, including their systematic versions. Moreover, a hybrid decoding algorithm called "inactivation decoding" is introduced, which is an integral part of all modern implementations of Raptor codes.The R10 and RQ codes have been continued and will continue to be adopted into a number of standards and thus there are publicly available specifications that describe exactly how to implement these codes. However, the standards' specifications provide no insight into the rationale for the design choices made. One of the primary purposes of this document is to provide this design rationale.We provide results of extensive simulations of R10 and RQ codes to show the behavior of these codes in many different scenarios.Suggested CitationAmin Shokrollahi and Michael Luby (2011), "Raptor Codes", Foundations and Trends® in Communications and Information Theory: Vol. 6: No. 3–4, pp 213-322. http://dx.doi.org/10.1561/0100000060
      PubDate: Wed, 18 May 2011 00:00:00 +020
       
  • Statistical Physics and Information Theory

    • Free pre-print version: Loading...

      Abstract: AbstractThis monograph is based on lecture notes of a graduate course, which focuses on the relations between information theory and statistical physics. The course was delivered at the Technion during the Spring of 2010 for the first time, and its target audience consists of EE graduate students in the area of communications and information theory, as well as graduate students in Physics who have basic background in information theory. Strong emphasis is given to the analogy and parallelism between information theory and statistical physics, as well as to the insights, the analysis tools and techniques that can be borrowed from statistical physics and 'imported' to certain problem areas in information theory. This is a research trend that has been very active in the last few decades, and the hope is that by exposing the students to the meeting points between these two disciplines, their background and perspective may be expanded and enhanced. This monograph is substantially revised and expanded relative to an earlier version posted in arXiv (1006.1565v1 [cs.iT]).Suggested CitationNeri Merhav (2010), "Statistical Physics and Information Theory", Foundations and Trends® in Communications and Information Theory: Vol. 6: No. 1–2, pp 1-212. http://dx.doi.org/10.1561/0100000052
      PubDate: Mon, 13 Dec 2010 00:00:00 +010
       
  • Combinatorial Designs for Authentication and Secrecy Codes

    • Free pre-print version: Loading...

      Abstract: AbstractCombinatorial design theory is a very active area of mathematical research, with many applications in communications and information theory, computer science, statistics, engineering, and life sciences. As one of the fundamental discrete structures, combinatorial designs are used in fields as diverse as error-correcting codes, statistical design of experiments, cryptography and information security, mobile and wireless communications, group testing algorithms in DNA screening, software and hardware testing, and interconnection networks. This monograph provides a tutorial on combinatorial designs, which gives an overview of the theory. Furthermore, the application of combinatorial designs to authentication and secrecy codes is described in depth. This close relationship of designs with cryptography and information security was first revealed in Shannon's seminal paper on secrecy systems. We bring together in one source foundational and current contributions concerning design-theoretic constructions and characterizations of authentication and secrecy codes.Suggested CitationMichael Huber (2010), "Combinatorial Designs for Authentication and Secrecy Codes", Foundations and Trends® in Communications and Information Theory: Vol. 5: No. 6, pp 581-675. http://dx.doi.org/10.1561/0100000044
      PubDate: Sun, 30 May 2010 00:00:00 +020
       
  • Information Theoretic Security

    • Free pre-print version: Loading...

      Abstract: AbstractThe topic of information theoretic security is introduced and the principal results in this area are reviewed. The basic wire-tap channel model is considered first, and then several specific types of wire-tap channels are considered, including Gaussian, multi-input multi-output (MIMO), compound, and feedback wire-tap channels, as well as the wire-tap channel with side information. Practical code design techniques to achieve secrecy for wire-tap channels are also introduced. The wire-tap formalism is then extended to the basic channels of multi-user networks, including broadcast channels, multiple-access channels (MACs), interference channels, relay channels and two-way channels. For all of these models, results on the fundamental communication limits under secrecy constraints and corresponding coding schemes are reviewed. Furthermore, several related topics including key agreement through common randomness, secure network coding, authentication, cross-layer design, and secure source coding are discussed.Suggested CitationYingbin Liang, H. Vincent Poor and Shlomo Shamai (Shitz) (2009), "Information Theoretic Security", Foundations and Trends® in Communications and Information Theory: Vol. 5: No. 4–5, pp 355-580. http://dx.doi.org/10.1561/0100000036
      PubDate: Mon, 15 Jun 2009 00:00:00 +020
       
  • Universal Estimation of Information Measures for Analog Sources

    • Free pre-print version: Loading...

      Abstract: AbstractThis monograph presents an overview of universal estimation of information measures for continuous-alphabet sources. Special attention is given to the estimation of mutual information and divergence based on independent and identically distributed (i.i.d.) data. Plug-in methods, partitioning-based algorithms, nearest-neighbor algorithms as well as other approaches are reviewed, with particular focus on consistency, speed of convergence and experimental performance.Suggested CitationQing Wang, Sanjeev R. Kulkarni and Sergio Verdú (2009), "Universal Estimation of Information Measures for Analog Sources", Foundations and Trends® in Communications and Information Theory: Vol. 5: No. 3, pp 265-353. http://dx.doi.org/10.1561/0100000021
      PubDate: Wed, 27 May 2009 00:00:00 +020
       
  • Bit-Interleaved Coded Modulation

    • Free pre-print version: Loading...

      Abstract: AbstractThe principle of coding in the signal space follows directly from Shannon's analysis of waveform Gaussian channels subject to an input constraint. The early design of communication systems focused separately on modulation, namely signal design and detection, and error correcting codes, which deal with errors introduced at the demodulator of the underlying waveform channel. The correct perspective of signal-space coding, although never out of sight of information theorists, was brought back into the focus of coding theorists and system designers by Imai's and Ungerböck's pioneering works on coded modulation. More recently, powerful families of binary codes with a good tradeoff between performance and decoding complexity have been (re-)discovered. Bit-Interleaved Coded Modulation (BICM) is a pragmatic approach combining the best out of both worlds: it takes advantage of the signal-space coding perspective, whilst allowing for the use of powerful families of binary codes with virtually any modulation format. BICM avoids the need for the complicated and somewhat less flexible design typical of coded modulation. As a matter of fact, most of today's systems that achieve high spectral efficiency such as DSL, Wireless LANs, WiMax and evolutions thereof, as well as systems based on low spectral efficiency orthogonal modulation, feature BICM, making BICM the de-facto general coding technique for waveform channels.The theoretical characterization of BICM is at the basis of efficient coding design techniques and also of improved BICM decoders, e.g., those based on the belief propagation iterative algorithm and approximations thereof. In this text, we review the theoretical foundations of BICM under the unified framework of error exponents for mismatched decoding. This framework allows an accurate analysis without any particular assumptions on the length of the interleaver or independence between the multiple bits in a symbol. We further consider the sensitivity of the BICM capacity with respect to the signal-to-noise ratio (SNR), and obtain a wideband regime (or low-SNR regime) characterization. We review efficient tools for the error probability analysis of BICM that go beyond the standard approach of considering infinite interleaving and take into consideration the dependency of the coded bit observations introduced by the modulation. We also present bounds that improve upon the union bound in the region beyond the cutoff rate, and are essential to characterize the performance of modern randomlike codes used in concatenation with BICM. Finally, we turn our attention to BICM with iterative decoding, we review extrinsic information transfer charts, the area theorem and code design via curve fitting. We conclude with an overview of some applications of BICM beyond the classical coherent Gaussian channel.Suggested CitationAlbert Guillén i Fàbregas, Alfonso Martinez and Giuseppe Caire (2008), "Bit-Interleaved Coded Modulation", Foundations and Trends® in Communications and Information Theory: Vol. 5: No. 1–2, pp 1-153. http://dx.doi.org/10.1561/0100000019
      PubDate: Sun, 30 Nov 2008 00:00:00 +010
       
  • Channel Coding in the Presence of Side Information

    • Free pre-print version: Loading...

      Abstract: AbstractIn this survey we review the concepts and methods of communication systems equipped with side information. We focus on the channel coding problem, where side information is available to the transmitter in either a causal or non-causal manner, and we also consider the source coding problem with side information at the receiver.We first summarize the main results for channels with causal/non-causal side information and the associated capacity formulas. Next, we consider specific channel models, such as Costa's dirty-paper model, the AWGN channel model with fading and the modulo additive noise channel. Further, we provide applications to the models considered here, in particular, we present the watermarking problem and the Gaussian MIMO broadcast channel. We also consider algorithms for the calculation of the channel's capacity, and practical coding schemes for the communication systems explored in this survey. Finally, we study several related information-theoretic problems and present both the Wyner–Ziv and the Slepian–Wolf problems. The source coding problems and the channel coding problems, are presented in a unified version and the duality between the problems is presented. We also present extensions for the MAC and broadcast channel models, to the case where they are controlled by a state process, and consider several hybrid models, e.g., joint source–channel coding for the Wyner–Ziv source and the Gel'fand–Pinsker channel, and the achievable tradeoff between the message and the state information rates.Suggested CitationGuy Keshet, Yossef Steinberg and Neri Merhav (2008), "Channel Coding in the Presence of Side Information", Foundations and Trends® in Communications and Information Theory: Vol. 4: No. 6, pp 445-586. http://dx.doi.org/10.1561/0100000025
      PubDate: Wed, 25 Jun 2008 00:00:00 +020
       
  • Topics in Multi-User Information Theory

    • Free pre-print version: Loading...

      Abstract: AbstractThis survey reviews fundamental concepts of multi-user information theory. Starting with typical sequences, the survey builds up knowledge on random coding, binning, superposition coding, and capacity converses by introducing progressively more sophisticated tools for a selection of source and channel models. The problems addressed include: Source Coding; Rate-Distortion and Multiple Descriptions; Capacity-Cost; The Slepian–Wolf Problem; The Wyner-Ziv Problem; The Gelfand-Pinsker Problem; The Broadcast Channel; The Multiaccess Channel; The Relay Channel; The Multiple Relay Channel; and The Multiaccess Channel with Generalized Feedback. The survey also includes a review of basic probability and information theory.Suggested CitationGerhard Kramer (2008), "Topics in Multi-User Information Theory", Foundations and Trends® in Communications and Information Theory: Vol. 4: No. 4–5, pp 265-444. http://dx.doi.org/10.1561/0100000028
      PubDate: Wed, 25 Jun 2008 00:00:00 +020
       
  • Reliability Criteria in Information Theory and in Statistical Hypothesis
           Testing

    • Free pre-print version: Loading...

      Abstract: AbstractThis survey is devoted to one of the central problems of Information Theory — the problem of determination of interdependence between coding rate and error probability exponent for different information transmission systems. The overview deals with memoryless systems of finite alphabet setting. It presents material complementary to the contents of the series of the most remarkable in Information Theory books of Feinstain, Fano, Wolfowitz, Gallager, Csiszar and Körner, Kolesnik and Poltirev, Blahut, Cover and Thomas and of the papers by Dobrushin, Gelfand and Prelov.We briefly formulate fundamental notions and results of Shannon theory on reliable transmission via coding and give a survey of results obtained in last two-three decades by the authors, their colleagues and some other researchers. The paper is written with the goal to make accessible to a broader circle of readers the theory of rate-reliability. We regard this concept useful to promote the noted problem solution in parallel with elaboration of the notion of reliability-reliability dependence relative to the statistical hypothesis testing and identification.Suggested CitationEvgueni A. Haroutunian, Mariam E. Haroutunian and Ashot N. Harutyunyan (2008), "Reliability Criteria in Information Theory and in Statistical Hypothesis Testing", Foundations and Trends® in Communications and Information Theory: Vol. 4: No. 2–3, pp 97-263. http://dx.doi.org/10.1561/0100000008
      PubDate: Thu, 28 Feb 2008 00:00:00 +010
       
  • Cyclic Division Algebras: A Tool for Space–Time Coding

    • Free pre-print version: Loading...

      Abstract: AbstractMultiple antennas at both the transmitter and receiver ends of a wireless digital transmission channel may increase both data rate and reliability. Reliable high rate transmission over such channels can only be achieved through Space–Time coding. Rank and determinant code design criteria have been proposed to enhance diversity and coding gain. The special case of full-diversity criterion requires that the difference of any two distinct codewords has full rank.Extensive work has been done on Space–Time coding, aiming at finding fully diverse codes with high rate. Division algebras have been proposed as a new tool for constructing Space–Time codes, since they are non-commutative algebras that naturally yield linear fully diverse codes. Their algebraic properties can thus be further exploited to improve the design of good codes.The aim of this work is to provide a tutorial introduction to the algebraic tools involved in the design of codes based on cyclic division algebras. The different design criteria involved will be illustrated, including the constellation shaping, the information lossless property, the non-vanishing determinant property, and the diversity multiplexing trade-off. The final target is to give the complete mathematical background underlying the construction of the Golden code and the other Perfect Space–Time block codes.Suggested CitationFrédérique Oggier, Jean-Claude Belfiore and Emanuele Viterbo (2007), "Cyclic Division Algebras: A Tool for Space–Time Coding", Foundations and Trends® in Communications and Information Theory: Vol. 4: No. 1, pp 1-95. http://dx.doi.org/10.1561/0100000016
      PubDate: Fri, 16 Nov 2007 00:00:00 +010
       
  • Majorization and Matrix-Monotone Functions in Wireless Communications

    • Free pre-print version: Loading...

      Abstract: AbstractThis short tutorial presents two mathematical techniques namely Majorization Theory and Matrix-Monotone Functions, reviews their basic definitions and describes their concepts clearly with many illustrative examples. In addition to this tutorial, new results are presented with respect to Schur-convex functions and regarding the properties of matrix-monotone functions.The techniques are applied to solve communication and information theoretic problems in wireless communications. The impact of spatial correlation in multiple antenna systems is characterized for many important performance measures, e.g., average mutual information, outage probability, error performance, minimum $\farc{E_{b}}{N_{0}}$ and wideband slope, zero-outage capacity, and capacity region. The impact of user distribution in cellular systems is characterized for different scenarios including perfectly informed transmitters and receivers, regarding, e.g., the average sum rate, the outage sum rate, maximum throughput. Finally, a unified framework for the performance analysis of multiple antenna systems is developed based on matrix-monotone functions. The optimization of transmit strategies for multiple antennas is carried out by optimization of matrix-monotone functions. The results within this framework resemble and complement the various results on optimal transmit strategies in single-user and multiple-user multiple-antenna systems.Suggested CitationEduard Jorswieck and Holger Boche (2007), "Majorization and Matrix-Monotone Functions in Wireless Communications", Foundations and Trends® in Communications and Information Theory: Vol. 3: No. 6, pp 553-701. http://dx.doi.org/10.1561/0100000026
      PubDate: Mon, 09 Jul 2007 00:00:00 +020
       
  • MIMO Transceiver Design via Majorization Theory

    • Free pre-print version: Loading...

      Abstract: Multiple-input multiple-output (MIMO) channels provide an abstract and unified representation of different physical communication systems, ranging from multi-antenna wireless channels to wireless digital subscriber line systems. They have the key property that several data streams can be simultaneously established.In general, the design of communication systems for MIMO channels is quite involved (if one can assume the use of sufficiently long and good codes, then the problem formulation simplifies drastically). The first difficulty lies on how to measure the global performance of such systems given the tradeoff on the performance among the different data streams. Once the problem formulation is defined, the resulting mathematical problem is typically too complicated to be optimally solved as it is a matrix-valued nonconvex optimization problem. This design problem has been studied for the past three decades (the first papers dating back to the 1970s) motivated initially by cable systems and more recently by wireless multi-antenna systems. The approach was to choose a specific global measure of performance and then to design the system accordingly, either optimally or suboptimally, depending on the difficulty of the problem.This text presents an up-to-date unified mathematical framework for the design of point-to-point MIMO transceivers with channel state information at both sides of the link according to an arbitrary cost function as a measure of the system performance. In addition, the framework embraces the design of systems with given individual performance on the data streams.Majorization theory is the underlying mathematical theory on which the framework hinges. It allows the transformation of the originally complicated matrix-valued nonconvex problem into a simple scalar problem. In particular, the additive majorization relation plays a key role in the design of linear MIMO transceivers (i.e., a linear precoder at the transmitter and a linear equalizer at the receiver), whereas the multiplicative majorization relation is the basis for nonlinear decision-feedback MIMO transceivers (i.e., a linear precoder at the transmitter and a decision-feedback equalizer at the receiver).Suggested CitationDaniel P. Palomar and Yi Jiang (2007), "MIMO Transceiver Design via Majorization Theory", Foundations and Trends® in Communications and Information Theory: Vol. 3: No. 4-5, pp 331-551. http://dx.doi.org/10.1561/0100000018
      PubDate: Sun, 10 Jun 2007 00:00:00 +020
       
  • Information Combining

    • Free pre-print version: Loading...

      Abstract: AbstractConsider coded transmission over a binary-input symmetric memoryless channel. The channel decoder uses the noisy observations of the code symbols to reproduce the transmitted code symbols. Thus, it combines the information about individual code symbols to obtain an overall information about each code symbol, which may be the reproduced code symbol or its a-posteriori probability. This tutorial addresses the problem of "information combining" from an information-theory point of view: the decoder combines the mutual information between channel input symbols and channel output symbols (observations) to the mutual information between one transmitted symbol and all channel output symbols. The actual value of the combined information depends on the statistical structure of the channels. However, it can be upper and lower bounded for the assumed class of channels. This book first introduces the concept of mutual information profiles and revisits the well-known Jensen's inequality. Using these tools, the bounds on information combining are derived for single parity-check codes and for repetition codes. The application of the bounds is illustrated in four examples: information processing characteristics of coding schemes, including extrinsic information transfer (EXIT) functions; design of multiple turbo codes; bounds for the decoding threshold of low-density parity-check codes; EXIT function of the accumulator.Suggested CitationIngmar Land and Johannes Huber (2006), "Information Combining", Foundations and Trends® in Communications and Information Theory: Vol. 3: No. 3, pp 227-330. http://dx.doi.org/10.1561/0100000013
      PubDate: Thu, 30 Nov 2006 00:00:00 +010
       
  • Performance Analysis of Linear Codes under Maximum-Likelihood Decoding: A
           Tutorial

    • Free pre-print version: Loading...

      Abstract: AbstractThis article is focused on the performance evaluation of linear codes under optimal maximum-likelihood (ML) decoding. Though the ML decoding algorithm is prohibitively complex for most practical codes, their performance analysis under ML decoding allows to predict their performance without resorting to computer simulations. It also provides a benchmark for testing the sub-optimality of iterative (or other practical) decoding algorithms. This analysis also establishes the goodness of linear codes (or ensembles), determined by the gap between their achievable rates under optimal ML decoding and information theoretical limits. In this article, upper and lower bounds on the error probability of linear codes under ML decoding are surveyed and applied to codes and ensembles of codes on graphs. For upper bounds, we discuss various bounds where focus is put on Gallager bounding techniques and their relation to a variety of other reported bounds. Within the class of lower bounds, we address de Caen's based bounds and their improvements, and also consider sphere-packing bounds with their recent improvements targeting codes of moderate block lengths.Suggested CitationIgal Sason and Shlomo Shamai (2006), "Performance Analysis of Linear Codes under Maximum-Likelihood Decoding: A Tutorial", Foundations and Trends® in Communications and Information Theory: Vol. 3: No. 1–2, pp 1-222. http://dx.doi.org/10.1561/0100000009
      PubDate: Fri, 07 Jul 2006 00:00:00 +020
       
  • QoS-Based Resource Allocation and Transceiver Optimization

    • Free pre-print version: Loading...

      Abstract: The control and reduction of multiuser interference is a fundamental problem in wireless communications. In order to increase the spectral efficiency and to provide individual quality-of-service (QoS), it is required to jointly optimize the power allocation together with possible receive and transmit strategies. This often leads to complex and difficult-to-handle problem formulations. There are many examples in the literature, where the special structure of the problem is exploited in order to solve special cases of this problem (e.g. multiuser beamforming or CDMA). So it is desirable to have a general theory, which can be applied to many practical QoS measures, like rates, delay, BER, etc. These measures can all be related to the signal-to-interference ratio (SIR) or the signal-to-interference-plus-noise ratio (SINR). This leads to the problem of SIR and SINR balancing, which is fundamental for many problems in communication theory.In this text we derive a comprehensive theoretical framework for SIR balancing, with and without noise. The theory considers the possible use of receive strategies (e.g. interference filtering or channel assignment), which can be included in the model in an abstract way. Power allocation and receiver design are mutually interdependent, thus joint optimization strategies are derived. The main purpose of this text is to provide a better understanding of interference balancing and the characterization of the QoS feasible region. We also provide a generic algorithmic framework, which may serve as a basis for the development of new resource allocation algorithms.We study different interference models, which are general enough to be valid for a wide range of system designs, but which are also specific enough to facilitate efficient algorithmic solutions. One important class of interference functions is based on axioms, which characterize the impact of the power allocation of the interference received by the individual users. Another class of interference functions is based on non-negative coupling matrices, which may be parameter-dependent in order to model the possible impact of receive strategies. Both models are studied with and without noise. We analyze the resulting QoS feasible region (the set of jointly achievable QoS) and discuss different allocation strategies for min-max fairness and sum-power minimization. Finally we study geometrical properties of the QoS region, which can be shown to be convex for log-convex interference functions.Suggested CitationMartin Schubert and Holger Boche (2006), "QoS-Based Resource Allocation and Transceiver Optimization", Foundations and Trends® in Communications and Information Theory: Vol. 2: No. 6, pp 383-529. http://dx.doi.org/10.1561/0100000010
      PubDate: Fri, 07 Jul 2006 00:00:00 +020
       
  • Network Coding Theory Part II: Multiple Source

    • Free pre-print version: Loading...

      Abstract: AbstractStore-and-forward had been the predominant technique for transmitting information through a network until its optimality was refuted by network coding theory. Network coding offers a new paradigm for network communications and has generated abundant research interest in information and coding theory, networking, switching, wireless communications, cryptography, computer science, operations research, and matrix theory.In this issue we review network coding theory for the scenario when there are multiple source nodes each intending to transmit to a different set of destination nodes.A companion issue reviews the foundational work that has led to the development of network coding theory and discusses the theory for the transmission from a single source node to other nodes in the network.Suggested CitationRaymond W. Yeung, Shuo-Yen Robert Li, Ning Cai and Zhen Zhang (2006), "Network Coding Theory Part II: Multiple Source", Foundations and Trends® in Communications and Information Theory: Vol. 2: No. 5, pp 330-381. http://dx.doi.org/10.1561/0100000007II
      PubDate: Fri, 07 Jul 2006 00:00:00 +020
       
  • Network Coding Theory Part I: Single Source

    • Free pre-print version: Loading...

      Abstract: AbstractStore-and-forward had been the predominant technique for transmitting information through a network until its optimality was refuted by network coding theory. Network coding offers a new paradigm for network communications and has generated abundant research interest in information and coding theory, networking, switching, wireless communications, cryptography, computer science, operations research, and matrix theory.We review the foundational work that has led to the development of network coding theory and discuss the theory for the transmission from a single source node to other nodes in the network. A companion issue discusses the theory when there are multiple source nodes each intending to transmit to a different set of destination nodes.Suggested CitationRaymond W. Yeung, Shuo-Yen Robert Li, Ning Cai and Zhen Zhang (2006), "Network Coding Theory Part I: Single Source", Foundations and Trends® in Communications and Information Theory: Vol. 2: No. 4, pp 241-329. http://dx.doi.org/10.1561/0100000007I
      PubDate: Fri, 07 Jul 2006 00:00:00 +020
       
  • Toeplitz and Circulant Matrices: A Review

    • Free pre-print version: Loading...

      Abstract: AbstractThe fundamental theorems on the asymptotic behavior of eigenvalues, inverses, and products of banded Toeplitz matrices and Toeplitz matrices with absolutely summable elements are derived in a tutorial manner. Mathematical elegance and generality are sacrificed for conceptual simplicity and insight in the hope of making these results available to engineers lacking either the background or endurance to attack the mathematical literature on the subject. By limiting the generality of the matrices considered, the essential ideas and results can be conveyed in a more intuitive manner without the mathematical machinery required for the most general cases. As an application the results are applied to the study of the covariance matrices and their factors of linear models of discrete time random processes.Suggested CitationRobert M. Gray (2006), "Toeplitz and Circulant Matrices: A Review", Foundations and Trends® in Communications and Information Theory: Vol. 2: No. 3, pp 155-239. http://dx.doi.org/10.1561/0100000006
      PubDate: Tue, 31 Jan 2006 00:00:00 +010
       
  • Geometric Programming for Communication Systems

    • Free pre-print version: Loading...

      Abstract: AbstractGeometric Programming (GP) is a class of nonlinear optimization with many useful theoretical and computational properties. Over the last few years, GP has been used to solve a variety of problems in the analysis and design of communication systems in several 'layers' in the communication network architecture, including information theory problems, signal processing algorithms, basic queuing system optimization, many network resource allocation problems such as power control and congestion control, and cross-layer design. We also start to understand why, in addition to how, GP can be applied to a surprisingly wide range of problems in communication systems. These applications have in turn spurred new research activities on GP, especially generalizations of GP formulations and development of distributed algorithms to solve GP in a network. This text provides both an in-depth tutorial on the theory, algorithms, and modeling methods of GP, and a comprehensive survey on the applications of GP to the study of communication systems.Suggested CitationMung Chiang (2005), "Geometric Programming for Communication Systems", Foundations and Trends® in Communications and Information Theory: Vol. 2: No. 1–2, pp 1-154. http://dx.doi.org/10.1561/0100000005
      PubDate: Fri, 15 Jul 2005 00:00:00 +020
       
  • Information Theory and Statistics: A Tutorial

    • Free pre-print version: Loading...

      Abstract: AbstractThis tutorial is concerned with applications of information theory concepts in statistics, in the finite alphabet setting. The information measure known as information divergence or Kullback-Leibler distance or relative entropy plays a key role, often with a geometric flavor as an analogue of squared Euclidean distance, as in the concepts of I-projection, I-radius and I-centroid. The topics covered include large deviations, hypothesis testing, maximum likelihood estimation in exponential families, analysis of contingency tables, and iterative algorithms with an "information geometry" background. Also, an introduction is provided to the theory of universal coding, and to statistical inference via the minimum description length principle motivated by that theory.Suggested CitationI. Csiszár and P.C. Shields (2004), "Information Theory and Statistics: A Tutorial", Foundations and Trends® in Communications and Information Theory: Vol. 1: No. 4, pp 417-528. http://dx.doi.org/10.1561/0100000004
      PubDate: Wed, 15 Dec 2004 00:00:00 +010
       
  • Algebraic Number Theory and Code Design for Rayleigh Fading Channels

    • Free pre-print version: Loading...

      Abstract: AbstractAlgebraic number theory is having an increasing impact in code design for many different coding applications, such as single antenna fading channels and more recently, MIMO systems.Extended work has been done on single antenna fading channels, and algebraic lattice codes have been proven to be an effective tool. The general framework has been settled in the last ten years and many explicit code constructions based on algebraic number theory are now available.The aim of this work is to provide both an overview on algebraic lattice code designs for Rayleigh fading channels, as well as a tutorial introduction to algebraic number theory. The basic facts of this mathematical field will be illustrated by many examples and by the use of a computer algebra freeware in order to make it more accessible to a large audience.Suggested CitationF. Oggier and E. Viterbo (2004), "Algebraic Number Theory and Code Design for Rayleigh Fading Channels", Foundations and Trends® in Communications and Information Theory: Vol. 1: No. 3, pp 333-415. http://dx.doi.org/10.1561/0100000003
      PubDate: Tue, 14 Dec 2004 00:00:00 +010
       
  • Transmission and Reception with Multiple Antennas: Theoretical Foundations

    • Free pre-print version: Loading...

      Abstract: AbstractWireless communication system design was until recently thought to have been limited in practice by time and bandwidth. The discovery that space, obtained by increasing the number of transmit and receive antennas, can also effectively generate degrees of freedom, and hence expand the range of choices made available to the design offers system designers important new opportunities. This paper focuses on the main aspects of single-user multiple-antenna theory, with the goal of presenting a comprehensive, yet compact, survey, emphasizing its mathematical aspects. After describing channel models, we compute the capacities they achieve, we briefly overview "space-time" codes, and we describe how suboptimum architectures can be employed to simplify the receiver.Suggested CitationE. Biglieri and G. Taricco (2004), "Transmission and Reception with Multiple Antennas: Theoretical Foundations", Foundations and Trends® in Communications and Information Theory: Vol. 1: No. 2, pp 183-332. http://dx.doi.org/10.1561/0100000002
      PubDate: Wed, 01 Sep 2004 00:00:00 +020
       
  • Random Matrix Theory and Wireless Communications

    • Free pre-print version: Loading...

      Abstract: AbstractRandom matrix theory has found many applications in physics, statistics and engineering since its inception. Although early developments were motivated by practical experimental problems, random matrices are now used in fields as diverse as Riemann hypothesis, stochastic differential equations, condensed matter physics, statistical physics, chaotic systems, numerical linear algebra, neural networks, multivariate statistics, information theory, signal processing and small-world networks. This article provides a tutorial on random matrices which provides an overview of the theory and brings together in one source the most significant results recently obtained. Furthermore, the application of random matrix theory to the fundamental limits of wireless communication channels is described in depth.Suggested CitationAntonia M. Tulino and Sergio Verdú (2004), "Random Matrix Theory and Wireless Communications", Foundations and Trends® in Communications and Information Theory: Vol. 1: No. 1, pp 1-182. http://dx.doi.org/10.1561/0100000001
      PubDate: Mon, 28 Jun 2004 00:00:00 +020
       
 
JournalTOCs
School of Mathematical and Computer Sciences
Heriot-Watt University
Edinburgh, EH14 4AS, UK
Email: journaltocs@hw.ac.uk
Tel: +00 44 (0)131 4513762
 


Your IP address: 44.200.137.63
 
Home (Search)
API
About JournalTOCs
News (blog, publications)
JournalTOCs on Twitter   JournalTOCs on Facebook

JournalTOCs © 2009-