Channel capacity

Summary

Channel capacity, in electrical engineering, computer science, and information theory, is the tight upper bound on the rate at which information can be reliably transmitted over a communication channel. Following the terms of the noisy-channel coding theorem, the channel capacity of a given channel is the highest information rate (in units of information per unit time) that can be achieved with arbitrarily small error probability. Information theory, developed by Claude E. Shannon in 1948, defines the notion of channel capacity and provides a mathematical model by which it may be computed. The key result states that the capacity of the channel, as defined above, is given by the maximum of the mutual information between the input and output of the channel, where the maximization is with respect to the input distribution. The notion of channel capacity has been central to the development of modern wireline and wireless communication systems, with the advent of novel error correction coding mechanisms that have resulted in achieving performance very close to the limits promised by channel capacity. The basic mathematical model for a communication system is the following: where: is the message to be transmitted; is the channel input symbol ( is a sequence of symbols) taken in an alphabet ; is the channel output symbol ( is a sequence of symbols) taken in an alphabet ; is the estimate of the transmitted message; is the encoding function for a block of length ; is the noisy channel, which is modeled by a conditional probability distribution; and, is the decoding function for a block of length . Let and be modeled as random variables. Furthermore, let be the conditional probability distribution function of given , which is an inherent fixed property of the communication channel. Then the choice of the marginal distribution completely determines the joint distribution due to the identity which, in turn, induces a mutual information . The channel capacity is defined as where the supremum is taken over all possible choices of .

Environmental policies: designing acceptable road pricing and voluntary waste sorting schemes

Linda Melina Tesauro

Growing urban population implies many challenges for the municipalities in terms of mobility, housing, waste management or infrastructures. Public policies are thus needed to ensure a sustainable development. The main objective of this thesis is to analyze different environmental policies in the domain of mobility and waste management in order to help municipalities in designing more efficient measures.Firstly, Chapter 2 focuses on traffic congestion and in particular the acceptability of a congestion charge. We design a large survey with different plausible schemes for the Canton of Geneva, Switzerland and assess their acceptability with a discrete choice experiment (DCE). Results show that public support depends crucially on the policy design and the information provided. We find an important demand for exemptions and a preference for constant pricing. This implies a clear trade-off between efficiency and acceptability. However, the gap can be partly closed by information provision. Analyzing heterogeneity, we observe that preferences vary according to personal characteristics, especially where people live and how they commute.Chapter 3 analyzes the determinants of households' municipal waste sorting. We design a survey to investigate households' sorting motivation and use a DCE to assess households' waste sorting scheme preferences in the Canton of Geneva. We observe that households' waste sorting depends on personal characteristics such as sensitivity to the environment, guilty conscience or information level. However, it is the satisfaction with the existing sorting scheme that increases most the probability to sort waste. Our results show clear preferences for better infrastructures, but with thresholds. Interestingly, the best infrastructures and services are not always needed. By looking at heterogeneity and linking personal beliefs and characteristics with preferences, we find different groups sorting a similar number of categories, but with different underlying mechanisms like a lack of knowledge or a need for more convenient infrastructures and services.To complement our analysis on voluntary policies and in particular on the effectiveness of convenient infrastructures, Chapter 4 assesses a new voluntary environmental policy implemented in the Canton of Geneva and compares the results with a bag tax, a monetary incentive policy introduced in the neighboring canton, Vaud. The voluntary policy consists of the distribution to households of specific bins for organic waste to increase the sorting rate and decrease the amount of unsorted waste. We use a difference-in-differences methodology to assess the causal impact of the policy on organic waste as well as on overall waste generation. We find that the introduction of the voluntary policy increases significantly the proportion of households sorting organic waste. Interestingly, we observe some positive spillover effects on other waste sorted. By comparing the voluntary policy in the Canton of Geneva and the bag tax in the Canton of Vaud, we find similar effects on organic waste sorting. However, the impact of the voluntary policy is smaller on unsorted waste than the short-term effect of the bag tax.In conclusion, we show that price is not the only factor to consider in environmental policies. More stringent policies can be acceptable if well designed. Furthermore, the power of non-monetary incentives should not be underestimated.

EPFL2022

