Lecture

Shannon's Theorem

Graph Chat

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

In course

CS-119(a): Information, Computation, Communication

D'une part, le cours aborde: (1) la notion d'algorithme et de représentation de l'information, (2) l'échantillonnage d'un signal et la compression de données et (3) des aspects liés aux systèmes: ordinateur, mémoire, etc. D'autre part, le cours donne une i ...

Description

This lecture covers the basics of binary codes, including definitions, examples, and the concept of prefix-free binary codes. It then introduces Shannon's Theorem, stating that for any prefix-free binary code used to represent a given sequence, the entropy of the sequence is always less than or equal to the average code length. The lecture also explains Kraft's inequality and provides a detailed demonstration of Shannon's Theorem, showcasing the relationship between entropy and code length. Additional inequalities related to entropy and code length are discussed, highlighting the limits of lossless data compression.

In MOOC

Information, Computation, Communication: Introduction to computational thinking

In the first part of the course, we'll look at how algorithms can be used to solve a problem in a very concrete way, leading us on to one of the great questions of modern theoretical computer science. The second part of the course will be devoted to information and communication: we'll be looking at a number of topics, including information representation, signal processing, data compression, communication and cryptography.

Instructors (3)

Olivier Lévêque

Olivier Lévêque was born in Switzerland in 1971. He received the physics diploma from EPFL in 1995 and completed his PhD in mathematics at EPFL in 2001. Since then, he has been with the Laboratory of Information Theory at EPFL. He spent the academical year 2005-2006 at the Electrical Engineering Department of Stanford University, where he was appointed as lecturer. His research interests include stochastic analysis, random matrices, wireless communications and information theory.

Dan-Cristian Tomozei

Mirjana Stojilovic

Mirjana Stojilović received the Dipl. Ing. and Ph.D. degrees from the School of Electrical Engineering, University of Belgrade, in 2006 and 2013, respectively. From 2010 to 2013, she was collaborating with the Processor Architecture Laboratory at EPFL, visiting periodically as a Guest Researcher. From 2013 to 2016, she was working at the University of Applied Sciences Western Switzerland as a senior researcher, and at EPFL as a lecturer. She joined Parallel Systems Architecture Lab at EPFL in October 2016. Mirjana's main research interests include electronic design automation, reconfigurable computing, electromagnetic-compatibility and signal-integrity issues, and hardware security. Mirjana Stojilović serves on the program committee of the FPGA, FPL, and FCCM conferences and as a reviewer for IEEE TCAD, TVLSI, TC, TEMC, IEEE Access and ACM TRETS. She received the Best Paper Award at 2016 International Symposium on Electromagnetic Compatibility (EMC Europe 2016), Young Scientist Award at 33rd International Conference on Lightning Protection (ICLP2016), and the Young Author Best Paper Award at the 20th Telecommunication Forum in Belgrade (TELFOR 2012). In 2015, the EPFL School of Computer and Communication Sciences (IC) presented her with the Teaching Award.

Official source

Quiz

Related concepts (32)

Data compression

In information theory, data compression, source coding, or bit-rate reduction is the process of encoding information using fewer bits than the original representation. Any particular compression is either lossy or lossless. Lossless compression reduces bits by identifying and eliminating statistical redundancy. No information is lost in lossless compression. Lossy compression reduces bits by removing unnecessary or less important information.

Lossy compression

In information technology, lossy compression or irreversible compression is the class of data compression methods that uses inexact approximations and partial data discarding to represent the content. These techniques are used to reduce data size for storing, handling, and transmitting content. The different versions of the photo of the cat on this page show how higher degrees of approximation create coarser images as more details are removed. This is opposed to lossless data compression (reversible data compression) which does not degrade the data.

Lossless compression

Lossless compression is a class of data compression that allows the original data to be perfectly reconstructed from the compressed data with no loss of information. Lossless compression is possible because most real-world data exhibits statistical redundancy. By contrast, lossy compression permits reconstruction only of an approximation of the original data, though usually with greatly improved compression rates (and therefore reduced media sizes).

Shannon's source coding theorem

In information theory, Shannon's source coding theorem (or noiseless coding theorem) establishes the limits to possible data compression, and the operational meaning of the Shannon entropy. Named after Claude Shannon, the source coding theorem shows that (in the limit, as the length of a stream of independent and identically-distributed random variable (i.i.d.) data tends to infinity) it is impossible to compress the data such that the code rate (average number of bits per symbol) is less than the Shannon entropy of the source, without it being virtually certain that information will be lost.

Compression artifact

A compression artifact (or artefact) is a noticeable distortion of media (including , audio, and video) caused by the application of lossy compression. Lossy data compression involves discarding some of the media's data so that it becomes small enough to be stored within the desired or transmitted (streamed) within the available bandwidth (known as the data rate or bit rate). If the compressor cannot store enough data in the compressed version, the result is a loss of quality, or introduction of artifacts.

Related lectures (64)

Data Compression and Shannon-Fano Algorithm

Explores the Shannon-Fano algorithm for data compression and its efficiency in creating unique binary codes for letters.

Data Compression and Shannon's Theorem: Entropy Calculation Example

Demonstrates the calculation of entropy for a specific example, resulting in an entropy value of 2.69.

Entropy and Algorithms: Applications in Sorting and Weighing

Covers the application of entropy in algorithms, focusing on sorting and decision-making strategies.

Data Compression and Shannon's Theorem Summary

Summarizes Shannon's theorem, emphasizing the importance of entropy in data compression.

Source Coding Theorem