Optimal Age over Erasure Channels

Given a source that produces a letter every T-s seconds and an erasure channel that can be used every T-c seconds, we ask what is the coding strategy that minimizes the time-average "age of information" that an observer of the channel output incurs. We will see that one has to distinguish the cases when the source and channel-input alphabets have equal or different size. In the first case, we show that a trivial coding strategy is optimal and a closed form expression for the age may be derived. In the second, we use random coding argument to bound the average age and show that the average age achieved using random codes converges to the optimal average age as the source alphabet becomes large.

Linear Universal Decoder for Compound Discrete Memoryless Channels

Rethnakaran Pulikkoonattu

Shannon in his seminal work \cite{paper:shannon} formalized the framework on the problem of digital communication of information and storage. He quantified the fundamental limits of compression and transmission rates. The quantity \textit{channel capacity} was coined to give an operational meaning on the ultimate limit of information transfer between two entities, transmitter and receiver. By using a random coding argument, he showed the achievability of reliable communication on any noisy channel as long as the rate is less than the channel capacity. More precisely, he argued that, using a fixed composition random codebook at the sender and a maximum likelihood decoder in the receiver, one can achieve almost zero error communication of information. Shannon's result was a promise on the achievability on the amount of data one can transfer over a medium. Achieving those promises has spurred scientific interest since 1948. Significant effort has been spent to find practical codes which gets close to the Shannon limits. For some class of channels, codes which are capacity achieving has been found since then. Low Density Parity Check Codes (LDPC) is one such capacity achieving family of codes for the class of binary erasure channels. Recently, Arikan proposed a family of codes known as Polar codes which are found to be capacity achieving for binary input memoryless channels. Slowly but steadily the longstanding problem of achieving Shannon limit is thus getting settled. In order to realize a practical system which can achieve the Shannon limits, two important things are necessary. One of them is an efficient capacity achieving code sequence and the other is an implementable decoding rule. Both these require the knowledge of the probabilistic law of the channel through which communication take place. At the transmitter one needs to know the channel capacity whereas at the receiver a perfect knowledge of the channel is necessitated to build optimum decoder. The question of whether a decoder can be designed without knowing the underlying channel, yet we can do a reliable communication arises here. This is the subject of discussion in this report. Consider a situation where a communication system is to be designed without explicit knowledge about the channel. Here, neither the transmitter nor the receiver knows the exact channel law. Suppose, the possible list of channels is made available upfront to both entities (transmitter and receiver). Can we devise a reliable communication scheme, irrespective of the actual channel picked without both transmitter and receiver being aware of it. This is the central theme in what is known\footnote{Also referred as \textit{coding for class of channels} as discussed in \cite{paper:blackwell}, \cite{book:Wolfowitz}.} as \textit{coding for compound channels}\cite{book:Csiszar}. Designing a reliable communication system for compound channels essentially involve building a codebook at the transmitter and a decoding rule at the receiver. The encoder-decoder pair together must guarantee reliable communication over a set of channels. In the general setting, no feedback is assumed from the receiver to the transmitter. Thus, a single coding strategy (codebook) must be devised (and fixed) upfront prior to transmission. At the receiver end, the decoding strategy must be devised independent of any knowledge of the channel. Of course, the codebook devised at the sender is perfectly known to the receiver. The answer to the question on whether such a communication system can be build is on the affirmative. In order to talk about the existence of reliable communication strategies, one must first talk about the maximum possible rate, the capacity. The highest achievable rate in a compound setting is known as the \textit{compound capacity} or capacity of the family. This is analogous to the famous Shannon capacity being the ultimate limit on achievable rate for any single channel. The capacity of compound set of memoryless channels has been studied by Blackwell et al in \cite{paper:blackwell} and that of linear dispersive channels is investigated by Root and Varaiya in \cite{paper:root:varaiya}. Lapidoth and Telatar looked at the compound capacity for families of channels with memory, more specifically the finite state channels \cite{paper:lapidoth-telatar1998}. As a special case, they have also derived the compound channel capacity of a class of Gilbert-Elliot channels. A decoder which operates without the knowledge of the channel in this setup is called a universal decoder. It is known that Maximum Mutual Information (MMI) decoders proposed by Goppa are universal. MMI decoders compute the empirical mutual between a received codeword against the codebook and find the best matching word as the true estimate. The complexity of MMI decoder remain fixed even if we were to find structured codes. This motivate us to ask the question whether we can build a universal decoder which offer better structure. Decoding rules which brings additive nature were considered in the literature as a potential scheme. Our work in this has been driven by this line of thoughts. In this work, we focus on class of discrete memoryless channels (DMC) and more specifically binary memoryless channels. We show that it is possible to build a linear universal decoder for any compound binary memoryless channels. The recent introduction of Polar codes motivated us to look into their suitability to the compound channel setup. We have carried out a preliminary investigation in this direction. While it is not clear whether Polar codes are universal under the optimum universal decoding, we find that they are universal for certain restricted classes of compound BMC sets.