Active Debris Removal missions consist of sending a satellite in space and removing one or more debris from their current orbit. A key challenge is to obtain information about the uncooperative target. By gathering the velocity, position, and rotation of the desired object, the satellite is able to plan its trajectory and define the sequence of approach. It requires the use of a variety of sensors with often a high data rate. For this task, a dedicated payload computer is envisioned with the responsibility of processing the information from the various rendezvous sensors. This component has the goal to provide meaningful information to the main satellite computer about the targeted debris. The focus of this work is on the data processing, the number of elements, and the electrical energy with constraints due to internal communication.First, an avionic testbench was built at the EPFL Space Center to assess early hardware and software architectures. The goal is to enable Hardware-In-the-Loop testing while developing the payload computer. A communication data bus has been implemented between the Platform and the Payload On-Board Computer. Emphasis was placed on the reliability of the high-level protocol and multiple concepts for improvement were analyzed.In a second phase, the testbench has been extended to support other data buses. The aim was to develop a reliable and efficient backup or fall-back data bus in case of failure in the main link. Four data buses have been tested with extensive analyses on their resilience to error and the efficiency of their data exchange.In parallel, extensive work has been performed to develop a simulation and optimization tool. Its goal is to support the design of payload avionic architectures for ADR missions by providing trade-offs and analyses. In the first iteration, a simulator has been created with instances of various high-level elements modeled.The second iteration introduced the additional dimension of optimization. It is trying to determine the best set of instruments and algorithms to use. With this capability, numerous analyses have been conducted on the influence of various parameters linked to the general optimizer behavior. It allows us to better understand the strength and limitations of the tool.The third step regarding the tool was to start its verification. The task has been to develop an Hardware-In-the-Loop architecture to compare its behavior with the results of the optimizer. The implementation of various mock-up algorithms enables the verification of their models in the tool. These analyses guarantee the feasibility of the outputted solution.The last part was dedicated to the creation and analysis of a realistic payload avionic architecture. The goal was to test the capability of the tool with hardware elements inspired by actual components. This work has shown the procedure to efficiently use the tool in the design phase of a mission.In conclusion, the work on the communication between the Payload and the Platform On-Board Computer has brought valuable lessons and experiences to the projects. They can now be used for the establishment of the high-level protocol into ClearSpace-1 flight software. In addition, the optimizer created allows tackling the design of complex payload avionic architecture where mass saving and processing resources are crucial. It is an essential point to develop a highly efficient payload computer for an Active Debris Removal satellite.

EPFL2022

A Functional Perspective on Information Measures

Amedeo Roberto Esposito

Since the birth of Information Theory, researchers have defined and exploited various information measures, as well as endowed them with operational meanings. Some were born as a "solution to a problem", like Shannon's Entropy and Mutual Information. Others were the fruit of generalisation and the mathematical genius of bright minds like Rényi, Csizsár and Sibson. These powerful objects allow us to manipulate probabilities intuitively and seem always to be somehow connected to concrete settings in communication, coding or estimation theory. A common theme is: take a problem in one of these areas, try to control (upper or lower-bound) the expected value of some function of interest (often, probabilities of error) and, with enough work, an information measure appears as a fundamental limit of the problem. The most striking example of this is in Shannon's seminal paper in 1948: his purpose was to characterise the smallest possible expected length of a uniquely decodable encoding that compresses the realisations of a random variable. As he brilliantly proved, the smallest expected length one can hope for is the Entropy of the random variable. In establishing this connection, another quantity needed to be implicitly controlled: the Kraft's sum of the code. Seemingly unrelated before, these three objects joined forces in harmony to provide a beautiful and fundamental result. But why are they related? The answer seems to be: duality. Duality is an abstract notion commonly used in linear algebra and functional analysis. It has been expanded and generalised over the years. Several incarnations have been discovered throughout mathematics. One particular instance of this involves vector spaces: given two vector spaces and a "duality pairing" one can jump from one space to the other (its dual) through Legendre-Fenchel-like transforms. In the most common settings in Information Theory, the two spaces and the pairing are, respectively: 1) the space of (probability)measures defined on X; 2) the space of bounded functions defined on X; 3) the Lebesgue integral of the function (the expected value of the function if the measure is a probability measure). Once these are set, Legendre-Fenchel-like transforms allow us to connect a) a functional acting on the space described in 1), b) a functional acting on the space described in 2) and the anchor point is c) the (expected) value described in 3).These three pieces (a), b) and c)) represent the actors of many of the results provided in Information Theory. Once they are found, one usually bounds the functional described in b) and obtains a bound connecting the expected value and the functional of measures (e.g., an information measure). Going back to Shannon's result, fixed a random variable (and thus, a probability measure) and selected the function to be the length of a code: the functional a) is the Shannon Entropy of the source; the functional b) is the Kraft sum of the code; the pairing c) is the expected length of the code. We explore this connection and this pattern throughout the thesis. We will see how it can be found in notable results like Coding Theorems for one-to-one codes, Campbell's Coding Theorem, Arikan's Guessing Theorem, Fano-like and Transportation-Cost Inequalities and so on. Moreover, unearthing the pattern allows us to generalise it to other information measures and apply the technique in a variety of fields, including Learning Theory, Estimation Theory and Hypothesis Testing.

EPFL2022