Typical set | EPFL Graph Search

Are you an EPFL student looking for a semester project?

Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.

In information theory, the typical set is a set of sequences whose probability is close to two raised to the negative power of the entropy of their source distribution. That this set has total probability close to one is a consequence of the asymptotic equipartition property (AEP) which is a kind of law of large numbers. The notion of typicality is only concerned with the probability of a sequence and not the actual sequence itself. This has great use in compression theory as it provides a theoretical means for compressing data, allowing us to represent any sequence Xn using nH(X) bits on average, and, hence, justifying the use of entropy as a measure of information from a source. The AEP can also be proven for a large class of stationary ergodic processes, allowing typical set to be defined in more general cases. (Weakly) typical sequences (weak typicality, entropy typicality) If a sequence x1, ..., xn is drawn from an i.i.d. distribution X defined over a finite

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related publications (8)

Related publications

Related people (3)

Related people

Related units (1)

Related units

Related concepts (1)

Related concepts

Related courses (6)

Related courses

Related lectures (6)

Related lectures

Towards an algebraic network information theory: Simultaneous joint typicality decoding

Chen Feng, Michael Christoph Gastpar, Sung Hoon Lim, Adriano Pastore

Recent work has employed joint typicality encoding and decoding of nested linear code ensembles to generalize the compute-forward strategy to discrete memoryless multiple-access channels (MACs). An appealing feature of these nested linear code ensembles is that the coding strategies and error probability bounds are conceptually similar to classical techniques for random i.i.d. code ensembles. In this paper, we consider the problem of recovering K linearly independent combinations over a K-user MAC, i.e., recovering the messages in their entirety via nested linear codes. While the MAC rate region is well-understood for random i.i.d. code ensembles, new techniques are needed to handle the statistical dependencies between competing codeword K-tuples that occur in nested linear code ensembles.

2017

Towards an Algebraic Network Information Theory: Distributed Lossy Computation of Linear Functions

Chen Feng, Michael Christoph Gastpar, Sung Hoon Lim, Adriano Pastore

Consider the important special case of the K-user distributed source coding problem where the decoder only wishes to recover one or more linear combinations of the sources. The work of Körner and Marton demonstrated that, in some cases, the optimal rate region is attained by random linear codes, and strictly improves upon the best-known achievable rate region established via random i.i.d. codes. Recent efforts have sought to develop a framework for characterizing the achievable rate region for nested linear codes via joint typicality encoding and decoding. Here, we make further progress along this direction by proposing an achievable rate region for simultaneous joint typicality decoding of nested linear codes. Our approach generalizes the results of Körner and Marton to computing an arbitrary number of linear combinations and to the lossy computation setting.

2019

A joint typicality approach to compute-forward

Chen Feng, Michael Christoph Gastpar, Sung Hoon Lim

A general framework for analyzing linear codes with joint typicality encoders and decoders is presented. Using this approach, we provide a new perspective on the compute-forward framework. In particular, an achievable rate region for computing the weighted sum of nested linear codewords over a discrete memoryless multiple access channel (MAC) is established. When specialized to the Gaussian MAC, we recover the lattice-based compute-forward rate region by Nazer and Gastpar, providing a unified treatment over both discrete memoryless and Gaussian networks. By further utilizing simultaneous joint typicality decoders, we provide a joint decoding rate region for computing two linear combinations of nested linear codewords from K-senders. Our result provides some insight on one of the main open problems in the compute-forward framework, the joint decoding rate region of compute-forward.

2015

Information theory

Information theory is the mathematical study of the quantification, storage, and communication of information. The field was originally established by the works of Harry Nyquist and Ralph Hartley, in

COM-621: Advanced Topics in Information Theory

The class will focus on information-theoretic progress of the last decade. Topics include: Network Information Theory ; Information Measures: definitions, properties, and applications to probabilistic models.

CS-523: Advanced topics on privacy enhancing technologies

This advanced course will provide students with the knowledge to tackle the design of privacy-preserving ICT systems. Students will learn about existing technologies to prect privacy, and how to evaluate the protection they provide.

COM-622: Topics in information-theoretic cryptography

Information-theoretic methods and their application to secrecy & privacy. Perfect information-theoretic secrecy. Randomness extraction & privacy amplification. Secret key generation from common randomness. Measures of information leakage incl. differential privacy, perfect privacy, & mutual info.