2009

Bits through Time

Elie Najm

In any communication system, there exist two dimensions through which the information at the source becomes distorted before reaching the destination: the noisy channel and time. Messages transmitted through a noisy channel are susceptible to modification in their content, due to the action of the noise of the channel. Claude E. Shannon, in his seminal paper of 1948 "A Mathematical Theory of Communication", introduces the bit as a unit of measure of information, and he lays down the theoretical foundations needed to understand the problem of sending bits reliably through a noisy channel. The distortion measure, which he used to quantify reliability, is the error probability. In his paper, Shannon shows that any channel is characterized by a number that he calls capacity: It represents the highest transmission rate that can be used to communicate information with, through this same channel, while guaranteeing a negligible error probability. Whereas, even if the messages are sent through a perfect channel, the time they take to reach their destination causes the receiver to acquire a distorted view of the status of the source that generated these messages. For instance, take the case of a monitor interested in the status of a distant process. A sender observes this process and, to keep the monitor up-to-date, sends updates to it. However, if, at any time t, the last received update at the monitor was generated at time u(t), then the information at the receiver reflects the status of the process at time u(t), not at time t. Hence, the monitor has a distorted version of reality. In fact, it has an obsolete version with an age of t-u(t). The concept of age as a distortion measure in communication systems was first used in 2011 by Kaul et al., in order to assess the performance of a given vehicular network. The aim of the authors was to come up with a transmission scheme that would minimize an age-related metric: the average age. Since then, a growing body of works has used this metric to evaluate the performance of multiple communication systems. The drive behind this interest lies in the importance that status-update applications are gaining in today's life (in vehicular networks, warehouse and environment surveillance, news feed,etc.). In this thesis, we choose age as a distortion measure and derive expressions for the average age and the average peak-age (another age-related metric) for different communication systems. Therefore, we divide this dissertation into two parts: In the first part, we assume that the the updates are transmitted through a noiseless channel that has a random service time. In the second part, we consider a special category of noisy channels, namely the erasure channel. In the first part of this thesis, in order to compute the age-related metrics, we employ queue-theoretic concepts. We study and compare the performance of various transmission schemes under different settings.We show that the optimal transmission scheme when the monitor is interested in a single source loses its optimality when another source of higher priority shares the system. In the second part of this thesis, we introduce, in our age calculations, the distortion caused by the erasure channel on the transmitted updates. In order to combat the erasures of the channel, we first consider two flavors of the hybrid automatic repeat request (HARQ). Finally, we focus on the optimal average age that could be achieved over an erasure channel.

EPFL2019

Asymptotic and finite-length optimization of LDPC codes

Abdelaziz Amraoui

This thesis addresses the problem of information transmission over noisy channels. In 1993, Berrou, Glavieux and Thitimajshima discovered Turbo-codes. These codes made it possible to achieve a very good performance at low decoding complexity. In hindsight, it was recognized that the underlying principle of using sparse graph codes in conjunction with message-passing decoding was the same as the one proposed in Gallager's remarkable thesis of 1963, although Gallager's work had all but been forgotten in the intervening 30 years. In 1997, there occurred a breakthrough in the analysis of this type of codes. Luby, Mitzenmacher, Shokrollahi, Spielman and Stemann were able to give a complete characterization of the behavior of Low-Density Parity-Check code ensembles in the infinite blocklength case when used over the binary erasure channel. Soon thereafter, Richardson and Urbanke extended their results to binary-input memoryless symmetric channels. In this thesis we present tools to analyze the performance of these types of codes and ways to optimize their parameters. The optimization for the infinite blocklength case is relatively straightforward and we give a simple and efficient method of doing so. However, this does not really solve the problem in practice, since the asymptotic analysis has only limited relevance for the short or moderate blocklengths that are typically used in practice. This brings us to the main objective of this thesis, which is to bridge the gap between the asymptotic case and the practical finite-length case. We follow the lead of Luby et al. by considering the binary erasure channel. We show that the performance of LDPC codes obeys a well-defined scaling law as the blocklength increases. This scaling law refines the asymptotic analysis and provides a good way to understand and approximate the behavior of LDPC codes of short to moderate length. We show how to compute the scaling parameters involved and demonstrate how to use the resulting approximation as a design and optimization tool.

EPFL2006